X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/95724d4a8dabb59052ed888bfedd65de712101dc..169edc40a9d6aac50da8647a98df1e2b7cd92727:/src/xbt/dict_elm.c diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c index cf03ba9378..eaa1c3ac77 100644 --- a/src/xbt/dict_elm.c +++ b/src/xbt/dict_elm.c @@ -7,16 +7,17 @@ /* 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(dict); -XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dict_elm,dict,"Dictionaries internals"); +XBT_LOG_EXTERNAL_CATEGORY(xbt_dict); +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict_elm,xbt_dict,"Dictionaries internals"); -XBT_LOG_NEW_SUBCATEGORY(dict_add,dict,"Dictionaries internals: elements addition"); -XBT_LOG_NEW_SUBCATEGORY(dict_search,dict,"Dictionaries internals: searching"); -XBT_LOG_NEW_SUBCATEGORY(dict_remove,dict,"Dictionaries internals: elements removal"); -XBT_LOG_NEW_SUBCATEGORY(dict_collapse,dict,"Dictionaries internals: post-removal cleanup"); -XBT_LOG_NEW_SUBCATEGORY(dict_multi,dict,"Dictionaries internals: dictionaries of dictionaries"); +XBT_LOG_NEW_SUBCATEGORY(xbt_dict_add,xbt_dict,"Dictionaries internals: elements addition"); +XBT_LOG_NEW_SUBCATEGORY(xbt_dict_search,xbt_dict,"Dictionaries internals: searching"); +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 ]#################################################*/ @@ -49,15 +50,14 @@ static void _xbt_dictelm_set_rec(s_xbt_dictelm_t *head, int offset, void *data, void_f_pvoid_t *free_f); -static xbt_error_t _xbt_dictelm_get_rec(s_xbt_dictelm_t *head, - const char *key, - int key_len, - int offset, - /* OUT */void **data); -static xbt_error_t _xbt_dictelm_remove_rec(s_xbt_dictelm_t *head, - const char *key, - int key_len, - int offset); +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 @@ -67,18 +67,6 @@ _collapse_if_need(s_xbt_dictelm_t *p_head, /* ---- */ -static _XBT_INLINE -void * -xbt_memdup(const void * const ptr, - const size_t length) { - void * new_ptr = NULL; - - new_ptr = xbt_malloc(length); - memcpy(new_ptr, ptr, length); - - return new_ptr; -} - /* * _xbt_nibble_to_char: * @@ -293,7 +281,7 @@ _dict_child_cmp(s_xbt_dictelm_t *p_dict, cmp = 1; } - CDEBUG6(dict_search, "Cmp '%.*s' and '%.*s' (offset=%d) => %d", + 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); @@ -341,10 +329,10 @@ _xbt_dictelm_child_search(s_xbt_dictelm_t *p_elm, int len = 0; - CDEBUG6(dict_search, "search child [%.*s] under [%.*s]=%p (len=%lu)", + 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 ? (p_elm->key?p_elm->key:"(NULL)") : "(head)", + p_elm ? PRINTF_STR(p_elm->key) : "(head)", p_elm, (p_elm&&p_elm->sub) ? xbt_dynar_length(p_elm->sub) : 0); @@ -397,9 +385,9 @@ _xbt_dictelm_child_search(s_xbt_dictelm_t *p_elm, *p_offset = o; *p_pos = p; *p_match = m; - CDEBUG6(dict_search, "search [%.*s] in [%.*s]=%p => %s", + 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?(p_elm->key?p_elm->key:"(null)"):"(head)", + 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" : @@ -455,7 +443,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, int pos = 0; const int old_offset = offset; - CDEBUG6(dict_add, "--> Insert '%.*s' after '%.*s' (offset=%d) in tree %p", + 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)"), @@ -466,7 +454,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, /* there is no key (we did enough recursion), change the value of head */ if (offset >= key_len) { - CDEBUG0(dict_add, "--> Change the value of head"); + 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 */ @@ -477,7 +465,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, /*** Search where to add this child, and how ***/ _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match); - CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d", + CDEBUG3(xbt_dict_add, "child_search => pos=%d, offset=%d, match=%d", pos, offset, match); switch (match) { @@ -487,7 +475,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, s_xbt_dictelm_t *p_child = NULL; _xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_child); - CDEBUG1(dict_add, "-> Add a child %p", (void*)p_child); + CDEBUG1(xbt_dict_add, "-> Add a child %p", (void*)p_child); xbt_dynar_insert_at(p_head->sub, pos, &p_child); return; @@ -498,7 +486,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, s_xbt_dictelm_t *p_child = NULL; p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - CDEBUG1(dict_add, "-> Change the value of the child %p", (void*)p_child); + 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); @@ -511,7 +499,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, s_xbt_dictelm_t *p_child = NULL; p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset); + 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); @@ -526,7 +514,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, 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(dict_add, "-> The child %p become child of new dict (%p)", + 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); @@ -547,11 +535,15 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, _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*); - anc_key = xbt_memdup(key, anc_key_len); + /* 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(dict_add, "-> Make a common ancestor %p (%.*s)", + 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]) { @@ -570,7 +562,7 @@ _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, } default: - DIE_IMPOSSIBLE; + THROW_IMPOSSIBLE; } } @@ -593,18 +585,21 @@ xbt_dictelm_set_ext(s_xbt_dictelm_t **pp_head, s_xbt_dictelm_t *p_head = *pp_head; char *key = NULL; - key = xbt_memdup(_key, key_len+1); + /* 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(dict_add, "Create an head"); + 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(dict_add, "Push %.*s as child of this head",key_len,key); + 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); @@ -642,51 +637,42 @@ xbt_dictelm_set(s_xbt_dictelm_t **pp_head, * @key: the key to find data * @offset: offset on the key * @data: the data that we are looking for - * @Returns: xbt_error * - * Search the given @key. mismatch_error when not found. + * Search the given @key. Throws not_found_error when not found. */ static -xbt_error_t +void * _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head, const char *key, int key_len, - int offset, - void **data) { + int offset) { - CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, (void*)p_head); + 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) { - *data = p_head->content; - - return no_error; + return p_head->content; } { int match = 0; int pos = 0; - *data = NULL; /* Let's be clean */ - /*** 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 */ - return mismatch_error; + 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*); - *data = p_child->content; - - return no_error; + return p_child->content; } case 2: /* A child constitutes a prefix of the key => recurse */ @@ -695,17 +681,17 @@ _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head, 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, data); + return _xbt_dictelm_get_rec(p_child, key, key_len, offset); } case 3: /* The key is a prefix of the child => not found */ - return mismatch_error; + 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 */ - return mismatch_error; + THROW2(not_found_error,0,"key %.*s not found",key_len,key); default: - RAISE_IMPOSSIBLE; + THROW_IMPOSSIBLE; } } } @@ -716,21 +702,18 @@ _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head, * @head: the head of the dict * @key: the key to find data * @data: the data that we are looking for - * @Returns: xbt_error * - * Search the given @key. mismatch_error when not found. + * Search the given @key. Throws not_found_error when not found. */ -xbt_error_t +void * xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head, - const char *key, - int key_len, - /* OUT */void **data) { + const char *key, + int key_len) { /* there is no head, go to hell */ - if (!p_head) { - return mismatch_error; - } + 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, data); + return _xbt_dictelm_get_rec(p_head, key, key_len, 0); } /** @@ -739,16 +722,14 @@ xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head, * @head: the head of the dict * @key: the key to find data * @data: the data that we are looking for - * @Returns: xbt_error * - * Search the given @key. mismatch_error when not found. + * Search the given @key. Throws not_found_error when not found. */ -xbt_error_t -xbt_dictelm_get(s_xbt_dictelm_t *p_head, - const char *key, - /* OUT */void **data) { +void * +xbt_dictelm_get(s_xbt_dictelm_t *p_head, + const char *key) { - return xbt_dictelm_get_ext(p_head, key, strlen(key), data); + return xbt_dictelm_get_ext(p_head, key, strlen(key)); } /*----[ _xbt_dict_collapse ]------------------------------------------------*/ @@ -759,7 +740,7 @@ _collapse_if_need(xbt_dictelm_t head, int offset) { xbt_dictelm_t child = NULL; - CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, (void*)head); + 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) */ @@ -770,27 +751,27 @@ _collapse_if_need(xbt_dictelm_t head, xbt_assert0(xbt_dynar_length(child->sub) == 0, "Found a dead child with grand childs. Internal error"); - CDEBUG1(dict_collapse, "Remove dead child %p.... ", (void*)child); + 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(dict_collapse, "Do not collapse the head, you stupid programm"); + 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(dict_collapse, "Cannot collapse"); + 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(dict_collapse, + CDEBUG2(xbt_dict_collapse, "Do collapse with only child %.*s", child->key_len, child->key); head->content = child->content; @@ -811,16 +792,14 @@ _collapse_if_need(xbt_dictelm_t head, * @head: the head of the dict * @key: the key of the data to be removed * @offset: offset on the key - * @Returns: xbt_error_t * - * Remove the entry associated with the given @key + * Remove the entry associated with the given @key. Throws not_found_error. */ -xbt_error_t +void _xbt_dictelm_remove_rec(xbt_dictelm_t head, const char *key, int key_len, int offset) { - xbt_error_t errcode = no_error; /* there is no key to search, we did enough recursion => kill current */ if (offset >= key_len) { @@ -840,7 +819,7 @@ _xbt_dictelm_remove_rec(xbt_dictelm_t head, head->key_len = 0; /* killme. Cleanup done one step higher in recursion */ } - return errcode; + return; } else { int match = 0; @@ -861,10 +840,10 @@ _xbt_dictelm_remove_rec(xbt_dictelm_t head, 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);*/ - TRY(_xbt_dictelm_remove_rec(p_child, key, key_len, offset)); + _xbt_dictelm_remove_rec(p_child, key, key_len, offset); _collapse_if_need(head, pos, old_offset); - return no_error; + return; } @@ -872,11 +851,10 @@ _xbt_dictelm_remove_rec(xbt_dictelm_t head, 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 */ - return mismatch_error; - + THROW2(not_found_error,0,"Unable to remove key '%.*s': not found",key_len,key); default: - RAISE_IMPOSSIBLE; + THROW_IMPOSSIBLE; } } @@ -887,20 +865,18 @@ _xbt_dictelm_remove_rec(xbt_dictelm_t head, * * @head: the head of the dict * @key: the key of the data to be removed - * @Returns: xbt_error_t * - * Remove the entry associated with the given @key + * Remove the entry associated with the given @key. Throws not_found_err */ -xbt_error_t +void xbt_dictelm_remove_ext(xbt_dictelm_t head, const char *key, int key_len) { /* there is no head, go to hell */ - if (!head) { - RAISE0(mismatch_error, "there is no head, go to hell"); - } + if (!head) + THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key); - return _xbt_dictelm_remove_rec(head, key, key_len, 0); + _xbt_dictelm_remove_rec(head, key, key_len, 0); } /** @@ -908,14 +884,13 @@ xbt_dictelm_remove_ext(xbt_dictelm_t head, * * @head: the head of the dict * @key: the key of the data to be removed - * @Returns: xbt_error_t * - * Remove the entry associated with the given @key + * Throws not_found when applicable */ -xbt_error_t +void xbt_dictelm_remove(xbt_dictelm_t head, const char *key) { - return _xbt_dictelm_remove_rec(head, key, strlen(key),0); + _xbt_dictelm_remove_rec(head, key, strlen(key),0); } /*----[ _xbt_dict_dump_rec ]------------------------------------------------*/ @@ -993,7 +968,6 @@ _xbt_dictelm_dump_rec(xbt_dictelm_t head, * * @head: the head of the dict * @output: a function to dump each data in the tree - * @Returns: xbt_error_t * * Ouputs the content of the structure. (for debuging purpose). @ouput is a * function to output the data. If NULL, data won't be displayed.