[Bug 1641] Red Black Tree data structure

[bugzilla-daemon at rtems.org]

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

Chris Johns <chrisj at rtems.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chrisj at rtems.org

--- Comment #7 from Chris Johns <chrisj at rtems.org> 2010-07-29 20:55:25 CDT ---
(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 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.

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 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 ?

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