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