potential rbtree optimizations

[Eric Blake]

Bruno, I noticed this thread on the gcc lists:

http://gcc.gnu.org/ml/gcc-patches/2009-05/msg00419.html

with some interesting ideas for speeding up iteration of an RB tree, either at 
the expense of two additional pointers (fastest speed, good cache usage, but 
large memory penalty), or with the addition of two bits (crammed in the padding 
adjacent to the red-black color indicator) which control whether existing 
pointers are tree relations vs. threaded links (no change in memory, faster 
iteration than current implementation, but slower rebalancing).

Would it be worth adding an additional gl_list RB-tree implementation that uses 
threading, such that it would be easy to for clients to experiment between 
implementations and determine whether they care more about memory and insertion 
speed, vs. better iteration speed?

-- 
Eric Blake