svn commit: r189204 - head/sys/sys

[Bruce M Simpson]

Author: bms
Date: Sun Mar  1 04:57:23 2009
New Revision: 189204
URL: http://svn.freebsd.org/changeset/base/189204

Log:
  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.

Modified:
  head/sys/sys/tree.h

Modified: head/sys/sys/tree.h
==============================================================================
--- head/sys/sys/tree.h	Sun Mar  1 04:49:42 2009	(r189203)
+++ head/sys/sys/tree.h	Sun Mar  1 04:57:23 2009	(r189204)
@@ -737,9 +737,14 @@ name##_RB_MINMAX(struct name *head, int 
 	     (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 
 	     (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_ */