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

[christos%zoulas.com@localhost (Christos Zoulas)]

On Jul 20,  9:11am, jeremyhu%apple.com@localhost (Jeremy Huddleston) wrote:
-- Subject: Re: lib/43488 (rb.[hc] API critiques/problems that should be addr

| Has any progress been bade on this?  As I mentioned in addition to the bug 
with the comparator return value, it would be beneficial to have a variant that 
allowed setting a context much like qsort_r.  The following is what I suggest 
as the API for this.  Please let me know your thoughts.  I can provide a patch 
if necessary.
| 
| Thanks,
| Jeremy

Sorry about that. Matt is it ok if I go ahead and make the suggested changes?

Thanks,

christos

| /*
|  * rbto_compare_nodes_fn:
|  *    return a negative value if the first node < the second node.
|  *    return a positive value if the first node > the second node.
|  *    return 0 if they are considered same.
|  *
|  * rbto_compare_key_fn:
|  *    return a negative value if the node < the key.
|  *    return a positive value if the node > the key.
|  *    return 0 if they are considered same.
|  *
|  * The _r versions take a context as the first argument.
|  */
| 
| typedef signed int (*rbto_compare_nodes_fn)(const struct rb_node *,
|                                             const struct rb_node *);
| typedef signed int (*rbto_compare_key_fn)(const struct rb_node *,
|                                           const void *);
| 
| typedef signed int (*rbto_compare_nodes_fn_r)(const void *, const struct 
rb_node *,
|                                               const struct rb_node *);
| typedef signed int (*rbto_compare_key_fn_r)(const void *, const struct 
rb_node *,
|                                             const void *);
| 
| struct rb_tree_ops {
|       rbto_compare_nodes_fn rbto_compare_nodes;
|       rbto_compare_key_fn rbto_compare_key;
| };
| 
| struct rb_tree_ops_r {
|       rbto_compare_nodes_fn_r rbto_compare_nodes_r;
|       rbto_compare_key_fn_r rbto_compare_key_r;
|       void *thunk;
| };
| 
| struct rb_tree {
|       struct rb_node *rbt_root;
|       unsigned ops_which;
|       union {
|               struct rb_tree_ops *rbt_ops;
|               struct rb_tree_ops_r *rbt_ops_r;
|       };
|       struct rb_node *rbt_minmax[2];
|       size_t rbt_count;
|       void *unused[4]; // Unused padding for possible future use
| };
| 
| void  rb_tree_init(struct rb_tree *, struct rb_tree_ops *);
| void  rb_tree_init_r(struct rb_tree *, struct rb_tree_ops_r *);
| 
| On Jun 21, 2010, at 15:55, Christos Zoulas wrote:
| 
| > The following reply was made to PR lib/43488; it has been noted by GNATS.
| > 
| > From: christos%zoulas.com@localhost (Christos Zoulas)
| > To: Jeremy Huddleston <jeremyhu%apple.com@localhost>, 
gnats-bugs%NetBSD.org@localhost
| > Cc: agc%NetBSD.org@localhost, lib-bug-people%netbsd.org@localhost, 
netbsd-bugs%netbsd.org@localhost, 
| >     gnats-admin%netbsd.org@localhost
| > Subject: Re: lib/43488 (rb.[hc] API critiques/problems that should be 
addressed before final release)
| > Date: Mon, 21 Jun 2010 18:54:51 -0400
| > 
| > On Jun 21, 11:19am, jeremyhu%apple.com@localhost (Jeremy Huddleston) wrote:
| > -- Subject: Re: lib/43488 (rb.[hc] API critiques/problems that should be 
addr
| > 
| > | Actually, the comparison functions are opposite what qsort does.  
qsort(3) says:
| > | 
| > |      The comparison function must return an integer less than, equal to, 
or
| > |      greater than zero if the first argument is considered to be 
respectively
| > |      less than, equal to, or greater than the second.
| > | 
| > | That is consistent with strcmp(3) and is opposite what rb(3) states.
| > 
| > I agree that this is what strcmp(3), qsort(3), and rb(3) state, and I think
| > it would be beneficial to change rb to behave the same for consistency.
| > 
| > christos
| > 
-- End of excerpt from Jeremy Huddleston