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 */
33 int bucketCount; /*!< number of used buckets */
34 int keyCount; /*!< number of keys */
36 int dataCount; /*!< number of data entries */
37 hashFreeData freeData;
42 * Find entry in hash table.
43 * @param ht pointer to hash table
44 * @param key pointer to key value
45 * @return pointer to hash bucket of key (or NULL)
48 Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
53 hash = ht->fn(key) % ht->numBuckets;
54 b = ht->buckets[hash];
56 while (b && ht->eq(b->key, key))
62 HASHTYPE HASHPREFIX(Create)(int numBuckets,
63 hashFunctionType fn, hashEqualityType eq,
66 , hashFreeData freeData
72 ht = xmalloc(sizeof(*ht));
73 ht->numBuckets = numBuckets;
74 ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
75 ht->freeKey = freeKey;
77 ht->freeData = freeData;
82 ht->bucketCount = ht->keyCount = 0;
86 static void HASHPREFIX(Resize)(HASHTYPE ht, int numBuckets) {
87 Bucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
89 for (int i=0; i<ht->numBuckets; i++) {
90 Bucket b = ht->buckets[i];
93 unsigned int hash = ht->fn(b->key) % numBuckets;
95 b->next = buckets[hash];
101 ht->buckets = buckets;
102 ht->numBuckets = numBuckets;
105 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
115 hash = ht->fn(key) % ht->numBuckets;
116 b = ht->buckets[hash];
117 b_addr = ht->buckets + hash;
120 ht->bucketCount += 1;
123 while (b && ht->eq(b->key, key)) {
130 b = xmalloc(sizeof(*b));
136 b->next = ht->buckets[hash];
137 ht->buckets[hash] = b;
141 // resizing bucket TODO: increase exponentially
142 // Bucket_s already contains space for one dataset
143 b = *b_addr = xrealloc(
144 b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
145 // though increasing dataCount after the resize
146 b->data[b->dataCount++] = data;
150 if (ht->keyCount > ht->numBuckets) {
151 HASHPREFIX(Resize)(ht, ht->numBuckets * 2);
155 void HASHPREFIX(Empty)( HASHTYPE ht)
160 if (ht->bucketCount == 0) return;
162 for (i = 0; i < ht->numBuckets; i++) {
166 ht->buckets[i] = NULL;
171 b->key = ht->freeKey(b->key);
175 for (j=0; j < b->dataCount; j++ ) {
176 b->data[j] = ht->freeData(b->data[j]);
181 } while ((b = n) != NULL);
190 HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
194 HASHPREFIX(Empty)(ht);
195 ht->buckets = _free(ht->buckets);
201 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
205 if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
208 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
210 HTDATATYPE** data, int * dataCount,
215 int rc = ((b = HASHPREFIX(findEntry)(ht, key)) != NULL);
219 *data = rc ? b->data : NULL;
221 *dataCount = rc ? b->dataCount : 0;
229 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht) {
230 return ht->numBuckets;
233 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht) {
234 return ht->bucketCount;
237 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht) {
242 unsigned int HASHPREFIX(NumData)(HASHTYPE ht) {
243 return ht->dataCount;
248 void HASHPREFIX(PrintStats)(HASHTYPE ht) {
252 int hashcnt=0, bucketcnt=0, datacnt=0;
255 for (i=0; i<ht->numBuckets; i++) {
257 for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
260 datacnt += bucket->dataCount;
263 if (maxbuckets < buckets) maxbuckets = buckets;
264 if (buckets) hashcnt++;
265 bucketcnt += buckets;
267 fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
268 fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
269 fprintf(stderr, "Keys: %i\n", bucketcnt);
270 fprintf(stderr, "Values: %i\n", datacnt);
271 fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);