Panda3D
|
00001 // Filename: uniqueIdAllocator.cxx 00002 // Created by: schuyler 2003-03-13 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 // 00015 00016 #include "pandabase.h" 00017 #include "pnotify.h" 00018 #include "notifyCategoryProxy.h" 00019 00020 #include "uniqueIdAllocator.h" 00021 00022 NotifyCategoryDecl(uniqueIdAllocator, EXPCL_PANDA_PUTIL, EXPTP_PANDA_PUTIL); 00023 NotifyCategoryDef(uniqueIdAllocator, ""); 00024 00025 const PN_uint32 UniqueIdAllocator::IndexEnd = (PN_uint32)-1; 00026 const PN_uint32 UniqueIdAllocator::IndexAllocated = (PN_uint32)-2; 00027 00028 #ifndef NDEBUG //[ 00029 // Non-release build: 00030 #define uniqueIdAllocator_debug(msg) \ 00031 if (uniqueIdAllocator_cat.is_debug()) { \ 00032 uniqueIdAllocator_cat->debug() << msg << endl; \ 00033 } else {} 00034 00035 #define uniqueIdAllocator_info(msg) \ 00036 uniqueIdAllocator_cat->info() << msg << endl 00037 00038 #define uniqueIdAllocator_warning(msg) \ 00039 uniqueIdAllocator_cat->warning() << msg << endl 00040 #else //][ 00041 // Release build: 00042 #define uniqueIdAllocator_debug(msg) ((void)0) 00043 #define uniqueIdAllocator_info(msg) ((void)0) 00044 #define uniqueIdAllocator_warning(msg) ((void)0) 00045 #endif //] 00046 00047 #define audio_error(msg) \ 00048 audio_cat->error() << msg << endl 00049 00050 00051 //////////////////////////////////////////////////////////////////// 00052 // Function: UniqueIdAllocator::Constructor 00053 // Access: Published 00054 // Description: Create a free id pool in the range [min:max]. 00055 //////////////////////////////////////////////////////////////////// 00056 UniqueIdAllocator:: 00057 UniqueIdAllocator(PN_uint32 min, PN_uint32 max) 00058 : _min(min), _max(max) { 00059 uniqueIdAllocator_debug("UniqueIdAllocator("<<min<<", "<<max<<")"); 00060 00061 nassertv(_max >= _min); 00062 _size = _max-_min+1; // +1 because min and max are inclusive. 00063 nassertv(_size != 0); // size must be > 0. 00064 00065 _table = (PN_uint32 *)PANDA_MALLOC_ARRAY(_size * sizeof(PN_uint32)); 00066 nassertv(_table); // This should be redundant if new throws an exception. 00067 00068 for (PN_uint32 i = 0; i < _size; ++i) { 00069 _table[i] = i + 1; 00070 } 00071 _table[_size - 1] = IndexEnd; 00072 _next_free = 0; 00073 _last_free = _size - 1; 00074 _free = _size; 00075 } 00076 00077 //////////////////////////////////////////////////////////////////// 00078 // Function: UniqueIdAllocator::Destructor 00079 // Access: Published 00080 // Description: 00081 //////////////////////////////////////////////////////////////////// 00082 UniqueIdAllocator:: 00083 ~UniqueIdAllocator() { 00084 uniqueIdAllocator_debug("~UniqueIdAllocator()"); 00085 PANDA_FREE_ARRAY(_table); 00086 } 00087 00088 00089 //////////////////////////////////////////////////////////////////// 00090 // Function: UniqueIdAllocator::allocate 00091 // Access: Published 00092 // Description: Returns an id between _min and _max (that were passed 00093 // to the constructor). 00094 // IndexEnd is returned if no ids are available. 00095 //////////////////////////////////////////////////////////////////// 00096 PN_uint32 UniqueIdAllocator:: 00097 allocate() { 00098 if (_next_free == IndexEnd) { 00099 // ...all ids allocated. 00100 uniqueIdAllocator_warning("allocate Error: no more free ids."); 00101 return IndexEnd; 00102 } 00103 PN_uint32 index = _next_free; 00104 nassertr(_table[index] != IndexAllocated, IndexEnd); 00105 00106 _next_free = _table[_next_free]; 00107 _table[index] = IndexAllocated; 00108 00109 --_free; 00110 00111 PN_uint32 id = index + _min; 00112 uniqueIdAllocator_debug("allocate() returning " << id); 00113 return id; 00114 } 00115 00116 //////////////////////////////////////////////////////////////////// 00117 // Function: UniqueIdAllocator::initial_reserve_id 00118 // Access: Published 00119 // Description: This may be called to mark a particular id as having 00120 // already been allocated (for instance, by a prior 00121 // pass). The specified id is removed from the 00122 // available pool. 00123 // 00124 // Because of the limitations of this algorithm, this is 00125 // most efficient when it is called before the first 00126 // call to allocate(), and when all the calls to 00127 // initial_reserve_id() are made in descending order by 00128 // id. However, this is a performance warning only; if 00129 // performance is not an issue, any id may be reserved 00130 // at any time. 00131 //////////////////////////////////////////////////////////////////// 00132 void UniqueIdAllocator:: 00133 initial_reserve_id(PN_uint32 id) { 00134 nassertv(id >= _min && id <= _max); // Attempt to reserve out-of-range id. 00135 PN_uint32 index = id - _min; // Convert to _table index. 00136 00137 nassertv(_table[index] != IndexAllocated); 00138 00139 if (_free == 1) { 00140 // We just reserved the last element in the free chain. 00141 _next_free = IndexEnd; 00142 00143 } else if (_next_free == index) { 00144 // We're reserving the head of the free chain. 00145 _next_free = _table[index]; 00146 00147 } else { 00148 // Since we don't store back pointers in the free chain, we have 00149 // to search for the element in the free chain that points to this 00150 // index. 00151 00152 // However, there is an easy optimal case: because we expect that 00153 // this call will be made before any calls to allocate(), 00154 // hopefully is it still true that the _table is still set up such 00155 // that _table[i] = i+1 (and if the numbers are reserved in 00156 // descending order, this will be true at least for all i <= 00157 // index). Thus, the free link to slot [index] is expected to be 00158 // the slot right before it, or if not, it usually won't be far 00159 // before it. 00160 00161 PN_uint32 prev_index = index; 00162 while (prev_index > 0 && _table[prev_index - 1] != index) { 00163 --prev_index; 00164 } 00165 if (prev_index > 0 && _table[prev_index - 1] == index) { 00166 // We've found it. 00167 --prev_index; 00168 00169 } else { 00170 // OK, it wasn't found below; we have to search above. 00171 prev_index = index + 1; 00172 while (prev_index < _size && _table[prev_index] != index) { 00173 ++prev_index; 00174 } 00175 } 00176 00177 nassertv(_table[prev_index] == index); 00178 _table[prev_index] = _table[index]; 00179 00180 if (index == _last_free) { 00181 _last_free = prev_index; 00182 } 00183 } 00184 00185 _table[index] = IndexAllocated; 00186 --_free; 00187 } 00188 00189 00190 //////////////////////////////////////////////////////////////////// 00191 // Function: UniqueIdAllocator::free 00192 // Access: Published 00193 // Description: Free an allocated index (index must be between _min 00194 // and _max that were passed to the constructor). 00195 //////////////////////////////////////////////////////////////////// 00196 void UniqueIdAllocator:: 00197 free(PN_uint32 id) { 00198 uniqueIdAllocator_debug("free("<<id<<")"); 00199 00200 nassertv(id >= _min && id <= _max); // Attempt to free out-of-range id. 00201 PN_uint32 index = id - _min; // Convert to _table index. 00202 nassertv(_table[index] == IndexAllocated); // Attempt to free non-allocated id. 00203 if (_next_free != IndexEnd) { 00204 nassertv(_table[_last_free] == IndexEnd); 00205 _table[_last_free] = index; 00206 } 00207 _table[index] = IndexEnd; // Mark this element as the end of the list. 00208 _last_free = index; 00209 00210 if (_next_free == IndexEnd) { 00211 // ...the free list was empty. 00212 _next_free = index; 00213 } 00214 00215 ++_free; 00216 } 00217 00218 00219 //////////////////////////////////////////////////////////////////// 00220 // Function: UniqueIdAllocator::fraction_used 00221 // Access: Published 00222 // Description: return the decimal fraction of the pool that is used. 00223 // The range is 0 to 1.0 (e.g. 75% would be 0.75). 00224 //////////////////////////////////////////////////////////////////// 00225 PN_stdfloat UniqueIdAllocator:: 00226 fraction_used() const { 00227 return PN_stdfloat(_size-_free)/_size; 00228 } 00229 00230 //////////////////////////////////////////////////////////////////// 00231 // Function: UniqueIdAllocator::output 00232 // Access: Published 00233 // Description: ...intended for debugging only. 00234 //////////////////////////////////////////////////////////////////// 00235 void UniqueIdAllocator:: 00236 output(ostream &out) const { 00237 out << "UniqueIdAllocator(" << _min << ", " << _max << "), " 00238 << _free << " id's remaining of " << _size; 00239 } 00240 00241 //////////////////////////////////////////////////////////////////// 00242 // Function: UniqueIdAllocator::write 00243 // Access: Published 00244 // Description: ...intended for debugging only. 00245 //////////////////////////////////////////////////////////////////// 00246 void UniqueIdAllocator:: 00247 write(ostream &out) const { 00248 out << "_min: " << _min << "; _max: " << _max 00249 << ";\n_next_free: " << PN_int32(_next_free) 00250 << "; _last_free: " << PN_int32(_last_free) 00251 << "; _size: " << _size 00252 << "; _free: " << _free 00253 << "; used: " << _size - _free 00254 << "; fraction_used: " << fraction_used() 00255 << ";\n"; 00256 00257 out << "Table:"; 00258 for (PN_uint32 i = 0; i < _size; ++i) { 00259 out << " " << PN_int32(_table[i]); 00260 } 00261 out << "\n"; 00262 00263 out << "Free chain:"; 00264 PN_uint32 index = _next_free; 00265 while (index != IndexEnd) { 00266 out << " " << index + _min; 00267 index = _table[index]; 00268 } 00269 out << "\n"; 00270 } 00271