/* This program is free software; you can redistribute it and/or modify it
* under the terms of the license (GNU LGPL) which comes with this package. */
+#include "xbt/ex.h"
#include "portable.h" /* PRINTF_STR */
#include "dict_private.h" /* prototypes of this module */
-XBT_LOG_EXTERNAL_CATEGORY(dict);
-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dict_elm,dict,"Dictionaries internals");
+XBT_LOG_EXTERNAL_CATEGORY(xbt_dict);
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict_elm,xbt_dict,"Dictionaries internals");
-XBT_LOG_NEW_SUBCATEGORY(dict_add,dict,"Dictionaries internals: elements addition");
-XBT_LOG_NEW_SUBCATEGORY(dict_search,dict,"Dictionaries internals: searching");
-XBT_LOG_NEW_SUBCATEGORY(dict_remove,dict,"Dictionaries internals: elements removal");
-XBT_LOG_NEW_SUBCATEGORY(dict_collapse,dict,"Dictionaries internals: post-removal cleanup");
-XBT_LOG_NEW_SUBCATEGORY(dict_multi,dict,"Dictionaries internals: dictionaries of dictionaries");
+XBT_LOG_NEW_SUBCATEGORY(xbt_dict_add,xbt_dict,"Dictionaries internals: elements addition");
+XBT_LOG_NEW_SUBCATEGORY(xbt_dict_search,xbt_dict,"Dictionaries internals: searching");
+XBT_LOG_NEW_SUBCATEGORY(xbt_dict_remove,xbt_dict,"Dictionaries internals: elements removal");
+XBT_LOG_NEW_SUBCATEGORY(xbt_dict_collapse,xbt_dict,"Dictionaries internals: post-removal cleanup");
/*####[ Private prototypes ]#################################################*/
int offset,
void *data,
void_f_pvoid_t *free_f);
-static xbt_error_t _xbt_dictelm_get_rec(s_xbt_dictelm_t *head,
- const char *key,
- int key_len,
- int offset,
- /* OUT */void **data);
-static xbt_error_t _xbt_dictelm_remove_rec(s_xbt_dictelm_t *head,
- const char *key,
- int key_len,
- int offset);
+static void * _xbt_dictelm_get_rec(s_xbt_dictelm_t *head,
+ const char *key,
+ int key_len,
+ int offset);
+static void _xbt_dictelm_remove_rec(s_xbt_dictelm_t *head,
+ const char *key,
+ int key_len,
+ int offset);
static _XBT_INLINE
void
/* ---- */
-static _XBT_INLINE
-void *
-xbt_memdup(const void * const ptr,
- const size_t length) {
- void * new_ptr = NULL;
-
- new_ptr = xbt_malloc(length);
- memcpy(new_ptr, ptr, length);
-
- return new_ptr;
-}
-
/*
* _xbt_nibble_to_char:
*
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);
int len = 0;
- CDEBUG6(dict_search, "search child [%.*s] under [%.*s]=%p (len=%lu)",
+ CDEBUG6(xbt_dict_search, "search child [%.*s] under [%.*s]=%p (len=%lu)",
key_len, key,
p_elm ? (p_elm->key_len?p_elm->key_len:6) : 6,
p_elm ? PRINTF_STR(p_elm->key) : "(head)",
*p_offset = o;
*p_pos = p;
*p_match = m;
- CDEBUG6(dict_search, "search [%.*s] in [%.*s]=%p => %s",
+ CDEBUG6(xbt_dict_search, "search [%.*s] in [%.*s]=%p => %s",
key_len, key,
p_elm?(p_elm->key_len?p_elm->key_len:6):6, p_elm?PRINTF_STR(p_elm->key):"(head)",
p_elm,
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)"),
/* there is no key (we did enough recursion), change the value of head */
if (offset >= key_len) {
- CDEBUG0(dict_add, "--> Change the value of head");
+ CDEBUG0(xbt_dict_add, "--> Change the value of head");
_xbt_dictelm_change_value(p_head, data, free_f);
free(key); /* Keep the key used in the tree */
/*** Search where to add this child, and how ***/
_xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
- CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d",
+ CDEBUG3(xbt_dict_add, "child_search => pos=%d, offset=%d, match=%d",
pos, offset, match);
switch (match) {
s_xbt_dictelm_t *p_child = NULL;
_xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_child);
- CDEBUG1(dict_add, "-> Add a child %p", (void*)p_child);
+ CDEBUG1(xbt_dict_add, "-> Add a child %p", (void*)p_child);
xbt_dynar_insert_at(p_head->sub, pos, &p_child);
return;
s_xbt_dictelm_t *p_child = NULL;
p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
- CDEBUG1(dict_add, "-> Change the value of the child %p", (void*)p_child);
+ CDEBUG1(xbt_dict_add, "-> Change the value of the child %p", (void*)p_child);
_xbt_dictelm_change_value(p_child, data, free_f);
free(key);
s_xbt_dictelm_t *p_child = NULL;
p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
- CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset);
+ CDEBUG2(xbt_dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset);
_xbt_dictelm_set_rec(p_child, key, key_len,
offset, data, free_f);
p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
_xbt_dictelm_alloc(key, key_len, old_offset, FALSE, data, free_f, &p_new);
- CDEBUG2(dict_add, "-> The child %p become child of new dict (%p)",
+ CDEBUG2(xbt_dict_add, "-> The child %p become child of new dict (%p)",
(void*)p_child, (void*)p_new);
xbt_dynar_push(p_new->sub, &p_child);
_xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_new);
p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
- anc_key = xbt_memdup(key, anc_key_len);
+ /* memdup the old key, taking care of the terminating NULL byte */
+ anc_key = xbt_malloc(anc_key_len+1);
+ memcpy(anc_key, key, anc_key_len);
+ anc_key[anc_key_len] = '\0';
+
_xbt_dictelm_alloc(anc_key, anc_key_len, old_offset, TRUE, NULL, NULL, &p_anc);
- CDEBUG3(dict_add, "-> Make a common ancestor %p (%.*s)",
+ CDEBUG3(xbt_dict_add, "-> Make a common ancestor %p (%.*s)",
(void*)p_anc, anc_key_len, anc_key);
if (key[offset] < p_child->key[offset]) {
}
default:
- DIE_IMPOSSIBLE;
+ THROW_IMPOSSIBLE;
}
}
s_xbt_dictelm_t *p_head = *pp_head;
char *key = NULL;
- key = xbt_memdup(_key, key_len+1);
+ /* Make sure the copied key is NULL-terminated */
+ key = xbt_malloc(key_len+1);
+ memcpy(key, _key, key_len);
+ key[key_len] = '\0';
/* there is no head, create it */
if (!p_head) {
s_xbt_dictelm_t *p_child = NULL;
- CDEBUG0(dict_add, "Create an head");
+ CDEBUG0(xbt_dict_add, "Create an head");
/* The head is priviledged by being the only one with a NULL key */
_xbt_dictelm_alloc(NULL, 0, 0, TRUE, NULL, NULL, &p_head);
- CDEBUG2(dict_add, "Push %.*s as child of this head",key_len,key);
+ CDEBUG2(xbt_dict_add, "Push %.*s as child of this head",key_len,key);
_xbt_dictelm_alloc(key, key_len, 0, FALSE, data, free_f, &p_child);
xbt_dynar_insert_at(p_head->sub, 0, &p_child);
* @key: the key to find data
* @offset: offset on the key
* @data: the data that we are looking for
- * @Returns: xbt_error
*
- * Search the given @key. mismatch_error when not found.
+ * Search the given @key. Throws not_found_error when not found.
*/
static
-xbt_error_t
+void *
_xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head,
const char *key,
int key_len,
- int offset,
- void **data) {
+ int offset) {
- CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, (void*)p_head);
+ CDEBUG3(xbt_dict_search, "Search %.*s in %p", key_len, key, (void*)p_head);
/*** The trivial case first ***/
/* we did enough recursion, we're done */
if (offset >= key_len) {
- *data = p_head->content;
-
- return no_error;
+ return p_head->content;
}
{
int match = 0;
int pos = 0;
- *data = NULL; /* Let's be clean */
-
/*** Search where is the good child, and how good it is ***/
_xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
switch (match) {
case 0: /* no child have a common prefix */
- return mismatch_error;
+ THROW2(not_found_error,0,"key '%.*s' not found",key_len,key);
case 1: /* A child have exactly this key => Got it */
{
s_xbt_dictelm_t *p_child = NULL;
-
p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
- *data = p_child->content;
-
- return no_error;
+ return p_child->content;
}
case 2: /* A child constitutes a prefix of the key => recurse */
p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
- return _xbt_dictelm_get_rec(p_child, key, key_len, offset, data);
+ return _xbt_dictelm_get_rec(p_child, key, key_len, offset);
}
case 3: /* The key is a prefix of the child => not found */
- return mismatch_error;
+ THROW2(not_found_error,0,"key %.*s not found",key_len,key);
case 4: /* A child share a common prefix with this key => not found */
- return mismatch_error;
+ THROW2(not_found_error,0,"key %.*s not found",key_len,key);
default:
- RAISE_IMPOSSIBLE;
+ THROW_IMPOSSIBLE;
}
}
}
* @head: the head of the dict
* @key: the key to find data
* @data: the data that we are looking for
- * @Returns: xbt_error
*
- * Search the given @key. mismatch_error when not found.
+ * Search the given @key. Throws not_found_error when not found.
*/
-xbt_error_t
+void *
xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head,
- const char *key,
- int key_len,
- /* OUT */void **data) {
+ const char *key,
+ int key_len) {
/* there is no head, go to hell */
- if (!p_head) {
- return mismatch_error;
- }
+ if (!p_head)
+ THROW2(not_found_error,0,"Key '%.*s' not found in dict",key_len,key);
- return _xbt_dictelm_get_rec(p_head, key, key_len, 0, data);
+ return _xbt_dictelm_get_rec(p_head, key, key_len, 0);
}
/**
* @head: the head of the dict
* @key: the key to find data
* @data: the data that we are looking for
- * @Returns: xbt_error
*
- * Search the given @key. mismatch_error when not found.
+ * Search the given @key. Throws not_found_error when not found.
*/
-xbt_error_t
-xbt_dictelm_get(s_xbt_dictelm_t *p_head,
- const char *key,
- /* OUT */void **data) {
+void *
+xbt_dictelm_get(s_xbt_dictelm_t *p_head,
+ const char *key) {
- return xbt_dictelm_get_ext(p_head, key, strlen(key), data);
+ return xbt_dictelm_get_ext(p_head, key, strlen(key));
}
/*----[ _xbt_dict_collapse ]------------------------------------------------*/
int offset) {
xbt_dictelm_t child = NULL;
- CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, (void*)head);
+ CDEBUG2(xbt_dict_collapse, "Collapse %d of %p... ", pos, (void*)head);
if (pos >= 0) {
/* Remove the child if |it's key| == 0 (meaning it's dead) */
xbt_assert0(xbt_dynar_length(child->sub) == 0,
"Found a dead child with grand childs. Internal error");
- CDEBUG1(dict_collapse, "Remove dead child %p.... ", (void*)child);
+ CDEBUG1(xbt_dict_collapse, "Remove dead child %p.... ", (void*)child);
xbt_dynar_remove_at(head->sub, pos, &child);
xbt_dictelm_free(&child);
}
}
if (!head->key) {
- CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
+ CDEBUG0(xbt_dict_collapse, "Do not collapse the head, you stupid programm");
return;
}
if (head->content || head->free_f ||
xbt_dynar_length(head->sub) != 1) {
- CDEBUG0(dict_collapse, "Cannot collapse");
+ CDEBUG0(xbt_dict_collapse, "Cannot collapse");
return; /* cannot collapse */
}
child = xbt_dynar_get_as(head->sub, 0, xbt_dictelm_t);
/* Get the child's key as new key */
- CDEBUG2(dict_collapse,
+ CDEBUG2(xbt_dict_collapse,
"Do collapse with only child %.*s", child->key_len, child->key);
head->content = child->content;
* @head: the head of the dict
* @key: the key of the data to be removed
* @offset: offset on the key
- * @Returns: xbt_error_t
*
- * Remove the entry associated with the given @key
+ * Remove the entry associated with the given @key. Throws not_found_error.
*/
-xbt_error_t
+void
_xbt_dictelm_remove_rec(xbt_dictelm_t head,
const char *key,
int key_len,
int offset) {
- xbt_error_t errcode = no_error;
/* there is no key to search, we did enough recursion => kill current */
if (offset >= key_len) {
head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
}
- return errcode;
+ return;
} else {
int match = 0;
p_child = xbt_dynar_get_as(head->sub, pos, s_xbt_dictelm_t*);
/*DEBUG5("Recurse on child %d of %p to remove %.*s (prefix=%d)",
pos, (void*)p_child, key+offset, key_len-offset,offset);*/
- TRY(_xbt_dictelm_remove_rec(p_child, key, key_len, offset));
+ _xbt_dictelm_remove_rec(p_child, key, key_len, offset);
_collapse_if_need(head, pos, old_offset);
- return no_error;
+ return;
}
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;
}
}
*
* @head: the head of the dict
* @key: the key of the data to be removed
- * @Returns: xbt_error_t
*
- * Remove the entry associated with the given @key
+ * Remove the entry associated with the given @key. Throws not_found_err
*/
-xbt_error_t
+void
xbt_dictelm_remove_ext(xbt_dictelm_t head,
const char *key,
int key_len) {
/* there is no head, go to hell */
- if (!head) {
- RAISE0(mismatch_error, "there is no head, go to hell");
- }
+ if (!head)
+ THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key);
- return _xbt_dictelm_remove_rec(head, key, key_len, 0);
+ _xbt_dictelm_remove_rec(head, key, key_len, 0);
}
/**
*
* @head: the head of the dict
* @key: the key of the data to be removed
- * @Returns: xbt_error_t
*
- * Remove the entry associated with the given @key
+ * Throws not_found when applicable
*/
-xbt_error_t
+void
xbt_dictelm_remove(xbt_dictelm_t head,
const char *key) {
- return _xbt_dictelm_remove_rec(head, key, strlen(key),0);
+ _xbt_dictelm_remove_rec(head, key, strlen(key),0);
}
/*----[ _xbt_dict_dump_rec ]------------------------------------------------*/
*
* @head: the head of the dict
* @output: a function to dump each data in the tree
- * @Returns: xbt_error_t
*
* Ouputs the content of the structure. (for debuging purpose). @ouput is a
* function to output the data. If NULL, data won't be displayed.
