source: to-imperative/trunk/runtime/pxx_heap_allocator.cc @ 285

// $Source$
// $Revision: 285 $
// $Date: 2002-12-16 08:15:24 +0000 (Mon, 16 Dec 2002) $

#include "pxx_heap_allocator.hh"

namespace pxx
{

HeapAllocator::HeapAllocator (
  void* const _start,
  size_t const _heap_size,
  int _fd /* = 0 */,
  bool _need_remap /* = true */
) :
  heap (_start, _heap_size, page_size, _fd, _need_remap),
  min_free_order (get_order(sizeof(MemoryBlock)))
{
  for (unsigned i = min_free_order; i < ROUNDS_SIZE; i++) {
    lists[i].init_size(rounds[i]);
  }
  (lists + get_order(page_size))->insert(static_cast<MemoryBlock*>(_start));
}

HeapAllocator::~HeapAllocator ()
{}

void* HeapAllocator::allocate (size_t _size, size_t *_order)
{
  //
  // first try to allocate a block within current heap
  {
    size_t order = get_order(_size);
    if (order < min_free_order) order = min_free_order;
    _size = rounds[order];
    //
    // choose appropriate block lists
    MemoryBlock *first_list = lists + order;
    MemoryBlock *last_list  = lists + heap.get_current_order();
    //
    // Walk through the lists until find a non-empty one. Then get a pointer
    // to next free block in it, rearrange memory, set *_order to the true
    // order of allocated block, and retrun pointer to the block.
    for (MemoryBlock *p = first_list; p <= last_list; p++) {
      if (!p->list_is_empty()) {
        MemoryBlock *q = p->get_free_block();
        for (--p; p >= first_list; p--) {
          p->insert_rest(q);
        }
        *_order = order;
        return q;
      }
    }
  }
  //
  // if current heap exhausted try to expand it
  {
    //
    // here we did not find any non-empty free block list,
    // so we should expand a heap
    //
    // if nothing there is in the heap then catenate blocks in one big chunk,
    // else insert separate block
    size_t order   = heap.get_current_order();
    size_t size    = rounds[order];
    int    shift   = 1;
    MemoryBlock *start = static_cast<MemoryBlock*>(heap.get_start());
    if (start->block_is_empty(size)) {
      size  = 0;
      shift = 0;
    }
    heap.expand();
    (lists + (heap.get_current_order() - shift))->insert(ptr_add(start, size));
    return allocate(_size, _order);
  }
}

void HeapAllocator::deallocate (void* _ptr, size_t _order)
{
  size_t size = rounds[_order];
  size_t current_size = rounds[heap.get_current_order()];
  MemoryBlock *start = static_cast<MemoryBlock*>(heap.get_start());
  //
  // loop and glue adjacent free blocks
  for (; size < current_size; size <<=1) {
    //
    // get a pointer to appropriate adjacent block
    MemoryBlock *q = ptr_add(start, (sub_ptr(_ptr, start) ^ size));
    //
    // if it isn't free then break
    if (!q->block_is_empty(size)) break;
    //
    // else delete it from list
    q->remove();
    //
    // and obtain a pointer to combined free block
    _ptr = ptr_add(start, sub_ptr(_ptr, start) & ~size);
  }
  //
  // insert it into appropriate free blocks list
  (lists + get_order(size))->insert(static_cast<MemoryBlock*>(_ptr));
}


#if DEBUG

void HeapAllocator::MemoryBlock::print_list() const
{
  for (MemoryBlock *q = next; q != this; q = q->next)
  {
    printf(" %p(%d,%p,%p)", q, q->size, q->prev, q->next);
  }
  printf("\n");
}

#endif // DEBUG

}