patch 1598684: better trace quantization

(bzr r1994)

1 files changed, 114 insertions, 0 deletions

diff --git a/src/trace/pool.h b/src/trace/pool.h
new file mode 100644
index 000000000..3f722f538
--- /dev/null
+++ b/src/trace/pool.h
@@ -0,0 +1,114 @@
+/*
+ * Pool memory allocation
+ *
+ * Authors:
+ *   Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL, 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 *) : realease 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 availlable) 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 <stdlib.h>
+
+template <typename T>
+class pool {
+
+ public:
+
+  pool()
+    {
+      cblock = 0;
+      size = sizeof(T) > sizeof(void *) ? sizeof(T) : sizeof(void *);
+      next = NULL;
+    }
+
+  ~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
+  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();
+      void *p = block[i];
+      for (int k = 0; k < blocksize - 1; k++)
+	{
+	  *(void**)p = (void *)((int)p + size);
+	  p = (void *)((int)p + size);
+	}
+      *(void **)p = next;
+      next = block[i];
+      //printf("done\n");//debug
+    }
+
+};
+