X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/9d96798dd6a87fb575d8d22612d18a79f3e1d309..bd6274487954af16de90c357090e2d698d886cd1:/src/xbt/dict.c

diff --git a/src/xbt/dict.c b/src/xbt/dict.c
index a673500b3b..c28171f432 100644
--- a/src/xbt/dict.c
+++ b/src/xbt/dict.c
@@ -7,43 +7,114 @@
 /* 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(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;
+  }
+  dict->count = 0;
+
+  return dict;
+}
+
+/**
+ * \brief Destructor
+ * \param dict the dictionnary to be freed
+ *
+ * Frees a dictionary with all the data
+ */
+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);
+      }
+    }
+    xbt_free((*dict)->table);
+    xbt_free(*dict);
+    *dict = NULL;
+  }
 }
+
 /**
- * @brief Destructor
- * @param dict the dictionnary to be freed
+ * \brief Change the hashtable size
+ * \param dict a dictionary
+ * \param hashsize the new hashtable size
  *
- * Frees a cache structure with all its childs.
+ * 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_free(xbt_dict_t *dict)  {
-  if (dict && *dict) {
-    if ((*dict)->head) {
-      xbt_dictelm_free( &( (*dict)->head ) );
-      (*dict)->head = NULL;
+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;
     }
-    free(*dict);
-    *dict=NULL;
   }
+
+  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;
 }
 
 /**
@@ -55,26 +126,51 @@ xbt_dict_free(xbt_dict_t *dict)  {
  * \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;
+    }
+    dict->count++;
+  }
+  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;
+  }
 }
 
 /**
  * \brief Add data to the dict (null-terminated key)
  *
- * \param dict the head of the dict
+ * \param dict the dict
  * \param key the key to set the new data
  * \param data the data to add in the dict
  * \param free_ctn function to call with (\a key as argument) when 
@@ -83,15 +179,14 @@ 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,
-	      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);
 }
 
 /**
@@ -100,18 +195,29 @@ xbt_dict_set(xbt_dict_t     dict,
  * \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;
 }
 
 /**
@@ -119,37 +225,47 @@ xbt_dict_get_ext(xbt_dict_t      dict,
  *
  * \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);
+  unsigned int hash_code = xbt_dict_hash(key) % dict->table_size;
+  xbt_dictelm_t current;
+
+  current = dict->table[hash_code];
+  while (current != NULL && (strcmp(key, current->key))) {
+    current = current->next;
+  }
+
+  if (current == NULL) {
+    THROW1(not_found_error, 0, "key %s not found", key);
+  }
+
+  return current->content;
 }
 
 /**
  * \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;
 }
 
 
@@ -159,36 +275,97 @@ xbt_dict_get_or_null(xbt_dict_t     dict,
  * \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);
+  dict->count--;
 }
 
 /**
  * \brief Remove data from the dict (null-terminated key)
  *
- * \param dict the head of the dict
+ * \param dict the dict
  * \param key the key of the data to be removed
  *
  * Remove the entry associated with the given \a 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);
+void xbt_dict_remove(xbt_dict_t  dict,
+		     const char  *key) {
+  xbt_assert(dict);
 
-  xbt_dictelm_remove(dict->head, key);
+  xbt_dict_remove_ext(dict, key, strlen(key));
 }
 
+/**
+ * \brief Remove all data from the dict
+ * \param dict the dict
+ */
+void xbt_dict_reset(xbt_dict_t dict) {
+  xbt_assert(dict);
+
+  int i;
+  xbt_dictelm_t current, previous = 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);
+    }
+    dict->table[i] = NULL;
+  }
+
+  dict->count = 0;
+}
+
+/**
+ * \brief Return the number of elements in the dict.
+ * \param dict a dictionary
+ */
+int xbt_dict_length(xbt_dict_t dict) {
+  xbt_assert(dict);
+
+  return dict->count;
+}
+
+/*
+ * 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) 
@@ -197,15 +374,27 @@ xbt_dict_remove(xbt_dict_t  dict,
  * \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
@@ -213,8 +402,8 @@ xbt_dict_dump(xbt_dict_t     dict,
 #include "xbt/ex.h"
 #include "portable.h"
 
-XBT_LOG_EXTERNAL_CATEGORY(dict);
-XBT_LOG_DEFAULT_CATEGORY(dict);
+XBT_LOG_EXTERNAL_CATEGORY(xbt_dict);
+XBT_LOG_DEFAULT_CATEGORY(xbt_dict);
 
 XBT_TEST_SUITE("dict","Dict data container");
 
@@ -229,7 +418,7 @@ static void debuged_add(xbt_dict_t head,const char*key)
   xbt_test_log1("Add %s",PRINTF_STR(key));
 
   xbt_dict_set(head,key,data,&free);
-  if (XBT_LOG_ISENABLED(dict,xbt_log_priority_debug)) {
+  if (XBT_LOG_ISENABLED(xbt_dict,xbt_log_priority_debug)) {
     xbt_dict_dump(head,(void (*)(void*))&printf);
     fflush(stdout);
   }
@@ -248,7 +437,6 @@ static void fill(xbt_dict_t *head) {
   debuged_add(*head,"1234");
   /* Need of common ancestor */
   debuged_add(*head,"123457");
-
 }
 
 static void search(xbt_dict_t head,const char*key) {
@@ -296,18 +484,23 @@ static void search_not_found(xbt_dict_t head, const char *data) {
   }
 }
 
+static void count(xbt_dict_t dict, int length) {
+  xbt_test_add1("Count elements (expecting %d)", length);
+  xbt_test_assert2(xbt_dict_length(dict) == length, "Length(%d) != %d.", xbt_dict_length(dict), length);
+}
+
 xbt_ex_t e;
 xbt_dict_t head=NULL;
 char *data;
 
 
-XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrive, traverse"){
-
+XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrieve, traverse"){
   xbt_test_add0("Traversal the empty dictionnary");
   traverse(head);
 
   xbt_test_add0("Traverse the full dictionnary");
   fill(&head);
+  count(head, 7);
 
   search(head,"12a");
   traverse(head);
@@ -318,22 +511,27 @@ XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrive, traverse"){
 
   /* CHANGING */
   fill(&head);
+  count(head, 7);
   xbt_test_add0("Change 123 to 'Changed 123'");
   xbt_dict_set(head,"123",strdup("Changed 123"),&free);
+  count(head, 7);
 
   xbt_test_add0("Change 123 back to '123'");
   xbt_dict_set(head,"123",strdup("123"),&free);
+  count(head, 7);
 
   xbt_test_add0("Change 12a to 'Dummy 12a'");
   xbt_dict_set(head,"12a",strdup("Dummy 12a"),&free);
+  count(head, 7);
 
   xbt_test_add0("Change 12a to '12a'");
   xbt_dict_set(head,"12a",strdup("12a"),&free);
+  count(head, 7);
 
   xbt_test_add0("Traverse the resulting dictionnary");
   traverse(head);
   
-  /* RETRIVE */
+  /* RETRIEVE */
   xbt_test_add0("Search 123");
   data = xbt_dict_get(head,"123");
   xbt_test_assert(data);
@@ -365,6 +563,7 @@ XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrive, traverse"){
 
 XBT_TEST_UNIT("remove",test_dict_remove,"Removing some values"){
   fill(&head);
+  count(head, 7);
   xbt_test_add0("Remove non existing data");
   TRY {
     debuged_remove(head,"Does not exist");
@@ -377,21 +576,16 @@ XBT_TEST_UNIT("remove",test_dict_remove,"Removing some values"){
 
   xbt_dict_free(&head);
 
-  xbt_test_add0("Remove data from the NULL dict");
-  TRY {
-    debuged_remove(head,"12345");
-  } CATCH(e) {
-    if (e.category != arg_error) 
-      xbt_test_exception(e);
-    xbt_ex_free(e);
-  } 
-
   xbt_test_add0("Remove each data manually (traversing the resulting dictionnary each time)");
   fill(&head);
   debuged_remove(head,"12a");    traverse(head);
+  count(head, 6);
   debuged_remove(head,"12b");    traverse(head);
+  count(head, 5);
   debuged_remove(head,"12");     traverse(head);
+  count(head, 4);
   debuged_remove(head,"123456"); traverse(head);
+  count(head, 3);
   TRY {
     debuged_remove(head,"12346");
   } CATCH(e) {
@@ -411,6 +605,13 @@ XBT_TEST_UNIT("remove",test_dict_remove,"Removing some values"){
     xbt_ex_free(e);
   }                              traverse(head);
   
+  xbt_test_add0("Remove all values");
+  xbt_dict_free(&head);
+  fill(&head);
+  xbt_dict_reset(head);
+  count(head, 0);
+  traverse(head);
+
   xbt_test_add0("Free the dictionnary twice");
   xbt_dict_free(&head);
   xbt_dict_free(&head);      
@@ -428,7 +629,7 @@ XBT_TEST_UNIT("nulldata",test_dict_nulldata,"NULL data management"){
     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"))