1 //
2 // Copyright 2002 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 // HandleAllocator.cpp: Implements the gl::HandleAllocator class, which is used
8 // to allocate GL handles.
9
10 #include "libANGLE/HandleAllocator.h"
11
12 #include <algorithm>
13 #include <functional>
14 #include <limits>
15
16 #include "common/debug.h"
17
18 namespace gl
19 {
20
21 struct HandleAllocator::HandleRangeComparator
22 {
operator ()gl::HandleAllocator::HandleRangeComparator23 bool operator()(const HandleRange &range, GLuint handle) const { return (range.end < handle); }
24 };
25
HandleAllocator()26 HandleAllocator::HandleAllocator() : mBaseValue(1), mNextValue(1), mLoggingEnabled(false)
27 {
28 mUnallocatedList.push_back(HandleRange(1, std::numeric_limits<GLuint>::max()));
29 }
30
HandleAllocator(GLuint maximumHandleValue)31 HandleAllocator::HandleAllocator(GLuint maximumHandleValue)
32 : mBaseValue(1), mNextValue(1), mLoggingEnabled(false)
33 {
34 mUnallocatedList.push_back(HandleRange(1, maximumHandleValue));
35 }
36
~HandleAllocator()37 HandleAllocator::~HandleAllocator() {}
38
setBaseHandle(GLuint value)39 void HandleAllocator::setBaseHandle(GLuint value)
40 {
41 ASSERT(mBaseValue == mNextValue);
42 mBaseValue = value;
43 mNextValue = value;
44 }
45
allocate()46 GLuint HandleAllocator::allocate()
47 {
48 ASSERT(!mUnallocatedList.empty() || !mReleasedList.empty());
49
50 // Allocate from released list, logarithmic time for pop_heap.
51 if (!mReleasedList.empty())
52 {
53 std::pop_heap(mReleasedList.begin(), mReleasedList.end(), std::greater<GLuint>());
54 GLuint reusedHandle = mReleasedList.back();
55 mReleasedList.pop_back();
56
57 if (mLoggingEnabled)
58 {
59 WARN() << "HandleAllocator::allocate reusing " << reusedHandle << std::endl;
60 }
61
62 return reusedHandle;
63 }
64
65 // Allocate from unallocated list, constant time.
66 auto listIt = mUnallocatedList.begin();
67
68 GLuint freeListHandle = listIt->begin;
69 ASSERT(freeListHandle > 0);
70
71 if (listIt->begin == listIt->end)
72 {
73 mUnallocatedList.erase(listIt);
74 }
75 else
76 {
77 listIt->begin++;
78 }
79
80 if (mLoggingEnabled)
81 {
82 WARN() << "HandleAllocator::allocate allocating " << freeListHandle << std::endl;
83 }
84
85 return freeListHandle;
86 }
87
release(GLuint handle)88 void HandleAllocator::release(GLuint handle)
89 {
90 if (mLoggingEnabled)
91 {
92 WARN() << "HandleAllocator::release releasing " << handle << std::endl;
93 }
94
95 // Try consolidating the ranges first.
96 for (HandleRange &handleRange : mUnallocatedList)
97 {
98 if (handleRange.begin - 1 == handle)
99 {
100 handleRange.begin--;
101 return;
102 }
103
104 if (handleRange.end == handle - 1)
105 {
106 handleRange.end++;
107 return;
108 }
109 }
110
111 // Add to released list, logarithmic time for push_heap.
112 mReleasedList.push_back(handle);
113 std::push_heap(mReleasedList.begin(), mReleasedList.end(), std::greater<GLuint>());
114 }
115
reserve(GLuint handle)116 void HandleAllocator::reserve(GLuint handle)
117 {
118 if (mLoggingEnabled)
119 {
120 WARN() << "HandleAllocator::reserve reserving " << handle << std::endl;
121 }
122
123 // Clear from released list -- might be a slow operation.
124 if (!mReleasedList.empty())
125 {
126 auto releasedIt = std::find(mReleasedList.begin(), mReleasedList.end(), handle);
127 if (releasedIt != mReleasedList.end())
128 {
129 mReleasedList.erase(releasedIt);
130 std::make_heap(mReleasedList.begin(), mReleasedList.end(), std::greater<GLuint>());
131 return;
132 }
133 }
134
135 // Not in released list, reserve in the unallocated list.
136 auto boundIt = std::lower_bound(mUnallocatedList.begin(), mUnallocatedList.end(), handle,
137 HandleRangeComparator());
138
139 ASSERT(boundIt != mUnallocatedList.end());
140
141 GLuint begin = boundIt->begin;
142 GLuint end = boundIt->end;
143
144 if (handle == begin || handle == end)
145 {
146 if (begin == end)
147 {
148 mUnallocatedList.erase(boundIt);
149 }
150 else if (handle == begin)
151 {
152 boundIt->begin++;
153 }
154 else
155 {
156 ASSERT(handle == end);
157 boundIt->end--;
158 }
159 return;
160 }
161
162 ASSERT(begin < handle && handle < end);
163
164 // need to split the range
165 auto placementIt = mUnallocatedList.erase(boundIt);
166 placementIt = mUnallocatedList.insert(placementIt, HandleRange(handle + 1, end));
167 mUnallocatedList.insert(placementIt, HandleRange(begin, handle - 1));
168 }
169
reset()170 void HandleAllocator::reset()
171 {
172 mUnallocatedList.clear();
173 mUnallocatedList.push_back(HandleRange(1, std::numeric_limits<GLuint>::max()));
174 mReleasedList.clear();
175 mBaseValue = 1;
176 mNextValue = 1;
177 }
178
enableLogging(bool enabled)179 void HandleAllocator::enableLogging(bool enabled)
180 {
181 mLoggingEnabled = enabled;
182 }
183
184 } // namespace gl
185