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
for performance. Actually, I'm not sure it's an elegant fix in the first
place.
The second diff also removes an unnecessary variable.
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); \
} \
