Menu
▾
▴
E CVS: libs/ewd rbdpngn
|
From: <enl...@li...> - 2001-06-12 19:42:42
|
Enlightenment CVS committal
Author : rbdpngn
Project : e17
Module : libs/ewd
Dir : e17/libs/ewd/src
Modified Files:
Makefile.am ewd_dlist.c ewd_hash.c ewd_hash.h ewd_macros.h
ewd_threads.h ewd_tree.c
Log Message:
Hash table should be working now, fixed a few issues in the debugging macros,
fixed up the thread code a bit, and lots of small fixes and tweaks. Still need
to work out some performance issues in the hash table.
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/Makefile.am,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -3 -r1.6 -r1.7
--- Makefile.am 2001/05/02 04:14:04 1.6
+++ Makefile.am 2001/06/12 19:42:11 1.7
@@ -15,6 +15,8 @@
ewd_value.h \
../ewd-config.h
+libewd_la_CFLAGS = -O6
+
libewd_la_SOURCES = \
ewd_dlist.c \
ewd_hash.c \
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_dlist.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- ewd_dlist.c 2001/05/01 18:00:10 1.2
+++ ewd_dlist.c 2001/06/12 19:42:11 1.3
@@ -48,7 +48,7 @@
void *data;
CHECK_PARAM_POINTER("list", list);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
while (list->first) {
data = _ewd_dlist_remove_first(list);
@@ -56,7 +56,7 @@
list->free_func(data);
}
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
EWD_DESTROY_LOCKS(list);
FREE(list);
@@ -127,7 +127,7 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
prev = EWD_LIST(list)->last;
ret = _ewd_list_append(EWD_LIST(list), data);
@@ -136,7 +136,7 @@
EWD_DLIST_NODE(prev);
}
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -154,7 +154,7 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
prev = EWD_LIST(list)->first;
ret = _ewd_list_prepend(EWD_LIST(list), data);
@@ -162,7 +162,7 @@
EWD_DLIST_NODE(prev)->previous =
EWD_DLIST_NODE(EWD_LIST(list)->first);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -181,7 +181,7 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
index = ewd_list_index(EWD_LIST(list));
current = EWD_LIST(list)->current;
@@ -194,7 +194,7 @@
_ewd_list_goto_index(EWD_LIST(list), index + 1);
}
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -211,7 +211,7 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
if (list->current) {
node = list->current->next;
@@ -220,7 +220,7 @@
}
ret = _ewd_list_remove(list);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -236,9 +236,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
ret = _ewd_dlist_remove_first(list);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -280,9 +280,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
ret = _ewd_list_remove_last(list);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -299,9 +299,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
ret = _ewd_dlist_goto_index(list, index);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -348,9 +348,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
ret = _ewd_list_goto(EWD_LIST(list), data);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -366,9 +366,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
ret = _ewd_list_goto_first(list);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -384,9 +384,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
ret = _ewd_list_goto_last(EWD_LIST(list));
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return ret;
}
@@ -400,9 +400,9 @@
{
void *ret;
- EWD_READ_LOCK_STRUCT(list);
+ EWD_READ_LOCK(list);
ret = _ewd_list_current(EWD_LIST(list));
- EWD_READ_UNLOCK_STRUCT(list);
+ EWD_READ_UNLOCK(list);
return ret;
}
@@ -416,9 +416,9 @@
{
void *data;
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
data = _ewd_list_next(list);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return data;
}
@@ -432,9 +432,9 @@
{
void *data;
- EWD_WRITE_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK(list);
data = _ewd_dlist_previous(list);
- EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK(list);
return data;
}
@@ -469,11 +469,11 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_READ_LOCK_STRUCT(list);
+ EWD_READ_LOCK(list);
ret = _ewd_list_for_each(list, function);
- EWD_READ_UNLOCK_STRUCT(list);
+ EWD_READ_UNLOCK(list);
return ret;
}
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_hash.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- ewd_hash.c 2001/05/01 18:00:10 1.2
+++ ewd_hash.c 2001/06/12 19:42:11 1.3
@@ -1,43 +1,31 @@
#include <Ewd.h>
+#define EWD_HASH_CHAIN_MAX 3
+
#define EWD_HASH_INCREASE(hash) ((hash && hash->size < PRIME_MAX) ? \
- ((double)hash->nodes / (double)ewd_prime_table[hash->size]) > \
+ (hash->nodes / ewd_prime_table[hash->size]) > \
EWD_HASH_CHAIN_MAX : FALSE)
#define EWD_HASH_REDUCE(hash) ((hash && hash->size > PRIME_MIN) ? \
(double)hash->nodes / (double)ewd_prime_table[hash->size-1] \
- < ((double)EWD_HASH_CHAIN_MAX * 3.0 / 8.0) : FALSE)
-
-#define EWD_HASH_KEY_IN_TABLE(table, key) (table == NULL ? FALSE : \
- ((key < (table->base + table->size)) && (key >= table->base)))
-
-#define FIND_TABLE(index) (index > PRIME_MIN ? \
- ((log((double)index) / log(2.0)) - 4) : 0)
+ < ((double)EWD_HASH_CHAIN_MAX * 0.375) : FALSE)
/* Private hash manipulation functions */
-static int ewd_hash_add_node(Ewd_Hash *hash, Ewd_Hash_Node *node);
-static Ewd_Hash_Node * ewd_hash_get_node(Ewd_Hash *hash, void *key);
-static int ewd_hash_increase(Ewd_Hash *hash);
-static int ewd_hash_decrease(Ewd_Hash *hash);
-static Ewd_Hash_Node *ewd_hash_get_with_size(Ewd_Hash *hash, void *key,
- int size);
-static int ewd_hash_find_table(Ewd_Hash *hash, unsigned int index);
-static Ewd_Hash_Node *ewd_hash_get_bucket(Ewd_Hash *hash, Ewd_List *bucket,
+static int _ewd_hash_add_node(Ewd_Hash *hash, Ewd_Hash_Node *node);
+static Ewd_Hash_Node * _ewd_hash_get_node(Ewd_Hash *hash, void *key);
+static int _ewd_hash_increase(Ewd_Hash *hash);
+static int _ewd_hash_decrease(Ewd_Hash *hash);
+inline int _ewd_hash_rehash(Ewd_Hash *hash, Ewd_List **old_table, int old_size);
+static int _ewd_hash_bucket_destroy(Ewd_List *list, Ewd_Free_Cb keyd,
+ Ewd_Free_Cb valued);
+inline Ewd_Hash_Node * _ewd_hash_get_bucket(Ewd_Hash *hash, Ewd_List *bucket,
void *key);
-static int ewd_hash_table_rehash(Ewd_Hash *hash, Ewd_Hash_Table *table);
-
-/* Private hash table manipulation functions */
-static Ewd_Hash_Table *ewd_hash_table_new(int size);
-static int ewd_hash_table_init(Ewd_Hash_Table *table, int size);
-static int ewd_hash_table_destroy(Ewd_Hash_Table *table, Ewd_Free_Cb keyd,
- Ewd_Free_Cb valued);
-static Ewd_Hash_Node *ewd_hash_node_new(void *key, void *value);
-static int ewd_hash_node_init(Ewd_Hash_Node *node, void *key, void *value);
-static int ewd_hash_node_destroy(Ewd_Hash_Node *node, Ewd_Free_Cb keyd,
+static Ewd_Hash_Node *_ewd_hash_node_new(void *key, void *value);
+static int _ewd_hash_node_init(Ewd_Hash_Node *node, void *key, void *value);
+static int _ewd_hash_node_destroy(Ewd_Hash_Node *node, Ewd_Free_Cb keyd,
Ewd_Free_Cb valued);
-
/*
* Description: Create and initialize a new hash
* Parameters: 1. hash_func - the function for determining hash position
@@ -76,7 +64,9 @@
if (compare)
hash->compare = compare;
- hash->tables[0] = ewd_hash_table_new(ewd_prime_table[0]);
+ hash->buckets = (Ewd_List **)malloc(ewd_prime_table[0] *
+ sizeof(Ewd_List *));
+ memset(hash->buckets, 0, ewd_prime_table[0] * sizeof(Ewd_List *));
EWD_INIT_LOCKS(hash);
@@ -94,7 +84,9 @@
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
CHECK_PARAM_POINTER_RETURN("function", function, FALSE);
+ EWD_WRITE_LOCK(hash);
hash->free_key = function;
+ EWD_WRITE_UNLOCK(hash);
return TRUE;
}
@@ -110,7 +102,9 @@
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
CHECK_PARAM_POINTER_RETURN("function", function, FALSE);
+ EWD_WRITE_LOCK(hash);
hash->free_value = function;
+ EWD_WRITE_UNLOCK(hash);
return TRUE;
}
@@ -130,14 +124,16 @@
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
- node = ewd_hash_get_node(hash, key);
+ EWD_WRITE_LOCK(hash);
+ node = _ewd_hash_get_node(hash, key);
if (node)
node->value = value;
else {
- node = ewd_hash_node_new(key, value);
+ node = _ewd_hash_node_new(key, value);
if (node)
- ret = ewd_hash_add_node(hash, node);
+ ret = _ewd_hash_add_node(hash, node);
}
+ EWD_WRITE_UNLOCK(hash);
return ret;
}
@@ -153,15 +149,15 @@
CHECK_PARAM_POINTER("hash", hash);
- EWD_WRITE_LOCK_STRUCT(hash);
+ EWD_WRITE_LOCK(hash);
- while (i <= hash->size) {
- ewd_hash_table_destroy(hash->tables[i], hash->free_key,
- hash->free_value);
+ while (i < ewd_prime_table[hash->size]) {
+ _ewd_hash_bucket_destroy(hash->buckets[i],
+ hash->free_key, hash->free_value);
i++;
}
- EWD_WRITE_UNLOCK_STRUCT(hash);
+ EWD_WRITE_UNLOCK(hash);
EWD_DESTROY_LOCKS(hash);
FREE(hash);
@@ -169,31 +165,15 @@
return;
}
-/*
- * Description: Free the hash table and the data contained inside it
- * Parameters: 1. table - the table to destroy
- * Returns: TRUE on success, FALSE on error
- */
static int
-ewd_hash_table_destroy(Ewd_Hash_Table *table, Ewd_Free_Cb keyd,
- Ewd_Free_Cb valued)
+_ewd_hash_bucket_destroy(Ewd_List *list, Ewd_Free_Cb keyd, Ewd_Free_Cb valued)
{
- int i;
- Ewd_List *list;
+ Ewd_Hash_Node *node;
- CHECK_PARAM_POINTER_RETURN("table", table, FALSE);
+ CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- for (i = 0; i < table->size; i++) {
- Ewd_Hash_Node *node;
- list = table->table[i];
-
- if (list) {
- ewd_list_goto_first(list);
- while ((node = EWD_HASH_NODE(ewd_list_next(list)))
- != NULL)
- ewd_hash_node_destroy(node, keyd, valued);
- }
- }
+ while ((node = ewd_list_remove_first(list)) != NULL)
+ _ewd_hash_node_destroy(node, keyd, valued);
return TRUE;
}
@@ -205,10 +185,8 @@
* Returns: FALSE on error, TRUE on success
*/
static int
-ewd_hash_add_node(Ewd_Hash *hash, Ewd_Hash_Node *node)
+_ewd_hash_add_node(Ewd_Hash *hash, Ewd_Hash_Node *node)
{
- int i = 0;
- Ewd_Hash_Table *table;
unsigned int hash_val;
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
@@ -216,41 +194,20 @@
/* Check to see if the hash needs to be resized */
if (EWD_HASH_INCREASE(hash))
- ewd_hash_increase(hash);
+ _ewd_hash_increase(hash);
else if (EWD_HASH_REDUCE(hash))
- ewd_hash_decrease(hash);
+ _ewd_hash_decrease(hash);
/* Compute the position in the table */
hash_val = hash->hash_func(node->key) % ewd_prime_table[hash->size];
-
- /* Traverse the list of tables until the one containing calculated
- * index is reached */
- /*
- while (i <= hash->size && !EWD_HASH_KEY_IN_TABLE(hash->tables[i],
- hash_val))
- i++;
- */
- i = FIND_TABLE(hash_val);
- table = hash->tables[i];
- if (!table)
- return FALSE;
-
- while (table->base + table->size < hash_val) {
- i++;
- table = hash->tables[i];
- if (!table)
- return FALSE;
- }
- /* Find the index into the table and create a list if none exists */
- hash_val -= table->base;
- if (!table->table[hash_val])
- table->table[hash_val] = ewd_list_new();
+ /* Create the list if it's not already present */
+ if (!hash->buckets[hash_val])
+ hash->buckets[hash_val] = ewd_list_new();
/* Append the node to the list at the index position */
- if (!ewd_list_append(table->table[hash_val], node))
+ if (!ewd_list_prepend(hash->buckets[hash_val], node))
return FALSE;
-
hash->nodes++;
return TRUE;
@@ -269,11 +226,13 @@
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
- node = ewd_hash_get_node(hash, key);
+ node = _ewd_hash_get_node(hash, key);
+ if (!node)
+ return NULL;
- EWD_READ_LOCK_STRUCT(node);
- data = (node ? node->value : NULL);
- EWD_READ_UNLOCK_STRUCT(node);
+ EWD_READ_LOCK(node);
+ data = node->value;
+ EWD_READ_UNLOCK(node);
return data;
}
@@ -284,129 +243,92 @@
* 2. key - the key to search for in the hash table
* Returns: NULL on error, node corresponding to key on success
*/
-static Ewd_Hash_Node *
-ewd_hash_get_node(Ewd_Hash *hash, void *key)
-{
- int size;
- Ewd_Hash_Node *node = NULL;
-
- CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
-
- size = hash->size;
- do {
- node = ewd_hash_get_with_size(hash, key, ewd_prime_table[size]);
- size--;
- } while (size >= 0 && !node);
-
- return node;
-}
-
-/*
- * Description: Search for a node using the given table size
- * Parameters: 1. hash - the hash table to search for the key
- * 2. key - the key to search the hash table
- * 3. size - the size of the hash table for this search
- * Returns: The found node on success, NULL on error or not found
- */
static Ewd_Hash_Node *
-ewd_hash_get_with_size(Ewd_Hash *hash, void *key, int size)
+_ewd_hash_get_node(Ewd_Hash *hash, void *key)
{
unsigned int hash_val;
- Ewd_Hash_Table *table = NULL;
- Ewd_List *list = NULL;
Ewd_Hash_Node *node = NULL;
CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
- hash_val = hash->hash_func(key) % size;
- table = hash->tables[ewd_hash_find_table(hash, hash_val)];
-/* printf("%d: %d\n", hash_val, ewd_hash_find_table(hash, hash_val)); */
- if (table) {
- hash_val -= table->base;
- list = table->table[hash_val];
- }
+ EWD_READ_LOCK(hash);
+ hash_val = hash->hash_func(key) % ewd_prime_table[hash->size];
+ if (hash->buckets[hash_val])
+ node = _ewd_hash_get_bucket(hash, hash->buckets[hash_val], key);
+ EWD_READ_UNLOCK(hash);
- if (list)
- node = ewd_hash_get_bucket(hash, list, key);
-
return node;
}
/*
- * Description: Determine the table that contains the given index
- * Parameters: 1. hash - the hash table to search
- * 2. index - the index to determine the needed table
- * Returns: -1 on error, a hash table index number on success
- */
-static int
-ewd_hash_find_table(Ewd_Hash *hash, unsigned int index)
-{
- int i;
-
- CHECK_PARAM_POINTER_RETURN("hash", hash, -1);
-
- i = FIND_TABLE(index);
- while (index >= ewd_prime_table[i] && i <= hash->size)
- i++;
-
- return i;
-}
-
-/*
* Description: Search the hash bucket for a specified key
* Parameters: 1. hash - the hash table to retrieve the comparison function
* 2. bucket - the list to search for the key
* 3. key - the key to search for in the list
* Returns: NULL on error or not found, the found node on success
*/
-static Ewd_Hash_Node *
-ewd_hash_get_bucket(Ewd_Hash *hash, Ewd_List *bucket, void *key)
+inline Ewd_Hash_Node *
+_ewd_hash_get_bucket(Ewd_Hash *hash, Ewd_List *bucket, void *key)
{
Ewd_Hash_Node *node = NULL;
+ EWD_READ_LOCK(hash);
+ ewd_list_goto_first(bucket);
if (hash->compare) {
while ((node = ewd_list_next(bucket)) != NULL) {
- if (hash->compare(node->key, key) == 0)
+ EWD_READ_LOCK(node);
+ if (hash->compare(node->key, key) == 0) {
+ EWD_READ_UNLOCK(node);
+ EWD_READ_UNLOCK(hash);
return node;
+ }
+ EWD_READ_UNLOCK(node);
}
}
else {
while ((node = ewd_list_next(bucket)) != NULL) {
- if (node->key == key)
+ EWD_READ_LOCK(node);
+ if (node->key == key) {
+ EWD_READ_UNLOCK(node);
+ EWD_READ_UNLOCK(hash);
return node;
+ }
+ EWD_READ_UNLOCK(node);
}
}
+ EWD_READ_UNLOCK(hash);
return NULL;
}
/*
- * Description: Increase the size of the hash table by > 2 * current size
+ * Description: Increase the size of the hash table by approx. 2 * current size
* Parameters: 1. hash - the hash table to increase the size of
* Returns: TRUE on success, FALSE on error
*/
static int
-ewd_hash_increase(Ewd_Hash *hash)
+_ewd_hash_increase(Ewd_Hash *hash)
{
- Ewd_Hash_Table *table, *last;
-
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
+ /* Max size reached so return FALSE */
if (hash->size == PRIME_TABLE_MAX)
return FALSE;
- table = ewd_hash_table_new(ewd_prime_table[hash->size + 1] -
- ewd_prime_table[hash->size]);
- if (!table)
+ hash->size++;
+ hash->buckets = (Ewd_List **)realloc(hash->buckets,
+ ewd_prime_table[hash->size] * sizeof(Ewd_List *));
+ if (!hash->buckets) {
+ hash->size--;
return FALSE;
+ }
- last = hash->tables[hash->size];
- if (last)
- table->base = last->base + last->size;
+ memset(hash->buckets + ewd_prime_table[hash->size - 1], 0,
+ (ewd_prime_table[hash->size] -
+ ewd_prime_table[hash->size - 1]) * sizeof(Ewd_List *));
+ hash->nodes = 0;
+ _ewd_hash_rehash(hash, hash->buckets, hash->size - 1);
- hash->size++;
- hash->tables[hash->size] = table;
-
return TRUE;
}
@@ -416,21 +338,38 @@
* Returns: TRUE on success, FALSE on error
*/
static int
-ewd_hash_decrease(Ewd_Hash *hash)
+_ewd_hash_decrease(Ewd_Hash *hash)
{
- Ewd_Hash_Table *table;
+ Ewd_List **old;
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
if (ewd_prime_table[hash->size] == PRIME_MIN)
return FALSE;
- table = hash->tables[hash->size];
hash->size--;
- ewd_hash_table_rehash(hash, table);
- ewd_hash_table_destroy(table, hash->free_key, hash->free_value);
+ old = hash->buckets;
+ hash->buckets = (Ewd_List **)malloc(ewd_prime_table[hash->size] *
+ sizeof(Ewd_List *));
+ if (!hash->buckets) {
+ hash->buckets = old;
+ hash->size++;
+ return FALSE;
+ }
+ memset(hash->buckets, 0, ewd_prime_table[hash->size]
+ * sizeof(Ewd_List *));
+ hash->nodes = 0;
- return TRUE;
+ if (_ewd_hash_rehash(hash, old, hash->size - 1)) {
+ int i;
+
+ for (i = 0; i < ewd_prime_table[hash->size - 1]; i++)
+ ewd_list_destroy(old[i]);
+ FREE(old);
+ return TRUE;
+ }
+
+ return FALSE;
}
/*
@@ -439,66 +378,35 @@
* 2. table - the table to remove the nodes from and place in hash
* Returns: TRUE on success, FALSE on success
*/
-static int
-ewd_hash_table_rehash(Ewd_Hash *hash, Ewd_Hash_Table *table)
+inline int
+_ewd_hash_rehash(Ewd_Hash *hash, Ewd_List **old_table, int old_size)
{
int i;
Ewd_Hash_Node *node;
+ Ewd_List *old;
+ printf("Rehashing now: %d nodes\n", hash->nodes);
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
- CHECK_PARAM_POINTER_RETURN("table", table, FALSE);
+ CHECK_PARAM_POINTER_RETURN("old_table", old_table, FALSE);
- for (i = 0; i < table->size; i++) {
- while ((node = EWD_HASH_NODE(ewd_list_remove(table->table[i])))
- != NULL)
- ewd_hash_add_node(hash, node);
- ewd_list_destroy(table->table[i]);
- table->table[i] = NULL;
- }
-
- return TRUE;
-}
-
-/*
- * Description: Create and initialize a new table
- * Parameters: 1. size - the size of the table to be created
- * Returns: NULL on error, a new table on success
- */
-static Ewd_Hash_Table *
-ewd_hash_table_new(int size)
-{
- Ewd_Hash_Table *table;
-
- table = (Ewd_Hash_Table *)malloc(sizeof(Ewd_Hash_Table));
- if (!table)
- return NULL;
+ for (i = 0; i < ewd_prime_table[old_size]; i++) {
+ /* Hash into a new list to avoid loops of rehashing the same
+ * nodes */
+ old = old_table[i];
+ old_table[i] = NULL;
+
+ /* Loop through re-adding each node to the hash table */
+ while (old && (node = ewd_list_remove_last(old))) {
+/* EWD_WRITE_UNLOCK(hash); */
+ _ewd_hash_add_node(hash, node);
+/* EWD_WRITE_LOCK(hash); */
+ }
- if (!ewd_hash_table_init(table, size)) {
- FREE(table);
- return NULL;
+ /* Now free up the old list space */
+ if (old)
+ ewd_list_destroy(old);
}
- return table;
-}
-
-/*
- * Description: Initialize a table to some sane starting value
- * Parameters: 1. table - the table to initialize
- * Returns: TRUE on success, FALSE on error
- */
-static int
-ewd_hash_table_init(Ewd_Hash_Table *table, int size)
-{
- CHECK_PARAM_POINTER_RETURN("table", table, FALSE);
-
- memset(table, 0, sizeof(Ewd_Hash_Table));
-
- table->table = (Ewd_List **)malloc(size * sizeof(Ewd_List *));
- if (!table->table)
- return FALSE;
-
- table->size = size;
-
return TRUE;
}
@@ -509,7 +417,7 @@
* Returns: NULL on error, a new hash node on success
*/
static Ewd_Hash_Node *
-ewd_hash_node_new(void *key, void *value)
+_ewd_hash_node_new(void *key, void *value)
{
Ewd_Hash_Node *node;
@@ -517,7 +425,7 @@
if (!node)
return NULL;
- if (!ewd_hash_node_init(node, key, value)) {
+ if (!_ewd_hash_node_init(node, key, value)) {
FREE(node);
return NULL;
}
@@ -533,7 +441,7 @@
* Returns: TRUE on success, FALSE on error
*/
static int
-ewd_hash_node_init(Ewd_Hash_Node *node, void *key, void *value)
+_ewd_hash_node_init(Ewd_Hash_Node *node, void *key, void *value)
{
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
@@ -551,7 +459,8 @@
* Returns: TRUE on success, FALSE on error
*/
static int
-ewd_hash_node_destroy(Ewd_Hash_Node *node, Ewd_Free_Cb keyd, Ewd_Free_Cb valued)
+_ewd_hash_node_destroy(Ewd_Hash_Node *node, Ewd_Free_Cb keyd,
+ Ewd_Free_Cb valued)
{
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_hash.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- ewd_hash.h 2001/05/01 18:00:10 1.2
+++ ewd_hash.h 2001/06/12 19:42:11 1.3
@@ -4,36 +4,11 @@
/*
* Hash Table Implementation:
*
- * This hash table implementation uses a combination of techniques for resolving
- * collision issues. It uses a combination of separate chaining and re-hashing.
- * Separate chaining is used for resolving collisions as data is inserted into
- * the table. Re-hashing is used for retrieving data from the table, as the
- * table size may change.
- *
- * The table size is changed by incrementing the size of the table to the next
- * prime number > 2 * current size. Hopefully, this will act as a pre-caching
- * mechanism. Then a table is constructed of size (old size - new size) and
- * added to the list of tables. Data is retrieved from the hash by first using
- * the current size as the modulo operator. If the data is not found in the
- * list located at the calculated position, previous sizes are tried until the
- * data is found or there are no previous sizes available to try. The previous
- * sizes are easily obtained from the ewd_prime_table in ewd_value.c.
- *
- * The main advantage of this scheme is that when the table size needs to be
- * increased, the data does not need to be recopied into the new table. When
- * the table size is decreased, the only data copied is that in the last
- * table.
- *
- * The disadvantage of this scheme is that searching time may be adversely
- * affected because of the multiple possible hash positions. The fact that
- * each table size is a prime number should cut down on this overhead.
- *
- * Once the scheme is filled out a little more, I plan to run some tests
- * comparing this hash table scheme vs. the glib hash table scheme.
+ * Traditional hash table implementation. I had tried a list of tables
+ * approach to save on the realloc's but it ended up being much slower than
+ * the traditional approach.
*/
-#define EWD_HASH_CHAIN_MAX 3
-
typedef struct _ewd_hash_node Ewd_Hash_Node;
#define EWD_HASH_NODE(hash) ((Ewd_Hash_Node *)hash)
@@ -44,23 +19,11 @@
EWD_DECLARE_LOCKS;
};
-typedef struct _ewd_hash_table Ewd_Hash_Table;
-#define EWD_HASH_TABLE(table) ((Ewd_Hash_Table *)table)
-
-struct _ewd_hash_table {
- Ewd_List **table; /* The table of nodes */
-
- int base; /* The base number of the nodes in this table */
- int size; /* The size of this table */
-
- EWD_DECLARE_LOCKS;
-};
-
typedef struct _ewd_hash Ewd_Hash;
#define EWD_HASH(hash) ((Ewd_Hash *)hash)
struct _ewd_hash {
- Ewd_Hash_Table *tables[PRIME_TABLE_MAX];
+ Ewd_List **buckets;
int size; /* An index into the table of primes to
determine size */
int nodes; /* The number of nodes currently in the hash */
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_macros.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -3 -r1.3 -r1.4
--- ewd_macros.h 2001/05/01 18:00:10 1.3
+++ ewd_macros.h 2001/06/12 19:42:11 1.4
@@ -26,13 +26,12 @@
#define CHECK_PARAM_POINTER_RETURN(sparam, param, ret) \
if (!(param)) \
{ \
- fprintf(stderr, "***** %s Developer Warning ***** :\n" \
+ fprintf(stderr, "***** Developer Warning ***** :\n" \
"\tThis program is calling:\n\n" \
"\t%s();\n\n" \
"\tWith the parameter:\n\n" \
"\t%s\n\n" \
- "\tbeing NULL. Please fix your program.\n", PACKAGE, \
- __FUNCTION__,\
+ "\tbeing NULL. Please fix your program.\n", __FUNCTION__,\
sparam); \
fflush(stdout); \
return ret; \
@@ -43,13 +42,12 @@
#define CHECK_PARAM_POINTER(sparam, param) \
if (!(param)) \
{ \
- fprintf(stderr, "***** %s Developer Warning ***** :\n" \
+ fprintf(stderr, "***** Developer Warning ***** :\n" \
"\tThis program is calling:\n\n" \
"\t%s();\n\n" \
"\tWith the parameter:\n\n" \
"\t%s\n\n" \
- "\tbeing NULL. Please fix your program.\n", PACKAGE, \
- __FUNCTION__, \
+ "\tbeing NULL. Please fix your program.\n", __FUNCTION__, \
sparam); \
fflush(stdout); \
return; \
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_threads.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -3 -r1.5 -r1.6
--- ewd_threads.h 2001/05/04 01:58:05 1.5
+++ ewd_threads.h 2001/06/12 19:42:11 1.6
@@ -28,14 +28,14 @@
pthread_cond_destroy(&structure->readers_cond); \
}
-#define EWD_READ_LOCK_STRUCT(structure) \
+#define EWD_READ_LOCK(structure) \
if (structure) { \
pthread_mutex_lock(&structure->readers_mutex); \
structure->readers++; \
pthread_mutex_unlock(&structure->readers_mutex); \
}
-#define EWD_READ_UNLOCK_STRUCT(structure) \
+#define EWD_READ_UNLOCK(structure) \
if (structure) { \
pthread_mutex_lock(&structure->readers_mutex); \
if (--structure->readers == 0) \
@@ -43,7 +43,7 @@
pthread_mutex_unlock(&structure->readers_mutex); \
}
-#define EWD_WRITE_LOCK_STRUCT(structure) \
+#define EWD_WRITE_LOCK(structure) \
if (structure) { \
pthread_mutex_lock(&structure->readers_mutex); \
pthread_mutex_lock(&structure->writers_mutex); \
@@ -53,7 +53,7 @@
pthread_mutex_unlock(&structure->readers_mutex); \
}
-#define EWD_WRITE_UNLOCK_STRUCT(structure) \
+#define EWD_WRITE_UNLOCK(structure) \
if (structure) \
pthread_mutex_unlock(&structure->writers_mutex); \
@@ -70,10 +70,10 @@
#define EWD_DECLARE_LOCKS
#define EWD_INIT_LOCKS(structure)
-#define EWD_READ_LOCK_STRUCT(structure)
-#define EWD_READ_UNLOCK_STRUCT(structure)
-#define EWD_WRITE_LOCK_STRUCT(structure)
-#define EWD_WRITE_UNLOCK_STRUCT(structure)
+#define EWD_READ_LOCK(structure)
+#define EWD_READ_UNLOCK(structure)
+#define EWD_WRITE_LOCK(structure)
+#define EWD_WRITE_UNLOCK(structure)
#define EWD_THREAD_CREATE(function, args)
#define EWD_DESTROY_LOCKS(structure)
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_tree.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- ewd_tree.c 2001/05/01 18:00:10 1.2
+++ ewd_tree.c 2001/06/12 19:42:11 1.3
@@ -103,9 +103,9 @@
{
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_WRITE_LOCK_STRUCT(tree);
+ EWD_WRITE_LOCK(tree);
tree->free_func = free_func;
- EWD_WRITE_UNLOCK_STRUCT(tree);
+ EWD_WRITE_UNLOCK(tree);
return TRUE;
}
@@ -165,10 +165,10 @@
{
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_WRITE_LOCK_STRUCT(node);
+ EWD_WRITE_LOCK(node);
if (data_free)
data_free(node->value);
- EWD_WRITE_UNLOCK_STRUCT(node);
+ EWD_WRITE_UNLOCK(node);
EWD_DESTROY_LOCKS(node);
@@ -188,9 +188,9 @@
CHECK_PARAM_POINTER_RETURN("node", node,
FALSE);
- EWD_WRITE_LOCK_STRUCT(node);
+ EWD_WRITE_LOCK(node);
node->value = value;
- EWD_WRITE_UNLOCK_STRUCT(node);
+ EWD_WRITE_UNLOCK(node);
return TRUE;
}
@@ -205,9 +205,9 @@
void *ret;
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_READ_LOCK_STRUCT(node);
+ EWD_READ_LOCK(node);
ret = node->value;
- EWD_READ_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK(node);
return ret;
}
@@ -222,9 +222,9 @@
{
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_WRITE_LOCK_STRUCT(node);
+ EWD_WRITE_LOCK(node);
node->key = key;
- EWD_WRITE_UNLOCK_STRUCT(node);
+ EWD_WRITE_UNLOCK(node);
return TRUE;
}
@@ -239,9 +239,9 @@
void *ret;
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_READ_LOCK_STRUCT(node);
+ EWD_READ_LOCK(node);
ret = node->key;
- EWD_READ_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK(node);
return ret;
}
@@ -255,10 +255,10 @@
{
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_WRITE_LOCK_STRUCT(tree);
+ EWD_WRITE_LOCK(tree);
while (tree->tree)
ewd_tree_remove_node(tree, tree->tree);
- EWD_WRITE_UNLOCK_STRUCT(tree);
+ EWD_WRITE_UNLOCK(tree);
EWD_DESTROY_LOCKS(tree);
FREE(tree);
@@ -276,9 +276,9 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
ret = tree_node_find(tree, key);
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(tree);
return ret;
}
@@ -294,13 +294,13 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
node = tree_node_find(tree, key);
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(tree);
- EWD_READ_LOCK_STRUCT(node);
+ EWD_READ_LOCK(node);
ret = (node ? node->value : NULL);
- EWD_READ_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK(node);
return ret;
}
@@ -315,26 +315,26 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
node = tree_node_find(tree, key);
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(tree);
if (node)
return node;
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
node = tree_node_find_parent(tree, key);
if (!node) {
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(tree);
return NULL;
}
- EWD_READ_LOCK_STRUCT(node);
+ EWD_READ_LOCK(node);
if (tree->compare_func(node->key, key) < 0)
return NULL;
- EWD_READ_UNLOCK_STRUCT(node);
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(node);
+ EWD_READ_UNLOCK(tree);
return node;
}
@@ -349,16 +349,16 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
node = tree_node_find(tree, key);
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(tree);
if (node)
return node;
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
node = tree_node_find_parent(tree, key);
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
if (node)
node = node->right_child;
@@ -377,9 +377,9 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_READ_LOCK_STRUCT(tree);
+ EWD_READ_LOCK(tree);
node = tree_node_find(tree, key);
- EWD_READ_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK(tree);
if (!node) {
node = ewd_tree_node_new();
@@ -389,10 +389,10 @@
}
ewd_tree_node_value_set(node, value);
- EWD_WRITE_LOCK_STRUCT(tree);
+ EWD_WRITE_LOCK(tree);
for (; node; node = node->parent)
tree_node_balance(tree, node);
- EWD_WRITE_UNLOCK_STRUCT(tree);
+ EWD_WRITE_UNLOCK(tree);
return TRUE;
}
|
