[Bug 1861] RBTree: redundant code removed

[bugzilla-daemon at rtems.org]

https://www.rtems.org/bugzilla/show_bug.cgi?id=1861

--- Comment #5 from Gedare <giddyup44 at yahoo.com> 2011-07-29 13:04:10 CDT ---
(In reply to comment #3)
> Ok, the first one I would know if the function returned non-void. So you mean I
> can test for it with the RTEMS_DEBUG macro?
> 
rtems_assert(something != NULL);

> The second one I have tested the condition for each node in rbtree (size 1 -
> 100 nodes incrementally inserting nodes) to have only a left child which did
> not occur. It is always on the right if a node is single child.
> 
The first paragraph of http://en.wikipedia.org/wiki/Red-black_tree#Removal
discusses the logic for searching down and then checking if there is a leaf
node or not. I suspect we're just not tripping the case with the simple way we
insert/extract nodes.

> The third one, I also have a test for trees of 1 - 100 nodes searching for
> condition where a dad and child are black and no other child is present. Not
> found. 
> But it is also just incremental insertion of nodes.
The Wikipedia page says this about the third case:
"The complex case is when both M and C are black. (This can only occur when
deleting a black node which has two leaf children, because if the black node M
had a black non-leaf child on one side but just a leaf child on the other side,
then the count of black nodes on both sides would be different, thus the tree
would had been an invalid red–black tree by violation of Property 5.)"

I'm not quite sure how to cause this situation, but nothing I know about the
tree properties prevents it from happening. We just need to figure out how to
cause the case while testing the tree.

I think we just haven't been smart enough with our test cases yet. Let's hold
off removing these cases until we can think about it some more.

Feel free to change the NULL checks into assertions, they should not happen
under normal usage (only when someone tries to use the functions on an
invalid/uninitialized tree).

-- 
Configure bugmail: https://www.rtems.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.