Date: Thu, 22 Dec 2005 15:13:47 -0800 From: Jason Evans <jasone@freebsd.org> To: freebsd-current@freebsd.org Subject: Adding RB_NFIND() to sys/tree.h Message-ID: <36D83F22-D5E0-4525-841D-4A03C64C0A19@freebsd.org>
next in thread | raw e-mail | index | archive | help
I'd like to add RB_NFIND() to sys/tree.h, since I need it for the
malloc implementation I've been working on. Mark Murray suggested
that I ask for comments here before committing. 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)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?36D83F22-D5E0-4525-841D-4A03C64C0A19>