[boost] [intrusive] Looking for some advice on intrusive splay trees

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-10-18 15:07:24

Hi to all,

  Lately I've been trying to implement splay trees for Intrusive. 
Excerpt taken from en.wikipedia.org/wiki/Splay_tree:

"A splay tree is a self-balancing binary search tree with the additional 
unusual property that recently accessed elements are quick to access 
again. It performs basic operations such as insertion, look-up and 
removal in O(log(n)) amortized time. For many non-uniform sequences of 
operations, splay trees perform better than other search trees, even 
when the specific pattern of the sequence is unknown. The splay tree was 
invented by Daniel Sleator and Robert Tarjan."

As most of you know, splay trees splay (rebalance) the tree also on 
searches, so that the target  node is placed as root, yielding to better 
search times for frequently searched nodes (cache effect).

The implementation I've taken as model is taken from the article written 
by Ralf Mattethat for C++ Users Journal (September 2005) titled 
"Implementing Splay Trees in C++" (http://www.ddj.com/architect/184402007).

Following usual STL-like implementations I've used left and right 
pointers of the header to point to the leftmost and rightmost node 
respectively. Several intrusive rbtree implementation tricks and 
optimizations can be easily reused for splay trees so I think we can 
have a useful intrusive splay tree.

My main issue is related to constness and thread-safety. I would like to 
offer a STL-like interface (that is, the interface actually implemented 
for other Intrusive containers like set, multiset and rbtree), but take 
in care that the tree will rebalance in each 
find/lower_bound/upper_bound operation so those operations couldn't be 
const members unless we declare the header as mutable. I plan to add 
optional (runtime) rebalancing for each operation (for example, the user 
could call find() without rebalancing if he doesn't want to alter the 
cache effect, or just needs more predictable search times).

iterator it = splay_tree.find(a);//Splay operation performed
iterator it = splay_tree.find(a, dont_splay);//No splay

Allowing const overloads (casting the constness away internally) with 
splaying (rebalancing):

const_iterator it = const_splay_tree.find(a); //Splaying performed

would break usual de-facto thread-safety guarantees for STL and 
Intrusive containers (read-only access from different threads is 
thread-safe).

So the main question is: what approach do you think would be better? 
¿Just splay in const operations and put a thread-safety warning? ¿Make 
const versions non-splaying? ¿Don't offer const versions of search 
functions?

Regards,

Ion