On Tue, May 04, 2010 at 09:25:29PM +0200, Tim van der Molen wrote:
> On Tue, 04 May 2010 00:20:47 +0200, Nicholas Marriott wrote:
> > SPLAY_REMOVE appears to returns the pointer it is given or NULL if the
> > item isn't found. I don't see what errors it could return NULL for, so I
> > think it would be better to say "NULL is returned if no item with that
> > key is found". Or at least if you can spot any errors I can't, "to
> > indicate an error or that the key is not found".
>
> How about "If the element does not exist in the tree, NULL is returned"?
> Below is an updated version of the original diff.
>
> > RB_REMOVE returns the pointer it is given whether or not the item is in
> > the tree (even for an empty tree). This seems unexpected, so it might be
> > a bug...
>
> I think you're right. If I'm not mistaken, RB_REMOVE will have to
> explicitly check whether the element exists in the tree. The second diff
> below uses RB_FIND to do that. I'm not sure what consequences this has
I don't think we should do this, at least not without knowing the
performance change. The return value of *_REMOVE is very rarely used, I
think just documenting it is fine.
I'm going to put in a tweaked version of your original diff soon.
> for performance. Actually, I'm not sure it's an elegant fix in the first
> place.
>
> The second diff also removes an unnecessary variable.
I'll look at this as well.
Thanks!
>
> Index: tree.3
> ===================================================================
> RCS file: /cvs/src/share/man/man3/tree.3,v
> retrieving revision 1.20
> diff -u tree.3
> --- tree.3 28 Jan 2009 12:22:48 -0000 1.20
> +++ tree.3 4 May 2010 19:10:37 -0000
> @@ -257,14 +257,24 @@
> .Fn SPLAY_INSERT
> macro inserts the new element
> .Fa elm
> -into the tree.
> +into the tree pointed to by
> +.Fa head .
> +Upon success,
> +.Va NULL
> +is returned.
> +If a matching element already exists in the tree, the insertion is
> +aborted, and a pointer to the existing element is returned.
> .Pp
> The
> .Fn SPLAY_REMOVE
> macro removes the element
> .Fa elm
> -from the tree pointed by
> +from the tree pointed to by
> .Fa head .
> +Upon success, a pointer to the removed element is returned.
> +If the element does not exist in the tree,
> +.Va NULL
> +is returned.
> .Pp
> The
> .Fn SPLAY_FIND
> @@ -392,7 +402,8 @@
> .Fn RB_INSERT
> macro inserts the new element
> .Fa elm
> -into the tree.
> +into the tree pointed to by
> +.Fa head .
> Upon success,
> .Va NULL
> is returned.
> @@ -403,8 +414,12 @@
> .Fn RB_REMOVE
> macro removes the element
> .Fa elm
> -from the tree pointed by
> +from the tree pointed to by
> .Fa head .
> +Upon success, a pointer to the removed element is returned.
> +If the element does not exist in the tree,
> +.Va NULL
> +is returned.
> .Pp
> The
> .Fn RB_FIND
> @@ -543,22 +558,5 @@
> free(var);
> }
> .Ed
> -.Pp
> -Both
> -.Fn RB_INSERT
> -and
> -.Fn SPLAY_INSERT
> -return
> -.Va NULL
> -if the element was inserted in the tree successfully, otherwise they
> -return a pointer to the element with the colliding key.
> -.Pp
> -Accordingly,
> -.Fn RB_REMOVE
> -and
> -.Fn SPLAY_REMOVE
> -return the pointer to the removed element, otherwise they return
> -.Va NULL
> -to indicate an error.
> .Sh AUTHORS
> The author of the tree macros is Niels Provos.
>
> Index: tree.h
> ===================================================================
> RCS file: /cvs/src/sys/sys/tree.h,v
> retrieving revision 1.12
> diff -p -u tree.h
> --- tree.h 2 Mar 2009 09:42:55 -0000 1.12
> +++ tree.h 4 May 2010 19:20:30 -0000
> @@ -521,7 +521,8 @@ attr struct type *
> \
> name##_RB_REMOVE(struct name *head, struct type *elm)
> \
> { \
> struct type *child, *parent, *old = elm; \
> - int color; \
> + if (name##_RB_FIND(head, elm) == NULL) \
> + return (NULL); \
> if (RB_LEFT(elm, field) == NULL) \
> child = RB_RIGHT(elm, field); \
> else if (RB_RIGHT(elm, field) == NULL) \
> @@ -533,7 +534,6 @@ name##_RB_REMOVE(struct name *head, struct type *elm)
> elm = left; \
> child = RB_RIGHT(elm, field); \
> parent = RB_PARENT(elm, field); \
> - color = RB_COLOR(elm, field); \
> if (child) \
> RB_PARENT(child, field) = parent; \
> if (parent) { \
> @@ -567,7 +567,6 @@ name##_RB_REMOVE(struct name *head, struct type *elm)
> goto color; \
> } \
> parent = RB_PARENT(elm, field); \
> - color = RB_COLOR(elm, field); \
> if (child) \
> RB_PARENT(child, field) = parent; \
> if (parent) { \
> @@ -579,7 +578,7 @@ name##_RB_REMOVE(struct name *head, struct type *elm)
> } else \
> RB_ROOT(head) = child; \
> color:
> \
> - if (color == RB_BLACK) \
> + if (RB_COLOR(elm, field) == RB_BLACK) \
> name##_RB_REMOVE_COLOR(head, parent, child); \
> return (old); \
> } \
