Is libiberty's splay-tree.c really a splay tree?

[Richard Sandiford]

Michael Matz <matz@suse.de> writes:
>> > There were other people pointing out issues with the splay tree (but 
>> > all w/o copyright assignment and much larger patches).
>> > 
>> > I know I did the last re-write of this piece of code but it's been a 
>> > long time ... in any case, previous reports were that the current 
>> > implementation degenerates in some cases.
>> 
>> And I also distinctly remember some actual measurements where our 
>> current non-splay-tree is faster for a bootstrap (or similar testcases) 
>> than a real splay tree.  Couple years ago, on this list.
>
> Referenced from:
>   http://gcc.gnu.org/ml/gcc/2006-10/msg00616.html

Thanks.  I knew I must be missing something.  I can't explain why
I didn't notice that when searching...

> Basically the reimplementation of richi (r106584) improved on the 
> benchmarks (the former implementation was fairly bogus).  The one from 
> Brian Makin with some changes by Ian Barnes was only slightly better (and 
> without copyright assignment).
>
> So it's very well possible that Richi doesn't rotate in optimal order.  I 
> think it's harmless for the average O(log n) invariants of a splay tree.  
> Try some benchmarks :)

Nah.  Now I know the reason, I'm happy. :-)

FWIW, the reason I asked was because I'm using a splay tree in a patch
that I hope to send soon.  The libiberty structures are a bit heavyweight,
with the hooks stored alongside the root pointer, and with each node
being a separate structure from the key and value.  Since all I needed
was a find-or-insert operation, I thought it would be OK to have a
splay function in the pass itself.  The justification was going to
be that splaying is a fairly short textbook algorithm.  Then I realised
that we don't actually implement the libiberty one in what I thought
was the textbook way.

I'll have another look at whether I can reuse the libiberty code
without bloating things too much.  If not, I might just copy the
algorithm we use there.

Richard