NetBSD Problem Report #43488

From www@NetBSD.org  Thu Jun 17 15:35:40 2010
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
	by www.NetBSD.org (Postfix) with ESMTP id 1EE8463B916
	for <gnats-bugs@gnats.NetBSD.org>; Thu, 17 Jun 2010 15:35:40 +0000 (UTC)
Message-Id: <20100617153539.CB23963B100@www.NetBSD.org>
Date: Thu, 17 Jun 2010 15:35:39 +0000 (UTC)
From: jeremyhu@apple.com
Reply-To: jeremyhu@apple.com
To: gnats-bugs@NetBSD.org
Subject: rb.[hc] API critiques/problems that should be addressed before final release
X-Send-Pr-Version: www-1.0

>Number:         43488
>Category:       lib
>Synopsis:       rb.[hc] API critiques/problems that should be addressed before final release
>Confidential:   no
>Severity:       serious
>Priority:       high
>Responsible:    rmind
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Jun 17 15:40:00 +0000 2010
>Closed-Date:    Sat Sep 25 00:19:14 +0000 2010
>Last-Modified:  Sat Sep 25 00:19:14 +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.

>Release-Note:

>Audit-Trail:

Responsible-Changed-From-To: lib-bug-people->agc
Responsible-Changed-By: agc@NetBSD.org
Responsible-Changed-When: Sat, 19 Jun 2010 23:24:14 +0000
Responsible-Changed-Why:
I thought I'd channel matt@ for this one


State-Changed-From-To: open->analyzed
State-Changed-By: agc@NetBSD.org
State-Changed-When: Sat, 19 Jun 2010 23:24:14 +0000
State-Changed-Why:
matt was saying that the comparator functions are modelled on the qsort ones,
which seems to be the correct approach to this pair of eyes - most people
cast within the comparison routine to the required type of argument, which
adds an air of genericism to the sorting, at the cost of access through void * pointers.

matt is also going to take a further look to check the direction of testing.
I'll update the bug when the oracle speaks further.


From: yamt@mwd.biglobe.ne.jp (YAMAMOTO Takashi)
To: gnats-bugs@NetBSD.org
Cc: lib-bug-people@netbsd.org, gnats-admin@netbsd.org, netbsd-bugs@netbsd.org
Subject: Re: lib/43488: rb.[hc] API critiques/problems that should be
 addressed before final release
Date: Mon, 21 Jun 2010 00:53:54 +0000 (UTC)

 hi,

 > 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.

 i agree.
 making rb_tree_insert_node return the existing node likely has
 no run-time cost.

 YAMAMOTO Takashi

From: Jeremy Huddleston <jeremyhu@apple.com>
To: gnats-bugs@NetBSD.org
Cc: agc@NetBSD.org, lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org,
 gnats-admin@netbsd.org
Subject: Re: lib/43488 (rb.[hc] API critiques/problems that should be addressed
 before final release)
Date: Mon, 21 Jun 2010 11:19:16 -0700

 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.


 On Jun 19, 2010, at 16:24, agc@NetBSD.org wrote:

 > Synopsis: rb.[hc] API critiques/problems that should be addressed before final release
 > 
 > Responsible-Changed-From-To: lib-bug-people->agc
 > Responsible-Changed-By: agc@NetBSD.org
 > Responsible-Changed-When: Sat, 19 Jun 2010 23:24:14 +0000
 > Responsible-Changed-Why:
 > I thought I'd channel matt@ for this one
 > 
 > 
 > State-Changed-From-To: open->analyzed
 > State-Changed-By: agc@NetBSD.org
 > State-Changed-When: Sat, 19 Jun 2010 23:24:14 +0000
 > State-Changed-Why:
 > matt was saying that the comparator functions are modelled on the qsort ones,
 > which seems to be the correct approach to this pair of eyes - most people
 > cast within the comparison routine to the required type of argument, which
 > adds an air of genericism to the sorting, at the cost of access through void * pointers.
 > 
 > matt is also going to take a further look to check the direction of testing.
 > I'll update the bug when the oracle speaks further.
 > 
 > 
 > 

From: christos@zoulas.com (Christos Zoulas)
To: Jeremy Huddleston <jeremyhu@apple.com>, gnats-bugs@NetBSD.org
Cc: agc@NetBSD.org, lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org, 
	gnats-admin@netbsd.org
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 (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

From: Jeremy Huddleston <jeremyhu@apple.com>
To: gnats-bugs@NetBSD.org
Cc: agc@NetBSD.org, gnats-admin@netbsd.org, netbsd-bugs@netbsd.org
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 (Christos Zoulas)
 > To: Jeremy Huddleston <jeremyhu@apple.com>, gnats-bugs@NetBSD.org
 > Cc: agc@NetBSD.org, lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org, 
 > 	gnats-admin@netbsd.org
 > 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 (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
 > 

From: christos@zoulas.com (Christos Zoulas)
To: Jeremy Huddleston <jeremyhu@apple.com>, gnats-bugs@NetBSD.org
Cc: agc@NetBSD.org, gnats-admin@netbsd.org, netbsd-bugs@netbsd.org, 
	matt@netbsd.org
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 (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 (Christos Zoulas)
 | > To: Jeremy Huddleston <jeremyhu@apple.com>, gnats-bugs@NetBSD.org
 | > Cc: agc@NetBSD.org, lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org, 
 | > 	gnats-admin@netbsd.org
 | > 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 (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

Here's a diff:

Index: sys/sys/rb.h
===================================================================
RCS file: /cvsroot/src/sys/sys/rb.h,v
retrieving revision 1.13
diff -u -u -r1.13 rb.h
--- sys/sys/rb.h	16 Aug 2009 10:57:01 -0000	1.13
+++ sys/sys/rb.h	20 Sep 2010 19:01:43 -0000
@@ -40,6 +40,7 @@
 #include <sys/queue.h>
 #include <sys/endian.h>

+__BEGIN_DECLS
 struct rb_node {
 	struct rb_node *rb_nodes[2];
 #define	RB_DIR_LEFT		0
@@ -124,24 +125,25 @@

 /*
  * rbto_compare_nodes_fn:
- *	return a positive value if the first node < the second node.
- *	return a negative value if the first node > the second node.
+ *	return a positive value if the first node > the second node.
+ *	return a negative value if the first node < the second node.
  *	return 0 if they are considered same.
  *
  * rbto_compare_key_fn:
- *	return a positive value if the node < the key.
- *	return a negative value if the node > the key.
+ *	return a positive value if the node > the key.
+ *	return a negative value if the node < the key.
  *	return 0 if they are considered same.
  */

-typedef signed int (*const rbto_compare_nodes_fn)(const struct rb_node *,
-    const struct rb_node *);
-typedef signed int (*const rbto_compare_key_fn)(const struct rb_node *,
-    const void *);
+typedef signed int (*const rbto_compare_nodes_fn)(void *,
+    const struct rb_node *, const struct rb_node *);
+typedef signed int (*const rbto_compare_key_fn)(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;
+	void *rbto_context;
 };

 struct rb_tree {
@@ -187,5 +189,6 @@
 #ifdef RBSTATS
 void	rb_tree_depths(const struct rb_tree *, size_t *);
 #endif
+__END_DECLS

 #endif	/* _SYS_RB_H_*/
Index: common/lib/libc/gen/rb.c
===================================================================
RCS file: /cvsroot/src/common/lib/libc/gen/rb.c,v
retrieving revision 1.6
diff -u -u -r1.6 rb.c
--- common/lib/libc/gen/rb.c	30 Apr 2010 13:58:09 -0000	1.6
+++ common/lib/libc/gen/rb.c	20 Sep 2010 19:01:43 -0000
@@ -113,11 +113,13 @@
 struct rb_node *
 rb_tree_find_node(struct rb_tree *rbt, const void *key)
 {
-	rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
+	const struct rb_tree_ops *rbto = rbt->rbt_ops;
+	rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
 	struct rb_node *parent = rbt->rbt_root;

 	while (!RB_SENTINEL_P(parent)) {
-		const signed int diff = (*compare_key)(parent, key);
+		const signed int diff = (*compare_key)(rbto->rbto_context,
+		    parent, key);
 		if (diff == 0)
 			return parent;
 		parent = parent->rb_nodes[diff > 0];
@@ -129,12 +131,14 @@
 struct rb_node *
 rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)
 {
-	rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
+	const struct rb_tree_ops *rbto = rbt->rbt_ops;
+	rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
 	struct rb_node *parent = rbt->rbt_root;
 	struct rb_node *last = NULL;

 	while (!RB_SENTINEL_P(parent)) {
-		const signed int diff = (*compare_key)(parent, key);
+		const signed int diff = (*compare_key)(rbto->rbto_context,
+		    parent, key);
 		if (diff == 0)
 			return parent;
 		if (diff < 0)
@@ -148,12 +152,14 @@
 struct rb_node *
 rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)
 {
-	rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
+	const struct rb_tree_ops *rbto = rbt->rbt_ops;
+	rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
 	struct rb_node *parent = rbt->rbt_root;
 	struct rb_node *last = NULL;

 	while (!RB_SENTINEL_P(parent)) {
-		const signed int diff = (*compare_key)(parent, key);
+		const signed int diff = (*compare_key)(rbto->rbto_context,
+		    parent, key);
 		if (diff == 0)
 			return parent;
 		if (diff > 0)
@@ -167,7 +173,8 @@
 bool
 rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
 {
-	rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
+	const struct rb_tree_ops *rbto = rbt->rbt_ops;
+	rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
 	struct rb_node *parent, *tmp;
 	unsigned int position;
 	bool rebalance;
@@ -189,7 +196,8 @@
 	 * Find out where to place this new leaf.
 	 */
 	while (!RB_SENTINEL_P(tmp)) {
-		const signed int diff = (*compare_nodes)(tmp, self);
+		const signed int diff = (*compare_nodes)(rbto->rbto_context,
+		    tmp, self);
 		if (__predict_false(diff == 0)) {
 			/*
 			 * Node already exists; don't insert.
@@ -221,8 +229,10 @@
 			prev = TAILQ_PREV(next, rb_node_qh, rb_link);
 		KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
 		KASSERT(next == NULL || !RB_SENTINEL_P(next));
-		KASSERT(prev == NULL || (*compare_nodes)(prev, self) > 0);
-		KASSERT(next == NULL || (*compare_nodes)(self, next) > 0);
+		KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+		    prev, self) > 0);
+		KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
+		    self, next) > 0);
 	}
 #endif

@@ -270,10 +280,12 @@
 	if (RB_ROOT_P(rbt, self)) {
 		RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
 	} else if (position == RB_DIR_LEFT) {
-		KASSERT((*compare_nodes)(self, RB_FATHER(self)) > 0);
+		KASSERT((*compare_nodes)(rbto->rbto_context, self,
+		    RB_FATHER(self)) > 0);
 		RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
 	} else {
-		KASSERT((*compare_nodes)(RB_FATHER(self), self) > 0);
+		KASSERT((*compare_nodes)(rbto->rbto_context,
+		    RB_FATHER(self), self) > 0);
 		RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
 		    self, rb_link);
 	}
@@ -1047,10 +1059,12 @@
 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
 	const struct rb_node *prev, bool red_check)
 {
-	rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
+	struct rb_tree_ops *rbto = rbt->rbt_ops;
+	rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;

 	KASSERT(!RB_SENTINEL_P(self));
-	KASSERT(prev == NULL || (*compare_nodes)(prev, self) > 0);
+	KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+	    prev, self) > 0);

 	/*
 	 * Verify our relationship to our parent.
@@ -1064,10 +1078,12 @@
 		KASSERT(self != rbt->rbt_root);
 		KASSERT(!RB_FATHER_SENTINEL_P(self));
 		if (RB_POSITION(self) == RB_DIR_LEFT) {
-			KASSERT((*compare_nodes)(self, RB_FATHER(self)) > 0);
+			KASSERT((*compare_nodes)(rbto->rbto_context, self,
+			    RB_FATHER(self)) > 0);
 			KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
 		} else {
-			KASSERT((*compare_nodes)(self, RB_FATHER(self)) < 0);
+			KASSERT((*compare_nodes)(rbto->rbto_context, self,
+			    RB_FATHER(self)) < 0);
 			KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
 		}
 	}
Index: share/man/man3/rb.3
===================================================================
RCS file: /cvsroot/src/share/man/man3/rb.3,v
retrieving revision 1.4
diff -u -u -r1.4 rb.3
--- share/man/man3/rb.3	14 Apr 2010 16:30:50 -0000	1.4
+++ share/man/man3/rb.3	20 Sep 2010 19:01:44 -0000
@@ -27,7 +27,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd March 19, 2010
+.Dd September 20, 2010
 .Dt RB 3
 .Os
 .Sh NAME
@@ -70,29 +70,32 @@
 .It Vt struct rb_tree
 A red-black tree.
 .It Vt typedef signed int \
-(*const rbto_compare_nodes_fn)(const struct rb_node *, const struct rb_node *);
-The node-comparison operator.
+(*const rbto_compare_nodes_fn)(void *, const struct rb_node *, \
+const struct rb_node *);
+The node-comparison operator; the first argument is the context.
 Defines an ordering on nodes.
-Returns a positive value if the first node precedes the second node.
-Returns a negative value if the first node follows the second node.
+Returns a negative value if the first node precedes the second node.
+Returns a positive value if the first node follows the second node.
 Returns 0 if the first node and the second are identical according
 to the ordering.
 .It Vt typedef signed int \
-(*const rbto_compare_key_fn)(const struct rb_node *, const void *);
-The node-key comparison operator.
+(*const rbto_compare_key_fn)(void *, const struct rb_node *, const void *);
+The node-key comparison operator; the first argument is the context.
 Defines the order of nodes and keys.
-Returns a positive value if the node precedes the key.
-Returns a negative value if the node follows the key.
+Returns a negative value if the node precedes the key.
+Returns a positive value if the node follows the key.
 Returns 0 if the node is identical to the key according to the ordering.
 .It Vt struct rb_tree_ops
 Defines the operators for comparing two nodes in the same tree,
-and for comparing a node in the tree with a key.
+and for comparing a node in the tree with a key, together with
+a context to be passed to the comparators.
 Members of
 .Vt rb_tree_ops
 are
 .Bd -literal
         rbto_compare_nodes_fn rbto_compare_nodes;
         rbto_compare_key_fn rbto_compare_key;
+        void * rbto_context;
 .Ed
 .It Vt struct rb_node
 A node in a red-black tree.
Index: common/lib/libprop/prop_dictionary.c
===================================================================
RCS file: /cvsroot/src/common/lib/libprop/prop_dictionary.c,v
retrieving revision 1.35
diff -u -u -r1.35 prop_dictionary.c
--- common/lib/libprop/prop_dictionary.c	14 Apr 2009 02:53:41 -0000	1.35
+++ common/lib/libprop/prop_dictionary.c	20 Sep 2010 19:01:44 -0000
@@ -176,23 +176,25 @@
  */

 static int
-_prop_dict_keysym_rb_compare_nodes(const struct rb_node *n1,
+/*ARGSUSED*/
+_prop_dict_keysym_rb_compare_nodes(void *ctx __unused, const struct rb_node *n1,
 				   const struct rb_node *n2)
 {
 	const prop_dictionary_keysym_t pdk1 = RBNODE_TO_PDK(n1);
 	const prop_dictionary_keysym_t pdk2 = RBNODE_TO_PDK(n2);

-	return (strcmp(pdk1->pdk_key, pdk2->pdk_key));
+	return strcmp(pdk1->pdk_key, pdk2->pdk_key);
 }

 static int
-_prop_dict_keysym_rb_compare_key(const struct rb_node *n,
+/*ARGSUSED*/
+_prop_dict_keysym_rb_compare_key(void *ctx __unused, const struct rb_node *n,
 				 const void *v)
 {
 	const prop_dictionary_keysym_t pdk = RBNODE_TO_PDK(n);
 	const char *cp = v;

-	return (strcmp(pdk->pdk_key, cp));
+	return strcmp(pdk->pdk_key, cp);
 }

 static const struct rb_tree_ops _prop_dict_keysym_rb_tree_ops = {
Index: common/lib/libprop/prop_number.c
===================================================================
RCS file: /cvsroot/src/common/lib/libprop/prop_number.c,v
retrieving revision 1.22
diff -u -u -r1.22 prop_number.c
--- common/lib/libprop/prop_number.c	15 Mar 2009 22:29:11 -0000	1.22
+++ common/lib/libprop/prop_number.c	20 Sep 2010 19:01:44 -0000
@@ -122,23 +122,25 @@
 }

 static int
-_prop_number_rb_compare_nodes(const struct rb_node *n1,
+/*ARGSUSED*/
+_prop_number_rb_compare_nodes(void *ctx __unused, const struct rb_node *n1,
 			      const struct rb_node *n2)
 {
 	const prop_number_t pn1 = RBNODE_TO_PN(n1);
 	const prop_number_t pn2 = RBNODE_TO_PN(n2);

-	return (_prop_number_compare_values(&pn1->pn_value, &pn2->pn_value));
+	return _prop_number_compare_values(&pn1->pn_value, &pn2->pn_value);
 }

 static int
-_prop_number_rb_compare_key(const struct rb_node *n,
+/*ARGSUSED*/
+_prop_number_rb_compare_key(void *ctx __unused, const struct rb_node *n,
 			    const void *v)
 {
 	const prop_number_t pn = RBNODE_TO_PN(n);
 	const struct _prop_number_value *pnv = v;

-	return (_prop_number_compare_values(&pn->pn_value, pnv));
+	return _prop_number_compare_values(&pn->pn_value, pnv);
 }

 static const struct rb_tree_ops _prop_number_rb_tree_ops = {
Responsible-Changed-From-To: agc->rmind
Responsible-Changed-By: rmind@NetBSD.org
Responsible-Changed-When: Tue, 21 Sep 2010 15:51:52 +0000
Responsible-Changed-Why:
Take-over.


From: Mindaugas Rasiukevicius <rmind@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/43488 CVS commit: src
Date: Fri, 24 Sep 2010 22:51:52 +0000

 Module Name:	src
 Committed By:	rmind
 Date:		Fri Sep 24 22:51:52 UTC 2010

 Modified Files:
 	src/common/lib/libc/gen: rb.c
 	src/common/lib/libprop: prop_dictionary.c prop_number.c
 	src/sys/fs/udf: udf.h udf_subr.c
 	src/sys/kern: subr_lockdebug.c
 	src/sys/net/npf: npf_session.c npf_tableset.c
 	src/sys/nfs: nfs_node.c
 	src/sys/rump/librump/rumpkern: vm.c
 	src/sys/sys: rb.h
 	src/sys/uvm: uvm_map.c uvm_object.h uvm_page.c

 Log Message:
 Fixes/improvements to RB-tree implementation:
 1. Fix inverted node order, so that negative value from comparison operator
    would represent lower (left) node, and positive - higher (right) node.
 2. Add an argument (i.e. "context"), passed to comparison operators.
 3. Change rb_tree_insert_node() to return a node - either inserted one or
    already existing one.
 4. Amend the interface to manipulate the actual object, instead of the
    rb_node (in a similar way as Patricia-tree interface does).
 5. Update all RB-tree users accordingly.

 XXX: Perhaps rename rb.h to rbtree.h, since cleaning-up..

 1-3 address the PR/43488 by Jeremy Huddleston.

 Passes RB-tree regression tests.
 Reviewed by: matt@, christos@


 To generate a diff of this commit:
 cvs rdiff -u -r1.6 -r1.7 src/common/lib/libc/gen/rb.c
 cvs rdiff -u -r1.35 -r1.36 src/common/lib/libprop/prop_dictionary.c
 cvs rdiff -u -r1.22 -r1.23 src/common/lib/libprop/prop_number.c
 cvs rdiff -u -r1.41 -r1.42 src/sys/fs/udf/udf.h
 cvs rdiff -u -r1.107 -r1.108 src/sys/fs/udf/udf_subr.c
 cvs rdiff -u -r1.41 -r1.42 src/sys/kern/subr_lockdebug.c
 cvs rdiff -u -r1.2 -r1.3 src/sys/net/npf/npf_session.c
 cvs rdiff -u -r1.1 -r1.2 src/sys/net/npf/npf_tableset.c
 cvs rdiff -u -r1.113 -r1.114 src/sys/nfs/nfs_node.c
 cvs rdiff -u -r1.95 -r1.96 src/sys/rump/librump/rumpkern/vm.c
 cvs rdiff -u -r1.13 -r1.14 src/sys/sys/rb.h
 cvs rdiff -u -r1.292 -r1.293 src/sys/uvm/uvm_map.c
 cvs rdiff -u -r1.26 -r1.27 src/sys/uvm/uvm_object.h
 cvs rdiff -u -r1.155 -r1.156 src/sys/uvm/uvm_page.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

State-Changed-From-To: analyzed->closed
State-Changed-By: rmind@NetBSD.org
State-Changed-When: Sat, 25 Sep 2010 00:19:14 +0000
State-Changed-Why:
Changes/fixes made, all points have been addressed.  Thanks for the report!
Note: few more should come, e.g. rb.h rename to rbtree.h .


>Unformatted:

Home	PR Database Search