diff options
| -rw-r--r-- | share/man/man3/Makefile | 1 | ||||
| -rw-r--r-- | share/man/man3/tree.3 | 7 | ||||
| -rw-r--r-- | sys/sys/tree.h | 31 |
3 files changed, 38 insertions, 1 deletions
diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile index 878cd20..923c762 100644 --- a/share/man/man3/Makefile +++ b/share/man/man3/Makefile @@ -108,6 +108,7 @@ MLINKS+= timeradd.3 timerclear.3 \ MLINKS+= tree.3 RB_EMPTY.3 \ tree.3 RB_ENTRY.3 \ tree.3 RB_FIND.3 \ + tree.3 RB_NFIND.3 \ tree.3 RB_FOREACH.3 \ tree.3 RB_GENERATE.3 \ tree.3 RB_HEAD.3 \ diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index c01aa8a..77ab368 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -62,6 +62,7 @@ .Nm RB_MIN , .Nm RB_MAX , .Nm RB_FIND , +.Nm RB_NFIND , .Nm RB_LEFT , .Nm RB_RIGHT , .Nm RB_PARENT , @@ -118,6 +119,8 @@ .Ft "struct TYPE *" .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" +.Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" .Ft "struct TYPE *" .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" @@ -405,7 +408,9 @@ from the tree pointed by .Pp The .Fn RB_FIND -macro can be used to find a particular element in the tree. +and +.Fn RB_NFIND +macros can be used to find a particular element in the tree. .Bd -literal -offset indent struct TYPE find, *res; find.key = 30; diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 6682ec7..47fd098 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -382,6 +382,7 @@ void name##_RB_REMOVE_COLOR(struct name *, struct type *, 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_NFIND(struct name *, struct type *); \ struct type *name##_RB_NEXT(struct type *); \ struct type *name##_RB_MINMAX(struct name *, int); \ \ @@ -628,6 +629,35 @@ name##_RB_FIND(struct name *head, struct type *elm) \ return (NULL); \ } \ \ +/* Finds the first node greater than or equal to the search key */ \ +struct type * \ +name##_RB_NFIND(struct name *head, struct type *elm) \ +{ \ + struct type *ret = RB_ROOT(head); \ + struct type *tmp; \ + int comp; \ + while (ret && (comp = cmp(elm, ret)) != 0) { \ + if (comp < 0) { \ + if ((tmp = RB_LEFT(ret, field)) == NULL) \ + break; \ + ret = tmp; \ + } else { \ + if ((tmp = RB_RIGHT(ret, field)) == NULL) { \ + tmp = ret; \ + ret = RB_PARENT(ret, field); \ + while (ret && tmp == RB_RIGHT(ret, \ + field)) { \ + tmp = ret; \ + ret = RB_PARENT(ret, field); \ + } \ + break; \ + } \ + ret = tmp; \ + } \ + } \ + return (ret); \ +} \ + \ /* ARGSUSED */ \ struct type * \ name##_RB_NEXT(struct type *elm) \ @@ -671,6 +701,7 @@ name##_RB_MINMAX(struct name *head, int val) \ #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) #define RB_FIND(name, x, y) name##_RB_FIND(x, y) +#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) #define RB_NEXT(name, x, y) name##_RB_NEXT(y) #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) |
