Ternary Search Trees

[bearophile]

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;
	}

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

>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.

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

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

Bye,
bearophile