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 = GLuint>
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 void updateValue();
67
68 const ResourceMap &mOrigin;
69 GLuint mFlatIndex;
70 typename HashMap::const_iterator mHashIndex;
71 IndexAndResource mValue;
72 };
73
74 // null values represent reserved handles.
75 Iterator begin() const;
76 Iterator end() const;
77 Iterator find(IDType handle) const;
78
79 // Not a constant-time operation, should only be used for verification.
80 bool empty() const;
81
82 private:
83 friend class Iterator;
84
85 GLuint nextNonNullResource(size_t flatIndex) const;
86
87 // constexpr methods cannot contain reinterpret_cast, so we need a static method.
88 static ResourceType *InvalidPointer();
89 static constexpr intptr_t kInvalidPointer = static_cast<intptr_t>(-1);
90
91 // Start with 32 maximum elements in the map, which can grow.
92 static constexpr size_t kInitialFlatResourcesSize = 0x20;
93
94 // Experimental testing suggests that 16k is a reasonable upper limit.
95 static constexpr size_t kFlatResourcesLimit = 0x4000;
96
97 // Size of one map element.
98 static constexpr size_t kElementSize = sizeof(ResourceType *);
99
100 size_t mFlatResourcesSize;
101 ResourceType **mFlatResources;
102
103 // A map of GL objects indexed by object ID.
104 HashMap mHashedResources;
105 };
106
107 template <typename ResourceType, typename IDType>
ResourceMap()108 ResourceMap<ResourceType, IDType>::ResourceMap()
109 : mFlatResourcesSize(kInitialFlatResourcesSize),
110 mFlatResources(new ResourceType *[kInitialFlatResourcesSize])
111 {
112 memset(mFlatResources, kInvalidPointer, mFlatResourcesSize * kElementSize);
113 }
114
115 template <typename ResourceType, typename IDType>
~ResourceMap()116 ResourceMap<ResourceType, IDType>::~ResourceMap()
117 {
118 ASSERT(empty());
119 delete[] mFlatResources;
120 }
121
122 template <typename ResourceType, typename IDType>
contains(IDType id)123 ANGLE_INLINE bool ResourceMap<ResourceType, IDType>::contains(IDType id) const
124 {
125 GLuint handle = GetIDValue(id);
126 if (handle < mFlatResourcesSize)
127 {
128 return (mFlatResources[handle] != InvalidPointer());
129 }
130 return (mHashedResources.find(handle) != mHashedResources.end());
131 }
132
133 template <typename ResourceType, typename IDType>
erase(IDType id,ResourceType ** resourceOut)134 bool ResourceMap<ResourceType, IDType>::erase(IDType id, ResourceType **resourceOut)
135 {
136 GLuint handle = GetIDValue(id);
137 if (handle < mFlatResourcesSize)
138 {
139 auto &value = mFlatResources[handle];
140 if (value == InvalidPointer())
141 {
142 return false;
143 }
144 *resourceOut = value;
145 value = InvalidPointer();
146 }
147 else
148 {
149 auto it = mHashedResources.find(handle);
150 if (it == mHashedResources.end())
151 {
152 return false;
153 }
154 *resourceOut = it->second;
155 mHashedResources.erase(it);
156 }
157 return true;
158 }
159
160 template <typename ResourceType, typename IDType>
assign(IDType id,ResourceType * resource)161 void ResourceMap<ResourceType, IDType>::assign(IDType id, ResourceType *resource)
162 {
163 GLuint handle = GetIDValue(id);
164 if (handle < kFlatResourcesLimit)
165 {
166 if (handle >= mFlatResourcesSize)
167 {
168 // Use power-of-two.
169 size_t newSize = mFlatResourcesSize;
170 while (newSize <= handle)
171 {
172 newSize *= 2;
173 }
174
175 ResourceType **oldResources = mFlatResources;
176
177 mFlatResources = new ResourceType *[newSize];
178 memset(&mFlatResources[mFlatResourcesSize], kInvalidPointer,
179 (newSize - mFlatResourcesSize) * kElementSize);
180 memcpy(mFlatResources, oldResources, mFlatResourcesSize * kElementSize);
181 mFlatResourcesSize = newSize;
182 delete[] oldResources;
183 }
184 ASSERT(mFlatResourcesSize > handle);
185 mFlatResources[handle] = resource;
186 }
187 else
188 {
189 mHashedResources[handle] = resource;
190 }
191 }
192
193 template <typename ResourceType, typename IDType>
begin()194 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::begin()
195 const
196 {
197 return Iterator(*this, nextNonNullResource(0), mHashedResources.begin());
198 }
199
200 template <typename ResourceType, typename IDType>
end()201 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::end() const
202 {
203 return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end());
204 }
205
206 template <typename ResourceType, typename IDType>
find(IDType handle)207 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::find(
208 IDType handle) const
209 {
210 if (handle < mFlatResourcesSize)
211 {
212 return (mFlatResources[handle] != InvalidPointer()
213 ? Iterator(handle, mHashedResources.begin())
214 : end());
215 }
216 else
217 {
218 return mHashedResources.find(handle);
219 }
220 }
221
222 template <typename ResourceType, typename IDType>
empty()223 bool ResourceMap<ResourceType, IDType>::empty() const
224 {
225 return (begin() == end());
226 }
227
228 template <typename ResourceType, typename IDType>
clear()229 void ResourceMap<ResourceType, IDType>::clear()
230 {
231 memset(mFlatResources, kInvalidPointer, kInitialFlatResourcesSize * kElementSize);
232 mFlatResourcesSize = kInitialFlatResourcesSize;
233 mHashedResources.clear();
234 }
235
236 template <typename ResourceType, typename IDType>
nextNonNullResource(size_t flatIndex)237 GLuint ResourceMap<ResourceType, IDType>::nextNonNullResource(size_t flatIndex) const
238 {
239 for (size_t index = flatIndex; index < mFlatResourcesSize; index++)
240 {
241 if (mFlatResources[index] != nullptr && mFlatResources[index] != InvalidPointer())
242 {
243 return static_cast<GLuint>(index);
244 }
245 }
246 return static_cast<GLuint>(mFlatResourcesSize);
247 }
248
249 template <typename ResourceType, typename IDType>
250 // static
InvalidPointer()251 ResourceType *ResourceMap<ResourceType, IDType>::InvalidPointer()
252 {
253 return reinterpret_cast<ResourceType *>(kInvalidPointer);
254 }
255
256 template <typename ResourceType, typename IDType>
Iterator(const ResourceMap & origin,GLuint flatIndex,typename ResourceMap<ResourceType,IDType>::HashMap::const_iterator hashIndex)257 ResourceMap<ResourceType, IDType>::Iterator::Iterator(
258 const ResourceMap &origin,
259 GLuint flatIndex,
260 typename ResourceMap<ResourceType, IDType>::HashMap::const_iterator hashIndex)
261 : mOrigin(origin), mFlatIndex(flatIndex), mHashIndex(hashIndex)
262 {
263 updateValue();
264 }
265
266 template <typename ResourceType, typename IDType>
267 bool ResourceMap<ResourceType, IDType>::Iterator::operator==(const Iterator &other) const
268 {
269 return (mFlatIndex == other.mFlatIndex && mHashIndex == other.mHashIndex);
270 }
271
272 template <typename ResourceType, typename IDType>
273 bool ResourceMap<ResourceType, IDType>::Iterator::operator!=(const Iterator &other) const
274 {
275 return !(*this == other);
276 }
277
278 template <typename ResourceType, typename IDType>
279 typename ResourceMap<ResourceType, IDType>::Iterator &ResourceMap<ResourceType, IDType>::Iterator::
280 operator++()
281 {
282 if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
283 {
284 mFlatIndex = mOrigin.nextNonNullResource(mFlatIndex + 1);
285 }
286 else
287 {
288 mHashIndex++;
289 }
290 updateValue();
291 return *this;
292 }
293
294 template <typename ResourceType, typename IDType>
295 const typename ResourceMap<ResourceType, IDType>::IndexAndResource
296 *ResourceMap<ResourceType, IDType>::Iterator::operator->() const
297 {
298 return &mValue;
299 }
300
301 template <typename ResourceType, typename IDType>
302 const typename ResourceMap<ResourceType, IDType>::IndexAndResource
303 &ResourceMap<ResourceType, IDType>::Iterator::operator*() const
304 {
305 return mValue;
306 }
307
308 template <typename ResourceType, typename IDType>
updateValue()309 void ResourceMap<ResourceType, IDType>::Iterator::updateValue()
310 {
311 if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
312 {
313 mValue.first = mFlatIndex;
314 mValue.second = mOrigin.mFlatResources[mFlatIndex];
315 }
316 else if (mHashIndex != mOrigin.mHashedResources.end())
317 {
318 mValue.first = mHashIndex->first;
319 mValue.second = mHashIndex->second;
320 }
321 }
322
323 } // namespace gl
324
325 #endif // LIBANGLE_RESOURCE_MAP_H_
326