1 // Copyright 2019 The SwiftShader Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef VK_DEBUG_WEAKMAP_HPP_
16 #define VK_DEBUG_WEAKMAP_HPP_
17
18 #include <map>
19 #include <memory>
20
21 namespace vk {
22 namespace dbg {
23
24 // WeakMap is an associative container of keys of type K to values of type
25 // std::weak_ptr<V>.
26 // WeakMap's iterators will skip over elements where the value has no more
27 // remaining std::shared_ptr<V> references.
28 // WeakMap is not thread-safe and requires the use of an external mutex to be
29 // used by multiple threads, concurrently.
30 template<typename K, typename V>
31 class WeakMap
32 {
33 using Map = std::map<K, std::weak_ptr<V>>;
34 using MapIterator = typename Map::const_iterator;
35
36 public:
37 class iterator
38 {
39 public:
40 inline iterator(const MapIterator &it, const MapIterator &end);
41 inline void operator++();
42 inline bool operator==(const iterator &) const;
43 inline bool operator!=(const iterator &) const;
44 inline std::pair<K, std::shared_ptr<V>> operator*() const;
45
46 private:
47 void skipNull();
48
49 MapIterator it;
50 const MapIterator end;
51 std::shared_ptr<V> sptr;
52 };
53
54 // begin() returns an iterator to the start of the map.
55 inline iterator begin() const;
56
57 // end() returns an iterator to the end of the map.
58 inline iterator end() const;
59
60 // approx_size() returns an approximate number of entries in the map. This
61 // is guaranteed to be greater than or equal to the actual number of
62 // elements in the map.
63 inline size_t approx_size() const;
64
65 // get() returns the std::shared_ptr<V> value for the given key, or nullptr
66 // if the map does not contain the key, or the last remaining
67 // std::shared_ptr<V> reference to the value has been dropped.
68 inline std::shared_ptr<V> get(const K &key) const;
69
70 // add() attempts to insert the key-value pair into the map.
71 // add() returns true if there was no existing entry with the given key,
72 // and the pair was added, otherwise false.
73 inline bool add(const K &key, const std::shared_ptr<V> &val);
74
75 // remove() attempts to remove the entry with the given key from the map.
76 // remove() returns true if there was no existing entry with the given key,
77 // and the entry was removed, otherwise false.
78 inline bool remove(const K &key);
79
80 private:
81 // reap() removes any entries that have values with no external references.
82 inline void reap();
83
84 Map map;
85 size_t reapAtSize = 32;
86 };
87
88 template<typename K, typename V>
iterator(const MapIterator & it,const MapIterator & end)89 WeakMap<K, V>::iterator::iterator(const MapIterator &it, const MapIterator &end)
90 : it(it)
91 , end(end)
92 {
93 skipNull();
94 }
95
96 template<typename K, typename V>
operator ++()97 void WeakMap<K, V>::iterator::operator++()
98 {
99 it++;
100 skipNull();
101 }
102
103 template<typename K, typename V>
skipNull()104 void WeakMap<K, V>::iterator::skipNull()
105 {
106 for(; it != end; ++it)
107 {
108 // Hold on to the shared_ptr when pointing at this map element.
109 // This ensures that the object is not released.
110 sptr = it->second.lock();
111 if(sptr)
112 {
113 return;
114 }
115 }
116 }
117
118 template<typename K, typename V>
operator ==(const iterator & rhs) const119 bool WeakMap<K, V>::iterator::operator==(const iterator &rhs) const
120 {
121 return it == rhs.it;
122 }
123
124 template<typename K, typename V>
operator !=(const iterator & rhs) const125 bool WeakMap<K, V>::iterator::operator!=(const iterator &rhs) const
126 {
127 return it != rhs.it;
128 }
129
130 template<typename K, typename V>
operator *() const131 std::pair<K, std::shared_ptr<V>> WeakMap<K, V>::iterator::operator*() const
132 {
133 return { it->first, sptr };
134 }
135
136 template<typename K, typename V>
begin() const137 typename WeakMap<K, V>::iterator WeakMap<K, V>::begin() const
138 {
139 return iterator(map.begin(), map.end());
140 }
141
142 template<typename K, typename V>
end() const143 typename WeakMap<K, V>::iterator WeakMap<K, V>::end() const
144 {
145 return iterator(map.end(), map.end());
146 }
147
148 template<typename K, typename V>
approx_size() const149 size_t WeakMap<K, V>::approx_size() const
150 {
151 return map.size();
152 }
153
154 template<typename K, typename V>
get(const K & key) const155 std::shared_ptr<V> WeakMap<K, V>::get(const K &key) const
156 {
157 auto it = map.find(key);
158 return (it != map.end()) ? it->second.lock() : nullptr;
159 }
160
161 template<typename K, typename V>
add(const K & key,const std::shared_ptr<V> & val)162 bool WeakMap<K, V>::add(const K &key, const std::shared_ptr<V> &val)
163 {
164 if(map.size() > reapAtSize)
165 {
166 reap();
167 reapAtSize = map.size() * 2 + 32;
168 }
169 return map.emplace(key, val).second;
170 }
171
172 template<typename K, typename V>
remove(const K & key)173 bool WeakMap<K, V>::remove(const K &key)
174 {
175 return map.erase(key) > 0;
176 }
177
178 template<typename K, typename V>
reap()179 void WeakMap<K, V>::reap()
180 {
181 for(auto it = map.begin(); it != map.end();)
182 {
183 if(it->second.expired())
184 {
185 map.erase(it++);
186 }
187 else
188 {
189 ++it;
190 }
191 }
192 }
193
194 } // namespace dbg
195 } // namespace vk
196
197 #endif // VK_DEBUG_WEAKMAP_HPP_
198