[Bug 1641] Red Black Tree data structure

[bugzilla-daemon at rtems.org]

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

--- Comment #19 from Gedare <giddyup44 at yahoo.com> 2010-12-08 21:06:45 CST ---
(In reply to comment #17)
> (In reply to comment #16)
> > The advantage of adding a generic balanced search tree to the score is that in
> > theory it can be used in multiple locations.  The AVL tree of the bdbuf is
> > embedded in the structure pretty tightly, so that the code and structure cannot
> > be easily re-used.
> 
> If the code can be shared we can lower the bdbuf foot print.
> 
> > In contrast, it should be easy to adapt the bdbuf to use the red-black tree
> > structure, although the cost-benefit should be thoroughly explored.
> 
> Yeap we should take a closer look. If it is close then a full tested tree is
> much better because increases our coverage when including the file system.
> 
I took a look and found two clear problems with using the rbtree in the bdbuf:

1) Comparisons and Ties
  The bdbuf AVL uses p->dev as a primary value for comparison, but then when
there is a tie in the p->dev value it will compare on the p->block value.  The
current rbtree implementation is deficient for this requirement because it
assumes unique keys.  I suppose that providing the "template support" for
search keys can resolve this problem.

2) Un-encapsulated bdbuf Fields
  The bdbuf AVL code relies on portions of the rtems_bdbuf_buffer that are not
embedded in the rtems_bdbuf_avl_node (.avl field).  In particular, the .dev and
.block fields.  This is related to the above, in that these are the fields used
for comparing values.  There might be some union magic that can allow for the
comparison fields and the template to overlap, although I'm not sure how robust
that would be.

These problems are solvable, and I think the code points that use the avl are
separated well enough.  I'd like a clearer picture on how to accomplish the
template support though.

> > Chris suggested that we might support both an integer and a string.  We should
> > capture the set of requirements for the tree's search parameter for whichever
> > core services it might support.  
> 
> Without something like template support we should have a couple of keys that we
> support. I assume for an int key performance is important. For the string key
> performance is not so important.
Is there a use case for the string-based tree in the CVS somewhere?  Given the
requirements of the AVL tree, I think these templates would probably be useful
for at least covering the intended use case (single primitive comparison) and
the bdbuf use case (a primary and a secondary comparison).

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