diff options
Diffstat (limited to '')
-rw-r--r-- | src/trace/pool.h | 119 |
1 files changed, 119 insertions, 0 deletions
diff --git a/src/trace/pool.h b/src/trace/pool.h new file mode 100644 index 0000000..4c088b8 --- /dev/null +++ b/src/trace/pool.h @@ -0,0 +1,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 + } + +}; + |