51 lines
1.1 KiB
OCaml
51 lines
1.1 KiB
OCaml
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
|