X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/67ebbc00442335b3f92177183bbbbb4574e35bf0..c383fa6fa203659a428a59e74522daca845dd1c6:/src/xbt/dict.c

diff --git a/src/xbt/dict.c b/src/xbt/dict.c
index 1ef05f0613..21b8f6019b 100644
--- a/src/xbt/dict.c
+++ b/src/xbt/dict.c
@@ -1,8 +1,6 @@
-/* $Id$ */
+/* dict - a generic dictionary, variation over hash table                   */
 
-/* dict - a generic dictionary, variation over the B-tree concept          */
-
-/* Copyright (c) 2003,2004 Martin Quinson. All rights reserved.             */
+/* Copyright (c) 2003-2010 Martin Quinson. All rights reserved.             */
 
 /* 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. */
@@ -100,7 +98,7 @@ void xbt_dict_free(xbt_dict_t * dict)
 /**
  * Returns the amount of elements in the dict
  */
-unsigned int xbt_dict_size(xbt_dict_t dict)
+XBT_INLINE unsigned int xbt_dict_size(xbt_dict_t dict)
 {
   return dict->count;
 }
@@ -297,7 +295,7 @@ XBT_INLINE void xbt_dict_set_ext(xbt_dict_t dict,
  * 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,
+XBT_INLINE void xbt_dict_set(xbt_dict_t dict,
                   const char *key, void *data, void_f_pvoid_t free_ctn)
 {
 
@@ -314,7 +312,7 @@ void xbt_dict_set(xbt_dict_t dict,
  *
  * 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)
+XBT_INLINE void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len)
 {
 
 
@@ -341,6 +339,7 @@ void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len)
  */
 void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len)
 {
+
   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
   xbt_dictelm_t current;
 
@@ -392,7 +391,7 @@ char *xbt_dict_get_key(xbt_dict_t dict, const void*data) {
  * 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)
+XBT_INLINE void *xbt_dict_get(xbt_dict_t dict, const char *key)
 {
 
   unsigned int hash_code = xbt_dict_hash(key);
@@ -414,7 +413,7 @@ void *xbt_dict_get(xbt_dict_t dict, const char *key)
 /**
  * \brief like xbt_dict_get(), but returning NULL when not found
  */
-void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key)
+XBT_INLINE void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key)
 {
   unsigned int hash_code = xbt_dict_hash(key);
   xbt_dictelm_t current;
@@ -442,7 +441,7 @@ void *xbt_dict_get_or_null(xbt_dict_t dict, const char *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)
+XBT_INLINE void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len)
 {
 
 
@@ -476,6 +475,8 @@ void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len)
   dict->count--;
 }
 
+
+
 /**
  * \brief Remove data from the dict (null-terminated key)
  *
@@ -484,11 +485,124 @@ void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len)
  *
  * Remove the entry associated with the given \a key
  */
-void xbt_dict_remove(xbt_dict_t dict, const char *key)
+XBT_INLINE void xbt_dict_remove(xbt_dict_t dict, const char *key)
 {
   xbt_dict_remove_ext(dict, key, strlen(key));
 }
 
+/**
+ * \brief Add data to the dict (arbitrary key)
+ * \param dict the container
+ * \param key the key to set the new data
+ * \param key_len the size of the \a key
+ * \param data the data to add in the dict
+ * \param free_ctn function to call with (\a key as argument) when
+ *        \a key is removed from the dictionary
+ *
+ * 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.
+ */
+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);
+
+  DEBUG5("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)) )) {
+    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;
+  }
+}
+
+/**
+ * \brief Retrieve data from the dict (key considered as a uintptr_t)
+ *
+ * \param dict the dealer of data
+ * \param key the key to find data
+ * \return the data that we are looking for (or 0 if not found)
+ *
+ * Mixing uintptr_t keys with regular keys in the same dict is discouraged
+ */
+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);
+}
+
+/** 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--;
+}
+
+
 /**
  * \brief Remove all data from the dict
  * \param dict the dict
@@ -522,7 +636,7 @@ void xbt_dict_reset(xbt_dict_t dict)
  * \brief Return the number of elements in the dict.
  * \param dict a dictionary
  */
-int xbt_dict_length(xbt_dict_t dict)
+XBT_INLINE int xbt_dict_length(xbt_dict_t dict)
 {
   xbt_assert(dict);
 
@@ -1035,6 +1149,45 @@ XBT_TEST_UNIT("nulldata", test_dict_nulldata, "NULL data management")
   xbt_dict_free(&head);
 }
 
+static void debuged_addi(xbt_dict_t head, uintptr_t key, uintptr_t data) {
+  xbt_test_log2("Add %zu under %zu", data, key);
+
+  xbt_dicti_set(head, key, data);
+  if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
+    xbt_dict_dump(head, (void (*)(void *)) &printf);
+    fflush(stdout);
+  }
+  uintptr_t stored_data = xbt_dicti_get(head, key);
+  xbt_test_assert3(stored_data==data,
+      "Retrieved data (%zu) is not what I just stored (%zu) under key %zu",stored_data,data,key);
+}
+
+XBT_TEST_UNIT("dicti", test_dict_scalar, "Scalar data and key management")
+{
+  xbt_test_add0("Fill in the dictionnary");
+
+  head = xbt_dict_new();
+  debuged_addi(head, 12, 12);
+  debuged_addi(head, 13, 13);
+  debuged_addi(head, 14, 14);
+  debuged_addi(head, 15, 15);
+  /* Change values */
+  debuged_addi(head, 12, 15);
+  debuged_addi(head, 15, 2000);
+  debuged_addi(head, 15, 3000);
+  /* 0 as key */
+  debuged_addi(head, 0, 1000);
+  debuged_addi(head, 0, 2000);
+  debuged_addi(head, 0, 3000);
+  /* 0 as value */
+  debuged_addi(head, 12, 0);
+  debuged_addi(head, 13, 0);
+  debuged_addi(head, 12, 0);
+  debuged_addi(head, 0, 0);
+
+  xbt_dict_free(&head);
+}
+
 #define NB_ELM 20000
 #define SIZEOFKEY 1024
 static int countelems(xbt_dict_t head)