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
|
/* Written by Kris Maglione */
/* Public domain */
#include "dat.h"
#include "fns.h"
/* Edit s/^([a-zA-Z].*)\n([a-z].*) {/\1 \2;/g x/^([^a-zA-Z]|static|$)/-+d s/ (\*map|val|*str)//g */
struct MapEnt {
ulong hash;
const char* key;
void* val;
MapEnt* next;
};
MapEnt *NM;
/* By Dan Bernstein. Public domain. */
static ulong
hash(const char *str) {
ulong h;
h = 5381;
while (*str != '\0') {
h += h << 5; /* h *= 33 */
h ^= *str++;
}
return h;
}
static void
insert(MapEnt **e, ulong val, const char *key) {
MapEnt *te;
te = emallocz(sizeof *te);
te->hash = val;
te->key = key;
te->next = *e;
*e = te;
}
static MapEnt**
map_getp(Map *map, ulong val, int create) {
MapEnt **e;
e = &map->bucket[val%map->nhash];
for(; *e; e = &(*e)->next)
if((*e)->hash >= val) break;
if(*e == nil || (*e)->hash != val) {
if(create)
insert(e, val, nil);
else
e = &NM;
}
return e;
}
static MapEnt**
hash_getp(Map *map, const char *str, int create) {
MapEnt **e;
ulong h;
int cmp;
h = hash(str);
e = map_getp(map, h, create);
if(*e && (*e)->key == nil)
(*e)->key = str;
else {
SET(cmp);
for(; *e; e = &(*e)->next)
if((*e)->hash > h || (cmp = strcmp((*e)->key, str)) >= 0)
break;
if(*e == nil || (*e)->hash > h || cmp > 0)
if(create)
insert(e, h, str);
}
return e;
}
void**
map_get(Map *map, ulong val, bool create) {
MapEnt *e;
e = *map_getp(map, val, create);
return e ? &e->val : nil;
}
void**
hash_get(Map *map, const char *str, bool create) {
MapEnt *e;
e = *hash_getp(map, str, create);
return e ? &e->val : nil;
}
void*
map_rm(Map *map, ulong val) {
MapEnt **e, *te;
void *ret;
ret = nil;
e = map_getp(map, val, 0);
if(*e) {
te = *e;
ret = te->val;
*e = te->next;
free(te);
}
return ret;
}
void*
hash_rm(Map *map, const char *str) {
MapEnt **e, *te;
void *ret;
ret = nil;
e = hash_getp(map, str, 0);
if(*e) {
te = *e;
ret = te->val;
*e = te->next;
free(te);
}
return ret;
}
|
