diff options
author | Niels Provos <provos@gmail.com> | 2003-04-29 18:29:16 +0000 |
---|---|---|
committer | Niels Provos <provos@gmail.com> | 2003-04-29 18:29:16 +0000 |
commit | bdf5a68b95d61051687507abe29349494c3fcc18 (patch) | |
tree | 3991033e69660f8dfad0e80522b2c33785d69677 /compat/sys | |
parent | 670b94e479791707584b38f8473b51ca4fc11569 (diff) | |
download | libevent-bdf5a68b95d61051687507abe29349494c3fcc18.tar.gz |
updated tree code
svn:r67
Diffstat (limited to 'compat/sys')
-rw-r--r-- | compat/sys/tree.h | 105 |
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 */ \ |