· 7 years ago · Dec 14, 2018, 07:34 PM
1#include <err.h>
2#include <string.h>
3#include <stdio.h>
4
5#include "htab.h"
6
7void print_htab(struct htab*);
8
9uint32_t hash(char *key)
10{
11 uint32_t hash = 0;
12 size_t i = 0, len = strlen(key);
13
14 for(;i < len;)
15 {
16 hash += key[i];
17 hash += (hash << 10);
18 hash ^= (hash >> 6);
19 ++i;
20 }
21 hash += (hash << 3);
22 hash ^= (hash >> 11);
23 hash += (hash << 15);
24 return hash;
25}
26
27void pair_free(struct pair* rm){
28 if(rm && rm->next)
29 pair_free(rm->next);
30 free(rm);
31}
32
33struct htab *htab_new()
34{
35 struct htab *table = malloc(sizeof(struct htab));
36 if(table == NULL){
37 errx(1,"Not enough memory!");
38 exit(EXIT_FAILURE);
39 }
40 table->capacity = 4;
41 table->size = 0;
42 table->data = malloc(sizeof(struct pair) * table->capacity);
43 if(table->data == NULL)
44 errx(1,"Not enough memory!");
45
46 for(size_t i = 0; i < table->capacity; i++)
47 {
48 struct pair sentinel = {0,0,0,NULL};
49 *(table->data + i) = sentinel;
50 }
51
52 return table;
53}
54
55/*
56void htab_clear(struct htab *ht)
57{ //Maybe change to CALLOC
58 for(int i = 0; i < ht->capacity ; i++){
59
60 //malloc 11 - free 18 WHY???
61 if((ht->data + i)->next){
62
63 struct pair *rm = ht->data + i;
64 pair_free(rm->next);
65 rm->next = NULL;
66 }
67
68 struct pair *rm = ht->data + i;
69 while(rm != NULL && rm->next != NULL){
70 struct pair *tmp = rm->next;
71 rm->next = NULL;
72 rm = tmp->next;
73 //free(tmp->key);
74 free(tmp);
75 }
76
77
78 }
79 ht->size = 0;
80}
81*/
82
83void htab_clear(struct htab *ht)
84{ //CHANGE TO CALLOC
85// print_htab(ht);
86 for(int i = ht->capacity-1; i >= 0 ; i--){
87 struct pair *rm = ht->data + i;
88 while(rm != NULL && rm->next != NULL){
89 struct pair *tmp = rm->next;
90 rm->next = NULL;
91 rm = tmp->next;
92 //free(tmp->key);
93 free(tmp);
94 }
95 }
96 ht->size = 0;
97}
98
99void htab_free(struct htab *ht)
100{
101 htab_clear(ht);
102 free(ht->data);
103 free(ht);
104}
105
106struct pair *htab_get(struct htab *ht, char *key)
107{
108 int found = 0;
109 uint32_t hashed = hash(key);
110 int i = hashed % ht->capacity;
111
112 struct pair *res = (ht->data + i)->next;
113 while(res && !found)
114 {
115 if(res->key == key)
116 found = 1;
117 res = res->next;
118 }
119
120 return res;
121}
122
123struct htab *autoresize(struct htab *htable)
124{
125 struct htab *table = malloc(sizeof(struct htab));
126 if(table == NULL){
127 errx(1,"Not enough memory!");
128 exit(EXIT_FAILURE);
129 }
130 table->capacity = 2 * htable->capacity;
131 table->size = 0;
132 table->data = malloc(sizeof(struct pair) * table->capacity);
133 if(table->data == NULL)
134 errx(1,"Not enough memory!");
135
136 for(size_t i = 0; i < table->capacity; i++)
137 {
138 struct pair sentinel = {0,0,0,NULL};
139 *(table->data + i) = sentinel;
140 while((htable->data +i)->next != NULL)
141 {
142 htab_insert(table, (htable->data + i)->key, (htable->data + i)->value);
143 (htable->data + i)->next = (htable->data + i)->next->next;
144 }
145 }
146
147 htab_clear(htable);
148
149return table;
150}
151
152int htab_insert(struct htab *ht, char *key, void *value)
153{
154 uint32_t elem = hash(key);
155
156 struct pair *ex = htab_get(ht,key);
157 if(ex != NULL){
158 if(!strcmp(ex->key, key))
159 ex->value = value;
160 printf("key already exists!");
161 return 0;
162 }
163
164 // Create new pair
165 struct pair *pt_pair = malloc(sizeof(struct pair));
166
167 pt_pair->hkey = elem;
168 //pt_pair->key = malloc(sizeof(char) * strlen(key));
169 pt_pair->key = key;
170 pt_pair->value = value;
171
172 pt_pair->next = NULL;
173
174
175 //check if pair's list is empty
176 uint32_t x = elem % ht->capacity;
177 if((ht->data + x)->next == NULL){
178 int ratio = 100 * ht->size / ht->capacity;
179
180 //If empty and ratio lower than 75
181 if(ratio < 75){
182 (ht->data + x)->next = pt_pair;
183 ht->size++;
184 }
185 else{
186 ht->capacity *= 2;
187 int kkk = ht->capacity;
188 struct pair *new_data = realloc(ht->data, kkk * sizeof(struct pair));
189 ht->data = new_data;
190
191 /*struct htab *newtable = autoresize(ht);
192 htab_free(ht);
193 struct htab *ht = newtable;*/
194
195 if(ht->data == NULL)
196 errx(1, "Not enough memory!");
197 //Replace all the elements :
198 for(size_t i = 0; i < ht->capacity/2; i++){
199
200 if((ht->data + i)->next){
201 struct pair* p = (ht->data + i);
202 while(p->next != NULL){
203 size_t new_i = p->next->hkey % ht->capacity;
204 if(i != new_i){
205 struct pair *toChange = p->next;
206 p->next = toChange->next;
207 toChange->next = (ht->data + new_i)->next;
208 (ht->data + new_i)->next = toChange;
209 }
210 else
211 p = p->next;
212 }
213
214 }
215 }
216
217 //Place the element
218 if((ht->data + x)->next == NULL){
219 (ht->data + x)->next = pt_pair;
220 ht->size++;
221 }
222 else{
223 pt_pair->next = (ht->data + x)->next;
224 (ht->data + x)->next = pt_pair;
225 }
226
227
228 }
229
230 }
231
232 else{
233 pt_pair->next = (ht->data + x)->next;
234 (ht->data + x)->next = pt_pair;
235 }
236 return 1;
237}
238
239void htab_remove(struct htab *ht, char *key)
240{
241 uint32_t elem = hash(key);
242 size_t i = elem % ht->capacity;
243 //int c = 0;
244 struct pair *pair = (ht->data + i);
245 while(pair->next && strcmp(key, pair->next->key) != 0){
246 pair = pair->next;
247 }
248
249 if(pair->next != NULL){
250 struct pair* rm = pair->next;
251 pair->next = rm->next;
252 rm->next = NULL;
253 free(rm);
254 }
255}
256
257
258
259
260void print_htab(struct htab* ht)
261{
262 puts("{");
263
264 for (size_t i = 0; i < ht->capacity; i++) {
265 struct pair* p = ht->data + i;
266
267 while (p->next) {
268 p = p->next;
269
270 printf("%lu - (%u) \"%s\" = \"%s\";\n",i, p->hkey, p->key,
271 (char*)p->value);
272 }
273 }
274
275 puts("}\n");
276}
277
278void print_pair(struct htab* ht, char* key)
279{
280 struct pair* p = htab_get(ht, key);
281
282 if (p == NULL)
283 puts("NULL");
284 else
285 printf("{ hkey = %u, key = \"%s\", value = \"%s\" }\n", p->hkey, p->key, (char*)p->value);
286}
287
288// http://debug-pro.com/epita/prog/s3/pw/pw_07_hash_tables
289int main()
290{
291
292
293
294 printf("%#08x -> %#08x \n",hash("France"), 0xd1f87070);
295 printf("%#08x -> %#08x \n",hash("Spain"), 0xa394a0be);
296 printf("%#08x -> %#08x \n",hash("Jamaica"), 0x82b25036);
297 printf("%#08x -> %#08x \n",hash("Cuba"), 0x2238f8bb);
298 printf("%#08x -> %#08x \n",hash("Turkey"), 0x06371821);
299
300
301 struct htab* ht = htab_new();
302
303 printf("Empty:\n");
304 print_htab(ht);
305
306 printf("Adding France -> paris:\n");
307 htab_insert(ht, "France", "Paris");
308 print_htab(ht);
309
310 printf("Getting 'france': ");
311 print_pair(ht, "France");
312
313 printf("Getting 'baz': ");
314 print_pair(ht, "baz");
315 puts("");
316
317 printf("Adding foo -> foo:\n");
318 htab_insert(ht, "foo", "foo");
319 print_htab(ht);
320
321 htab_insert(ht, "Spain", "Madrid");
322 print_htab(ht);
323
324 htab_insert(ht, "Jamaica", "Kingston");
325 print_htab(ht);
326
327
328 htab_insert(ht, "Iraq", "Baghdad");
329 print_htab(ht);
330
331 printf("Adding foo -> foo:\n");
332 htab_insert(ht, "Cuba", "Havana");
333 print_htab(ht);
334
335 htab_insert(ht, "Turkey", "Ankara");
336 print_htab(ht);
337
338
339/*
340 printf("Removing 'foo':\n");
341 htab_remove(ht, "foo");
342 print_htab(ht);
343
344 printf("Adding 42 -> 1337:\n");
345 htab_insert(ht, "42", "1337");
346 print_htab(ht);
347
348 puts("Clearing:");
349 htab_clear(ht);
350 print_htab(ht);
351
352 puts("Stress test:");
353 for (size_t i = 0; i < 1000; i++) {
354 size_t len = 4 + rand() % 20;
355 char* buf = malloc(len + 1);
356
357 buf[len] = 0;
358
359 for (size_t j = 0; j < len; j++)
360 buf[j] = 'a' + (rand() % 26);
361
362 htab_insert(ht, buf, "useless placeholder /╲/\\â•( ͡° ͡° ͜ʖ ͡° ͡°)â•®/\\╱\\");
363 }
364 print_htab(ht);*/
365
366 puts("Clearing:");
367 htab_clear(ht);
368 print_htab(ht);
369
370 htab_free(ht);
371 return 0;
372}