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

[Jeremy Huddleston <jeremyhu%apple.com@localhost>]

The following reply was made to PR lib/43488; it has been noted by GNATS.

From: Jeremy Huddleston <jeremyhu%apple.com@localhost>
To: gnats-bugs%NetBSD.org@localhost
Cc: agc%NetBSD.org@localhost, gnats-admin%netbsd.org@localhost, 
netbsd-bugs%netbsd.org@localhost
Subject: Re: lib/43488 (rb.[hc] API critiques/problems that should be addressed
 before final release)
Date: Tue, 20 Jul 2010 09:11:10 -0700

 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
 
 
 /*
  * 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
 >