type ('k, 'v) t = {
  mutable index : int;
  entries : ('k, 'v) entry array;
  lookup : ('k, int Dllist.t) Hashtbl.t;
}

and ('k, 'v) entry =
  | Empty
  | Entry of 'k * 'v

let make n = {
  index = 0;
  entries = Array.make n Empty;
  lookup = Hashtbl.create (n * 2);
}

let find_all t k =
  match Hashtbl.find t.lookup k with
  | hist ->
    Dllist.fold_r
      (fun i vs ->
         match t.entries.(i) with
         | Empty -> failwith "Cache.find: BUG! empty entry"
         | Entry (_, v) -> v :: vs)
      hist []
  | exception Not_found ->
    []

let evict t =
  match t.entries.(t.index) with
  | Empty -> ()
  | Entry (k, _) ->
    let hist = Hashtbl.find t.lookup k in
    let i = Dllist.take_r hist in
    assert (i = t.index);
    if Dllist.is_empty hist then Hashtbl.remove t.lookup k;
    t.entries.(i) <- Empty

let add t k v =
  evict t;
  let i = t.index in
  let hist = try Hashtbl.find t.lookup k
    with Not_found ->
      let l = Dllist.create () in
      Hashtbl.replace t.lookup k l;
      l
  in
  Dllist.add_l i hist |> ignore;
  t.entries.(i) <- Entry (k, v);
  t.index <- succ i mod Array.length t.entries