Public Member Functions | Static Public Attributes | Protected Attributes

UniqueIdAllocator Class Reference

Manage a set of ID values from min to max inclusive. More...

#include "uniqueIdAllocator.h"

List of all members.

Public Member Functions

 UniqueIdAllocator (PN_uint32 min=0, PN_uint32 max=20)
 Create a free id pool in the range [min:max].
PN_uint32 allocate ()
 Returns an id between _min and _max (that were passed to the constructor).
float fraction_used () const
 return the decimal fraction of the pool that is used.
void free (PN_uint32 index)
 Free an allocated index (index must be between _min and _max that were passed to the constructor).
void initial_reserve_id (PN_uint32 id)
 This may be called to mark a particular id as having already been allocated (for instance, by a prior pass).
void output (ostream &out) const
 ...intended for debugging only.
void write (ostream &out) const
 ...intended for debugging only.

Static Public Attributes

static const PN_uint32 IndexAllocated = (PN_uint32)-2
static const PN_uint32 IndexEnd = (PN_uint32)-1

Protected Attributes

PN_uint32 _free
PN_uint32 _last_free
PN_uint32 _max
PN_uint32 _min
PN_uint32 _next_free
PN_uint32 _size
PN_uint32 * _table

Detailed Description

Manage a set of ID values from min to max inclusive.

The ID numbers that are freed will be allocated (reused) in the same order. I.e. the oldest ID numbers will be allocated.

This implementation will use 4 bytes per id number, plus a few bytes of management data. e.g. 10,000 ID numbers will use 40KB.

Also be advised that ID -1 and -2 are used internally by the allocator. If allocate returns IndexEnd (-1) then the allocator is out of free ID numbers.

There are other implementations that can better leverage runs of used or unused IDs or use bit arrays for the IDs. But, it takes extra work to track the age of freed IDs, which is required for what we wanted. If you would like to kick around other implementation ideas, please contact Schuyler.

Definition at line 44 of file uniqueIdAllocator.h.

Constructor & Destructor Documentation

UniqueIdAllocator::UniqueIdAllocator ( PN_uint32  min = 0,
PN_uint32  max = 20 
)

Create a free id pool in the range [min:max].

Definition at line 57 of file uniqueIdAllocator.cxx.

Member Function Documentation

PN_uint32 UniqueIdAllocator::allocate ( )

Returns an id between _min and _max (that were passed to the constructor).

IndexEnd is returned if no ids are available.

Definition at line 97 of file uniqueIdAllocator.cxx.

float UniqueIdAllocator::fraction_used ( ) const

return the decimal fraction of the pool that is used.

The range is 0 to 1.0 (e.g. 75% would be 0.75).

Definition at line 226 of file uniqueIdAllocator.cxx.

Referenced by write().

void UniqueIdAllocator::free ( PN_uint32  index)

Free an allocated index (index must be between _min and _max that were passed to the constructor).

Definition at line 197 of file uniqueIdAllocator.cxx.

void UniqueIdAllocator::initial_reserve_id ( PN_uint32  id)

This may be called to mark a particular id as having already been allocated (for instance, by a prior pass).

The specified id is removed from the available pool.

Because of the limitations of this algorithm, this is most efficient when it is called before the first call to allocate(), and when all the calls to initial_reserve_id() are made in descending order by id. However, this is a performance warning only; if performance is not an issue, any id may be reserved at any time.

Definition at line 133 of file uniqueIdAllocator.cxx.

void UniqueIdAllocator::output ( ostream &  out) const

...intended for debugging only.

Definition at line 236 of file uniqueIdAllocator.cxx.

void UniqueIdAllocator::write ( ostream &  out) const

...intended for debugging only.

Definition at line 247 of file uniqueIdAllocator.cxx.

References fraction_used().

The documentation for this class was generated from the following files: