(** A bounded key-value cache with first-in-first-out eviction.

    Keys are strings; values are whatever the instance stores. When the cache
    is full, adding a new key evicts the oldest one. Adding a key that is
    already present is a no-op: callers build keys from content identifiers (a
    repository head hash, for example), so a key's value never changes.

    No locking: the server runs on a single Lwt event loop, and no operation
    here yields. *)

type 'a t = {
  capacity : int;
  table : (string, 'a) Hashtbl.t;
  order : string Queue.t;
}

let create ~capacity =
  { capacity; table = Hashtbl.create 64; order = Queue.create () }

let find cache key = Hashtbl.find_opt cache.table key

let add cache key value =
  if not (Hashtbl.mem cache.table key) then (
    if Queue.length cache.order >= cache.capacity then (
      match Queue.take_opt cache.order with
      | Some oldest -> Hashtbl.remove cache.table oldest
      | None -> ());
    Hashtbl.replace cache.table key value;
    Queue.add key cache.order)