Panda3D
 All Classes Functions Variables Enumerations
uniqueIdAllocator.cxx
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 
 All Classes Functions Variables Enumerations