Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
52 lines (42 sloc) 1.27 KB
open Core.Std
type ('a, 'b) t = { mutable length: int;
buckets: ('a * 'b) list array;
}
let num_buckets = 17
let hash_bucket key = (Hashtbl.hash key) mod num_buckets
let create () =
{ length = 0;
buckets = Array.create ~len:num_buckets [];
}
let length t = t.length
let find t key =
List.find_map t.buckets.(hash_bucket key)
~f:(fun (key',data) -> if key' = key then Some data else None)
let iter t ~f =
for i = 0 to Array.length t.buckets - 1 do
List.iter t.buckets.(i) ~f:(fun (key, data) -> f ~key ~data)
done
let bucket_has_key t i key =
List.exists t.buckets.(i) ~f:(fun (key',_) -> key' = key)
let add t ~key ~data =
let i = hash_bucket key in
let replace = bucket_has_key t i key in
let filtered_bucket =
if replace then
List.filter t.buckets.(i) ~f:(fun (key',_) -> key' <> key)
else
t.buckets.(i)
in
(* part 1 *)
let () = t.buckets.(i) <- (key, data) :: filtered_bucket in
if not replace then t.length <- t.length + 1
(* part 2 *)
let remove t key =
let i = hash_bucket key in
if bucket_has_key t i key then (
let filtered_bucket =
List.filter t.buckets.(i) ~f:(fun (key',_) -> key' <> key)
in
t.buckets.(i) <- filtered_bucket;
t.length <- t.length - 1
)