From ea7d823fa584b36e9a34a43c32dc476beede5ea2 Mon Sep 17 00:00:00 2001 From: Dmitri Pal Date: Sun, 27 Sep 2009 22:18:41 -0400 Subject: COLLECTION Enhancing hashing and iteration functions --- common/collection/collection.c | 10 +++++++--- common/collection/collection.h | 9 +++++++-- common/collection/collection_iter.c | 30 ++++++++++++++++++++++++++++-- common/collection/collection_ut.c | 35 ++++++++++++++++++++++++++++++++++- 4 files changed, 76 insertions(+), 8 deletions(-) (limited to 'common') diff --git a/common/collection/collection.c b/common/collection/collection.c index d0078d9e4..27dee8364 100644 --- a/common/collection/collection.c +++ b/common/collection/collection.c @@ -241,7 +241,7 @@ int col_allocate_item(struct collection_item **ci, const char *property, return ENOMEM; } - item->phash = col_make_hash(property, &(item->property_len)); + item->phash = col_make_hash(property, 0, &(item->property_len)); TRACE_INFO_NUMBER("Item hash", item->phash); TRACE_INFO_NUMBER("Item property length", item->property_len); TRACE_INFO_NUMBER("Item property strlen", strlen(item->property)); @@ -2866,7 +2866,7 @@ int col_modify_item(struct collection_item *item, } /* Update property length and hash if we rename the property */ - item->phash = col_make_hash(property, &(item->property_len)); + item->phash = col_make_hash(property, 0, &(item->property_len)); TRACE_INFO_NUMBER("Item hash", item->phash); TRACE_INFO_NUMBER("Item property length", item->property_len); TRACE_INFO_NUMBER("Item property strlen", strlen(item->property)); @@ -3016,7 +3016,7 @@ uint64_t col_get_item_hash(struct collection_item *ci) * of the string not counting 0. * Length argument can be NULL. */ -uint64_t col_make_hash(const char *string, int *length) +uint64_t col_make_hash(const char *string, int sub_len, int *length) { uint64_t hash = 0; int str_len = 0; @@ -3026,6 +3026,10 @@ uint64_t col_make_hash(const char *string, int *length) if (string) { hash = FNV1a_base; while (string[str_len] != 0) { + + /* Check if we need to stop */ + if ((sub_len > 0) && (str_len == sub_len)) break; + hash = hash ^ toupper(string[str_len]); hash *= FNV1a_prime; str_len++; diff --git a/common/collection/collection.h b/common/collection/collection.h index be1240ca5..2e2fe642f 100644 --- a/common/collection/collection.h +++ b/common/collection/collection.h @@ -498,8 +498,12 @@ uint64_t col_get_item_hash(struct collection_item *ci); * algorithm. Populates "length" with length * of the string not counting 0. * Length argument can be NULL. + * If sub_len is greater than zero + * this value is used to count how many characters + * from string should be included into hash + * calculation. */ -uint64_t col_make_hash(const char *string, int *length); +uint64_t col_make_hash(const char *string, int sub_len, int *length); /* Compare two items. * The second item is evaluated against the first. @@ -745,7 +749,8 @@ int col_get_item_depth(struct collection_iterator *iterator, int *depth); /* Pins down the iterator to loop around current point */ void col_pin_iterator(struct collection_iterator *iterator); -/* FIXME - Do we need to be able to rewind iterator? */ +/* Rewinds iterator to the beginning */ +void col_rewind_iterator(struct collection_iterator *iterator); /* Set collection class */ int col_set_collection_class(struct collection_item *item, /* Collection */ diff --git a/common/collection/collection_iter.c b/common/collection/collection_iter.c index f66fc3085..0baefe83a 100644 --- a/common/collection/collection_iter.c +++ b/common/collection/collection_iter.c @@ -382,8 +382,13 @@ void col_pin_iterator(struct collection_iterator *iterator) { TRACE_FLOW_STRING("col_iterator_add_pin", "Entry"); - while ((iterator->stack[iterator->stack_depth - 1] == NULL) && - (iterator->stack_depth)) { + if ((!iterator) || (!iterator->stack)) { + TRACE_FLOW_STRING("Invalid itertor", "Ingoring"); + return; + } + + while ((iterator->stack_depth) && + (iterator->stack[iterator->stack_depth - 1] == NULL)) { iterator->stack_depth--; } @@ -399,3 +404,24 @@ void col_pin_iterator(struct collection_iterator *iterator) TRACE_FLOW_STRING("col_iterator_add_pin", "Exit"); } + + +/* Rewinds iterator to the beginning */ +void col_rewind_iterator(struct collection_iterator *iterator) +{ + TRACE_FLOW_STRING("col_rewind_iterator", "Entry"); + + if ((!iterator) || (!iterator->stack)) { + TRACE_FLOW_STRING("Invalid itertor", "Ingoring"); + return; + } + + iterator->pin = iterator->top; + iterator->stack[0] = iterator->top; + iterator->stack_depth = 1; + iterator->item_level = 0; + iterator->pin_level = 0; + iterator->can_break = 0; + + TRACE_FLOW_STRING("col_rewind_iterator", "Exit"); +} diff --git a/common/collection/collection_ut.c b/common/collection/collection_ut.c index 5d0c58463..1e91c2326 100644 --- a/common/collection/collection_ut.c +++ b/common/collection/collection_ut.c @@ -594,6 +594,8 @@ int iterator_test(void) int idepth = 0; int len = 0; int i; + uint64_t hash1, hash2; + int rwnd = 0; printf("\n\n==== ITERATOR TEST ====\n\n"); @@ -785,10 +787,34 @@ int iterator_test(void) printf("Item length: %d\n", len); len = 0; + hash1 = col_make_hash("new_name", 0, &len); printf("String name: %s\n", "new_name"); - printf("String hash: %lu\n", (unsigned long int)col_make_hash("new_name", &len)); + printf("String hash: %lu\n", (unsigned long int)hash1); printf("String length: %d\n", len); + len = 0; + hash2 = col_make_hash("new_name_suffix", 8, &len); + printf("String name: %.*s\n", len, "new_name_suffix"); + printf("String hash: %lu\n", (unsigned long int)hash2); + printf("String length: %d\n", len); + if (hash1 != hash2) { + printf("Hash calculation failed\n"); + col_unbind_iterator(iterator); + col_destroy_collection(peer); + return EINVAL; + } + + hash2 = col_make_hash("new_name", 8, &len); + printf("String name: %.*s\n", len, "new_name"); + printf("String hash: %lu\n", (unsigned long int)hash2); + printf("String length: %d\n", len); + if (hash1 != hash2) { + printf("Hash calculation failed\n"); + col_unbind_iterator(iterator); + col_destroy_collection(peer); + return EINVAL; + } + } } while(1); @@ -824,6 +850,13 @@ int iterator_test(void) printf("%*s", depth * 4, ""); col_debug_item(item); + if ((strcmp(col_get_item_property(item, NULL), "queue") == 0) && + (rwnd == 0)) { + printf("Rewinding iterator...\n"); + col_rewind_iterator(iterator); + rwnd++; + } + } while(1); -- cgit