Panda3D
Loading...
Searching...
No Matches
uniqueIdAllocator.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file uniqueIdAllocator.cxx
10 * @author schuyler
11 * @date 2003-03-13
12 */
13
14#include "pandabase.h"
15#include "pnotify.h"
16#include "notifyCategoryProxy.h"
17
18#include "uniqueIdAllocator.h"
19
20using std::endl;
21
22NotifyCategoryDecl(uniqueIdAllocator, EXPCL_PANDA_PUTIL, EXPTP_PANDA_PUTIL);
23NotifyCategoryDef(uniqueIdAllocator, "");
24
25const uint32_t UniqueIdAllocator::IndexEnd = (uint32_t)-1;
26const uint32_t UniqueIdAllocator::IndexAllocated = (uint32_t)-2;
27
28#ifndef NDEBUG //[
29 // Non-release build:
30 #define uniqueIdAllocator_debug(msg) \
31 if (uniqueIdAllocator_cat.is_debug()) { \
32 uniqueIdAllocator_cat->debug() << msg << endl; \
33 } else {}
34
35 #define uniqueIdAllocator_info(msg) \
36 uniqueIdAllocator_cat->info() << msg << endl
37
38 #define uniqueIdAllocator_warning(msg) \
39 uniqueIdAllocator_cat->warning() << msg << endl
40#else //][
41 // Release build:
42 #define uniqueIdAllocator_debug(msg) ((void)0)
43 #define uniqueIdAllocator_info(msg) ((void)0)
44 #define uniqueIdAllocator_warning(msg) ((void)0)
45#endif //]
46
47/**
48 * Create a free id pool in the range [min:max].
49 */
51UniqueIdAllocator(uint32_t min, uint32_t max)
52 : _min(min), _max(max) {
53 uniqueIdAllocator_debug("UniqueIdAllocator("<<min<<", "<<max<<")");
54
55 nassertv(_max >= _min);
56 _size = _max-_min+1; // +1 because min and max are inclusive.
57 nassertv(_size != 0); // size must be > 0.
58
59 _table = (uint32_t *)PANDA_MALLOC_ARRAY(_size * sizeof(uint32_t));
60 nassertv(_table); // This should be redundant if new throws an exception.
61
62 for (uint32_t i = 0; i < _size; ++i) {
63 _table[i] = i + 1;
64 }
65 _table[_size - 1] = IndexEnd;
66 _next_free = 0;
67 _last_free = _size - 1;
68 _free = _size;
69}
70
71/**
72 *
73 */
74UniqueIdAllocator::
75~UniqueIdAllocator() {
76 uniqueIdAllocator_debug("~UniqueIdAllocator()");
77 PANDA_FREE_ARRAY(_table);
78}
79
80
81/**
82 * Returns an id between _min and _max (that were passed to the constructor).
83 * IndexEnd is returned if no ids are available.
84 */
86allocate() {
87 if (_next_free == IndexEnd) {
88 // ...all ids allocated.
89 uniqueIdAllocator_warning("allocate Error: no more free ids.");
90 return IndexEnd;
91 }
92 uint32_t index = _next_free;
93 nassertr(_table[index] != IndexAllocated, IndexEnd);
94
95 _next_free = _table[_next_free];
96 _table[index] = IndexAllocated;
97
98 --_free;
99
100 uint32_t id = index + _min;
101 uniqueIdAllocator_debug("allocate() returning " << id);
102 return id;
103}
104
105/**
106 * This may be called to mark a particular id as having already been allocated
107 * (for instance, by a prior pass). The specified id is removed from the
108 * available pool.
109 *
110 * Because of the limitations of this algorithm, this is most efficient when
111 * it is called before the first call to allocate(), and when all the calls to
112 * initial_reserve_id() are made in descending order by id. However, this is
113 * a performance warning only; if performance is not an issue, any id may be
114 * reserved at any time.
115 */
117initial_reserve_id(uint32_t id) {
118 nassertv(id >= _min && id <= _max); // Attempt to reserve out-of-range id.
119 uint32_t index = id - _min; // Convert to _table index.
120
121 nassertv(_table[index] != IndexAllocated);
122
123 if (_free == 1) {
124 // We just reserved the last element in the free chain.
125 _next_free = IndexEnd;
126
127 } else if (_next_free == index) {
128 // We're reserving the head of the free chain.
129 _next_free = _table[index];
130
131 } else {
132 // Since we don't store back pointers in the free chain, we have to search
133 // for the element in the free chain that points to this index.
134
135/*
136 * However, there is an easy optimal case: because we expect that this call
137 * will be made before any calls to allocate(), hopefully is it still true
138 * that the _table is still set up such that _table[i] = i+1 (and if the
139 * numbers are reserved in descending order, this will be true at least for
140 * all i <= index). Thus, the free link to slot [index] is expected to be the
141 * slot right before it, or if not, it usually won't be far before it.
142 */
143
144 uint32_t prev_index = index;
145 while (prev_index > 0 && _table[prev_index - 1] != index) {
146 --prev_index;
147 }
148 if (prev_index > 0 && _table[prev_index - 1] == index) {
149 // We've found it.
150 --prev_index;
151
152 } else {
153 // OK, it wasn't found below; we have to search above.
154 prev_index = index + 1;
155 while (prev_index < _size && _table[prev_index] != index) {
156 ++prev_index;
157 }
158 }
159
160 nassertv(_table[prev_index] == index);
161 _table[prev_index] = _table[index];
162
163 if (index == _last_free) {
164 _last_free = prev_index;
165 }
166 }
167
168 _table[index] = IndexAllocated;
169 --_free;
170}
171
172
173/**
174 * Free an allocated index (index must be between _min and _max that were
175 * passed to the constructor).
176 */
178free(uint32_t id) {
179 uniqueIdAllocator_debug("free("<<id<<")");
180
181 nassertv(id >= _min && id <= _max); // Attempt to free out-of-range id.
182 uint32_t index = id - _min; // Convert to _table index.
183 nassertv(_table[index] == IndexAllocated); // Attempt to free non-allocated id.
184 if (_next_free != IndexEnd) {
185 nassertv(_table[_last_free] == IndexEnd);
186 _table[_last_free] = index;
187 }
188 _table[index] = IndexEnd; // Mark this element as the end of the list.
189 _last_free = index;
190
191 if (_next_free == IndexEnd) {
192 // ...the free list was empty.
193 _next_free = index;
194 }
195
196 ++_free;
197}
198
199
200/**
201 * return the decimal fraction of the pool that is used. The range is 0 to
202 * 1.0 (e.g. 75% would be 0.75).
203 */
205fraction_used() const {
206 return PN_stdfloat(_size-_free)/_size;
207}
208
209/**
210 * ...intended for debugging only.
211 */
213output(std::ostream &out) const {
214 out << "UniqueIdAllocator(" << _min << ", " << _max << "), "
215 << _free << " id's remaining of " << _size;
216}
217
218/**
219 * ...intended for debugging only.
220 */
222write(std::ostream &out) const {
223 out << "_min: " << _min << "; _max: " << _max
224 << ";\n_next_free: " << int32_t(_next_free)
225 << "; _last_free: " << int32_t(_last_free)
226 << "; _size: " << _size
227 << "; _free: " << _free
228 << "; used: " << _size - _free
229 << "; fraction_used: " << fraction_used()
230 << ";\n";
231
232 out << "Table:";
233 for (uint32_t i = 0; i < _size; ++i) {
234 out << " " << int32_t(_table[i]);
235 }
236 out << "\n";
237
238 out << "Free chain:";
239 uint32_t index = _next_free;
240 while (index != IndexEnd) {
241 out << " " << index + _min;
242 index = _table[index];
243 }
244 out << "\n";
245}
void initial_reserve_id(uint32_t id)
This may be called to mark a particular id as having already been allocated (for instance,...
void output(std::ostream &out) const
...intended for debugging only.
void write(std::ostream &out) const
...intended for debugging only.
uint32_t allocate()
Returns an id between _min and _max (that were passed to the constructor).
PN_stdfloat fraction_used() const
return the decimal fraction of the pool that is used.
void free(uint32_t index)
Free an allocated index (index must be between _min and _max that were passed to the constructor).
UniqueIdAllocator(uint32_t min=0, uint32_t max=20)
Create a free id pool in the range [min:max].
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.