1 #include "khtable.h"
2 #include <stdlib.h>
3 #include <string.h>
4 #include "rmalloc.h"
5
6 static uint32_t primes[] = {5ul, 11ul, 23ul, 47ul, 97ul, 199ul,
7 409ul, 823ul, 1741ul, 3469ul, 6949ul, 14033ul,
8 28411ul, 57557ul, 116731ul, 236897ul, 480881ul, 976369ul,
9 1982627ul, 4026031ul, 8175383ul, 16601593ul, 33712729ul, 68460391ul,
10 139022417ul, 282312799ul, 0};
11
KHTable_Init(KHTable * table,const KHTableProcs * procs,void * ctx,size_t estSize)12 void KHTable_Init(KHTable *table, const KHTableProcs *procs, void *ctx, size_t estSize) {
13 // Traverse a list of primes until we find one suitable
14 uint32_t *p;
15 for (p = primes; *p; p++) {
16 if (*p > estSize) {
17 table->numBuckets = *p;
18 break;
19 }
20 }
21 if (*p == 0) {
22 p--;
23 table->numBuckets = *p;
24 }
25
26 table->buckets = rm_calloc(sizeof(*table->buckets), table->numBuckets);
27 table->numItems = 0;
28 table->procs = *procs;
29 table->alloc = ctx;
30 }
31
KHTable_Free(KHTable * table)32 void KHTable_Free(KHTable *table) {
33 rm_free(table->buckets);
34 }
35
KHTable_Clear(KHTable * table)36 void KHTable_Clear(KHTable *table) {
37 memset(table->buckets, 0, sizeof(*table->buckets) * table->numBuckets);
38 table->numItems = 0;
39 }
40
KHTable_Rehash(KHTable * table)41 static int KHTable_Rehash(KHTable *table) {
42 // Find new capacity
43 size_t newCapacity = 0;
44 for (uint32_t *p = primes; *p; p++) {
45 if (*p > table->numItems) {
46 newCapacity = *p;
47 break;
48 }
49 }
50
51 if (!newCapacity) {
52 return 0;
53 }
54
55 // printf("Rehashing %lu -> %lu\n", table->numBuckets, newCapacity);
56
57 KHTableEntry **newEntries = rm_calloc(newCapacity, sizeof(*table->buckets));
58 for (size_t ii = 0; ii < table->numBuckets; ++ii) {
59
60 KHTableEntry *cur = table->buckets[ii];
61 while (cur) {
62 uint32_t hash = table->procs.Hash(cur);
63 KHTableEntry **newBucket = newEntries + (hash % newCapacity);
64 KHTableEntry *next = cur->next;
65 if (*newBucket) {
66 cur->next = *newBucket;
67 } else {
68 cur->next = NULL;
69 }
70 *newBucket = cur;
71 cur = next;
72 }
73 }
74
75 rm_free(table->buckets);
76 table->buckets = newEntries;
77 table->numBuckets = newCapacity;
78
79 return 1;
80 }
81
KHTable_InsertNewEntry(KHTable * table,uint32_t hash,KHTableEntry ** bucketHead)82 static KHTableEntry *KHTable_InsertNewEntry(KHTable *table, uint32_t hash,
83 KHTableEntry **bucketHead) {
84 if (++table->numItems == table->numBuckets) {
85 KHTable_Rehash(table);
86 bucketHead = table->buckets + (hash % table->numBuckets);
87 }
88 KHTableEntry *entry = table->procs.Alloc(table->alloc);
89 if (*bucketHead) {
90 entry->next = *bucketHead;
91 } else {
92 entry->next = NULL;
93 }
94 *bucketHead = entry;
95 return entry;
96 }
97
98 /**
99 * Return an entry for the given key, creating one if it does not already exist.
100 */
KHTable_GetEntry(KHTable * table,const void * s,size_t n,uint32_t hash,int * isNew)101 KHTableEntry *KHTable_GetEntry(KHTable *table, const void *s, size_t n, uint32_t hash, int *isNew) {
102 // Find the bucket
103 uint32_t ix = hash % table->numBuckets;
104 KHTableEntry **bucket = table->buckets + ix;
105
106 if (*bucket == NULL) {
107 if (!isNew) {
108 return NULL;
109 }
110 *isNew = 1;
111 // Most likely case - no need for rehashing
112 if (++table->numItems != table->numBuckets) {
113 *bucket = table->procs.Alloc(table->alloc);
114 (*bucket)->next = NULL;
115 return *bucket;
116 } else {
117 KHTable_Rehash(table);
118 KHTableEntry *ret =
119 KHTable_InsertNewEntry(table, hash, table->buckets + (hash % table->numBuckets));
120 // Decrement the count again
121 table->numItems--;
122 return ret;
123 }
124 }
125
126 for (KHTableEntry *cur = *bucket; cur; cur = cur->next) {
127 if (table->procs.Compare(cur, s, n, hash) == 0) {
128 return cur;
129 }
130 }
131
132 if (!isNew) {
133 return NULL;
134 }
135
136 *isNew = 1;
137 return KHTable_InsertNewEntry(table, hash, bucket);
138 }
139
KHTableIter_Init(KHTable * ht,KHTableIterator * iter)140 void KHTableIter_Init(KHTable *ht, KHTableIterator *iter) {
141 iter->ht = ht;
142 iter->curBucket = 0;
143 iter->cur = ht->buckets[iter->curBucket];
144 }
145
KHtableIter_Next(KHTableIterator * iter)146 KHTableEntry *KHtableIter_Next(KHTableIterator *iter) {
147 KHTableEntry *ret = iter->cur;
148
149 if (!iter->cur) {
150 for (++iter->curBucket; iter->curBucket < iter->ht->numBuckets; ++iter->curBucket) {
151 iter->cur = iter->ht->buckets[iter->curBucket];
152 if (iter->cur) {
153 ret = iter->cur;
154 break;
155 }
156 }
157 }
158
159 if (iter->cur) {
160 iter->cur = iter->cur->next;
161 }
162 return ret;
163 }
164
KHTable_FreeEx(KHTable * table,void * arg,void (* Free)(KHTableEntry * e,void * ctx,void * arg))165 void KHTable_FreeEx(KHTable *table, void *arg,
166 void (*Free)(KHTableEntry *e, void *ctx, void *arg)) {
167 KHTableIterator iter;
168 KHTableIter_Init(table, &iter);
169 KHTableEntry *ent;
170 while ((ent = KHtableIter_Next(&iter))) {
171 Free(ent, table->alloc, arg);
172 }
173 KHTable_Free(table);
174 }
175
khTable_Dump(const KHTable * table,FILE * fp)176 static void khTable_Dump(const KHTable *table, FILE *fp) {
177 printf("Table=%p\n", table);
178 printf("NumEntries: %lu\n", table->numItems);
179 printf("NumBuckets: %lu\n", table->numBuckets);
180 for (size_t ii = 0; ii < table->numBuckets; ++ii) {
181 KHTableEntry *baseEnt = table->buckets[ii];
182 if (!baseEnt) {
183 continue;
184 }
185 printf("Bucket[%lu]\n", ii);
186 for (; baseEnt; baseEnt = baseEnt->next) {
187 printf(" => ");
188 if (table->procs.Print) {
189 table->procs.Print(baseEnt, fp);
190 } else {
191 fprintf(fp, "%p", baseEnt);
192 }
193 }
194 }
195 }
196