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