Re: [PATCH] Add ternary search trees to libiberty

[Daniel Berlin <dan at cgsoftware dot com>]

Mark Mitchell <mark@codesourcery.com> writes:

> I am all for putting a collection of useful algorithms in libiberty --
> even if we don't know what they're good for exactly at the moment.
> 
> It's a shame that so much GNU software contains implementations of the
> same basic data structures and algorithms.  If we can write something
> in a clean enough way that other people *might* use it, that's good
> enough for me.

Yup.
Just looking around the various subdirs, i've already found a few
places where TST's are a better choice:
To pick an example out of a hat:


libobjc/class.c

It uses a hash table (not libiberty's mind you, the one in hash.c),
hashing on the class name.

When adding classes to the hash (every class goes in the hash, AFAICT), it checks if they exist.
Misses will occur for every class at least once.
When looking up classes, we hit the same problem, because misses occur
all the time when you use things like proxy classes (since a miss
makes it call a hook).


On lookups in this hash, the number of string compares we do is
dependent on the length of the chains.

On lookups in a TST, you do the equivalent of one strcmp, at most, on
any single lookup.

libobjc/selector.c
Same deal with the hash used for selector names.


I spent about 30 seconds looking, and i found quite a few more places
to use them that make sense just in binutils, gcc, and gdb.


-- 
I bought a self-learning record to learn Spanish.  I turned it
on and went to sleep; the record got stuck.  The next day I
could only stutter in Spanish.