/** @file pool.h
 *
 *	Declaration of memory pool classes interface.
 *
 *	Memory pools are designed to save 1.) place and 2.) time.
 *
 *	1.) Dynamic allocation of memory requires some extra space for information
 *	about the size of allocated memory piece (to let deallocator know how much
 *	memory should be retrieved). In case of small objects this information can
 *	be even as big as stored object. So if the memory for that kind of objects
 *	is allocated in big chunk, there is no extra space cost for each object.
 *
 *	2.) Frequent memory allocation is time consuming, so if performed only once
 *	in a while, the time is saved.
 *
 *	Of course memory pools have their disadvantages as well. The biggest one is
 *	the fact, that there is no way to deallocate only single object. Whole pool
 *	(or block) has to be deallocated at once. (Although it's not tough to add
 *	this kind of behavior to memory pool classes, but there is no need of it in
 *	PACE, so it would be useless overhead cost).
 *
 *	The memory pools are implemented as templates, so they can be used with
 *	various types.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _POOL_H
#define	_POOL_H

#include <cassert>
#include <map>

namespace ace {

/////// MemoryBlock ///////

/** Memory block is designed to keep large continuous chunk of memory within
 *	and provides methods for subsequent transfer of small pieces to client subjects.
 *	@param _Type Type to be stored within the block.
 */
template<class _Type>
class MemoryBlock {
	/** Stored unit size (sizeof(_Type) result).
	 */
	const size_t _unit_size;
	/** Pointers to the start of the block
	 *	Following must be always true: _memory <= _free <= _upper_bound.
	 */
	_Type *_memory;
	/** Pointer to the beginning of free memory.
	 *	Following must be always true: _memory <= _free <= _upper_bound.
	 */
	_Type *_free;
	/** Pointers to the first address behind block memory.
	 *	Following must be always true: _memory <= _free <= _upper_bound.
	 */
	_Type *_upper_bound;

protected:
	// TODO: Block assignments between derived classes?
	/** No copy constructs.
	 */	
	MemoryBlock<_Type>(const MemoryBlock<_Type>& mpb);
	/** No assignments.
	 */
	MemoryBlock<_Type>& operator=(const MemoryBlock<_Type>& mpb);

public:	
	/** Constructor tries to allocate memory `block_size` units long.
	 *	If allocation succeeds both `_start` and `_free` point to the newly allocated
	 *	memory, otherwise std::bad_alloc is throwed.
	 *	@param block_size Size of newly allocated memory (in template type units).
	 *	@throws std::bad_alloc When the memory for block cannot be allocated.
	 */
	MemoryBlock(size_t block_size): _unit_size(sizeof(_Type)), _memory(NULL), _free(NULL), _upper_bound(NULL) {
		_free = _memory = static_cast<_Type *>(operator new(block_size*_unit_size));
		_upper_bound = _memory + block_size;
	}
	/** Destructor frees allocated memory.
	 */
	virtual ~MemoryBlock(void) throw() {
		operator delete(_memory);
	}
	/** @returns Pointer to the next free chunk of memory within the block.
	 */
	inline _Type * assigned_mem_bound(void) const throw() { return _free; }
	/** @return Count of remaining free space within block.
	 */
	inline size_t count_free_memory(void) const throw() { return (_free != NULL) ? (_upper_bound - _free) : 0; }
	/** @return True, if no more memory can be assigned within this block.
	 */
	inline bool is_full(void) const throw() { return ( (_memory != NULL) && (_free == _upper_bound) ); }
	/** Returns pointer to the next `mem_size` units long chunk of memory and advances
	 *	internal free memory pointer. In case there is not enough of memory in the pool
	 *	NULL is returned.
	 *	@param mem_size Size of demanded memory (in units stored, not in bytes!).
	 *	@return Pointer to free memory of size `mem_size` or NULL.
	 */
	_Type * get_memory(size_t mem_size = 1) throw() {
		if ( (_memory == NULL) || (count_free_memory() < mem_size) ) {
			// Also catches when mem_size == 0.
			return NULL;
		}
		_Type *alloc = _free;
		// Advance internal free memory pointer by `mem_size`!
		_free += mem_size;
		return alloc;
	}
	/** @return Pointer to the first address within the memory block.
	 */
	inline _Type * lower_bound(void) const throw() { return _memory; }
	/** @return Pointer to the first address behind the memory block.
	 */
	inline _Type * upper_bound(void) const throw() { return _upper_bound; }
	/** @return Size of stored unit (result of sizeof(_Type) operator).
	 */
	inline size_t unit_size(void) const throw() { return _unit_size; }
};


/** Definition of memory pool (abstract) interface. Doesn't do much, just define some
 *	basic behavior.
 *	@param _Type Stored unit type.
 *	@param _Block Pool memory block template class.
 */
template<class _Type, template<typename _Type> class _Block>
class MemoryPool {
	/** Block size
	 */
	size_t _block_size;

protected:

	/** Function for allocation of new memory blocks.
	 */
	virtual _Block<_Type> * create_new_block(void) = 0;

public:
	/** Constructor accepts and stores block size, doesn't allocate any memory yet.
	 *	@param block_size Size of memory blocks within the pool.
	 */
	MemoryPool(size_t block_size) throw(): _block_size(block_size) {}
	/** Destructor does nothing useful, just is.
	 */
	virtual ~MemoryPool(void) throw() {}
	/** @return Size of single memory block.
	 */
	inline size_t block_size(void) const throw() { return _block_size; }
	/** Method used to clear the pool - should deallocate all dynamically allocated memory.
	 */
	virtual void clear(void) throw() = 0;
	/** Returns pointer to free memory of size `mem_size` or throws std::bad_alloc in case
	 *	there is not enough free memory.
	 *	@param mem_size The size of demanded memory.
	 *	@return Pointer to beginning of the returned memory.
	 *	@throws std::bad_alloc When there is no more memory available.
	 */
	virtual _Type * get_memory(size_t mem_size) = 0;
};


/**	RandomSizedMemoryPool, as its name suggests, allows to transfer various-sized chunks
 *	of memory. It's perfectly useful to stored random-sized strings (as char sequences).
 *	Note that class is derived from MemoryPool template class with given type and
 *	MemoryBlock as particular type of block to be used.
 *	@param _Type Stored unit type.
 */
template<class _Type>
class RandomSizedMemoryPool: public MemoryPool<_Type, MemoryBlock> {
protected:
	/**
	 */
	typedef MemoryBlock<_Type> _block_type;

	// TODO: Remember the pool with maximum free memory (heap-like approach)?
	/** Type used to keep info about remaining (available) memory in all existing pool blocks,
	 *	except the one recently used (see below).
	 */
	typedef typename std::multimap<size_t, _block_type *> _blocks_free_sizes_map;
	/** Pool block recently used for allocation.
	 */
	_block_type *_recently_used_block;
	/** Mapping from size of available free memory in certain block to the pointer to its instance.
	 */
	_blocks_free_sizes_map _mem_blocks;

protected:
	/** Creates new memory block.
	 *	@return Pointer to newly created memory pool block.
	 *	@throws std::bad_alloc when there is not enough memory left to allocate new pool block. 
	 */
	virtual _block_type * create_new_block(void) {
		// Get new block with desired size and return.
		return new _block_type(this->block_size()); // This may throw!
	}

public:		
	/** Constructor initializes new pool, but does not allocate any memory.
	 *	@param block_size Size of memory blocks within the pool.
	 */
	RandomSizedMemoryPool(size_t block_size) throw(): MemoryPool<_Type, MemoryBlock>(block_size), _recently_used_block(NULL), _mem_blocks() {}
	/** Destructor frees all allocated memory by calling clear().
	 */
	virtual ~RandomSizedMemoryPool(void) throw() {
		this->clear();
	}
	/** Frees all the allocated memory (deletes all memory pool blocks). Use only when there is a guaranty
	 *	that there are no pointers pointing at the memory pool left.
	 */
	virtual void clear(void) throw() {
		// Call delete on every memory block.
		for ( typename _blocks_free_sizes_map::iterator i_pool = _mem_blocks.begin(); i_pool != _mem_blocks.end(); ++i_pool ) {
			delete i_pool->second;
		}
		// Clear pools map.
		_mem_blocks.clear();
	}
	/** Returns pointer to free memory of size `mem_size`. If `mem_size` is bigger than size
	 *	of memory blocks within the pool, NULL is returned. Moreover if there is not enough
	 *	memory and new memory cannot be allocated, function throws std::bad_alloc.
	 *	there is not enough free memory.
	 *	@param mem_size The size of demanded memory.
	 *	@return Pointer to beginning of the returned memory or NULL if `mem_size` is invalid.
	 *	@throws std::bad_alloc When there is no more memory available.
	 */
	virtual _Type * get_memory(size_t mem_size) {
		
		if ( mem_size > this->block_size() ) {
			// No way to get so much memory...
			return NULL;
		}
		
		_block_type *mb = NULL;
		
		// So, which block to use (which has enough of memory?)
		if ( _recently_used_block == NULL ) {
			// First block to be created within the pool.
			mb = _recently_used_block = this->create_new_block(); // This may throw!
		} else if ( mem_size <= _recently_used_block->count_free_memory() ) {
			// There is enough memory in recently used block.
			mb = _recently_used_block;
		} else {
			// Recently used block has not enough free memory.
			if ( !_mem_blocks.empty() && (mem_size <= _mem_blocks.rbegin()->first) ) {			
				// There must be already allocated block with enough free memory.
				// Find the smallest one.
				typename _blocks_free_sizes_map::iterator i_pools = _mem_blocks.lower_bound(mem_size);
				// Following must be always true.
				assert(i_pools != _mem_blocks.end());
				// Get the block.
				mb = i_pools->second;
				// After memory retrieval this mapping will not be up-to-date anymore, so:
				_mem_blocks.erase(i_pools);
			} else {
				// No allocated block within pool has enough memory.
				// Get brand new block.
				mb = create_new_block(); // This may throw!
			}
			// Recently used memory block will be no longer "recently used",
			// so store it inside the memory blocks map.
			_mem_blocks.insert(typename _blocks_free_sizes_map::value_type(_recently_used_block->count_free_memory(), _recently_used_block));
			// Store for future use:
			_recently_used_block = mb;
		}
		// Return pointer to desired memory:
		return mb->get_memory(mem_size);
	}
};

/** VoidPool performs as pool of void type, although internally
 *	it's implementation is based on pool of char(s).
 */
class VoidPool: public RandomSizedMemoryPool<char> {
public:
	/** Constructor initializes new pool, but does not allocate any memory.
	 *	@param block_size Size of the pool (in sizeof(chars)).
	 */
	VoidPool(size_t block_size) throw(): RandomSizedMemoryPool<char>(block_size) {}
	/** Destroys the pool, deallocate all blocks.
	 */
	virtual ~VoidPool(void) throw() {}

	/** Returns pointer to free memory of size `mem_size`. If `mem_size` is bigger than size
	 *	of memory blocks within the pool, NULL is returned. Moreover if there is not enough
	 *	memory and new memory cannot be allocated, function throws std::bad_alloc.
	 *	@param mem_size The size of demanded memory.
	 *	@return Pointer to beginning of the returned memory or NULL if `mem_size` is invalid.
	 *	@throws std::bad_alloc When there is no more memory available.
	 */
	virtual void * get_raw_memory(size_t mem_size) {
		return this->get_memory(mem_size);
	}

};

} // namespace ace

#endif
