答复: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first

[Li,Rongqing]

> You're right that rb_add() does a tail-add for elements it considers equal -- there
> is actually code in the tree that relies on this.
> 
> But that doesn't mean rb_find_first() should go right, it *must*not*, because
> then it wouldn't find the 'first' aka 'leftmost' instance of the equal elements.
> 
> Also, you're only considering building the tree in-order with rb_add(), trees get
> modified all the time and the pattern Michel gave is perfectly valid (also see
> rb_prev()).
> 
> Sure the snippet is not a balanced tree, but you can construct the pattern as
> part of a larger tree just fine, just add some elements:
> 
> 
> 	 10(b)
> 	/  \
>        5   10(c)
>         \
> 	10(a)
> 
> is a tree that is balanced (remember, RB trees only require the left and right
> depths to no more than double -- as opposed to AVL trees, which have a tighter
> constraint). This tree has order: 5, 10(a), 10(b), 10(c).
> Also note that the tree rotations are stable -- they must be since they do not
> refence the order function.
> 
> As such, if we rb_find_first() for 10, we must find 10(a), the leftmost
> 10 in the tree.

I see, Thanks for the explanation. Sorry for the noise.

-Li