libart
libart copied to clipboard
bugs for art_insert in some case
In the following example, I insert two keys and do a search, I expect get right value, but it will raising error.
#include "art.h"
#include "assert.h"
#include "stdio.h"
void test(){
art_tree tree;
art_tree_init(&tree);
unsigned char key1[1] = {0};
unsigned char key2[2] = {0, 1};
int value1 = 1, value2 = 2;
art_insert(&tree, key1, 1, &value1);
art_insert(&tree, key2, 2, &value2);
int* value_ptr = (int*)art_search(&tree, key1, 1);
assert(value_ptr != NULL);
assert(*value_ptr == value1);
}
int main(){
test();
}
I find if we insert a string whose prefix is a existed key, the previous key may be missed due to following code in art.c:580 :
add_child4(new_node, ref, l->key[depth+longest_prefix], SET_LEAF(l));
add_child4(new_node, ref, l2->key[depth+longest_prefix], SET_LEAF(l2));
depth + longest_prefix overflows in my example
You can reference this issue as a fix: https://github.com/armon/libart/issues/42