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