diff options
| author | jasone <jasone@FreeBSD.org> | 2006-01-11 15:48:36 +0000 |
|---|---|---|
| committer | jasone <jasone@FreeBSD.org> | 2006-01-11 15:48:36 +0000 |
| commit | 3c55fbecc573cb9c1d0662104ce9485950b986ae (patch) | |
| tree | 07dde63ea169823889a636e0466b6359dc5e7e66 /sys/sys/tree.h | |
| parent | bb26b447587ea480273607b18f31bf7916e6a462 (diff) | |
| download | FreeBSD-src-3c55fbecc573cb9c1d0662104ce9485950b986ae.zip FreeBSD-src-3c55fbecc573cb9c1d0662104ce9485950b986ae.tar.gz | |
Add the RB_NFIND() macro, which is useful for red-black tree searches
for which there may not be an exact match.
Reviewed by: glebius, julian
Approved by: markm (mentor)
Diffstat (limited to 'sys/sys/tree.h')
| -rw-r--r-- | sys/sys/tree.h | 31 |
1 files changed, 31 insertions, 0 deletions
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) |
