diff options
| author | jasone <jasone@FreeBSD.org> | 2007-12-28 07:03:26 +0000 |
|---|---|---|
| committer | jasone <jasone@FreeBSD.org> | 2007-12-28 07:03:26 +0000 |
| commit | 6a9a3f192972770da07da18a96d36dad51f89834 (patch) | |
| tree | 2b05f280a76f20e8edc06ce608bcd6b2f7630d2e | |
| parent | c9054ae803ccb0b5c30333ca4d58280dffdaf79c (diff) | |
| download | FreeBSD-src-6a9a3f192972770da07da18a96d36dad51f89834.zip FreeBSD-src-6a9a3f192972770da07da18a96d36dad51f89834.tar.gz | |
Implement RB_PREV() AND RB_FOREACH_REVERSE().
| -rw-r--r-- | share/man/man3/tree.3 | 12 | ||||
| -rw-r--r-- | sys/sys/tree.h | 29 |
2 files changed, 39 insertions, 2 deletions
diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index 78ba4b0..aa53eb1 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -30,7 +30,7 @@ .\" .\" $FreeBSD$ .\" -.Dd January 17, 2006 +.Dd December 27, 2007 .Dt TREE 3 .Os .Sh NAME @@ -61,6 +61,7 @@ .Nm RB_ROOT , .Nm RB_EMPTY , .Nm RB_NEXT , +.Nm RB_PREV , .Nm RB_MIN , .Nm RB_MAX , .Nm RB_FIND , @@ -69,6 +70,7 @@ .Nm RB_RIGHT , .Nm RB_PARENT , .Nm RB_FOREACH , +.Nm RB_FOREACH_REVERSE , .Nm RB_INIT , .Nm RB_INSERT , .Nm RB_REMOVE @@ -117,6 +119,8 @@ .Ft "struct TYPE *" .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" +.Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" .Fn RB_MIN NAME "RB_HEAD *head" .Ft "struct TYPE *" .Fn RB_MAX NAME "RB_HEAD *head" @@ -131,6 +135,7 @@ .Ft "struct TYPE *" .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head" +.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head" .Ft void .Fn RB_INIT "RB_HEAD *head" .Ft "struct TYPE *" @@ -433,14 +438,17 @@ The .Fn RB_ROOT , .Fn RB_MIN , .Fn RB_MAX , +.Fn RB_NEXT , and -.Fn RB_NEXT +.Fn RB_PREV macros can be used to traverse the tree: .Pp .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))" .Pp Or, for simplicity, one can use the .Fn RB_FOREACH +or +.Fn RB_FOREACH_REVERSE macro: .Bd -ragged -offset indent .Fn RB_FOREACH np NAME head diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 3af9a2b..54ea6da 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -390,6 +390,7 @@ attr struct type *name##_RB_INSERT(struct name *, struct type *); \ attr struct type *name##_RB_FIND(struct name *, struct type *); \ attr struct type *name##_RB_NFIND(struct name *, struct type *); \ attr struct type *name##_RB_NEXT(struct type *); \ +attr struct type *name##_RB_PREV(struct type *); \ attr struct type *name##_RB_MINMAX(struct name *, int); \ \ @@ -682,6 +683,28 @@ name##_RB_NEXT(struct type *elm) \ return (elm); \ } \ \ +/* ARGSUSED */ \ +attr struct type * \ +name##_RB_PREV(struct type *elm) \ +{ \ + if (RB_LEFT(elm, field)) { \ + elm = RB_LEFT(elm, field); \ + while (RB_RIGHT(elm, field)) \ + elm = RB_RIGHT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ +} \ + \ attr struct type * \ name##_RB_MINMAX(struct name *head, int val) \ { \ @@ -705,6 +728,7 @@ name##_RB_MINMAX(struct name *head, int val) \ #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_PREV(name, x, y) name##_RB_PREV(y) #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) @@ -713,4 +737,9 @@ name##_RB_MINMAX(struct name *head, int val) \ (x) != NULL; \ (x) = name##_RB_NEXT(x)) +#define RB_FOREACH_REVERSE(x, name, head) \ + for ((x) = RB_MAX(name, head); \ + (x) != NULL; \ + (x) = name##_RB_PREV(x)) + #endif /* _SYS_TREE_H_ */ |
