pool.h revision 05006d8a2d9936dd59989a228de12a5e316fd29b
e8767bd3cabb360b1307698236a7778044950900buliabyak/*
e8767bd3cabb360b1307698236a7778044950900buliabyak * Pool memory allocation
e8767bd3cabb360b1307698236a7778044950900buliabyak *
e8767bd3cabb360b1307698236a7778044950900buliabyak * Authors:
e8767bd3cabb360b1307698236a7778044950900buliabyak * Stéphane Gimenez <dev@gim.name>
e8767bd3cabb360b1307698236a7778044950900buliabyak *
e8767bd3cabb360b1307698236a7778044950900buliabyak * Copyright (C) 2004-2006 Authors
e8767bd3cabb360b1307698236a7778044950900buliabyak *
e8767bd3cabb360b1307698236a7778044950900buliabyak * Released under GNU GPL, read the file 'COPYING' for more information
e8767bd3cabb360b1307698236a7778044950900buliabyak */
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak// not thread safe (a pool cannot be shared by threads safely)
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak/*
e8767bd3cabb360b1307698236a7778044950900buliabyak-- principle:
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak - user operations on a pool of objects of type T are:
e8767bd3cabb360b1307698236a7778044950900buliabyak - T *draw() : obtain a unused slot to store an object T
e8767bd3cabb360b1307698236a7778044950900buliabyak - void drop(T *) : realease a slot
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak-- implementation:
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak - a pool for objects T is:
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak * blocks[64] : an array of allocated blocks of memory:
e8767bd3cabb360b1307698236a7778044950900buliabyak |---0--> block with capacity 64
e8767bd3cabb360b1307698236a7778044950900buliabyak |---1--> block with capacity 64
e8767bd3cabb360b1307698236a7778044950900buliabyak |---2--> block with capacity 128
e8767bd3cabb360b1307698236a7778044950900buliabyak |---3--> block with capacity 128
e8767bd3cabb360b1307698236a7778044950900buliabyak |---4--> block with capacity 256
e8767bd3cabb360b1307698236a7778044950900buliabyak |---5--> block with capacity 256
e8767bd3cabb360b1307698236a7778044950900buliabyak |---6--> block with capacity 512
e8767bd3cabb360b1307698236a7778044950900buliabyak |---7--> not yet allocated
e8767bd3cabb360b1307698236a7778044950900buliabyak :
e8767bd3cabb360b1307698236a7778044950900buliabyak |---k--> not yet allocated (future capacity ~ 2^(6+k/2))
e8767bd3cabb360b1307698236a7778044950900buliabyak :
e8767bd3cabb360b1307698236a7778044950900buliabyak '--63--> not yet allocated
e8767bd3cabb360b1307698236a7778044950900buliabyak * cblock : the index of the next unallocated block (here 7).
e8767bd3cabb360b1307698236a7778044950900buliabyak * next : a pointer to an unused slot inside an allocated bloc
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak - the first bytes of an unallocated slot inside a bloc are used to store a
e8767bd3cabb360b1307698236a7778044950900buliabyak pointer to some other unallocated slot. (this way, we keep a list of all
e8767bd3cabb360b1307698236a7778044950900buliabyak unused slots starting at <next>)
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak - insertions and deletions in this list are done at the root <next>.
e8767bd3cabb360b1307698236a7778044950900buliabyak if <next> points to NULL (no slots are availlable) when a draw()
e8767bd3cabb360b1307698236a7778044950900buliabyak operation is performed a new block is allocated, and the unused slots
e8767bd3cabb360b1307698236a7778044950900buliabyak list is filled with the allocated slots.
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak - memory is freed only at pool's deletion.
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak*/
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak#include <stdlib.h>
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyaktemplate <typename T>
e8767bd3cabb360b1307698236a7778044950900buliabyakclass pool {
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak public:
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak pool()
e8767bd3cabb360b1307698236a7778044950900buliabyak {
e8767bd3cabb360b1307698236a7778044950900buliabyak cblock = 0;
e8767bd3cabb360b1307698236a7778044950900buliabyak size = sizeof(T) > sizeof(void *) ? sizeof(T) : sizeof(void *);
e8767bd3cabb360b1307698236a7778044950900buliabyak next = NULL;
e8767bd3cabb360b1307698236a7778044950900buliabyak }
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak ~pool()
e8767bd3cabb360b1307698236a7778044950900buliabyak {
e8767bd3cabb360b1307698236a7778044950900buliabyak for (int k = 0; k < cblock; k++)
e8767bd3cabb360b1307698236a7778044950900buliabyak free(block[k]);
e8767bd3cabb360b1307698236a7778044950900buliabyak }
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak T *draw()
e8767bd3cabb360b1307698236a7778044950900buliabyak {
e8767bd3cabb360b1307698236a7778044950900buliabyak if (!next) addblock();
e8767bd3cabb360b1307698236a7778044950900buliabyak void *p = next;
e8767bd3cabb360b1307698236a7778044950900buliabyak next = *(void **)p;
e8767bd3cabb360b1307698236a7778044950900buliabyak return (T *) p;
e8767bd3cabb360b1307698236a7778044950900buliabyak }
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak void drop(T *p)
e8767bd3cabb360b1307698236a7778044950900buliabyak {
e8767bd3cabb360b1307698236a7778044950900buliabyak *(void **)p = next;
e8767bd3cabb360b1307698236a7778044950900buliabyak next = (void *) p;
e8767bd3cabb360b1307698236a7778044950900buliabyak }
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak private:
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak int size;
e8767bd3cabb360b1307698236a7778044950900buliabyak int cblock;
e8767bd3cabb360b1307698236a7778044950900buliabyak void *block[64]; //enough to store unlimited number of objects
e8767bd3cabb360b1307698236a7778044950900buliabyak void *next;
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak void addblock()
e8767bd3cabb360b1307698236a7778044950900buliabyak {
e8767bd3cabb360b1307698236a7778044950900buliabyak int i = cblock++;
e8767bd3cabb360b1307698236a7778044950900buliabyak int blocksize = 1 << (6 + (i/2));
e8767bd3cabb360b1307698236a7778044950900buliabyak //printf("pool allocating block: %d (size:%d)...", i, blocksize);//debug
e8767bd3cabb360b1307698236a7778044950900buliabyak block[i] = (void *)malloc(blocksize * size);
e8767bd3cabb360b1307698236a7778044950900buliabyak if (!block[i]) throw std::bad_alloc();
05006d8a2d9936dd59989a228de12a5e316fd29bsgimenez char *p = (char *)block[i];
e8767bd3cabb360b1307698236a7778044950900buliabyak for (int k = 0; k < blocksize - 1; k++)
e8767bd3cabb360b1307698236a7778044950900buliabyak {
05006d8a2d9936dd59989a228de12a5e316fd29bsgimenez *(void**)p = (void *)(p + size);
05006d8a2d9936dd59989a228de12a5e316fd29bsgimenez p += size;
e8767bd3cabb360b1307698236a7778044950900buliabyak }
e8767bd3cabb360b1307698236a7778044950900buliabyak *(void **)p = next;
e8767bd3cabb360b1307698236a7778044950900buliabyak next = block[i];
e8767bd3cabb360b1307698236a7778044950900buliabyak //printf("done\n");//debug
e8767bd3cabb360b1307698236a7778044950900buliabyak }
e8767bd3cabb360b1307698236a7778044950900buliabyak
e8767bd3cabb360b1307698236a7778044950900buliabyak};
e8767bd3cabb360b1307698236a7778044950900buliabyak