Menu
▾
▴
E CVS: libs/ewd rbdpngn
|
From: <enl...@li...> - 2001-05-01 18:00:11
|
Enlightenment CVS committal
Author : rbdpngn
Project : e17
Module : libs/ewd
Dir : e17/libs/ewd/src
Modified Files:
Ewd.h Makefile.am ewd_dlist.c ewd_dlist.h ewd_hash.c
ewd_hash.h ewd_list.h ewd_list_private.h ewd_macros.h
ewd_threads.h ewd_tree.c ewd_tree.h ewd_value.c ewd_value.h
Log Message:
Committing some major changes so that things will compile. Don't bother trying
to use the hash code right now. It's a mess of stuff I was experimenting with.
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/Ewd.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- Ewd.h 2001/04/14 07:19:16 1.2
+++ Ewd.h 2001/05/01 18:00:10 1.3
@@ -3,6 +3,7 @@
#include <stdio.h>
#include <stdlib.h>
+#include <math.h>
#ifndef TRUE
#define TRUE 1
@@ -12,15 +13,13 @@
#define FALSE 0
#endif
-#ifndef PACKAGE
-#define PACKAGE "Ewd"
-#endif
-
+#include <ewd-config.h>
+#include <ewd_macros.h>
#include <ewd_threads.h>
#include <ewd_value.h>
#include <ewd_list.h>
#include <ewd_dlist.h>
#include <ewd_tree.h>
-#include <ewd_macros.h>
+#include <ewd_hash.h>
#endif
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/Makefile.am,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -3 -r1.3 -r1.4
--- Makefile.am 2001/04/14 07:19:16 1.3
+++ Makefile.am 2001/05/01 18:00:10 1.4
@@ -5,19 +5,22 @@
lib_LTLIBRARIES = libewd.la
installed_headers_DATA = \
Ewd.h \
- ewd_list.h \
ewd_dlist.h \
+ ewd_hash.h \
+ ewd_list.h \
ewd_list_private.h \
+ ewd_macros.h \
+ ewd_threads.h \
ewd_tree.h \
ewd_value.h \
- ewd_threads.h \
- ewd_macros.h
+ ../ewd-config.h
libewd_la_SOURCES = \
- ewd_value.c \
- ewd_list.c \
ewd_dlist.c \
- ewd_tree.c
+ ewd_hash.c \
+ ewd_list.c \
+ ewd_tree.c \
+ ewd_value.c
libewd_la_LIBADD = -lm
libewd_la_LDFLAGS = -version-info 0:0:0
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_dlist.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_dlist.c 2001/04/14 07:19:16 1.1
+++ ewd_dlist.c 2001/05/01 18:00:10 1.2
@@ -1,5 +1,3 @@
-#include <../config.h>
-
#include <Ewd.h>
#include <ewd_list_private.h>
@@ -35,7 +33,7 @@
memset(list, 0, sizeof(Ewd_DList));
- EWD_INIT_STRUCT_LOCK(list);
+ EWD_INIT_LOCKS(list);
return TRUE;
}
@@ -47,16 +45,21 @@
*/
void ewd_dlist_destroy(Ewd_DList * list)
{
+ void *data;
CHECK_PARAM_POINTER("list", list);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
- while (list->first)
- _ewd_dlist_remove_first(list);
+ while (list->first) {
+ data = _ewd_dlist_remove_first(list);
+ if (list->free_func)
+ list->free_func(data);
+ }
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
+ EWD_DESTROY_LOCKS(list);
- IF_FREE(list);
+ FREE(list);
}
/*
@@ -124,15 +127,16 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
prev = EWD_LIST(list)->last;
ret = _ewd_list_append(EWD_LIST(list), data);
- if (ret)
+ if (ret) {
EWD_DLIST_NODE(EWD_LIST(list)->last)->previous =
EWD_DLIST_NODE(prev);
+ }
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -150,7 +154,7 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
prev = EWD_LIST(list)->first;
ret = _ewd_list_prepend(EWD_LIST(list), data);
@@ -158,7 +162,7 @@
EWD_DLIST_NODE(prev)->previous =
EWD_DLIST_NODE(EWD_LIST(list)->first);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -177,9 +181,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
- index = _ewd_list_index(EWD_LIST(list));
+ index = ewd_list_index(EWD_LIST(list));
current = EWD_LIST(list)->current;
ret = _ewd_list_insert(list, data);
@@ -190,7 +194,7 @@
_ewd_list_goto_index(EWD_LIST(list), index + 1);
}
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -200,14 +204,14 @@
* Parameters: 1. list - the list to remove the current item
* Returns: TRUE on success, FALSE on error
*/
-int ewd_dlist_remove(Ewd_DList * list)
+void *ewd_dlist_remove(Ewd_DList * list)
{
- int ret;
+ void *ret;
Ewd_List_Node *node;
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
if (list->current) {
node = list->current->next;
@@ -216,7 +220,7 @@
}
ret = _ewd_list_remove(list);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -226,23 +230,35 @@
* Parameters: 1. list - the list to remove the current item
* Returns: TRUE on success, FALSE on error
*/
-int ewd_dlist_remove_first(Ewd_DList * list)
+void *ewd_dlist_remove_first(Ewd_DList * list)
{
- int ret;
+ void *ret;
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
ret = _ewd_dlist_remove_first(list);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
-int _ewd_dlist_remove_first(Ewd_DList *list)
+/*
+ * Description: Remove and destroy the data in the list at current position
+ * Parameters: 1. list - the list to remove the data from
+ * Returns: TRUE on success, FALSE on error
+ */
+int ewd_dlist_remove_destroy(Ewd_DList *list)
{
- int ret;
+ CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
+
+ return ewd_list_remove_destroy(list);
+}
+void *_ewd_dlist_remove_first(Ewd_DList *list)
+{
+ void *ret;
+
if (!list)
return FALSE;
@@ -250,7 +266,7 @@
if (ret && EWD_LIST(list)->first)
EWD_DLIST_NODE(EWD_LIST(list)->first)->previous = NULL;
- return TRUE;
+ return ret;
}
/*
@@ -258,15 +274,15 @@
* Parameters: 1. list - the list to remove the last node from
* Returns: TRUE on success, FALSE on error
*/
-int ewd_dlist_remove_last(Ewd_DList * list)
+void *ewd_dlist_remove_last(Ewd_DList * list)
{
- int ret;
+ void *ret;
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
ret = _ewd_list_remove_last(list);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -283,9 +299,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
ret = _ewd_dlist_goto_index(list, index);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -299,18 +315,18 @@
if (!list)
return FALSE;
- if (_ewd_list_is_empty(EWD_LIST(list)))
+ if (ewd_list_is_empty(EWD_LIST(list)))
return FALSE;
- if (index > _ewd_list_nodes(EWD_LIST(list)) || index < 0)
+ if (index > ewd_list_nodes(EWD_LIST(list)) || index < 0)
return FALSE;
- if (index < _ewd_list_index(EWD_LIST(list)))
+ if (index < ewd_list_index(EWD_LIST(list)))
increment = 1;
else
increment = -1;
- for (i = _ewd_list_index(EWD_LIST(list)); i != index; i += increment) {
+ for (i = ewd_list_index(EWD_LIST(list)); i != index; i += increment) {
if (increment > 0)
_ewd_list_next(list);
else
@@ -332,9 +348,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
ret = _ewd_list_goto(EWD_LIST(list), data);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -350,9 +366,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
ret = _ewd_list_goto_first(list);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -368,9 +384,9 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
ret = _ewd_list_goto_last(EWD_LIST(list));
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return ret;
}
@@ -384,9 +400,9 @@
{
void *ret;
- EWD_LOCK_STRUCT(list);
+ EWD_READ_LOCK_STRUCT(list);
ret = _ewd_list_current(EWD_LIST(list));
- EWD_UNLOCK_STRUCT(list);
+ EWD_READ_UNLOCK_STRUCT(list);
return ret;
}
@@ -400,9 +416,9 @@
{
void *data;
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
data = _ewd_list_next(list);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return data;
}
@@ -416,9 +432,9 @@
{
void *data;
- EWD_LOCK_STRUCT(list);
+ EWD_WRITE_LOCK_STRUCT(list);
data = _ewd_dlist_previous(list);
- EWD_UNLOCK_STRUCT(list);
+ EWD_WRITE_UNLOCK_STRUCT(list);
return data;
}
@@ -453,11 +469,11 @@
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- EWD_LOCK_STRUCT(list);
+ EWD_READ_LOCK_STRUCT(list);
ret = _ewd_list_for_each(list, function);
- EWD_UNLOCK_STRUCT(list);
+ EWD_READ_UNLOCK_STRUCT(list);
return ret;
}
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_dlist.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_dlist.h 2001/04/14 07:19:16 1.1
+++ ewd_dlist.h 2001/05/01 18:00:10 1.2
@@ -15,18 +15,25 @@
/* Creating and initializing new list structures */
Ewd_DList *ewd_dlist_new();
int ewd_dlist_init(Ewd_DList *list);
+void ewd_dlist_destroy(Ewd_DList *list);
/* Adding items to the list */
int ewd_dlist_append(Ewd_DList * _e_dlist, void *_data);
int ewd_dlist_prepend(Ewd_DList * _e_dlist, void *_data);
int ewd_dlist_insert(Ewd_DList * _e_dlist, void *_data);
+/* Info about list's state */
+void *ewd_dlist_current(Ewd_DList *list);
+int ewd_dlist_index(Ewd_DList *list);
+int ewd_dlist_nodes(Ewd_DList *list);
+
/* Removing items from the list */
-int ewd_dlist_remove(Ewd_DList * _e_dlist);
-int ewd_dlist_remove_first(Ewd_DList * _e_dlist);
-int ewd_dlist_remove_last(Ewd_DList * _e_dlist);
+void *ewd_dlist_remove(Ewd_DList * _e_dlist);
+void *ewd_dlist_remove_first(Ewd_DList * _e_dlist);
+void *ewd_dlist_remove_last(Ewd_DList * _e_dlist);
/* Traversing the list */
+int ewd_dlist_for_each(Ewd_DList *list, Ewd_For_Each function);
int ewd_dlist_goto_first(Ewd_DList * _e_dlist);
int ewd_dlist_goto_last(Ewd_DList * _e_dlist);
int ewd_dlist_goto_index(Ewd_DList * _e_dlist, int index);
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_hash.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_hash.c 2001/04/14 07:19:16 1.1
+++ ewd_hash.c 2001/05/01 18:00:10 1.2
@@ -1,11 +1,54 @@
-#include <../config.h>
#include <Ewd.h>
-Ewd_Hash *ewd_hash_new()
+#define EWD_HASH_INCREASE(hash) ((hash && hash->size < PRIME_MAX) ? \
+ ((double)hash->nodes / (double)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)
+
+
+/* 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,
+ 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,
+ Ewd_Free_Cb valued);
+
+
+/*
+ * Description: Create and initialize a new hash
+ * Parameters: 1. hash_func - the function for determining hash position
+ * 2. compare - the function for comparing node keys
+ * Returns: NULL on error, a new hash on success
+ */
+Ewd_Hash *ewd_hash_new(Ewd_Hash_Cb hash_func, Ewd_Compare_Cb compare)
{
Ewd_Hash *new = (Ewd_Hash *)malloc(sizeof(Ewd_Hash));
- if (!ewd_hash_init(new)) {
+ if (!ewd_hash_init(new, hash_func, compare)) {
FREE(new);
return NULL;
}
@@ -13,14 +56,512 @@
return new;
}
-int ewd_hash_init(Ewd_Hash *hash)
+/*
+ * Description: Initialize a hash to some sane starting values
+ * Parameters: 1. hash - the hash table to initialize
+ * 2. compare - the function for comparing node keys
+ * Returns: TRUE on success, FALSE on an error.
+ */
+int ewd_hash_init(Ewd_Hash *hash, Ewd_Hash_Cb hash_func, Ewd_Compare_Cb compare)
{
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
memset(hash, 0, sizeof(Ewd_Hash));
+
+ if (hash_func)
+ hash->hash_func = hash_func;
+ else
+ hash->hash_func = ewd_direct_hash;
+
+ if (compare)
+ hash->compare = compare;
+
+ hash->tables[0] = ewd_hash_table_new(ewd_prime_table[0]);
+
+ EWD_INIT_LOCKS(hash);
+
+ return TRUE;
+}
+
+/*
+ * Description: Set the function called when node's are free'd to free keys
+ * Parameters: 1. hash - the hash that this will affect
+ * 2. function - the function that will free the node keys
+ * Returns: TRUE on success, FALSE on error
+ */
+int ewd_hash_set_free_key(Ewd_Hash *hash, Ewd_Free_Cb function)
+{
+ CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
+ CHECK_PARAM_POINTER_RETURN("function", function, FALSE);
+
+ hash->free_key = function;
+
+ return TRUE;
+}
+
+/*
+ * Description: Set the function called when node's are free'd to free values
+ * Parameters: 1. hash - the hash that this will affect
+ * 2. function - the function that will free the node values
+ * Returns: TRUE on success, FALSE on error
+ */
+int ewd_hash_set_free_value(Ewd_Hash *hash, Ewd_Free_Cb function)
+{
+ CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
+ CHECK_PARAM_POINTER_RETURN("function", function, FALSE);
+
+ hash->free_value = function;
+
+ return TRUE;
+}
+
+/*
+ * Description: Set the key/value pair in the hash table, if node doesn't exist
+ * then create it.
+ * Parameters: 1. hash - the hash table to set the the value in
+ * 2. key - the key for this value pair
+ * 3. value - the value corresponding with the key
+ * Returns: TRUE if successful, FALSE if not
+ */
+int ewd_hash_set(Ewd_Hash *hash, void *key, void *value)
+{
+ int ret = FALSE;
+ Ewd_Hash_Node *node;
+
+ CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
+
+ node = ewd_hash_get_node(hash, key);
+ if (node)
+ node->value = value;
+ else {
+ node = ewd_hash_node_new(key, value);
+ if (node)
+ ret = ewd_hash_add_node(hash, node);
+ }
+
+ return ret;
+}
+
+/*
+ * Description: Free the hash table and the data contained inside it
+ * Parameters: 1. hash - the hash table to destroy
+ * Returns: TRUE on success, FALSE on error
+ */
+void ewd_hash_destroy(Ewd_Hash *hash)
+{
+ int i = 0;
+
+ CHECK_PARAM_POINTER("hash", hash);
+
+ EWD_WRITE_LOCK_STRUCT(hash);
+
+ while (i <= hash->size) {
+ ewd_hash_table_destroy(hash->tables[i], hash->free_key,
+ hash->free_value);
+ i++;
+ }
+
+ EWD_WRITE_UNLOCK_STRUCT(hash);
+ EWD_DESTROY_LOCKS(hash);
+
+ FREE(hash);
+
+ 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)
+{
+ int i;
+ Ewd_List *list;
+
+ CHECK_PARAM_POINTER_RETURN("table", table, 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);
+ }
+ }
+
+ return TRUE;
+}
+
+/*
+ * Description: Add the node to the hash table
+ * Parameters: 1. hash - the hash table to add the key
+ * 2. node - the node to add to the hash table
+ * Returns: FALSE on error, TRUE on success
+ */
+static int
+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);
+ CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
+
+ /* Check to see if the hash needs to be resized */
+ if (EWD_HASH_INCREASE(hash))
+ ewd_hash_increase(hash);
+ else if (EWD_HASH_REDUCE(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();
+
+ /* Append the node to the list at the index position */
+ if (!ewd_list_append(table->table[hash_val], node))
+ return FALSE;
+
+ hash->nodes++;
+
+ return TRUE;
+}
+
+/*
+ * Description: Retrieve the value associated with key
+ * Parameters: 1. hash - the hash table to search for the key
+ * 2. key - the key to search for in the hash table
+ * Returns: NULL on error, value corresponding to key on success
+ */
+void *ewd_hash_get(Ewd_Hash *hash, void *key)
+{
+ void *data = NULL;
+ Ewd_Hash_Node *node;
+
+ CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
+
+ node = ewd_hash_get_node(hash, key);
+
+ EWD_READ_LOCK_STRUCT(node);
+ data = (node ? node->value : NULL);
+ EWD_READ_UNLOCK_STRUCT(node);
+
+ return data;
+}
+
+/*
+ * Description: Retrieve the node associated with key
+ * Parameters: 1. hash - the hash table to search for the key
+ * 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)
+{
+ 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];
+ }
+
+ 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)
+{
+ Ewd_Hash_Node *node = NULL;
+
+ if (hash->compare) {
+ while ((node = ewd_list_next(bucket)) != NULL) {
+ if (hash->compare(node->key, key) == 0)
+ return node;
+ }
+ }
+ else {
+ while ((node = ewd_list_next(bucket)) != NULL) {
+ if (node->key == key)
+ return node;
+ }
+ }
+
+ return NULL;
+}
+
+/*
+ * Description: Increase the size of the hash table by > 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_Table *table, *last;
+
+ CHECK_PARAM_POINTER_RETURN("hash", hash, 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)
+ return FALSE;
+
+ last = hash->tables[hash->size];
+ if (last)
+ table->base = last->base + last->size;
+
+ hash->size++;
+ hash->tables[hash->size] = table;
+
+ return TRUE;
+}
+
+/*
+ * Description: Decrease the size of the hash table by < 1/2 * current size
+ * Parameters: 1. hash - the hash table to decrease the size of
+ * Returns: TRUE on success, FALSE on error
+ */
+static int
+ewd_hash_decrease(Ewd_Hash *hash)
+{
+ Ewd_Hash_Table *table;
+
+ 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);
+
+ return TRUE;
+}
+
+/*
+ * Description: Rehash the nodes of a table into the hash table
+ * Parameters: 1. hash - the hash to place the nodes of the table
+ * 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)
+{
+ int i;
+ Ewd_Hash_Node *node;
+
+ CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
+ CHECK_PARAM_POINTER_RETURN("table", 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;
+
+ if (!ewd_hash_table_init(table, size)) {
+ FREE(table);
+ return NULL;
+ }
+
+ 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;
+}
+
+/*
+ * Description: Create a new hash node for key and value storage
+ * Parameters: 1. key - the key for this node
+ * 2. value - the value that the key references
+ * 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 *node;
+
+ node = (Ewd_Hash_Node *)malloc(sizeof(Ewd_Hash_Node));
+ if (!node)
+ return NULL;
+
+ if (!ewd_hash_node_init(node, key, value)) {
+ FREE(node);
+ return NULL;
+ }
+
+ return node;
+}
+
+/*
+ * Description: Initialize a hash node to some sane default values
+ * Parameters: 1. node - the node to set the values
+ * 2. key - the key to reference this node
+ * 3. value - the value that key refers to
+ * Returns: TRUE on success, FALSE on error
+ */
+static int
+ewd_hash_node_init(Ewd_Hash_Node *node, void *key, void *value)
+{
+ CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
+
+ node->key = key;
+ node->value = value;
+
+ return TRUE;
+}
+
+/*
+ * Description: Destroy a node and call the specified callbacks to free data
+ * Parameters: 1. node - the node to be destroyed
+ * 2. keyd - the function to free the key
+ * 3. valued - the function to free the value
+ * 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)
+{
+ CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
+
+ if (keyd)
+ keyd(node->key);
+
+ if (valued)
+ valued(node->value);
-#ifdef __USE_PTHREADS
- hash->lock = PTHREAD_MUTEX_INITIALIZER;
-#endif
+ FREE(node);
+ return TRUE;
}
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_hash.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_hash.h 2001/04/14 07:19:16 1.1
+++ ewd_hash.h 2001/05/01 18:00:10 1.2
@@ -1,20 +1,87 @@
#ifndef _EWD_HASH_H
#define _EWD_HASH_H
+/*
+ * 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.
+ */
+
+#define EWD_HASH_CHAIN_MAX 3
+
typedef struct _ewd_hash_node Ewd_Hash_Node;
#define EWD_HASH_NODE(hash) ((Ewd_Hash_Node *)hash)
struct _ewd_hash_node {
- Ewd_List *bucket;
- EWD_DECLARE_LOCK;
-}
+ void *key; /* The key for the data node */
+ void *value; /* The value associated with this node */
+
+ 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_List_Node *table;
- EWD_DECLARE_LOCK;
-}
+ Ewd_Hash_Table *tables[PRIME_TABLE_MAX];
+ int size; /* An index into the table of primes to
+ determine size */
+ int nodes; /* The number of nodes currently in the hash */
+
+ Ewd_Compare_Cb compare; /* The function used to compare node values */
+ Ewd_Hash_Cb hash_func; /* The function used to compare node values */
+
+ Ewd_Free_Cb free_key; /* The callback function to free key */
+ Ewd_Free_Cb free_value; /* The callback function to determine hash */
+
+ EWD_DECLARE_LOCKS;
+};
+
+/* Create and initialize a hash */
+Ewd_Hash *ewd_hash_new(Ewd_Hash_Cb hash_func, Ewd_Compare_Cb compare);
+int ewd_hash_init(Ewd_Hash *hash, Ewd_Hash_Cb hash_func,
+ Ewd_Compare_Cb compare);
+void ewd_hash_destroy(Ewd_Hash *hash);
+
+/* Retrieve and store data into the hash */
+void *ewd_hash_get(Ewd_Hash *hash, void *key);
+int ewd_hash_set(Ewd_Hash *hash, void *key, void *value);
#endif
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_list.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- ewd_list.h 2001/04/14 07:19:16 1.2
+++ ewd_list.h 2001/05/01 18:00:10 1.3
@@ -11,7 +11,7 @@
void *data;
struct _ewd_list_node *next;
- EWD_DECLARE_LOCK;
+ EWD_DECLARE_LOCKS;
};
struct _ewd_list {
@@ -24,7 +24,7 @@
int nodes; /* The number of nodes in the list */
int index; /* The position from the front of the
list of current node */
- EWD_DECLARE_LOCK;
+ EWD_DECLARE_LOCKS;
};
@@ -38,11 +38,13 @@
int ewd_list_insert(Ewd_List * list, void *_data);
/* Removing items from the list */
-int ewd_list_remove(Ewd_List * list);
-int ewd_list_remove_first(Ewd_List * list);
-int ewd_list_remove_last(Ewd_List * list);
+int ewd_list_remove_destroy(Ewd_List *list);
+void *ewd_list_remove(Ewd_List * list);
+void *ewd_list_remove_first(Ewd_List * list);
+void *ewd_list_remove_last(Ewd_List * list);
/* Retrieve the current position in the list */
+void *ewd_list_current(Ewd_List * list);
int ewd_list_index(Ewd_List * list);
int ewd_list_nodes(Ewd_List * list);
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_list_private.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_list_private.h 2001/04/14 07:19:16 1.1
+++ ewd_list_private.h 2001/05/01 18:00:10 1.2
@@ -14,9 +14,9 @@
int _ewd_list_prepend(Ewd_List * list, void *data);
/* Remove functions */
-int _ewd_list_remove(Ewd_List * list);
-int _ewd_list_remove_first(Ewd_List * list);
-int _ewd_list_remove_last(Ewd_List * list);
+void *_ewd_list_remove(Ewd_List * list);
+void *_ewd_list_remove_first(Ewd_List * list);
+void *_ewd_list_remove_last(Ewd_List * list);
/* Basic traversal functions */
void *_ewd_list_next(Ewd_List * list);
@@ -30,5 +30,5 @@
/* Private double linked list functions */
void *_ewd_dlist_previous(Ewd_DList * list);
-int _ewd_dlist_remove_first(Ewd_DList *list);
+void *_ewd_dlist_remove_first(Ewd_DList *list);
int _ewd_dlist_goto_index(Ewd_DList *list, int index);
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_macros.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -3 -r1.2 -r1.3
--- ewd_macros.h 2001/04/14 07:19:16 1.2
+++ ewd_macros.h 2001/05/01 18:00:10 1.3
@@ -34,6 +34,7 @@
"\tbeing NULL. Please fix your program.\n", PACKAGE, \
__FUNCTION__,\
sparam); \
+ fflush(stdout); \
return ret; \
}
#endif
@@ -50,6 +51,7 @@
"\tbeing NULL. Please fix your program.\n", PACKAGE, \
__FUNCTION__, \
sparam); \
+ fflush(stdout); \
return; \
}
#endif
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_threads.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_threads.h 2001/04/14 07:19:16 1.1
+++ ewd_threads.h 2001/05/01 18:00:10 1.2
@@ -1,30 +1,83 @@
#ifndef _EWD_THREADS_H
#define _EWD_THREADS_H
+/* #undef HAVE_PTHREADS */
#ifdef HAVE_PTHREADS /* pthreads are installed */
#include <pthread.h>
-#define EWD_DECLARE_LOCK pthread_mutex_t lock;
+#define EWD_DECLARE_LOCKS \
+int readers; \
+pthread_mutex_t readers_mutex; \
+pthread_mutex_t writers_mutex; \
+pthread_cond_t readers_cond;
+
+#define EWD_INIT_LOCKS(structure) \
+if (structure) { \
+ pthread_mutex_init(&structure->readers_mutex, NULL); \
+ pthread_mutex_init(&structure->writers_mutex, NULL); \
+ pthread_cond_init(&structure->readers_cond, NULL); \
+}
+
+#define EWD_DESTROY_LOCKS(structure) \
+if (structure) { \
+ pthread_mutex_destroy(&structure->readers_mutex); \
+ pthread_mutex_destroy(&structure->writers_mutex); \
+ pthread_cond_destroy(&structure->readers_cond); \
+}
+
+#define EWD_READ_LOCK_STRUCT(structure) \
+if (structure) { \
+ pthread_mutex_lock(&structure->readers_mutex); \
+ structure->readers++; \
+ pthread_mutex_unlock(&structure->readers_mutex); \
+}
+
+#define EWD_READ_UNLOCK_STRUCT(structure) \
+if (structure) { \
+ pthread_mutex_lock(&structure->readers_mutex); \
+ if (--structure->readers == 0) \
+ pthread_cond_broadcast(&structure->readers_cond); \
+ pthread_mutex_unlock(&structure->readers_mutex); \
+}
+
+#define EWD_WRITE_LOCK_STRUCT(structure) \
+if (structure) { \
+ pthread_mutex_lock(&structure->readers_mutex); \
+ pthread_mutex_lock(&structure->writers_mutex); \
+ while (structure->readers > 0) \
+ pthread_cond_wait(&structure->readers_cond, \
+ &structure->readers_mutex); \
+ pthread_mutex_unlock(&structure->readers_mutex); \
+}
+
+#define EWD_WRITE_UNLOCK_STRUCT(structure) \
+if (structure) \
+ pthread_mutex_unlock(&structure->writers_mutex); \
+
+#define EWD_THREAD_CREATE(function, arg) \
+if (function) { \
+ pthread_t thread; \
+ pthread_create(&thread, NULL, function, arg); \
+ pthread_detach(thread); \
+}
-#define EWD_INIT_STRUCT_LOCK(structure) if (structure) \
- pthread_mutex_init(&structure->lock, NULL);
+#define EWD_NO_THREADS(function, arg)
-#define EWD_LOCK_STRUCT(structure) if (structure) \
- pthread_mutex_lock(&structure->lock);
-
-#define EWD_UNLOCK_STRUCT(structure) if (structure) \
- pthread_mutex_unlock(&structure->lock);
+#else /* No pthreads available */
+#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_THREAD_CREATE(function, args)
-#else /* No pthreads available */
+#define EWD_THREAD_CREATE(function, arg)
-#define EWD_DECLARE_LOCK
-#define EWD_INIT_STRUCT_LOCK(structure) if (structure);
-#define EWD_LOCK_STRUCT(structure) if (structure);
-#define EWD_UNLOCK_STRUCT(structure) if (structure);
+#define EWD_NO_THREADS(function, arg) if (function) function(arg);
#endif /* HAVE_PTHREADS */
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_tree.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_tree.c 2001/04/14 07:19:16 1.1
+++ ewd_tree.c 2001/05/01 18:00:10 1.2
@@ -23,7 +23,6 @@
*/
-#include <../config.h>
#include <Ewd.h>
/* A macro for determining the highest node at given branch */
@@ -86,7 +85,7 @@
else
new->compare_func = compare_func;
- EWD_INIT_STRUCT_LOCK(new);
+ EWD_INIT_LOCKS(new);
return TRUE;
}
@@ -104,9 +103,9 @@
{
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_WRITE_LOCK_STRUCT(tree);
tree->free_func = free_func;
- EWD_UNLOCK_STRUCT(tree);
+ EWD_WRITE_UNLOCK_STRUCT(tree);
return TRUE;
}
@@ -129,7 +128,7 @@
new->max_left = new->max_right = 0;
- EWD_INIT_STRUCT_LOCK(new);
+ EWD_INIT_LOCKS(new);
return TRUE;
}
@@ -166,13 +165,15 @@
{
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_LOCK_STRUCT(node);
+ EWD_WRITE_LOCK_STRUCT(node);
if (data_free)
data_free(node->value);
- EWD_UNLOCK_STRUCT(node);
+ EWD_WRITE_UNLOCK_STRUCT(node);
- IF_FREE(node);
+ EWD_DESTROY_LOCKS(node);
+ FREE(node);
+
return TRUE;
}
@@ -187,9 +188,9 @@
CHECK_PARAM_POINTER_RETURN("node", node,
FALSE);
- EWD_LOCK_STRUCT(node);
+ EWD_WRITE_LOCK_STRUCT(node);
node->value = value;
- EWD_UNLOCK_STRUCT(node);
+ EWD_WRITE_UNLOCK_STRUCT(node);
return TRUE;
}
@@ -204,9 +205,9 @@
void *ret;
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_LOCK_STRUCT(node);
+ EWD_READ_LOCK_STRUCT(node);
ret = node->value;
- EWD_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK_STRUCT(node);
return ret;
}
@@ -221,9 +222,9 @@
{
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_LOCK_STRUCT(node);
+ EWD_WRITE_LOCK_STRUCT(node);
node->key = key;
- EWD_UNLOCK_STRUCT(node);
+ EWD_WRITE_UNLOCK_STRUCT(node);
return TRUE;
}
@@ -238,9 +239,9 @@
void *ret;
CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
- EWD_LOCK_STRUCT(node);
+ EWD_READ_LOCK_STRUCT(node);
ret = node->key;
- EWD_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK_STRUCT(node);
return ret;
}
@@ -254,12 +255,13 @@
{
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_WRITE_LOCK_STRUCT(tree);
while (tree->tree)
ewd_tree_remove_node(tree, tree->tree);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_WRITE_UNLOCK_STRUCT(tree);
+ EWD_DESTROY_LOCKS(tree);
- IF_FREE(tree);
+ FREE(tree);
return TRUE;
}
@@ -274,9 +276,9 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
ret = tree_node_find(tree, key);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(tree);
return ret;
}
@@ -292,13 +294,13 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
node = tree_node_find(tree, key);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(tree);
- EWD_LOCK_STRUCT(node);
+ EWD_READ_LOCK_STRUCT(node);
ret = (node ? node->value : NULL);
- EWD_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK_STRUCT(node);
return ret;
}
@@ -313,26 +315,26 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
node = tree_node_find(tree, key);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(tree);
if (node)
return node;
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
node = tree_node_find_parent(tree, key);
if (!node) {
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(tree);
return NULL;
}
- EWD_LOCK_STRUCT(node);
+ EWD_READ_LOCK_STRUCT(node);
if (tree->compare_func(node->key, key) < 0)
return NULL;
- EWD_UNLOCK_STRUCT(node);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(node);
+ EWD_READ_UNLOCK_STRUCT(tree);
return node;
}
@@ -347,16 +349,16 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
node = tree_node_find(tree, key);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(tree);
if (node)
return node;
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
node = tree_node_find_parent(tree, key);
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
if (node)
node = node->right_child;
@@ -375,9 +377,9 @@
CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
- EWD_LOCK_STRUCT(tree);
+ EWD_READ_LOCK_STRUCT(tree);
node = tree_node_find(tree, key);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_READ_UNLOCK_STRUCT(tree);
if (!node) {
node = ewd_tree_node_new();
@@ -387,10 +389,10 @@
}
ewd_tree_node_value_set(node, value);
- EWD_LOCK_STRUCT(tree);
+ EWD_WRITE_LOCK_STRUCT(tree);
for (; node; node = node->parent)
tree_node_balance(tree, node);
- EWD_UNLOCK_STRUCT(tree);
+ EWD_WRITE_UNLOCK_STRUCT(tree);
return TRUE;
}
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_tree.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_tree.h 2001/04/14 07:19:16 1.1
+++ ewd_tree.h 2001/05/01 18:00:10 1.2
@@ -18,7 +18,7 @@
int max_right;
int max_left;
- EWD_DECLARE_LOCK;
+ EWD_DECLARE_LOCKS;
};
typedef struct _Ewd_Tree Ewd_Tree;
@@ -33,7 +33,7 @@
/* Callback for freeing node data, default is NULL */
Ewd_Free_Cb free_func;
- EWD_DECLARE_LOCK;
+ EWD_DECLARE_LOCKS;
};
/* Some basic tree functions */
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_value.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_value.c 2001/04/14 07:19:16 1.1
+++ ewd_value.c 2001/05/01 18:00:10 1.2
@@ -24,8 +24,12 @@
*/
-#include <../config.h>
#include <Ewd.h>
+
+const unsigned int ewd_prime_table[] = { 17, 31, 61, 127, 257, 509, 1021,
+ 2053, 4093, 8191, 16381, 32771, 65537, 131071, 262147, 524287, 1048573,
+ 2097143, 4194301, 8388617, 16777213
+};
/* Direct Hash function, just casts the key to an unsigned int */
unsigned int ewd_direct_hash(void *key)
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ewd/src/ewd_value.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -3 -r1.1 -r1.2
--- ewd_value.h 2001/04/14 07:19:16 1.1
+++ ewd_value.h 2001/05/01 18:00:10 1.2
@@ -27,12 +27,21 @@
#ifndef _EWD_VALUE_H
#define _EWD_VALUE_H
-typedef void (*Ewd_Free_Cb) (void *data);
-#define EWD_FREE_CB(func) ((Ewd_Free_Cb)func)
+#define PRIME_TABLE_MAX 21
+#define PRIME_MIN 17
+#define PRIME_MAX 16777213
+extern const unsigned int ewd_prime_table[];
+
typedef void (*Ewd_For_Each) (void *value);
#define EWD_FOR_EACH(function) ((Ewd_For_Each)function)
+typedef void (*Ewd_Free_Cb) (void *data);
+#define EWD_FREE_CB(func) ((Ewd_Free_Cb)func)
+
+typedef unsigned int (*Ewd_Hash_Cb) (void *key);
+#define EWD_HASH_CB(function) ((Ewd_Hash_Cb)function)
+
typedef int (*Ewd_Compare_Cb) (void *data1, void *data2);
#define EWD_COMPARE_CB(function) ((Ewd_Compare_Cb)function)
@@ -41,4 +50,5 @@
unsigned int ewd_direct_hash(void *key);
unsigned int ewd_str_hash(void *key);
+
#endif /* _EWD_VALUE_H */
|
