Panda3D
|
00001 // Filename: uniqueIdAllocator.h 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 #ifndef _UNIQUEIDALLOCATOR_H //[ 00017 #define _UNIQUEIDALLOCATOR_H 00018 00019 #include "pandabase.h" 00020 #include "numeric_types.h" 00021 00022 //////////////////////////////////////////////////////////////////// 00023 // Class : UniqueIdAllocator 00024 // Description : Manage a set of ID values from min to max inclusive. 00025 // The ID numbers that are freed will be allocated 00026 // (reused) in the same order. I.e. the oldest ID numbers 00027 // will be allocated. 00028 // 00029 // This implementation will use 4 bytes per id number, 00030 // plus a few bytes of management data. e.g. 10,000 00031 // ID numbers will use 40KB. 00032 // 00033 // Also be advised that ID -1 and -2 are used internally by 00034 // the allocator. If allocate returns IndexEnd (-1) then 00035 // the allocator is out of free ID numbers. 00036 // 00037 // There are other implementations that can better leverage 00038 // runs of used or unused IDs or use bit arrays for the 00039 // IDs. But, it takes extra work to track the age of 00040 // freed IDs, which is required for what we wanted. If 00041 // you would like to kick around other implementation 00042 // ideas, please contact Schuyler. 00043 //////////////////////////////////////////////////////////////////// 00044 class EXPCL_PANDA_PUTIL UniqueIdAllocator { 00045 PUBLISHED: 00046 UniqueIdAllocator(PN_uint32 min=0, PN_uint32 max=20); 00047 ~UniqueIdAllocator(); 00048 00049 PN_uint32 allocate(); 00050 void initial_reserve_id(PN_uint32 id); 00051 00052 void free(PN_uint32 index); 00053 PN_stdfloat fraction_used() const; 00054 00055 void output(ostream &out) const; 00056 void write(ostream &out) const; 00057 00058 public: 00059 static const PN_uint32 IndexEnd; 00060 static const PN_uint32 IndexAllocated; 00061 00062 protected: 00063 // _table stores an array of _size words, corresponding to each 00064 // allocatable id. 00065 00066 // For each free id, the table entry at the corresponding index 00067 // contains the index number of the next free id, thus defining a 00068 // chain of free id's. The last element of the chain contains 00069 // IndexEnd. 00070 00071 // For an allocated id, the table entry at the corresponding index 00072 // contains IndexAllocated. 00073 PN_uint32 *_table; 00074 00075 // The minimum and maximum as passed to the constructor. 00076 PN_uint32 _min; 00077 PN_uint32 _max; 00078 00079 // This is the head of the free chain: as elements are allocated, 00080 // they are taken from _table[_next_free]. If the free chain is 00081 // empty, _next_free == IndexEnd. 00082 PN_uint32 _next_free; 00083 00084 // This is the tail of the free chain: as elements are freed, they 00085 // are stored in _table[_last_free]. Normally, _table[_last_free] 00086 // is the end of the free chain, unless the free chain is empty. 00087 PN_uint32 _last_free; 00088 00089 // The total number of elements in _table. 00090 PN_uint32 _size; 00091 00092 // The number of free elements in _table. 00093 PN_uint32 _free; 00094 }; 00095 00096 #endif //]