X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/c42000db0f347a26ac1645d830ac949194ec4da0..169edc40a9d6aac50da8647a98df1e2b7cd92727:/src/xbt/dict_elm.c diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c index 380a35599a..eaa1c3ac77 100644 --- a/src/xbt/dict_elm.c +++ b/src/xbt/dict_elm.c @@ -2,34 +2,35 @@ /* dict - a generic dictionnary, variation over the B-tree concept */ -/* Authors: Martin Quinson */ -/* Copyright (C) 2003 the OURAGAN project. */ +/* Copyright (c) 2003, 2004 Martin Quinson. 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. */ + * 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 */ -GRAS_LOG_EXTERNAL_CATEGORY(dict); -GRAS_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"); -GRAS_LOG_NEW_SUBCATEGORY(dict_add,dict,"Dictionaries internals: elements addition"); -GRAS_LOG_NEW_SUBCATEGORY(dict_search,dict,"Dictionaries internals: searching"); -GRAS_LOG_NEW_SUBCATEGORY(dict_remove,dict,"Dictionaries internals: elements removal"); -GRAS_LOG_NEW_SUBCATEGORY(dict_collapse,dict,"Dictionaries internals: post-removal cleanup"); -GRAS_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 ]#################################################*/ -static _GRAS_INLINE void _gras_dictelm_alloc(char *key, - int offset, - int key_len, - void *data, - void_f_pvoid_t *free_ctn, - /*OUT*/gras_dictelm_t **where); +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 _GRAS_INLINE void _str_prefix_lgr(const char *key1, +static _XBT_INLINE void _str_prefix_lgr(const char *key1, int key_len1, const char *key2, int key_len2, @@ -37,78 +38,65 @@ static _GRAS_INLINE void _str_prefix_lgr(const char *key1, int *match); -static void _gras_dictelm_dump_rec(gras_dictelm_t *head, +static void _xbt_dictelm_dump_rec(s_xbt_dictelm_t *head, int offset, void_f_pvoid_t *output); -static void _gras_dictelm_set_rec(gras_dictelm_t *head, +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_ctn); -static gras_error_t _gras_dictelm_get_rec(gras_dictelm_t *head, - const char *key, - int key_len, - int offset, - /* OUT */void **data); -static gras_error_t _gras_dictelm_remove_rec(gras_dictelm_t *head, - const char *key, - int key_len, - int offset); - -static _GRAS_INLINE + 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(gras_dictelm_t *p_head, +_collapse_if_need(s_xbt_dictelm_t *p_head, int pos, int offset); /* ---- */ -static _GRAS_INLINE -void * -gras_memdup(const void * const ptr, - const size_t length) { - void * new_ptr = NULL; - - new_ptr = gras_malloc(length); - memcpy(new_ptr, ptr, length); - - return new_ptr; -} - /* - * _gras_nibble_to_char: + * _xbt_nibble_to_char: * * Change any byte to a printable char */ -static _GRAS_INLINE +static _XBT_INLINE char -_gras_nibble_to_char(unsigned char c) { +_xbt_nibble_to_char(unsigned char c) { c &= 0x0f; return c>9 ? c-10+'a' : c + '0'; } /* - * _gras_bytes_to_string: + * _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 _GRAS_INLINE +static _XBT_INLINE char * -_gras_bytes_to_string(char * const ptr, +_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++ = _gras_nibble_to_char(*src & 0x0f ); - *dst++ = _gras_nibble_to_char(*src++ & 0xf0 >> 4); + *dst++ = _xbt_nibble_to_char(*src & 0x0f ); + *dst++ = _xbt_nibble_to_char(*src++ & 0xf0 >> 4); } *dst = 0; @@ -119,59 +107,58 @@ _gras_bytes_to_string(char * const ptr, /* ---- */ /* - * _gras_dictelm_alloc: + * _xbt_dictelm_alloc: * * Alloc a dict element with no child. */ -static _GRAS_INLINE +static _XBT_INLINE void -_gras_dictelm_alloc(char *key, - int key_len, - int offset, - void *data, - void_f_pvoid_t *free_ctn, - /*OUT*/gras_dictelm_t **pp_elm) { - gras_error_t errcode = no_error; - gras_dictelm_t *p_elm = NULL; +_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 = gras_new(gras_dictelm_t,1); + 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_ctn = free_ctn; - p_elm->sub = gras_dynar_new(sizeof(gras_dictelm_t*), _dictelm_wrapper_free); + p_elm->free_f = free_f; + p_elm->sub = xbt_dynar_new(sizeof(s_xbt_dictelm_t*), _dictelm_wrapper_free); *pp_elm = p_elm; } /** - * gras_dictelm_free: + * xbt_dictelm_free: * * @pp_elm: the dict elem to be freed * * Frees a dictionnary element with all its childs. */ void -gras_dictelm_free(gras_dictelm_t **pp_elm) { +xbt_dictelm_free(s_xbt_dictelm_t **pp_elm) { if (*pp_elm) { - gras_dictelm_t *p_elm = *pp_elm; + s_xbt_dictelm_t *p_elm = *pp_elm; - gras_dynar_free(p_elm->sub); + xbt_dynar_free(&(p_elm->sub)); if (p_elm->key) { - gras_free(p_elm->key); + free(p_elm->key); } - if (p_elm->free_ctn && p_elm->content) { - p_elm->free_ctn(p_elm->content); + if (p_elm->free_f && p_elm->content) { + p_elm->free_f(p_elm->content); } - memset(p_elm, 0, sizeof (*p_elm)); - - gras_free(p_elm); + free(p_elm); *pp_elm = NULL; } } @@ -185,9 +172,9 @@ static void _dictelm_wrapper_free(void *pp_elm) { DEBUG3("Free dictelm '%.*s' %p", - (*(gras_dictelm_t**)pp_elm)->key_len, (*(gras_dictelm_t**)pp_elm)->key, + (*(s_xbt_dictelm_t**)pp_elm)->key_len, (*(s_xbt_dictelm_t**)pp_elm)->key, *(void**)pp_elm); - gras_dictelm_free((gras_dictelm_t**)pp_elm); + xbt_dictelm_free((s_xbt_dictelm_t**)pp_elm); } /*####[ utility functions ]##################################################*/ @@ -196,9 +183,9 @@ _dictelm_wrapper_free(void *pp_elm) { * * * Returns the length of the common prefix of @str1 and @str2. - * Do make sure the strings are not null + * Do make sure the strings are not null, this function don't */ -static _GRAS_INLINE +static _XBT_INLINE void _str_prefix_lgr(const char *key1, int key_len1, @@ -233,15 +220,21 @@ _str_prefix_lgr(const char *key1, if (o >= key_len1) { if (o >= key_len2) { - m = 1; + m = 1; /* exact match */ } else { - m = 2; + m = 2; /* child is prefix */ } } else if (o >= key_len2) { - m = 3; - } else { - m = 4; + 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) */ } } @@ -254,23 +247,23 @@ _str_prefix_lgr(const char *key1, * _dictelm_child_cmp: * * Compares two dictelm keys and return their matching (using the same - * convention than @_gras_dict_child_search() ) + * convention than @_xbt_dict_child_search() ) */ -static _GRAS_INLINE +static _XBT_INLINE void -_dict_child_cmp(gras_dictelm_t *p_dict, +_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) { - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_child = NULL; int cmp = 0; int o = *p_offset; int m = *p_match; - gras_dynar_get(p_dict->sub, pos, &p_child); + 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 */ @@ -288,7 +281,7 @@ _dict_child_cmp(gras_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); @@ -300,7 +293,7 @@ _dict_child_cmp(gras_dictelm_t *p_dict, } /** - * _gras_dict_child_search: + * _xbt_dict_child_search: * * Search where would be inserted @key between the childs of @p_elm. * @@ -321,14 +314,14 @@ _dict_child_cmp(gras_dictelm_t *p_dict, * handled by previous levels of recursion. In output, that the one counting * also this level. */ -static _GRAS_INLINE +static _XBT_INLINE void -_gras_dictelm_child_search(gras_dictelm_t *p_elm, - const char *key, - int key_len, - int *p_pos, - int *p_offset, - int *p_match) { +_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; @@ -336,32 +329,66 @@ _gras_dictelm_child_search(gras_dictelm_t *p_elm, int len = 0; - CDEBUG5(dict_search, "search child [%.*s] under [%.*s] (len=%lu)", + CDEBUG6(xbt_dict_search, "search child [%.*s] under [%.*s]=%p (len=%lu)", key_len, key, - p_elm?p_elm->key_len:6, p_elm?p_elm->key:"(head)", - (p_elm&&p_elm->sub)?gras_dynar_length(p_elm->sub):0); + 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); - len = gras_dynar_length(p_elm->sub); - - for (p = 0; p < len; p++) { - int cmp = 0; + len = xbt_dynar_length(p_elm->sub); - _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp); - - if (m) - break; - - o = *p_offset; - m = 0; + { + 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; - CDEBUG5(dict_search, "search [%.*s] in [%.*s] => %s", + CDEBUG6(xbt_dict_search, "search [%.*s] in [%.*s]=%p => %s", key_len, key, - p_elm?p_elm->key_len:6, p_elm?p_elm->key:"(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" : ( m == 2 ? "selected child constitutes a prefix" : @@ -372,51 +399,51 @@ _gras_dictelm_child_search(gras_dictelm_t *p_elm, } /** - * _gras_dictelm_change_value: + * _xbt_dictelm_change_value: * - * Change the value of the dictelm, making sure to free the old one, if any. + * Change the value of the dictelm, making sure to free the old one, if any. The node also become a non-internal one. */ -static _GRAS_INLINE +static _XBT_INLINE void -_gras_dictelm_change_value(gras_dictelm_t *p_elm, +_xbt_dictelm_change_value(s_xbt_dictelm_t *p_elm, void *data, - void_f_pvoid_t *free_ctn) { + void_f_pvoid_t *free_f) { - if (p_elm->content && p_elm->free_ctn) { - p_elm->free_ctn(p_elm->content); + if (p_elm->content && p_elm->free_f) { + p_elm->free_f(p_elm->content); } - p_elm->free_ctn = free_ctn; + p_elm->free_f = free_f; p_elm->content = data; + p_elm->internal = FALSE; } /** - * _gras_dictelm_set_rec: + * _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 - * @Returns: a gras_error * * 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 gras_dict_set which locks the struct and + * This is a helper function to xbt_dict_set which locks the struct and * strdup the key before action. */ void -_gras_dictelm_set_rec(gras_dictelm_t *p_head, +_xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head, char *key, int key_len, int offset, void *data, - void_f_pvoid_t *free_ctn) { + void_f_pvoid_t *free_f) { int match = 0; 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)"), @@ -427,382 +454,372 @@ _gras_dictelm_set_rec(gras_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"); - _gras_dictelm_change_value(p_head, data, free_ctn); - gras_free(key); /* Keep the key used in the tree */ + _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 ***/ - _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match); + _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) { case 0: /* no child have a common prefix */ { - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_child = NULL; - _gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_child); - CDEBUG1(dict_add, "-> Add a child %p", (void*)p_child); - gras_dynar_insert_at(p_head->sub, pos, &p_child); + _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*/ { - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_child = NULL; - gras_dynar_get(p_head->sub, pos, &p_child); - CDEBUG1(dict_add, "-> Change the value of the child %p", (void*)p_child); - _gras_dictelm_change_value(p_child, data, free_ctn); + 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); - gras_free(key); + free(key); return; } case 2: /* A child constitutes a prefix of the key => recurse */ { - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_child = NULL; - gras_dynar_get(p_head->sub, pos, &p_child); - CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset); + 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); - _gras_dictelm_set_rec(p_child, key, key_len, - offset, data, free_ctn); + _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 */ { - gras_dictelm_t *p_new = NULL; - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_new = NULL; + s_xbt_dictelm_t *p_child = NULL; - gras_dynar_get(p_head->sub, pos, &p_child); - _gras_dictelm_alloc(key, key_len, old_offset, data, free_ctn, &p_new); + 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); - gras_dynar_push(p_new->sub, &p_child); + xbt_dynar_push(p_new->sub, &p_child); p_child->offset = offset; - gras_dynar_set(p_head->sub, pos, &p_new); + xbt_dynar_set(p_head->sub, pos, &p_new); return; } case 4: /* A child share a common prefix with this key => Common ancestor */ { - gras_dictelm_t *p_new = NULL; - gras_dictelm_t *p_child = NULL; - gras_dictelm_t *p_anc = NULL; + 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; - _gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_new); - gras_dynar_get(p_head->sub, pos, &p_child); + _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'; - anc_key = gras_memdup(key, anc_key_len); - _gras_dictelm_alloc(anc_key, anc_key_len, old_offset, NULL, NULL, &p_anc); + _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]) { - gras_dynar_push(p_anc->sub, &p_new); - gras_dynar_push(p_anc->sub, &p_child); + xbt_dynar_push(p_anc->sub, &p_new); + xbt_dynar_push(p_anc->sub, &p_child); } else { - gras_dynar_push(p_anc->sub, &p_child); - gras_dynar_push(p_anc->sub, &p_new); + xbt_dynar_push(p_anc->sub, &p_child); + xbt_dynar_push(p_anc->sub, &p_new); } p_child->offset = offset; - gras_dynar_set(p_head->sub, pos, &p_anc); + xbt_dynar_set(p_head->sub, pos, &p_anc); return; } default: - DIE_IMPOSSIBLE; + THROW_IMPOSSIBLE; } } /** - * gras_dictelm_set_ext: + * 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 - * @Returns: a gras_error * * 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 -gras_dictelm_set_ext(gras_dictelm_t **pp_head, +xbt_dictelm_set_ext(s_xbt_dictelm_t **pp_head, const char *_key, int key_len, void *data, - void_f_pvoid_t *free_ctn) { - gras_dictelm_t *p_head = *pp_head; + void_f_pvoid_t *free_f) { + s_xbt_dictelm_t *p_head = *pp_head; char *key = NULL; - key = gras_memdup(_key, key_len); + /* 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) { - gras_dictelm_t *p_child = NULL; + 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 */ - _gras_dictelm_alloc(NULL, 0, 0, NULL, NULL, &p_head); + _xbt_dictelm_alloc(NULL, 0, 0, TRUE, NULL, NULL, &p_head); - _gras_dictelm_alloc(key, key_len, 0, data, free_ctn, &p_child); - gras_dynar_insert_at(p_head->sub, 0, &p_child); + 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; } - _gras_dictelm_set_rec(p_head, key, key_len, 0, data, free_ctn); + _xbt_dictelm_set_rec(p_head, key, key_len, 0, data, free_f); } /** - * gras_dictelm_set: + * 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 - * @Returns: a gras_error * * set the @data in the structure under the @key, which is a * null terminated string. */ void -gras_dictelm_set(gras_dictelm_t **pp_head, +xbt_dictelm_set(s_xbt_dictelm_t **pp_head, const char *_key, void *data, - void_f_pvoid_t *free_ctn) { + void_f_pvoid_t *free_f) { - gras_dictelm_set_ext(pp_head, _key, 1+strlen(_key), data, free_ctn); + xbt_dictelm_set_ext(pp_head, _key, strlen(_key), data, free_f); } /** - * _gras_dict_get_rec: + * _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 - * @Returns: gras_error * - * Search the given @key. mismatch_error when not found. + * Search the given @key. Throws not_found_error when not found. */ static -gras_error_t -_gras_dictelm_get_rec(gras_dictelm_t *p_head, +void * +_xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head, const char *key, int key_len, - int offset, - void **data) { - void *res; + 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; /* Make it ready to answer 'not found' in one operation */ - /*** Search where is the good child, and how good it is ***/ - _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match); + _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 */ { - gras_dictelm_t *p_child = NULL; - - gras_dynar_get(p_head->sub, pos, &p_child); - *data = p_child->content; - - return no_error; + 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 */ { - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_child = NULL; - gras_dynar_get(p_head->sub, pos, &p_child); + p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*); - return _gras_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; } } } /** - * gras_dictelm_get_ext: + * xbt_dictelm_get_ext: * * @head: the head of the dict * @key: the key to find data * @data: the data that we are looking for - * @Returns: gras_error * - * Search the given @key. mismatch_error when not found. + * Search the given @key. Throws not_found_error when not found. */ -gras_error_t -gras_dictelm_get_ext(gras_dictelm_t *p_head, - const char *key, - int key_len, - /* OUT */void **data) { +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) { - return mismatch_error; - } + if (!p_head) + THROW2(not_found_error,0,"Key '%.*s' not found in dict",key_len,key); - return _gras_dictelm_get_rec(p_head, key, key_len, 0, data); + return _xbt_dictelm_get_rec(p_head, key, key_len, 0); } /** - * gras_dictelm_get: + * xbt_dictelm_get: * * @head: the head of the dict * @key: the key to find data * @data: the data that we are looking for - * @Returns: gras_error * - * Search the given @key. mismatch_error when not found. + * Search the given @key. Throws not_found_error when not found. */ -gras_error_t -gras_dictelm_get(gras_dictelm_t *p_head, - const char *key, - /* OUT */void **data) { +void * +xbt_dictelm_get(s_xbt_dictelm_t *p_head, + const char *key) { - return gras_dictelm_get_ext(p_head, key, 1+strlen(key), data); + return xbt_dictelm_get_ext(p_head, key, strlen(key)); } -/*----[ _gras_dict_collapse ]------------------------------------------------*/ -static _GRAS_INLINE +/*----[ _xbt_dict_collapse ]------------------------------------------------*/ +static _XBT_INLINE void -_collapse_if_need(gras_dictelm_t *p_head, - int pos, - int offset) { - gras_dictelm_t *p_child = NULL; +_collapse_if_need(xbt_dictelm_t head, + int pos, + int offset) { + xbt_dictelm_t child = NULL; - CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, (void*)p_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) */ - gras_dynar_get(p_head->sub, pos, &p_child); + child = xbt_dynar_get_as(head->sub, pos, xbt_dictelm_t); - if (offset >= p_child->key_len) { + if (offset >= child->key_len) { - gras_assert0(gras_dynar_length(p_child->sub) == 0, + 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*)p_child); - gras_dynar_remove_at(p_head->sub, pos, &p_child); + CDEBUG1(xbt_dict_collapse, "Remove dead child %p.... ", (void*)child); + xbt_dynar_remove_at(head->sub, pos, &child); + xbt_dictelm_free(&child); } } - if (!p_head->key) { - CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm"); + if (!head->key) { + CDEBUG0(xbt_dict_collapse, "Do not collapse the head, you stupid programm"); return; } - if (p_head->content || p_head->free_ctn || - gras_dynar_length(p_head->sub) != 1) { - CDEBUG0(dict_collapse, "Cannot collapse"); + if (head->content || head->free_f || + xbt_dynar_length(head->sub) != 1) { + CDEBUG0(xbt_dict_collapse, "Cannot collapse"); return; /* cannot collapse */ } - gras_dynar_get(p_head->sub, 0, &p_child); + child = xbt_dynar_get_as(head->sub, 0, xbt_dictelm_t); /* Get the child's key as new key */ - CDEBUG2(dict_collapse, - "Do collapse with only child %.*s", p_child->key_len, p_child->key); + CDEBUG2(xbt_dict_collapse, + "Do collapse with only child %.*s", child->key_len, child->key); - p_head->content = p_child->content; - p_head->free_ctn = p_child->free_ctn; - gras_free(p_head->key); - p_head->key = p_child->key; - p_head->key_len = p_child->key_len; + head->content = child->content; + head->free_f = child->free_f; + free(head->key); + head->key = child->key; + head->key_len = child->key_len; - gras_dynar_free_container(p_head->sub) ; + xbt_dynar_free_container(&(head->sub)) ; - p_head->sub = p_child->sub; - gras_free(p_child); + head->sub = child->sub; + free(child); } /** - * _gras_dict_remove_rec: + * _xbt_dict_remove_rec: * * @head: the head of the dict * @key: the key of the data to be removed * @offset: offset on the key - * @Returns: gras_error_t * - * Remove the entry associated with the given @key + * Remove the entry associated with the given @key. Throws not_found_error. */ -gras_error_t -_gras_dictelm_remove_rec(gras_dictelm_t *p_head, +void +_xbt_dictelm_remove_rec(xbt_dictelm_t head, const char *key, int key_len, int offset) { - gras_error_t errcode = no_error; /* 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 (p_head->content && p_head->free_ctn) { - p_head->free_ctn(p_head->content); + if (head->content && head->free_f) { + head->free_f(head->content); } - killme = !gras_dynar_length(p_head->sub); - p_head->content = NULL; - p_head->free_ctn = NULL; - _collapse_if_need(p_head, -1, offset); + 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"); - p_head->key_len = 0; /* killme. Cleanup done one step higher in recursion */ + head->key_len = 0; /* killme. Cleanup done one step higher in recursion */ } - return errcode; + return; } else { int match = 0; @@ -810,7 +827,7 @@ _gras_dictelm_remove_rec(gras_dictelm_t *p_head, int old_offset = offset; /*** Search where is the good child, and how good it is ***/ - _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match); + _xbt_dictelm_child_search(head, key, key_len, &pos, &offset, &match); switch (match) { @@ -818,15 +835,15 @@ _gras_dictelm_remove_rec(gras_dictelm_t *p_head, case 2: /* A child constitutes a prefix of the key => recurse */ { - gras_dictelm_t *p_child = NULL; + s_xbt_dictelm_t *p_child = NULL; - gras_dynar_get(p_head->sub, pos, &p_child); + 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(_gras_dictelm_remove_rec(p_child, key, key_len, offset)); + _xbt_dictelm_remove_rec(p_child, key, key_len, offset); - _collapse_if_need(p_head, pos, old_offset); - return no_error; + _collapse_if_need(head, pos, old_offset); + return; } @@ -834,72 +851,68 @@ _gras_dictelm_remove_rec(gras_dictelm_t *p_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; } } } /** - * gras_dictelm_remove_ext: + * xbt_dictelm_remove_ext: * * @head: the head of the dict * @key: the key of the data to be removed - * @Returns: gras_error_t * - * Remove the entry associated with the given @key + * Remove the entry associated with the given @key. Throws not_found_err */ -gras_error_t -gras_dictelm_remove_ext(gras_dictelm_t *p_head, - const char *key, - int key_len) { +void +xbt_dictelm_remove_ext(xbt_dictelm_t head, + const char *key, + int key_len) { /* there is no head, go to hell */ - if (!p_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 _gras_dictelm_remove_rec(p_head, key, key_len, 0); + _xbt_dictelm_remove_rec(head, key, key_len, 0); } /** - * gras_dictelm_remove: + * xbt_dictelm_remove: * * @head: the head of the dict * @key: the key of the data to be removed - * @Returns: gras_error_t * - * Remove the entry associated with the given @key + * Throws not_found when applicable */ -gras_error_t -gras_dictelm_remove(gras_dictelm_t *p_head, +void +xbt_dictelm_remove(xbt_dictelm_t head, const char *key) { - return _gras_dictelm_remove_rec(p_head, key, 1+strlen(key),0); + _xbt_dictelm_remove_rec(head, key, strlen(key),0); } -/*----[ _gras_dict_dump_rec ]------------------------------------------------*/ -/* private function to do the job of gras_dict_dump recursively */ +/*----[ _xbt_dict_dump_rec ]------------------------------------------------*/ +/* private function to do the job of xbt_dict_dump recursively */ /*---------------------------------------------------------------------------*/ static void -_gras_dictelm_dump_rec(gras_dictelm_t *p_head, - int offset, - void_f_pvoid_t *output) { - gras_dictelm_t *p_child = NULL; - char *key = NULL; - int key_len = 0; - int i = 0; +_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 (!p_head) + if (!head) return; - printf("[%p] ", (void*)p_head); + printf("[%p] ", (void*)head); - key = p_head->key; - key_len = p_head->key_len; + key = head->key; + key_len = head->key_len; if (key_len) printf (" "); @@ -910,62 +923,64 @@ _gras_dictelm_dump_rec(gras_dictelm_t *p_head, fflush(stdout); if (key) { - - if (!key_len) { - printf ("HEAD"); - } else { - char *key_string = NULL; - - key_string = gras_malloc(key_len*2+1); - _gras_bytes_to_string(key, key_len, key_string); - - printf("%.*s|(%d)", key_len-offset, key_string + offset, offset); - - gras_free(key_string); - } - + + 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 (p_head->content) { + if (head->content) { if (output) { - output(p_head->content); + output(head->content); } else { printf("(data)"); } + } else if (head->internal) { + printf("(internal node)"); } else { printf("(null)"); } - printf(" \t\t\t[ %lu child(s) ]\n", gras_dynar_length(p_head->sub)); + printf(" \t\t\t[ %lu child(s) ]\n", xbt_dynar_length(head->sub)); - gras_dynar_foreach(p_head->sub, i, p_child) - _gras_dictelm_dump_rec(p_child, p_child->offset, output); + xbt_dynar_foreach(head->sub, i, child) + _xbt_dictelm_dump_rec(child, child->offset, output); } /** - * gras_dictelm_dump: + * xbt_dictelm_dump: * * @head: the head of the dict * @output: a function to dump each data in the tree - * @Returns: gras_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. */ void -gras_dictelm_dump(gras_dictelm_t *p_head, - void_f_pvoid_t *output) { - _gras_dictelm_dump_rec(p_head, 0, output); +xbt_dictelm_dump(xbt_dictelm_t head, + void_f_pvoid_t *output) { + _xbt_dictelm_dump_rec(head, 0, output); } /** - * gras_dictelm_print_fct: + * xbt_dictelm_print_fct: * * @data: * @@ -973,7 +988,7 @@ gras_dictelm_dump(gras_dictelm_t *p_head, */ void -gras_dictelm_print_fct(void *data) { +xbt_dictelm_print_fct(void *data) { printf("tree %p", (void*)data); }