From 5258186325dd9c566e68ef3217202d4ecf78b30e Mon Sep 17 00:00:00 2001 From: Dmitri Pal Date: Wed, 15 Jul 2009 17:28:54 -0400 Subject: COLLECTION Improving searches Addressing ticket #71. The searches were not taking advantage of the hashes, now they are. --- common/collection/collection.c | 61 ++++++++++++++++-- common/collection/collection_ut.c | 129 ++++++++++++++++++++++++++++++++++++-- 2 files changed, 181 insertions(+), 9 deletions(-) (limited to 'common') diff --git a/common/collection/collection.c b/common/collection/collection.c index 113d9f037..31b47a052 100644 --- a/common/collection/collection.c +++ b/common/collection/collection.c @@ -140,7 +140,7 @@ static int col_validate_property(const char *property) check = property; while (*check != '\0') { - if ((!isalnum(*check)) && (!ispunct(*check))) { + if (((!isalnum(*check)) && (!ispunct(*check))) || (*check == '.')) { invalid = 1; break; } @@ -227,7 +227,7 @@ static int col_allocate_item(struct collection_item **ci, const char *property, item->property_len = 0; while (property[item->property_len] != 0) { - item->phash = item->phash ^ property[item->property_len]; + item->phash = item->phash ^ toupper(property[item->property_len]); item->phash *= FNV1a_prime; item->property_len++; } @@ -301,7 +301,7 @@ static int col_find_property(struct collection_item *collection, /* Create hash of the string to search */ while(refprop[i] != 0) { - ps.hash = ps.hash ^ refprop[i]; + ps.hash = ps.hash ^ toupper(refprop[i]); ps.hash *= FNV1a_prime; i++; } @@ -1125,6 +1125,7 @@ struct path_data { struct find_name { const char *name_to_find; int name_len_to_find; + uint64_t hash; int type_to_match; char *given_name; int given_len; @@ -1197,6 +1198,7 @@ static int col_match_item(struct collection_item *current, TRACE_FLOW_STRING("col_match_item", "Entry"); if (traverse_data->type_to_match & current->type) { + /* Check if there is any value to match */ if ((traverse_data->name_to_find == NULL) || (*(traverse_data->name_to_find) == '\0')) { @@ -1205,6 +1207,14 @@ static int col_match_item(struct collection_item *current, return COL_MATCH; } + /* Check the hashes - if they do not match return */ + if (traverse_data->hash != current->phash) { + TRACE_INFO_STRING("col_match_item","Returning NO match!"); + return COL_NOMATCH; + } + + /* We will do the actual string comparison only if the hashes matched */ + /* Start comparing the two strings from the end */ find_str = traverse_data->name_to_find + traverse_data->name_len_to_find; start = current->property; @@ -1463,6 +1473,9 @@ static int col_find_item_and_do(struct collection_item *ci, int error = EOK; struct find_name *traverse_data = NULL; unsigned depth = 0; + int count = 0; + const char *last_part; + char *dot; TRACE_FLOW_STRING("col_find_item_and_do", "Entry."); @@ -1483,7 +1496,7 @@ static int col_find_item_and_do(struct collection_item *ci, } /* Prepare data for traversal */ errno = 0; - traverse_data= (struct find_name *)malloc(sizeof(struct find_name)); + traverse_data = (struct find_name *)malloc(sizeof(struct find_name)); if (traverse_data == NULL) { error = errno; TRACE_ERROR_NUMBER("Failed to allocate traverse data memory - returning error!", errno); @@ -1493,7 +1506,45 @@ static int col_find_item_and_do(struct collection_item *ci, TRACE_INFO_STRING("col_find_item_and_do", "Filling in traverse data."); traverse_data->name_to_find = property_to_find; - traverse_data->name_len_to_find = strlen(property_to_find); + + if (property_to_find != NULL) { + + traverse_data->name_len_to_find = strlen(property_to_find); + + /* Check if the search string ends with dot - this is ellegal */ + if (traverse_data->name_to_find[traverse_data->name_len_to_find - 1] == '.') { + TRACE_ERROR_NUMBER("Search string is invalid.", EINVAL); + free(traverse_data); + return EINVAL; + } + + /* Find last dot if any */ + dot = strrchr(traverse_data->name_to_find, '.'); + if (dot != NULL) { + dot++; + last_part = dot; + } + else last_part = traverse_data->name_to_find; + + TRACE_INFO_STRING("Last item", last_part); + + /* Create hash of the last part */ + traverse_data->hash = FNV1a_base; + + /* Create hash of the string to search */ + while(last_part[count] != 0) { + traverse_data->hash = traverse_data->hash ^ toupper(last_part[count]); + traverse_data->hash *= FNV1a_prime; + count++; + } + } + else { + /* We a looking for a first element of a given type */ + TRACE_INFO_STRING("No search string", ""); + traverse_data->name_len_to_find = 0; + } + + traverse_data->type_to_match = type; traverse_data->given_name = NULL; traverse_data->given_len = 0; diff --git a/common/collection/collection_ut.c b/common/collection/collection_ut.c index af7746c40..a3da2e20a 100644 --- a/common/collection/collection_ut.c +++ b/common/collection/collection_ut.c @@ -119,7 +119,7 @@ int single_collection_test(void) (error = col_add_str_property(handle, NULL, "property_1", "some data", 0)) || (error = col_add_str_property(handle, NULL, "property_2", "some other data", 2)) || (error = col_add_str_property(handle, NULL, "property_3", "more data", 7))) { - printf("Failed to add property. Error %d", error); + printf("Failed to add property. Error %d\n", error); col_destroy_collection(handle); return error; } @@ -133,14 +133,14 @@ int single_collection_test(void) error = col_add_double_property(handle, NULL, "double", 0.253545); if (error) { - printf("Failed to add property. Error %d", error); + printf("Failed to add double property. Error %d\n", error); col_destroy_collection(handle); return error; } error = col_update_double_property(handle, "double", COL_TRAVERSE_DEFAULT, 1.999999); if (error) { - printf("Failed to add property. Error %d", error); + printf("Failed to update double property. Error %d\n", error); col_destroy_collection(handle); return error; } @@ -1246,6 +1246,126 @@ int delete_test(void) return error; } +/* Search test */ +int search_test(void) +{ + struct collection_item *level1 = NULL; + struct collection_item *level2 = NULL; + struct collection_item *level3 = NULL; + struct collection_item *level4 = NULL; + char binary_dump[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; + int found = 0; + int error = 0; + + printf("\n\n==== SEARCH TEST ====\n\n"); + + if ((error = col_create_collection(&level1, "level1", 0)) || + (error = col_create_collection(&level2, "level2", 0)) || + (error = col_add_collection_to_collection(level1, NULL, NULL, level2, COL_ADD_MODE_REFERENCE)) || + (error = col_create_collection(&level3, "level3", 0)) || + (error = col_add_collection_to_collection(level1, "level2", NULL, level3, COL_ADD_MODE_REFERENCE)) || + (error = col_create_collection(&level4, "level4", 0)) || + (error = col_add_collection_to_collection(level1, "level3", NULL, level4, COL_ADD_MODE_REFERENCE)) || + (error = col_add_int_property(level1, "level4", "id", 1)) || + (error = col_add_long_property(level1, "level3", "packets", 100000000L)) || + (error = col_add_binary_property(level1, "level2", "stack", binary_dump, sizeof(binary_dump)))) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Failed to build test. Error %d\n", error); + return error; + } + + col_debug_collection(level1, COL_TRAVERSE_DEFAULT); + + error = col_is_item_in_collection(level1, "level1.level2.level3.level4.", COL_TYPE_ANY, COL_TRAVERSE_DEFAULT, &found); + if (!error) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Expected error here since the search data is illegal but got success\n"); + return EINVAL; + } + + found = 0; + error = 0; + error = col_is_item_in_collection(level1, "level1.level2.level3.level4.id", COL_TYPE_ANY, COL_TRAVERSE_DEFAULT, &found); + if ((error) || (!found)) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Failed to find item [level1.level2.level3.level4.id]. Error %d\n", error); + return error ? error : ENOENT; + } + else printf("Expected item is found\n"); + + + found = 0; + error = 0; + error = col_is_item_in_collection(level1, "level3.level4.id", COL_TYPE_ANY, COL_TRAVERSE_DEFAULT, &found); + if ((error) || (!found)) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Failed to find item [level3.level4.id]. Error %d\n", error); + return error ? error : ENOENT; + } + else printf("Expected item is found\n"); + + found = 0; + error = 0; + error = col_is_item_in_collection(level1, "level3.packets", COL_TYPE_ANY, COL_TRAVERSE_DEFAULT, &found); + if ((error) || (!found)) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Failed to find item [level3.packets]. Error %d\n", error); + return error ? error : ENOENT; + } + else printf("Expected item is found\n"); + + found = 0; + error = 0; + error = col_is_item_in_collection(level1, "level1.level2.stack", COL_TYPE_ANY, COL_TRAVERSE_DEFAULT, &found); + if ((error) || (!found)) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Failed to find item [level1.level2.stack]. Error %d\n", error); + return error ? error : ENOENT; + } + else printf("Expected item is found\n"); + + found = 0; + error = 0; + error = col_is_item_in_collection(level1, "level1.level2.level3", COL_TYPE_ANY, COL_TRAVERSE_DEFAULT, &found); + if ((error) || (!found)) { + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + printf("Failed to find item [level1.level2.level3]. Error %d\n", error); + return error ? error : ENOENT; + } + else printf("Expected item is found\n"); + + col_destroy_collection(level1); + col_destroy_collection(level2); + col_destroy_collection(level3); + col_destroy_collection(level4); + + printf("\n\n==== SEARCH TEST END ====\n\n"); + + return EOK; +} + + /* Main function of the unit test */ int main(int argc, char *argv[]) @@ -1259,7 +1379,8 @@ int main(int argc, char *argv[]) (error = mixed_collection_test()) || (error = iterator_test()) || (error = insert_extract_test()) || - (error = delete_test())) { + (error = delete_test()) || + (error = search_test())) { printf("Failed!\n"); } else printf("Success!\n"); -- cgit