diff options
author | bms <bms@FreeBSD.org> | 2009-03-01 04:57:23 +0000 |
---|---|---|
committer | bms <bms@FreeBSD.org> | 2009-03-01 04:57:23 +0000 |
commit | 7dc8e87695c3612caae13c4d6250c405e7540c5c (patch) | |
tree | 4b20a2bc43d37431b5bee2bcca92052ea8859202 | |
parent | ac5e32881783d2a790978c8d3e987b0da27f0f2a (diff) | |
download | FreeBSD-src-7dc8e87695c3612caae13c4d6250c405e7540c5c.zip FreeBSD-src-7dc8e87695c3612caae13c4d6250c405e7540c5c.tar.gz |
In sys/tree.h:
* Add RB_FOREACH_FROM() which continues traversal *at*
the y-node provided. There is no pre-increment.
* Nuke RB_FOREACH_SAFE as it was buggy; it would omit the final node.
* Replace RB_FOREACH_SAFE() with a working implementation
derived from RB_FOREACH_FROM().
The key observation is that we now only check the loop-control
variable, but still cache the next member pointer.
* Add RB_FOREACH_REVERSE_FROM() which continues backwards
traversal *at* the y-node provided. There is no pre-increment.
Typically this is used to back out of allocations made
whilst walking an RB-tree.
* Add RB_FOREACH_REVERSE_SAFE() which performs insertion and
deletion safe backwards traversal.
-rw-r--r-- | sys/sys/tree.h | 17 |
1 files changed, 16 insertions, 1 deletions
diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 44c0c99..1cce727 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -737,9 +737,14 @@ name##_RB_MINMAX(struct name *head, int val) \ (x) != NULL; \ (x) = name##_RB_NEXT(x)) +#define RB_FOREACH_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ + (x) = (y)) + #define RB_FOREACH_SAFE(x, name, head, y) \ for ((x) = RB_MIN(name, head); \ - (x) != NULL && ((y) = name##_RB_NEXT(x)); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ (x) = (y)) #define RB_FOREACH_REVERSE(x, name, head) \ @@ -747,4 +752,14 @@ name##_RB_MINMAX(struct name *head, int val) \ (x) != NULL; \ (x) = name##_RB_PREV(x)) +#define RB_FOREACH_REVERSE_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = RB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ + (x) = (y)) + #endif /* _SYS_TREE_H_ */ |