Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)

[dholland%NetBSD.org@localhost]

Synopsis: RB_REMOVE trashes link to tree, when requested to remove object that 
isn't in tree

State-Changed-From-To: feedback->closed
State-Changed-By: dholland%NetBSD.org@localhost
State-Changed-When: Sat, 14 Feb 2009 22:53:11 +0000
State-Changed-Why:
I think that since the remove operation takes an object (as opposed to
e.g. a key to look up to find an object) it makes sense for it to 
require that the object be actually in the tree it's to be removed from.
The analogous remove operation in any linked list library, if it needs
the list head at all, will require that the node to be removed be on the
list whose head is provided, and not some other list or no list.

However, because there's also a perfectly valid model where a tree is a
lookup table and it makes sense to ask the tree to remove any object(s)
matching some lookup key, and it's not entirely obvious at first glance
that this model doesn't apply to RB_REMOVE, I've documented the requirement
prominently.

It doesn't appear all that practical or particularly desirable to check
if the object and tree passed in match up; also, if the object isn't on
*any* tree the link pointers might equally likely be uninitialized, and
then you get nasal demons in any event.

Hopefully this will satisfy everyone... patches to improve the docs
further are of course always welcome.