From 0ae85f6545b1d4a64836b0a3a5676a0bed9854d5 Mon Sep 17 00:00:00 2001 From: "Rafael G. Martins" Date: Sat, 24 Jun 2017 11:45:40 +0200 Subject: 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. --- src/common/utils.c | 4 +-- tests/common/check_config_parser.c | 33 ++++++++++++++++++++++++ tests/common/check_utils.c | 52 +++++++++++++++++++++++++++++++++++--- 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 @@ -600,6 +600,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) { @@ -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), -- cgit v1.2.3-18-g5258