1 //
2 // Copyright 2017 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // ResourceMap:
7 // An optimized resource map which packs the first set of allocated objects into a
8 // flat array, and then falls back to an unordered map for the higher handle values.
9 //
10
11 #ifndef LIBANGLE_RESOURCE_MAP_H_
12 #define LIBANGLE_RESOURCE_MAP_H_
13
14 #include "libANGLE/angletypes.h"
15
16 namespace gl
17 {
18
19 template <typename ResourceType, typename IDType>
20 class ResourceMap final : angle::NonCopyable
21 {
22 public:
23 ResourceMap();
24 ~ResourceMap();
25
query(IDType id)26 ANGLE_INLINE ResourceType *query(IDType id) const
27 {
28 GLuint handle = GetIDValue(id);
29 if (handle < mFlatResourcesSize)
30 {
31 ResourceType *value = mFlatResources[handle];
32 return (value == InvalidPointer() ? nullptr : value);
33 }
34 auto it = mHashedResources.find(handle);
35 return (it == mHashedResources.end() ? nullptr : it->second);
36 }
37
38 // Returns true if the handle was reserved. Not necessarily if the resource is created.
39 bool contains(IDType id) const;
40
41 // Returns the element that was at this location.
42 bool erase(IDType id, ResourceType **resourceOut);
43
44 void assign(IDType id, ResourceType *resource);
45
46 // Clears the map.
47 void clear();
48
49 using IndexAndResource = std::pair<GLuint, ResourceType *>;
50 using HashMap = std::unordered_map<GLuint, ResourceType *>;
51
52 class Iterator final
53 {
54 public:
55 bool operator==(const Iterator &other) const;
56 bool operator!=(const Iterator &other) const;
57 Iterator &operator++();
58 const IndexAndResource *operator->() const;
59 const IndexAndResource &operator*() const;
60
61 private:
62 friend class ResourceMap;
63 Iterator(const ResourceMap &origin,
64 GLuint flatIndex,
65 typename HashMap::const_iterator hashIndex,
66 bool skipNulls);
67 void updateValue();
68
69 const ResourceMap &mOrigin;
70 GLuint mFlatIndex;
71 typename HashMap::const_iterator mHashIndex;
72 IndexAndResource mValue;
73 bool mSkipNulls;
74 };
75
76 // null values represent reserved handles.
77 Iterator begin() const;
78 Iterator end() const;
79 Iterator find(IDType handle) const;
80
81 Iterator beginWithNull() const;
82 Iterator endWithNull() const;
83
84 // Not a constant-time operation, should only be used for verification.
85 bool empty() const;
86
87 private:
88 friend class Iterator;
89
90 GLuint nextResource(size_t flatIndex, bool skipNulls) const;
91
92 // constexpr methods cannot contain reinterpret_cast, so we need a static method.
93 static ResourceType *InvalidPointer();
94 static constexpr intptr_t kInvalidPointer = static_cast<intptr_t>(-1);
95
96 // Start with 32 maximum elements in the map, which can grow.
97 static constexpr size_t kInitialFlatResourcesSize = 0x20;
98
99 // Experimental testing suggests that 16k is a reasonable upper limit.
100 static constexpr size_t kFlatResourcesLimit = 0x4000;
101
102 // Size of one map element.
103 static constexpr size_t kElementSize = sizeof(ResourceType *);
104
105 size_t mFlatResourcesSize;
106 ResourceType **mFlatResources;
107
108 // A map of GL objects indexed by object ID.
109 HashMap mHashedResources;
110 };
111
112 template <typename ResourceType, typename IDType>
ResourceMap()113 ResourceMap<ResourceType, IDType>::ResourceMap()
114 : mFlatResourcesSize(kInitialFlatResourcesSize),
115 mFlatResources(new ResourceType *[kInitialFlatResourcesSize])
116 {
117 memset(mFlatResources, kInvalidPointer, mFlatResourcesSize * kElementSize);
118 }
119
120 template <typename ResourceType, typename IDType>
~ResourceMap()121 ResourceMap<ResourceType, IDType>::~ResourceMap()
122 {
123 ASSERT(empty());
124 delete[] mFlatResources;
125 }
126
127 template <typename ResourceType, typename IDType>
contains(IDType id)128 ANGLE_INLINE bool ResourceMap<ResourceType, IDType>::contains(IDType id) const
129 {
130 GLuint handle = GetIDValue(id);
131 if (handle < mFlatResourcesSize)
132 {
133 return (mFlatResources[handle] != InvalidPointer());
134 }
135 return (mHashedResources.find(handle) != mHashedResources.end());
136 }
137
138 template <typename ResourceType, typename IDType>
erase(IDType id,ResourceType ** resourceOut)139 bool ResourceMap<ResourceType, IDType>::erase(IDType id, ResourceType **resourceOut)
140 {
141 GLuint handle = GetIDValue(id);
142 if (handle < mFlatResourcesSize)
143 {
144 auto &value = mFlatResources[handle];
145 if (value == InvalidPointer())
146 {
147 return false;
148 }
149 *resourceOut = value;
150 value = InvalidPointer();
151 }
152 else
153 {
154 auto it = mHashedResources.find(handle);
155 if (it == mHashedResources.end())
156 {
157 return false;
158 }
159 *resourceOut = it->second;
160 mHashedResources.erase(it);
161 }
162 return true;
163 }
164
165 template <typename ResourceType, typename IDType>
assign(IDType id,ResourceType * resource)166 void ResourceMap<ResourceType, IDType>::assign(IDType id, ResourceType *resource)
167 {
168 GLuint handle = GetIDValue(id);
169 if (handle < kFlatResourcesLimit)
170 {
171 if (handle >= mFlatResourcesSize)
172 {
173 // Use power-of-two.
174 size_t newSize = mFlatResourcesSize;
175 while (newSize <= handle)
176 {
177 newSize *= 2;
178 }
179
180 ResourceType **oldResources = mFlatResources;
181
182 mFlatResources = new ResourceType *[newSize];
183 memset(&mFlatResources[mFlatResourcesSize], kInvalidPointer,
184 (newSize - mFlatResourcesSize) * kElementSize);
185 memcpy(mFlatResources, oldResources, mFlatResourcesSize * kElementSize);
186 mFlatResourcesSize = newSize;
187 delete[] oldResources;
188 }
189 ASSERT(mFlatResourcesSize > handle);
190 mFlatResources[handle] = resource;
191 }
192 else
193 {
194 mHashedResources[handle] = resource;
195 }
196 }
197
198 template <typename ResourceType, typename IDType>
begin()199 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::begin()
200 const
201 {
202 return Iterator(*this, nextResource(0, true), mHashedResources.begin(), true);
203 }
204
205 template <typename ResourceType, typename IDType>
end()206 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::end() const
207 {
208 return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end(), true);
209 }
210
211 template <typename ResourceType, typename IDType>
212 typename ResourceMap<ResourceType, IDType>::Iterator
beginWithNull()213 ResourceMap<ResourceType, IDType>::beginWithNull() const
214 {
215 return Iterator(*this, nextResource(0, false), mHashedResources.begin(), false);
216 }
217
218 template <typename ResourceType, typename IDType>
219 typename ResourceMap<ResourceType, IDType>::Iterator
endWithNull()220 ResourceMap<ResourceType, IDType>::endWithNull() const
221 {
222 return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end(), false);
223 }
224
225 template <typename ResourceType, typename IDType>
find(IDType handle)226 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::find(
227 IDType handle) const
228 {
229 if (handle < mFlatResourcesSize)
230 {
231 return (mFlatResources[handle] != InvalidPointer()
232 ? Iterator(handle, mHashedResources.begin())
233 : end());
234 }
235 else
236 {
237 return mHashedResources.find(handle);
238 }
239 }
240
241 template <typename ResourceType, typename IDType>
empty()242 bool ResourceMap<ResourceType, IDType>::empty() const
243 {
244 return (begin() == end());
245 }
246
247 template <typename ResourceType, typename IDType>
clear()248 void ResourceMap<ResourceType, IDType>::clear()
249 {
250 memset(mFlatResources, kInvalidPointer, kInitialFlatResourcesSize * kElementSize);
251 mFlatResourcesSize = kInitialFlatResourcesSize;
252 mHashedResources.clear();
253 }
254
255 template <typename ResourceType, typename IDType>
nextResource(size_t flatIndex,bool skipNulls)256 GLuint ResourceMap<ResourceType, IDType>::nextResource(size_t flatIndex, bool skipNulls) const
257 {
258 for (size_t index = flatIndex; index < mFlatResourcesSize; index++)
259 {
260 if ((mFlatResources[index] != nullptr || !skipNulls) &&
261 mFlatResources[index] != InvalidPointer())
262 {
263 return static_cast<GLuint>(index);
264 }
265 }
266 return static_cast<GLuint>(mFlatResourcesSize);
267 }
268
269 template <typename ResourceType, typename IDType>
270 // static
InvalidPointer()271 ResourceType *ResourceMap<ResourceType, IDType>::InvalidPointer()
272 {
273 return reinterpret_cast<ResourceType *>(kInvalidPointer);
274 }
275
276 template <typename ResourceType, typename IDType>
Iterator(const ResourceMap & origin,GLuint flatIndex,typename ResourceMap<ResourceType,IDType>::HashMap::const_iterator hashIndex,bool skipNulls)277 ResourceMap<ResourceType, IDType>::Iterator::Iterator(
278 const ResourceMap &origin,
279 GLuint flatIndex,
280 typename ResourceMap<ResourceType, IDType>::HashMap::const_iterator hashIndex,
281 bool skipNulls)
282 : mOrigin(origin), mFlatIndex(flatIndex), mHashIndex(hashIndex), mSkipNulls(skipNulls)
283 {
284 updateValue();
285 }
286
287 template <typename ResourceType, typename IDType>
288 bool ResourceMap<ResourceType, IDType>::Iterator::operator==(const Iterator &other) const
289 {
290 return (mFlatIndex == other.mFlatIndex && mHashIndex == other.mHashIndex);
291 }
292
293 template <typename ResourceType, typename IDType>
294 bool ResourceMap<ResourceType, IDType>::Iterator::operator!=(const Iterator &other) const
295 {
296 return !(*this == other);
297 }
298
299 template <typename ResourceType, typename IDType>
300 typename ResourceMap<ResourceType, IDType>::Iterator &ResourceMap<ResourceType, IDType>::Iterator::
301 operator++()
302 {
303 if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
304 {
305 mFlatIndex = mOrigin.nextResource(mFlatIndex + 1, mSkipNulls);
306 }
307 else
308 {
309 mHashIndex++;
310 }
311 updateValue();
312 return *this;
313 }
314
315 template <typename ResourceType, typename IDType>
316 const typename ResourceMap<ResourceType, IDType>::IndexAndResource
317 *ResourceMap<ResourceType, IDType>::Iterator::operator->() const
318 {
319 return &mValue;
320 }
321
322 template <typename ResourceType, typename IDType>
323 const typename ResourceMap<ResourceType, IDType>::IndexAndResource
324 &ResourceMap<ResourceType, IDType>::Iterator::operator*() const
325 {
326 return mValue;
327 }
328
329 template <typename ResourceType, typename IDType>
updateValue()330 void ResourceMap<ResourceType, IDType>::Iterator::updateValue()
331 {
332 if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
333 {
334 mValue.first = mFlatIndex;
335 mValue.second = mOrigin.mFlatResources[mFlatIndex];
336 }
337 else if (mHashIndex != mOrigin.mHashedResources.end())
338 {
339 mValue.first = mHashIndex->first;
340 mValue.second = mHashIndex->second;
341 }
342 }
343
344 } // namespace gl
345
346 #endif // LIBANGLE_RESOURCE_MAP_H_
347