Panda3D
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 
20 using std::endl;
21 
22 NotifyCategoryDecl(uniqueIdAllocator, EXPCL_PANDA_PUTIL, EXPTP_PANDA_PUTIL);
23 NotifyCategoryDef(uniqueIdAllocator, "");
24 
25 const uint32_t UniqueIdAllocator::IndexEnd = (uint32_t)-1;
26 const 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  */
51 UniqueIdAllocator(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  */
74 UniqueIdAllocator::
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  */
86 allocate() {
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  */
117 initial_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  */
178 free(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  */
205 fraction_used() const {
206  return PN_stdfloat(_size-_free)/_size;
207 }
208 
209 /**
210  * ...intended for debugging only.
211  */
213 output(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  */
222 write(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.