- 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);
