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