X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/81b2c8f6358e3f5c0e1d480a45e8d1b574210177..4e213dc3614ff1ac4adb8432cc5bd387a322ca95:/src/xbt/dict.c diff --git a/src/xbt/dict.c b/src/xbt/dict.c index 6d788f0897..84c45869eb 100644 --- a/src/xbt/dict.c +++ b/src/xbt/dict.c @@ -127,12 +127,25 @@ void xbt_dict_hashsize_set(xbt_dict_t dict, int hashsize) { /** * Returns the hash code of a string. */ -unsigned int xbt_dict_hash(const char *str) { +static unsigned int xbt_dict_hash_ext(const char *str, int str_len) { /* fast implementation of djb2 algorithm */ unsigned int hash = 5381; int c; - while ((c = *str++)) { + while (str_len--) { + c = *str++; + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + } + + return hash; +} + +static unsigned int xbt_dict_hash(const char *str) { + /* fast implementation of djb2 algorithm */ + unsigned int hash = 5381; + int c; + + while ( (c = *str++) ) { hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ } @@ -156,10 +169,12 @@ void xbt_dict_set_ext(xbt_dict_t dict, int key_len, void *data, void_f_pvoid_t *free_ctn) { - xbt_assert(dict); - unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + unsigned int hash_code; xbt_dictelm_t current, previous = NULL; + xbt_assert(dict); + + hash_code = xbt_dict_hash_ext(key,key_len) % dict->table_size; current = dict->table[hash_code]; while (current != NULL && @@ -224,11 +239,15 @@ void xbt_dict_set(xbt_dict_t dict, void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len) { - xbt_assert(dict); - unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + + unsigned int hash_code; xbt_dictelm_t current; + xbt_assert(dict); + + hash_code = xbt_dict_hash_ext(key,key_len) % dict->table_size; + current = dict->table[hash_code]; while (current != NULL && (key_len != current->key_len || strncmp(key, current->key, key_len))) { @@ -255,11 +274,15 @@ void *xbt_dict_get_ext(xbt_dict_t dict, */ void *xbt_dict_get(xbt_dict_t dict, const char *key) { - xbt_assert(dict); - unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + + unsigned int hash_code ; xbt_dictelm_t current; + xbt_assert(dict); + + hash_code = xbt_dict_hash(key) % dict->table_size; + current = dict->table[hash_code]; while (current != NULL && (strcmp(key, current->key))) { current = current->next; @@ -303,11 +326,15 @@ void *xbt_dict_get_or_null(xbt_dict_t dict, void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len) { - xbt_assert(dict); - unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + + unsigned int hash_code ; xbt_dictelm_t current, previous = NULL; + xbt_assert(dict); + + hash_code = xbt_dict_hash_ext(key,key_len) % dict->table_size; + current = dict->table[hash_code]; while (current != NULL && (key_len != current->key_len || strncmp(key, current->key, key_len))) { @@ -351,10 +378,16 @@ void xbt_dict_remove(xbt_dict_t dict, * \param dict the dict */ void xbt_dict_reset(xbt_dict_t dict) { - xbt_assert(dict); + int i; xbt_dictelm_t current, previous = NULL; + + xbt_assert(dict); + + if (dict->count == 0) + return; + for (i = 0; i < dict->table_size; i++) { current = dict->table[i]; while (current != NULL) { @@ -382,9 +415,13 @@ int xbt_dict_length(xbt_dict_t dict) { * Add an already mallocated element to a dictionary. */ void xbt_dict_add_element(xbt_dict_t dict, xbt_dictelm_t element) { - xbt_assert(dict); - int hashcode = xbt_dict_hash(element->key) % dict->table_size; + + int hashcode; + + xbt_assert(dict); + + hashcode = xbt_dict_hash_ext(element->key,element->key_len) % dict->table_size; element->next = dict->table[hashcode]; dict->table[hashcode] = element; } @@ -458,11 +495,10 @@ static void print_str(void *str) { printf("%s",(char*)PRINTF_STR(str)); } -static void debuged_add(xbt_dict_t head,const char*key) -{ - char *data=xbt_strdup(key); +static void debuged_add_ext(xbt_dict_t head,const char*key,const char*data_to_fill) { + char *data=xbt_strdup(data_to_fill); - xbt_test_log1("Add %s",PRINTF_STR(key)); + xbt_test_log2("Add %s under %s",PRINTF_STR(data_to_fill),PRINTF_STR(key)); xbt_dict_set(head,key,data,&free); if (XBT_LOG_ISENABLED(xbt_dict,xbt_log_priority_debug)) { @@ -470,6 +506,9 @@ static void debuged_add(xbt_dict_t head,const char*key) fflush(stdout); } } +static void debuged_add(xbt_dict_t head,const char*key) { + debuged_add_ext(head,key,key); +} static void fill(xbt_dict_t *head) { xbt_test_add0("Fill in the dictionnary"); @@ -486,14 +525,21 @@ static void fill(xbt_dict_t *head) { debuged_add(*head,"123457"); } -static void search(xbt_dict_t head,const char*key) { - void *data; + +static void search_ext(xbt_dict_t head,const char*key, const char *data) { + void *found; xbt_test_add1("Search %s",key); - data=xbt_dict_get(head,key); - xbt_test_log1("Found %s",(char *)data); + found=xbt_dict_get(head,key); + xbt_test_log1("Found %s",(char *)found); if (data) - xbt_test_assert0(!strcmp((char*)data,key),"Key and data do not match"); + xbt_test_assert1(found,"data do not match expectations: found NULL while searching for %s",data); + if (found) + xbt_test_assert2(!strcmp((char*)data,found),"data do not match expectations: found %s while searching for %s", (char*)found, data); +} + +static void search(xbt_dict_t head,const char*key) { + search_ext(head,key,key); } static void debuged_remove(xbt_dict_t head,const char*key) { @@ -517,18 +563,21 @@ static void traverse(xbt_dict_t head) { } static void search_not_found(xbt_dict_t head, const char *data) { + int ok=0; xbt_ex_t e; xbt_test_add1("Search %s (expected not to be found)",data); TRY { - data = xbt_dict_get(head,"Can't be found"); + data = xbt_dict_get(head, data); THROW1(unknown_error,0,"Found something which shouldn't be there (%s)",data); } CATCH(e) { if (e.category != not_found_error) xbt_test_exception(e); xbt_ex_free(e); + ok=1; } + xbt_test_assert0(ok,"Exception not raised"); } static void count(xbt_dict_t dict, int length) { @@ -542,12 +591,28 @@ char *data; XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrieve, traverse"){ - xbt_test_add0("Traversal the empty dictionnary"); + xbt_test_add0("Traversal the null dictionnary"); traverse(head); + xbt_test_add0("Traversal and search the empty dictionnary"); + head = xbt_dict_new(); + traverse(head); + TRY { + debuged_remove(head,"12346"); + } CATCH(e) { + if (e.category != not_found_error) + xbt_test_exception(e); + xbt_ex_free(e); + } + xbt_dict_free(&head); + xbt_test_add0("Traverse the full dictionnary"); fill(&head); count(head, 7); + + debuged_add_ext(head,"toto","tutu"); + search_ext(head,"toto","tutu"); + debuged_remove(head,"toto"); search(head,"12a"); traverse(head); @@ -669,7 +734,7 @@ XBT_TEST_UNIT("nulldata",test_dict_nulldata,"NULL data management"){ xbt_test_add0("Store NULL under 'null'"); xbt_dict_set(head,"null",NULL,NULL); - search(head,"null"); + search_ext(head,"null",NULL); xbt_test_add0("Check whether I see it while traversing..."); { @@ -715,7 +780,7 @@ XBT_TEST_UNIT("crash",test_dict_crash,"Crash test"){ for (i=0;i<10;i++) { head=xbt_dict_new(); - // if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); + /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */ nb=0; for (j=0;j<1000;j++) { key=xbt_malloc(SIZEOFKEY); @@ -738,7 +803,7 @@ XBT_TEST_UNIT("crash",test_dict_crash,"Crash test"){ head=xbt_dict_new(); xbt_test_add1("Fill %d elements, with keys being the number of element",NB_ELM); for (j=0;j