Implement RB_PREV() AND RB_FOREACH_REVERSE().

1 files changed, 29 insertions, 0 deletions

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