3 * Hash table implemenation
10 #define Bucket JOIN(HASHTYPE,Buket)
11 #define Bucket_s JOIN(HASHTYPE,Buket_s)
13 typedef struct Bucket_s * Bucket;
18 Bucket next; /*!< pointer to next item in bucket */
19 HTKEYTYPE key; /*!< hash key */
21 int dataCount; /*!< data entries */
22 HTDATATYPE data[1]; /*!< data - grows by resizing whole bucket */
29 int numBuckets; /*!< number of hash buckets */
30 Bucket * buckets; /*!< hash bucket array */
31 hashFunctionType fn; /*!< generate hash value for key */
32 hashEqualityType eq; /*!< compare hash keys for equality */
34 int bucketCount; /*!< number of used buckets */
35 int keyCount; /*!< number of keys */
37 int dataCount; /*!< number of data entries */
38 hashFreeData freeData;
43 * Find entry in hash table.
44 * @param ht pointer to hash table
45 * @param key pointer to key value
46 * @param keyHash key hash
47 * @return pointer to hash bucket of key (or NULL)
50 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
52 unsigned int hash = keyHash % ht->numBuckets;
53 Bucket b = ht->buckets[hash];
55 while (b && ht->eq(b->key, key))
61 HASHTYPE HASHPREFIX(Create)(int numBuckets,
62 hashFunctionType fn, hashEqualityType eq,
65 , hashFreeData freeData
71 ht = xmalloc(sizeof(*ht));
72 ht->numBuckets = numBuckets;
73 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
74 ht->freeKey = freeKey;
76 ht->freeData = freeData;
81 ht->bucketCount = ht->keyCount = 0;
85 static void HASHPREFIX(Resize)(HASHTYPE ht, int numBuckets) {
86 Bucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
88 for (int i=0; i<ht->numBuckets; i++) {
89 Bucket b = ht->buckets[i];
92 unsigned int hash = ht->fn(b->key) % numBuckets;
94 b->next = buckets[hash];
100 ht->buckets = buckets;
101 ht->numBuckets = numBuckets;
104 unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key)
109 void HASHPREFIX(AddHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash
115 unsigned int hash = keyHash % ht->numBuckets;
116 Bucket b = ht->buckets[hash];
118 Bucket * b_addr = ht->buckets + hash;
122 ht->bucketCount += 1;
125 while (b && ht->eq(b->key, key)) {
134 b = xmalloc(sizeof(*b));
140 b->next = ht->buckets[hash];
141 ht->buckets[hash] = b;
145 // resizing bucket TODO: increase exponentially
146 // Bucket_s already contains space for one dataset
147 b = *b_addr = xrealloc(
148 b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
149 // though increasing dataCount after the resize
150 b->data[b->dataCount++] = data;
154 if (ht->keyCount > ht->numBuckets) {
155 HASHPREFIX(Resize)(ht, ht->numBuckets * 2);
159 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
166 HASHPREFIX(AddHEntry)(ht, key, ht->fn(key), data);
168 HASHPREFIX(AddHEntry)(ht, key, ht->fn(key));
172 void HASHPREFIX(Empty)( HASHTYPE ht)
177 if (ht->bucketCount == 0) return;
179 for (i = 0; i < ht->numBuckets; i++) {
183 ht->buckets[i] = NULL;
188 b->key = ht->freeKey(b->key);
192 for (j=0; j < b->dataCount; j++ ) {
193 b->data[j] = ht->freeData(b->data[j]);
198 } while ((b = n) != NULL);
207 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
211 HASHPREFIX(Empty)(ht);
212 ht->buckets = _free(ht->buckets);
218 int HASHPREFIX(HasHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
222 if (!(b = HASHPREFIX(findEntry)(ht, key, keyHash))) return 0; else return 1;
225 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
227 return HASHPREFIX(HasHEntry)(ht, key, ht->fn(key));
230 int HASHPREFIX(GetHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash,
232 HTDATATYPE** data, int * dataCount,
237 int rc = ((b = HASHPREFIX(findEntry)(ht, key, keyHash)) != NULL);
241 *data = rc ? b->data : NULL;
243 *dataCount = rc ? b->dataCount : 0;
251 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
253 HTDATATYPE** data, int * dataCount,
257 return HASHPREFIX(GetHEntry)(ht, key, ht->fn(key),
264 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht) {
265 return ht->numBuckets;
268 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht) {
269 return ht->bucketCount;
272 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht) {
277 unsigned int HASHPREFIX(NumData)(HASHTYPE ht) {
278 return ht->dataCount;
283 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
287 int hashcnt=0, bucketcnt=0, datacnt=0;
290 for (i=0; i<ht->numBuckets; i++) {
292 for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
295 datacnt += bucket->dataCount;
298 if (maxbuckets < buckets) maxbuckets = buckets;
299 if (buckets) hashcnt++;
300 bucketcnt += buckets;
302 fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
303 fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
304 fprintf(stderr, "Keys: %i\n", bucketcnt);
305 fprintf(stderr, "Values: %i\n", datacnt);
306 fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);