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&#324;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:

NetBSD Home
NetBSD PR Database Search

(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.