On Thu, Jul 12, 2012 at 7:12 AM, Peter Zijlstra wrote:
> On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
>>
>> In __rb_erase_color(), some of the cases are more complicated than you drew
>> however, because some node colors aren't known.
>
> Right, the wikipedia article draws them bla
On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
>
> In __rb_erase_color(), some of the cases are more complicated than you drew
> however, because some node colors aren't known.
Right, the wikipedia article draws them blank, I couldn't come up with a
3rd case, although maybe we can a
On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
> Do you mean the case you marked XXX ? it is actually parent that is
> red, which we know because we tested that a few lines earlier.
>
> > @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
> > } else if (rb_i
On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra wrote:
> Looks nice.. How about something like the below on top.. I couldn't
> immediately find a sane reason for the grand-parent to always be red in
> the insertion case.
Do you mean the case you marked XXX ? it is actually parent that is
red, whi
Looks nice.. How about something like the below on top.. I couldn't
immediately find a sane reason for the grand-parent to always be red in
the insertion case.
---
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -23,6 +23,25 @@
#include
#include
+/*
+ * red-black trees properties: http://en.wikip
I recently started looking at the rbtree code (with an eye towards
improving the augmented rbtree support, but I haven't gotten there
yet). I noticed a lot of possible speed improvements, which I am now
proposing in this patch set.
Patches 1-4 are preparatory: remove internal functions from rbtre
6 matches
Mail list logo
