updated tree code

svn:r67

1 files changed, 57 insertions, 48 deletions

diff --git a/compat/sys/tree.h b/compat/sys/tree.h
index 2cef70b4..927ca04c 100644
--- a/compat/sys/tree.h
+++ b/compat/sys/tree.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: tree.h,v 1.4 2002/03/26 02:47:28 hugh Exp $	*/
+/*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * All rights reserved.
@@ -114,8 +114,47 @@ struct {								\
 #define SPLAY_PROTOTYPE(name, type, field, cmp)				\
 void name##_SPLAY(struct name *, struct type *);			\
 void name##_SPLAY_MINMAX(struct name *, int);				\
+struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
 									\
-static __inline void							\
+/* Finds the node with the same key as elm */				\
+static __inline struct type *						\
+name##_SPLAY_FIND(struct name *head, struct type *elm)			\
+{									\
+	if (SPLAY_EMPTY(head))						\
+		return(NULL);						\
+	name##_SPLAY(head, elm);					\
+	if ((cmp)(elm, (head)->sph_root) == 0)				\
+		return (head->sph_root);				\
+	return (NULL);							\
+}									\
+									\
+static __inline struct type *						\
+name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
+{									\
+	name##_SPLAY(head, elm);					\
+	if (SPLAY_RIGHT(elm, field) != NULL) {				\
+		elm = SPLAY_RIGHT(elm, field);				\
+		while (SPLAY_LEFT(elm, field) != NULL) {		\
+			elm = SPLAY_LEFT(elm, field);			\
+		}							\
+	} else								\
+		elm = NULL;						\
+	return (elm);							\
+}									\
+									\
+static __inline struct type *						\
+name##_SPLAY_MIN_MAX(struct name *head, int val)			\
+{									\
+	name##_SPLAY_MINMAX(head, val);					\
+        return (SPLAY_ROOT(head));					\
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp)				\
+struct type *								\
 name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
 {									\
     if (SPLAY_EMPTY(head)) {						\
@@ -133,17 +172,18 @@ name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
 	    } else							\
-		    return;						\
+		    return ((head)->sph_root);				\
     }									\
     (head)->sph_root = (elm);						\
+    return (NULL);							\
 }									\
 									\
-static __inline void							\
+struct type *								\
 name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
 {									\
 	struct type *__tmp;						\
 	if (SPLAY_EMPTY(head))						\
-		return;							\
+		return (NULL);						\
 	name##_SPLAY(head, elm);					\
 	if ((cmp)(elm, (head)->sph_root) == 0) {			\
 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
@@ -154,47 +194,13 @@ name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
 			name##_SPLAY(head, elm);			\
 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
 		}							\
+		return (elm);						\
 	}								\
-}									\
-									\
-/* Finds the node with the same key as elm */				\
-static __inline struct type *						\
-name##_SPLAY_FIND(struct name *head, struct type *elm)			\
-{									\
-	if (SPLAY_EMPTY(head))						\
-		return(NULL);						\
-	name##_SPLAY(head, elm);					\
-	if ((cmp)(elm, (head)->sph_root) == 0)				\
-		return (head->sph_root);				\
 	return (NULL);							\
 }									\
 									\
-static __inline struct type *						\
-name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
-{									\
-	name##_SPLAY(head, elm);					\
-	if (SPLAY_RIGHT(elm, field) != NULL) {				\
-		elm = SPLAY_RIGHT(elm, field);				\
-		while (SPLAY_LEFT(elm, field) != NULL) {		\
-			elm = SPLAY_LEFT(elm, field);			\
-		}							\
-	} else								\
-		elm = NULL;						\
-	return (elm);							\
-}									\
-									\
-static __inline struct type *						\
-name##_SPLAY_MIN_MAX(struct name *head, int val)			\
-{									\
-	name##_SPLAY_MINMAX(head, val);					\
-        return (SPLAY_ROOT(head));					\
-}
-
-/* Main splay operation.
- * Moves node close to the key of elm to top
- */
-#define SPLAY_GENERATE(name, type, field, cmp)				\
-void name##_SPLAY(struct name *head, struct type *elm)			\
+void									\
+name##_SPLAY(struct name *head, struct type *elm)			\
 {									\
 	struct type __node, *__left, *__right, *__tmp;			\
 	int __comp;							\
@@ -337,12 +343,13 @@ struct {								\
 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
 		else							\
 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
-		RB_AUGMENT(RB_PARENT(elm, field));			\
 	} else								\
 		(head)->rbh_root = (tmp);				\
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_PARENT(elm, field) = (tmp);					\
 	RB_AUGMENT(tmp);						\
+	if ((RB_PARENT(tmp, field)))					\
+		RB_AUGMENT(RB_PARENT(tmp, field));			\
 } while (0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
@@ -356,19 +363,20 @@ struct {								\
 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
 		else							\
 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
-		RB_AUGMENT(RB_PARENT(elm, field));			\
 	} else								\
 		(head)->rbh_root = (tmp);				\
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_PARENT(elm, field) = (tmp);					\
 	RB_AUGMENT(tmp);						\
+	if ((RB_PARENT(tmp, field)))					\
+		RB_AUGMENT(RB_PARENT(tmp, field));			\
 } while (0)
 
 /* Generates prototypes and inline functions */
 #define RB_PROTOTYPE(name, type, field, cmp)				\
 void name##_RB_INSERT_COLOR(struct name *, struct type *);	\
 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
-void name##_RB_REMOVE(struct name *, struct type *);			\
+struct type *name##_RB_REMOVE(struct name *, struct type *);		\
 struct type *name##_RB_INSERT(struct name *, struct type *);		\
 struct type *name##_RB_FIND(struct name *, struct type *);		\
 struct type *name##_RB_NEXT(struct name *, struct type *);		\
@@ -499,17 +507,17 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
 		RB_COLOR(elm, field) = RB_BLACK;			\
 }									\
 									\
-void									\
+struct type *								\
 name##_RB_REMOVE(struct name *head, struct type *elm)			\
 {									\
-	struct type *child, *parent;					\
+	struct type *child, *parent, *old = elm;			\
 	int color;							\
 	if (RB_LEFT(elm, field) == NULL)				\
 		child = RB_RIGHT(elm, field);				\
 	else if (RB_RIGHT(elm, field) == NULL)				\
 		child = RB_LEFT(elm, field);				\
 	else {								\
-		struct type *old = elm, *left;				\
+		struct type *left;					\
 		elm = RB_RIGHT(elm, field);				\
 		while ((left = RB_LEFT(elm, field)))			\
 			elm = left;					\
@@ -563,6 +571,7 @@ name##_RB_REMOVE(struct name *head, struct type *elm)			\
 color:									\
 	if (color == RB_BLACK)						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
+	return (old);							\
 }									\
 									\
 /* Inserts a node into the RB tree */					\