Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys/sys Updates from OpenBSD:
details: https://anonhg.NetBSD.org/src/rev/df950502f0e2
branches: trunk
changeset: 534593:df950502f0e2
user: soren <soren%NetBSD.org@localhost>
date: Tue Jul 30 06:12:13 2002 +0000
description:
Updates from OpenBSD:
date: 2002/06/11 18:59:22; author: provos; state: Exp; lines: +48 -42
SPLAY_{INSERT,REMOVE} have return values now that can be used for error
checking
date: 2002/06/11 22:09:52; author: provos; state: Exp; lines: +6 -5
have rb_remove return the right value, too.
diffstat:
sys/sys/tree.h | 105 ++++++++++++++++++++++++++++++--------------------------
1 files changed, 56 insertions(+), 49 deletions(-)
diffs (155 lines):
diff -r 7abfed9c5e22 -r df950502f0e2 sys/sys/tree.h
--- a/sys/sys/tree.h Tue Jul 30 06:10:46 2002 +0000
+++ b/sys/sys/tree.h Tue Jul 30 06:12:13 2002 +0000
@@ -1,5 +1,5 @@
-/* $NetBSD: tree.h,v 1.2 2002/06/18 16:53:49 thorpej Exp $ */
-/* $OpenBSD: tree.h,v 1.4 2002/03/26 02:47:28 hugh Exp $ */
+/* $NetBSD: tree.h,v 1.3 2002/07/30 06:12:13 soren Exp $ */
+/* $OpenBSD: tree.h,v 1.6 2002/06/11 22:09:52 provos Exp $ */
/*
* Copyright 2002 Niels Provos <provos%citi.umich.edu@localhost>
* All rights reserved.
@@ -115,48 +115,8 @@
#define SPLAY_PROTOTYPE(name, type, field, cmp) \
void name##_SPLAY(struct name *, struct type *); \
void name##_SPLAY_MINMAX(struct name *, int); \
- \
-static __inline void \
-name##_SPLAY_INSERT(struct name *head, struct type *elm) \
-{ \
- if (SPLAY_EMPTY(head)) { \
- SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
- } else { \
- int __comp; \
- name##_SPLAY(head, elm); \
- __comp = (cmp)(elm, (head)->sph_root); \
- if(__comp < 0) { \
- SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
- SPLAY_RIGHT(elm, field) = (head)->sph_root; \
- SPLAY_LEFT((head)->sph_root, field) = NULL; \
- } else if (__comp > 0) { \
- SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
- SPLAY_LEFT(elm, field) = (head)->sph_root; \
- SPLAY_RIGHT((head)->sph_root, field) = NULL; \
- } else \
- return; \
- } \
- (head)->sph_root = (elm); \
-} \
- \
-static __inline void \
-name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
-{ \
- struct type *__tmp; \
- if (SPLAY_EMPTY(head)) \
- return; \
- name##_SPLAY(head, elm); \
- if ((cmp)(elm, (head)->sph_root) == 0) { \
- if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
- (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
- } else { \
- __tmp = SPLAY_RIGHT((head)->sph_root, field); \
- (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
- name##_SPLAY(head, elm); \
- SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
- } \
- } \
-} \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
\
/* Finds the node with the same key as elm */ \
static __inline struct type * \
@@ -195,7 +155,53 @@
* 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) \
+struct type * \
+name##_SPLAY_INSERT(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) { \
+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
+ } else { \
+ int __comp; \
+ name##_SPLAY(head, elm); \
+ __comp = (cmp)(elm, (head)->sph_root); \
+ if(__comp < 0) { \
+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \
+ SPLAY_LEFT((head)->sph_root, field) = NULL; \
+ } else if (__comp > 0) { \
+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT(elm, field) = (head)->sph_root; \
+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \
+ } else \
+ return ((head)->sph_root); \
+ } \
+ (head)->sph_root = (elm); \
+ return (NULL); \
+} \
+ \
+struct type * \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__tmp; \
+ if (SPLAY_EMPTY(head)) \
+ return (NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) { \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+ } else { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+ name##_SPLAY(head, elm); \
+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
+ } \
+ return (elm); \
+ } \
+ return (NULL); \
+} \
+ \
+void \
+name##_SPLAY(struct name *head, struct type *elm) \
{ \
struct type __node, *__left, *__right, *__tmp; \
int __comp; \
@@ -369,7 +375,7 @@
#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 *); \
@@ -500,17 +506,17 @@
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; \
@@ -564,6 +570,7 @@
color: \
if (color == RB_BLACK) \
name##_RB_REMOVE_COLOR(head, parent, child); \
+ return (old); \
} \
\
/* Inserts a node into the RB tree */ \
Home |
Main Index |
Thread Index |
Old Index