Re: [PATCH] Add ternary search trees to libiberty

[Daniel Berlin <dan at cgsoftware dot com>]

DJ Delorie <dj@redhat.com> writes:

> Would it be useful for anything besides gdb?  I'm wondering if it
> should just go in gdb for now, and if we discover some other use
> later, move it to libiberty then.

Yes, it's useful for anywhere we use hash tables with string keys,
where any of the following happen:
1. Misses occur fairly frequently
2. You have long strings
3. Insert and delete happen less than searches (usual case for hash
tables, of course, but ....)
4. You have unicode strings
5. You want to be able to traverse stuff you would normally store in a hash
table, in sorted order.
6. You want to do partial matching or near-neighbor searching
7. Hash table resizing is expensive

In short, there's a lot of places we could use it besides GDB.
And besides hashtables, anywhere you would use a binary search tree,
or digital search tries, there are substantial advantages to using
TST's.

We have expandable hash tables in libiberty, why not TST's?
They are, for most things, faster and more useful.

I'm in the middle of testing replacing the stringpool hashtable with it.

-- 
There's a pizza place near where I live that sells only slices.
in the back you can see a guy tossing a triangle in the air.