We have been working on a CritBit tree implementation for pike. We would like to get it upstream, however we have made a few changes elsewhere that may need discussion:
precompile.pike templating: we added a simple template support to precompile.pike. It basically replaces a set of identifiers in the template file before precompilation. The syntax is admittedly not very beautiful. Autodoc to support global paths in AUTODOC_SRC_IN: we could not figure out how to make the autodoc generator to extract docs from several .cmod files without the AUTODOC_SRC_IN feature applied on the generated .c-files with absolute paths.
You can check it out using git from http://fortranland.com/git/pike. The branch is called critbit. We have not done any testing on non x86 machines. It would be nice if someone could run the testsuite on some big endian machine. Also, we only compiled on linux machines. There might be problems on other environments because of the gcc intrinsics we are using for prefix searches.
Currently there are trees supporting float, integers and pike strings and two derived types for ipv4 ip addresses and date objects. The lookup, insert and delete operations are comparable in speed to pike mappings (1.X slower in our tests). In worst case scenario critbit trees can be slow in insert and lookup (e.g. keys like "a"*i).
However, critbit trees should be more memory efficient in many cases because of the mapping overhead. Also, they support several operations that mappings don't offer, namely, iteration in lexicographical order, range lookup and finding biggest/smallest index, etc.
We have written quite extensive tests and a complete documentation, which you can find at http://fortranland.com/refdoc/modref/ex/predef_3A_3A/ADT/CritBit.html
Any hints, suggestions, bugreports and comments are welcome.
arne and tobias