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