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
