X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/dff9e15c44ab6340d27215957c56fa72fad246a2..f2e6d1720c871dfec7d3ba04e8e0189337f8dd3d:/src/xbt/dict.c diff --git a/src/xbt/dict.c b/src/xbt/dict.c index 967e0ecbee..150bf69d00 100644 --- a/src/xbt/dict.c +++ b/src/xbt/dict.c @@ -1,8 +1,7 @@ -/* $Id$ */ +/* dict - a generic dictionary, variation over hash table */ -/* dict - a generic dictionary, variation over the B-tree concept */ - -/* Copyright (c) 2003,2004 Martin Quinson. All rights reserved. */ +/* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team. + * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ @@ -80,7 +79,9 @@ void xbt_dict_free(xbt_dict_t * dict) if (dict != NULL && *dict != NULL) { table_size = (*dict)->table_size; table = (*dict)->table; - for (i = 0; (*dict)->count && i < table_size; i++) { + /* Warning: the size of the table is 'table_size+1'... + * This is because table_size is used as a binary mask in xbt_dict_rehash */ + for (i = 0; (*dict)->count && i <= table_size; i++) { current = table[i]; while (current != NULL) { previous = current; @@ -98,7 +99,7 @@ void xbt_dict_free(xbt_dict_t * dict) /** * Returns the amount of elements in the dict */ -unsigned int xbt_dict_size(xbt_dict_t dict) +XBT_INLINE unsigned int xbt_dict_size(xbt_dict_t dict) { return dict->count; } @@ -295,7 +296,7 @@ XBT_INLINE void xbt_dict_set_ext(xbt_dict_t dict, * set the \a data in the structure under the \a key, which is a * null terminated string. */ -void xbt_dict_set(xbt_dict_t dict, +XBT_INLINE void xbt_dict_set(xbt_dict_t dict, const char *key, void *data, void_f_pvoid_t free_ctn) { @@ -312,7 +313,7 @@ void xbt_dict_set(xbt_dict_t dict, * * Search the given \a key. Throws not_found_error when not found. */ -void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len) +XBT_INLINE void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len) { @@ -339,6 +340,7 @@ void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len) */ void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len) { + unsigned int hash_code = xbt_dict_hash_ext(key, key_len); xbt_dictelm_t current; @@ -357,6 +359,28 @@ void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len) return current->content; } +/** + * @brief retrieve the key associated to that object. Warning, that's a linear search + * + * Returns NULL if the object cannot be found + */ +char *xbt_dict_get_key(xbt_dict_t dict, const void*data) { + int i; + xbt_dictelm_t current; + + + for (i = 0; i <= dict->table_size; i++) { + current = dict->table[i]; + while (current != NULL) { + if (current->content == data) + return current->key; + current = current->next; + } + } + + return NULL; +} + /** * \brief Retrieve data from the dict (null-terminated key) * @@ -368,7 +392,7 @@ void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len) * Check xbt_dict_get_or_null() for a version returning NULL without exception when * not found. */ -void *xbt_dict_get(xbt_dict_t dict, const char *key) +XBT_INLINE void *xbt_dict_get(xbt_dict_t dict, const char *key) { unsigned int hash_code = xbt_dict_hash(key); @@ -390,7 +414,7 @@ void *xbt_dict_get(xbt_dict_t dict, const char *key) /** * \brief like xbt_dict_get(), but returning NULL when not found */ -void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key) +XBT_INLINE void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key) { unsigned int hash_code = xbt_dict_hash(key); xbt_dictelm_t current; @@ -418,7 +442,7 @@ void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key) * * Remove the entry associated with the given \a key (throws not_found) */ -void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len) +XBT_INLINE void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len) { @@ -452,6 +476,8 @@ void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len) dict->count--; } + + /** * \brief Remove data from the dict (null-terminated key) * @@ -460,11 +486,124 @@ void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len) * * Remove the entry associated with the given \a key */ -void xbt_dict_remove(xbt_dict_t dict, const char *key) +XBT_INLINE void xbt_dict_remove(xbt_dict_t dict, const char *key) { xbt_dict_remove_ext(dict, key, strlen(key)); } +/** + * \brief Add data to the dict (arbitrary key) + * \param dict the container + * \param key the key to set the new data + * \param key_len the size of the \a key + * \param data the data to add in the dict + * \param free_ctn function to call with (\a key as argument) when + * \a key is removed from the dictionary + * + * Set the \a data in the structure under the \a key, which can be any kind + * of data, as long as its length is provided in \a key_len. + */ +XBT_INLINE void xbt_dicti_set(xbt_dict_t dict, + uintptr_t key, uintptr_t data) { + + unsigned int hash_code = xbt_dict_hash_ext((void*)&key, sizeof(uintptr_t)); + + xbt_dictelm_t current, previous = NULL; + xbt_assert(dict); + + DEBUG5("ADD %zu->%zu; hash = %d, size = %d, & = %d", key, data, hash_code, + dict->table_size, hash_code & dict->table_size); + current = dict->table[hash_code & dict->table_size]; + while (current != NULL && + (hash_code != current->hash_code || sizeof(uintptr_t) != current->key_len + || (((uintptr_t)key) != ((uintptr_t)current->key)) )) { + current = current->next; + } + + if (current == NULL) { + /* this key doesn't exist yet */ + current = xbt_dictielm_new(key, hash_code, data); + dict->count++; + if (previous == NULL) { + dict->table[hash_code & dict->table_size] = current; + dict->fill++; + if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT) + xbt_dict_rehash(dict); + } else { + previous->next = current; + } + } else { + + /* there is already an element with the same key: overwrite it */ + if (current->content != NULL && current->free_f != NULL) { + current->free_f(current->content); + } + current->content = (void*)data; + current->free_f = NULL; + } +} + +/** + * \brief Retrieve data from the dict (key considered as a uintptr_t) + * + * \param dict the dealer of data + * \param key the key to find data + * \return the data that we are looking for (or 0 if not found) + * + * Mixing uintptr_t keys with regular keys in the same dict is discouraged + */ +XBT_INLINE uintptr_t xbt_dicti_get(xbt_dict_t dict, uintptr_t key) { + + unsigned int hash_code = xbt_dict_hash_ext(((void*)&key), sizeof(uintptr_t)); + xbt_dictelm_t current; + + xbt_assert(dict); + + current = dict->table[hash_code & dict->table_size]; + while (current != NULL && + (hash_code != current->hash_code || sizeof(uintptr_t) != current->key_len + || (((uintptr_t)key) != ((uintptr_t)current->key)) )) { + current = current->next; + } + + if (current == NULL) + return 0; + + return (uintptr_t)(current->content); +} + +/** Remove a uintptr_t key from the dict */ +XBT_INLINE void xbt_dicti_remove(xbt_dict_t dict, uintptr_t key) { + + unsigned int hash_code = xbt_dict_hash_ext(((void*)&key), sizeof(uintptr_t)); + xbt_dictelm_t current, previous = NULL; + + + current = dict->table[hash_code & dict->table_size]; + while (current != NULL && + (hash_code != current->hash_code || sizeof(uintptr_t) != current->key_len + || (((uintptr_t)key) != ((uintptr_t)current->key)) )) { + previous = current; /* save the previous node */ + current = current->next; + } + + if (current == NULL) + THROW1(not_found_error, 0, "key %zu not found", key); + + if (previous != NULL) { + previous->next = current->next; + } else { + dict->table[hash_code & dict->table_size] = current->next; + } + + if (!dict->table[hash_code & dict->table_size]) + dict->fill--; + + xbt_dictelm_free(current); + dict->count--; +} + + /** * \brief Remove all data from the dict * \param dict the dict @@ -498,7 +637,7 @@ void xbt_dict_reset(xbt_dict_t dict) * \brief Return the number of elements in the dict. * \param dict a dictionary */ -int xbt_dict_length(xbt_dict_t dict) +XBT_INLINE int xbt_dict_length(xbt_dict_t dict) { xbt_assert(dict); @@ -790,11 +929,37 @@ static void count(xbt_dict_t dict, int length) "Announced length(%d) != %d.", xbt_dict_length(dict), length); + xbt_dict_foreach(dict, cursor, key, data) + effective++; + + xbt_test_assert2(effective == length, "Effective length(%d) != %d.", + effective, length); + +} + +static void count_check_get_key(xbt_dict_t dict, int length) +{ + xbt_dict_cursor_t cursor; + char *key,*key2; + void *data; + int effective = 0; + + + xbt_test_add1("Count elements (expecting %d), and test the getkey function", length); + xbt_test_assert2(xbt_dict_length(dict) == length, + "Announced length(%d) != %d.", xbt_dict_length(dict), + length); + xbt_dict_foreach(dict, cursor, key, data) { effective++; + key2 = xbt_dict_get_key(dict,data); + xbt_assert2(!strcmp(key,key2), + "The data was registered under %s instead of %s as expected",key2,key); } + xbt_test_assert2(effective == length, "Effective length(%d) != %d.", effective, length); + } xbt_ex_t e; @@ -802,8 +967,7 @@ xbt_dict_t head = NULL; char *data; -XBT_TEST_UNIT("basic", test_dict_basic, - "Basic usage: change, retrieve, traverse") +XBT_TEST_UNIT("basic", test_dict_basic,"Basic usage: change, retrieve, traverse") { xbt_test_add0("Traversal the null dictionary"); traverse(head); @@ -822,7 +986,7 @@ XBT_TEST_UNIT("basic", test_dict_basic, xbt_test_add0("Traverse the full dictionary"); fill(&head); - count(head, 7); + count_check_get_key(head, 7); debuged_add_ext(head, "toto", "tutu"); search_ext(head, "toto", "tutu"); @@ -837,22 +1001,22 @@ XBT_TEST_UNIT("basic", test_dict_basic, /* CHANGING */ fill(&head); - count(head, 7); + count_check_get_key(head, 7); xbt_test_add0("Change 123 to 'Changed 123'"); xbt_dict_set(head, "123", strdup("Changed 123"), &free); - count(head, 7); + count_check_get_key(head, 7); xbt_test_add0("Change 123 back to '123'"); xbt_dict_set(head, "123", strdup("123"), &free); - count(head, 7); + count_check_get_key(head, 7); xbt_test_add0("Change 12a to 'Dummy 12a'"); xbt_dict_set(head, "12a", strdup("Dummy 12a"), &free); - count(head, 7); + count_check_get_key(head, 7); xbt_test_add0("Change 12a to '12a'"); xbt_dict_set(head, "12a", strdup("12a"), &free); - count(head, 7); + count_check_get_key(head, 7); xbt_test_add0("Traverse the resulting dictionary"); traverse(head); @@ -986,6 +1150,45 @@ XBT_TEST_UNIT("nulldata", test_dict_nulldata, "NULL data management") xbt_dict_free(&head); } +static void debuged_addi(xbt_dict_t head, uintptr_t key, uintptr_t data) { + xbt_test_log2("Add %zu under %zu", data, key); + + xbt_dicti_set(head, key, data); + if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) { + xbt_dict_dump(head, (void (*)(void *)) &printf); + fflush(stdout); + } + uintptr_t stored_data = xbt_dicti_get(head, key); + xbt_test_assert3(stored_data==data, + "Retrieved data (%zu) is not what I just stored (%zu) under key %zu",stored_data,data,key); +} + +XBT_TEST_UNIT("dicti", test_dict_scalar, "Scalar data and key management") +{ + xbt_test_add0("Fill in the dictionnary"); + + head = xbt_dict_new(); + debuged_addi(head, 12, 12); + debuged_addi(head, 13, 13); + debuged_addi(head, 14, 14); + debuged_addi(head, 15, 15); + /* Change values */ + debuged_addi(head, 12, 15); + debuged_addi(head, 15, 2000); + debuged_addi(head, 15, 3000); + /* 0 as key */ + debuged_addi(head, 0, 1000); + debuged_addi(head, 0, 2000); + debuged_addi(head, 0, 3000); + /* 0 as value */ + debuged_addi(head, 12, 0); + debuged_addi(head, 13, 0); + debuged_addi(head, 12, 0); + debuged_addi(head, 0, 0); + + xbt_dict_free(&head); +} + #define NB_ELM 20000 #define SIZEOFKEY 1024 static int countelems(xbt_dict_t head)