Skip to content

bugs for art_insert in some case #51

Description

@yizhang2077

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

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions