Skip to content

Instantly share code, notes, and snippets.

@ksmr
Created December 12, 2013 22:19
Show Gist options
  • Save ksmr/7936595 to your computer and use it in GitHub Desktop.
Save ksmr/7936595 to your computer and use it in GitHub Desktop.
A polymorphic bloom filter in Ocaml implemented using Int32
type 'a bloom32 = {
size : int;
bits : int32 array;
hash_funs : ('a -> int) list
};;
let empty (n : int) (hfs : ('a -> int) list) =
let n_bits = if n mod 32 = 0 then n/32 else (n/32)+1 in
{
size = n;
bits = Array.make n_bits 0l;
hash_funs = hfs
}
let set_bit (ba : 'a bloom32) (n : int) =
let array_index = n/32 in
let bit_index = n mod 32 in
ba.bits.(array_index) <- Int32.logor ba.bits.(array_index) (Int32.shift_left 0b1l bit_index)
let add (ba : 'a bloom32) (e : 'a) =
ignore (List.map (fun f -> set_bit ba (f e)) ba.hash_funs)
let is_bit_set (ba : 'a bloom32) (n : int) =
let array_index = n/32 in
let bit_index = n mod 32 in
Int32.logand ba.bits.(array_index) (Int32.shift_left 0b1l bit_index) <> 0l;;
let query (ba : 'a bloom32) (e : 'a) =
List.exists (fun f -> is_bit_set ba (f e)) ba.hash_funs;;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment