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

Last change on this file since 285 was 285, checked in by orlov, 18 years ago

* empty log message *

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 3.1 KB
Line 
1// $Source$
2// $Revision: 285 $
3// $Date: 2002-12-16 08:15:24 +0000 (Mon, 16 Dec 2002) $
4
5#include "pxx_heap_allocator.hh"
6
7namespace pxx
8{
9
10HeapAllocator::HeapAllocator (
11  void* const _start,
12  size_t const _heap_size,
13  int _fd /* = 0 */,
14  bool _need_remap /* = true */
15) :
16  heap (_start, _heap_size, page_size, _fd, _need_remap),
17  min_free_order (get_order(sizeof(MemoryBlock)))
18{
19  for (unsigned i = min_free_order; i < ROUNDS_SIZE; i++) {
20    lists[i].init_size(rounds[i]);
21  }
22  (lists + get_order(page_size))->insert(static_cast<MemoryBlock*>(_start));
23}
24
25HeapAllocator::~HeapAllocator ()
26{}
27
28void* HeapAllocator::allocate (size_t _size, size_t *_order)
29{
30  //
31  // first try to allocate a block within current heap
32  {
33    size_t order = get_order(_size);
34    if (order < min_free_order) order = min_free_order;
35    _size = rounds[order];
36    //
37    // choose appropriate block lists
38    MemoryBlock *first_list = lists + order;
39    MemoryBlock *last_list  = lists + heap.get_current_order();
40    //
41    // Walk through the lists until find a non-empty one. Then get a pointer
42    // to next free block in it, rearrange memory, set *_order to the true
43    // order of allocated block, and retrun pointer to the block.
44    for (MemoryBlock *p = first_list; p <= last_list; p++) {
45      if (!p->list_is_empty()) {
46        MemoryBlock *q = p->get_free_block();
47        for (--p; p >= first_list; p--) {
48          p->insert_rest(q);
49        }
50        *_order = order;
51        return q;
52      }
53    }
54  }
55  //
56  // if current heap exhausted try to expand it
57  {
58    //
59    // here we did not find any non-empty free block list,
60    // so we should expand a heap
61    //
62    // if nothing there is in the heap then catenate blocks in one big chunk,
63    // else insert separate block
64    size_t order   = heap.get_current_order();
65    size_t size    = rounds[order];
66    int    shift   = 1;
67    MemoryBlock *start = static_cast<MemoryBlock*>(heap.get_start());
68    if (start->block_is_empty(size)) {
69      size  = 0;
70      shift = 0;
71    }
72    heap.expand();
73    (lists + (heap.get_current_order() - shift))->insert(ptr_add(start, size));
74    return allocate(_size, _order);
75  }
76}
77
78void HeapAllocator::deallocate (void* _ptr, size_t _order)
79{
80  size_t size = rounds[_order];
81  size_t current_size = rounds[heap.get_current_order()];
82  MemoryBlock *start = static_cast<MemoryBlock*>(heap.get_start());
83  //
84  // loop and glue adjacent free blocks
85  for (; size < current_size; size <<=1) {
86    //
87    // get a pointer to appropriate adjacent block
88    MemoryBlock *q = ptr_add(start, (sub_ptr(_ptr, start) ^ size));
89    //
90    // if it isn't free then break
91    if (!q->block_is_empty(size)) break;
92    //
93    // else delete it from list
94    q->remove();
95    //
96    // and obtain a pointer to combined free block
97    _ptr = ptr_add(start, sub_ptr(_ptr, start) & ~size);
98  }
99  //
100  // insert it into appropriate free blocks list
101  (lists + get_order(size))->insert(static_cast<MemoryBlock*>(_ptr));
102}
103
104
105#if DEBUG
106
107void HeapAllocator::MemoryBlock::print_list() const
108{
109  for (MemoryBlock *q = next; q != this; q = q->next)
110  {
111    printf(" %p(%d,%p,%p)", q, q->size, q->prev, q->next);
112  }
113  printf("\n");
114}
115
116#endif // DEBUG
117
118}
Note: See TracBrowser for help on using the repository browser.