Ternary Search Trees

[Robert Fraser]

bearophile wrote:
> 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

Cool, thanks for posting this... Why is the default block size so 
freaking huge (16kb)?