diff options
Diffstat (limited to 'lib/rpmhash.C')
| -rw-r--r-- | lib/rpmhash.C | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/lib/rpmhash.C b/lib/rpmhash.C index 79a82b0d7..d8cfdd76e 100644 --- a/lib/rpmhash.C +++ b/lib/rpmhash.C @@ -30,7 +30,10 @@ struct HASHSTRUCT { hashFunctionType fn; /*!< generate hash value for key */ hashEqualityType eq; /*!< compare hash keys for equality */ hashFreeKey freeKey; + int bucketCount; /*!< number of used buckets */ + int keyCount; /*!< number of keys */ #ifdef HTDATATYPE + int dataCount; /*!< number of data entries */ hashFreeData freeData; #endif }; @@ -72,12 +75,33 @@ HASHTYPE HASHPREFIX(Create)(int numBuckets, ht->freeKey = freeKey; #ifdef HTDATATYPE ht->freeData = freeData; + ht->dataCount = 0; #endif ht->fn = fn; ht->eq = eq; + ht->bucketCount = ht->keyCount = 0; return ht; } +static HASHPREFIX(Resize)(HASHTYPE ht, int numBuckets) { + Bucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets)); + + for (int i=0; i<ht->numBuckets; i++) { + Bucket b = ht->buckets[i]; + Bucket nextB; + while (b != NULL) { + unsigned int hash = ht->fn(b->key) % numBuckets; + nextB = b->next; + b->next = buckets[hash]; + buckets[hash] = b; + b = nextB; + } + } + free(ht->buckets); + ht->buckets = buckets; + ht->numBuckets = numBuckets; +} + void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key #ifdef HTDATATYPE , HTDATATYPE data @@ -92,12 +116,17 @@ void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key b = ht->buckets[hash]; b_addr = ht->buckets + hash; + if (b == NULL) { + ht->bucketCount += 1; + } + while (b && ht->eq(b->key, key)) { b_addr = &(b->next); b = b->next; } if (b == NULL) { + ht->keyCount += 1; b = xmalloc(sizeof(*b)); b->key = key; #ifdef HTDATATYPE @@ -116,7 +145,11 @@ void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key // though increasing dataCount after the resize b->data[b->dataCount++] = data; } + ht->dataCount += 1; #endif + if (ht->keyCount > ht->numBuckets) { + HASHPREFIX(Resize)(ht, ht->numBuckets * 2); + } } HASHTYPE HASHPREFIX(Free)(HASHTYPE ht) |