From 93207863493b54e794098b4ee5987d59c8c4b14b Mon Sep 17 00:00:00 2001 From: Allan McRae Date: Sat, 29 Jan 2011 22:50:55 +1000 Subject: Rehash efficiently Rehash without recreating the hash table list or reallocating the memory for holding the list nodes. Signed-off-by: Allan McRae --- lib/libalpm/pkghash.c | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-) (limited to 'lib/libalpm') 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); -- cgit v1.2.3-70-g09d2