Ternary Search Trees

[bearophile]

OK, now the code works. Besude the TST struct I have created this helper struct that keeps a pool of tree nodes:

struct StructPool(TyStruct, int MAX_BLOCK_SIZE_BYTES=1 << 14) {
    static assert(MAX_BLOCK_SIZE_BYTES >= 1);

    struct Block {
        // Block is not too much big nor too much small
        const int MAXB = MAX_BLOCK_SIZE_BYTES / TyStruct.sizeof;
        const int SIZE = MAXB >= 1 ? MAXB : 1;
        TyStruct[StructPool.Block.SIZE] structs;
    }

    static TyStruct* next_free_struct_ptr, last_struct_ptr;
    static Block*[] blocks;

    static TyStruct* newStruct() {
        if (StructPool.next_free_struct_ptr >= StructPool.last_struct_ptr) {
            // then add new block

            // this whole new block gets scanned by the GC even if you need only 1 node
            StructPool.blocks.length = StructPool.blocks.length + 1;
            StructPool.blocks[$-1] = new Block;

            StructPool.next_free_struct_ptr = StructPool.blocks[$-1].structs.ptr;
            StructPool.last_struct_ptr = StructPool.next_free_struct_ptr + Block.SIZE;

        }

        return StructPool.next_free_struct_ptr++;
    }

    /// deallocate blocks of structs
    static void free() {
        foreach (block_ptr; StructPool.blocks)
            delete block_ptr;
        StructPool.blocks[] = null;
        StructPool.blocks.length = 0;
        StructPool.next_free_struct_ptr = null;
        StructPool.last_struct_ptr = null;
    }
}

alias StructPool!(TST!(char)) TSTpool;

(I have used to static pointers, one single index to the last filled up struct is also enough.)
That newStruct() is fast, about as class allocations in Java :-)

It's not nice code yet, with that external alias and so on, but it seems to work and it almost halves the total allocation time of a big ternary search tree (but despite the improve cache coherence the positive lookups into such TST are about as fast as in a normally allocated TST, maybe because the D GC packs the nodes closely in memory anyway). So I think in certain situations it can be useful.

Now I'm trying to make the code nicer and less bug-prone, for example turning that StructPool struct into a template mixin that I can use to add such pool capability to other structs too that need to allocate many small structs and to deallocate them all at the same time. But so far I have had the same kinds errors I have shown in the two past posts.

Bye,
bearophile