Adding RB_NFIND() to sys/tree.h

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Adding RB_NFIND() to sys/tree.h

Jason Evans-2
[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)

_______________________________________________
[hidden email] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: Adding RB_NFIND() to sys/tree.h

Julian Elischer
Jason Evans wrote:

> [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


I see no reason to not add it.


_______________________________________________
[hidden email] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: Adding RB_NFIND() to sys/tree.h

Gleb Smirnoff
In reply to this post by Jason Evans-2
On Wed, Dec 28, 2005 at 06:58:20AM -0800, Jason Evans wrote:
J> [This is a slightly edited copy of email originally sent to -
J> current.  The only response I received was that -arch is a better  
J> list on which to ask for feedback on this issue.]
J>
J> I'd like to add RB_NFIND() to sys/tree.h, since I need it for the  
J> malloc implementation I've been working on.  sys/tree.h comes from  
J> NetBSD, and up to now, the only changes we've made have been for the  
J> purpose of avoiding compiler warnings.
J>
J> RB_NFIND() is like RB_FIND(), but if an exact match isn't found,  
J> RB_NFIND() returns the next object in the tree (if there is one).  
J> Emulating RB_NFIND() with the existing RB_*() API is possible, but  
J> certainly not ideal.
J>
J> I would claim that RB_PFIND() isn't necessary, since it could be  
J> easily (if not quite as efficiently) emulated with RB_NFIND(),  
J> followed by RB_PREV().  However, there is no RB_PREV(), even though  
J> there is RB_NEXT().  This seems to me like an API design oversight  
J> (as is the omission of RB_FOREACH_REVERSE()), but it doesn't cause me  
J> issues, so I haven't tackled it.
J>
J> A patch follows (manpage changes omitted).  Are there any objections  
J> to committing this?

I see it useful, and probably will utilize soon in ipfw(4). Thanks.

--
Totus tuus, Glebius.
GLEBIUS-RIPN GLEB-RIPE
_______________________________________________
[hidden email] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"