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
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
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
On Thu, Jul 12, 2012 at 7:12 AM, Peter Zijlstra pet...@infradead.org 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
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
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
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,
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:
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 linux/rbtree.h
#include linux/export.h
+/*
+ * red-black trees
On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra pet...@infradead.org 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
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
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
12 matches
Mail list logo
