From 5e158336eb3abc9925d13e02d7851cbff00dd095 Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Fri, 25 Nov 2011 18:30:36 +0100 Subject: [PATCH] Rewrite integer dicts using regular dicts. 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 | 90 ++---------------------------------------- src/xbt/dict_elm.c | 26 ++---------- src/xbt/dict_private.h | 5 +-- 3 files changed, 7 insertions(+), 114 deletions(-) diff --git a/src/xbt/dict.c b/src/xbt/dict.c index b7c5b5729b..d4ed6ce906 100644 --- a/src/xbt/dict.c +++ b/src/xbt/dict.c @@ -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); } diff --git a/src/xbt/dict_elm.c b/src/xbt/dict_elm.c index 0591621117..cda2c44aa9 100644 --- a/src/xbt/dict_elm.c +++ b/src/xbt/dict_elm.c @@ -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); diff --git a/src/xbt/dict_private.h b/src/xbt/dict_private.h index 033500f2b8..b403501870 100644 --- a/src/xbt/dict_private.h +++ b/src/xbt/dict_private.h @@ -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_ */ -- 2.20.1