RB-tree в sglib

Наткнулся на довольно мерзкий баг, в когда-то уважаемой мной библиотеке sglib. Дело в том, что на определенных наборах данных у rb-tree из этой библиотеки сносит башню! В результате добавленные ранее элементы перестают находиться, хотя, количество элементов не изменяется и при обходе дерева все элементы в нем присутствуют.

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include "sglib.h"

struct rb_tree
{
    int64_t data;
    char color_field;
    struct rb_tree *left;
    struct rb_tree *right;
};
typedef struct rb_tree rb_tree;

#define CMPARATOR(x,y) ((x->data)-(y->data))

SGLIB_DEFINE_RBTREE_PROTOTYPES(rb_tree, left, right, color_field, CMPARATOR);
SGLIB_DEFINE_RBTREE_FUNCTIONS(rb_tree, left, right, color_field, CMPARATOR);

rb_tree *the_tree = 0;

int main(int argc, char *argv[])
{
    if( argc < 2 )
        return -1;

    const char *data_file_path = argv[1];
    FILE *data_file;
    data_file = fopen( data_file_path, "r" );
    if( 0 == data_file )
        return -1;

    uint64_t value;
    rb_tree *node, e;
    e.data = 6610223104;
    int added = 0;
    while( EOF != fscanf( data_file, "%llun", &value ) )
    {
        if( value == e.data )
            added = 1;
        node = malloc( sizeof(rb_tree) );
        node->data = value;
        sglib_rb_tree_add( &the_tree, node );
        if( 0 != added )
        {
            node = sglib_rb_tree_find_member( the_tree, &e );
            if( 0 == node )
                printf("ERRORn");
        }
    }

    return 0;
}

Файл с тестовыми данными.

5 Comments RB-tree в sglib

    1. Alexander Stavonin

      Ой, только заметил вопрос, извини.
      Нет, не поправил, просто выкинул кусок на Си и переписал на C++. В Си ну уж очень утомляет необходимость поиска велосипедов.

      Reply
      1. Денис

        Конечно не поправил, потому что бага там нет.

        Обычно баг в коде криворукого, а виновата библиотека, компилятор, операционная система, менеджер, заказчик, правительство и ZOG.

        У вас переполнение при приведении к int. Да и вообще смешаны unsigned и signed
        #define CMPARATOR(x,y) (x->data data ? -1 : (x->data == y->data ? 0 : 1))

        Reply
          1. Алексей

            Действительно, очень интересная gotcha… Так с ходу и не догадаешься никогда, в чём может быть проблема…

Leave a Reply to alexey sudachen Cancel reply