1 /* g/h.c
2 **
3 */
4 #include "all.h"
5
6 static void
7 _ch_slot_put(u3h_slot* sot_w, u3_noun kev, c3_w lef_w, c3_w rem_w, c3_w* use_w);
8
9 static c3_o
10 _ch_trim_slot(u3h_root* har_u, u3h_slot *sot_w, c3_w lef_w, c3_w rem_w);
11
12 c3_w
13 _ch_skip_slot(c3_w mug_w, c3_w lef_w);
14
15 /* u3h_new_cache(): create hashtable with bounded size.
16 */
17 u3p(u3h_root)
u3h_new_cache(c3_w max_w)18 u3h_new_cache(c3_w max_w)
19 {
20 u3h_root* har_u = u3a_walloc(c3_wiseof(u3h_root));
21 u3p(u3h_root) har_p = u3of(u3h_root, har_u);
22 c3_w i_w;
23
24 har_u->max_w = max_w;
25 har_u->use_w = 0;
26 har_u->arm_u.mug_w = 0;
27 har_u->arm_u.inx_w = 0;
28 har_u->arm_u.buc_o = c3n;
29
30 for ( i_w = 0; i_w < 64; i_w++ ) {
31 har_u->sot_w[i_w] = 0;
32 }
33 return har_p;
34 }
35
36 /* u3h_new(): create hashtable.
37 */
38 u3p(u3h_root)
u3h_new(void)39 u3h_new(void)
40 {
41 return u3h_new_cache(0);
42 }
43
44 /* _ch_popcount(): number of bits set in word. A standard intrinsic.
45 */
46 static c3_w
_ch_popcount(c3_w num_w)47 _ch_popcount(c3_w num_w)
48 {
49 return __builtin_popcount(num_w);
50 }
51
52 /* _ch_buck_new(): create new, empty bucket.
53 */
54 static u3h_buck*
_ch_buck_new(void)55 _ch_buck_new(void)
56 {
57 u3h_buck* hab_u = u3a_walloc(c3_wiseof(u3h_buck));
58
59 hab_u->len_w = 0;
60 return hab_u;
61 }
62
63 /* _ch_node_new(): create new, empty node.
64 */
65 static u3h_node*
_ch_node_new(void)66 _ch_node_new(void)
67 {
68 u3h_node* han_u = u3a_walloc(c3_wiseof(u3h_node));
69
70 han_u->map_w = 0;
71 return han_u;
72 }
73
74 /* _ch_some_new(): create node or bucket.
75 */
76 static void*
_ch_some_new(c3_w lef_w)77 _ch_some_new(c3_w lef_w)
78 {
79 if ( 0 == lef_w ) {
80 return _ch_buck_new();
81 }
82 else {
83 return _ch_node_new();
84 }
85 }
86
87 /* _ch_node_add(): add to node.
88 */
89 static u3h_node*
_ch_node_add(u3h_node * han_u,c3_w lef_w,c3_w rem_w,u3_noun kev,c3_w * use_w)90 _ch_node_add(u3h_node* han_u, c3_w lef_w, c3_w rem_w, u3_noun kev, c3_w *use_w)
91 {
92 c3_w bit_w, inx_w, map_w, i_w;
93
94 lef_w -= 5;
95 bit_w = (rem_w >> lef_w);
96 rem_w = (rem_w & ((1 << lef_w) - 1));
97 map_w = han_u->map_w;
98 inx_w = _ch_popcount(map_w & ((1 << bit_w) - 1));
99
100 if ( map_w & (1 << bit_w) ) {
101 _ch_slot_put(&(han_u->sot_w[inx_w]), kev, lef_w, rem_w, use_w);
102 return han_u;
103 }
104 else {
105 // nothing was at this slot.
106 // Optimize: use u3a_wealloc.
107 //
108 c3_w len_w = _ch_popcount(map_w);
109 u3h_node* nah_u = u3a_walloc(c3_wiseof(u3h_node) +
110 ((len_w + 1) * c3_wiseof(u3h_slot)));
111 nah_u->map_w = han_u->map_w | (1 << bit_w);
112
113 for ( i_w = 0; i_w < inx_w; i_w++ ) {
114 nah_u->sot_w[i_w] = han_u->sot_w[i_w];
115 }
116 nah_u->sot_w[inx_w] = u3h_noun_be_warm(u3h_noun_to_slot(kev));
117 for ( i_w = inx_w; i_w < len_w; i_w++ ) {
118 nah_u->sot_w[i_w + 1] = han_u->sot_w[i_w];
119 }
120
121 u3a_wfree(han_u);
122 *use_w += 1;
123 return nah_u;
124 }
125 }
126
127 /* ch_buck_add(): add to bucket.
128 */
129 static u3h_buck*
_ch_buck_add(u3h_buck * hab_u,u3_noun kev,c3_w * use_w)130 _ch_buck_add(u3h_buck* hab_u, u3_noun kev, c3_w *use_w)
131 {
132 c3_w i_w;
133
134 // if our key is equal to any of the existing keys in the bucket,
135 // then replace that key-value pair with kev.
136 //
137 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
138 u3_noun kov = u3h_slot_to_noun(hab_u->sot_w[i_w]);
139 if ( c3y == u3r_sing(u3h(kev), u3h(kov)) ) {
140 u3a_lose(kov);
141 hab_u->sot_w[i_w] = u3h_noun_to_slot(kev);
142
143 return hab_u;
144 }
145 }
146
147 // create mutant bucket with added key-value pair.
148 {
149 c3_w len_w = hab_u->len_w;
150 u3h_buck* bah_u = u3a_walloc(c3_wiseof(u3h_buck) +
151 (len_w + 1) * c3_wiseof(u3h_slot));
152
153 bah_u->len_w = len_w + 1;
154 bah_u->sot_w[0] = u3h_noun_to_slot(kev);
155
156 // Optimize: use u3a_wealloc().
157 //
158 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
159 bah_u->sot_w[i_w + 1] = hab_u->sot_w[i_w];
160 }
161
162 u3a_wfree(hab_u);
163 *use_w += 1;
164 return bah_u;
165 }
166 }
167
168 /* _ch_some_add(): add to node or bucket.
169 */
170 static void*
_ch_some_add(void * han_v,c3_w lef_w,c3_w rem_w,u3_noun kev,c3_w * use_w)171 _ch_some_add(void* han_v, c3_w lef_w, c3_w rem_w, u3_noun kev, c3_w *use_w)
172 {
173 if ( 0 == lef_w ) {
174 return _ch_buck_add((u3h_buck*)han_v, kev, use_w);
175 }
176 else return _ch_node_add((u3h_node*)han_v, lef_w, rem_w, kev, use_w);
177 }
178
179 /* _ch_slot_put(): store a key-value pair in a u3h_slot (root or node)
180 */
181 static void
_ch_slot_put(u3h_slot * sot_w,u3_noun kev,c3_w lef_w,c3_w rem_w,c3_w * use_w)182 _ch_slot_put(u3h_slot* sot_w, u3_noun kev, c3_w lef_w, c3_w rem_w, c3_w* use_w)
183 {
184 if ( c3y == u3h_slot_is_null(*sot_w) ) {
185 *sot_w = u3h_noun_be_warm(u3h_noun_to_slot(kev));
186 *use_w += 1;
187 }
188 else if ( c3y == u3h_slot_is_noun(*sot_w) ) {
189 u3_noun kov = u3h_slot_to_noun(*sot_w);
190 if ( c3y == u3r_sing(u3h(kev), u3h(kov)) ) {
191 *sot_w = u3h_noun_be_warm(u3h_noun_to_slot(kev));
192 u3z(kov);
193 }
194 else {
195 c3_w rom_w = u3r_mug(u3h(kov)) & ((1 << lef_w) - 1);
196 void* hav_v = _ch_some_new(lef_w);
197
198 *use_w -= 1; // take one out, add two
199 hav_v = _ch_some_add(hav_v, lef_w, rom_w, kov, use_w);
200 hav_v = _ch_some_add(hav_v, lef_w, rem_w, kev, use_w);
201 *sot_w = u3h_node_to_slot(hav_v);
202 }
203 }
204 else {
205 void* hav_v = _ch_some_add(u3h_slot_to_node(*sot_w),
206 lef_w,
207 rem_w,
208 kev,
209 use_w);
210
211 c3_assert( c3y == u3h_slot_is_node(*sot_w) );
212 *sot_w = u3h_node_to_slot(hav_v);
213 }
214 }
215
216 /* _ch_trim_node(): trim one entry from a node slot or its children
217 */
218 static c3_o
_ch_trim_node(u3h_root * har_u,u3h_slot * sot_w,c3_w lef_w,c3_w rem_w)219 _ch_trim_node(u3h_root* har_u, u3h_slot* sot_w, c3_w lef_w, c3_w rem_w)
220 {
221 c3_w bit_w, map_w, inx_w;
222 u3h_slot* tos_w;
223 u3h_node* han_u = (u3h_node*) u3h_slot_to_node(*sot_w);
224
225 lef_w -= 5;
226 bit_w = (rem_w >> lef_w);
227 map_w = han_u->map_w;
228
229 if ( 0 == (map_w & (1 << bit_w)) ) {
230 har_u->arm_u.mug_w = _ch_skip_slot(har_u->arm_u.mug_w, lef_w);
231 return c3n;
232 }
233
234 rem_w = (rem_w & ((1 << lef_w) - 1));
235 inx_w = _ch_popcount(map_w & ((1 << bit_w) - 1));
236 tos_w = &(han_u->sot_w[inx_w]);
237
238 if ( c3n == _ch_trim_slot(har_u, tos_w, lef_w, rem_w) ) {
239 // nothing trimmed
240 return c3n;
241 }
242 else if ( 0 != *tos_w ) {
243 // something trimmed, but slot still has value
244 return c3y;
245 }
246 else {
247 // shrink!
248 c3_w i_w, len_w = _ch_popcount(map_w);
249
250 if ( 2 == len_w ) {
251 // only one left, pick the other
252 *sot_w = han_u->sot_w[ 0 == inx_w ? 1 : 0 ];
253
254 u3a_wfree(han_u);
255 }
256 else {
257 // shrink node in place; don't reallocate, we could be low on memory
258 //
259 han_u->map_w = han_u->map_w & ~(1 << bit_w);
260
261 for ( i_w = inx_w; i_w < (len_w - 1); i_w++ ) {
262 han_u->sot_w[i_w] = han_u->sot_w[i_w + 1];
263 }
264 }
265 return c3y;
266 }
267 }
268
269 /* _ch_trim_node(): trim one entry from a bucket slot
270 */
271 static c3_o
_ch_trim_buck(u3h_root * har_u,u3h_slot * sot_w)272 _ch_trim_buck(u3h_root* har_u, u3h_slot* sot_w)
273 {
274 c3_w i_w, len_w;
275 u3h_buck* hab_u = u3h_slot_to_node(*sot_w);
276
277 for ( har_u->arm_u.buc_o = c3y, len_w = hab_u->len_w;
278 har_u->arm_u.inx_w < len_w;
279 har_u->arm_u.inx_w += 1 )
280 {
281 u3h_slot* tos_w = &(hab_u->sot_w[har_u->arm_u.inx_w]);
282 if ( c3y == _ch_trim_slot(har_u, tos_w, 0, 0) ) {
283 if ( 2 == len_w ) {
284 // 2 things in bucket: debucketize to key-value pair, the next
285 // run will point at this pair (same mug_w, no longer in bucket)
286 *sot_w = hab_u->sot_w[ (0 == har_u->arm_u.inx_w) ? 1 : 0 ];
287 u3a_wfree(hab_u);
288 har_u->arm_u.inx_w = 0;
289 har_u->arm_u.buc_o = c3n;
290 }
291 else {
292 // shrink bucket in place; don't reallocate, we could be low on memory
293 //
294 hab_u->len_w = len_w - 1;
295
296 for ( i_w = har_u->arm_u.inx_w; i_w < (len_w - 1); ++i_w ) {
297 hab_u->sot_w[i_w] = hab_u->sot_w[i_w + 1];
298 }
299 }
300 return c3y;
301 }
302 }
303
304 har_u->arm_u.mug_w = (har_u->arm_u.mug_w + 1) & 0x7FFFFFFF; // modulo 2^31
305 har_u->arm_u.inx_w = 0;
306 har_u->arm_u.buc_o = c3n;
307 return c3n;
308 }
309
310 /* _ch_trim_some(): trim one entry from a bucket or node slot
311 */
312 static c3_o
_ch_trim_some(u3h_root * har_u,u3h_slot * sot_w,c3_w lef_w,c3_w rem_w)313 _ch_trim_some(u3h_root* har_u, u3h_slot* sot_w, c3_w lef_w, c3_w rem_w)
314 {
315 if ( 0 == lef_w ) {
316 return _ch_trim_buck(har_u, sot_w);
317 }
318 else {
319 return _ch_trim_node(har_u, sot_w, lef_w, rem_w);
320 }
321 }
322
323 /* _ch_skip_slot(): increment arm over hash prefix.
324 */
325 c3_w
_ch_skip_slot(c3_w mug_w,c3_w lef_w)326 _ch_skip_slot(c3_w mug_w, c3_w lef_w)
327 {
328 c3_w hig_w = mug_w >> lef_w;
329 c3_w new_w = (hig_w + 1) & ((1 << (31 - lef_w)) - 1); // modulo 2^(31 - lef_w)
330 return new_w << lef_w;
331 }
332
333 /* _ch_trim_slot(): trim one entry from a slot
334 */
335 static c3_o
_ch_trim_slot(u3h_root * har_u,u3h_slot * sot_w,c3_w lef_w,c3_w rem_w)336 _ch_trim_slot(u3h_root* har_u, u3h_slot *sot_w, c3_w lef_w, c3_w rem_w)
337 {
338 if ( _(u3h_slot_is_null(*sot_w)) ) {
339 har_u->arm_u.mug_w = _ch_skip_slot(har_u->arm_u.mug_w, lef_w);
340 return c3n;
341 }
342 else if ( _(u3h_slot_is_node(*sot_w)) ) {
343 return _ch_trim_some(har_u, sot_w, lef_w, rem_w);
344 }
345 else if ( _(u3h_slot_is_warm(*sot_w)) ) {
346 *sot_w = u3h_noun_be_cold(*sot_w);
347 if ( c3n == har_u->arm_u.buc_o ) {
348 har_u->arm_u.mug_w = (har_u->arm_u.mug_w + 1) & 0x7FFFFFFF; // modulo 2^31
349 }
350 return c3n;
351 }
352 else {
353 u3_noun kev = u3h_slot_to_noun(*sot_w);
354 *sot_w = 0;
355 // uL(fprintf(uH, "trim: freeing %x, use count %d\r\n", kev, u3a_use(kev)));
356 u3z(kev);
357
358 har_u->arm_u.mug_w = _ch_skip_slot(har_u->arm_u.mug_w, lef_w);
359 return c3y;
360 }
361 }
362
363 /* _ch_trim_slot(): trim one entry from a hashtable
364 */
365 static c3_o
_ch_trim_root(u3h_root * har_u)366 _ch_trim_root(u3h_root* har_u)
367 {
368 c3_w mug_w = har_u->arm_u.mug_w;
369 c3_w inx_w = mug_w >> 25; // 6 bits
370 c3_w rem_w = mug_w & ((1 << 25) - 1);
371 u3h_slot* sot_w = &(har_u->sot_w[inx_w]);
372
373 return _ch_trim_slot(har_u, sot_w, 25, rem_w);
374 }
375
376 /* u3h_trim_to(): trim to n key-value pairs
377 */
378 void
u3h_trim_to(u3p (u3h_root)har_p,c3_w n_w)379 u3h_trim_to(u3p(u3h_root) har_p, c3_w n_w)
380 {
381 u3h_root* har_u = u3to(u3h_root, har_p);
382
383 while ( har_u->use_w > n_w ) {
384 if ( c3y == _ch_trim_root(har_u) ) {
385 har_u->use_w -= 1;
386 }
387 /* TODO: remove
388 if ( c3n == har_u->arm_u.buc_o ) {
389 // lower 31 bits of increment (next mug)
390 har_u->arm_u.mug_w = (har_u->arm_u.mug_w + 1) & 0x7FFFFFFF;
391 har_u->arm_u.inx_w = 0;
392 }
393 */
394 }
395 }
396
397 /* u3h_put(): insert in hashtable.
398 **
399 ** `key` is RETAINED; `val` is transferred.
400 */
401 void
u3h_put(u3p (u3h_root)har_p,u3_noun key,u3_noun val)402 u3h_put(u3p(u3h_root) har_p, u3_noun key, u3_noun val)
403 {
404 u3h_root* har_u = u3to(u3h_root, har_p);
405 u3_noun kev = u3nc(u3k(key), val);
406 c3_w mug_w = u3r_mug(key);
407 c3_w inx_w = (mug_w >> 25); // 6 bits
408 c3_w rem_w = (mug_w & ((1 << 25) - 1));
409
410 _ch_slot_put(&(har_u->sot_w[inx_w]), kev, 25, rem_w, &(har_u->use_w));
411 if ( har_u->max_w > 0 ) {
412 u3h_trim_to(har_p, har_u->max_w);
413 }
414 }
415
416 /* _ch_buck_hum(): read in bucket.
417 */
418 static c3_o
_ch_buck_hum(u3h_buck * hab_u,c3_w mug_w)419 _ch_buck_hum(u3h_buck* hab_u, c3_w mug_w)
420 {
421 c3_w i_w;
422
423 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
424 if ( mug_w == u3r_mug(u3h(u3h_slot_to_noun(hab_u->sot_w[i_w]))) ) {
425 return c3y;
426 }
427 }
428 return c3n;
429 }
430
431 /* _ch_node_hum(): read in node.
432 */
433 static c3_o
_ch_node_hum(u3h_node * han_u,c3_w lef_w,c3_w rem_w,c3_w mug_w)434 _ch_node_hum(u3h_node* han_u, c3_w lef_w, c3_w rem_w, c3_w mug_w)
435 {
436 c3_w bit_w, map_w;
437
438 lef_w -= 5;
439 bit_w = (rem_w >> lef_w);
440 rem_w = (rem_w & ((1 << lef_w) - 1));
441 map_w = han_u->map_w;
442
443 if ( !(map_w & (1 << bit_w)) ) {
444 return c3n;
445 }
446 else {
447 c3_w inx_w = _ch_popcount(map_w & ((1 << bit_w) - 1));
448 c3_w sot_w = han_u->sot_w[inx_w];
449
450 if ( _(u3h_slot_is_noun(sot_w)) ) {
451 u3_noun kev = u3h_slot_to_noun(sot_w);
452
453 if ( mug_w == u3r_mug(u3h(kev)) ) {
454 return c3y;
455 }
456 else {
457 return c3n;
458 }
459 }
460 else {
461 void* hav_v = u3h_slot_to_node(sot_w);
462
463 if ( 0 == lef_w ) {
464 return _ch_buck_hum(hav_v, mug_w);
465 }
466 else return _ch_node_hum(hav_v, lef_w, rem_w, mug_w);
467 }
468 }
469 }
470
471 /* u3h_hum(): check presence in hashtable.
472 **
473 ** `key` is RETAINED.
474 */
475 c3_o
u3h_hum(u3p (u3h_root)har_p,c3_w mug_w)476 u3h_hum(u3p(u3h_root) har_p, c3_w mug_w)
477 {
478 u3h_root* har_u = u3to(u3h_root, har_p);
479 c3_w inx_w = (mug_w >> 25);
480 c3_w rem_w = (mug_w & ((1 << 25) - 1));
481 c3_w sot_w = har_u->sot_w[inx_w];
482
483 if ( _(u3h_slot_is_null(sot_w)) ) {
484 return c3n;
485 }
486 else if ( _(u3h_slot_is_noun(sot_w)) ) {
487 u3_noun kev = u3h_slot_to_noun(sot_w);
488
489 if ( mug_w == u3r_mug(u3h(kev)) ) {
490 return c3y;
491 }
492 else {
493 return c3n;
494 }
495 }
496 else {
497 u3h_node* han_u = u3h_slot_to_node(sot_w);
498
499 return _ch_node_hum(han_u, 25, rem_w, mug_w);
500 }
501 }
502
503 /* _ch_buck_git(): read in bucket.
504 */
505 static u3_weak
_ch_buck_git(u3h_buck * hab_u,u3_noun key)506 _ch_buck_git(u3h_buck* hab_u, u3_noun key)
507 {
508 c3_w i_w;
509
510 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
511 u3_noun kev = u3h_slot_to_noun(hab_u->sot_w[i_w]);
512 if ( _(u3r_sing(key, u3h(kev))) ) {
513 return u3t(kev);
514 }
515 }
516 return u3_none;
517 }
518
519 /* _ch_node_git(): read in node.
520 */
521 static u3_weak
_ch_node_git(u3h_node * han_u,c3_w lef_w,c3_w rem_w,u3_noun key)522 _ch_node_git(u3h_node* han_u, c3_w lef_w, c3_w rem_w, u3_noun key)
523 {
524 c3_w bit_w, map_w;
525
526 lef_w -= 5;
527 bit_w = (rem_w >> lef_w);
528 rem_w = (rem_w & ((1 << lef_w) - 1));
529 map_w = han_u->map_w;
530
531 if ( !(map_w & (1 << bit_w)) ) {
532 return u3_none;
533 }
534 else {
535 c3_w inx_w = _ch_popcount(map_w & ((1 << bit_w) - 1));
536 c3_w sot_w = han_u->sot_w[inx_w];
537
538 if ( _(u3h_slot_is_noun(sot_w)) ) {
539 u3_noun kev = u3h_slot_to_noun(sot_w);
540
541 if ( _(u3r_sing(key, u3h(kev))) ) {
542 return u3t(kev);
543 }
544 else {
545 return u3_none;
546 }
547 }
548 else {
549 void* hav_v = u3h_slot_to_node(sot_w);
550
551 if ( 0 == lef_w ) {
552 return _ch_buck_git(hav_v, key);
553 }
554 else return _ch_node_git(hav_v, lef_w, rem_w, key);
555 }
556 }
557 }
558
559 /* u3h_git(): read from hashtable.
560 **
561 ** `key` is RETAINED; result is RETAINED.
562 */
563 u3_weak
u3h_git(u3p (u3h_root)har_p,u3_noun key)564 u3h_git(u3p(u3h_root) har_p, u3_noun key)
565 {
566 u3h_root* har_u = u3to(u3h_root, har_p);
567 c3_w mug_w = u3r_mug(key);
568 c3_w inx_w = (mug_w >> 25);
569 c3_w rem_w = (mug_w & ((1 << 25) - 1));
570 c3_w sot_w = har_u->sot_w[inx_w];
571
572 if ( _(u3h_slot_is_null(sot_w)) ) {
573 return u3_none;
574 }
575 else if ( _(u3h_slot_is_noun(sot_w)) ) {
576 u3_noun kev = u3h_slot_to_noun(sot_w);
577
578 if ( _(u3r_sing(key, u3h(kev))) ) {
579 har_u->sot_w[inx_w] = u3h_noun_be_warm(sot_w);
580 return u3t(kev);
581 }
582 else {
583 return u3_none;
584 }
585 }
586 else {
587 u3h_node* han_u = u3h_slot_to_node(sot_w);
588
589 return _ch_node_git(han_u, 25, rem_w, key);
590 }
591 }
592
593 /* u3h_get(): read from hashtable, incrementing refcount.
594 **
595 ** `key` is RETAINED; result is PRODUCED.
596 */
597 u3_weak
u3h_get(u3p (u3h_root)har_p,u3_noun key)598 u3h_get(u3p(u3h_root) har_p, u3_noun key)
599 {
600 u3_noun pro = u3h_git(har_p, key);
601
602 if ( u3_none != pro ) {
603 u3a_gain(pro);
604 }
605 return pro;
606 }
607
608 /* _ch_buck_gut(): read in bucket, unifying key nouns.
609 */
610 static u3_weak
_ch_buck_gut(u3h_buck * hab_u,u3_noun key)611 _ch_buck_gut(u3h_buck* hab_u, u3_noun key)
612 {
613 c3_w i_w;
614
615 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
616 u3_noun kev = u3h_slot_to_noun(hab_u->sot_w[i_w]);
617 if ( _(u3r_sung(key, u3h(kev))) ) {
618 return u3a_gain(u3t(kev));
619 }
620 }
621 return u3_none;
622 }
623
624 /* _ch_node_gut(): read in node, unifying key nouns.
625 */
626 static u3_weak
_ch_node_gut(u3h_node * han_u,c3_w lef_w,c3_w rem_w,u3_noun key)627 _ch_node_gut(u3h_node* han_u, c3_w lef_w, c3_w rem_w, u3_noun key)
628 {
629 c3_w bit_w, map_w;
630
631 lef_w -= 5;
632 bit_w = (rem_w >> lef_w);
633 rem_w = (rem_w & ((1 << lef_w) - 1));
634 map_w = han_u->map_w;
635
636 if ( !(map_w & (1 << bit_w)) ) {
637 return u3_none;
638 }
639 else {
640 c3_w inx_w = _ch_popcount(map_w & ((1 << bit_w) - 1));
641 c3_w sot_w = han_u->sot_w[inx_w];
642
643 if ( _(u3h_slot_is_noun(sot_w)) ) {
644 u3_noun kev = u3h_slot_to_noun(sot_w);
645
646 if ( _(u3r_sung(key, u3h(kev))) ) {
647 return u3a_gain(u3t(kev));
648 }
649 else {
650 return u3_none;
651 }
652 }
653 else {
654 void* hav_v = u3h_slot_to_node(sot_w);
655
656 if ( 0 == lef_w ) {
657 return _ch_buck_gut(hav_v, key);
658 }
659 else return _ch_node_gut(hav_v, lef_w, rem_w, key);
660 }
661 }
662 }
663
664 /* u3h_gut(): read from hashtable, unifying key nouns.
665 **
666 ** `key` is RETAINED.
667 */
668 u3_weak
u3h_gut(u3p (u3h_root)har_p,u3_noun key)669 u3h_gut(u3p(u3h_root) har_p, u3_noun key)
670 {
671 u3h_root* har_u = u3to(u3h_root, har_p);
672 c3_w mug_w = u3r_mug(key);
673 c3_w inx_w = (mug_w >> 25);
674 c3_w rem_w = (mug_w & ((1 << 25) - 1));
675 c3_w sot_w = har_u->sot_w[inx_w];
676
677 if ( _(u3h_slot_is_null(sot_w)) ) {
678 return u3_none;
679 }
680 else if ( _(u3h_slot_is_noun(sot_w)) ) {
681 u3_noun kev = u3h_slot_to_noun(sot_w);
682
683 if ( _(u3r_sung(key, u3h(kev))) ) {
684 har_u->sot_w[inx_w] = u3h_noun_be_warm(sot_w);
685 return u3a_gain(u3t(kev));
686 }
687 else {
688 return u3_none;
689 }
690 }
691 else {
692 u3h_node* han_u = u3h_slot_to_node(sot_w);
693
694 return _ch_node_gut(han_u, 25, rem_w, key);
695 }
696 }
697
698 /* _ch_free_buck(): free bucket
699 */
700 static void
_ch_free_buck(u3h_buck * hab_u)701 _ch_free_buck(u3h_buck* hab_u)
702 {
703 c3_w i_w;
704
705 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
706 u3a_lose(u3h_slot_to_noun(hab_u->sot_w[i_w]));
707 }
708 u3a_wfree(hab_u);
709 }
710
711 /* _ch_free_node(): free node.
712 */
713 static void
_ch_free_node(u3h_node * han_u,c3_w lef_w)714 _ch_free_node(u3h_node* han_u, c3_w lef_w)
715 {
716 c3_w len_w = _ch_popcount(han_u->map_w);
717 c3_w i_w;
718
719 lef_w -= 5;
720
721 for ( i_w = 0; i_w < len_w; i_w++ ) {
722 c3_w sot_w = han_u->sot_w[i_w];
723
724 if ( _(u3h_slot_is_noun(sot_w)) ) {
725 u3_noun kev = u3h_slot_to_noun(sot_w);
726
727 u3a_lose(kev);
728 }
729 else {
730 void* hav_v = u3h_slot_to_node(sot_w);
731
732 if ( 0 == lef_w ) {
733 _ch_free_buck(hav_v);
734 } else {
735 _ch_free_node(hav_v, lef_w);
736 }
737 }
738 }
739 u3a_wfree(han_u);
740 }
741
742 /* u3h_free(): free hashtable.
743 */
744 void
u3h_free(u3p (u3h_root)har_p)745 u3h_free(u3p(u3h_root) har_p)
746 {
747 u3h_root* har_u = u3to(u3h_root, har_p);
748 c3_w i_w;
749
750 for ( i_w = 0; i_w < 64; i_w++ ) {
751 c3_w sot_w = har_u->sot_w[i_w];
752
753 if ( _(u3h_slot_is_noun(sot_w)) ) {
754 u3_noun kev = u3h_slot_to_noun(sot_w);
755
756 u3a_lose(kev);
757 }
758 else if ( _(u3h_slot_is_node(sot_w)) ) {
759 u3h_node* han_u = u3h_slot_to_node(sot_w);
760
761 _ch_free_node(han_u, 25);
762 }
763 }
764 u3a_wfree(har_u);
765 }
766
767 /* _ch_walk_buck(): walk bucket for gc.
768 */
769 static void
_ch_walk_buck(u3h_buck * hab_u,void (* fun_f)(u3_noun))770 _ch_walk_buck(u3h_buck* hab_u, void (*fun_f)(u3_noun))
771 {
772 c3_w i_w;
773
774 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
775 fun_f(u3h_slot_to_noun(hab_u->sot_w[i_w]));
776 }
777 }
778
779 /* _ch_walk_node(): walk node for gc.
780 */
781 static void
_ch_walk_node(u3h_node * han_u,c3_w lef_w,void (* fun_f)(u3_noun))782 _ch_walk_node(u3h_node* han_u, c3_w lef_w, void (*fun_f)(u3_noun))
783 {
784 c3_w len_w = _ch_popcount(han_u->map_w);
785 c3_w i_w;
786
787 lef_w -= 5;
788
789 for ( i_w = 0; i_w < len_w; i_w++ ) {
790 c3_w sot_w = han_u->sot_w[i_w];
791
792 if ( _(u3h_slot_is_noun(sot_w)) ) {
793 u3_noun kev = u3h_slot_to_noun(sot_w);
794
795 fun_f(kev);
796 }
797 else {
798 void* hav_v = u3h_slot_to_node(sot_w);
799
800 if ( 0 == lef_w ) {
801 _ch_walk_buck(hav_v, fun_f);
802 } else {
803 _ch_walk_node(hav_v, lef_w, fun_f);
804 }
805 }
806 }
807 }
808
809 /* u3h_walk(): walk hashtable for gc.
810 */
811 void
u3h_walk(u3p (u3h_root)har_p,void (* fun_f)(u3_noun))812 u3h_walk(u3p(u3h_root) har_p, void (*fun_f)(u3_noun))
813 {
814 u3h_root* har_u = u3to(u3h_root, har_p);
815 c3_w i_w;
816
817 for ( i_w = 0; i_w < 64; i_w++ ) {
818 c3_w sot_w = har_u->sot_w[i_w];
819
820 if ( _(u3h_slot_is_noun(sot_w)) ) {
821 u3_noun kev = u3h_slot_to_noun(sot_w);
822
823 fun_f(kev);
824 }
825 else if ( _(u3h_slot_is_node(sot_w)) ) {
826 u3h_node* han_u = u3h_slot_to_node(sot_w);
827
828 _ch_walk_node(han_u, 25, fun_f);
829 }
830 }
831 }
832
833
834 /* _ch_mark_buck(): mark bucket for gc.
835 */
836 c3_w
_ch_mark_buck(u3h_buck * hab_u)837 _ch_mark_buck(u3h_buck* hab_u)
838 {
839 c3_w tot_w = 0;
840 c3_w i_w;
841
842 for ( i_w = 0; i_w < hab_u->len_w; i_w++ ) {
843 tot_w += u3a_mark_noun(u3h_slot_to_noun(hab_u->sot_w[i_w]));
844 }
845 tot_w += u3a_mark_ptr(hab_u);
846
847 return tot_w;
848 }
849
850 /* _ch_mark_node(): mark node for gc.
851 */
852 c3_w
_ch_mark_node(u3h_node * han_u,c3_w lef_w)853 _ch_mark_node(u3h_node* han_u, c3_w lef_w)
854 {
855 c3_w tot_w = 0;
856 c3_w len_w = _ch_popcount(han_u->map_w);
857 c3_w i_w;
858
859 lef_w -= 5;
860
861 for ( i_w = 0; i_w < len_w; i_w++ ) {
862 c3_w sot_w = han_u->sot_w[i_w];
863
864 if ( _(u3h_slot_is_noun(sot_w)) ) {
865 u3_noun kev = u3h_slot_to_noun(sot_w);
866
867 tot_w += u3a_mark_noun(kev);
868 }
869 else {
870 void* hav_v = u3h_slot_to_node(sot_w);
871
872 if ( 0 == lef_w ) {
873 tot_w += _ch_mark_buck(hav_v);
874 } else {
875 tot_w += _ch_mark_node(hav_v, lef_w);
876 }
877 }
878 }
879
880 tot_w += u3a_mark_ptr(han_u);
881
882 return tot_w;
883 }
884
885 /* u3h_mark(): mark hashtable for gc.
886 */
887 c3_w
u3h_mark(u3p (u3h_root)har_p)888 u3h_mark(u3p(u3h_root) har_p)
889 {
890 c3_w tot_w = 0;
891 u3h_root* har_u = u3to(u3h_root, har_p);
892 c3_w i_w;
893
894 for ( i_w = 0; i_w < 64; i_w++ ) {
895 c3_w sot_w = har_u->sot_w[i_w];
896
897 if ( _(u3h_slot_is_noun(sot_w)) ) {
898 u3_noun kev = u3h_slot_to_noun(sot_w);
899
900 tot_w += u3a_mark_noun(kev);
901 }
902 else if ( _(u3h_slot_is_node(sot_w)) ) {
903 u3h_node* han_u = u3h_slot_to_node(sot_w);
904
905 tot_w += _ch_mark_node(han_u, 25);
906 }
907 }
908
909 tot_w += u3a_mark_ptr(har_u);
910
911 return tot_w;
912 }
913