Наткнулся на довольно мерзкий баг, в когда-то уважаемой мной библиотеке 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;
}
#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;
}
баг то поправил?
Ой, только заметил вопрос, извини.
Нет, не поправил, просто выкинул кусок на Си и переписал на C++. В Си ну уж очень утомляет необходимость поиска велосипедов.
Конечно не поправил, потому что бага там нет.
Обычно баг в коде криворукого, а виновата библиотека, компилятор, операционная система, менеджер, заказчик, правительство и ZOG.
У вас переполнение при приведении к int. Да и вообще смешаны unsigned и signed
#define CMPARATOR(x,y) (x->data data ? -1 : (x->data == y->data ? 0 : 1))
Спасибо за дополнение.
P.S. говорить культурно все же стоит поучиться.
Действительно, очень интересная gotcha… Так с ходу и не догадаешься никогда, в чём может быть проблема…