Created
December 12, 2013 22:19
-
-
Save ksmr/7936595 to your computer and use it in GitHub Desktop.
A polymorphic bloom filter in Ocaml implemented using Int32
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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