lib/47144: rbtree itteration is broken

[jeremyhu%apple.com@localhost]

>Number:         47144
>Category:       lib
>Synopsis:       rbtree itteration is broken
>Confidential:   no
>Severity:       serious
>Priority:       high
>Responsible:    lib-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Oct 30 21:50:00 +0000 2012
>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.