lib/43488: rb.[hc] API critiques/problems that should be addressed before final release

[jeremyhu%apple.com@localhost]

>Number:         43488
>Category:       lib
>Synopsis:       rb.[hc] API critiques/problems that should be addressed before 
>final release
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    lib-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Jun 17 15:40:00 +0000 2010
>Originator:     Jeremy Huddleston
>Release:        unreleased
>Organization:
Apple
>Environment:
N/A
>Description:
I emailed Matt, but I haven't had a response, so I decided to file a report for 
greater exposure:

Hi Matt,

We're interested in including your red black tree API in a future release of 
OSX, but I had some concerns that I wanted to share with you.  Since the API 
hasn't reached an official NetBSD release, hopefully there is time to adjust it 
such that we can have more similar (or exactly the same) API.

1) The comparators are inverted from what is expected.

Three different people have now reported this to me.  Some used the API for 
months before noticing that things were sorted backwards.  Others indicated 
that the enumerators were incorrect... it all boils down to the comparators.  
Your API does things inverted from what is expected for comparators.  strcmp is 
a great example of this.  To work with your API sorting strings, the users 
would need to negate the value returned by strcmp.

2) Lack of context

The comparators do not take a "void * context" which make using this API in 
higher levels difficult.  We want to make the following change:

typedef signed int (*rbto_compare_nodes_fn)(const struct rb_node *,
   const struct rb_node *, const void *);
typedef signed int (*rbto_compare_key_fn)(const struct rb_node *,
   const void *, const void *);

struct rb_tree_ops {
     rbto_compare_nodes_fn rbto_compare_nodes;
     rbto_compare_key_fn rbto_compare_key;
     void *context;
};


3) Someone else noted that the API inserts a node if and only if it is not 
already in the tree.  It would be beneficial to have an API to insert a node if 
it is not already in the tree and otherwise return the equivalent node so it 
can be updated.  This is needed to efficiently implement higher level objects 
using red-black trees.


---

Can you please comment on the above concerns.  We'd very much like to avoid 
diverging from the NetBSD API, so we're hoping that you would welcome the 
changes above back into NetBSD.  I can of course provide patches for the above, 
but I'm not sure about its every use in NetBSD.

>How-To-Repeat:

>Fix:
Not yet available.  I can create patches if desired.  I need feedback first on 
these issues.