blob: 4c088b8c27fe80244ac1c5f4334fe81d4928ff69 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
// SPDX-License-Identifier: GPL-2.0-or-later
/*
* Pool memory allocation
*
* Authors:
* Stéphane Gimenez <dev@gim.name>
*
* Copyright (C) 2004-2006 Authors
*
* Released under GNU GPL v2+, read the file 'COPYING' for more information.
*/
// not thread safe (a pool cannot be shared by threads safely)
/*
-- principle:
- user operations on a pool of objects of type T are:
- T *draw() : obtain a unused slot to store an object T
- void drop(T *) : release a slot
-- implementation:
- a pool for objects T is:
* blocks[64] : an array of allocated blocks of memory:
|---0--> block with capacity 64
|---1--> block with capacity 64
|---2--> block with capacity 128
|---3--> block with capacity 128
|---4--> block with capacity 256
|---5--> block with capacity 256
|---6--> block with capacity 512
|---7--> not yet allocated
:
|---k--> not yet allocated (future capacity ~ 2^(6+k/2))
:
'--63--> not yet allocated
* cblock : the index of the next unallocated block (here 7).
* next : a pointer to an unused slot inside an allocated bloc
- the first bytes of an unallocated slot inside a bloc are used to store a
pointer to some other unallocated slot. (this way, we keep a list of all
unused slots starting at <next>)
- insertions and deletions in this list are done at the root <next>.
if <next> points to NULL (no slots are available) when a draw()
operation is performed a new block is allocated, and the unused slots
list is filled with the allocated slots.
- memory is freed only at pool's deletion.
*/
#include <cstdlib>
template <typename T>
class pool {
public:
pool()
{
cblock = 0;
size = sizeof(T) > sizeof(void *) ? sizeof(T) : sizeof(void *);
next = nullptr;
for (auto & k : block) {
k = nullptr;
}
}
~pool()
{
for (int k = 0; k < cblock; k++) {
free(block[k]);
}
}
T *draw()
{
if (!next) addblock();
void *p = next;
next = *(void **)p;
return (T *) p;
}
void drop(T *p)
{
*(void **)p = next;
next = (void *) p;
}
private:
int size;
int cblock;
void *block[64]; //enough to store unlimited number of objects, if 64 is changed: see constructor too
void *next;
void addblock()
{
int i = cblock++;
int blocksize = 1 << (6 + (i/2));
//printf("pool allocating block: %d (size:%d)...", i, blocksize);//debug
block[i] = (void *)malloc(blocksize * size);
if (!block[i]) throw std::bad_alloc();
char *p = (char *)block[i];
for (int k = 0; k < blocksize - 1; k++)
{
*(void**)p = (void *)(p + size);
p += size;
}
*(void **)p = next;
next = block[i];
//printf("done\n");//debug
}
};
|
