structure Hashtable: HASHTABLE = struct
  open Array
  open Word

  (* buf * taken * mask *)
  type 'a t = (string * 'a) option array * int * word

  val ` = Word.fromInt
  val ! = Word.toInt

  infixr 4 <<
  infix 5 andb
  infixr 6 +
  infixr 7 *

  fun createLog log =
  let
    val size = `1 << `log
    val mask = size - `1
  in
    (array (Word.toInt size, NONE), 0, mask)
  end

  exception Full and Exists

  fun hash key =
    List.foldl (fn (c, s) => s * `31 + `(ord c)) (`17) (explode key)

  fun checkFreeSpace (array, taken, _) =
  let
    open Real
    val ` = fromInt
  in
    if `taken / `(length array) > 0.75 then
      raise Full
    else
      ()
  end

  fun next idx mask = (idx + `1) andb mask

  fun lookup2 ((array, _, mask): 'a t) (key: string) f g =
  let
    fun find idx =
      case sub (array, !idx) of
           NONE => g ()
         | SOME (key', v: 'a) =>
             if key' = key then
               case f v of
                    (NONE, res) => res
                  | (SOME v, res) =>
                      (update (array, !idx, SOME (key, v)); res)
             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 insert (H as (array, _, mask)) key v =
  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)
  in
    find (hash key andb mask)
  end
end