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

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

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
>