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