NetBSD Problem Report #47144

From www@NetBSD.org  Tue Oct 30 21:47:16 2012
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [149.20.53.66])
	by www.NetBSD.org (Postfix) with ESMTP id 2B00563CAFB
	for <gnats-bugs@gnats.NetBSD.org>; Tue, 30 Oct 2012 21:47:16 +0000 (UTC)
Message-Id: <20121030214715.182F163CAFB@www.NetBSD.org>
Date: Tue, 30 Oct 2012 21:47:14 +0000 (UTC)
From: jeremyhu@apple.com
Reply-To: jeremyhu@apple.com
To: gnats-bugs@NetBSD.org
Subject: rbtree itteration is broken
X-Send-Pr-Version: www-1.0

>Number:         47144
>Category:       lib
>Synopsis:       rbtree itteration is broken
>Confidential:   no
>Severity:       serious
>Priority:       high
>Responsible:    lib-bug-people
>State:          closed
>Class:          doc-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Oct 30 21:50:00 +0000 2012
>Last-Modified:  Mon Oct 27 05:55:01 +0000 2014
>Originator:     Jeremy Huddleston Sequoia
>Release:        6.0
>Organization:
Apple Inc
>Environment:
NetBSD netbsd6.apple.com 6.0_RC2 NetBSD 6.0_RC2 (GENERIC) amd64

>Description:
rbtree itteration is broken

rb_tree_iterate(&rbt, NULL, RB_DIR_RIGHT); returns the last node in the tree.  It should return the first.

rb_tree_iterate(&rbt, NULL, RB_DIR_LEFT); returns the first node in the tree.  It should return the last.


>How-To-Repeat:
#include <sys/rbtree.h>
#include <sys/types.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    struct rb_node      rbnode;
    char                *value;
} rbtest_node_t;

static int
_rbtest_compare_nodes(__unused void *context, const void *_node1, const void *_node2) {
    rbtest_node_t *node1 = (rbtest_node_t *) _node1;
    rbtest_node_t *node2 = (rbtest_node_t *) _node2;

    return strcmp(node1->value, node2->value);
}

static int
_rbtest_compare_key(__unused void *context, const void *_node, const void *value)
{
    rbtest_node_t *node = (rbtest_node_t *) _node;

    return strcmp(node->value, value);
}

static const rb_tree_ops_t ops = {
    .rbto_compare_nodes = _rbtest_compare_nodes,
    .rbto_compare_key = _rbtest_compare_key,
    .rbto_node_offset = offsetof(rbtest_node_t, rbnode),
    .rbto_context = NULL
};

/* Generate a pseudorandom string */
static void
_rbtest_random_string(char *str, size_t len) {
    size_t i;

    for (i=0; i < len - 2; i++) {
        str[i] = 'a' + random() % 26;
    }
    str[len - 1] = '\0';
}

static void
_rbtest_insert_random_string_node(rb_tree_t *rbt) {
    rbtest_node_t *node;

    node = calloc(1, sizeof(*node));

    node->value = malloc(32 * sizeof(char));
    _rbtest_random_string(node->value, 32);

    printf("Inserting %s\n", node->value);
    rb_tree_insert_node(rbt, node);
}

int main() {
    rb_tree_t rbt;
    rbtest_node_t *it;
    size_t i;

    rb_tree_init(&rbt, &ops);

    srandom(0);

    for (i=0; i < 100; i++) {
        _rbtest_insert_random_string_node(&rbt);
    }

    it = rb_tree_iterate(&rbt, NULL, RB_DIR_RIGHT);
    while (it != NULL) {
        printf("%s\n", it->value);
        it = rb_tree_iterate(&rbt, it, RB_DIR_RIGHT);
    }

    return 0;
}

>Fix:
I have not tested if the RBSMALL path is also affected by this issue.


>Release-Note:

>Audit-Trail:

State-Changed-From-To: open->closed
State-Changed-By: rmind@NetBSD.org
State-Changed-When: Tue, 30 Oct 2012 22:12:28 +0000
State-Changed-Why:
It is perhaps a bit confusing and unintuitive API behaviour, but the iteration
is not broken.  The problem is wrong documentation, which ought to be fixed.

See PR/46034.  Closing this as a duplicate.


From: Jeremy Huddleston Sequoia <jeremyhu@apple.com>
To: gnats-bugs@NetBSD.org
Cc: 
Subject: Re: lib/47144: rbtree iteration is broken
Date: Tue, 30 Oct 2012 14:57:23 -0700

 This should fix it (not yet tested).

 direction is the direction we want to travel.
 minmax[direction] is the ultimate node in that direction (the end point in that direction).  We want the start point.

 Index: rb.c
 ===================================================================
 --- rb.c	(revision 84243)
 +++ rb.c	(working copy)
 @@ -976,13 +976,13 @@
  #ifndef RBSMALL
  		if (RB_SENTINEL_P(rbt->rbt_root))
  			return NULL;
 -		return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
 +		return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction == RB_DIR_LEFT ? RB_DIR_RIGHT : RB_DIR_LEFT]);
  #else
  		self = rbt->rbt_root;
  		if (RB_SENTINEL_P(self))
  			return NULL;
 -		while (!RB_SENTINEL_P(self->rb_nodes[direction]))
 -			self = self->rb_nodes[direction];
 +		while (!RB_SENTINEL_P(self->rb_nodes[direction == RB_DIR_LEFT ? RB_DIR_RIGHT : RB_DIR_LEFT]))
 +			self = self->rb_nodes[direction == RB_DIR_LEFT ? RB_DIR_RIGHT : RB_DIR_LEFT];
  		return RB_NODETOITEM(rbto, self);
  #endif /* !RBSMALL */
  	}


 On Oct 30, 2012, at 2:50 PM, gnats-admin@netbsd.org wrote:

 > Thank you very much for your problem report.
 > It has the internal identification `lib/47144'.
 > The individual assigned to look at your
 > report is: lib-bug-people. 
 > 
 >> Category:       lib
 >> Responsible:    lib-bug-people
 >> Synopsis:       rbtree itteration is broken
 >> Arrival-Date:   Tue Oct 30 21:50:00 +0000 2012
 > 

From: Jeremy Huddleston Sequoia <jeremyhu@apple.com>
To: gnats-bugs@NetBSD.org
Cc: lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org, gnats-admin@netbsd.org,
 rmind@NetBSD.org
Subject: Re: lib/47144 (rbtree itteration is broken)
Date: Tue, 30 Oct 2012 15:17:11 -0700

 RB_TREE_MIN and RB_TREE_MAX also need to be fixed:

 Index: rbtree.h
 ===================================================================
 --- rbtree.h	(revision 84264)
 +++ rbtree.h	(working copy)
 @@ -95,8 +95,8 @@
    } while (/*CONSTCOND*/ 0)
  } rb_node_t;

 -#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
 -#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
 +#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
 +#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
  #define RB_TREE_FOREACH(N, T) \
      for ((N) = RB_TREE_MIN(T); (N); \
  	(N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))


 On Oct 30, 2012, at 3:12 PM, rmind@NetBSD.org wrote:

 > Synopsis: rbtree itteration is broken
 > 
 > State-Changed-From-To: open->closed
 > State-Changed-By: rmind@NetBSD.org
 > State-Changed-When: Tue, 30 Oct 2012 22:12:28 +0000
 > State-Changed-Why:
 > It is perhaps a bit confusing and unintuitive API behaviour, but the iteration
 > is not broken.  The problem is wrong documentation, which ought to be fixed.
 > 
 > See PR/46034.  Closing this as a duplicate.
 > 
 > 
 > 

From: Mindaugas Rasiukevicius <rmind@netbsd.org>
To: Jeremy Huddleston Sequoia <jeremyhu@apple.com>
Cc: gnats-bugs@NetBSD.org, lib-bug-people@netbsd.org,
 netbsd-bugs@netbsd.org, gnats-admin@netbsd.org, rmind@NetBSD.org
Subject: Re: lib/47144 (rbtree itteration is broken)
Date: Tue, 30 Oct 2012 23:31:44 +0000

 Jeremy Huddleston Sequoia <jeremyhu@apple.com> wrote:
 > RB_TREE_MIN and RB_TREE_MAX also need to be fixed:
 > 
 > Index: rbtree.h
 > ===================================================================
 > --- rbtree.h	(revision 84264)
 > +++ rbtree.h	(working copy)
 > @@ -95,8 +95,8 @@
 >    } while (/*CONSTCOND*/ 0)
 >  } rb_node_t;
 >  
 > -#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
 > -#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
 > +#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
 > +#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
 >  #define RB_TREE_FOREACH(N, T) \
 >      for ((N) = RB_TREE_MIN(T); (N); \
 >  	(N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))

 Well, it does not.. the current behaviour of rb_tree_iterate() returns
 the left-most node, which *is* the minimum.

 -- 
 Mindaugas

From: Jeremy Huddleston Sequoia <jeremyhu@apple.com>
To: "gnats-bugs@NetBSD.org" <gnats-bugs@NetBSD.org>
Cc: "lib-bug-people@netbsd.org" <lib-bug-people@netbsd.org>,
 "gnats-admin@netbsd.org" <gnats-admin@netbsd.org>,
 "netbsd-bugs@netbsd.org" <netbsd-bugs@netbsd.org>
Subject: Re: lib/47144 (rbtree itteration is broken)
Date: Tue, 30 Oct 2012 18:46:19 -0700

 yes, you need *BOTH* patches.  One to fix the function, and one to update rhe macro to use the correct function call.  Please see my example code.

 Sent from my iPhone...

 On Oct 30, 2012, at 16:35, Mindaugas Rasiukevicius <rmind@netbsd.org> wrote:

 > The following reply was made to PR lib/47144; it has been noted by GNATS.
 > 
 > From: Mindaugas Rasiukevicius <rmind@netbsd.org>
 > To: Jeremy Huddleston Sequoia <jeremyhu@apple.com>
 > Cc: gnats-bugs@NetBSD.org, lib-bug-people@netbsd.org,
 > netbsd-bugs@netbsd.org, gnats-admin@netbsd.org, rmind@NetBSD.org
 > Subject: Re: lib/47144 (rbtree itteration is broken)
 > Date: Tue, 30 Oct 2012 23:31:44 +0000
 > 
 > Jeremy Huddleston Sequoia <jeremyhu@apple.com> wrote:
 >> RB_TREE_MIN and RB_TREE_MAX also need to be fixed:
 >> 
 >> Index: rbtree.h
 >> ===================================================================
 >> --- rbtree.h    (revision 84264)
 >> +++ rbtree.h    (working copy)
 >> @@ -95,8 +95,8 @@
 >>   } while (/*CONSTCOND*/ 0)
 >> } rb_node_t;
 >> 
 >> -#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
 >> -#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
 >> +#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
 >> +#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
 >> #define RB_TREE_FOREACH(N, T) \
 >>     for ((N) = RB_TREE_MIN(T); (N); \
 >>    (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT))
 > 
 > Well, it does not.. the current behaviour of rb_tree_iterate() returns
 > the left-most node, which *is* the minimum.
 > 
 > -- 
 > Mindaugas
 > 

From: "Taylor R Campbell" <riastradh@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/47144 CVS commit: src/share/man/man3
Date: Wed, 13 Mar 2013 13:38:06 +0000

 Module Name:	src
 Committed By:	riastradh
 Date:		Wed Mar 13 13:38:05 UTC 2013

 Modified Files:
 	src/share/man/man3: rbtree.3

 Log Message:
 Fix documentation of rbtree(3) iteration.

 . Fix sense of rb_tree_iterate(rbt, NULL, ...).
 . Document RB_TREE_MIN/RB_TREE_MAX to avoid relying on that sense.
 . Document RB_TREE_FOREACH and RB_TREE_FOREACH_REVERSE to simplify
 iteration.

 Addresses PR lib/46034 and PR lib/47144.  It would have been nice to
 make `x = NULL; while ((x = rb_tree_iterate(t, NULL, ...)) != NULL)'
 DTRT to traverse t, but it's too much late for that now.

 We probably ought to have an RB_TREE_FOREACH{,_REVERSE}_SAFE too.

 ok christos


 To generate a diff of this commit:
 cvs rdiff -u -r1.7 -r1.8 src/share/man/man3/rbtree.3

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

From: "SAITOH Masanobu" <msaitoh@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/47144 CVS commit: [netbsd-6] src/share/man/man3
Date: Mon, 27 Oct 2014 05:51:57 +0000

 Module Name:	src
 Committed By:	msaitoh
 Date:		Mon Oct 27 05:51:57 UTC 2014

 Modified Files:
 	src/share/man/man3 [netbsd-6]: rbtree.3

 Log Message:
 Pull up following revision(s) (requested by riastradh in ticket #1136):
 	share/man/man3/rbtree.3: revision 1.8
 Fix documentation of rbtree(3) iteration.
 . Fix sense of rb_tree_iterate(rbt, NULL, ...).
 . Document RB_TREE_MIN/RB_TREE_MAX to avoid relying on that sense.
 . Document RB_TREE_FOREACH and RB_TREE_FOREACH_REVERSE to simplify
 iteration.
 Addresses PR lib/46034 and PR lib/47144.  It would have been nice to
 make `x = NULL; while ((x = rb_tree_iterate(t, NULL, ...)) != NULL)'
 DTRT to traverse t, but it's too much late for that now.
 We probably ought to have an RB_TREE_FOREACH{,_REVERSE}_SAFE too.
 ok christos


 To generate a diff of this commit:
 cvs rdiff -u -r1.5.6.1 -r1.5.6.2 src/share/man/man3/rbtree.3

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

>Unformatted:

Home	PR Database Search