NetBSD Problem Report #43333
From www@NetBSD.org Fri May 21 08:57:24 2010
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
by www.NetBSD.org (Postfix) with ESMTP id 55AA163B879
for <gnats-bugs@gnats.NetBSD.org>; Fri, 21 May 2010 08:57:24 +0000 (UTC)
Message-Id: <20100521085724.20D6763B873@www.NetBSD.org>
Date: Fri, 21 May 2010 08:57:24 +0000 (UTC)
From: adam@NetBSD.org
Reply-To: adam@NetBSD.org
To: gnats-bugs@NetBSD.org
Subject: Patch: Optimized red-black tree algorithm
X-Send-Pr-Version: www-1.0
>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:
(Contact us)
$NetBSD: query-full-pr,v 1.39 2013/11/01 18:47:49 spz Exp $
$NetBSD: gnats_config.sh,v 1.8 2006/05/07 09:23:38 tsutsui Exp $
Copyright © 1994-2014
The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.