NetBSD-Bugs archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

kern/43333: Patch: Optimized red-black tree algorithm



>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:



Home | Main Index | Thread Index | Old Index