/* 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 <string.h>
#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
* \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;
+ }
}
/**
* 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);
}
/**
* \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;
}
/**
*
* \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;
}
* \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);
}
/**
*
* 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)
* \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
debuged_add(*head,"1234");
/* Need of common ancestor */
debuged_add(*head,"123457");
-
}
static void search(xbt_dict_t head,const char*key) {
XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrieve, traverse"){
-
xbt_test_add0("Traversal the empty dictionnary");
traverse(head);
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"))
/* 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);
* @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;
}
}
/*
* 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;
+ }
}
/**
* @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;
+ }
}
/**
*
* @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;
}
* @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;
}
/**
* @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;
}
/* 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);
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);
-}
-