1 /*
2 * Copyright (C) 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 #ifndef WeakGCMap_h
27 #define WeakGCMap_h
28
29 #include "Collector.h"
30 #include <wtf/HashMap.h>
31
32 namespace JSC {
33
34 class JSCell;
35
36 // A HashMap whose get() function returns emptyValue() for cells awaiting destruction.
37 template<typename KeyType, typename MappedType>
38 class WeakGCMap : public FastAllocBase {
39 /*
40 Invariants:
41 * A value enters the WeakGCMap marked. (Guaranteed by set().)
42 * A value that becomes unmarked leaves the WeakGCMap before being recycled. (Guaranteed by the value's destructor removing it from the WeakGCMap.)
43 * A value that becomes unmarked leaves the WeakGCMap before becoming marked again. (Guaranteed by all destructors running before the mark phase begins.)
44 * During the mark phase, all values in the WeakGCMap are valid. (Guaranteed by all destructors running before the mark phase begins.)
45 */
46
47 public:
48 typedef typename HashMap<KeyType, MappedType>::iterator iterator;
49 typedef typename HashMap<KeyType, MappedType>::const_iterator const_iterator;
50
isEmpty()51 bool isEmpty() { return m_map.isEmpty(); }
52
53 MappedType get(const KeyType& key) const;
54 pair<iterator, bool> set(const KeyType&, const MappedType&);
55 MappedType take(const KeyType& key);
56
57 // These unchecked functions provide access to a value even if the value's
58 // mark bit is not set. This is used, among other things, to retrieve values
59 // during the GC mark phase, which begins by clearing all mark bits.
60
uncheckedGet(const KeyType & key)61 MappedType uncheckedGet(const KeyType& key) const { return m_map.get(key); }
62 bool uncheckedRemove(const KeyType&, const MappedType&);
63
uncheckedBegin()64 iterator uncheckedBegin() { return m_map.begin(); }
uncheckedEnd()65 iterator uncheckedEnd() { return m_map.end(); }
66
uncheckedBegin()67 const_iterator uncheckedBegin() const { return m_map.begin(); }
uncheckedEnd()68 const_iterator uncheckedEnd() const { return m_map.end(); }
69
70 private:
71 HashMap<KeyType, MappedType> m_map;
72 };
73
74 template<typename KeyType, typename MappedType>
get(const KeyType & key)75 inline MappedType WeakGCMap<KeyType, MappedType>::get(const KeyType& key) const
76 {
77 MappedType result = m_map.get(key);
78 if (result == HashTraits<MappedType>::emptyValue())
79 return result;
80 if (!Heap::isCellMarked(result))
81 return HashTraits<MappedType>::emptyValue();
82 return result;
83 }
84
85 template<typename KeyType, typename MappedType>
take(const KeyType & key)86 MappedType WeakGCMap<KeyType, MappedType>::take(const KeyType& key)
87 {
88 MappedType result = m_map.take(key);
89 if (result == HashTraits<MappedType>::emptyValue())
90 return result;
91 if (!Heap::isCellMarked(result))
92 return HashTraits<MappedType>::emptyValue();
93 return result;
94 }
95
96 template<typename KeyType, typename MappedType>
set(const KeyType & key,const MappedType & value)97 pair<typename HashMap<KeyType, MappedType>::iterator, bool> WeakGCMap<KeyType, MappedType>::set(const KeyType& key, const MappedType& value)
98 {
99 Heap::markCell(value); // If value is newly allocated, it's not marked, so mark it now.
100 pair<iterator, bool> result = m_map.add(key, value);
101 if (!result.second) { // pre-existing entry
102 result.second = !Heap::isCellMarked(result.first->second);
103 result.first->second = value;
104 }
105 return result;
106 }
107
108 template<typename KeyType, typename MappedType>
uncheckedRemove(const KeyType & key,const MappedType & value)109 bool WeakGCMap<KeyType, MappedType>::uncheckedRemove(const KeyType& key, const MappedType& value)
110 {
111 iterator it = m_map.find(key);
112 if (it == m_map.end())
113 return false;
114 if (it->second != value)
115 return false;
116 m_map.remove(it);
117 return true;
118 }
119
120 } // namespace JSC
121
122 #endif // WeakGCMap_h
123