src/trace/pool.h

   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  */
  11
  12 // not thread safe (a pool cannot be shared by threads safely)
  13
  14 /*
  15 -- principle:
  16
  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
  20
  21 -- implementation:
  22
  23  - a pool for objects T is:
  24
  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
  40
  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>)
  44
  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.
  49
  50  - memory is freed only at pool's deletion.
  51
  52 */
  53
  54 #include <stdlib.h>
  55
  56 template <typename T>
  57 class pool {
  58
  59  public:
  60
  61   pool()
  62     {
  63       cblock = 0;
  64       size = sizeof(T) > sizeof(void *) ? sizeof(T) : sizeof(void *);
  65       next = NULL;
  66     }
  67
  68   ~pool()
  69     {
  70       for (int k = 0; k < cblock; k++)
  71         free(block[k]);
  72     }
  73
  74   T *draw()
  75   {
  76     if (!next) addblock();
  77     void *p = next;
  78     next = *(void **)p;
  79     return (T *) p;
  80   }
  81
  82   void drop(T *p)
  83   {
  84     *(void **)p = next;
  85     next = (void *) p;
  86   }
  87
  88  private:
  89
  90   int size;
  91   int cblock;
  92   void *block[64]; //enough to store unlimited number of objects
  93   void *next;
  94
  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     }
 112
 113 };
 114