Fix memory leak when deleting a random entry that fits in a type3 (48)

amarince · amarince · commit cfbfaf7d017d · 2017-11-22T22:38:46.000+01:00
node

Add new unit test to verify no memory leaks with random delete of
entries
diff --git a/src/art.c b/src/art.c
@@ -68,7 +68,7 @@ static void destroy_node(art_node *n) {
     }
 
     // Handle each node type
-    int i;
+    int i, idx;
     union {
         art_node4 *p1;
         art_node16 *p2;
@@ -92,8 +92,10 @@ static void destroy_node(art_node *n) {
 
         case NODE48:
             p.p3 = (art_node48*)n;
-            for (i=0;i<n->num_children;i++) {
-                destroy_node(p.p3->children[i]);
+            for (i=0;i<256;i++) {
+                idx = ((art_node48*)n)->keys[i]; 
+                if (!idx) continue; 
+                destroy_node(p.p3->children[idx-1]);
             }
             break;
 
diff --git a/tests/runner.c b/tests/runner.c
@@ -19,11 +19,13 @@ int main(void)
     tcase_add_test(tc1, test_art_insert_verylong);
     tcase_add_test(tc1, test_art_insert_search);
     tcase_add_test(tc1, test_art_insert_delete);
+    tcase_add_test(tc1, test_art_insert_random_delete);
     tcase_add_test(tc1, test_art_insert_iter);
     tcase_add_test(tc1, test_art_iter_prefix);
     tcase_add_test(tc1, test_art_long_prefix);
     tcase_add_test(tc1, test_art_insert_search_uuid);
     tcase_add_test(tc1, test_art_max_prefix_len_scan_prefix);
+    tcase_set_timeout(tc1, 180);
 
     srunner_run_all(sr, CK_ENV);
     nf = srunner_ntests_failed(sr);
diff --git a/tests/test_art.c b/tests/test_art.c
@@ -200,6 +200,48 @@ START_TEST(test_art_insert_delete)
 }
 END_TEST
 
+START_TEST(test_art_insert_random_delete)
+{
+    art_tree t;
+    int res = art_tree_init(&t);
+    fail_unless(res == 0);
+
+    int len;
+    char buf[512];
+    FILE *f = fopen("tests/words.txt", "r");
+
+    uintptr_t line = 1;
+    while (fgets(buf, sizeof buf, f)) {
+        len = strlen(buf);
+        buf[len-1] = '\0';
+        fail_unless(NULL ==
+            art_insert(&t, (unsigned char*)buf, len, (void*)line));
+        line++;
+    }
+
+    // Can be improved ensuring one delete on each node type
+    // A is in 48 node
+    uintptr_t lineno = 1;
+    // Search first, ensure all entries are visible
+    uintptr_t val = (uintptr_t)art_search(&t, (unsigned char*)"A", strlen("A")+1);
+    fail_unless(lineno == val, "Line: %d Val: %" PRIuPTR " Str: %s\n", lineno,
+        val, "A");
+
+    // Delete a single entry, should get lineno back
+    val = (uintptr_t )art_delete(&t, (unsigned char *) "A", strlen("A")+1);
+    fail_unless(lineno == val, "Line: %d Val: %" PRIuPTR " Str: %s\n", lineno,
+        val, "A");
+
+    // Ensure  the entry is no longer visible
+    val = (uintptr_t)art_search(&t, (unsigned char*)"A", strlen("A")+1);
+    fail_unless(0 == val, "Line: %d Val: %" PRIuPTR " Str: %s\n", 0,
+        val, "A");
+
+    res = art_tree_destroy(&t);
+    fail_unless(res == 0);
+}
+END_TEST
+
 int iter_cb(void *data, const unsigned char* key, uint32_t key_len, void *val) {
     uint64_t *out = (uint64_t*)data;
     uintptr_t line = (uintptr_t)val;
@@ -448,5 +490,3 @@ START_TEST(test_art_max_prefix_len_scan_prefix)
     fail_unless(res == 0);
 }
 END_TEST
-
-
