table.om (2323B)
1 struct tentry { 2 present: int; 3 key: int; 4 value: int; 5 } 6 7 struct table { 8 a: *alloc; 9 table: *tentry; 10 load: int; 11 fill: int; 12 cap: int; 13 } 14 15 func thash(x: int): int { 16 return x * -0x61c8864680b583eb; 17 } 18 19 func tcreate(a: *alloc): *table { 20 var t: *table; 21 22 t = alloc(a, sizeof(*t)) as *table; 23 24 t.a = a; 25 t.table = nil; 26 t.fill = 0; 27 t.cap = 0; 28 29 return t; 30 } 31 32 func trehash(t: *table, cap: int) { 33 var table: *tentry; 34 var o: *tentry; 35 var e: *tentry; 36 var len: int; 37 var i: int; 38 39 table = t.table; 40 t.table = alloc(t.a, cap * sizeof(*table)) as *tentry; 41 42 len = t.cap; 43 i = 0; 44 loop { 45 if i == len { 46 break; 47 } 48 49 o = &table[i]; 50 51 if o.present == 1 { 52 e = tfind(t, o.key); 53 e.present = 1; 54 e.key = o.key; 55 e.value = o.value; 56 } 57 58 i = i + 1; 59 } 60 61 free(t.a, table as *byte); 62 t.load = t.fill; 63 t.cap = cap; 64 } 65 66 // This trick I got from CPython. 67 // Use a LCG with the right parameters to get full period on a power of two sized table 68 // to get "randomized" probing. 69 func tfind(t: *table, x: int): *tentry { 70 var e: *tentry; 71 var mask: int; 72 var h: int; 73 74 h = thash(x) & mask; 75 loop { 76 e = &t.table[h]; 77 78 if e.present == 0 || e.key == x { 79 return e; 80 } 81 82 h = (h * 5 + 1) & mask; 83 } 84 } 85 86 func tget(t: *table, x: int, ok: *int): int { 87 var e: *tentry; 88 89 if t.fill == 0 { 90 if ok { 91 *ok = 0; 92 } 93 94 return 0; 95 } 96 97 e = tfind(t, x); 98 99 if e.present != 1 { 100 if ok { 101 *ok = 0; 102 } 103 104 return 0; 105 } 106 107 if ok { 108 *ok = 1; 109 } 110 111 return e.value; 112 } 113 114 func tset(t: *table, x: int, y: int) { 115 var e: *tentry; 116 117 if t.cap == 0 { 118 t.cap = 16; 119 t.table = alloc(t.a, t.cap * sizeof(*t.table)) as *tentry; 120 } 121 122 e = tfind(t, x); 123 124 if e.present != 1 { 125 t.fill = t.fill + 1; 126 e.present = 1; 127 } 128 129 if e.present == 0 { 130 t.load = t.load + 1; 131 } 132 133 e.value = y; 134 135 if t.load * 5 >= t.cap * 4 { 136 if t.fill * 5 >= t.cap * 4 { 137 trehash(t, t.cap * 2); 138 } else { 139 trehash(t, t.cap); 140 } 141 } 142 } 143 144 func tdel(t: *table, x: int) { 145 var e: *tentry; 146 147 if t.fill == 0 { 148 return; 149 } 150 151 e = tfind(t, x); 152 153 if e.present != 1 { 154 return; 155 } 156 157 t.fill = t.fill - 1; 158 e.present = 2; 159 160 if t.fill > 16 && t.fill * 3 < t.cap { 161 trehash(t, t.cap / 2); 162 } 163 } 164 165 func tclear(t: *table) { 166 free(t.a, t.table as *byte); 167 t.table = nil; 168 t.fill = 0; 169 t.cap = 0; 170 } 171 172 func tfree(t: *table) { 173 if t.table { 174 free(t.a, t.table as *byte); 175 } 176 177 free(t.a, t as *byte); 178 }