summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAllan McRae <allan@archlinux.org>2011-01-29 22:50:55 +1000
committerAllan McRae <allan@archlinux.org>2011-02-04 09:55:45 +1000
commit93207863493b54e794098b4ee5987d59c8c4b14b (patch)
treebc9014d31b0493190450143fca806163ab3d3433
parentc9820ec97b417d33dc37eb589f069766f1068ea1 (diff)
Rehash efficiently
Rehash without recreating the hash table list or reallocating the memory for holding the list nodes. Signed-off-by: Allan McRae <allan@archlinux.org>
-rw-r--r--lib/libalpm/pkghash.c24
1 files changed, 21 insertions, 3 deletions
diff --git a/lib/libalpm/pkghash.c b/lib/libalpm/pkghash.c
index 8f7168d2..44a03ab5 100644
--- a/lib/libalpm/pkghash.c
+++ b/lib/libalpm/pkghash.c
@@ -86,7 +86,8 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
{
pmpkghash_t *newhash;
alpm_list_t *ptr;
- size_t newsize;
+ size_t newsize, position, i;
+
/* Hash tables will need resized in two cases:
* - adding packages to the local database
* - poor estimation of the number of packages in sync database
@@ -112,10 +113,27 @@ static pmpkghash_t *rehash(pmpkghash_t *oldhash)
return(oldhash);
}
- for(ptr = oldhash->list; ptr != NULL; ptr = ptr->next) {
- newhash = _alpm_pkghash_add(newhash, ptr->data);
+ newhash->list = oldhash->list;
+ oldhash->list = NULL;
+
+ for(i = 0; i < oldhash->buckets; i++) {
+ if(oldhash->hash_table[i] != NULL) {
+ pmpkg_t *package = oldhash->hash_table[i]->data;
+
+ position = package->name_hash % newhash->buckets;
+
+ /* collision resolution using open addressing with linear probing */
+ while((ptr = newhash->hash_table[position]) != NULL) {
+ position = (position + 1) % newhash->buckets;
+ }
+
+ newhash->hash_table[position] = oldhash->hash_table[i];
+ oldhash->hash_table[i] = NULL;
+ }
}
+ newhash->entries = oldhash->entries;
+
_alpm_pkghash_free(oldhash);
return(newhash);