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  */
85 uint32_t UniqueIdAllocator::
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  */
204 PN_stdfloat UniqueIdAllocator::
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 }
pandabase.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
notifyCategoryProxy.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
UniqueIdAllocator::initial_reserve_id
void initial_reserve_id(uint32_t id)
This may be called to mark a particular id as having already been allocated (for instance,...
Definition: uniqueIdAllocator.cxx:117
pnotify.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
UniqueIdAllocator::allocate
uint32_t allocate()
Returns an id between _min and _max (that were passed to the constructor).
Definition: uniqueIdAllocator.cxx:86
UniqueIdAllocator::write
void write(std::ostream &out) const
...intended for debugging only.
Definition: uniqueIdAllocator.cxx:222
UniqueIdAllocator::output
void output(std::ostream &out) const
...intended for debugging only.
Definition: uniqueIdAllocator.cxx:213
uniqueIdAllocator.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
UniqueIdAllocator::free
void free(uint32_t index)
Free an allocated index (index must be between _min and _max that were passed to the constructor).
Definition: uniqueIdAllocator.cxx:178
UniqueIdAllocator::UniqueIdAllocator
UniqueIdAllocator(uint32_t min=0, uint32_t max=20)
Create a free id pool in the range [min:max].
Definition: uniqueIdAllocator.cxx:51
UniqueIdAllocator::fraction_used
PN_stdfloat fraction_used() const
return the decimal fraction of the pool that is used.
Definition: uniqueIdAllocator.cxx:205