NetBSD-Bugs archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

lib/47144: rbtree itteration is broken

>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
Apple Inc
NetBSD 6.0_RC2 NetBSD 6.0_RC2 (GENERIC) amd64

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.

#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 
    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);


    for (i=0; i < 100; i++) {

    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;

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

Home | Main Index | Thread Index | Old Index