//

// zepeh's library  

// filename: pool.hpp 

//


#ifndef ZL_POOL_HPP

#define ZL_POOL_HPP


#include <cstddef>

#include <memory>


namespace zl

{

template < typename Allocator = std::allocator<unsigned char> > // byte type allocator

class pool;


// pool //

template< typename Allocator >

class pool

{

public:

typedef typename Allocator user_allocator;

typedef typename Allocator::size_type size_type;

typedef typename Allocator::difference_type difference_type;

typedef typename Allocator::value_type byte_type;


private:

const size_type requestedSize;

const size_type blockLength;


private:

static user_allocator allocator;

void** storage;

size_type index;

byte_type* tail;


public:

void* allocate( void );

void deallocate( void* const ptr );

void* allocate( const size_type num );

void deallocate( void* const ptr, size_type num );

inline size_type requested_size( void ) const { return requestedSize; }

explicit pool( const size_type requested_size, const size_type block_length = 32 );

~pool( void );


private:

static inline void* zl::pool<Allocator>::create_block( const size_type direction_count, const size_type bytes );

static inline void zl::pool<Allocator>::release_block( const size_type direction_count, void* const block );

static inline void*& next_of( void* const block );

static inline void*& prev_of( void* const block );

static inline void segregate( void** const storage, byte_type* chunk, size_type count, const size_type partition_size );

};


template< typename Allocator >

void* zl::pool<Allocator>::allocate( void )

{

if( index == 0 )

{

if( prev_of( storage ) )

{

storage = static_cast<void**>( prev_of( storage ) );

}

else

{

byte_type* fresh = static_cast<byte_type*>( create_block( 1, requestedSize * blockLength ) );

next_of( fresh ) = tail;

tail = fresh;

/* 

/* 0 [nextptr(null)][ ][ ][ ][ ][ ]...[ ] <= first 

/* 1 [nextptr(0)][ ][ ][ ][ ][ ]...[ ]

/* 2 [nextptr(1)][ ][ ][ ][ ][ ]...[ ]

/* ...

/* n [nextptr(n-1)][ ][ ][ ][ ][ ]...[ ] <= last 

*/ 



segregate( storage, fresh, blockLength, requestedSize );

}


index = blockLength;

}


return storage[--index];

}


template< typename Allocator >

void* zl::pool<Allocator>::allocate( const size_type num )

{

if( num <= 1 ) return allocate();


void* const fresh = create_block( 1, requestedSize * num );

next_of( fresh ) = tail;


tail = static_cast<byte_type*>( fresh );


return fresh;

}


template< typename Allocator >

void zl::pool<Allocator>::deallocate( void* const ptr )

{

if( index == blockLength )

{

if( pool::next_of( storage ) == NULL )

{

void* const next = next_of( storage ) = static_cast<void*>( create_block( 2, sizeof(void*) * blockLength ) );

prev_of( next ) = static_cast<void*>( storage );

next_of( next ) = NULL;

/*

/* 0 [nextptr(1)][prevptr(null)][ ][ ][ ][ ][ ]...[ ] <= first 

/* 1 [nextptr(2)][prevptr(0)][ ][ ][ ][ ][ ]...[ ]

/* 2 [nextptr(3)][prevptr(1)][ ][ ][ ][ ][ ]...[ ]

/* ...

/* n [nextptr(null)][prevptr(n-1)][ ][ ][ ][ ][ ]...[ ] <= last 

*/

}


storage = static_cast<void**>( next_of( storage ) );

index = 0;

}


storage[index++] = ptr;

}


template< typename Allocator >

void zl::pool<Allocator>::deallocate( void* const ptr, size_type num )

{

byte_type* p = static_cast<byte_type*>( ptr );


while( ( num-- ) != 0 )

{

deallocate( p );

p += requestedSize;

}

}


template< typename Allocator >

zl::pool<Allocator>::pool( const size_type requested_size, const size_type block_length ) :

   requestedSize( requested_size ),

blockLength( block_length ),

index( blockLength )

{

/* initialize */

byte_type* chunk = static_cast<byte_type*>( 

create_block( 0,

( requestedSize * blockLength )  // fresh chunk size

+ ( sizeof(void*) * ( blockLength + 3 ) ) // storage size + ( storage node(2) + fresh chunk node(1) ) 

) 

);


storage = static_cast<void**>( static_cast<void*>( static_cast<byte_type*>( chunk ) + ( sizeof(void*) * 2 ) ) );

tail = chunk + ( sizeof(void*) * ( blockLength + 3 ) );

next_of( tail ) = prev_of( storage ) = next_of( storage ) = NULL;

/*

/* [storage prevptr][storage nextptr][][]...[(blockLength-1)*sizeof(void*)][tail nextptr][][][]...[]

*/


segregate( storage, tail, blockLength, requestedSize );

}


template< typename Allocator >

zl::pool<Allocator>::~pool( void )

{

if( storage )

{

void* temp;


while( temp = next_of( tail ) ){

release_block( 1, tail );

tail = static_cast<byte_type*>( temp );

}


void* left = prev_of( storage );


// -> //

do{

temp = next_of( storage );

release_block( 2, storage );

}while( storage = static_cast<void**>( temp ) );


// <- ( & first chunk ) //

while( temp = left ){

left = prev_of( temp );

release_block( 2, temp );

}

}

}


// [ link data ] 

// [ requested chunk ] <= [in, out] ptr

template< typename Allocator >

void* zl::pool<Allocator>::create_block( const size_type direction_count, const size_type bytes )

{ return ( static_cast<void**>( static_cast<void*>( allocator.allocate( ( ( sizeof(void*) * direction_count ) + bytes ) ) ) ) + direction_count  ); }


template< typename Allocator >

void zl::pool<Allocator>::release_block( const size_type direction_count, void* const block )

{ allocator.deallocate( static_cast<byte_type*>( static_cast<void*>( ( static_cast<void**>( block ) ) - direction_count ) ), 1 ); }


template< typename Allocator >

void*& zl::pool<Allocator>::next_of( void* const block )

{ return *( static_cast<void**>( block ) - 1 ); }


template< typename Allocator >

void*& zl::pool<Allocator>::prev_of( void* const block )

{ return *( static_cast<void**>( block ) - 2 ); }


template< typename Allocator >

void zl::pool<Allocator>::segregate( void** const storage, byte_type* chunk, size_type count, const size_type partition_size )

{

do{

storage[--count] = static_cast<void*>( chunk );

static_cast<byte_type*>( chunk ) += partition_size;

}while( count != 0 );

/*

/* [      chunk     ] => [[ 1 ][ 2 ][ ... ][ n ]]

*/

}


template< typename Allocator >

typename zl::pool<Allocator>::user_allocator zl::pool<Allocator>::allocator;

}


#endif