[Bug 1641] Red Black Tree data structure

[bugzilla-daemon at rtems.org]

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

--- Comment #8 from Gedare <giddyup44 at yahoo.com> 2010-07-30 10:05:03 CDT ---
(In reply to comment #7)
> (In reply to comment #6)
> > (In reply to comment #5)
> > > For the Bdbuf we use AVL-trees.  Why do we need both tree (AVL and red black)
> > > algorithms?  Can we discard one and share code?
> 
> Nice idea.
> 
> > 
> > My understanding of the requirements of code in score is that it should be
> > self-contained. So I re-wrote a balanced binary search tree, and chose
> > red-black because it seems appropriate for tracking ready tasks.
> 
> If it is accessible by a user, which this could be we also need C User manual
> documentation. :)
> 
I'll work on that..

> > I was unaware
> > of any fully self-contained balanced search tree implementations under the
> > RTEMS license.  I would be OK with switching to one or the other, although
> > switching to AVL will delay my gsoc.
> > 
> 
> I do not mind which implementation we use in the file system cache as long as
> it uses the same or less memory and is as fast as the AVL tree when used in the
> cache.
> 
Speed should be comparable, barring implementation flaws.  In terms of space,
the tree has a fixed overhead of 4 pointers for the 'control' node, and then
each node of the tree consists of  3 pointers, an unsigned int, and an enum.
The node is embedded in whatever structure you want on the tree. There is a
'container_of' routine to retrieve the structure.

> The AVL tree code has a stack based limit which we should not hit but does
> exist. Does the red/black tree have the same limitation ?
>
I can't think of a particular limit. Since the nodes are embedded, the space
overhead of each node is part of the structure containing it.

> I suspect we may need a bake-off between them to decide which the cache uses so
> I am happy to wait until the other GSoC work is finished. Is the use of the
> tree abstracted in the score ?
It is not abstracted right now, although the code points that are introduced
aren't too hard to re-write, it would depend on how different the AVL node is
compared to the rbtree node.

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