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
