1 //
2 // Copyright (c) 2016 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
7 // HandleRangeAllocator.cpp : Implementation for HandleRangeAllocator.h
8
9 #include "libANGLE/HandleRangeAllocator.h"
10
11 #include <algorithm>
12 #include <limits>
13 #include <utility>
14
15 #include "common/angleutils.h"
16 #include "common/debug.h"
17
18 namespace gl
19 {
20
21 const GLuint HandleRangeAllocator::kInvalidHandle = 0;
22
HandleRangeAllocator()23 HandleRangeAllocator::HandleRangeAllocator()
24 {
25 // Simplify the code by making sure that lower_bound(id) never
26 // returns the beginning of the map, if id is valid (eg != kInvalidHandle).
27 mUsed.insert(std::make_pair(0u, 0u));
28 }
29
~HandleRangeAllocator()30 HandleRangeAllocator::~HandleRangeAllocator()
31 {
32 }
33
allocate()34 GLuint HandleRangeAllocator::allocate()
35 {
36 return allocateRange(1u);
37 }
38
allocateAtOrAbove(GLuint wanted)39 GLuint HandleRangeAllocator::allocateAtOrAbove(GLuint wanted)
40 {
41 if (wanted == 0u || wanted == 1u)
42 return allocateRange(1u);
43
44 auto current = mUsed.lower_bound(wanted);
45 auto next = current;
46 if (current == mUsed.end() || current->first > wanted)
47 {
48 current--;
49 }
50 else
51 {
52 next++;
53 }
54
55 GLuint firstId = current->first;
56 GLuint lastId = current->second;
57 ASSERT(wanted >= firstId);
58
59 if (wanted - 1u <= lastId)
60 {
61 // Append to current range.
62 lastId++;
63 if (lastId == 0)
64 {
65 // The increment overflowed.
66 return allocateRange(1u);
67 }
68
69 current->second = lastId;
70
71 if (next != mUsed.end() && next->first - 1u == lastId)
72 {
73 // Merge with next range.
74 current->second = next->second;
75 mUsed.erase(next);
76 }
77 return lastId;
78 }
79 else if (next != mUsed.end() && next->first - 1u == wanted)
80 {
81 // Prepend to next range.
82 GLuint lastExisting = next->second;
83 mUsed.erase(next);
84 mUsed.insert(std::make_pair(wanted, lastExisting));
85 return wanted;
86 }
87 mUsed.insert(std::make_pair(wanted, wanted));
88 return wanted;
89 }
90
allocateRange(GLuint range)91 GLuint HandleRangeAllocator::allocateRange(GLuint range)
92 {
93 ASSERT(range != 0);
94
95 auto current = mUsed.begin();
96 auto next = current;
97
98 while (++next != mUsed.end())
99 {
100 if (next->first - current->second > range)
101 break;
102 current = next;
103 }
104 const GLuint firstId = current->second + 1u;
105 const GLuint lastId = firstId + range - 1u;
106
107 // deal with wraparound
108 if (firstId == 0u || lastId < firstId)
109 return kInvalidHandle;
110
111 current->second = lastId;
112
113 if (next != mUsed.end() && next->first - 1u == lastId)
114 {
115 // merge with next range
116 current->second = next->second;
117 mUsed.erase(next);
118 }
119 return firstId;
120 }
121
markAsUsed(GLuint handle)122 bool HandleRangeAllocator::markAsUsed(GLuint handle)
123 {
124 ASSERT(handle);
125 auto current = mUsed.lower_bound(handle);
126 if (current != mUsed.end() && current->first == handle)
127 return false;
128
129 auto next = current;
130 --current;
131
132 if (current->second >= handle)
133 return false;
134
135 ASSERT(current->first < handle && current->second < handle);
136
137 if (current->second + 1u == handle)
138 {
139 // Append to current range.
140 current->second = handle;
141 if (next != mUsed.end() && next->first - 1u == handle)
142 {
143 // Merge with next range.
144 current->second = next->second;
145 mUsed.erase(next);
146 }
147 return true;
148 }
149 else if (next != mUsed.end() && next->first - 1u == handle)
150 {
151 // Prepend to next range.
152 GLuint lastExisting = next->second;
153 mUsed.erase(next);
154 mUsed.insert(std::make_pair(handle, lastExisting));
155 return true;
156 }
157
158 mUsed.insert(std::make_pair(handle, handle));
159 return true;
160 }
161
release(GLuint handle)162 void HandleRangeAllocator::release(GLuint handle)
163 {
164 releaseRange(handle, 1u);
165 }
166
releaseRange(GLuint first,GLuint range)167 void HandleRangeAllocator::releaseRange(GLuint first, GLuint range)
168 {
169 if (range == 0u || (first == 0u && range == 1u))
170 return;
171
172 if (first == 0u)
173 {
174 first++;
175 range--;
176 }
177
178 GLuint last = first + range - 1u;
179 if (last < first)
180 last = std::numeric_limits<GLuint>::max();
181
182 while (true)
183 {
184 auto current = mUsed.lower_bound(last);
185 if (current == mUsed.end() || current->first > last)
186 --current;
187
188 if (current->second < first)
189 return;
190
191 if (current->first >= first)
192 {
193 const GLuint lastExisting = current->second;
194 mUsed.erase(current);
195 if (last < lastExisting)
196 {
197 mUsed.insert(std::make_pair(last + 1u, lastExisting));
198 }
199 }
200 else if (current->second <= last)
201 {
202 current->second = first - 1u;
203 }
204 else
205 {
206 ASSERT(current->first < first && current->second > last);
207 const GLuint lastExisting = current->second;
208 current->second = first - 1u;
209 mUsed.insert(std::make_pair(last + 1u, lastExisting));
210 }
211 }
212 }
213
isUsed(GLuint handle) const214 bool HandleRangeAllocator::isUsed(GLuint handle) const
215 {
216 if (handle == kInvalidHandle)
217 return false;
218
219 auto current = mUsed.lower_bound(handle);
220 if (current != mUsed.end())
221 {
222 if (current->first == handle)
223 return true;
224 }
225 --current;
226 return current->second >= handle;
227 }
228
229 } // namespace gl