e59ec033a8fef24dc1af72e52b2e18a9a576fcb2
[WebKit-https.git] / Source / JavaScriptCore / runtime / WeakGCMap.h
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 "Weak.h"
30 #include "WeakInlines.h"
31 #include <wtf/HashMap.h>
32
33 namespace JSC {
34
35 // A HashMap with Weak<JSCell> values, which automatically removes values once they're garbage collected.
36
37 template<typename KeyArg, typename ValueArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
38     typename KeyTraitsArg = HashTraits<KeyArg>>
39 class WeakGCMap {
40     WTF_MAKE_FAST_ALLOCATED;
41     typedef Weak<ValueArg> ValueType;
42     typedef HashMap<KeyArg, ValueType, HashArg, KeyTraitsArg> HashMapType;
43
44 public:
45     typedef typename HashMapType::KeyType KeyType;
46     typedef typename HashMapType::AddResult AddResult;
47     typedef typename HashMapType::iterator iterator;
48     typedef typename HashMapType::const_iterator const_iterator;
49
50     WeakGCMap()
51         : m_gcThreshold(minGCThreshold)
52     {
53     }
54
55     ValueArg* get(const KeyType& key) const
56     {
57         return m_map.get(key);
58     }
59
60     AddResult set(const KeyType& key, ValueType value)
61     {
62         gcMapIfNeeded();
63         return m_map.set(key, std::move(value));
64     }
65
66     ALWAYS_INLINE AddResult add(const KeyType& key, ValueType value)
67     {
68         gcMapIfNeeded();
69         AddResult addResult = m_map.fastAdd(key, nullptr);
70         if (!addResult.iterator->value) { // New value or found a zombie value.
71             addResult.isNewEntry = true;
72             addResult.iterator->value = std::move(value);
73         }
74         return addResult;
75     }
76
77     bool remove(const KeyType& key)
78     {
79         return m_map.remove(key);
80     }
81
82     void clear()
83     {
84         m_map.clear();
85     }
86
87     iterator find(const KeyType& key)
88     {
89         iterator it = m_map.find(key);
90         iterator end = m_map.end();
91         if (it != end && !it->value) // Found a zombie value.
92             return end;
93         return it;
94     }
95
96     const_iterator find(const KeyType& key) const
97     {
98         return const_cast<WeakGCMap*>(this)->find(key);
99     }
100
101     bool contains(const KeyType& key) const
102     {
103         return find(key) != m_map.end();
104     }
105
106 private:
107     static const int minGCThreshold = 3;
108
109     NEVER_INLINE void gcMap()
110     {
111         Vector<KeyType, 4> zombies;
112
113         for (iterator it = m_map.begin(), end = m_map.end(); it != end; ++it) {
114             if (!it->value)
115                 zombies.append(it->key);
116         }
117
118         for (size_t i = 0; i < zombies.size(); ++i)
119             m_map.remove(zombies[i]);
120     }
121
122     void gcMapIfNeeded()
123     {
124         if (m_map.size() < m_gcThreshold)
125             return;
126
127         gcMap();
128         m_gcThreshold = std::max(minGCThreshold, m_map.size() * 2 - 1);
129     }
130
131     HashMapType m_map;
132     int m_gcThreshold;
133 };
134
135 template<typename KeyArg, typename RawMappedArg, typename HashArg, typename KeyTraitsArg>
136 const int WeakGCMap<KeyArg, RawMappedArg, HashArg, KeyTraitsArg>::minGCThreshold;
137
138 } // namespace JSC
139
140 #endif // WeakGCMap_h