From: thiery Date: Thu, 3 Aug 2006 08:38:53 +0000 (+0000) Subject: Reimplement dictionaries as hashtables X-Git-Tag: v3.3~2676 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/43e9ac12ea9282621bfaed783cb4c96847e9406b?ds=sidebyside Reimplement dictionaries as hashtables git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@2683 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- diff --git a/include/xbt/dict.h b/include/xbt/dict.h index 686f396987..017d985b58 100644 --- a/include/xbt/dict.h +++ b/include/xbt/dict.h @@ -20,9 +20,8 @@ SG_BEGIN_DECL() * @brief The dictionnary data structure (comparable to hash tables) * * This section describes the API to a dictionnary structure that - * associates as string to a void* key. Even if it provides the same - * functionnality than an hash table, the implementation differs and the - * internal data-structure rather looks like a tree. + * associates as string to a void* key. It provides the same + * functionnality than an hash table. * * Here is a little example of use: * \verbatim xbt_dict_t mydict = xbt_dict_new(); @@ -46,7 +45,9 @@ SG_BEGIN_DECL() /** \brief Dictionnary data type (opaque structure) */ typedef struct xbt_dict_ *xbt_dict_t; xbt_dict_t xbt_dict_new(void); + xbt_dict_t xbt_dict_new_ext(int hashsize); void xbt_dict_free(xbt_dict_t *dict); + void xbt_dict_hashsize_set(xbt_dict_t dict, int hashsize); /** @} */ /** @defgroup XBT_dict_basic Dictionnaries basic usage diff --git a/src/xbt/dict.c b/src/xbt/dict.c index 8810081a5f..e69810ae40 100644 --- a/src/xbt/dict.c +++ b/src/xbt/dict.c @@ -7,45 +7,115 @@ /* 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. */ +#include #include "xbt/ex.h" +#include "xbt/log.h" #include "dict_private.h" -XBT_LOG_NEW_SUBCATEGORY(xbt_dict,xbt, +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict,xbt, "Dictionaries provide the same functionnalities than hash tables"); /*####[ Private prototypes ]#################################################*/ /*####[ Code ]###############################################################*/ /** - * @brief Constructor - * @return pointer to the destination + * \brief Constructor + * \return pointer to the destination + * \see xbt_dict_new_ext(), xbt_dict_free() * - * Creates and initialize a new dictionnary + * Creates and initialize a new dictionnary with a default hashtable size. */ -xbt_dict_t -xbt_dict_new(void) { - xbt_dict_t res= xbt_new(s_xbt_dict_t,1); - res->head=NULL; - return res; +xbt_dict_t xbt_dict_new(void) { + return xbt_dict_new_ext(256); +} + +/** + * \brief Create a new dictionary with the specified hashtable size + * \param hashsize the hashtable size + * \return a pointer to the created object + * \see xbt_dict_new(), xbt_dict_free() + */ +xbt_dict_t xbt_dict_new_ext(int hashsize) { + int i; + xbt_dict_t dict = xbt_new0(s_xbt_dict_t, 1); + dict->table_size = hashsize; + dict->table = xbt_new0(xbt_dictelm_t, dict->table_size); + + for (i = 0; i < hashsize; i++) { + dict->table[i] = NULL; + } + + return dict; } + /** - * @brief Destructor - * @param dict the dictionnary to be freed + * \brief Destructor + * \param dict the dictionnary to be freed * - * Frees a cache structure with all its childs. + * Frees a dictionary with all the data */ -void -xbt_dict_free(xbt_dict_t *dict) { - if (dict && *dict) { - if ((*dict)->head) { - xbt_dictelm_free( &( (*dict)->head ) ); - (*dict)->head = NULL; +void xbt_dict_free(xbt_dict_t *dict) { + int i; + xbt_dictelm_t current, previous; + if (dict != NULL && *dict != NULL) { + for (i = 0; i < (*dict)->table_size; i++) { + current = (*dict)->table[i]; + while (current != NULL) { + previous = current; + current = current->next; + xbt_dictelm_free(previous); + } } - free(*dict); - *dict=NULL; + xbt_free((*dict)->table); + xbt_free(*dict); + *dict = NULL; } } +/** + * \brief Change the hashtable size + * \param dict a dictionary + * \param hashsize the new hashtable size + * + * Change the hashtable size is a long operation, so it's better + * to use xbt_dict_new_ext or to call xbt_dict_hashsize_set when + * the dictionary is empty. + */ +void xbt_dict_hashsize_set(xbt_dict_t dict, int hashsize) { + xbt_dict_t new_dict = xbt_dict_new_ext(hashsize); + xbt_dictelm_t element, next; + int i; + + for (i = 0; i < dict->table_size; i++) { + element = dict->table[i]; + while (element != NULL) { + next = element->next; /* save the next because it will be lost */ + xbt_dict_add_element(new_dict, element); /* no new xbt_dictelm_t is mallocated */ + element = next; + } + } + + xbt_free(dict->table); + dict->table = new_dict->table; + dict->table_size = hashsize; + xbt_free(new_dict); +} + +/** + * Returns the hash code of a string. + */ +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 */ + } + + return hash; +} + /** * \brief Add data to the dict (arbitrary key) * \param dict the container @@ -55,20 +125,44 @@ xbt_dict_free(xbt_dict_t *dict) { * \param free_ctn function to call with (\a key as argument) when * \a key is removed from the dictionnary * - * set the \a data in the structure under the \a key, which can be any kind + * 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. */ -void -xbt_dict_set_ext(xbt_dict_t dict, - const char *key, - int key_len, - void *data, - void_f_pvoid_t *free_ctn) { - +void xbt_dict_set_ext(xbt_dict_t dict, + const char *key, + int key_len, + void *data, + void_f_pvoid_t *free_ctn) { xbt_assert(dict); - xbt_dictelm_set_ext(&(dict->head), - key, key_len, data, free_ctn); + unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + xbt_dictelm_t current, previous = NULL; + + current = dict->table[hash_code]; + while (current != NULL && + (key_len != current->key_len || strncmp(key, current->key, key_len))) { + previous = current; + current = current->next; + } + + if (current == NULL) { + /* this key doesn't exist yet */ + current = xbt_dictelm_new(key, key_len, data, free_ctn, NULL); + if (previous == NULL) { + dict->table[hash_code] = current; + } + else { + previous->next = current; + } + } + else { + /* there is already an element with the same key: we overwrite it */ + if (current->content != NULL && current->free_f != NULL) { + current->free_f(current->content); + } + current->content = data; + current->free_f = free_ctn; + } } /** @@ -83,15 +177,14 @@ 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, - const char *key, - void *data, - void_f_pvoid_t *free_ctn) { +void xbt_dict_set(xbt_dict_t dict, + const char *key, + void *data, + void_f_pvoid_t *free_ctn) { xbt_assert(dict); - xbt_dictelm_set(&(dict->head), key, data, free_ctn); + xbt_dict_set_ext(dict, key, strlen(key), data, free_ctn); } /** @@ -100,18 +193,29 @@ xbt_dict_set(xbt_dict_t dict, * \param dict the dealer of data * \param key the key to find data * \param key_len the size of the \a key - * \returns the data that we are looking for + * \return the data that we are looking for * - * Search the given \a key. throws not_found_error when not found. + * 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) { - +void *xbt_dict_get_ext(xbt_dict_t dict, + const char *key, + int key_len) { xbt_assert(dict); - return xbt_dictelm_get_ext(dict->head, key, key_len); + unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + xbt_dictelm_t current; + + current = dict->table[hash_code]; + while (current != NULL && + (key_len != current->key_len || strncmp(key, current->key, key_len))) { + current = current->next; + } + + if (current == NULL) { + THROW2(not_found_error, 0, "key %.*s not found", key_len, key); + } + + return current->content; } /** @@ -119,37 +223,35 @@ xbt_dict_get_ext(xbt_dict_t dict, * * \param dict the dealer of data * \param key the key to find data - * \returns the data that we are looking for + * \return the data that we are looking for * - * Search the given \a key. THROWs mismatch_error when not found. + * Search the given \a key. Throws not_found_error when not found. * 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) { +void *xbt_dict_get(xbt_dict_t dict, + const char *key) { xbt_assert(dict); - return xbt_dictelm_get(dict->head, key); + return xbt_dict_get_ext(dict, key, strlen(key)); } /** * \brief like xbt_dict_get(), but returning NULL when not found */ -void * -xbt_dict_get_or_null(xbt_dict_t dict, +void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key) { xbt_ex_t e; - void *res=NULL; + void *result = NULL; TRY { - res = xbt_dictelm_get(dict->head, key); + result = xbt_dict_get(dict, key); } CATCH(e) { if (e.category != not_found_error) RETHROW; xbt_ex_free(e); - res=NULL; + result = NULL; } - return res; + return result; } @@ -159,17 +261,37 @@ xbt_dict_get_or_null(xbt_dict_t dict, * \param dict the trash can * \param key the key of the data to be removed * \param key_len the size of the \a 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) { +void xbt_dict_remove_ext(xbt_dict_t dict, + const char *key, + int key_len) { xbt_assert(dict); - - xbt_dictelm_remove_ext(dict->head, key, key_len); + + unsigned int hash_code = xbt_dict_hash(key) % dict->table_size; + xbt_dictelm_t current, previous = NULL; + + current = dict->table[hash_code]; + while (current != NULL && + (key_len != current->key_len || strncmp(key, current->key, key_len))) { + previous = current; /* save the previous node */ + current = current->next; + } + + if (current == NULL) { + THROW2(not_found_error, 0, "key %.*s not found", key_len, key); + } + + if (previous != NULL) { + xbt_assert0(previous->next == current, "previous-next != current"); + previous->next = current->next; + } + else { + dict->table[hash_code] = current->next; + } + + xbt_dictelm_free(current); } /** @@ -180,15 +302,24 @@ xbt_dict_remove_ext(xbt_dict_t dict, * * Remove the entry associated with the given \a key */ -void -xbt_dict_remove(xbt_dict_t dict, - const char *key) { +void xbt_dict_remove(xbt_dict_t dict, + const char *key) { if (!dict) - THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key); + THROW1(arg_error, 0, "Asked to remove key %s from NULL dict", key); - xbt_dictelm_remove(dict->head, key); + xbt_dict_remove_ext(dict, key, strlen(key)); } +/* + * 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; + element->next = dict->table[hashcode]; + dict->table[hashcode] = element; +} /** * \brief Outputs the content of the structure (debuging purpose) @@ -197,15 +328,27 @@ xbt_dict_remove(xbt_dict_t dict, * \param output a function to dump each data in the tree * * Ouputs the content of the structure. (for debuging purpose). \a ouput is a - * function to output the data. If NULL, data won't be displayed, just the tree structure. + * function to output the data. If NULL, data won't be displayed. */ -void -xbt_dict_dump(xbt_dict_t dict, - void_f_pvoid_t *output) { - - printf("Dict %p:\n", (void*)dict); - xbt_dictelm_dump(dict ? dict->head: NULL, output); +void xbt_dict_dump(xbt_dict_t dict, + void_f_pvoid_t *output) { + int i; + xbt_dictelm_t element; + printf("Dict %p:\n", dict); + if (dict != NULL) { + for (i = 0; i < dict->table_size; i++) { + element = dict->table[i]; + while (element != NULL) { + printf("%s -> ", element->key); + if (output != NULL) { + output(element->content); + } + printf("\n"); + element = element->next; + } + } + } } #ifdef SIMGRID_TEST @@ -248,7 +391,6 @@ static void fill(xbt_dict_t *head) { debuged_add(*head,"1234"); /* Need of common ancestor */ debuged_add(*head,"123457"); - } static void search(xbt_dict_t head,const char*key) { @@ -302,7 +444,6 @@ char *data; XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrieve, traverse"){ - xbt_test_add0("Traversal the empty dictionnary"); traverse(head); @@ -428,7 +569,7 @@ XBT_TEST_UNIT("nulldata",test_dict_nulldata,"NULL data management"){ xbt_dict_cursor_t cursor=NULL; char *key; int found=0; - + xbt_dict_foreach(head,cursor,key,data) { xbt_test_log2("Seen: %s->%s",PRINTF_STR(key),PRINTF_STR(data)); if (!strcmp(key,"null")) diff --git a/src/xbt/dict_cursor.c b/src/xbt/dict_cursor.c index ee1bfb44de..1110af7516 100644 --- a/src/xbt/dict_cursor.c +++ b/src/xbt/dict_cursor.c @@ -22,34 +22,22 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict_cursor,xbt_dict,"To traverse dictionari /* Don't add or remove entries to the dict while traversing !!! */ /*###########################################################################*/ struct xbt_dict_cursor_ { - /* we store all level encountered until here, to backtrack on next() */ - xbt_dynar_t keys; - xbt_dynar_t key_lens; - int pos; - int pos_len; - xbt_dictelm_t head; + xbt_dictelm_t current; + int line; + xbt_dict_t dict; }; -static _XBT_INLINE void -_cursor_push_keys(xbt_dict_cursor_t p_cursor, - xbt_dictelm_t p_elm); - #undef xbt_dict_CURSOR_DEBUG /*#define xbt_dict_CURSOR_DEBUG 1*/ /** @brief Creator - * @param head the dict + * @param dict the dict */ -xbt_dict_cursor_t -xbt_dict_cursor_new(const xbt_dict_t head) { +xbt_dict_cursor_t xbt_dict_cursor_new(const xbt_dict_t dict) { xbt_dict_cursor_t res = NULL; - res = xbt_new(s_xbt_dict_cursor_t,1); - res->keys = xbt_dynar_new(sizeof(char **), NULL); - res->key_lens = xbt_dynar_new(sizeof(int *), NULL); - res->pos = 0; - res->pos_len = 0; - res->head = head ? head->head : NULL; + res = xbt_new(s_xbt_dict_cursor_t, 1); + res->dict = dict; xbt_dict_cursor_rewind(res); @@ -60,12 +48,9 @@ xbt_dict_cursor_new(const xbt_dict_t head) { * @brief Destructor * @param cursor poor victim */ -void -xbt_dict_cursor_free(xbt_dict_cursor_t *cursor) { +void xbt_dict_cursor_free(xbt_dict_cursor_t *cursor) { if (*cursor) { - xbt_dynar_free(&((*cursor)->keys)); - xbt_dynar_free(&((*cursor)->key_lens)); - free(*cursor); + xbt_free(*cursor); *cursor = NULL; } } @@ -73,59 +58,23 @@ xbt_dict_cursor_free(xbt_dict_cursor_t *cursor) { /* * Sanity check to see if the head contains something */ -static _XBT_INLINE -void -__cursor_not_null(xbt_dict_cursor_t cursor) { - +static _XBT_INLINE void __cursor_not_null(xbt_dict_cursor_t cursor) { xbt_assert0(cursor, "Null cursor"); - - if (!cursor->head) - THROW0(arg_error,0,"Null headed cursor"); } -static _XBT_INLINE -void -_cursor_push_keys(xbt_dict_cursor_t cursor, - xbt_dictelm_t elm) { - xbt_dictelm_t child = NULL; - int i = 0; - static volatile int count = 0; /* ??? */ - - CDEBUG3(xbt_dict_cursor, "Push childs of %p (%.*s) in the cursor", (void*)elm, elm->key_len, elm->key); - - if (!elm->internal) { - xbt_dynar_push(cursor->keys, &elm->key ); - xbt_dynar_push(cursor->key_lens, &elm->key_len); - count++; - } - - xbt_dynar_foreach(elm->sub, i, child) { - if (child) - _cursor_push_keys(cursor, child); - } - - CDEBUG1(xbt_dict_cursor, "Count = %d", count); -} - /** @brief Reinitialize the cursor. Mandatory after removal or add in dict. */ -void -xbt_dict_cursor_rewind(xbt_dict_cursor_t cursor) { - +void xbt_dict_cursor_rewind(xbt_dict_cursor_t cursor) { CDEBUG0(xbt_dict_cursor, "xbt_dict_cursor_rewind"); xbt_assert(cursor); - xbt_dynar_reset(cursor->keys); - xbt_dynar_reset(cursor->key_lens); - - if (!cursor->head) - return ; - - _cursor_push_keys(cursor, cursor->head); - - xbt_dynar_cursor_first(cursor->keys, &cursor->pos ); - xbt_dynar_cursor_first(cursor->key_lens, &cursor->pos_len); - + cursor->line = 0; + if (cursor->dict != NULL) { + cursor->current = cursor->dict->table[0]; + } + else { + cursor->current = NULL; + } } /** @@ -134,30 +83,50 @@ xbt_dict_cursor_rewind(xbt_dict_cursor_t cursor) { * @param dict on what to let the cursor iterate * @param[out] cursor dest address */ -void xbt_dict_cursor_first (const xbt_dict_t dict, - xbt_dict_cursor_t *cursor){ - +void xbt_dict_cursor_first(const xbt_dict_t dict, + xbt_dict_cursor_t *cursor){ + DEBUG0("xbt_dict_cursor_first"); if (!*cursor) { DEBUG0("Create the cursor on first use"); - *cursor=xbt_dict_cursor_new(dict); + *cursor = xbt_dict_cursor_new(dict); + } + else { + xbt_dict_cursor_rewind(*cursor); + } + if (dict != NULL && (*cursor)->current == NULL) { + xbt_dict_cursor_step(*cursor); /* find the first element */ } - - xbt_dict_cursor_rewind(*cursor); } /** * \brief Move to the next element. */ -void -xbt_dict_cursor_step(xbt_dict_cursor_t cursor) { +void xbt_dict_cursor_step(xbt_dict_cursor_t cursor) { + DEBUG0("xbt_dict_cursor_step"); xbt_assert(cursor); - DEBUG2("step cursor. Current=%.*s", - xbt_dynar_get_as(cursor->key_lens,cursor->pos_len,int), - xbt_dynar_get_as(cursor->keys,cursor->pos,char *)); - xbt_dynar_cursor_step(cursor->keys, &cursor->pos); - xbt_dynar_cursor_step(cursor->key_lens, &cursor->pos_len); + xbt_dictelm_t current = cursor->current; + int line = cursor->line; + + if (cursor->dict != NULL) { + + if (current != NULL) { + DEBUG0("current is not null, take the next element"); + current = current->next; + DEBUG1("next element: %p", current); + } + + while (current == NULL && ++line < cursor->dict->table_size) { + DEBUG0("current is NULL, take the next line"); + current = cursor->dict->table[line]; + DEBUG1("element in the next line: %p", current); + } + DEBUG2("search finished, current = %p, line = %d", current, line); + + cursor->current = current; + cursor->line = line; + } } /** @@ -165,34 +134,24 @@ xbt_dict_cursor_step(xbt_dict_cursor_t cursor) { * * @returns true if it's ok, false if there is no more data */ -int -xbt_dict_cursor_get_or_free(xbt_dict_cursor_t *cursor, - char **key, - void **data) { - int key_len = 0; - xbt_ex_t e; - +int xbt_dict_cursor_get_or_free(xbt_dict_cursor_t *cursor, + char **key, + void **data) { + DEBUG0("xbt_dict_get_or_free"); + + xbt_dictelm_t current; + if (!cursor || !(*cursor)) return FALSE; - if (xbt_dynar_length((*cursor)->keys) <= (*cursor)->pos) { + current = (*cursor)->current; + if (current == NULL) { /* no data left */ xbt_dict_cursor_free(cursor); return FALSE; } - - *key = xbt_dynar_get_as((*cursor)->keys, (*cursor)->pos, char*); - key_len = xbt_dynar_get_as((*cursor)->key_lens, (*cursor)->pos_len, int); - - TRY { - *data = xbt_dictelm_get_ext((*cursor)->head, *key, key_len); - } CATCH(e) { - if (e.category == mismatch_error) { - xbt_dict_cursor_free(cursor); - xbt_ex_free(e); - return FALSE; - } - RETHROW; - } + + *key = current->key; + *data = current->content; return TRUE; } @@ -201,11 +160,10 @@ xbt_dict_cursor_get_or_free(xbt_dict_cursor_t *cursor, * @param cursor: the cursor * @returns the current key */ -char * -xbt_dict_cursor_get_key(xbt_dict_cursor_t cursor) { +char *xbt_dict_cursor_get_key(xbt_dict_cursor_t cursor) { __cursor_not_null(cursor); - return xbt_dynar_get_as(cursor->keys, cursor->pos - 1, char*); + return cursor->current->key; } /** @@ -213,17 +171,10 @@ xbt_dict_cursor_get_key(xbt_dict_cursor_t cursor) { * @param cursor the cursor * @returns the current data */ -void * -xbt_dict_cursor_get_data(xbt_dict_cursor_t cursor) { - char *key = NULL; - int key_len = 0; - +void *xbt_dict_cursor_get_data(xbt_dict_cursor_t cursor) { __cursor_not_null(cursor); - key = xbt_dynar_get_as(cursor->keys, cursor->pos-1, char *); - key_len = xbt_dynar_get_as(cursor->key_lens, cursor->pos_len-1, int); - - return xbt_dictelm_get_ext(cursor->head, key, key_len); + return cursor->current->content; } diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c index eaa1c3ac77..1db002921e 100644 --- a/src/xbt/dict_elm.c +++ b/src/xbt/dict_elm.c @@ -7,8 +7,6 @@ /* 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. */ -#include "xbt/ex.h" -#include "portable.h" /* PRINTF_STR */ #include "dict_private.h" /* prototypes of this module */ XBT_LOG_EXTERNAL_CATEGORY(xbt_dict); @@ -19,976 +17,32 @@ XBT_LOG_NEW_SUBCATEGORY(xbt_dict_search,xbt_dict,"Dictionaries internals: search XBT_LOG_NEW_SUBCATEGORY(xbt_dict_remove,xbt_dict,"Dictionaries internals: elements removal"); XBT_LOG_NEW_SUBCATEGORY(xbt_dict_collapse,xbt_dict,"Dictionaries internals: post-removal cleanup"); -/*####[ Private prototypes ]#################################################*/ - -static _XBT_INLINE void _xbt_dictelm_alloc(char *key, - int offset, - int key_len, - int internal, - void *data, - void_f_pvoid_t *free_f, - /*OUT*/s_xbt_dictelm_t **where); -static void _dictelm_wrapper_free(void*); - -static _XBT_INLINE void _str_prefix_lgr(const char *key1, - int key_len1, - const char *key2, - int key_len2, - int *offset, - int *match); - - -static void _xbt_dictelm_dump_rec(s_xbt_dictelm_t *head, - int offset, - void_f_pvoid_t *output); - - - -static void _xbt_dictelm_set_rec(s_xbt_dictelm_t *head, - char *key, - int key_len, - int offset, - void *data, - void_f_pvoid_t *free_f); -static void * _xbt_dictelm_get_rec(s_xbt_dictelm_t *head, - const char *key, - int key_len, - int offset); -static void _xbt_dictelm_remove_rec(s_xbt_dictelm_t *head, - const char *key, - int key_len, - int offset); - -static _XBT_INLINE -void -_collapse_if_need(s_xbt_dictelm_t *p_head, - int pos, - int offset); - -/* ---- */ - -/* - * _xbt_nibble_to_char: - * - * Change any byte to a printable char - */ - -static _XBT_INLINE -char -_xbt_nibble_to_char(unsigned char c) { - c &= 0x0f; - return c>9 ? c-10+'a' : c + '0'; -} - -/* - * _xbt_bytes_to_string: - * - * Change any byte array to a printable string - * The length of string_container should at least be data_len*2+1 - */ -static _XBT_INLINE -char * -_xbt_bytes_to_string(char * const ptr, - int data_len, - char * const string_container) { - unsigned char *src = (unsigned char *)ptr; - char *dst = string_container; - - while (data_len--) { - *dst++ = _xbt_nibble_to_char(*src & 0x0f ); - *dst++ = _xbt_nibble_to_char(*src++ & 0xf0 >> 4); - } - - *dst = 0; - - return ptr; -} - -/* ---- */ - -/* - * _xbt_dictelm_alloc: - * - * Alloc a dict element with no child. - */ -static _XBT_INLINE -void -_xbt_dictelm_alloc(char *key, - int key_len, - int offset, - int internal, - void *data, - void_f_pvoid_t *free_f, - /*OUT*/s_xbt_dictelm_t **pp_elm) { - s_xbt_dictelm_t *p_elm = NULL; - - p_elm = xbt_new(s_xbt_dictelm_t,1); - - p_elm->key = key; - p_elm->key_len = key_len; - p_elm->offset = offset; - p_elm->internal = internal; - p_elm->content = data; - p_elm->free_f = free_f; - p_elm->sub = xbt_dynar_new(sizeof(s_xbt_dictelm_t*), _dictelm_wrapper_free); - - *pp_elm = p_elm; - -} - -/** - * xbt_dictelm_free: - * - * @pp_elm: the dict elem to be freed - * - * Frees a dictionnary element with all its childs. - */ -void -xbt_dictelm_free(s_xbt_dictelm_t **pp_elm) { - if (*pp_elm) { - s_xbt_dictelm_t *p_elm = *pp_elm; - - xbt_dynar_free(&(p_elm->sub)); - - if (p_elm->key) { - free(p_elm->key); - } - - if (p_elm->free_f && p_elm->content) { - p_elm->free_f(p_elm->content); - } - - free(p_elm); - *pp_elm = NULL; - } -} - -/** - * _dictelm_wrapper_free: - * - * a wrapper to free dictelm with the right prototype to be usable within dynar - */ -static -void -_dictelm_wrapper_free(void *pp_elm) { - DEBUG3("Free dictelm '%.*s' %p", - (*(s_xbt_dictelm_t**)pp_elm)->key_len, (*(s_xbt_dictelm_t**)pp_elm)->key, - *(void**)pp_elm); - xbt_dictelm_free((s_xbt_dictelm_t**)pp_elm); -} - -/*####[ utility functions ]##################################################*/ -/** - * _str_prefix_lgr: - * - * - * Returns the length of the common prefix of @str1 and @str2. - * Do make sure the strings are not null, this function don't - */ -static _XBT_INLINE -void -_str_prefix_lgr(const char *key1, - int key_len1, - const char *key2, - int key_len2, - int *p_offset, - int *p_match) { - const int old_offset = *p_offset; - int o = *p_offset; - int m = *p_match; - - m = 0; - - /*CDEBUG5(dict_search, "%s: [%.*s] <=> [%.*s]", __FUNCTION__, - key1,key_len1,key2,key_len2);*/ - - if (o < key_len1 && o < key_len2) { - - while (key1[o] == key2[o]) { - o++; - - if (!(o < key_len1 && o < key_len2)) - break; - - } - - } - - - if (o != old_offset) { - - if (o >= key_len1) { - - if (o >= key_len2) { - m = 1; /* exact match */ - } else { - m = 2; /* child is prefix */ - } - - } else if (o >= key_len2) { - m = 3; /* key prefix of child */ - } else { - DEBUG7("Common prefix. o=%d; key1=%.*s; key_len1=%d; key2=%.*s; key_len2=%d", - o, - key_len1, key1, - key_len1, - key_len2, key2, - key_len2); - m = 4; /* Common prefix (=> common ancestor) */ - } - } - - - *p_offset = o; - *p_match = m; -} - -/** - * _dictelm_child_cmp: - * - * Compares two dictelm keys and return their matching (using the same - * convention than @_xbt_dict_child_search() ) - */ -static _XBT_INLINE -void -_dict_child_cmp(s_xbt_dictelm_t *p_dict, - int pos, - const char *key, - const int key_len, - int *p_offset, - int *p_match, - int *p_cmp) { - s_xbt_dictelm_t *p_child = NULL; - int cmp = 0; - int o = *p_offset; - int m = *p_match; - - p_child = xbt_dynar_get_as(p_dict->sub, pos, s_xbt_dictelm_t*); - - /* Compute the length of the prefix - and if the searched key is before or after cur */ - _str_prefix_lgr(p_child->key, p_child->key_len, - key, key_len, - &o, &m); - - - if (m) /* found, get out */ - goto end; - - if (o < p_child->key_len && (o >= key_len || key[o] < p_child->key[o])) { - cmp = -1; - } else { - cmp = 1; - } - - CDEBUG6(xbt_dict_search, "Cmp '%.*s' and '%.*s' (offset=%d) => %d", - p_child->key_len - *p_offset, p_child->key + *p_offset, - key_len - *p_offset, key + *p_offset, - *p_offset,cmp); - - end: - *p_offset = o; - *p_match = m; - *p_cmp = cmp; -} - -/** - * _xbt_dict_child_search: - * - * Search where would be inserted @key between the childs of @p_elm. - * - * Returns position of the child having a common prefix with this key - * If *match==0, no child have a common prefix - * *pos is where to add the key - * If *match==1, A child (located at *pos) have exactly this key - * If *match==2, A child (located at *pos) constitutes a prefix of the key - * the recursion have to go on that guy - * *prefix = the size of the key eaten at this level - * If *match==3 The key is a prefix of the child at *pos - * If *match==4, A child (loc. at *pos) share a common prefix with this key - * *prefix = size of the prefix. - * If searching, that's a mismatch. - * If inserting, you have to break the child and create an - * internal node having {child, key} as childs - * offset is used in input and output. In input, that's the length of the key - * handled by previous levels of recursion. In output, that the one counting - * also this level. - */ -static _XBT_INLINE -void -_xbt_dictelm_child_search(s_xbt_dictelm_t *p_elm, - const char *key, - int key_len, - int *p_pos, - int *p_offset, - int *p_match) { - - int p = 0; - int o = *p_offset; - int m = 0; - int len = 0; - - - CDEBUG6(xbt_dict_search, "search child [%.*s] under [%.*s]=%p (len=%lu)", - key_len, key, - p_elm ? (p_elm->key_len?p_elm->key_len:6) : 6, - p_elm ? PRINTF_STR(p_elm->key) : "(head)", - p_elm, - (p_elm&&p_elm->sub) ? xbt_dynar_length(p_elm->sub) : 0); +xbt_dictelm_t xbt_dictelm_new(const char *key, + int key_len, + void *content, + void_f_pvoid_t free_f, + xbt_dictelm_t next) { + xbt_dictelm_t element = xbt_new0(s_xbt_dictelm_t, 1); + element->key = xbt_new0(char, key_len + 1); + strncpy(element->key, key, key_len); - len = xbt_dynar_length(p_elm->sub); - - { - int p_min = 0; - int p_max = len-1; - int cmp = 0; - - p = p_min; - if(len==0) { - p=0; - } else { - _dict_child_cmp(p_elm, p_min, key, key_len, &o, &m, &cmp); - if(!m) { /* OK, maybe it is somewhere else. */ - o = *p_offset; - if (cmp<0) { /* Insert at the very beginning */ - p=0; - } else if (p_max<=0) { /* No way. It is not there. Insert at the very end */ - p=p_max+1; - m = 0; - } else { - p=p_max; - _dict_child_cmp(p_elm, p_max, key, key_len, &o, &m, &cmp); - if(!m) { - o = *p_offset; - if(cmp>0) { /* Should be located at the end of the table */ - p=p_max+1; - } else { /* Too bad, let's go for a dichotomic search. */ - while(p_max-p_min>1) { - _dict_child_cmp(p_elm, (p_min+p_max)/2, key, key_len, &o, &m, &cmp); - if(m) break; - o = *p_offset; - if(cmp<0) p_max=(p_min+p_max)/2; - if(cmp>0) p_min=(p_min+p_max)/2; - } - if(m) /* We have the element */ - p=(p_min+p_max)/2 ; - else /* it should be inserted just after p_min */ - p=p_min + 1; - } - } - } - } - } - } - - *p_offset = o; - *p_pos = p; - *p_match = m; - CDEBUG6(xbt_dict_search, "search [%.*s] in [%.*s]=%p => %s", - key_len, key, - p_elm?(p_elm->key_len?p_elm->key_len:6):6, p_elm?PRINTF_STR(p_elm->key):"(head)", - p_elm, - ( m == 0 ? "no child have a common prefix" : - ( m == 1 ? "selected child have exactly this key" : - ( m == 2 ? "selected child constitutes a prefix" : - ( m == 3 ? "key is a prefix of selected child" : - (m == 4 ? "selected child share a prefix" : - "internal error"))))) - ); -} - -/** - * _xbt_dictelm_change_value: - * - * Change the value of the dictelm, making sure to free the old one, if any. The node also become a non-internal one. - */ -static _XBT_INLINE -void -_xbt_dictelm_change_value(s_xbt_dictelm_t *p_elm, - void *data, - void_f_pvoid_t *free_f) { - - if (p_elm->content && p_elm->free_f) { - p_elm->free_f(p_elm->content); - } - - p_elm->free_f = free_f; - p_elm->content = data; - p_elm->internal = FALSE; -} - -/** - * _xbt_dictelm_set_rec: - * - * @head: the head of the dict - * @key: the key to set the new data - * @offset: offset on key. - * @data: the data to add in the dict - * - * set the @data in the structure under the @key. The @key is destroyed - * in the process. Think to strdup it before. - * - * This is a helper function to xbt_dict_set which locks the struct and - * strdup the key before action. - */ -void -_xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, - char *key, - int key_len, - int offset, - void *data, - void_f_pvoid_t *free_f) { - int match = 0; - int pos = 0; - const int old_offset = offset; - - CDEBUG6(xbt_dict_add, "--> Insert '%.*s' after '%.*s' (offset=%d) in tree %p", - key_len, key, - ((p_head && p_head->key) ? p_head->key_len : 6), - ((p_head && p_head->key) ? p_head->key : "(head)"), - offset, (void*)p_head); - - /*** The trivial cases first ***/ - - /* there is no key (we did enough recursion), change the value of head */ - if (offset >= key_len) { - - CDEBUG0(xbt_dict_add, "--> Change the value of head"); - - _xbt_dictelm_change_value(p_head, data, free_f); - free(key); /* Keep the key used in the tree */ - - return; - } - - /*** Search where to add this child, and how ***/ - _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match); - - CDEBUG3(xbt_dict_add, "child_search => pos=%d, offset=%d, match=%d", - pos, offset, match); - - switch (match) { - - case 0: /* no child have a common prefix */ - { - s_xbt_dictelm_t *p_child = NULL; - - _xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_child); - CDEBUG1(xbt_dict_add, "-> Add a child %p", (void*)p_child); - xbt_dynar_insert_at(p_head->sub, pos, &p_child); - - return; - } - - case 1: /* A child have exactly this key => change its value*/ - { - s_xbt_dictelm_t *p_child = NULL; - - p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - CDEBUG1(xbt_dict_add, "-> Change the value of the child %p", (void*)p_child); - _xbt_dictelm_change_value(p_child, data, free_f); - - free(key); - - return; - } - - case 2: /* A child constitutes a prefix of the key => recurse */ - { - s_xbt_dictelm_t *p_child = NULL; - - p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - CDEBUG2(xbt_dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset); - - _xbt_dictelm_set_rec(p_child, key, key_len, - offset, data, free_f); - return; - } - - case 3: /* The key is a prefix of the child => child becomes child of p_new */ - { - s_xbt_dictelm_t *p_new = NULL; - s_xbt_dictelm_t *p_child = NULL; - - p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - _xbt_dictelm_alloc(key, key_len, old_offset, FALSE, data, free_f, &p_new); - - CDEBUG2(xbt_dict_add, "-> The child %p become child of new dict (%p)", - (void*)p_child, (void*)p_new); - - xbt_dynar_push(p_new->sub, &p_child); - p_child->offset = offset; - xbt_dynar_set(p_head->sub, pos, &p_new); - - return; - } - - case 4: /* A child share a common prefix with this key => Common ancestor */ - { - s_xbt_dictelm_t *p_new = NULL; - s_xbt_dictelm_t *p_child = NULL; - s_xbt_dictelm_t *p_anc = NULL; - char *anc_key = NULL; - int anc_key_len = offset; - - _xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_new); - p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - - /* memdup the old key, taking care of the terminating NULL byte */ - anc_key = xbt_malloc(anc_key_len+1); - memcpy(anc_key, key, anc_key_len); - anc_key[anc_key_len] = '\0'; - - - _xbt_dictelm_alloc(anc_key, anc_key_len, old_offset, TRUE, NULL, NULL, &p_anc); - - CDEBUG3(xbt_dict_add, "-> Make a common ancestor %p (%.*s)", - (void*)p_anc, anc_key_len, anc_key); - - if (key[offset] < p_child->key[offset]) { - xbt_dynar_push(p_anc->sub, &p_new); - xbt_dynar_push(p_anc->sub, &p_child); - } else { - xbt_dynar_push(p_anc->sub, &p_child); - xbt_dynar_push(p_anc->sub, &p_new); - } - - p_child->offset = offset; - - xbt_dynar_set(p_head->sub, pos, &p_anc); - - return; - } - - default: - THROW_IMPOSSIBLE; - } -} - -/** - * xbt_dictelm_set_ext: - * - * @head: the head of the dict - * @key: the key to set the new data - * @data: the data to add in the dict - * - * set the @data in the structure under the @key, which can be any kind - * of data, as long as its length is provided in @key_len. - */ -void -xbt_dictelm_set_ext(s_xbt_dictelm_t **pp_head, - const char *_key, - int key_len, - void *data, - void_f_pvoid_t *free_f) { - s_xbt_dictelm_t *p_head = *pp_head; - char *key = NULL; - - /* Make sure the copied key is NULL-terminated */ - key = xbt_malloc(key_len+1); - memcpy(key, _key, key_len); - key[key_len] = '\0'; - - /* there is no head, create it */ - if (!p_head) { - s_xbt_dictelm_t *p_child = NULL; - - CDEBUG0(xbt_dict_add, "Create an head"); - - /* The head is priviledged by being the only one with a NULL key */ - _xbt_dictelm_alloc(NULL, 0, 0, TRUE, NULL, NULL, &p_head); - - CDEBUG2(xbt_dict_add, "Push %.*s as child of this head",key_len,key); - _xbt_dictelm_alloc(key, key_len, 0, FALSE, data, free_f, &p_child); - xbt_dynar_insert_at(p_head->sub, 0, &p_child); - - *pp_head = p_head; - - return; - } - - _xbt_dictelm_set_rec(p_head, key, key_len, 0, data, free_f); -} - -/** - * xbt_dictelm_set: - * - * @head: the head of the dict - * @key: the key to set the new data - * @data: the data to add in the dict - * - * set the @data in the structure under the @key, which is a - * null terminated string. - */ -void -xbt_dictelm_set(s_xbt_dictelm_t **pp_head, - const char *_key, - void *data, - void_f_pvoid_t *free_f) { - - xbt_dictelm_set_ext(pp_head, _key, strlen(_key), data, free_f); -} - -/** - * _xbt_dict_get_rec: - * - * @head: the head of the dict - * @key: the key to find data - * @offset: offset on the key - * @data: the data that we are looking for - * - * Search the given @key. Throws not_found_error when not found. - */ -static -void * -_xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head, - const char *key, - int key_len, - int offset) { - - CDEBUG3(xbt_dict_search, "Search %.*s in %p", key_len, key, (void*)p_head); - - /*** The trivial case first ***/ - - /* we did enough recursion, we're done */ - if (offset >= key_len) { - return p_head->content; - } - - { - int match = 0; - int pos = 0; - - /*** Search where is the good child, and how good it is ***/ - _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match); - - switch (match) { - - case 0: /* no child have a common prefix */ - THROW2(not_found_error,0,"key '%.*s' not found",key_len,key); - - case 1: /* A child have exactly this key => Got it */ - { - s_xbt_dictelm_t *p_child = NULL; - p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - return p_child->content; - } - - case 2: /* A child constitutes a prefix of the key => recurse */ - { - s_xbt_dictelm_t *p_child = NULL; - - p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - - return _xbt_dictelm_get_rec(p_child, key, key_len, offset); - } - - case 3: /* The key is a prefix of the child => not found */ - THROW2(not_found_error,0,"key %.*s not found",key_len,key); - - case 4: /* A child share a common prefix with this key => not found */ - THROW2(not_found_error,0,"key %.*s not found",key_len,key); - - default: - THROW_IMPOSSIBLE; - } - } -} - -/** - * xbt_dictelm_get_ext: - * - * @head: the head of the dict - * @key: the key to find data - * @data: the data that we are looking for - * - * Search the given @key. Throws not_found_error when not found. - */ -void * -xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head, - const char *key, - int key_len) { - /* there is no head, go to hell */ - if (!p_head) - THROW2(not_found_error,0,"Key '%.*s' not found in dict",key_len,key); - - return _xbt_dictelm_get_rec(p_head, key, key_len, 0); -} - -/** - * xbt_dictelm_get: - * - * @head: the head of the dict - * @key: the key to find data - * @data: the data that we are looking for - * - * Search the given @key. Throws not_found_error when not found. - */ -void * -xbt_dictelm_get(s_xbt_dictelm_t *p_head, - const char *key) { - - return xbt_dictelm_get_ext(p_head, key, strlen(key)); -} - -/*----[ _xbt_dict_collapse ]------------------------------------------------*/ -static _XBT_INLINE -void -_collapse_if_need(xbt_dictelm_t head, - int pos, - int offset) { - xbt_dictelm_t child = NULL; - - CDEBUG2(xbt_dict_collapse, "Collapse %d of %p... ", pos, (void*)head); - - if (pos >= 0) { - /* Remove the child if |it's key| == 0 (meaning it's dead) */ - child = xbt_dynar_get_as(head->sub, pos, xbt_dictelm_t); - - if (offset >= child->key_len) { - - xbt_assert0(xbt_dynar_length(child->sub) == 0, - "Found a dead child with grand childs. Internal error"); - - CDEBUG1(xbt_dict_collapse, "Remove dead child %p.... ", (void*)child); - xbt_dynar_remove_at(head->sub, pos, &child); - xbt_dictelm_free(&child); - } - } - - if (!head->key) { - CDEBUG0(xbt_dict_collapse, "Do not collapse the head, you stupid programm"); - return; - } - - if (head->content || head->free_f || - xbt_dynar_length(head->sub) != 1) { - CDEBUG0(xbt_dict_collapse, "Cannot collapse"); - return; /* cannot collapse */ - } - - child = xbt_dynar_get_as(head->sub, 0, xbt_dictelm_t); - - /* Get the child's key as new key */ - CDEBUG2(xbt_dict_collapse, - "Do collapse with only child %.*s", child->key_len, child->key); - - head->content = child->content; - head->free_f = child->free_f; - free(head->key); - head->key = child->key; - head->key_len = child->key_len; - - xbt_dynar_free_container(&(head->sub)) ; - - head->sub = child->sub; - free(child); -} - -/** - * _xbt_dict_remove_rec: - * - * @head: the head of the dict - * @key: the key of the data to be removed - * @offset: offset on the key - * - * Remove the entry associated with the given @key. Throws not_found_error. - */ -void -_xbt_dictelm_remove_rec(xbt_dictelm_t head, - const char *key, - int key_len, - int offset) { - - /* there is no key to search, we did enough recursion => kill current */ - if (offset >= key_len) { - int killme = 0; /* do I need to suicide me ? */ - - if (head->content && head->free_f) { - head->free_f(head->content); - } - - killme = !xbt_dynar_length(head->sub); - head->content = NULL; - head->free_f = NULL; - _collapse_if_need(head, -1, offset); - - if (killme) { - DEBUG0("kill this node"); - head->key_len = 0; /* killme. Cleanup done one step higher in recursion */ - } - - return; - - } else { - int match = 0; - int pos = 0; - int old_offset = offset; - - /*** Search where is the good child, and how good it is ***/ - _xbt_dictelm_child_search(head, key, key_len, &pos, &offset, &match); - - switch (match) { - - case 1: /* A child have exactly this key => recurse */ - case 2: /* A child constitutes a prefix of the key => recurse */ - - { - s_xbt_dictelm_t *p_child = NULL; - - p_child = xbt_dynar_get_as(head->sub, pos, s_xbt_dictelm_t*); - /*DEBUG5("Recurse on child %d of %p to remove %.*s (prefix=%d)", - pos, (void*)p_child, key+offset, key_len-offset,offset);*/ - _xbt_dictelm_remove_rec(p_child, key, key_len, offset); - - _collapse_if_need(head, pos, old_offset); - return; - } - - - case 0: /* no child have a common prefix */ - case 3: /* The key is a prefix of the child => not found */ - case 4: /* A child share a common prefix with this key => not found */ - - THROW2(not_found_error,0,"Unable to remove key '%.*s': not found",key_len,key); - - default: - THROW_IMPOSSIBLE; - - } - } -} - -/** - * xbt_dictelm_remove_ext: - * - * @head: the head of the dict - * @key: the key of the data to be removed - * - * Remove the entry associated with the given @key. Throws not_found_err - */ -void -xbt_dictelm_remove_ext(xbt_dictelm_t head, - const char *key, - int key_len) { - /* there is no head, go to hell */ - if (!head) - THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key); + element->key_len = key_len; + element->content = content; + element->free_f = free_f; + element->next = next; - _xbt_dictelm_remove_rec(head, key, key_len, 0); + return element; } -/** - * xbt_dictelm_remove: - * - * @head: the head of the dict - * @key: the key of the data to be removed - * - * Throws not_found when applicable - */ -void -xbt_dictelm_remove(xbt_dictelm_t head, - const char *key) { - _xbt_dictelm_remove_rec(head, key, strlen(key),0); -} - -/*----[ _xbt_dict_dump_rec ]------------------------------------------------*/ -/* private function to do the job of xbt_dict_dump recursively */ -/*---------------------------------------------------------------------------*/ -static -void -_xbt_dictelm_dump_rec(xbt_dictelm_t head, - int offset, - void_f_pvoid_t *output) { - xbt_dictelm_t child = NULL; - char *key = NULL; - int key_len = 0; - int i = 0; - - if (!head) - return; - - printf("[%p] ", (void*)head); - - key = head->key; - key_len = head->key_len; - - if (key_len) - printf (" "); - - for (i = 0; i < offset; i++) - printf("-"); - - fflush(stdout); - - if (key) { - - if (!key_len) { - printf ("HEAD"); - } else if (key[key_len] != '\0') { - char *key_string = NULL; - - key_string = xbt_malloc(key_len*2+1); - _xbt_bytes_to_string(key, key_len, key_string); - - printf("%.*s|(%d)", key_len-2*offset, key_string + 2*offset, offset); - - free(key_string); - } else { - printf("%.*s|(%d)", key_len-offset, key + offset , offset); - } - } - - printf(" -> "); - - if (head->content) { - - if (output) { - output(head->content); - } else { - printf("(data)"); +void xbt_dictelm_free(xbt_dictelm_t element) { + if (element != NULL) { + xbt_free(element->key); + + if (element->free_f != NULL && element->content != NULL) { + element->free_f(element->content); } - - } else if (head->internal) { - printf("(internal node)"); - } else { - printf("(null)"); + + xbt_free(element); } - - printf(" \t\t\t[ %lu child(s) ]\n", xbt_dynar_length(head->sub)); - - xbt_dynar_foreach(head->sub, i, child) - _xbt_dictelm_dump_rec(child, child->offset, output); - } - -/** - * xbt_dictelm_dump: - * - * @head: the head of the dict - * @output: a function to dump each data in the tree - * - * Ouputs the content of the structure. (for debuging purpose). @ouput is a - * function to output the data. If NULL, data won't be displayed. - */ - -void -xbt_dictelm_dump(xbt_dictelm_t head, - void_f_pvoid_t *output) { - _xbt_dictelm_dump_rec(head, 0, output); -} - -/** - * xbt_dictelm_print_fct: - * - * @data: - * - * To dump multidict, this function dumps a dict - */ - -void -xbt_dictelm_print_fct(void *data) { - printf("tree %p", (void*)data); -} - diff --git a/src/xbt/dict_private.h b/src/xbt/dict_private.h index 7ad68349fa..97b23c9899 100644 --- a/src/xbt/dict_private.h +++ b/src/xbt/dict_private.h @@ -8,8 +8,8 @@ /* 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. */ -#ifndef _XBT_DICT_ELM_T_ -#define _XBT_DICT_ELM_T_ +#ifndef _XBT_DICT_PRIVATE_H__ +#define _XBT_DICT_PRIVATE_H__ #include "xbt/sysdep.h" #include "xbt/log.h" @@ -17,53 +17,32 @@ #include "xbt/dynar.h" #include "xbt/dict.h" -/*####[ Type definition ]####################################################*/ -typedef struct xbt_dictelm_ { - char *key; - int key_len; - int offset; /* offset on the key */ - int internal; /* true if it's only an internal node */ - void *content; - void_f_pvoid_t *free_f; /*pointer to the function to call to free this ctn*/ +typedef struct xbt_dictelm_ *xbt_dictelm_t; - xbt_dynar_t sub; /* sub */ -} s_xbt_dictelm_t, *xbt_dictelm_t; +typedef struct xbt_dictelm_ { + char *key; + int key_len; + void *content; + void_f_pvoid_t *free_f; + xbt_dictelm_t next; +} s_xbt_dictelm_t; typedef struct xbt_dict_ { - s_xbt_dictelm_t *head; + xbt_dictelm_t *table; + int table_size; } s_xbt_dict_t; typedef struct xbt_dict_cursor_ s_xbt_dict_cursor_t; -/*####[ Function prototypes ]################################################*/ -void xbt_dictelm_free (s_xbt_dictelm_t **pp_elm); - -void xbt_dictelm_set (s_xbt_dictelm_t **pp_head, - const char *_key, - void *data, - void_f_pvoid_t *free_ctn); -void xbt_dictelm_set_ext (s_xbt_dictelm_t **pp_head, - const char *_key, - int key_len, - void *data, - void_f_pvoid_t *free_ctn); - -void* xbt_dictelm_get (s_xbt_dictelm_t *p_head, - const char *key); -void* xbt_dictelm_get_ext (s_xbt_dictelm_t *p_head, - const char *key, - int key_len); - -void xbt_dictelm_remove (s_xbt_dictelm_t *p_head, - const char *key); -void xbt_dictelm_remove_ext(s_xbt_dictelm_t *p_head, - const char *key, - int key_len); - -void xbt_dictelm_dump (s_xbt_dictelm_t *p_head, - void_f_pvoid_t *output); - -void xbt_dictelm_print_fct (void *data); - -#endif /* _XBT_DICT_ELM_T_ */ +unsigned int xbt_dict_hash(const char *str); +/*####[ Function prototypes ]################################################*/ +xbt_dictelm_t xbt_dictelm_new(const char *key, + int key_len, + void *content, + void_f_pvoid_t free_f, + xbt_dictelm_t next); +void xbt_dictelm_free(xbt_dictelm_t element); +void xbt_dict_add_element(xbt_dict_t dict, xbt_dictelm_t element); + +#endif /* _XBT_DICT_PRIVATE_H_ */