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

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

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, gnats-admin%netbsd.org@localhost, 
netbsd-bugs%netbsd.org@localhost, 
        matt%netbsd.org@localhost
Subject: Re: lib/43488 (rb.[hc] API critiques/problems that should be addressed 
before final release)
Date: Tue, 20 Jul 2010 14:08:48 -0400

 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