commit 3c2cd14fc90f271cecd3eab71c77dcdd9cb218f5
parent 82543c91aae01d0798fe0cff438a9e8904037eb0
Author: erai <erai@omiltem.net>
Date: Sat, 15 Feb 2025 20:53:17 +0000
integer hash table
Diffstat:
| A | table.om | | | 175 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 175 insertions(+), 0 deletions(-)
diff --git a/table.om b/table.om
@@ -0,0 +1,175 @@
+struct tentry {
+ present: int;
+ key: int;
+ value: int;
+}
+
+struct table {
+ a: *alloc;
+ table: *tentry;
+ load: int;
+ fill: int;
+ cap: int;
+}
+
+func thash(x: int): int {
+ return x * 0x9e3779b97f4a7c15;
+}
+
+func tcreate(a: *alloc): *table {
+ var t: *table;
+
+ t = alloc(a, sizeof(*t)) as *table;
+
+ t.a = a;
+ t.table = nil;
+ t.fill = 0;
+ t.cap = 0;
+
+ return t;
+}
+
+func trehash(t: *table, cap: int) {
+ var table: *tentry;
+ var o: *tentry;
+ var e: *tentry;
+ var len: int;
+ var i: int;
+
+ table = t.table;
+ t.table = alloc(t.a, cap * sizeof(*table));
+
+ len = t.cap;
+ i = 0;
+ loop {
+ if i == len {
+ break;
+ }
+
+ o = &table[i];
+
+ if o.present == 1 {
+ e = tfind(t, o.key);
+ e.present = 1;
+ e.key = o.key;
+ e.value = o.value;
+ }
+
+ i = i + 1;
+ }
+
+ free(t.a, table as *byte);
+ t.load = t.fill;
+ t.cap = cap;
+}
+
+func tfind(t: *table, x: int): *tentry {
+ var e: *tentry;
+ var mask: int;
+ var h: int;
+
+ h = thash(x) & mask;
+ loop {
+ e = &t.table[h];
+
+ if e.present == 0 || e.key == x {
+ return e;
+ }
+
+ h = (h * 5 + 1) & mask;
+ }
+}
+
+func tget(t: *table, x: int, ok: *int): int {
+ var e: *tentry;
+
+ if t.fill == 0 {
+ if ok {
+ *ok = 0;
+ }
+
+ return 0;
+ }
+
+ e = tfind(t, x);
+
+ if e.present != 1 {
+ if ok {
+ *ok = 0;
+ }
+
+ return 0;
+ }
+
+ if ok {
+ *ok = 1;
+ }
+
+ return e.value;
+}
+
+func tset(t: *table, x: int, y: int) {
+ var e: *tentry;
+
+ if t.cap == 0 {
+ t.cap = 16;
+ t.table = alloc(t.a, t.cap * sizeof(*t.table));
+ }
+
+ e = tfind(t, x);
+
+ if e.present != 1 {
+ t.fill = t.fill + 1;
+ e.present = 1;
+ }
+
+ if e.present == 0 {
+ t.load = t.load + 1;
+ }
+
+ e.value = y;
+
+ if t.load * 5 >= t.cap * 4 {
+ if t.fill * 5 >= t.cap * 4 {
+ trehash(t, t.cap * 2);
+ } else {
+ trehash(t, t.cap);
+ }
+ }
+}
+
+func tdel(t: *table, x: int) {
+ var e: *tentry;
+
+ if t.fill == 0 {
+ return;
+ }
+
+ e = tfind(t, x);
+
+ if e.present != 1 {
+ return;
+ }
+
+ t.fill = t.fill - 1;
+ e.present = 2;
+
+ if t.fill > 16 && t.fill * 3 < t.cap {
+ trehash(t, t.cap / 2);
+ }
+}
+
+func tclear(t: *table) {
+ free(t.a, t.table as *byte);
+ t.table = nil;
+ t.fill = 0;
+ t.cap = 0;
+}
+
+func tfree(t: *table) {
+ if t.table {
+ free(t.a, t.table as *byte);
+ }
+
+ free(t.a, t as *byte);
+}
