utils: trie: fixed bug in foreach implementation.

when looping through the tree, the algorithm would stop, if found a '\0'
in the key of the tree node. there should be no "child" field after a '\0',
but "next" fields may exist.

3 files changed, 83 insertions, 6 deletions

diff --git a/src/common/utils.c b/src/common/utils.c
index 1ed79bf..97fa671 100644
--- a/src/common/utils.c
+++ b/src/common/utils.c
@@ -615,10 +615,8 @@ bc_trie_foreach_node(bc_trie_node_t *node, bc_string_t *str,
     if (node == NULL || str == NULL || func == NULL)
         return;
 
-    if (node->key == '\0') {
+    if (node->key == '\0')
         func(str->str, node->data, user_data);
-        return;
-    }
 
     if (node->child != NULL) {
         bc_string_t *child = bc_string_dup(str);
diff --git a/tests/common/check_config_parser.c b/tests/common/check_config_parser.c
index 942facd..b1e42a6 100644
--- a/tests/common/check_config_parser.c
+++ b/tests/common/check_config_parser.c
@@ -601,6 +601,38 @@ test_config_quoted_values(void **state)
 
 
 static void
+test_config_key_prefix(void **state)
+{
+    const char *a =
+        "[foo]\n"
+        "LAST_FLIGHT = lol\n"
+        "LAST_FLIGHT_SLUG = hehe\n";
+    bc_error_t *err = NULL;
+    bc_config_t *c = bc_config_parse(a, strlen(a), NULL, &err);
+    assert_null(err);
+    assert_non_null(c);
+    assert_non_null(c->root);
+    assert_int_equal(bc_trie_size(c->root), 1);
+    char **s = bc_config_list_sections(c);
+    assert_non_null(s);
+    assert_int_equal(bc_strv_length(s), 1);
+    assert_string_equal(s[0], "foo");
+    assert_null(s[1]);
+    bc_strv_free(s);
+    char **k = bc_config_list_keys(c, "foo");
+    assert_non_null(k);
+    assert_int_equal(bc_strv_length(k), 2);
+    assert_string_equal(k[0], "LAST_FLIGHT");
+    assert_string_equal(k[1], "LAST_FLIGHT_SLUG");
+    assert_null(k[2]);
+    bc_strv_free(k);
+    assert_string_equal(bc_config_get(c, "foo", "LAST_FLIGHT"), "lol");
+    assert_string_equal(bc_config_get(c, "foo", "LAST_FLIGHT_SLUG"), "hehe");
+    bc_config_free(c);
+}
+
+
+static void
 test_config_error_start(void **state)
 {
     const char *a =
@@ -678,6 +710,7 @@ main(void)
         unit_test(test_config_section_multiple_sections),
         unit_test(test_config_section_list),
         unit_test(test_config_quoted_values),
+        unit_test(test_config_key_prefix),
         unit_test(test_config_error_start),
         unit_test(test_config_error_section_with_newline),
         unit_test(test_config_error_key_without_value),
diff --git a/tests/common/check_utils.c b/tests/common/check_utils.c
index 7fd1d87..dc1eadd 100644
--- a/tests/common/check_utils.c
+++ b/tests/common/check_utils.c
@@ -907,8 +907,8 @@ test_trie_size(void **state)
 
 
 static unsigned int counter;
-static char *expected_keys[] = {"chu", "copa", "bola", "bote", "bo", "b", "test"};
-static char *expected_datas[] = {"nda", "bu", "guda", "aba", "haha", "c", "asd"};
+static char *expected_keys[] = {"chu", "copa", "bola", "bote", "bo", "b", "test", "testa"};
+static char *expected_datas[] = {"nda", "bu", "guda", "aba", "haha", "c", "asd", "lol"};
 
 static void
 mock_foreach(const char *key, void *data, void *user_data)
@@ -931,13 +931,58 @@ test_trie_foreach(void **state)
     bc_trie_insert(trie, "copa", bc_strdup("bu"));
     bc_trie_insert(trie, "b", bc_strdup("c"));
     bc_trie_insert(trie, "test", bc_strdup("asd"));
+    bc_trie_insert(trie, "testa", bc_strdup("lol"));
 
     counter = 0;
     bc_trie_foreach(trie, mock_foreach, "foo");
     bc_trie_foreach(NULL, mock_foreach, "foo");
     bc_trie_foreach(trie, NULL, "foo");
     bc_trie_foreach(NULL, NULL, "foo");
-    assert_int_equal(counter, 7);
+    assert_int_equal(counter, 8);
+
+    bc_trie_free(trie);
+}
+
+
+static void
+test_trie_inserted_after_prefix(void **state)
+{
+    bc_trie_t *trie = bc_trie_new(free);
+
+    bc_trie_insert(trie, "bola", bc_strdup("guda"));
+    assert_true(trie->root->key == 'b');
+    assert_null(trie->root->data);
+    assert_true(trie->root->child->key == 'o');
+    assert_null(trie->root->child->data);
+    assert_true(trie->root->child->child->key == 'l');
+    assert_null(trie->root->child->child->data);
+    assert_true(trie->root->child->child->child->key == 'a');
+    assert_null(trie->root->child->child->child->data);
+    assert_true(trie->root->child->child->child->child->key == '\0');
+    assert_string_equal(trie->root->child->child->child->child->data, "guda");
+
+    bc_trie_insert(trie, "bolaoo", bc_strdup("asdf"));
+    assert_true(trie->root->key == 'b');
+    assert_null(trie->root->data);
+    assert_true(trie->root->child->key == 'o');
+    assert_null(trie->root->child->data);
+    assert_true(trie->root->child->child->key == 'l');
+    assert_null(trie->root->child->child->data);
+    assert_true(trie->root->child->child->child->key == 'a');
+    assert_null(trie->root->child->child->child->data);
+    assert_true(trie->root->child->child->child->child->key == '\0');
+    assert_string_equal(trie->root->child->child->child->child->data, "guda");
+    assert_non_null(trie->root->child->child->child->child->next);
+    assert_true(trie->root->child->child->child->child->next->key == 'o');
+    assert_null(trie->root->child->child->child->child->next->data);
+    assert_true(trie->root->child->child->child->child->next->child->key == 'o');
+    assert_null(trie->root->child->child->child->child->next->child->data);
+    assert_true(trie->root->child->child->child->child->next->child->child->key == '\0');
+    assert_string_equal(trie->root->child->child->child->child->next->child->child->data, "asdf");
+
+    assert_int_equal(bc_trie_size(trie), 2);
+    assert_string_equal(bc_trie_lookup(trie, "bola"), "guda");
+    assert_string_equal(bc_trie_lookup(trie, "bolaoo"), "asdf");
 
     bc_trie_free(trie);
 }
@@ -1015,6 +1060,7 @@ main(void)
         unit_test(test_trie_lookup),
         unit_test(test_trie_size),
         unit_test(test_trie_foreach),
+        unit_test(test_trie_inserted_after_prefix),
 
         // shell
         unit_test(test_shell_quote),