1 /* Written by Kris Maglione */
2 /* Public domain */
3 #include "dat.h"
4 #include <stdlib.h>
5 #include <string.h>
6 #include "fns.h"
7
8 /* Edit s/^([a-zA-Z].*)\n([a-z].*) {/\1 \2;/g x/^([^a-zA-Z]|static|$)/-+d s/ (\*map|val|*str)//g */
9
10 MapEnt *NM;
11
12 /* By Dan Bernstein. Public domain. */
13 static ulong
hash(const char * str)14 hash(const char *str) {
15 ulong h;
16
17 h = 5381;
18 while (*str != '\0') {
19 h += h << 5; /* h *= 33 */
20 h ^= *str++;
21 }
22 return h;
23 }
24
25 static void
insert(MapEnt ** e,ulong val,char * key)26 insert(MapEnt **e, ulong val, char *key) {
27 MapEnt *te;
28
29 te = emallocz(sizeof *te);
30 te->hash = val;
31 te->key = key;
32 te->next = *e;
33 *e = te;
34 }
35
36 static MapEnt**
mapgetp(Map * map,ulong val,int create)37 mapgetp(Map *map, ulong val, int create) {
38 MapEnt **e;
39
40 e = &map->bucket[val%map->nhash];
41 for(; *e; e = &(*e)->next)
42 if((*e)->hash >= val) break;
43 if(*e == nil || (*e)->hash != val) {
44 if(create)
45 insert(e, val, nil);
46 else
47 e = &NM;
48 }
49 return e;
50 }
51
52 static MapEnt**
hashgetp(Map * map,char * str,int create)53 hashgetp(Map *map, char *str, int create) {
54 MapEnt **e;
55 ulong h;
56 int cmp;
57
58 h = hash(str);
59 e = mapgetp(map, h, create);
60 if(*e && (*e)->key == nil)
61 (*e)->key = str;
62 else {
63 SET(cmp);
64 for(; *e; e = &(*e)->next)
65 if((*e)->hash > h || (cmp = strcmp((*e)->key, str)) >= 0)
66 break;
67 if(*e == nil || (*e)->hash > h || cmp > 0)
68 if(create)
69 insert(e, h, str);
70 }
71 return e;
72 }
73
74 MapEnt*
mapget(Map * map,ulong val,int create)75 mapget(Map *map, ulong val, int create) {
76 MapEnt **e;
77
78 e = mapgetp(map, val, create);
79 return *e;
80 }
81
82 MapEnt*
hashget(Map * map,char * str,int create)83 hashget(Map *map, char *str, int create) {
84 MapEnt **e;
85
86 e = hashgetp(map, str, create);
87 return *e;
88 }
89
90 void*
maprm(Map * map,ulong val)91 maprm(Map *map, ulong val) {
92 MapEnt **e, *te;
93 void *ret;
94
95 ret = nil;
96 e = mapgetp(map, val, 0);
97 if(*e) {
98 te = *e;
99 ret = te->val;
100 *e = te->next;
101 free(te);
102 }
103 return ret;
104 }
105
106 void*
hashrm(Map * map,char * str)107 hashrm(Map *map, char *str) {
108 MapEnt **e, *te;
109 void *ret;
110
111 ret = nil;
112 e = hashgetp(map, str, 0);
113 if(*e) {
114 te = *e;
115 ret = te->val;
116 *e = te->next;
117 free(te);
118 }
119 return ret;
120 }
121