Splay Tree

[Ian Blanes]

Could this patch be applied now?
http://gcc.gnu.org/ml/gcc/2006-07/msg00210.html

Discussion starts here:
http://gcc.gnu.org/ml/gcc/2006-07/msg00147.html (benchmarks are wrong)

Original patch posted by Brian Makin here:
http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00762.html

Quote:

I've been recently looking at the splay tree implementation. I've noticed 
that this revision http://gcc.gnu.org/viewcvs?view=rev&revision=106584
does a strange splaying. It does a bottom up splaying but starting at the 
root (not the same that top down). It works but performs worst. One 
example of this is that while in the implementation described in 
http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf the root node 
ends at most two levels down, in the current implementation it can end at 
an arbiratry depth (example attached). So the property of keeping recently 
used nodes up doesn't work.

ian