-
- 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;
- char *anc_key = NULL;
- int anc_key_len = offset;
-
- TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_new));
- gras_dynar_get(p_head->sub, pos, &p_child);
-
- anc_key = memdup(key, anc_key_len);
-
- TRY(_gras_dictelm_alloc(anc_key, anc_key_len, old_offset,
- NULL, NULL, &p_anc));
-
- CDEBUG2(dict_add, "-> Make a common ancestor %p (%s)", p_anc, anc_key);
-
- if (key[offset] < p_child->key[offset]) {
- TRY(gras_dynar_push(p_anc->sub, &p_new));
- TRY(gras_dynar_push(p_anc->sub, &p_child));
- } else {
- TRY(gras_dynar_push(p_anc->sub, &p_child));
- TRY(gras_dynar_push(p_anc->sub, &p_new));
- }
-
- p_child->offset = offset;
-
- TRY(gras_dynar_set(p_head->sub, pos, &p_anc));
-
- return errcode;
- }
-
- default:
- RAISE_IMPOSSIBLE;
- }
-
-}
-
-/**
- * gras_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.
- */
-gras_error_t
-gras_dictelm_set_ext(gras_dictelm_t **pp_head,
- const char *_key,
- int key_len,
- void *data,
- void_f_pvoid_t *free_ctn) {
- gras_error_t errcode = no_error;
- gras_dictelm_t *p_head = *pp_head;
- char *key = NULL;
-
- key = memdup(_key, key_len);
- if (!key)
- RAISE_MALLOC;
-
- /* there is no head, create it */
- if (!p_head) {
- gras_dictelm_t *p_child = NULL;
-
- CDEBUG0(dict_add, "Create an head");
-
- /* The head is priviledged by being the only one with a NULL key */
- TRY(_gras_dictelm_alloc(NULL, 0, 0, NULL, NULL, &p_head));
-
- TRY(_gras_dictelm_alloc(key, key_len, 0, data, free_ctn, &p_child));
- TRY(gras_dynar_insert_at(p_head->sub, 0, &p_child));
-
- *pp_head = p_head;
-
- return errcode;
- }
-
- return _gras_dictelm_set_rec(p_head, key, key_len, 0, data, free_ctn);
-}
-
-/**
- * gras_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.
- */
-gras_error_t
-gras_dictelm_set(gras_dictelm_t **pp_head,
- const char *_key,
- void *data,
- void_f_pvoid_t *free_ctn) {
-
- return gras_dictelm_set_ext(pp_head, _key, 1+strlen(_key), data, free_ctn);
-}
-
-/**
- * _gras_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.
- */
-static
-gras_error_t
-_gras_dictelm_get_rec(gras_dictelm_t *p_head,
- const char *key,
- int key_len,
- int offset,
- /* OUT */void **data) {
-
- gras_error_t errcode = no_error;
-
- CDEBUG2(dict_search, "Search %s in %p", key, p_head);
-
- /*** The trivial case first ***/
-
- /* we did enough recursion, we're done */
- if (offset >= key_len) {
- *data = p_head->content;
-
- return errcode;
- }
-
- {
- 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);
-
- switch (match) {
-
- case 0: /* no child have a common prefix */
- return mismatch_error;
-
- 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 errcode;
- }
-
- case 2: /* A child constitutes a prefix of the key => recurse */
- {
- gras_dictelm_t *p_child = NULL;
-
- gras_dynar_get(p_head->sub, pos, &p_child);
-
- return _gras_dictelm_get_rec(p_child, key, key_len, offset, data);
- }
-
- case 3: /* The key is a prefix of the child => not found */
- return mismatch_error;
-
- case 4: /* A child share a common prefix with this key => not found */
- return mismatch_error;
-
- default:
- RAISE_IMPOSSIBLE;
- }
- }
-}
-
-/**
- * gras_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.
- */
-gras_error_t
-gras_dictelm_get_ext(gras_dictelm_t *p_head,
- const char *key,
- int key_len,
- /* OUT */void **data) {
- /* there is no head, go to hell */
- if (!p_head) {
- return mismatch_error;
- }
-
- return _gras_dictelm_get_rec(p_head, key, key_len, 0, data);
-}
-
-/**
- * gras_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.
- */
-gras_error_t
-gras_dictelm_get(gras_dictelm_t *p_head,
- const char *key,
- /* OUT */void **data) {
-
- return gras_dictelm_get_ext(p_head, key, 1+strlen(key), data);
-}
-
-/*----[ _gras_dict_collapse ]------------------------------------------------*/
-static inline
-void
-_collapse_if_need(gras_dictelm_t *p_head,
- int pos,
- int offset) {
- gras_dictelm_t *p_child = NULL;
-
- CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, p_head); fflush(stdout);
-
- if (pos >= 0) {
- /* Remove the child if |it's key| == 0 (meaning it's dead) */
- gras_dynar_get(p_head->sub, pos, &p_child);
-
- if (offset >= p_child->key_len) {
-
- gras_assert0(gras_dynar_length(p_child->sub) == 0,
- "Found a dead child with grand childs. Internal error");
-
- CDEBUG1(dict_collapse, "Remove dead child %p.... ", p_child);
- gras_dynar_remove_at(p_head->sub, pos, &p_child);
- }
- }
-
- if (!p_head->key) {
- CDEBUG0(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");
- return; /* cannot collapse */
- }
-
- gras_dynar_get(p_head->sub, 0, &p_child);
-
- /* Get the child's key as new key */
- CDEBUG1(dict_collapse, "Do collapse with only child %s", p_child->key);
-
- p_head->content = p_child->content;
- p_head->free_ctn = p_child->free_ctn;
- free(p_head->key);
- p_head->key = p_child->key;
- p_head->key_len = p_child->key_len;
-
- gras_dynar_free_container(p_head->sub) ;
-
- p_head->sub = p_child->sub;
- free(p_child);
-}
-
-/**
- * _gras_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
- */
-gras_error_t
-_gras_dictelm_remove_rec(gras_dictelm_t *p_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);
- }
-
- killme = !gras_dynar_length(p_head->sub);
- p_head->content = NULL;
- p_head->free_ctn = NULL;
- _collapse_if_need(p_head, -1, offset);
-
- if (killme) {
- DEBUG0("kill this node");
- p_head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
- }
-
- return errcode;
-
- } else {
- int match = 0;
- int pos = 0;
- 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);
-
- switch (match) {
-
- case 1: /* A child have exactly this key => recurse */
- case 2: /* A child constitutes a prefix of the key => recurse */
-
- {
- gras_dictelm_t *p_child = NULL;
-
- gras_dynar_get(p_head->sub, pos, &p_child);
- /*DEBUG4("Recurse on child %d of %p to remove %s (prefix=%d)",
- pos, p_child, key+offset, offset);*/
- TRY(_gras_dictelm_remove_rec(p_child, key, key_len, offset));
-
- _collapse_if_need(p_head, pos, old_offset);
- return no_error;
- }
-
-
- 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 */
-
- return mismatch_error;
-
-
- default:
- RAISE_IMPOSSIBLE;
-
- }
- }
-}
-
-/**
- * gras_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
- */
-gras_error_t
-gras_dictelm_remove_ext(gras_dictelm_t *p_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");