structure Hashtable: HASHTABLE = struct
  open Array
  open Word

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

  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
    ref (array (Word.toInt size, NONE), 0, mask)
  end

  exception Full

  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 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 => (update (array, ~> idx, SOME (key, v)); inc H; NONE)
         | SOME (key', v') =>
             if key' = key then
               (SOME v')
             else
               find (next idx mask)
  in
    find (hash key andb mask)
  end

  fun taken H =
  let
    val (_, taken, _) = !H
  in
    taken
  end

  fun size H =
  let
    val (array, _, _) = !H
  in
    length array
  end
end