Panda3D

uniqueIdAllocator.h

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 //]
 All Classes Functions Variables Enumerations