HAT-trie in ANSI C implementation?

Question

I am looking for ANSI C HAT-trie implementation released under some free license. I have not found one. Can you point me to some standalone implementation or a program that uses HAT-tries to get at least slight idea how to implement it the roght way, please?

The original paper on HAT-trie can be found here: http://crpit.com/confpapers/CRPITV62Askitis.pdf

PS: In case faster cache-conscious data structured well-suited for strings evolved since the time the above paper was written, please point me to the papers or example source codes rather.

Answer 1

Someone is implementing it in C++ over on github

https://github.com/chris-vaszauskas/hat-trie

If you need a plain C implementation, this would be a good base to start from.

Java is also fairly readable for a C programmer

http://www.stochasticgeometry.ie/2008/05/06/implementing-hat-tries-in-java/

Answer 2

Please see the HAT-trie implementation site at code.google.com/p/hat-trie for implementation notes and source code.