// Filename: uniqueIdAllocator.h
// Created by:  schuyler 2003-03-13
//
////////////////////////////////////////////////////////////////////
//
// PANDA 3D SOFTWARE
// Copyright (c) 2001 - 2004, Disney Enterprises, Inc.  All rights reserved
//
// All use of this software is subject to the terms of the Panda 3d
// Software license.  You should have received a copy of this license
// along with this source code; you will also find a current copy of
// the license at http://etc.cmu.edu/panda3d/docs/license/ .
//
// To contact the maintainers of this program write to
// panda3d-general@lists.sourceforge.net .
//
////////////////////////////////////////////////////////////////////
// 

#ifndef _UNIQUEIDALLOCATOR_H //[
#define _UNIQUEIDALLOCATOR_H

#include "pandabase.h"
#include "numeric_types.h"

////////////////////////////////////////////////////////////////////
//       Class : UniqueIdAllocator
// 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.
////////////////////////////////////////////////////////////////////
class EXPCL_PANDA UniqueIdAllocator {
PUBLISHED:
  UniqueIdAllocator(PN_uint32 min=0, PN_uint32 max=20);
  ~UniqueIdAllocator();

  PN_uint32 allocate();
  void initial_reserve_id(PN_uint32 id);

  void free(PN_uint32 index);
  float fraction_used() const;

  void output(ostream &out) const;
  void write(ostream &out) const;

public:  
  static const PN_uint32 IndexEnd;
  static const PN_uint32 IndexAllocated;

protected:
  // _table stores an array of _size words, corresponding to each
  // allocatable id.

  // For each free id, the table entry at the corresponding index
  // contains the index number of the next free id, thus defining a
  // chain of free id's.  The last element of the chain contains
  // IndexEnd.

  // For an allocated id, the table entry at the corresponding index
  // contains IndexAllocated.
  PN_uint32 *_table;

  // The minimum and maximum as passed to the constructor.
  PN_uint32 _min;
  PN_uint32 _max;

  // This is the head of the free chain: as elements are allocated,
  // they are taken from _table[_next_free].  If the free chain is
  // empty, _next_free == IndexEnd.
  PN_uint32 _next_free;

  // This is the tail of the free chain: as elements are freed, they
  // are stored in _table[_last_free].  Normally, _table[_last_free]
  // is the end of the free chain, unless the free chain is empty.
  PN_uint32 _last_free;

  // The total number of elements in _table.
  PN_uint32 _size;

  // The number of free elements in _table.
  PN_uint32 _free;
};

#endif //]
