>Number: 43333
>Category: kern
>Synopsis: Patch: Optimized red-black tree algorithm
>Confidential: no
>Severity: non-critical
>Priority: low
>Responsible: kern-bug-people
>State: open
>Class: change-request
>Submitter-Id: net
>Arrival-Date: Fri May 21 09:00:00 +0000 2010
>Originator: Adam Ciarciński
>Release: netbsd-5, netbsd-current
>Organization:
>Environment:
NetBSD virtual 5.99.29 NetBSD 5.99.29 (VIRTUAL) #4: Sun May 16 10:05:22 CEST
2010 root@virtual:/dist/src/obj.amd64/sys/arch/amd64/compile/VIRTUAL amd64
>Description:
This is a patch for sys/sys/tree.h to make red-black tree algorithm
implementation smaller and faster. The full description has been sent to
tech-kern. The patch can be applied on netbsd-5 and netbsd-current.
--- sys/sys/tree.h.orig 2008-03-21 14:07:15.000000000 +0100
+++ sys/sys/tree.h 2010-05-04 20:16:08.000000000 +0200
@@ -324,15 +324,11 @@
RB_COLOR(elm, field) = RB_RED; \
} while (/*CONSTCOND*/ 0)
-#define RB_SET_BLACKRED(black, red, field) do {
\
- RB_COLOR(black, field) = RB_BLACK; \
- RB_COLOR(red, field) = RB_RED; \
-} while (/*CONSTCOND*/ 0)
-
#ifndef RB_AUGMENT
#define RB_AUGMENT(x) (void)(x)
#endif
+/* After rotation, tmp will be the new top element (new elm's parent) */
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
(tmp) = RB_RIGHT(elm, field); \
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
@@ -345,7 +341,7 @@
else \
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
} else \
- (head)->rbh_root = (tmp); \
+ RB_ROOT(head) = (tmp); \
RB_LEFT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
RB_AUGMENT(tmp); \
@@ -365,7 +361,7 @@
else \
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
} else \
- (head)->rbh_root = (tmp); \
+ RB_ROOT(head) = (tmp); \
RB_RIGHT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
RB_AUGMENT(tmp); \
@@ -405,41 +401,40 @@
while ((parent = RB_PARENT(elm, field)) != NULL && \
RB_COLOR(parent, field) == RB_RED) { \
gparent = RB_PARENT(parent, field); \
+ RB_COLOR(gparent, field) = RB_RED; \
if (parent == RB_LEFT(gparent, field)) { \
tmp = RB_RIGHT(gparent, field); \
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
RB_COLOR(tmp, field) = RB_BLACK; \
- RB_SET_BLACKRED(parent, gparent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
elm = gparent; \
continue; \
} \
if (RB_RIGHT(parent, field) == elm) { \
RB_ROTATE_LEFT(head, parent, tmp, field);\
- tmp = parent; \
- parent = elm; \
- elm = tmp; \
+ elm = parent; \
+ parent = tmp; \
} \
- RB_SET_BLACKRED(parent, gparent, field); \
+ RB_COLOR(parent, field) = RB_BLACK; \
RB_ROTATE_RIGHT(head, gparent, tmp, field); \
} else { \
tmp = RB_LEFT(gparent, field); \
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
RB_COLOR(tmp, field) = RB_BLACK; \
- RB_SET_BLACKRED(parent, gparent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
elm = gparent; \
continue; \
} \
if (RB_LEFT(parent, field) == elm) { \
RB_ROTATE_RIGHT(head, parent, tmp, field);\
- tmp = parent; \
- parent = elm; \
- elm = tmp; \
+ elm = parent; \
+ parent = tmp; \
} \
- RB_SET_BLACKRED(parent, gparent, field); \
+ RB_COLOR(parent, field) = RB_BLACK; \
RB_ROTATE_LEFT(head, gparent, tmp, field); \
} \
} \
- RB_COLOR(head->rbh_root, field) = RB_BLACK; \
+ RB_COLOR(RB_ROOT(head), field) = RB_BLACK; \
} \
\
attr void \
@@ -451,7 +446,8 @@
if (RB_LEFT(parent, field) == elm) { \
tmp = RB_RIGHT(parent, field); \
if (RB_COLOR(tmp, field) == RB_RED) { \
- RB_SET_BLACKRED(tmp, parent, field); \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_COLOR(parent, field) = RB_RED; \
RB_ROTATE_LEFT(head, parent, tmp, field);\
tmp = RB_RIGHT(parent, field); \
} \
@@ -465,18 +461,12 @@
} else { \
if (RB_RIGHT(tmp, field) == NULL || \
RB_COLOR(RB_RIGHT(tmp, field), field) ==
RB_BLACK) {\
- struct type *oleft; \
- if ((oleft = RB_LEFT(tmp, field)) \
- != NULL) \
- RB_COLOR(oleft, field) =
RB_BLACK;\
- RB_COLOR(tmp, field) = RB_RED; \
- RB_ROTATE_RIGHT(head, tmp, oleft,
field);\
- tmp = RB_RIGHT(parent, field); \
+ RB_ROTATE_RIGHT(head, tmp, elm, field);\
+ tmp = elm; \
} \
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
RB_COLOR(parent, field) = RB_BLACK; \
- if (RB_RIGHT(tmp, field)) \
- RB_COLOR(RB_RIGHT(tmp, field), field) =
RB_BLACK;\
+ RB_COLOR(RB_RIGHT(tmp, field), field) =
RB_BLACK;\
RB_ROTATE_LEFT(head, parent, tmp, field);\
elm = RB_ROOT(head); \
break; \
@@ -484,7 +474,8 @@
} else { \
tmp = RB_LEFT(parent, field); \
if (RB_COLOR(tmp, field) == RB_RED) { \
- RB_SET_BLACKRED(tmp, parent, field); \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_COLOR(parent, field) = RB_RED; \
RB_ROTATE_RIGHT(head, parent, tmp, field);\
tmp = RB_LEFT(parent, field); \
} \
@@ -498,18 +489,12 @@
} else { \
if (RB_LEFT(tmp, field) == NULL || \
RB_COLOR(RB_LEFT(tmp, field), field) ==
RB_BLACK) {\
- struct type *oright; \
- if ((oright = RB_RIGHT(tmp, field)) \
- != NULL) \
- RB_COLOR(oright, field) =
RB_BLACK;\
- RB_COLOR(tmp, field) = RB_RED; \
- RB_ROTATE_LEFT(head, tmp, oright,
field);\
- tmp = RB_LEFT(parent, field); \
+ RB_ROTATE_LEFT(head, tmp, elm, field);\
+ tmp = elm; \
} \
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
RB_COLOR(parent, field) = RB_BLACK; \
- if (RB_LEFT(tmp, field)) \
- RB_COLOR(RB_LEFT(tmp, field), field) =
RB_BLACK;\
+ RB_COLOR(RB_LEFT(tmp, field), field) =
RB_BLACK;\
RB_ROTATE_RIGHT(head, parent, tmp, field);\
elm = RB_ROOT(head); \
break; \
>How-To-Repeat:
>Fix: