Ternary Search Trees

[bearophile]

This is the final version I am added to the dlibs:

/********************************************
To create a memory pool of a native item, like structs. Not thread-safe.
It allows to create new items (it performs block-allocations for speed), and then
free them all at once (and then you can create some more).
*/
struct MemoryPool(T, int MAX_BLOCK_BYTES=1 << 14) {
    static assert(!is(T == class), "MemoryPool is designed for native data, not classes.");
    static assert(MAX_BLOCK_BYTES >= 1,
                  "MemoryPool: MAX_BLOCK_BYTES must be >= 1 bytes.");

    struct Block {
        static assert(MAX_BLOCK_BYTES >= T.sizeof,
                      "MemoryPool: MAX_BLOCK_BYTES must be bigger than a T.");
        static if ((T.sizeof * 5) > MAX_BLOCK_BYTES)
            pragma(msg, "MemoryPool: Block is very small, so probably a MemoryPool isn't useful.");

        T[(MAX_BLOCK_BYTES / T.sizeof)] items;
    }

    static Block*[] blocks;
    static T* nextFree, lastFree; // a single int that keeps the number of items used
                                  // in the last block is enough, but it may lead to a
                                  // bit slower code.

    /// Return pointer to a new item. Allocates memory if necessary.
    static T* newItem() {
        if (nextFree >= lastFree) { // then add new block.
            // this whole new block gets scanned by the GC,
            // even if you need only 1 item
            blocks.length = blocks.length + 1;
            blocks[$-1] = new Block;

            nextFree = blocks[$-1].items.ptr;
            lastFree = nextFree + Block.items.length;
        }

        return nextFree++;
    }

    /// Deallocate all items at once. You can then create new ones.
    static void freeAll() {
        foreach (block_ptr; blocks)
            delete block_ptr;
        blocks[] = null;
        blocks.length = 0;
        nextFree = null;
        lastFree = null;
    }

    // This is like free() but doesn't deallocate memory, just cleans it up so
    //   when you create new items there's no new memory allocation, and it's
    //   faster. But to implement this other static members seem necessary.
    //static void cleanMemory() {
    //}
} // end of MemoryPool!()

unittest { // tests of MemoryPool!()
    struct BinaryTreeNode {
        BinaryTreeNode* left, right;
        int data;

        string toString() {
            string nrepr(BinaryTreeNode* n) { return n is null ? "nil" : str(*n); }
            return "<" ~ str(data) ~ ", " ~ nrepr(left)  ~ ", " ~ nrepr(right)  ~ ">";
        }
    }

    MemoryPool!(BinaryTreeNode) BinaryTreeNodePool;

    auto t = BinaryTreeNodePool.newItem();
    t.data = 100;
    t.left = BinaryTreeNodePool.newItem();
    t.left.data = 7;
    t.right = BinaryTreeNodePool.newItem();
    t.right.data = 150;

    assert(str(*t) == "<100, <7, nil, nil>, <150, nil, nil>>");
} // end tests of MemoryPool!()