Ternary Search Trees

[Robert Fraser]

Thanks for reading through it!

bearophile wrote:
> Robert Fraser:
>> Attached, if you don't mind NO comments.
> 
> This is your code, I can see you have not used the union trick to reduce the memory used by each node that I suggested you:
> 
> 	private static struct TreeNode
> 	{
> 		TreeNode* left;
> 		TreeNode* right;
> 	    TreeNode* mid;
> 		K split;
> 		K[] key;
> 		V value;
> 	}

How does the union trick work exactly?

> And it seems all nodes contain a value, not just the leaves.

I'm assuming that V.sizeof == (void*).sizeof. There's actually 12 bytes 
that are unused on all but nodes containing values, since the key is 
also cached in there. This could eliminated by keeping track of the 
current stack in the opApply methods, but that slows down iteration.

Non-leaf nodes can also have values. For example, if you have "var" = 5 
and "var2" = 10, "r" will have a value and a mid.

>> the compiler wasn't unrolling the tail call<
> 
> I think still DMD isn't able to unroll tail calls.
> 
> Regarding the memory.d, in my implementation I have used a:
> T[(MAX_BLOCK_BYTES / T.sizeof)] items;
> 
> you have used:
> private void[BLOCK_SIZE] data = void;
> memset(blk.data.ptr, 0, BLOCK_SIZE);
> 
> Not setting that void array (of uint? ubyte?) to void the compiler sets it to zero with a memset, so I don't understand what you have gained.

void[SIZE]; fails with an obscure error message... you need to 
initialize it to void.

> And allocating an array of nodes offers a GC a chance to know what's inside the block of memory, so it's more compatible with better future GCs (it may be better even now).
> It also allows for safer initializations of the struct fields, for example on some CPUs null can be != 0

I agree, but I wanted a generic construct that could also be used for 
allocating class instances.

> Later I'll try to adapt your code to Phobos1.

Thanks!