source: to-imperative/trunk/runtime/pxx_heap_allocator.hh @ 286

// $Source$
// $Revision: 286 $
// $Date: 2002-12-17 13:29:30 +0000 (Tue, 17 Dec 2002) $

#ifndef __pxx_heap_allocator_hh__
#define __pxx_heap_allocator_hh__

#include "pxx_heap.hh"

namespace pxx {

class HeapAllocator
{
  //
  // linked list of free memory blocks
  class MemoryBlock
  {
    uintptr_t    size;          // size of block
    MemoryBlock *prev;          // pointer to previous free block
    MemoryBlock *next;          // pointer to next free block

#if PARANOIA
  //
  // private copy constructor and operator= for error checking,
  // memory blocks shouldn't be copied but inserted/removed instead
  inline MemoryBlock( const MemoryBlock & );
  inline const MemoryBlock &operator=( const MemoryBlock & );
#endif
    //
    // following and only following private messages we recive from
    // HeapAllocator
    friend class HeapAllocator;
    //
    // we can't set size from default constructor, so HeapAllocator's
    // constructor should send us appropriate message
    inline void init_size( size_t _size );
  public:
    //
    // default constructor doesn't set size
    MemoryBlock() : prev( this ), next( this ) {};
    //
    // check if current list is empty
    inline bool list_is_empty() const;
    //
    // take off next free block from the list and return pointer to it
    inline MemoryBlock *get_free_block();
    //
    // remove block from its list
    inline void remove();
    //
    // insert new _block in this list
    inline void insert( MemoryBlock *_block );
    //
    // insert proper amount of memory in the proper distance from _block,
    // when some memory starting from _block is allocated
    inline void insert_rest( MemoryBlock *_block );
    //
    // check if block is completely empty, i.e. its size is equal to its
    // maximum possible size, which is passed to the function as parameter
    inline bool block_is_empty( size_t _size ) const;
#if DEBUG
    //
    // dump block list to the screen
    void print_list() const;
    //
    // print sizes of all blocks in the heap starting from this and ending
    // before this + _current_size,
    // ((T*)this)->get_order() should return real order of the block
    template <class T>
    void print_blocks( size_t _current_size );
#endif // DEBUG
  };
  
private:

  Heap heap;
  size_t min_free_order;
  MemoryBlock lists [ROUNDS_SIZE];

public:
  //
  // constructor
  HeapAllocator(
    void* const _start,
    size_t const _heap_size,
    int _fd = 0,
    bool _need_remap = true
  );
  //
  // destructor
  ~HeapAllocator();
  //
  // allocate memory block of _size bytes and set *_order to the real order of
  // allocated space
  void *allocate( size_t _size, size_t *_order );
  //
  // free memory block of size rounds[_order] at _ptr
  void deallocate( void *_ptr, size_t _order );
  //
  // _ptr points inside memory block of size rounds[_order],
  // return pointer to its start
  inline void *get_block_start( void *_ptr, size_t _order ) const;
  
#if DEBUG
  //
  // dump memory map
  // T::get_order() should return real order of memory blocks
  template <class T>
  void memory_dump() const;
#endif // DEBUG

};

#if PARANOIA

inline HeapAllocator::MemoryBlock::MemoryBlock( const MemoryBlock & )
{
  FATAL( "Copy constructor for MemoryBlock class shouldn't be used!" );
}

inline const
HeapAllocator::MemoryBlock &HeapAllocator::MemoryBlock::operator=(
    const MemoryBlock &
)
{
  FATAL( "operator=() for MemoryBlock class shouldn't be used!" );
  return *this;
}

#endif

inline void HeapAllocator::MemoryBlock::init_size( size_t _size )
{
  size = _size;
}

inline bool HeapAllocator::MemoryBlock::list_is_empty() const
{
  return this == next;
}

inline HeapAllocator::MemoryBlock *HeapAllocator::MemoryBlock::get_free_block()
{
  MemoryBlock *block = next;
  block->remove();
  return block;
}

inline void HeapAllocator::MemoryBlock::remove()
{
  prev->next = next;
  next->prev = prev;
}

inline void HeapAllocator::MemoryBlock::insert( MemoryBlock *_block )
{
  _block->next = this;
  _block->prev = prev;
  prev->next = _block;
  prev = _block;
  _block->size = size;
}

inline void HeapAllocator::MemoryBlock::insert_rest( MemoryBlock *_block )
{
  insert( ptr_add(_block, size) );
}

inline bool HeapAllocator::MemoryBlock::block_is_empty( size_t _size ) const
{
  return _size == size;
}

inline void *HeapAllocator::get_block_start( void *_ptr, size_t _order ) const
{
  return ptr_add( heap.get_start(),
                  sub_ptr(_ptr, heap.get_start()) & ~(rounds[_order] - 1) );
}


#if DEBUG

template <class T>
void HeapAllocator::MemoryBlock::print_blocks( size_t _current_size )
{
  for( size_t offset = 0; offset < _current_size; )
  {
    MemoryBlock *q = ptr_add( this, offset );
    size_t sz = q->size;
    if( sz & (sz - 1) )
    {
      sz = rounds[((T*)q)->get_order()];
      printf( "a(%p):%u ", q, sz );
    }
    else
    {
      printf( "f(%p):%u ", q, sz );
    }
    if( !sz )
    {
      printf( "...block orders are corrupted..." );
      break;
    }
    offset += sz;
  }
  printf( "\n\n" );
}

template <class T>
void HeapAllocator::memory_dump() const
{
  MemoryBlock *p = (MemoryBlock*)( heap.get_start() );
  printf( "Heap at %p\n", p );
  p->MemoryBlock::print_blocks<T>( rounds[heap.get_current_order()] );

  for (unsigned i =  min_free_order;
                i <= heap.get_current_order();
                i++)
  {
    printf( "%u(%p):", rounds[i], lists + i );
    (lists + i)->print_list();
  }
  printf( "\n" );
}

#endif // DEBUG

}

#endif // __pxx_heap_allocator_hh__