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

Last change on this file since 286 was 286, 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: 5.4 KB
Line 
1// $Source$
2// $Revision: 286 $
3// $Date: 2002-12-17 13:29:30 +0000 (Tue, 17 Dec 2002) $
4
5#ifndef __pxx_heap_allocator_hh__
6#define __pxx_heap_allocator_hh__
7
8#include "pxx_heap.hh"
9
10namespace pxx {
11
12class HeapAllocator
13{
14  //
15  // linked list of free memory blocks
16  class MemoryBlock
17  {
18    uintptr_t    size;          // size of block
19    MemoryBlock *prev;          // pointer to previous free block
20    MemoryBlock *next;          // pointer to next free block
21
22#if PARANOIA
23  //
24  // private copy constructor and operator= for error checking,
25  // memory blocks shouldn't be copied but inserted/removed instead
26  inline MemoryBlock( const MemoryBlock & );
27  inline const MemoryBlock &operator=( const MemoryBlock & );
28#endif
29    //
30    // following and only following private messages we recive from
31    // HeapAllocator
32    friend class HeapAllocator;
33    //
34    // we can't set size from default constructor, so HeapAllocator's
35    // constructor should send us appropriate message
36    inline void init_size( size_t _size );
37  public:
38    //
39    // default constructor doesn't set size
40    MemoryBlock() : prev( this ), next( this ) {};
41    //
42    // check if current list is empty
43    inline bool list_is_empty() const;
44    //
45    // take off next free block from the list and return pointer to it
46    inline MemoryBlock *get_free_block();
47    //
48    // remove block from its list
49    inline void remove();
50    //
51    // insert new _block in this list
52    inline void insert( MemoryBlock *_block );
53    //
54    // insert proper amount of memory in the proper distance from _block,
55    // when some memory starting from _block is allocated
56    inline void insert_rest( MemoryBlock *_block );
57    //
58    // check if block is completely empty, i.e. its size is equal to its
59    // maximum possible size, which is passed to the function as parameter
60    inline bool block_is_empty( size_t _size ) const;
61#if DEBUG
62    //
63    // dump block list to the screen
64    void print_list() const;
65    //
66    // print sizes of all blocks in the heap starting from this and ending
67    // before this + _current_size,
68    // ((T*)this)->get_order() should return real order of the block
69    template <class T>
70    void print_blocks( size_t _current_size );
71#endif // DEBUG
72  };
73 
74private:
75
76  Heap heap;
77  size_t min_free_order;
78  MemoryBlock lists [ROUNDS_SIZE];
79
80public:
81  //
82  // constructor
83  HeapAllocator(
84    void* const _start,
85    size_t const _heap_size,
86    int _fd = 0,
87    bool _need_remap = true
88  );
89  //
90  // destructor
91  ~HeapAllocator();
92  //
93  // allocate memory block of _size bytes and set *_order to the real order of
94  // allocated space
95  void *allocate( size_t _size, size_t *_order );
96  //
97  // free memory block of size rounds[_order] at _ptr
98  void deallocate( void *_ptr, size_t _order );
99  //
100  // _ptr points inside memory block of size rounds[_order],
101  // return pointer to its start
102  inline void *get_block_start( void *_ptr, size_t _order ) const;
103 
104#if DEBUG
105  //
106  // dump memory map
107  // T::get_order() should return real order of memory blocks
108  template <class T>
109  void memory_dump() const;
110#endif // DEBUG
111
112};
113
114#if PARANOIA
115
116inline HeapAllocator::MemoryBlock::MemoryBlock( const MemoryBlock & )
117{
118  FATAL( "Copy constructor for MemoryBlock class shouldn't be used!" );
119}
120
121inline const
122HeapAllocator::MemoryBlock &HeapAllocator::MemoryBlock::operator=(
123    const MemoryBlock &
124)
125{
126  FATAL( "operator=() for MemoryBlock class shouldn't be used!" );
127  return *this;
128}
129
130#endif
131
132inline void HeapAllocator::MemoryBlock::init_size( size_t _size )
133{
134  size = _size;
135}
136
137inline bool HeapAllocator::MemoryBlock::list_is_empty() const
138{
139  return this == next;
140}
141
142inline HeapAllocator::MemoryBlock *HeapAllocator::MemoryBlock::get_free_block()
143{
144  MemoryBlock *block = next;
145  block->remove();
146  return block;
147}
148
149inline void HeapAllocator::MemoryBlock::remove()
150{
151  prev->next = next;
152  next->prev = prev;
153}
154
155inline void HeapAllocator::MemoryBlock::insert( MemoryBlock *_block )
156{
157  _block->next = this;
158  _block->prev = prev;
159  prev->next = _block;
160  prev = _block;
161  _block->size = size;
162}
163
164inline void HeapAllocator::MemoryBlock::insert_rest( MemoryBlock *_block )
165{
166  insert( ptr_add(_block, size) );
167}
168
169inline bool HeapAllocator::MemoryBlock::block_is_empty( size_t _size ) const
170{
171  return _size == size;
172}
173
174inline void *HeapAllocator::get_block_start( void *_ptr, size_t _order ) const
175{
176  return ptr_add( heap.get_start(),
177                  sub_ptr(_ptr, heap.get_start()) & ~(rounds[_order] - 1) );
178}
179
180
181#if DEBUG
182
183template <class T>
184void HeapAllocator::MemoryBlock::print_blocks( size_t _current_size )
185{
186  for( size_t offset = 0; offset < _current_size; )
187  {
188    MemoryBlock *q = ptr_add( this, offset );
189    size_t sz = q->size;
190    if( sz & (sz - 1) )
191    {
192      sz = rounds[((T*)q)->get_order()];
193      printf( "a(%p):%u ", q, sz );
194    }
195    else
196    {
197      printf( "f(%p):%u ", q, sz );
198    }
199    if( !sz )
200    {
201      printf( "...block orders are corrupted..." );
202      break;
203    }
204    offset += sz;
205  }
206  printf( "\n\n" );
207}
208
209template <class T>
210void HeapAllocator::memory_dump() const
211{
212  MemoryBlock *p = (MemoryBlock*)( heap.get_start() );
213  printf( "Heap at %p\n", p );
214  p->MemoryBlock::print_blocks<T>( rounds[heap.get_current_order()] );
215
216  for (unsigned i =  min_free_order;
217                i <= heap.get_current_order();
218                i++)
219  {
220    printf( "%u(%p):", rounds[i], lists + i );
221    (lists + i)->print_list();
222  }
223  printf( "\n" );
224}
225
226#endif // DEBUG
227
228}
229
230#endif // __pxx_heap_allocator_hh__
Note: See TracBrowser for help on using the repository browser.