COLLECTION Improving searches

Addressing ticket #71.
The searches were not taking advantage of the hashes,
now they are.

2 files changed, 181 insertions, 9 deletions

diff --git a/common/collection/collection.c b/common/collection/collection.c
index 113d9f03..31b47a05 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 af7746c4..a3da2e20 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");