1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "common.h"
#include "hashtbl.h"
static struct hash_item *hash_item_alloc();
static void hash_item_reset_rec(struct hash_item *item, bool should_free);
static struct hash_item *hash_item_find(struct hash_item *item, char *key, bool create);
static size_t hash(char *str)
{
size_t hash = 5381;
char c;
while ((c = *str++) != 0)
hash = ((hash << 5) + hash) + (size_t)c;
// return hash;
return 0;
}
// ---------- Exported Functions ---------- //
hashtbl_t hashtbl_create(size_t cap)
{
hashtbl_t hashtbl = xmalloc(sizeof(*hashtbl));
hashtbl->cap = cap;
hashtbl->items = xcalloc(hashtbl->cap, sizeof(*hashtbl->items));
for(size_t i = 0; i < hashtbl->cap; i++) {
hashtbl->items[i] = hash_item_alloc();
}
return hashtbl;
}
void hashtbl_destroy(hashtbl_t hashtbl)
{
if(hashtbl == NULL) return;
for(int i = 0; i < hashtbl->cap; i++) {
hash_item_reset_rec(hashtbl->items[i], true);
}
free(hashtbl->items);
free(hashtbl);
}
void hashtbl_reset(hashtbl_t hashtbl)
{
for(int i = 0; i < hashtbl->cap; i++) {
hash_item_reset_rec(hashtbl->items[i]->next, true);
hash_item_reset_rec(hashtbl->items[i]->next, false);
}
}
#define HEAD_ITEM (hashtbl->items[hash(key) % hashtbl->cap])
int hashtbl_insert(hashtbl_t hashtbl, char *key, void *data, size_t data_sz)
{
struct hash_item *item = hash_item_find(HEAD_ITEM, key, true);
if(item->data) free(item->data);
item->data = xmalloc(data_sz);
memcpy(item->data, data, data_sz);
return 0;
}
int hashtbl_query(hashtbl_t hashtbl, char *key, void **dest)
{
struct hash_item *item = hash_item_find(HEAD_ITEM, key, false);
if(item == NULL) return 1;
if(dest != NULL) *dest = item->data;
return 0;
}
// ---------- Helper Functions ---------- //
static struct hash_item *hash_item_alloc()
{
struct hash_item *item = xmalloc(sizeof(struct hash_item));
item->next = NULL;
item->key = NULL;
item->data = NULL;
return item;
}
static void hash_item_reset_rec(struct hash_item *item, bool should_free)
{
if(item == NULL) return;
if(item->key) free(item->key);
if(item->data) free(item->data);
hash_item_reset_rec(item->next, should_free);
if(should_free) free(item);
}
static struct hash_item *hash_item_find(struct hash_item *item, char *key, bool create)
{
if(item-> key == NULL) {
if(!create) return NULL;
item->key = xmalloc(strlen(key) + 1);
strcpy(item->key, key);
return item;
}
if(strcmp(key, item->key) == 0) {
return item;
}
if(item->next == NULL) {
if(!create) return NULL;
struct hash_item *next = hash_item_alloc();
next->key = xmalloc(strlen(key) + 1);
strcpy(next->key, key);
item->next = next;
return item->next;
}
return hash_item_find(item->next, key, create);
}
|
