From 6f3fa80b37ca5f8d992f5d6f66aee77ead303bf4 Mon Sep 17 00:00:00 2001
From: Vladimir Azarov <avm@intermediate-node.net>
Date: Mon, 26 May 2025 14:42:35 +0200
Subject: Symbol table

---
 hashtable.sml | 54 ++++++++++++++++++++++++++++++------------------------
 1 file changed, 30 insertions(+), 24 deletions(-)

(limited to 'hashtable.sml')

diff --git a/hashtable.sml b/hashtable.sml
index 822d1fd..286d241 100644
--- a/hashtable.sml
+++ b/hashtable.sml
@@ -3,10 +3,11 @@ structure Hashtable: HASHTABLE = struct
   open Word
 
   (* buf * taken * mask *)
-  type 'a t = (string * 'a) option array * int * word
+  type 'a t = ((string * 'a) option array * int * word) ref
+
 
   val ` = Word.fromInt
-  val ! = Word.toInt
+  val ~> = Word.toInt
 
   infixr 4 <<
   infix 5 andb
@@ -18,10 +19,10 @@ structure Hashtable: HASHTABLE = struct
     val size = `1 << `log
     val mask = size - `1
   in
-    (array (Word.toInt size, NONE), 0, mask)
+    ref (array (Word.toInt size, NONE), 0, mask)
   end
 
-  exception Full and Exists
+  exception Full
 
   fun hash key =
     List.foldl (fn (c, s) => s * `31 + `(ord c)) (`17) (explode key)
@@ -39,37 +40,42 @@ structure Hashtable: HASHTABLE = struct
 
   fun next idx mask = (idx + `1) andb mask
 
-  fun lookup2 (array, _, mask) key f g =
+  fun insertIfNew H key v =
   let
+    val (array, _, mask) = !H
+
+    fun inc H =
+    let
+      open Int
+      val (array, taken, mask) = !H
+    in
+      H := (array, taken + 1, mask)
+    end
+
+    val () = checkFreeSpace $ !H
     fun find idx =
-      case sub (array, !idx) of
-           NONE => g ()
-         | SOME (key', v) =>
+      case sub (array, ~> idx) of
+           NONE => (update (array, ~> idx, SOME (key, v)); inc H; NONE)
+         | SOME (key', v') =>
              if key' = key then
-               case f v of
-                    (NONE, res) => res
-                  | (SOME v, res) =>
-                      (update (array, !idx, SOME (key, v)); res)
+               (SOME v')
              else
                find (next idx mask)
   in
     find (hash key andb mask)
   end
 
-  fun lookup H key = lookup2 H key (fn v => (NONE, SOME v)) (fn () => NONE)
+  fun taken H =
+  let
+    val (_, taken, _) = !H
+  in
+    taken
+  end
 
-  fun insert (H as (array, _, mask)) key v =
+  fun size H =
   let
-    val () = checkFreeSpace H;
-    fun find idx =
-      case sub (array, !idx) of
-           NONE => update (array, !idx, SOME (key, v))
-         | SOME (key', _) =>
-             if key' = key then
-               raise Exists
-             else
-               find (next idx mask)
+    val (array, _, _) = !H
   in
-    find (hash key andb mask)
+    length array
   end
 end
-- 
cgit v1.2.3