* Szabolcs Nagy <nsz@port70.net> [2011-06-25 20:31:06 +0200]:
> tsearch:
>     i provided two different implementations: plain binary
>     tree (as used in bsd) and a self balancing avl tree
>     (glibc seems to use rb-tree)
> 
>     the avl tree implementation uses recursive functions
>     (max depth of an avl tree with 2^42 nodes is 60)

i was not sure about the performance of this
so i did some benchmarks now
it turns out my avl tree is a little bit faster at word
counting than glibc rb-tree

i had to change scanf("%s", buf) to custom getword(buf)
as musl scanf is slower than glibc's and it took
comparable amount of time to the actual tree operations

on a large text file (gcc info page ~ 30K different words)
musl vs glibc tsearch (best run out of several tries)

$ time ./words <gcc.info 
30617

real	0m0.261s
user	0m0.240s
sys	0m0.020s


$ time ./words-gnu <gcc.info 
30617

real	0m0.291s
user	0m0.284s
sys	0m0.008s


by comparision hsearch version gives

$ time ./words <gcc.info 
30617

real	0m0.116s
user	0m0.100s
sys	0m0.016s

(i could not test the glibc version of
hsearch as it segfaults after a while
even when allocate memory for every string
so i think it's a glibc bug)