Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Rewrite integer dicts using regular dicts.
authorArnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Fri, 25 Nov 2011 17:30:36 +0000 (18:30 +0100)
committerArnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Thu, 1 Dec 2011 10:30:35 +0000 (11:30 +0100)
The goal here is to reduce the code complexity for further changes.

It's certainly not optimized anymore, but who cares?
Nobody seems to use them anymore.  Integer dicts could be marked as deprecated.

The main difference is that memory is malloc'ed to store a copy of
the key.

src/xbt/dict.c
src/xbt/dict_elm.c
src/xbt/dict_private.h

index b7c5b57..d4ed6ce 100644 (file)
@@ -490,45 +490,7 @@ XBT_INLINE void xbt_dict_remove(xbt_dict_t dict, const char *key)
 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);
 }
 
 /**
@@ -542,59 +504,13 @@ XBT_INLINE void xbt_dicti_set(xbt_dict_t dict,
  */
 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)
-    THROWF(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);
 }
 
 
index 0591621..cda2c44 100644 (file)
@@ -1,6 +1,6 @@
-/* dict - a generic dictionary, variation over the B-tree concept           */
+/* 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
@@ -30,7 +30,6 @@ xbt_dictelm_t xbt_dictelm_new(const char *key,
 {
   xbt_dictelm_t element = xbt_mallocator_get(dict_elm_mallocator);
 
-  element->dictielem = 0;       /* please free the key on free */
   element->key = xbt_new(char, key_len + 1);
   memcpy((void *) element->key, (void *) key, key_len);
   element->key[key_len] = '\0';
@@ -45,29 +44,10 @@ xbt_dictelm_t xbt_dictelm_new(const char *key,
   return element;
 }
 
-xbt_dictelm_t xbt_dictielm_new(uintptr_t key, unsigned int hash_code,
-                               uintptr_t content)
-{
-  xbt_dictelm_t element = xbt_mallocator_get(dict_elm_mallocator);
-
-  element->key = (void *) key;
-
-  element->dictielem = 1;       /* please DONT free the key on free */
-  element->key_len = sizeof(uintptr_t);
-  element->hash_code = hash_code;
-
-  element->content = (void *) content;
-  element->free_f = NULL;
-  element->next = NULL;
-
-  return element;
-}
-
 void xbt_dictelm_free(xbt_dictelm_t element)
 {
   if (element != NULL) {
-    if (!element->dictielem)
-      xbt_free(element->key);
+    xbt_free(element->key);
 
     if (element->free_f != NULL && element->content != NULL) {
       element->free_f(element->content);
index 033500f..b403501 100644 (file)
@@ -1,7 +1,7 @@
 /* dict_elm - elements of generic dictionnaries                             */
 /* This file is not to be loaded from anywhere but dict.c                   */
 
-/* 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
@@ -22,7 +22,6 @@ typedef struct s_xbt_dictelm *xbt_dictelm_t;
 #define MAX_FILL_PERCENT 80
 
 typedef struct s_xbt_dictelm {
-  int dictielem:1;
   char *key;
   int key_len;
   unsigned int hash_code;
@@ -51,8 +50,6 @@ extern void *dict_elm_mallocator_new_f(void);
 xbt_dictelm_t xbt_dictelm_new(const char *key, int key_len,
                               unsigned int hash_code, void *content,
                               void_f_pvoid_t free_f);
-xbt_dictelm_t xbt_dictielm_new(uintptr_t key, unsigned int hash_code,
-                               uintptr_t content);
 void xbt_dictelm_free(xbt_dictelm_t element);
 
 #endif                          /* _XBT_DICT_PRIVATE_H_ */