1 files changed, 117 insertions, 0 deletions
diff --git a/src/trace/pool.h b/src/trace/pool.h
new file mode 100644
index 0000000..742050a
--- /dev/null
+++ b/src/trace/pool.h
@@ -0,0 +1,117 @@
+// 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.
+*/
+#ifndef INKSCAPE_TRACE_POOL_H
+#define INKSCAPE_TRACE_POOL_H
+
+#include <cstdlib>
+#include <exception>
+#include <algorithm>
+
+template <typename T>
+class Pool
+{
+public:
+    Pool()
+    {
+        cblock = 0;
+        size = std::max(sizeof(T), sizeof(void *));
+        next = nullptr;
+        for (auto &k : block) {
+            k = nullptr;
+        }
+    }
+
+    ~Pool()
+    {
+        for (int k = 0; k < cblock; k++) {
+            std::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));
+        block[i] = (void *)std::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];
+    }
+};
+
+#endif // INKSCAPE_TRACE_POOL_H