i have code implements b+ tree. order 3
the problem if insert third value in tree ( leaf split ) throws me segmentation fault @ line
temp_pointers = (void**) malloc(order * sizeof(void *));
here full code leaf split
node * split_leaf_and_insert(node * root, node * leaf, char* key, record * pointer) { node * new_leaf = null; char ** temp_keys = null; void ** temp_pointers = null; int insertion_index, split, i, j; char*new_key; new_leaf = create_leaf(); temp_keys = (char**) malloc(order * sizeof(char*)); if (temp_keys == null) { exit(exit_failure); } temp_pointers = (void**) malloc(order * sizeof(void *)); if (temp_pointers == null) { exit(exit_failure); } insertion_index = 0; while (insertion_index < order - 1 && leaf->keys[insertion_index] < key) { insertion_index++; } (i = 0, j = 0; < leaf->number_of_keys; i++, j++) { if (j == insertion_index) { j++; } temp_keys[j] = (char*) malloc(strlen(leaf->keys[i]) + 1); strcpy(temp_keys[j], leaf->keys[i]); } temp_keys[insertion_index] = (char*) malloc(strlen(key) + 1); strcpy(temp_keys[insertion_index], key); temp_pointers[insertion_index] = pointer; leaf->number_of_keys = 0; split = cut(order - 1); (i = 0; < split; i++) { leaf->pointers[i] = temp_pointers[i]; leaf->keys[i] = (char*) malloc((strlen(temp_keys[i]) + 1)); strcpy(leaf->keys[i], temp_keys[i]); leaf->number_of_keys++; (i = split, j = 0; < order; i++, j++) { new_leaf->pointers[j] = temp_pointers[i]; new_leaf->keys[j] = (char*) malloc(strlen(temp_keys[i]) + 1); strcpy(new_leaf->keys[j], temp_keys[i]); new_leaf->number_of_keys++; } free(temp_pointers); free(temp_keys); new_leaf->pointers[order - 1] = leaf->pointers[order - 1]; leaf->pointers[order - 1] = new_leaf; (i = leaf->number_of_keys; < order - 1; i++) { leaf->pointers[i] = null; } (i = new_leaf->number_of_keys; < order - 1; i++) { new_leaf->pointers[i] = null; } new_leaf->parent = leaf->parent; new_key = (char*) malloc(strlen(new_leaf->keys[0]) + 1); strcpy(new_key, new_leaf->keys[0]); } return insert_value_into_parent(root, leaf, new_key, new_leaf); }
like said first 2 records works third says
use of uninitialised value of size 8 when use malloc in c stack trace ==1336== use of uninitialised value of size 8 ==1336== @ 0x4041f5: display (b-tree.c:754) ==1336== 0x40519c: main (main.c:54) ==1336== uninitialised value created heap allocation ==1336== @ 0x4c2b6cd: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==1336== 0x4036d0: split_leaf_and_insert (b-tree.c:597) ==1336== 0x402e3c: insert_value (b-tree.c:477) ==1336== 0x4029b1: search (b-tree.c:396) ==1336== 0x404159: display (b-tree.c:739) ==1336== 0x40519c: main (main.c:54) ==1336== ==1336== invalid read of size 8 ==1336== @ 0x4041f5: display (b-tree.c:754) ==1336== 0x40519c: main (main.c:54) ==1336== address 0x0 not stack'd, malloc'd or (recently) free'd ==1336== ==1336==
the next function insert function calls 1 above
node * insert_value(node * root, char* key, record * rec) { node * leaf; if (root == null) { return create_new_tree(key, rec); } leaf = find_leaf(root, key); if (leaf->number_of_keys < order - 1) { leaf = insert_value_into_leaf(leaf, key, rec); return root; } return split_leaf_and_insert(root, leaf, key, rec); }
can explain me happening?
Comments
Post a Comment