1 #include <stdint.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5
6 #define HASH_BUCKET_MAX (1024)
7 #define HASH_BUCKET_CAPACITY_MAX (256)
8 #define HASHTABLE_DEBUG
9 #define TRUE 1
10 #define FALSE 0
11
12 #ifdef HASHTABLE_DEBUG
13 #define DEBUG(format, ...) printf("[%s] [%d] : "format"
", __FUNCTION__, __LINE__, __VA_ARGS__)
14 #else
15 #define DEBUG(format, ...)
16 #endif
17
18 struct hash_bucket {
19 int capacity; /* 桶的容量 */
20 void *hkey; /* hashtable的key */
21 void *hdata; /* hashtable的data */
22 struct hash_bucket *prev;
23 struct hash_bucket *next;
24 struct hash_bucket *tail;
25 };
26
27 struct hash {
28 uint32_t (*hash_key)(void *);
29 int (*hash_cmp)(const void *, const void*, int len);
30 struct hash_bucket* bucket[HASH_BUCKET_MAX];
31 };
32
33 uint32_t string_hash_key(void* str);
34 int string_hash_cmp(const void* src, const void* dst);
35
36 static struct hash *g_htable = NULL;
37
38 void hash_create();
39 void *hash_lookup(void *key);
40 int hash_add(void *key, void* data);
41 int hash_delete(void *key);
42 void hash_destroy();
43 void hash_iter_print();
44
45 #define bucket_free(bucket)
46 free(bucket->hkey);
47 free(bucket->hdata);
48 free(bucket);
49 bucket = NULL;
50
51 uint32_t string_hash_key(void* str) {
52 char *tmp = (char *)str;
53 uint32_t key = 0;
54 while(*tmp)
55 key = (key * 33) ^ (uint32_t)(tmp++);
56
57 DEBUG("string key : %u, index : %d", key, key%HASH_BUCKET_MAX);
58
59 return key%HASH_BUCKET_MAX;
60 }
61
62 int string_hash_cmp(const void* src, const void* dst, int len) {
63 if (!src || !dst) {
64 DEBUG("src addr: %p, dst addr: %p", src, dst);
65 return -1;
66 }
67 return strncmp((char *)src, (char *)dst, len);
68 }
69
70 void hash_create() {
71 if (g_htable) {
72 DEBUG("the default hashtable is already created");
73 return;
74 }
75
76 g_htable = (struct hash *)malloc(sizeof(struct hash));
77 if (!g_htable) {
78 DEBUG("memory alloc failed.");
79 return;
80 }
81
82 memset(g_htable, 0, sizeof(struct hash));
83
84 g_htable->hash_key = string_hash_key;
85 g_htable->hash_cmp = string_hash_cmp;
86
87 return;
88 }
89
90 static void bucket_delete(struct hash_bucket** ptr) {
91 struct hash_bucket *bucket = *ptr;
92 struct hash_bucket *tmp;
93
94 while(bucket) {
95 tmp = bucket;
96 bucket = bucket->next;
97 bucket_free(tmp);
98 }
99 }
100
101 void hash_destroy() {
102 if (g_htable) {
103 for(int i=0; i<HASH_BUCKET_MAX; i++) {
104 if (g_htable->bucket[i]) {
105 bucket_delete(&g_htable->bucket[i]);
106 }
107 }
108
109 free(g_htable);
110 g_htable = NULL;
111 }
112 return;
113 }
114
115 #define lru_bucket_move(bucket, head)
116 bucket->next = head;
117 bucket->prev = NULL;
118 bucket->capacity = head->capacity;
119
120 head->prev = bucket;
121 head->tail = NULL;
122
123 void *hash_lookup(void *key) {
124 if (!key) {
125 DEBUG("input para is NULL
");
126 return NULL;
127 }
128
129 uint32_t index = g_htable->hash_key(key);
130 struct hash_bucket* head = g_htable->bucket[index];
131 struct hash_bucket* bucket = head;
132
133 while(bucket) {
134 if (0 == g_htable->hash_cmp(key, bucket->hkey, strlen((char*)key))) {
135 if (head != bucket && bucket != head->tail) {
136 bucket->prev->next = bucket->next;
137 bucket->next->prev = bucket->prev;
138 bucket->tail = head->tail;
139
140 lru_bucket_move(bucket, head);
141 } else if (bucket == head->tail && head->capacity>1) {
142 bucket->prev->next = NULL;
143 bucket->tail = bucket->prev;
144
145 lru_bucket_move(bucket, head);
146 }
147 g_htable->bucket[index] = bucket;
148 return bucket->hdata;
149 }
150 bucket = bucket->next;
151 }
152 return NULL;
153 }
154
155 int hash_add(void *key, void* data) {
156 if (!key || !data) {
157 DEBUG("input para is NULL
");
158 return FALSE;
159 }
160
161 uint32_t index = g_htable->hash_key(key);
162 struct hash_bucket* head = g_htable->bucket[index];
163
164 if (!head) {
165 head = (struct hash_bucket*)malloc(sizeof(struct hash_bucket));
166 if (!head) {
167 DEBUG("no memory for more hash_bucket
");
168 return FALSE;
169 }
170
171 memset(head, 0, sizeof(*head));
172 head->capacity++;
173
174 head->hkey = strdup((char *)key);
175 head->hdata = strdup((char *)data);
176 head->tail = head;
177 g_htable->bucket[index] = head;
178 return TRUE;
179 }
180
181 int capacity = head->capacity;
182 struct hash_bucket *new_bucket =
183 (struct hash_bucket *)malloc(sizeof(struct hash_bucket));
184
185 if (!new_bucket) {
186 DEBUG("no memory for more hash_bucket
");
187 return FALSE;
188 }
189
190 if (capacity >= HASH_BUCKET_CAPACITY_MAX) {
191 struct hash_bucket *tail = head->tail;
192 head->tail = tail->prev;
193
194 tail->prev->next = NULL;
195 bucket_free(tail);
196 }
197
198 head->prev = new_bucket;
199 new_bucket->next = head;
200 new_bucket->capacity = capacity + 1;
201 new_bucket->tail = head->tail;
202 head->tail = NULL;
203
204 head->hkey = strdup((char *)key);
205 head->hdata = strdup((char *)data);
206
207 g_htable->bucket[index] = new_bucket;
208
209 return TRUE;
210 }
211
212 int hash_delete(void *key) {
213 if (!key) {
214 DEBUG("input para is NULL
");
215 return FALSE;
216 }
217
218 uint32_t index = g_htable->hash_key(key);
219 struct hash_bucket* head = g_htable->bucket[index];
220 struct hash_bucket* bkt = head;
221
222 while(bkt) {
223 if (0 == g_htable->hash_cmp(key, bkt->hkey, strlen((char*)key))) {
224 if (head != bkt && bkt != head->tail) {
225 bkt->prev->next = bkt->next;
226 bkt->next->prev = bkt->prev;
227
228 } else if (bkt == head->tail && head->capacity>1) {
229 bkt->prev->next = NULL;
230 bkt->tail = bkt->prev;
231
232 } else {
233 if (bkt->next) {
234 bkt->next->tail = bkt->tail;
235 bkt->next->capacity = bkt->capacity;
236 bkt->next->prev = NULL;
237 g_htable->bucket[index] = bkt->next;
238 } else {
239 g_htable->bucket[index] = NULL;
240 }
241 }
242
243 bucket_free(bkt);
244 if (g_htable->bucket[index]) {
245 g_htable->bucket[index]->capacity--;
246 }
247
248 return TRUE;
249 }
250 bkt = bkt->next;
251 }
252 return FALSE;
253 }
254
255 static void bucket_print(struct hash_bucket** ptr) {
256 struct hash_bucket *bkt = *ptr;
257 struct hash_bucket *tmp;
258
259 while(bkt) {
260 printf("key=[%s],data=[%s]
", (char*)bkt->hkey, (char*)bkt->hdata);
261 bkt = bkt->next;
262 }
263 }
264
265 void hash_iter_print() {
266 if (g_htable) {
267 for(int i=0; i<HASH_BUCKET_MAX; i++) {
268 if (g_htable->bucket[i]) {
269 bucket_print(&g_htable->bucket[i]);
270 }
271 }
272 }
273 }
274
275 int main(int argc, char* argv[]) {
276 hash_create();
277
278 hash_add("first", "danxi");
279 hash_add("second", "test");
280 hash_add("three", "sad code");
281 hash_add("four", "let's go");
282
283 hash_iter_print();
284
285 char * t1 = (char *)hash_lookup("first");
286 char * t2 = (char *)hash_lookup("second");
287
288 printf("%s %s
", t1, t2);
289 printf("%s
", (char*)hash_lookup("four"));
290
291 hash_delete("four");
292 hash_iter_print();
293 hash_destroy();
294
295 return 0;
296 }
