1 /* include/n/h.h
2 **
3 ** This file is in the public domain.
4 */
5   /**  Data structures.
6   **/
7     /**  Straightforward implementation of the classic Bagwell
8     ***  HAMT (hash array mapped trie), using a mug hash.
9     ***
10     ***  Because a mug is 31 bits, the root table has 64 slots.
11     ***  The 31 bits of a mug are divided into the first lookup,
12     ***  which is 6 bits (corresponding to the 64 entries in the
13     ***  root table), followed by 5 more branchings of 5 bits each,
14     ***  corresponding to the 32-slot nodes for everything under
15     ***  the root node.
16     ***
17     ***  We store an extra "freshly warm" bit for a simple
18     ***  clock-algorithm reclamation policy, not yet implemented.
19     ***  Search "clock algorithm" to figure it out.
20     **/
21       /* u3h_slot: map slot.
22       **
23       **   Either a key-value cell or a loom offset, decoded as a pointer
24       **   to a u3h_node, or a u3h_buck at the bottom.  Matches the u3_noun
25       **   format - coordinate with allocate.h.  The top two bits are:
26       **
27       **     00 - empty (in the root table only)
28       **     01 - table
29       **     02 - entry, stale
30       **     03 - entry, fresh
31       */
32         typedef c3_w u3h_slot;
33 
34       /* u3h_node: map node.
35       */
36         typedef struct {
37           c3_w     map_w;
38           u3h_slot sot_w[0];
39         } u3h_node;
40 
41       /* u3h_root: hash root table
42       */
43         typedef struct {
44           c3_w     max_w;     // number of cache lines (0 for no trimming)
45           c3_w     use_w;     // number of lines currently filled
46           struct {
47             c3_w  mug_w;      // current hash
48             c3_w  inx_w;      // index into current hash bucket iff buc_o
49             c3_o  buc_o;      // yes if in middle of hash bucket
50           } arm_u;            // clock arm
51           u3h_slot sot_w[64]; // slots
52         } u3h_root;
53 
54       /* u3h_buck: bottom bucket.
55       */
56         typedef struct {
57           c3_w    len_w;
58           u3h_slot sot_w[0];
59         } u3h_buck;
60 
61     /**  HAMT macros.
62     ***
63     ***  Coordinate with u3_noun definition!
64     **/
65       /* u3h_slot_is_null(): yes iff slot is empty
66       ** u3h_slot_is_noun(): yes iff slot contains a key/value cell
67       ** u3h_slot_is_node(): yes iff slot contains a subtable/bucket
68       ** u3h_slot_is_warm(): yes iff fresh bit is set
69       ** u3h_slot_to_node(): slot to node pointer
70       ** u3h_node_to_slot(): node pointer to slot
71       ** u3h_slot_to_noun(): slot to cell
72       ** u3h_noun_to_slot(): cell to slot
73       ** u3h_noun_be_warm(): warm mutant
74       ** u3h_noun_be_cold(): cold mutant
75       */
76 #     define  u3h_slot_is_null(sot)  ((0 == ((sot) >> 30)) ? c3y : c3n)
77 #     define  u3h_slot_is_node(sot)  ((1 == ((sot) >> 30)) ? c3y : c3n)
78 #     define  u3h_slot_is_noun(sot)  ((1 == ((sot) >> 31)) ? c3y : c3n)
79 #     define  u3h_slot_is_warm(sot)  (((sot) & 0x40000000) ? c3y : c3n)
80 #     define  u3h_slot_to_node(sot)  (u3a_into((sot) & 0x3fffffff))
81 #     define  u3h_node_to_slot(ptr)  (u3a_outa(ptr) | 0x40000000)
82 #     define  u3h_noun_be_warm(sot)  ((sot) | 0x40000000)
83 #     define  u3h_noun_be_cold(sot)  ((sot) & ~0x40000000)
84 #     define  u3h_slot_to_noun(sot)  (0x40000000 | (sot))
85 #     define  u3h_noun_to_slot(som)  (u3h_noun_be_warm(som))
86 
87     /**  Functions.
88     ***
89     ***  Needs: delete and merge functions; clock reclamation function.
90     **/
91       /* u3h_new_cache(): create hashtable with bounded size.
92       */
93         u3p(u3h_root)
94         u3h_new_cache(c3_w clk_w);
95 
96       /* u3h_new(): create hashtable.
97       */
98         u3p(u3h_root)
99         u3h_new(void);
100 
101       /* u3h_put(): insert in hashtable.
102       **
103       ** `key` is RETAINED; `val` is transferred.
104       */
105         void
106         u3h_put(u3p(u3h_root) har_p, u3_noun key, u3_noun val);
107 
108       /* u3h_get(): read from hashtable.
109       **
110       ** `key` is RETAINED; result is PRODUCED.
111       */
112         u3_weak
113         u3h_get(u3p(u3h_root) har_p, u3_noun key);
114 
115       /* u3h_git(): read from hashtable, retaining result.
116       **
117       ** `key` is RETAINED; result is RETAINED.
118       */
119         u3_weak
120         u3h_git(u3p(u3h_root) har_p, u3_noun key);
121 
122       /* u3h_gut(): read from hashtable, unifying key nouns.
123       **
124       ** `key` is RETAINED.
125       */
126         u3_weak
127         u3h_gut(u3p(u3h_root) har_p, u3_noun key);
128 
129       /* u3h_trim_to(): trim to n key-value pairs
130       */
131         void
132         u3h_trim_to(u3p(u3h_root) har_p, c3_w n_w);
133 
134       /* u3h_free(): free hashtable.
135       */
136         void
137         u3h_free(u3p(u3h_root) har_p);
138 
139       /* u3h_mark(): mark hashtable for gc.
140       */
141         c3_w
142         u3h_mark(u3p(u3h_root) har_p);
143 
144       /* u3h_walk(): traverse hashtable with key, value fn; RETAINS.
145       */
146         void
147         u3h_walk(u3p(u3h_root) har_p, void (*fun_f)(u3_noun));
148