summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDmitri Pal <dpal@redhat.com>2009-07-15 17:28:54 -0400
committerStephen Gallagher <sgallagh@redhat.com>2009-07-16 17:29:13 -0400
commit5258186325dd9c566e68ef3217202d4ecf78b30e (patch)
tree63b39cfbaa94f289cb934a62b4f3ad22e3cb2224
parentccff2c2124b9ff085fb8473610a35daf1ab875cd (diff)
downloadsssd-5258186325dd9c566e68ef3217202d4ecf78b30e.tar.gz
sssd-5258186325dd9c566e68ef3217202d4ecf78b30e.tar.xz
sssd-5258186325dd9c566e68ef3217202d4ecf78b30e.zip
COLLECTION Improving searches
Addressing ticket #71. The searches were not taking advantage of the hashes, now they are.
-rw-r--r--common/collection/collection.c61
-rw-r--r--common/collection/collection_ut.c129
2 files changed, 181 insertions, 9 deletions
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");