00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
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
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
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
00053
00054
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;
00063 nassertv(_size != 0);
00064
00065 _table = (PN_uint32 *)PANDA_MALLOC_ARRAY(_size * sizeof(PN_uint32));
00066 nassertv(_table);
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
00079
00080
00081
00082 UniqueIdAllocator::
00083 ~UniqueIdAllocator() {
00084 uniqueIdAllocator_debug("~UniqueIdAllocator()");
00085 PANDA_FREE_ARRAY(_table);
00086 }
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096 PN_uint32 UniqueIdAllocator::
00097 allocate() {
00098 if (_next_free == IndexEnd) {
00099
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
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132 void UniqueIdAllocator::
00133 initial_reserve_id(PN_uint32 id) {
00134 nassertv(id >= _min && id <= _max);
00135 PN_uint32 index = id - _min;
00136
00137 nassertv(_table[index] != IndexAllocated);
00138
00139 if (_free == 1) {
00140
00141 _next_free = IndexEnd;
00142
00143 } else if (_next_free == index) {
00144
00145 _next_free = _table[index];
00146
00147 } else {
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
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
00167 --prev_index;
00168
00169 } else {
00170
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
00192
00193
00194
00195
00196 void UniqueIdAllocator::
00197 free(PN_uint32 id) {
00198 uniqueIdAllocator_debug("free("<<id<<")");
00199
00200 nassertv(id >= _min && id <= _max);
00201 PN_uint32 index = id - _min;
00202 nassertv(_table[index] == IndexAllocated);
00203 if (_next_free != IndexEnd) {
00204 nassertv(_table[_last_free] == IndexEnd);
00205 _table[_last_free] = index;
00206 }
00207 _table[index] = IndexEnd;
00208 _last_free = index;
00209
00210 if (_next_free == IndexEnd) {
00211
00212 _next_free = index;
00213 }
00214
00215 ++_free;
00216 }
00217
00218
00219
00220
00221
00222
00223
00224
00225 PN_stdfloat UniqueIdAllocator::
00226 fraction_used() const {
00227 return PN_stdfloat(_size-_free)/_size;
00228 }
00229
00230
00231
00232
00233
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
00243
00244
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