/* dict - a generic dictionary, variation over hash table */
-/* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team.
+/* Copyright (c) 2004-2011. The SimGrid Team.
* All rights reserved. */
/* This program is free software; you can redistribute it and/or modify it
XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt,
"Dictionaries provide the same functionalities than hash tables");
-/*####[ Private prototypes ]#################################################*/
-
-static xbt_mallocator_t dict_mallocator = NULL;
-static void *dict_mallocator_new_f(void);
-static void dict_mallocator_free_f(void *dict);
-static void dict_mallocator_reset_f(void *dict);
+/**
+ * \brief Constructor
+ * \return pointer to the destination
+ * \see xbt_dict_free()
+ *
+ * Creates and initialize a new dictionary with a default hashtable size.
+ * The dictionary is heterogeneous: each element can have a different free
+ * function.
+ */
+xbt_dict_t xbt_dict_new(void)
+{
+ xbt_dict_t dict = xbt_dict_new_homogeneous(NULL);
+ dict->homogeneous = 0;
-/*####[ Code ]###############################################################*/
+ return dict;
+}
/**
* \brief Constructor
+ * \param free_ctn function to call with (\a data as argument) when
+ * \a data is removed from the dictionary
* \return pointer to the destination
- * \see xbt_dict_new_ext(), xbt_dict_free()
+ * \see xbt_dict_new(), xbt_dict_free()
*
* Creates and initialize a new dictionary with a default hashtable size.
+ * The dictionary is homogeneous: each element share the same free function.
*/
-xbt_dict_t xbt_dict_new(void)
+xbt_dict_t xbt_dict_new_homogeneous(void_f_pvoid_t free_ctn)
{
xbt_dict_t dict;
- dict = xbt_mallocator_get(dict_mallocator);
+ dict = xbt_new(s_xbt_dict_t, 1);
+ dict->free_f = free_ctn;
dict->table_size = 127;
dict->table = xbt_new0(xbt_dictelm_t, dict->table_size + 1);
dict->count = 0;
dict->fill = 0;
+ dict->homogeneous = 1;
return dict;
}
while (current != NULL) {
previous = current;
current = current->next;
- xbt_dictelm_free(previous);
+ xbt_dictelm_free(*dict, previous);
(*dict)->count--;
}
}
xbt_free(table);
- xbt_mallocator_release(dict_mallocator, *dict);
+ xbt_free(*dict);
*dict = NULL;
}
}
if (current == NULL) {
/* this key doesn't exist yet */
- current = xbt_dictelm_new(key, key_len, hash_code, data, free_ctn);
+ current = xbt_dictelm_new(dict, key, key_len, hash_code, data, free_ctn);
dict->count++;
if (previous == NULL) {
dict->table[hash_code & dict->table_size] = current;
previous->next = current;
}
} else {
-
XBT_DEBUG("Replace %.*s by %.*s under key %.*s",
key_len, (char *) current->content,
key_len, (char *) data, key_len, (char *) key);
/* there is already an element with the same key: overwrite it */
- if (current->content != NULL && current->free_f != NULL) {
- current->free_f(current->content);
- }
- current->content = data;
- current->free_f = free_ctn;
+ xbt_dictelm_set_data(dict, current, data, free_ctn);
}
}
}
if (current == NULL)
- THROW2(not_found_error, 0, "key %.*s not found", key_len, key);
+ THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
return current->content;
}
current = current->next;
if (current == NULL)
- THROW1(not_found_error, 0, "key %s not found", key);
+ THROWF(not_found_error, 0, "key %s not found", key);
return current->content;
}
}
if (current == NULL)
- THROW2(not_found_error, 0, "key %.*s not found", key_len, key);
+ THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
if (previous != NULL) {
previous->next = current->next;
if (!dict->table[hash_code & dict->table_size])
dict->fill--;
- xbt_dictelm_free(current);
+ xbt_dictelm_free(dict, current);
dict->count--;
}
XBT_INLINE void xbt_dicti_set(xbt_dict_t dict,
uintptr_t key, uintptr_t data)
{
-
- unsigned int hash_code =
- xbt_dict_hash_ext((void *) &key, sizeof(uintptr_t));
-
- xbt_dictelm_t current, previous = NULL;
- xbt_assert(dict);
-
- XBT_DEBUG("ADD %zu->%zu; hash = %d, size = %d, & = %d", key, data,
- hash_code, dict->table_size, hash_code & dict->table_size);
- current = dict->table[hash_code & dict->table_size];
- while (current != NULL &&
- (hash_code != current->hash_code
- || sizeof(uintptr_t) != current->key_len
- || (((uintptr_t) key) != ((uintptr_t) current->key)))) {
- previous = current;
- current = current->next;
- }
-
- if (current == NULL) {
- /* this key doesn't exist yet */
- current = xbt_dictielm_new(key, hash_code, data);
- dict->count++;
- if (previous == NULL) {
- dict->table[hash_code & dict->table_size] = current;
- dict->fill++;
- if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT)
- xbt_dict_rehash(dict);
- } else {
- previous->next = current;
- }
- } else {
-
- /* there is already an element with the same key: overwrite it */
- if (current->content != NULL && current->free_f != NULL) {
- current->free_f(current->content);
- }
- current->content = (void *) data;
- current->free_f = NULL;
- }
+ xbt_dict_set_ext(dict, (void *)&key, sizeof key, (void*)data, NULL);
}
/**
*/
XBT_INLINE uintptr_t xbt_dicti_get(xbt_dict_t dict, uintptr_t key)
{
-
- unsigned int hash_code =
- xbt_dict_hash_ext(((void *) &key), sizeof(uintptr_t));
- xbt_dictelm_t current;
-
- xbt_assert(dict);
-
- current = dict->table[hash_code & dict->table_size];
- while (current != NULL &&
- (hash_code != current->hash_code
- || sizeof(uintptr_t) != current->key_len
- || (((uintptr_t) key) != ((uintptr_t) current->key)))) {
- current = current->next;
- }
-
- if (current == NULL)
- return 0;
-
- return (uintptr_t) (current->content);
+ return (uintptr_t)xbt_dict_get_or_null_ext(dict, (void *)&key, sizeof key);
}
/** Remove a uintptr_t key from the dict */
XBT_INLINE void xbt_dicti_remove(xbt_dict_t dict, uintptr_t key)
{
-
- unsigned int hash_code =
- xbt_dict_hash_ext(((void *) &key), sizeof(uintptr_t));
- xbt_dictelm_t current, previous = NULL;
-
-
- current = dict->table[hash_code & dict->table_size];
- while (current != NULL &&
- (hash_code != current->hash_code
- || sizeof(uintptr_t) != current->key_len
- || (((uintptr_t) key) != ((uintptr_t) current->key)))) {
- previous = current; /* save the previous node */
- current = current->next;
- }
-
- if (current == NULL)
- THROW1(not_found_error, 0, "key %zu not found", key);
-
- if (previous != NULL) {
- previous->next = current->next;
- } else {
- dict->table[hash_code & dict->table_size] = current->next;
- }
-
- if (!dict->table[hash_code & dict->table_size])
- dict->fill--;
-
- xbt_dictelm_free(current);
- dict->count--;
+ xbt_dict_remove_ext(dict, (void *)&key, sizeof key);
}
while (current != NULL) {
previous = current;
current = current->next;
- xbt_dictelm_free(previous);
+ xbt_dictelm_free(dict, previous);
}
dict->table[i] = NULL;
}
*/
XBT_INLINE int xbt_dict_is_empty(xbt_dict_t dict)
{
- return (xbt_dict_size(dict) == 0);
+ return !dict || (xbt_dict_length(dict) == 0);
}
/**
while (element != NULL) {
printf(" %s -> '", element->key);
if (output != NULL) {
- (*output) (element->content);
+ output(element->content);
}
printf("'\n");
element = element->next;
*/
void xbt_dict_preinit(void)
{
- if (dict_mallocator != NULL) {
+ if (dict_elm_mallocator != NULL) {
/* Already created. I guess we want to switch to MC mode, so kill the previously created mallocator */
- xbt_mallocator_free(dict_mallocator);
xbt_mallocator_free(dict_elm_mallocator);
+ xbt_mallocator_free(dict_het_elm_mallocator);
}
- dict_mallocator = xbt_mallocator_new(256,
- dict_mallocator_new_f,
- dict_mallocator_free_f,
- dict_mallocator_reset_f);
dict_elm_mallocator = xbt_mallocator_new(256,
dict_elm_mallocator_new_f,
dict_elm_mallocator_free_f,
dict_elm_mallocator_reset_f);
+ dict_het_elm_mallocator = xbt_mallocator_new(256,
+ dict_het_elm_mallocator_new_f,
+ dict_het_elm_mallocator_free_f,
+ dict_het_elm_mallocator_reset_f);
}
/**
*/
void xbt_dict_postexit(void)
{
- if (dict_mallocator != NULL) {
- xbt_mallocator_free(dict_mallocator);
- dict_mallocator = NULL;
+ if (dict_elm_mallocator != NULL) {
xbt_mallocator_free(dict_elm_mallocator);
dict_elm_mallocator = NULL;
+ xbt_mallocator_free(dict_het_elm_mallocator);
+ dict_het_elm_mallocator = NULL;
}
if (all_sizes) {
unsigned int count;
}
}
-static void *dict_mallocator_new_f(void)
-{
- return xbt_new(s_xbt_dict_t, 1);
-}
-
-static void dict_mallocator_free_f(void *dict)
-{
- xbt_free(dict);
-}
-
-static void dict_mallocator_reset_f(void *dict)
-{
- /* nothing to do because all fields are
- * initialized in xbt_dict_new
- */
-}
-
#ifdef SIMGRID_TEST
#include "xbt.h"
#include "xbt/ex.h"
TRY {
data = xbt_dict_get(head, data);
- THROW1(unknown_error, 0,
+ THROWF(unknown_error, 0,
"Found something which shouldn't be there (%s)", data);
- } CATCH(e) {
+ }
+ CATCH(e) {
if (e.category != not_found_error)
xbt_test_exception(e);
xbt_ex_free(e);
static void count_check_get_key(xbt_dict_t dict, int length)
{
xbt_dict_cursor_t cursor;
- char *key, *key2;
+ char *key;
+ _XBT_GNUC_UNUSED char *key2;
void *data;
int effective = 0;
xbt_dict_foreach(dict, cursor, key, data) {
effective++;
key2 = xbt_dict_get_key(dict, data);
- xbt_assert2(!strcmp(key, key2),
+ xbt_assert(!strcmp(key, key2),
"The data was registered under %s instead of %s as expected",
key2, key);
}
traverse(head);
TRY {
debuged_remove(head, "12346");
- } CATCH(e) {
+ }
+ CATCH(e) {
if (e.category != not_found_error)
xbt_test_exception(e);
xbt_ex_free(e);
XBT_TEST_UNIT("crash", test_dict_crash, "Crash test")
{
xbt_dict_t head = NULL;
- int i, j, k, nb;
+ int i, j, k;
char *key;
void *data;
SIZEOFKEY);
head = xbt_dict_new();
/* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
- nb = 0;
for (j = 0; j < 1000; j++) {
char *data = NULL;
key = xbt_malloc(SIZEOFKEY);
