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