libart icon indicating copy to clipboard operation
libart copied to clipboard

bugs for art_insert in some case

Open yizhang2077 opened this issue 3 years ago • 1 comments

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

yizhang2077 avatar Feb 12 '22 15:02 yizhang2077

You can reference this issue as a fix: https://github.com/armon/libart/issues/42

yuedai avatar Jan 10 '23 01:01 yuedai