#ifndef INCLUDE_BUFFERPOOL_H
#define INCLUDE_BUFFERPOOL_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <list>
#include "using-std.h"


/***********************************************************************
 *
 *  BufferPool implements a reusable collection of fixed-size buffers.
 *  The typical usage pattern is to request individual buffers using
 *  BufferPool::alloc(), and then release all buffers at once using
 *  BufferPool::reset().  Released buffers are then placed on a free
 *  list, and may be used to satisfy future allocation requests.  One
 *  may also release individual buffers using BufferPool::release(),
 *  although this is less efficient.
 *
 *  When unused buffers are available on the free list, buffer
 *  allocation is a constant time operation.  If no unused buffers are
 *  available, then allocation requires constant time plus time for
 *  a call to the underlying C++ allocator.
 *
 *  Resetting the buffer pool is a constant time operation.
 *
 *  In the average case, releasing a single buffer requires time
 *  linear in the number of active buffers.  This reduces to constant
 *  time if the pattern of allocations and releases obeys a stack
 *  discipline.
 *
 *  Destroying a buffer pool returns all of its buffers to the C++
 *  heap.  This requires time linear in the total number of active or
 *  free buffers.
 *
 *  Buffer pools do not respect or call destructors.  If buffers
 *  obtained from the pool will be used to store instances with
 *  nontrivial destructors, subclass InstancePool should be used
 *  instead.
 *
 **********************************************************************/


template< size_t Size > class BufferPool {
public:
  void *alloc();
  void release( void * );
  void reset();
  
  size_t freeSize() const;
  size_t usedSize() const;
  
  BufferPool() { }
  ~BufferPool();

protected:
  typedef list< char * > List;
  List used;
  List free;

private:
  // forbidden
  BufferPool( const BufferPool & );
  BufferPool & operator =( const BufferPool & );
};


template< size_t Size > void *BufferPool< Size >::alloc()
{
  if (free.empty())
    used.push_front( new char[ Size ] );
  else
    used.splice( used.begin(), free, free.begin() );
  
  return used.front();
}


template< size_t Size > void BufferPool< Size >::release( void *buffer )
{
  List::iterator chaff = find( used.begin(), used.end(), buffer );
  assert( chaff != used.end() );
  
  free.splice( free.begin(), used, chaff );
}


template< size_t Size > inline void BufferPool< Size >::reset()
{
  free.splice( free.begin(), used );
}


template< size_t Size > inline size_t BufferPool< Size >::freeSize() const
{
  return free.size();
}


template< size_t Size > inline size_t BufferPool< Size >::usedSize() const
{
  return used.size();
}


template< size_t Size > BufferPool< Size >::~BufferPool()
{
  reset();

  for (List::const_iterator chaff = free.begin(); chaff != free.end(); ++chaff)
    delete[] *chaff;
}


#endif // !INCLUDE_BUFFERPOOL_H