| 1 |
/* |
| 2 |
* block_alloc.hpp - Memory allocation in blocks |
| 3 |
* |
| 4 |
* Kheperix (C) 2003 Gwenole Beauchesne |
| 5 |
* |
| 6 |
* This program is free software; you can redistribute it and/or modify |
| 7 |
* it under the terms of the GNU General Public License as published by |
| 8 |
* the Free Software Foundation; either version 2 of the License, or |
| 9 |
* (at your option) any later version. |
| 10 |
* |
| 11 |
* This program is distributed in the hope that it will be useful, |
| 12 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 |
* GNU General Public License for more details. |
| 15 |
* |
| 16 |
* You should have received a copy of the GNU General Public License |
| 17 |
* along with this program; if not, write to the Free Software |
| 18 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 19 |
*/ |
| 20 |
|
| 21 |
#ifndef BLOCK_ALLOC_H |
| 22 |
#define BLOCK_ALLOC_H |
| 23 |
|
| 24 |
/** |
| 25 |
* Slow memory allocator |
| 26 |
* |
| 27 |
* Each time a DATA item is requested (resp. released), the block |
| 28 |
* is immediately allocated (resp. free'd). |
| 29 |
**/ |
| 30 |
|
| 31 |
template< class data > |
| 32 |
struct slow_allocator |
| 33 |
{ |
| 34 |
data * acquire() const { return new data; } |
| 35 |
void release(data * const x) const { delete x; } |
| 36 |
}; |
| 37 |
|
| 38 |
/** |
| 39 |
* Lazy memory allocator |
| 40 |
* |
| 41 |
* Allocate a big memory block, typically larger than a page, |
| 42 |
* that contains up to POOL_COUNT data items of type DATA. |
| 43 |
**/ |
| 44 |
|
| 45 |
template< class data > |
| 46 |
class lazy_allocator |
| 47 |
{ |
| 48 |
static const int pool_size = 4096; |
| 49 |
static const int pool_count = 1 + pool_size / sizeof(data); |
| 50 |
|
| 51 |
struct chunk |
| 52 |
{ |
| 53 |
data value; |
| 54 |
chunk * next; |
| 55 |
}; |
| 56 |
|
| 57 |
struct pool |
| 58 |
{ |
| 59 |
chunk chunks[pool_count]; |
| 60 |
pool * next; |
| 61 |
}; |
| 62 |
|
| 63 |
pool * pools; |
| 64 |
chunk * chunks; |
| 65 |
|
| 66 |
public: |
| 67 |
lazy_allocator() : pools(0), chunks(0) { } |
| 68 |
~lazy_allocator(); |
| 69 |
data * acquire(); |
| 70 |
void release(data * const); |
| 71 |
}; |
| 72 |
|
| 73 |
template< class data > |
| 74 |
lazy_allocator<data>::~lazy_allocator() |
| 75 |
{ |
| 76 |
pool * p = pools; |
| 77 |
while (p) { |
| 78 |
pool * d = p; |
| 79 |
p = p->next; |
| 80 |
delete d; |
| 81 |
} |
| 82 |
} |
| 83 |
|
| 84 |
template< class data > |
| 85 |
data * lazy_allocator<data>::acquire() |
| 86 |
{ |
| 87 |
if (!chunks) { |
| 88 |
// There is no chunk left, allocate a new pool and link the |
| 89 |
// chunks into the free list |
| 90 |
pool * p = new pool; |
| 91 |
for (chunk * c = &p->chunks[0]; c < &p->chunks[pool_count]; c++) { |
| 92 |
c->next = chunks; |
| 93 |
chunks = c; |
| 94 |
} |
| 95 |
p->next = pools; |
| 96 |
pools = p; |
| 97 |
} |
| 98 |
chunk * c = chunks; |
| 99 |
chunks = c->next; |
| 100 |
return &c->value; |
| 101 |
} |
| 102 |
|
| 103 |
template< class data > |
| 104 |
void lazy_allocator<data>::release(data * const d) |
| 105 |
{ |
| 106 |
chunk *c = (chunk *)d; |
| 107 |
c->next = chunks; |
| 108 |
chunks = c; |
| 109 |
} |
| 110 |
|
| 111 |
/** |
| 112 |
* Helper memory allocator |
| 113 |
**/ |
| 114 |
|
| 115 |
template< class data_type, template< class > class allocator_type = lazy_allocator > |
| 116 |
class allocator_helper |
| 117 |
{ |
| 118 |
static allocator_type<data_type> allocator; |
| 119 |
public: |
| 120 |
static inline void *allocate() |
| 121 |
{ return allocator.acquire(); } |
| 122 |
static inline void deallocate(void * p) |
| 123 |
{ allocator.release((data_type *)p); } |
| 124 |
}; |
| 125 |
|
| 126 |
#endif /* BLOCK_ALLOC_H */ |
