1 #ifndef MPU_KEYVAL_H
2 #define MPU_KEYVAL_H
3
4 #include "ptypes.h"
5
6 typedef struct {
7 UV key;
8 UV val;
9 } keyval_t;
10
11 typedef struct {
12 keyval_t *keyval;
13 UV mask;
14 long maxsize;
15 long size;
16 } set_t;
17
18
19
20
21 #if BITS_PER_WORD == 32
_hash(UV x)22 static UV _hash(UV x) {
23 x = ((x >> 16) ^ x) * 0x45d9f3b;
24 x = ((x >> 16) ^ x) * 0x45d9f3b;
25 x = (x >> 16) ^ x;
26 return x;
27 }
28 #else
_hash(UV x)29 static UV _hash(UV x) {
30 x = (x ^ (x >> 30)) * UVCONST(0xbf58476d1ce4e5b9);
31 x = (x ^ (x >> 27)) * UVCONST(0x94d049bb133111eb);
32 x = x ^ (x >> 31);
33 return x;
34 }
35 #endif
36
37
38 /******************************************************************************/
39
init_set(set_t * S,UV isize)40 static void init_set(set_t *S, UV isize) {
41 int bits = 0;
42 while (isize > 0) {
43 bits++;
44 isize >>= 1;
45 }
46 S->size = 0;
47 S->maxsize = UVCONST(1) << ((bits < 3) ? 3 : bits);
48 S->mask = S->maxsize - 1;
49 Newz(0,S->keyval,S->maxsize,keyval_t);
50 }
51
free_set(set_t * S)52 static void free_set(set_t *S) {
53 S->size = S->maxsize = 0;
54 Safefree(S->keyval);
55 }
56
_set_expand(set_t * S)57 static void _set_expand(set_t *S) {
58 long i, max = S->maxsize, newmax = max*2, newsize = 0, newmask = newmax-1;
59 keyval_t *nkv;
60 Newz(0, nkv, newmax, keyval_t);
61 for (i = 0; i < max; i++) {
62 UV key = S->keyval[i].key;
63 if (key != 0) {
64 UV h = _hash(key) & newmask;
65 while (nkv[h].key > 0 && nkv[h].key != key)
66 h = (h+1) & newmask;
67 nkv[h] = S->keyval[i];
68 newsize++;
69 }
70 }
71 Safefree(S->keyval);
72 S->keyval = nkv;
73 S->maxsize = newmax;
74 S->mask = newmax-1;
75 MPUassert(newsize == S->size, "keyval set size mismatch");
76 }
77
set_search(set_t S,UV key)78 static long set_search(set_t S, UV key) {
79 long h = _hash(key) & S.mask;
80 while (S.keyval[h].key > 0 && S.keyval[h].key != key)
81 h = (h+1) & S.mask; /* Linear probe */
82 return (S.keyval[h].key == key) ? h : -1;
83 }
84
set_getval(set_t S,UV key)85 static UV set_getval(set_t S, UV key) {
86 long i = set_search(S, key);
87 return (i == -1) ? 0 : S.keyval[i].val;
88 }
89
set_addsum(set_t * S,keyval_t kv)90 static void set_addsum(set_t *S, keyval_t kv) {
91 UV h = _hash(kv.key) & S->mask;
92 while (S->keyval[h].key > 0 && S->keyval[h].key != kv.key)
93 h = (h+1) & S->mask;
94 if (S->keyval[h].key == kv.key) {
95 /* if (kv.val > UV_MAX - S->keyval[h].val) croak("add overflow\n"); */
96 S->keyval[h].val += kv.val;
97 } else {
98 S->keyval[h] = kv;
99 if (S->size++ > 0.65 * S->maxsize)
100 _set_expand(S);
101 }
102 }
103
set_merge(set_t * S,set_t T)104 static void set_merge(set_t *S, set_t T) {
105 long j;
106 for (j = 0; j < T.maxsize; j++)
107 if (T.keyval[j].key > 0)
108 set_addsum(S, T.keyval[j]);
109 }
110
111 /******************************************************************************/
112
113 typedef struct {
114 UV key;
115 UV *vals;
116 long size;
117 long maxsize;
118 } keylist_t;
119
120 typedef struct {
121 keylist_t *keylist;
122 UV mask;
123 long maxsize;
124 long size;
125 } set_list_t;
126
init_setlist(set_list_t * L,UV isize)127 static void init_setlist(set_list_t *L, UV isize) {
128 int bits = 0;
129 while (isize > 0) {
130 bits++;
131 isize >>= 1;
132 }
133 L->size = 0;
134 L->maxsize = UVCONST(1) << ((bits < 3) ? 3 : bits);
135 L->mask = L->maxsize - 1;
136 Newz(0, L->keylist, L->maxsize, keylist_t);
137 }
138
free_setlist(set_list_t * L)139 static void free_setlist(set_list_t *L) {
140 long i;
141 L->size = L->maxsize = 0;
142 for (i = 0; i < L->maxsize; i++)
143 if (L->keylist[i].size > 0)
144 Safefree(L->keylist[i].vals);
145 Safefree(L->keylist);
146 }
147
_setlist_expand(set_list_t * L)148 static void _setlist_expand(set_list_t *L) {
149 long i, max = L->maxsize, newmax = max*2, newsize = 0, newmask = newmax-1;
150 keylist_t *nlist;
151 Newz(0, nlist, newmax, keylist_t);
152 for (i = 0; i < max; i++) {
153 UV key = L->keylist[i].key;
154 if (key != 0) {
155 UV h = _hash(key) & newmask;
156 while (nlist[h].key > 0 && nlist[h].key != key)
157 h = (h+1) & newmask;
158 nlist[h] = L->keylist[i];
159 newsize++;
160 }
161 }
162 Safefree(L->keylist);
163 L->keylist = nlist;
164 L->maxsize = newmax;
165 L->mask = newmax-1;
166 MPUassert(newsize == L->size, "setlist size mismatch");
167 }
168
setlist_search(set_list_t L,UV key)169 static long setlist_search(set_list_t L, UV key) {
170 long h = _hash(key) & L.mask;
171 while (L.keylist[h].key > 0 && L.keylist[h].key != key)
172 h = (h+1) & L.mask; /* Linear probe */
173 return (L.keylist[h].key == key) ? h : -1;
174 }
175
setlist_addlist(set_list_t * L,UV key,long nvals,UV * list,UV mult)176 static void setlist_addlist(set_list_t *L, UV key, long nvals, UV* list, UV mult) {
177 UV *vptr;
178 long j, h = _hash(key) & L->mask;
179 while (L->keylist[h].key > 0 && L->keylist[h].key != key)
180 h = (h+1) & L->mask;
181 if (L->keylist[h].key == key) {
182 long size = L->keylist[h].size;
183 long maxsize = L->keylist[h].maxsize;
184 if (size + nvals > maxsize) {
185 maxsize = 2 * (size+nvals);
186 Renew(L->keylist[h].vals, maxsize, UV);
187 L->keylist[h].maxsize = maxsize;
188 }
189 vptr = L->keylist[h].vals + size;
190 for (j = 0; j < nvals; j++)
191 vptr[j] = list[j] * mult;
192 L->keylist[h].size = size + nvals;
193 } else {
194 long maxsize = (nvals < 5) ? 12 : (nvals+1) * 2;
195 New(0, L->keylist[h].vals, maxsize, UV);
196 L->keylist[h].maxsize = maxsize;
197 vptr = L->keylist[h].vals;
198 for (j = 0; j < nvals; j++)
199 vptr[j] = list[j] * mult;
200 L->keylist[h].size = nvals;
201 L->keylist[h].key = key;
202 if (L->size++ > 0.65 * L->maxsize)
203 _setlist_expand(L);
204 }
205 }
206
setlist_addval(set_list_t * L,UV key,UV val)207 static void setlist_addval(set_list_t *L, UV key, UV val) {
208 setlist_addlist(L, key, 1, &val, 1);
209 }
210
setlist_getlist(UV * nvals,set_list_t L,UV key)211 static UV* setlist_getlist(UV *nvals, set_list_t L, UV key) {
212 long i = setlist_search(L, key);
213 if (i == -1) {
214 *nvals = 0;
215 return 0;
216 }
217 *nvals = L.keylist[i].size;
218 return L.keylist[i].vals;
219 }
220
setlist_merge(set_list_t * L,set_list_t T)221 static void setlist_merge(set_list_t *L, set_list_t T) {
222 long j;
223 for (j = 0; j < T.maxsize; j++) {
224 if (T.keylist[j].key > 0) {
225 UV key = T.keylist[j].key;
226 UV nvals = T.keylist[j].size;
227 UV *vals = T.keylist[j].vals;
228 setlist_addlist(L, key, nvals, vals, 1);
229 }
230 }
231 }
232
233 #endif
234