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.

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_ */