Ternary Search Trees

[bearophile]

To shorten the code further I have replaced the Block struct with a typedefined fixed-size array:

struct TST(T) {
    // *** TST instance attributes here ***

    const int BLOCKSIZE = ((1 << 16) / TST.sizeof) > 1 ? ((1 << 16) / TST.sizeof) : 1;

    // usedLastBlock keeps the number of nodes used from the last block of blocks
    // there's no need to keep the whole number of blocks, because its usage is
    // slower and all the blocks but the last one are full anyway.
    static int usedLastBlock;

    typedef TST[BLOCKSIZE] Block;
    static Block*[] blocks;

    static TST* newNode() {
        if (!TST.blocks.length || TST.usedLastBlock >= Block.length) {
            // add new block
            TST.blocks.length = blocks.length + 1;
            // this whole new block gets scanned by the GC even if you need only 1 node
            TST.blocks[$-1] = new Block; // this doesn't work, you can't new a static array
            TST.usedLastBlock = 0;
        }

        return &(*(TST.blocks[$-1])[TST.usedLastBlock++]);
    }

    /// deallocate blocks of nodes
    static void free() {
        foreach (block_ptr; TST.blocks)
            delete block_ptr;
        TST.blocks.length = 0;
    }


But beside the same bug as before:
struct test.TST!(char).TST no size yet for forward reference
it's even more buggy, because now you can't even new a Block. Oh, well.

Bye,
bearophile