blob: 742050a681972aed8136988fa92a8fcf4d2dd354 (
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
|
// 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.
*/
#ifndef INKSCAPE_TRACE_POOL_H
#define INKSCAPE_TRACE_POOL_H
#include <cstdlib>
#include <exception>
#include <algorithm>
template <typename T>
class Pool
{
public:
Pool()
{
cblock = 0;
size = std::max(sizeof(T), sizeof(void *));
next = nullptr;
for (auto &k : block) {
k = nullptr;
}
}
~Pool()
{
for (int k = 0; k < cblock; k++) {
std::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));
block[i] = (void *)std::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];
}
};
#endif // INKSCAPE_TRACE_POOL_H
|
