[PATCH 06/13] rbtree: break out of rb_insert_color loop after tree rotation

2012-07-09 Thread Michel Lespinasse
It is a well known property of rbtrees that insertion never requires more than two tree rotations. In our implementation, after one loop iteration identified one or two necessary tree rotations, we would iterate and look for more. However at that point the node's parent would always be black,

[PATCH 06/13] rbtree: break out of rb_insert_color loop after tree rotation

2012-07-09 Thread Michel Lespinasse
It is a well known property of rbtrees that insertion never requires more than two tree rotations. In our implementation, after one loop iteration identified one or two necessary tree rotations, we would iterate and look for more. However at that point the node's parent would always be black,