Adding RB_NFIND() to sys/tree.h

[Jason Evans]

[This is a slightly edited copy of email originally sent to - 
current.  The only response I received was that -arch is a better  
list on which to ask for feedback on this issue.]

I'd like to add RB_NFIND() to sys/tree.h, since I need it for the  
malloc implementation I've been working on.  sys/tree.h comes from  
NetBSD, and up to now, the only changes we've made have been for the  
purpose of avoiding compiler warnings.

RB_NFIND() is like RB_FIND(), but if an exact match isn't found,  
RB_NFIND() returns the next object in the tree (if there is one).   
Emulating RB_NFIND() with the existing RB_*() API is possible, but  
certainly not ideal.

I would claim that RB_PFIND() isn't necessary, since it could be  
easily (if not quite as efficiently) emulated with RB_NFIND(),  
followed by RB_PREV().  However, there is no RB_PREV(), even though  
there is RB_NEXT().  This seems to me like an API design oversight  
(as is the omission of RB_FOREACH_REVERSE()), but it doesn't cause me  
issues, so I haven't tackled it.

A patch follows (manpage changes omitted).  Are there any objections  
to committing this?

Thanks,
Jason

Index: sys/sys/tree.h
===================================================================
RCS file: /home/ncvs/src/sys/sys/tree.h,v
retrieving revision 1.3
diff -u -r1.3 tree.h
--- sys/sys/tree.h	10 Jun 2005 11:44:57 -0000	1.3
+++ sys/sys/tree.h	17 Dec 2005 03:00:01 -0000
@@ -382,6 +382,7 @@
struct type *name##_RB_REMOVE(struct name *, struct type *);		\
struct type *name##_RB_INSERT(struct name *, struct type *);		\
struct type *name##_RB_FIND(struct name *, struct type *);		\
+struct type *name##_RB_NFIND(struct name *, struct type *);		\
struct type *name##_RB_NEXT(struct type *);				\
struct type *name##_RB_MINMAX(struct name *, int);			\
									\
@@ -628,6 +629,35 @@
	return (NULL);							\
}									\
									\
+/* Finds the first node greater than or equal to the search key */	\
+struct type *								\
+name##_RB_NFIND(struct name *head, struct type *elm)			\
+{									\
+	struct type *ret = RB_ROOT(head);				\
+	struct type *tmp;						\
+	int comp;							\
+	while (ret && (comp = cmp(elm, ret)) != 0) {			\
+		if (comp < 0) {						\
+			if ((tmp = RB_LEFT(ret, field)) == NULL)	\
+				break;					\
+			ret = tmp;					\
+		} else {						\
+			if ((tmp = RB_RIGHT(ret, field)) == NULL) {	\
+				tmp = ret;				\
+				ret = RB_PARENT(ret, field);		\
+				while (ret && tmp == RB_RIGHT(ret,	\
+				    field)) {				\
+					tmp = ret;			\
+					ret = RB_PARENT(ret, field);	\
+				}					\
+				break;					\
+			}						\
+			ret = tmp;					\
+		}							\
+	}								\
+	return (ret);							\
+}									\
+									\
/* ARGSUSED */								\
struct type *								\
name##_RB_NEXT(struct type *elm)					\
@@ -671,6 +701,7 @@
#define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
#define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
#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_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
#define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)