diff options
Diffstat (limited to 'ghash.c')
| -rw-r--r-- | ghash.c | 414 |
1 files changed, 167 insertions, 247 deletions
@@ -24,7 +24,6 @@ typedef struct _GHashNode GHashNode; -typedef struct _GRealHashTable GRealHashTable; struct _GHashNode { @@ -33,7 +32,7 @@ struct _GHashNode GHashNode *next; }; -struct _GRealHashTable +struct _GHashTable { gint size; gint nnodes; @@ -44,17 +43,16 @@ struct _GRealHashTable }; -static void g_hash_table_resize (GHashTable *hash_table); -static gint g_hash_closest_prime (gint num); -static GHashNode* g_hash_node_new (gpointer key, - gpointer value); -static void g_hash_node_destroy (GHashNode *hash_node); -static void g_hash_nodes_destroy (GHashNode *hash_node); +static void g_hash_table_resize (GHashTable *hash_table); +static GHashNode** g_hash_table_lookup_node(GHashTable *hash_table, + gconstpointer key); +static gint g_hash_closest_prime (gint num); +static GHashNode* g_hash_node_new (gpointer key, + gpointer value); +static void g_hash_node_destroy (GHashNode *hash_node); +static void g_hash_nodes_destroy (GHashNode *hash_node); -extern gint g_primes[]; -extern gint g_nprimes; - static GMemChunk *node_mem_chunk = NULL; static GHashNode *node_free_list = NULL; @@ -63,38 +61,35 @@ GHashTable* g_hash_table_new (GHashFunc hash_func, GCompareFunc key_compare_func) { - GRealHashTable *hash_table; - - g_return_val_if_fail (hash_func != NULL, NULL); - - hash_table = g_new (GRealHashTable, 1); - hash_table->size = 0; + GHashTable *hash_table; + gint i; + + hash_table = g_new (GHashTable, 1); + hash_table->size = HASH_TABLE_MIN_SIZE; hash_table->nnodes = 0; hash_table->frozen = FALSE; - hash_table->nodes = NULL; - hash_table->hash_func = hash_func; + hash_table->hash_func = hash_func ? hash_func : g_direct_hash; hash_table->key_compare_func = key_compare_func; + hash_table->nodes = g_new (GHashNode*, hash_table->size); + + for (i = 0; i < hash_table->size; i++) + hash_table->nodes[i] = NULL; - return ((GHashTable*) hash_table); + return hash_table; } void g_hash_table_destroy (GHashTable *hash_table) { - GRealHashTable *rhash_table; gint i; - if (hash_table) - { - rhash_table = (GRealHashTable*) hash_table; - - for (i = 0; i < rhash_table->size; i++) - g_hash_nodes_destroy (rhash_table->nodes[i]); - - if (rhash_table->nodes) - g_free (rhash_table->nodes); - g_free (rhash_table); - } + g_return_if_fail (hash_table); + + for (i = 0; i < hash_table->size; i++) + g_hash_nodes_destroy (hash_table->nodes[i]); + + g_free (hash_table->nodes); + g_free (hash_table); } void @@ -102,45 +97,28 @@ g_hash_table_insert (GHashTable *hash_table, gpointer key, gpointer value) { - GRealHashTable *rhash_table; - GHashNode *node; - guint hash_val; + GHashNode **node; - if (hash_table) - { - rhash_table = (GRealHashTable*) hash_table; + g_return_if_fail (hash_table); + + node = g_hash_table_lookup_node (hash_table, key); - if (rhash_table->size == 0) + if (*node) + { + /* do not reset node->key in this place, keeping + * the old key might be intended. + * a g_hash_table_remove/g_hash_table_insert pair + * can be used otherwise. + * + * node->key = key; */ + (*node)->value = value; + } + else + { + *node = g_hash_node_new (key, value); + hash_table->nnodes++; + if (!hash_table->frozen) g_hash_table_resize (hash_table); - - hash_val = (* rhash_table->hash_func) (key) % rhash_table->size; - - node = rhash_table->nodes[hash_val]; - while (node) - { - if ((rhash_table->key_compare_func && - (* rhash_table->key_compare_func) (node->key, key)) || - (node->key == key)) - { - /* do not reset node->key in this place, keeping - * the old key might be intended. - * a g_hash_table_remove/g_hash_table_insert pair - * can be used otherwise. - * - * node->key = key; - */ - node->value = value; - return; - } - node = node->next; - } - - node = g_hash_node_new (key, value); - node->next = rhash_table->nodes[hash_val]; - rhash_table->nodes[hash_val] = node; - - rhash_table->nnodes += 1; - g_hash_table_resize (hash_table); } } @@ -148,110 +126,73 @@ void g_hash_table_remove (GHashTable *hash_table, gconstpointer key) { - GRealHashTable *rhash_table; - GHashNode *node; - GHashNode *prev; - guint hash_val; + GHashNode **node, *dest; + + g_return_if_fail (hash_table); - rhash_table = (GRealHashTable*) hash_table; - if (hash_table && rhash_table->size) + while (*(node = g_hash_table_lookup_node (hash_table, key))) { - hash_val = (* rhash_table->hash_func) (key) % rhash_table->size; - - prev = NULL; - node = rhash_table->nodes[hash_val]; - - while (node) - { - if ((rhash_table->key_compare_func && - (* rhash_table->key_compare_func) (node->key, key)) || - (node->key == key)) - { - if (prev) - prev->next = node->next; - if (node == rhash_table->nodes[hash_val]) - rhash_table->nodes[hash_val] = node->next; - - g_hash_node_destroy (node); - - rhash_table->nnodes -= 1; - g_hash_table_resize (hash_table); - break; - } - - prev = node; - node = node->next; - } + dest = *node; + (*node) = dest->next; + g_hash_node_destroy (dest); + hash_table->nnodes--; } + if (!hash_table->frozen) + g_hash_table_resize (hash_table); } gpointer g_hash_table_lookup (GHashTable *hash_table, gconstpointer key) { - GRealHashTable *rhash_table; GHashNode *node; - guint hash_val; + + g_return_val_if_fail (hash_table, NULL); + + node = *g_hash_table_lookup_node (hash_table, key); + return node ? node->value : NULL; +} - rhash_table = (GRealHashTable*) hash_table; - if (hash_table && rhash_table->size) +gboolean +g_hash_table_lookup_full (GHashTable *hash_table, + gconstpointer lookup_key, + gpointer *orig_key, + gpointer *value) +{ + GHashNode *node; + + g_return_val_if_fail (hash_table, FALSE); + + node = *g_hash_table_lookup_node (hash_table, lookup_key); + + if (node) { - hash_val = (* rhash_table->hash_func) (key) % rhash_table->size; - - node = rhash_table->nodes[hash_val]; - - /* Hash table lookup needs to be fast. - * We therefore remove the extra conditional of testing - * whether to call the key_compare_func or not from - * the inner loop. - */ - if (rhash_table->key_compare_func) - { - while (node) - { - if ((* rhash_table->key_compare_func) (node->key, key)) - return node->value; - node = node->next; - } - } - else - { - while (node) - { - if (node->key == key) - return node->value; - node = node->next; - } - } + if (orig_key) + *orig_key = node->key; + if (value) + *value = node->value; + return TRUE; } - - return NULL; + else + return FALSE; } void g_hash_table_freeze (GHashTable *hash_table) { - GRealHashTable *rhash_table; + g_return_if_fail (hash_table); - if (hash_table) - { - rhash_table = (GRealHashTable*) hash_table; - rhash_table->frozen = TRUE; - } + hash_table->frozen = TRUE; } void g_hash_table_thaw (GHashTable *hash_table) { - GRealHashTable *rhash_table; + g_return_if_fail (hash_table); - if (hash_table) - { - rhash_table = (GRealHashTable*) hash_table; - rhash_table->frozen = FALSE; + hash_table->frozen = FALSE; - g_hash_table_resize (hash_table); - } + g_hash_table_resize (hash_table); } void @@ -259,110 +200,96 @@ g_hash_table_foreach (GHashTable *hash_table, GHFunc func, gpointer user_data) { - GRealHashTable *rhash_table; GHashNode *node; gint i; - if (hash_table) - { - rhash_table = (GRealHashTable*) hash_table; - - for (i = 0; i < rhash_table->size; i++) - { - node = rhash_table->nodes[i]; - - while (node) - { - (* func) (node->key, node->value, user_data); - node = node->next; - } - } - } + g_return_if_fail (hash_table); + + for (i = 0; i < hash_table->size; i++) + for (node = hash_table->nodes[i]; node; node = node->next) + (* func) (node->key, node->value, user_data); } +/* Returns the number of elements contained in the hash table. */ +gint g_hash_table_size (GHashTable *hash_table) +{ + g_return_val_if_fail (hash_table, 0); + + return hash_table->nnodes; +} static void g_hash_table_resize (GHashTable *hash_table) { - GRealHashTable *rhash_table; GHashNode **new_nodes; GHashNode *node; GHashNode *next; gfloat nodes_per_list; guint hash_val; gint new_size; - gint need_resize; gint i; - if (hash_table) - { - rhash_table = (GRealHashTable*) hash_table; - - if (rhash_table->size == 0) - { - rhash_table->size = HASH_TABLE_MIN_SIZE; - rhash_table->nodes = g_new (GHashNode*, rhash_table->size); - - for (i = 0; i < rhash_table->size; i++) - rhash_table->nodes[i] = NULL; - } - else if (!rhash_table->frozen) - { - need_resize = FALSE; - nodes_per_list = (gfloat) rhash_table->nnodes / (gfloat) rhash_table->size; - - if (nodes_per_list < 0.3) - { - if (rhash_table->size > HASH_TABLE_MIN_SIZE) - need_resize = TRUE; - } - else if (nodes_per_list > 3.0) - { - if (rhash_table->size < HASH_TABLE_MAX_SIZE) - need_resize = TRUE; - } - - if (need_resize) - { - new_size = g_hash_closest_prime (rhash_table->nnodes); - if (new_size < HASH_TABLE_MIN_SIZE) - new_size = HASH_TABLE_MIN_SIZE; - else if (new_size > HASH_TABLE_MAX_SIZE) - new_size = HASH_TABLE_MAX_SIZE; - - new_nodes = g_new (GHashNode*, new_size); - - for (i = 0; i < new_size; i++) - new_nodes[i] = NULL; - - for (i = 0; i < rhash_table->size; i++) - { - node = rhash_table->nodes[i]; - - while (node) - { - next = node->next; - - hash_val = (* rhash_table->hash_func) (node->key) % new_size; - node->next = new_nodes[hash_val]; - new_nodes[hash_val] = node; - - node = next; - } - } - - g_free (rhash_table->nodes); - - rhash_table->nodes = new_nodes; - rhash_table->size = new_size; - } - } - } + g_return_if_fail (hash_table); + + nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size; + + if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) && + (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE)) + return; + + new_size = CLAMP(g_hash_closest_prime (hash_table->nnodes), + HASH_TABLE_MIN_SIZE, + HASH_TABLE_MAX_SIZE); + new_nodes = g_new (GHashNode*, new_size); + + for (i = 0; i < new_size; i++) + new_nodes[i] = NULL; + + for (i = 0; i < hash_table->size; i++) + for (node = hash_table->nodes[i]; node; node = next) + { + next = node->next; + hash_val = (* hash_table->hash_func) (node->key) % new_size; + node->next = new_nodes[hash_val]; + new_nodes[hash_val] = node; + } + + g_free (hash_table->nodes); + hash_table->nodes = new_nodes; + hash_table->size = new_size; +} + +static GHashNode ** +g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key) +{ + GHashNode **node; + + g_return_val_if_fail (hash_table, NULL); + + node = &hash_table->nodes + [(* hash_table->hash_func) (key) % hash_table->size]; + + /* Hash table lookup needs to be fast. + * We therefore remove the extra conditional of testing + * whether to call the key_compare_func or not from + * the inner loop. + */ + if (hash_table->key_compare_func) + while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) + node = &(*node)->next; + else + while (*node && (*node)->key != key) + node = &(*node)->next; + + return node; } static gint g_hash_closest_prime (gint num) { + extern gint g_primes[]; + extern gint g_nprimes; gint i; for (i = 0; i < g_nprimes; i++) @@ -403,11 +330,10 @@ g_hash_node_new (gpointer key, static void g_hash_node_destroy (GHashNode *hash_node) { - if (hash_node) - { - hash_node->next = node_free_list; - node_free_list = hash_node; - } + g_return_if_fail (hash_node); + + hash_node->next = node_free_list; + node_free_list = hash_node; } static void @@ -415,20 +341,14 @@ g_hash_nodes_destroy (GHashNode *hash_node) { GHashNode *node; - if (hash_node) - { - node = hash_node; - while (node->next) - node = node->next; - node->next = node_free_list; - node_free_list = hash_node; - } -} + if (!hash_node) + return; -/* Returns the number of elements contained in the hash table. */ -gint g_hash_table_size (GHashTable *hash_table) -{ - g_return_val_if_fail (hash_table, 0); + node = hash_node; + + while (node->next) + node = node->next; - return ((GRealHashTable *) hash_table)->nnodes; + node->next = node_free_list; + node_free_list = hash_node; } |