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
|
#include "ht.h"
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#define FNV_BASIS 0x811c9dc5
#define FNV_PRIME 0x01000193
// fnv-1a
static uint32_t hash(char *s) {
uint32_t h = FNV_BASIS;
for(;;) {
h ^= *s;
h *= FNV_PRIME;
if (*s == '\0') break;
s++;
}
return h;
}
Ht ht_new() {
Ht h;
h.len = 0;
for (int i = 0; i < HT_SIZE; i++) {
h.b[i] = (HtEntry){ .k = NULL, .v=0 };
}
return h;
}
void ht_put(Ht *h, char *k, int v) {
uint32_t hv = hash(k);
int start = hv%HT_SIZE;
for (int cur = start; cur != start - 1; cur = (cur+1)%HT_SIZE) {
HtEntry *ent = &h->b[cur];
if (ent->k == NULL) {
printf(" p %d\n",cur);
ent->k = strdup(k);
ent->v = v;
h->len++;
break;
} else if (0 == strcmp(k, ent->k)) {
printf(" r %d\n",cur);
ent->v = v;
break;
} else {
printf(" n %d\n",cur);
}
}
}
int ht_get(Ht *h, char *k, int *v) {
uint32_t hv = hash(k);
int start = hv%HT_SIZE;
for (int cur = start; cur != start - 1; cur = (cur+1)%HT_SIZE) {
HtEntry *ent = &h->b[cur];
if (ent->k == NULL) {
return 0; // not found
} else if (0 == strncmp(ent->k, k, 80)) {
*v = ent->v;
return 1;
}
}
return 0; // exhausted
}
void ht_dump(Ht *h) {
printf("#%d:\n",h->len);
for (int i = 0; i < HT_SIZE; i++) {
HtEntry ent = h->b[i];
if (ent.k != NULL) {
printf(" %s:%d\n",ent.k,ent.v);
}
}
}
|
