Enlightenment CVS committal
Author : rbdpngn
Project : e17
Module : libs/ecore
Dir : e17/libs/ecore/src/lib/ecore
Modified Files:
Ecore_Data.h ecore_hash.c
Log Message:
Ecore hash was originally written to teach the concept of a hash, so it used
high level lists. Since it's getting more extensive use, I've switched it to
use it's own list structure for collision chaining. This is more memory
efficient and overall faster.
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ecore/src/lib/ecore/Ecore_Data.h,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -3 -r1.15 -r1.16
--- Ecore_Data.h 5 Sep 2005 15:01:40 -0000 1.15
+++ Ecore_Data.h 16 Nov 2005 22:17:11 -0000 1.16
@@ -104,7 +104,7 @@
# define ECORE_NO_THREADS(function, arg)
# else /* No pthreads available */
-
+
# define ECORE_DECLARE_LOCKS
# define ECORE_INIT_LOCKS(structure)
# define ECORE_READ_LOCK(structure)
@@ -266,8 +266,9 @@
# define ECORE_HASH_NODE(hash) ((Ecore_Hash_Node *)hash)
struct _ecore_hash_node {
- void *key; /* The key for the data node */
- void *value; /* The value associated with this node */
+ Ecore_Hash_Node *next; /* Pointer to the next node in the bucket list */
+ void *key; /* The key for the data node */
+ void *value; /* The value associated with this node */
ECORE_DECLARE_LOCKS;
};
@@ -276,12 +277,12 @@
# define ECORE_HASH(hash) ((Ecore_Hash *)hash)
struct _ecore_hash {
- Ecore_List **buckets;
+ Ecore_Hash_Node **buckets;
int size; /* An index into the table of primes to
determine size */
int nodes; /* The number of nodes currently in the hash */
- int index; /* The current index into the bucket
table */
+ int index; /* The current index into the bucket table */
Ecore_Compare_Cb compare; /* The function used to compare node
values */
Ecore_Hash_Cb hash_func; /* The function used to compare node values */
===================================================================
RCS file: /cvsroot/enlightenment/e17/libs/ecore/src/lib/ecore/ecore_hash.c,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -3 -r1.18 -r1.19
--- ecore_hash.c 15 Oct 2005 10:37:37 -0000 1.18
+++ ecore_hash.c 16 Nov 2005 22:17:11 -0000 1.19
@@ -24,11 +24,11 @@
static Ecore_Hash_Node * _ecore_hash_get_node(Ecore_Hash *hash, void *key);
static int _ecore_hash_increase(Ecore_Hash *hash);
static int _ecore_hash_decrease(Ecore_Hash *hash);
-inline int _ecore_hash_rehash(Ecore_Hash *hash, Ecore_List **old_table, int
old_size);
-static int _ecore_hash_bucket_destroy(Ecore_List *list, Ecore_Free_Cb keyd,
+inline int _ecore_hash_rehash(Ecore_Hash *hash, Ecore_Hash_Node **old_table,
int old_size);
+static int _ecore_hash_bucket_destroy(Ecore_Hash_Node *list, Ecore_Free_Cb
keyd,
Ecore_Free_Cb valued);
-inline Ecore_Hash_Node * _ecore_hash_get_bucket(Ecore_Hash *hash, Ecore_List
*bucket,
- void *key);
+inline Ecore_Hash_Node * _ecore_hash_get_bucket(Ecore_Hash *hash,
+ Ecore_Hash_Node *bucket, void *key);
static Ecore_Hash_Node *_ecore_hash_node_new(void *key, void *value);
static int _ecore_hash_node_init(Ecore_Hash_Node *node, void *key, void
*value);
@@ -79,9 +79,8 @@
hash->hash_func = hash_func;
hash->compare = compare;
- hash->buckets = (Ecore_List **)malloc(ecore_prime_table[0] *
- sizeof(Ecore_List *));
- memset(hash->buckets, 0, ecore_prime_table[0] * sizeof(Ecore_List *));
+ hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[0],
+ sizeof(Ecore_Hash_Node *));
ECORE_INIT_LOCKS(hash);
@@ -182,9 +181,11 @@
ECORE_WRITE_LOCK(hash);
while (i < ecore_prime_table[hash->size]) {
- if (hash->buckets[i])
+ if (hash->buckets[i]) {
_ecore_hash_bucket_destroy(hash->buckets[i],
hash->free_key, hash->free_value);
+ hash->buckets[i] = NULL;
+ }
i++;
}
@@ -226,8 +227,7 @@
if (hash->buckets[i]) {
Ecore_Hash_Node *node;
- ecore_list_goto_first(hash->buckets[i]);
- while ((node = ecore_list_next(hash->buckets[i]))) {
+ for (node = hash->buckets[i]; node; node = node->next) {
for_each_func(node, user_data);
}
}
@@ -260,8 +260,7 @@
if (hash->buckets[i]) {
Ecore_Hash_Node *node;
- ecore_list_goto_first(hash->buckets[i]);
- while ((node = ecore_list_next(hash->buckets[i]))) {
+ for (node = hash->buckets[i]; node; node = node->next) {
ecore_list_append(keys, node->key);
}
}
@@ -285,23 +284,28 @@
unsigned int i;
for (i = 0; i < ecore_prime_table[hash->size]; i++)
- if (hash->buckets[i])
- printf("%d\t%u\n", i,
ecore_list_nodes(hash->buckets[i]));
+ if (hash->buckets[i]) {
+ int n = 0;
+ Ecore_Hash_Node *node;
+ for (node = hash->buckets[i]; node; node = node->next)
+ n++;
+ printf("%d\t%u\n", i, n);
+ }
else
printf("%d\t0\n", i);
}
static int
-_ecore_hash_bucket_destroy(Ecore_List *list, Ecore_Free_Cb keyd, Ecore_Free_Cb
valued)
+_ecore_hash_bucket_destroy(Ecore_Hash_Node *list, Ecore_Free_Cb keyd,
Ecore_Free_Cb valued)
{
Ecore_Hash_Node *node;
CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
- while ((node = ecore_list_remove_first(list)) != NULL)
+ for (node = list; node; node = list) {
+ list = list->next;
_ecore_hash_node_destroy(node, keyd, valued);
-
- ecore_list_destroy(list);
+ }
return TRUE;
}
@@ -330,13 +334,9 @@
else
hash_val = ECORE_COMPUTE_HASH(hash, node->key);
- /* Create the list if it's not already present */
- if (!hash->buckets[hash_val])
- hash->buckets[hash_val] = ecore_list_new();
-
- /* Append the node to the list at the index position */
- if (!ecore_list_prepend(hash->buckets[hash_val], node))
- return FALSE;
+ /* Prepend the node to the list at the index position */
+ node->next = hash->buckets[hash_val];
+ hash->buckets[hash_val] = node;
hash->nodes++;
return TRUE;
@@ -381,7 +381,7 @@
void *ecore_hash_remove(Ecore_Hash *hash, void *key)
{
Ecore_Hash_Node *node = NULL;
- Ecore_List *list;
+ Ecore_Hash_Node *list;
unsigned int hash_val;
void *ret = NULL;
@@ -401,24 +401,32 @@
*/
if (hash->buckets[hash_val]) {
list = hash->buckets[hash_val];
- ecore_list_goto_first(list);
/*
* Traverse the list to find the specified key
*/
+ node = list;
if (hash->compare) {
- while ((node = ecore_list_current(list)) &&
- hash->compare(node->key, key) != 0)
- ecore_list_next(list);
+ while ((node) && (hash->compare(node->key, key) != 0)) {
+ list = node;
+ node = node->next;
+ }
}
else {
- while ((node = ecore_list_current(list)) &&
- node->key != key)
- ecore_list_next(list);
+ while ((node) && (node->key != key)) {
+ list = node;
+ node = node->next;
+ }
}
+ /*
+ * Remove the node with the matching key and free it's memory
+ */
if (node) {
- ecore_list_remove(list);
+ if (list == node)
+ hash->buckets[hash_val] = node->next;
+ else
+ list->next = node->next;
ret = node->value;
node->value = NULL;
_ecore_hash_node_destroy(node, hash->free_key,
@@ -450,6 +458,11 @@
ECORE_READ_LOCK(hash);
+ if (!hash->buckets) {
+ ECORE_READ_UNLOCK(hash);
+ return NULL;
+ }
+
/* Compute the position in the table */
if (!hash->hash_func)
hash_val = (unsigned int )key % ecore_prime_table[hash->size];
@@ -457,8 +470,17 @@
hash_val = ECORE_COMPUTE_HASH(hash, key);
/* Grab the bucket at the specified position */
- if (hash->buckets[hash_val])
+ if (hash->buckets[hash_val]) {
node = _ecore_hash_get_bucket(hash, hash->buckets[hash_val],
key);
+ /*
+ * Move matched node to the front of the list as it's likely
+ * to be searched for again soon.
+ */
+ if (node && node != hash->buckets[hash_val]) {
+ node->next = hash->buckets[hash_val];
+ hash->buckets[hash_val] = node;
+ }
+ }
ECORE_READ_UNLOCK(hash);
@@ -473,42 +495,52 @@
* @return Returns NULL on error or not found, the found node on success
*/
inline Ecore_Hash_Node *
-_ecore_hash_get_bucket(Ecore_Hash *hash, Ecore_List *bucket, void *key)
+_ecore_hash_get_bucket(Ecore_Hash *hash, Ecore_Hash_Node *bucket, void *key)
{
+ Ecore_Hash_Node *prev = NULL;
Ecore_Hash_Node *node = NULL;
ECORE_READ_LOCK(hash);
- ecore_list_goto_first(bucket);
/*
* Traverse the list to find the desired node, if the node is in the
* list, then return the node.
*/
if (hash->compare) {
- while ((node = ecore_list_next(bucket)) != NULL) {
+ for (node = bucket; node; node = node->next) {
ECORE_READ_LOCK(node);
- if (hash->compare(node->key, key) == 0) {
- ECORE_READ_UNLOCK(node);
- ECORE_READ_UNLOCK(hash);
- return node;
- }
+ if (hash->compare(node->key, key) == 0)
+ break;
+ prev = node;
ECORE_READ_UNLOCK(node);
}
}
else {
- while ((node = ecore_list_next(bucket)) != NULL) {
+ for (node = bucket; node; node = node->next) {
ECORE_READ_LOCK(node);
- if (node->key == key) {
- ECORE_READ_UNLOCK(node);
- ECORE_READ_UNLOCK(hash);
- return node;
- }
+ if (node->key == key)
+ break;
+ prev = node;
ECORE_READ_UNLOCK(node);
}
}
+
+ /*
+ * Remove node from the list to replace it at the beginning.
+ */
+ if (node && prev) {
+ ECORE_WRITE_LOCK(prev);
+ prev->next = node->next;
+ ECORE_WRITE_UNLOCK(prev);
+
+ ECORE_WRITE_LOCK(node);
+ node->next = NULL;
+ ECORE_WRITE_UNLOCK(node);
+ }
+
ECORE_READ_UNLOCK(hash);
- return NULL;
+ return node;
}
/*
@@ -536,8 +568,8 @@
/*
* Allocate a new bucket area, of the new larger size
*/
- hash->buckets = (Ecore_List **)calloc(ecore_prime_table[hash->size],
- sizeof(Ecore_List *));
+ hash->buckets = calloc(ecore_prime_table[hash->size],
+ sizeof(Ecore_Hash_Node *));
/*
* Make sure the allocation succeeded, if not replace the old data and
@@ -574,7 +606,7 @@
static int
_ecore_hash_decrease(Ecore_Hash *hash)
{
- Ecore_List **old;
+ Ecore_Hash_Node **old;
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
@@ -590,8 +622,8 @@
/*
* Allocate a new area to store the data
*/
- hash->buckets = (Ecore_List **)malloc(ecore_prime_table[hash->size] *
- sizeof(Ecore_List *));
+ hash->buckets = (Ecore_Hash_Node
**)calloc(ecore_prime_table[hash->size],
+ sizeof(Ecore_Hash_Node *));
/*
* Make sure allocation succeeded otherwise rreturn to the previous
@@ -603,11 +635,6 @@
return FALSE;
}
- /*
- * Zero out the new area
- */
- memset(hash->buckets, 0, ecore_prime_table[hash->size]
- * sizeof(Ecore_List *));
hash->nodes = 0;
if (_ecore_hash_rehash(hash, old, hash->size - 1)) {
@@ -625,11 +652,10 @@
* @return Returns TRUE on success, FALSE on success
*/
inline int
-_ecore_hash_rehash(Ecore_Hash *hash, Ecore_List **old_table, int old_size)
+_ecore_hash_rehash(Ecore_Hash *hash, Ecore_Hash_Node **old_table, int old_size)
{
unsigned int i;
- Ecore_Hash_Node *node;
- Ecore_List *old;
+ Ecore_Hash_Node *old;
CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
CHECK_PARAM_POINTER_RETURN("old_table", old_table, FALSE);
@@ -641,13 +667,10 @@
old_table[i] = NULL;
/* Loop through re-adding each node to the hash table */
- while (old && (node = ecore_list_remove_last(old))) {
- _ecore_hash_add_node(hash, node);
+ while ((old = old_table[i])) {
+ _ecore_hash_add_node(hash, old);
+ old_table[i] = old->next;
}
-
- /* Now free up the old list space */
- if (old)
- ecore_list_destroy(old);
}
return TRUE;
-------------------------------------------------------
This SF.Net email is sponsored by the JBoss Inc. Get Certified Today
Register for a JBoss Training Course. Free Certification Exam
for All Training Attendees Through End of 2005. For more info visit:
http://ads.osdn.com/?ad_id=7628&alloc_id=16845&op=click
_______________________________________________
enlightenment-cvs mailing list
enlightenment-cvs@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/enlightenment-cvs
