Author: pepeto
Date: Mon Jun 2 09:26:58 2014
New Revision: 25011
URL: http://svn.gna.org/viewcvs/freeciv?rev=25011&view=rev
Log:
Cache the hash values for every entry of the hash tables.
See gna patch #4730
Modified:
trunk/utility/genhash.c
Modified: trunk/utility/genhash.c
URL:
http://svn.gna.org/viewcvs/freeciv/trunk/utility/genhash.c?rev=25011&r1=25010&r2=25011&view=diff
==============================================================================
--- trunk/utility/genhash.c (original)
+++ trunk/utility/genhash.c Mon Jun 2 09:26:58 2014
@@ -75,6 +75,7 @@
struct genhash_entry {
void *key;
void *data;
+ genhash_val_t hash_val;
struct genhash_entry *next;
};
@@ -351,7 +352,6 @@
{
struct genhash_entry **new_buckets, **bucket, **end, **slot;
struct genhash_entry *iter, *next;
- genhash_val_fn_t key_val_func = pgenhash->key_val_func;
fc_assert(new_nbuckets >= pgenhash->num_entries);
@@ -361,7 +361,7 @@
end = bucket + pgenhash->num_buckets;
for (; bucket < end; bucket++) {
for (iter = *bucket; NULL != iter; iter = next) {
- slot = new_buckets + (key_val_func(iter->key) % new_nbuckets);
+ slot = new_buckets + (iter->hash_val % new_nbuckets);
next = iter->next;
iter->next = *slot;
*slot = iter;
@@ -424,14 +424,16 @@
it should go if it is to be a new key.
****************************************************************************/
static inline struct genhash_entry **
-genhash_slot_lookup(const struct genhash *pgenhash, const void *key)
+genhash_slot_lookup(const struct genhash *pgenhash,
+ const void *key,
+ genhash_val_t hash_val)
{
struct genhash_entry **slot;
- for (slot = (pgenhash->buckets
- + (pgenhash->key_val_func(key) % pgenhash->num_buckets));
+ for (slot = (pgenhash->buckets + (hash_val % pgenhash->num_buckets));
NULL != *slot; slot = &(*slot)->next) {
- if (pgenhash->key_comp_func((*slot)->key, key)) {
+ if (hash_val == (*slot)->hash_val
+ && pgenhash->key_comp_func((*slot)->key, key)) {
return slot;
}
}
@@ -472,12 +474,14 @@
****************************************************************************/
static inline void genhash_slot_create(struct genhash *pgenhash,
struct genhash_entry **slot,
- const void *key, const void *data)
+ const void *key, const void *data,
+ genhash_val_t hash_val)
{
struct genhash_entry *entry = fc_malloc(sizeof(*entry));
entry->key = pgenhash->key_copy_func(key);
entry->data = pgenhash->data_copy_func(data);
+ entry->hash_val = hash_val;
entry->next = *slot;
*slot = entry;
}
@@ -572,8 +576,10 @@
for (; src_bucket < end; src_bucket++, dest_bucket++) {
dest_slot = dest_bucket;
- for (src_iter = *src_bucket; NULL != src_iter; src_iter = src_iter->next) {
- genhash_slot_create(new_genhash, dest_slot, src_iter->key,
src_iter->data);
+ for (src_iter = *src_bucket; NULL != src_iter;
+ src_iter = src_iter->next) {
+ genhash_slot_create(new_genhash, dest_slot, src_iter->key,
+ src_iter->data, src_iter->hash_val);
dest_slot = &(*dest_slot)->next;
}
}
@@ -610,15 +616,17 @@
const void *data)
{
struct genhash_entry **slot;
+ genhash_val_t hash_val;
fc_assert_ret_val(NULL != pgenhash, FALSE);
genhash_maybe_expand(pgenhash);
- slot = genhash_slot_lookup(pgenhash, key);
+ hash_val = pgenhash->key_val_func(key);
+ slot = genhash_slot_lookup(pgenhash, key, hash_val);
if (NULL != *slot) {
return FALSE;
} else {
- genhash_slot_create(pgenhash, slot, key, data);
+ genhash_slot_create(pgenhash, slot, key, data, hash_val);
pgenhash->num_entries++;
return TRUE;
}
@@ -649,12 +657,14 @@
void **old_pdata)
{
struct genhash_entry **slot;
+ genhash_val_t hash_val;
fc_assert_action(NULL != pgenhash,
genhash_default_get(old_pkey, old_pdata); return FALSE);
genhash_maybe_expand(pgenhash);
- slot = genhash_slot_lookup(pgenhash, key);
+ hash_val = pgenhash->key_val_func(key);
+ slot = genhash_slot_lookup(pgenhash, key, hash_val);
if (NULL != *slot) {
/* Replace. */
genhash_slot_get(slot, old_pkey, old_pdata);
@@ -663,7 +673,7 @@
} else {
/* Insert. */
genhash_default_get(old_pkey, old_pdata);
- genhash_slot_create(pgenhash, slot, key, data);
+ genhash_slot_create(pgenhash, slot, key, data, hash_val);
pgenhash->num_entries++;
return FALSE;
}
@@ -681,7 +691,7 @@
fc_assert_action(NULL != pgenhash,
genhash_default_get(NULL, pdata); return FALSE);
- slot = genhash_slot_lookup(pgenhash, key);
+ slot = genhash_slot_lookup(pgenhash, key, pgenhash->key_val_func(key));
if (NULL != *slot) {
genhash_slot_get(slot, NULL, pdata);
return TRUE;
@@ -716,7 +726,7 @@
return FALSE);
genhash_maybe_shrink(pgenhash);
- slot = genhash_slot_lookup(pgenhash, key);
+ slot = genhash_slot_lookup(pgenhash, key, pgenhash->key_val_func(key));
if (NULL != *slot) {
genhash_slot_get(slot, deleted_pkey, deleted_pdata);
genhash_slot_free(pgenhash, slot);
@@ -775,7 +785,7 @@
max1 = bucket1 + pgenhash1->num_buckets;
for (; bucket1 < max1; bucket1++) {
for (iter1 = *bucket1; NULL != iter1; iter1 = iter1->next) {
- slot2 = genhash_slot_lookup(pgenhash2, iter1->key);
+ slot2 = genhash_slot_lookup(pgenhash2, iter1->key, iter1->hash_val);
if (NULL == *slot2
|| !data_comp_func(iter1->data, (*slot2)->data)) {
return FALSE;
_______________________________________________
Freeciv-commits mailing list
Freeciv-commits@gna.org
https://mail.gna.org/listinfo/freeciv-commits
