Panda3D
 All Classes Functions Variables Enumerations
uniqueIdAllocator.h
1 // Filename: uniqueIdAllocator.h
2 // Created by: schuyler 2003-03-13
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 //
15 
16 #ifndef _UNIQUEIDALLOCATOR_H //[
17 #define _UNIQUEIDALLOCATOR_H
18 
19 #include "pandabase.h"
20 #include "numeric_types.h"
21 
22 ////////////////////////////////////////////////////////////////////
23 // Class : UniqueIdAllocator
24 // Description : Manage a set of ID values from min to max inclusive.
25 // The ID numbers that are freed will be allocated
26 // (reused) in the same order. I.e. the oldest ID numbers
27 // will be allocated.
28 //
29 // This implementation will use 4 bytes per id number,
30 // plus a few bytes of management data. e.g. 10,000
31 // ID numbers will use 40KB.
32 //
33 // Also be advised that ID -1 and -2 are used internally by
34 // the allocator. If allocate returns IndexEnd (-1) then
35 // the allocator is out of free ID numbers.
36 //
37 // There are other implementations that can better leverage
38 // runs of used or unused IDs or use bit arrays for the
39 // IDs. But, it takes extra work to track the age of
40 // freed IDs, which is required for what we wanted. If
41 // you would like to kick around other implementation
42 // ideas, please contact Schuyler.
43 ////////////////////////////////////////////////////////////////////
44 class EXPCL_PANDA_PUTIL UniqueIdAllocator {
45 PUBLISHED:
46  UniqueIdAllocator(PN_uint32 min=0, PN_uint32 max=20);
48 
49  PN_uint32 allocate();
50  void initial_reserve_id(PN_uint32 id);
51 
52  void free(PN_uint32 index);
53  PN_stdfloat fraction_used() const;
54 
55  void output(ostream &out) const;
56  void write(ostream &out) const;
57 
58 public:
59  static const PN_uint32 IndexEnd;
60  static const PN_uint32 IndexAllocated;
61 
62 protected:
63  // _table stores an array of _size words, corresponding to each
64  // allocatable id.
65 
66  // For each free id, the table entry at the corresponding index
67  // contains the index number of the next free id, thus defining a
68  // chain of free id's. The last element of the chain contains
69  // IndexEnd.
70 
71  // For an allocated id, the table entry at the corresponding index
72  // contains IndexAllocated.
73  PN_uint32 *_table;
74 
75  // The minimum and maximum as passed to the constructor.
76  PN_uint32 _min;
77  PN_uint32 _max;
78 
79  // This is the head of the free chain: as elements are allocated,
80  // they are taken from _table[_next_free]. If the free chain is
81  // empty, _next_free == IndexEnd.
82  PN_uint32 _next_free;
83 
84  // This is the tail of the free chain: as elements are freed, they
85  // are stored in _table[_last_free]. Normally, _table[_last_free]
86  // is the end of the free chain, unless the free chain is empty.
87  PN_uint32 _last_free;
88 
89  // The total number of elements in _table.
90  PN_uint32 _size;
91 
92  // The number of free elements in _table.
93  PN_uint32 _free;
94 };
95 
96 #endif //]
Manage a set of ID values from min to max inclusive.