3 * Hash table implemenation
9 #define Bucket JOIN(HASHTYPE,Buket)
10 #define Bucket_s JOIN(HASHTYPE,Buket_s)
12 typedef struct Bucket_s * Bucket;
17 Bucket next; /*!< pointer to next item in bucket */
18 HTKEYTYPE key; /*!< hash key */
20 int dataCount; /*!< data entries */
21 HTDATATYPE data[1]; /*!< data - grows by resizing whole bucket */
28 int numBuckets; /*!< number of hash buckets */
29 Bucket * buckets; /*!< hash bucket array */
30 hashFunctionType fn; /*!< generate hash value for key */
31 hashEqualityType eq; /*!< compare hash keys for equality */
34 hashFreeData freeData;
39 * Find entry in hash table.
40 * @param ht pointer to hash table
41 * @param key pointer to key value
42 * @return pointer to hash bucket of key (or NULL)
45 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
50 hash = ht->fn(key) % ht->numBuckets;
51 b = ht->buckets[hash];
53 while (b && b->key && ht->eq(b->key, key))
59 HASHTYPE HASHPREFIX(Create)(int numBuckets,
60 hashFunctionType fn, hashEqualityType eq,
63 , hashFreeData freeData
69 ht = xmalloc(sizeof(*ht));
70 ht->numBuckets = numBuckets;
71 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
72 ht->freeKey = freeKey;
74 ht->freeData = freeData;
81 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
91 hash = ht->fn(key) % ht->numBuckets;
92 b = ht->buckets[hash];
93 b_addr = ht->buckets + hash;
95 while (b && b->key && ht->eq(b->key, key)) {
101 b = xmalloc(sizeof(*b));
107 b->next = ht->buckets[hash];
108 ht->buckets[hash] = b;
112 // resizing bucket TODO: increase exponentially
113 // Bucket_s already contains space for one dataset
114 b = *b_addr = xrealloc(
115 b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
116 // though increasing dataCount after the resize
117 b->data[b->dataCount++] = data;
122 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
127 for (i = 0; i < ht->numBuckets; i++) {
131 ht->buckets[i] = NULL;
133 b->key = ht->freeKey(b->key);
140 for (j=0; j < b->dataCount; j++ ) {
141 b->data[j] = ht->freeData(b->data[j]);
146 } while ((b = n) != NULL);
149 ht->buckets = _free(ht->buckets);
155 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
159 if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
164 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE** data,
165 int * dataCount, HTKEYTYPE* tableKey)
168 int rc = ((b = HASHPREFIX(findEntry)(ht, key)) != NULL);
171 *data = rc ? b->data : NULL;
173 *dataCount = rc ? b->dataCount : 0;
175 *tableKey = rc ? b->key : NULL;
180 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
184 int hashcnt=0, bucketcnt=0, datacnt=0;
187 for (i=0; i<ht->numBuckets; i++) {
189 for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
192 datacnt += bucket->dataCount;
195 if (maxbuckets < buckets) maxbuckets = buckets;
196 if (buckets) hashcnt++;
197 bucketcnt += buckets;
199 fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
200 fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
201 fprintf(stderr, "Keys: %i\n", bucketcnt);
202 fprintf(stderr, "Values: %i\n", datacnt);
203 fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);