Current section
Files
Jump to
Current section
Files
src/gauzy@bloom_filter.erl
-module(gauzy@bloom_filter).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/gauzy/bloom_filter.gleam").
-export([new_hash_fn_pair/2, bit_size/1, false_positive_rate/1, hash_fn_count/1, new/3, insert/2, might_contain/2, reset/1, estimate_cardinality/1, insert_many/2]).
-export_type([bloom_filter_error/0, hash_function_pair/1, bloom_filter/1]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" This module provides an implementation of a Bloom filter, a space-efficient\n"
" probabilistic data structure that is used to test whether an element is a\n"
" member of a set. False positive matches are possible, but false negatives\n"
" are not – in other words, a query returns either \"possibly in set\" or\n"
" \"definitely not in set\".\n"
"\n"
" Bloom filters are useful in situations where the size of the set would\n"
" require an impractically large amount of memory to store, or where the\n"
" cost of a false positive is acceptable compared to the cost of a more\n"
" precise data structure.\n"
"\n"
" The module provides functions for creating, inserting into, querying, and\n"
" resetting Bloom filters.\n"
).
-type bloom_filter_error() :: equal_hash_functions |
invalid_capacity |
invalid_target_error_rate.
-opaque hash_function_pair(IMD) :: {hash_function_pair,
fun((IMD) -> integer()),
fun((IMD) -> integer())}.
-opaque bloom_filter(IME) :: {bloom_filter,
iv:array(integer()),
integer(),
integer(),
float(),
hash_function_pair(IME),
integer()}.
-file("src/gauzy/bloom_filter.gleam", 54).
?DOC(
" Creates a new pair of hash functions for the `BloomFilter`.\n"
"\n"
" The hash functions must not be equal! For optimal performance,\n"
" the hash functions should be random, uniform, and pairwise independent.\n"
"\n"
" * `first_hash_function`: The first hash function.\n"
" * `second_hash_function`: The second hash function.\n"
).
-spec new_hash_fn_pair(fun((IMF) -> integer()), fun((IMF) -> integer())) -> {ok,
hash_function_pair(IMF)} |
{error, bloom_filter_error()}.
new_hash_fn_pair(Hash_fn_1, Hash_fn_2) ->
case Hash_fn_1 =:= Hash_fn_2 of
false ->
{ok, {hash_function_pair, Hash_fn_1, Hash_fn_2}};
true ->
{error, equal_hash_functions}
end.
-file("src/gauzy/bloom_filter.gleam", 167).
?DOC(
" Returns the size of the `BloomFilter`'s underlying bit array.\n"
"\n"
" * `filter`: The `BloomFilter` from which to get the size\n"
).
-spec bit_size(bloom_filter(any())) -> integer().
bit_size(Filter) ->
erlang:element(3, Filter).
-file("src/gauzy/bloom_filter.gleam", 174).
?DOC(
" Returns the `BloomFilter`'s actual false positive rate\n"
"\n"
" * `filter`: The `BloomFilter` from which to get the error rate\n"
).
-spec false_positive_rate(bloom_filter(any())) -> float().
false_positive_rate(Filter) ->
erlang:element(5, Filter).
-file("src/gauzy/bloom_filter.gleam", 181).
?DOC(
" Returns the number of hash functions the `BloomFilter` uses.\n"
"\n"
" * `filter`: The `BloomFilter` from which to get the hash function count\n"
).
-spec hash_fn_count(bloom_filter(any())) -> integer().
hash_fn_count(Filter) ->
erlang:element(4, Filter).
-file("src/gauzy/bloom_filter.gleam", 220).
?DOC(
" Calculates the optimal size in bits of a Bloom filter.\n"
" Used in filter construction.\n"
"\n"
" * `capacity`: The number of bits that constitute the filter\n"
" * `target_err_rate`: The Bloom filter's acceptable false positive rate\n"
).
-spec optimal_bit_size(integer(), float()) -> integer().
optimal_bit_size(Capacity, Target_err_rate) ->
Ln_2@1 = case gleam@float:logarithm(2.0) of
{ok, Ln_2} -> Ln_2;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"gauzy/bloom_filter"/utf8>>,
function => <<"optimal_bit_size"/utf8>>,
line => 222,
value => _assert_fail,
start => 7571,
'end' => 7613,
pattern_start => 7582,
pattern_end => 7590})
end,
Ln_2_squared@1 = case gleam@float:power(Ln_2@1, 2.0) of
{ok, Ln_2_squared} -> Ln_2_squared;
_assert_fail@1 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"gauzy/bloom_filter"/utf8>>,
function => <<"optimal_bit_size"/utf8>>,
line => 224,
value => _assert_fail@1,
start => 7661,
'end' => 7713,
pattern_start => 7672,
pattern_end => 7688})
end,
Ln_target_err_rate@1 = case gleam@float:logarithm(Target_err_rate) of
{ok, Ln_target_err_rate} -> Ln_target_err_rate;
_assert_fail@2 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"gauzy/bloom_filter"/utf8>>,
function => <<"optimal_bit_size"/utf8>>,
line => 226,
value => _assert_fail@2,
start => 7779,
'end' => 7847,
pattern_start => 7790,
pattern_end => 7812})
end,
_pipe = case Ln_2_squared@1 of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> -1.0 * (erlang:float(Capacity) * Ln_target_err_rate@1)
/ Gleam@denominator
end,
_pipe@1 = math:ceil(_pipe),
erlang:round(_pipe@1).
-file("src/gauzy/bloom_filter.gleam", 239).
?DOC(
" * `capacity`: The number of elements that the filter shall be able to hold\n"
" Calculates the optimal number of hash functions for a Bloom filter.\n"
" Used in filter construction.\n"
"\n"
" * `bit_size`: The number of bits that constitute the filter\n"
" * `capacity`: The number of elements that the filter shall be able to hold\n"
).
-spec optimal_hash_fn_count(integer(), integer()) -> integer().
optimal_hash_fn_count(Bit_size, Capacity) ->
Ln_2@1 = case gleam@float:logarithm(2.0) of
{ok, Ln_2} -> Ln_2;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"gauzy/bloom_filter"/utf8>>,
function => <<"optimal_hash_fn_count"/utf8>>,
line => 241,
value => _assert_fail,
start => 8421,
'end' => 8463,
pattern_start => 8432,
pattern_end => 8440})
end,
_pipe = (case erlang:float(Capacity) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> erlang:float(Bit_size) / Gleam@denominator
end) * Ln_2@1,
_pipe@1 = erlang:round(_pipe),
gleam@int:max(_pipe@1, 1).
-file("src/gauzy/bloom_filter.gleam", 255).
?DOC(
" Calculates the actual false positive rate of a `Bloomfilter`.\n"
" Used in filter construction.\n"
"\n"
" * `bit_size`: The number of bits that constitute the filter\n"
" * `capacity`: The number of elements that the filter shall be able to hold\n"
" * `hash_fns_count`: The number of hash functions the filter uses\n"
"\n"
" Returns an `f64` as the expected false positive rate.\n"
).
-spec actual_false_positive_rate(integer(), integer(), integer()) -> float().
actual_false_positive_rate(Bit_size, Capacity, Hash_fn_count) ->
False_positive_rate@1 = case gleam@float:power(
1.0 - math:exp(case (erlang:float(Bit_size)) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> -1.0 * (erlang:float(Hash_fn_count) * erlang:float(
Capacity
))
/ Gleam@denominator
end),
erlang:float(Hash_fn_count)
) of
{ok, False_positive_rate} -> False_positive_rate;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"gauzy/bloom_filter"/utf8>>,
function => <<"actual_false_positive_rate"/utf8>>,
line => 263,
value => _assert_fail,
start => 9178,
'end' => 9442,
pattern_start => 9189,
pattern_end => 9212})
end,
False_positive_rate@1.
-file("src/gauzy/bloom_filter.gleam", 282).
?DOC(
" Returns a list of unique, sorted bit indices for the given `item`\n"
" using the `BloomFilter`'s hash functions.\n"
"\n"
" * `bloom_filter`: The `BloomFilter` to get the bit indices from\n"
" * `item`: The item to calculate the bit indices for\n"
).
-spec get_bit_indices(bloom_filter(INI), INI) -> list(integer()).
get_bit_indices(Filter, Item) ->
{hash_function_pair, Hash_fn_1, Hash_fn_2} = erlang:element(6, Filter),
Hash_1@2 = case Hash_fn_1(Item) of
Hash_1 when Hash_1 < 0 ->
_pipe = (2 * Hash_1),
gleam@int:absolute_value(_pipe);
Hash_1@1 ->
Hash_1@1
end,
Hash_2@2 = case Hash_fn_2(Item) of
Hash_2 when Hash_2 < 0 ->
_pipe@1 = (2 * Hash_2),
gleam@int:absolute_value(_pipe@1);
Hash_2@1 ->
Hash_2@1
end,
gleam@int:range(
0,
erlang:element(4, Filter),
[],
fun(Acc, I) ->
[(I * erlang:element(7, Filter)) + (case erlang:element(7, Filter) of
0 -> 0;
Gleam@denominator -> (Hash_1@2 + (I * Hash_2@2)) rem Gleam@denominator
end) |
Acc]
end
).
-file("src/gauzy/bloom_filter.gleam", 351).
?DOC(
" Sets bits in the array according to the provided word masks.\n"
" Returns an `Array` with the specified bits applied using bitwise OR.\n"
" \n"
" * `array`: The bit array to update\n"
" * `word_masks`: Dict mapping word indices to their bit masks\n"
).
-spec set_bits_in_array(
iv:array(integer()),
gleam@dict:dict(integer(), integer())
) -> iv:array(integer()).
set_bits_in_array(Array, Word_masks) ->
gleam@dict:fold(
Word_masks,
Array,
fun(Array@1, Word_idx, Mask) ->
iv:try_update(
Array@1,
Word_idx,
fun(Word) -> erlang:'bor'(Word, Mask) end
)
end
).
-file("src/gauzy/bloom_filter.gleam", 84).
?DOC(
" Creates a new `BloomFilter`.\n"
"\n"
" * `capacity`: The number of items the `BloomFilter` is expected to hold.\n"
" * `target_error_rate`: The desired false positive rate (between 0.0 and 1.0).\n"
" * `hash_function_pair`: The hash functions used to generate indices.\n"
).
-spec new(integer(), float(), hash_function_pair(IMH)) -> {ok,
bloom_filter(IMH)} |
{error, bloom_filter_error()}.
new(Capacity, Target_error_rate, Hash_function_pair) ->
gleam@bool:guard(
Capacity < 1,
{error, invalid_capacity},
fun() ->
gleam@bool:guard(
(Target_error_rate =< +0.0) orelse (1.0 =< Target_error_rate),
{error, invalid_target_error_rate},
fun() ->
Optimal_bit_size = optimal_bit_size(
Capacity,
Target_error_rate
),
Hash_fn_count = optimal_hash_fn_count(
Optimal_bit_size,
Capacity
),
Bit_size = case case Hash_fn_count of
0 -> 0;
Gleam@denominator -> Optimal_bit_size rem Gleam@denominator
end of
0 ->
Optimal_bit_size;
_ ->
Optimal_bit_size + (Hash_fn_count - (case Hash_fn_count of
0 -> 0;
Gleam@denominator@1 -> Optimal_bit_size rem Gleam@denominator@1
end))
end,
False_positive_rate = actual_false_positive_rate(
Bit_size,
Capacity,
Hash_fn_count
),
Chunk_size = case Hash_fn_count of
0 -> 0;
Gleam@denominator@2 -> Bit_size div Gleam@denominator@2
end,
Word_chunk_count = (case 52 of
0 -> 0;
Gleam@denominator@3 -> Bit_size div Gleam@denominator@3
end) + 1,
{ok,
{bloom_filter,
iv:repeat(0, Word_chunk_count),
Bit_size,
Hash_fn_count,
False_positive_rate,
Hash_function_pair,
Chunk_size}}
end
)
end
).
-file("src/gauzy/bloom_filter.gleam", 120).
?DOC(
" Inserts an item into the `BloomFilter`.\n"
"\n"
" * `filter`: The `BloomFilter` to insert into.\n"
" * `item`: The item to insert.\n"
).
-spec insert(bloom_filter(IMM), IMM) -> bloom_filter(IMM).
insert(Filter, Item) ->
Indices = get_bit_indices(Filter, Item),
Array@1 = gleam@list:fold(
Indices,
erlang:element(2, Filter),
fun(Array, Idx) ->
Word_idx = case 52 of
0 -> 0;
Gleam@denominator -> Idx div Gleam@denominator
end,
Mask = erlang:'bsl'(1, (case 52 of
0 -> 0;
Gleam@denominator@1 -> Idx rem Gleam@denominator@1
end)),
iv:try_update(
Array,
Word_idx,
fun(Word) -> erlang:'bor'(Word, Mask) end
)
end
),
{bloom_filter,
Array@1,
erlang:element(3, Filter),
erlang:element(4, Filter),
erlang:element(5, Filter),
erlang:element(6, Filter),
erlang:element(7, Filter)}.
-file("src/gauzy/bloom_filter.gleam", 152).
?DOC(
" Checks if the `BloomFilter` might contain the given `item`.\n"
"\n"
" * `filter`: The `BloomFilter` to check\n"
" * `item`: The item to check for\n"
).
-spec might_contain(bloom_filter(IMT), IMT) -> boolean().
might_contain(Filter, Item) ->
_pipe = get_bit_indices(Filter, Item),
gleam@list:all(
_pipe,
fun(Idx) ->
Word_idx = case 52 of
0 -> 0;
Gleam@denominator -> Idx div Gleam@denominator
end,
Word = iv:get_or_default(erlang:element(2, Filter), Word_idx, 0),
Mask = erlang:'bsl'(1, case 52 of
0 -> 0;
Gleam@denominator@1 -> Idx rem Gleam@denominator@1
end),
erlang:'band'(Word, Mask) =:= Mask
end
).
-file("src/gauzy/bloom_filter.gleam", 211).
?DOC(
" Returns an empty `BloomFilter` with the same characteristics as the input filter.\n"
"\n"
" * `filter`: The `BloomFilter` to reset\n"
).
-spec reset(bloom_filter(IND)) -> bloom_filter(IND).
reset(Filter) ->
{bloom_filter, iv:repeat(0, (case 52 of
0 -> 0;
Gleam@denominator -> erlang:element(3, Filter) div Gleam@denominator
end) + 1), erlang:element(3, Filter), erlang:element(4, Filter), erlang:element(
5,
Filter
), erlang:element(6, Filter), erlang:element(7, Filter)}.
-file("src/gauzy/bloom_filter.gleam", 303).
?DOC(
" Counts the number of set bits (population count) in an integer.\n"
" Used by `estimate_cardinality`.\n"
"\n"
" * `word`: The integer (representing a word from the bit array) for which to count set bits.\n"
).
-spec count_set_bits(integer()) -> integer().
count_set_bits(Word) ->
gleam@int:range(
0,
52,
0,
fun(Acc, I) ->
Mask = erlang:'bsl'(1, I),
case erlang:'band'(Word, Mask) =:= Mask of
true ->
Acc + 1;
false ->
Acc
end
end
).
-file("src/gauzy/bloom_filter.gleam", 189).
?DOC(
" Returns an _approximation_ of unique items inserted into the `BloomFilter`.\n"
" This can differ substantially from reality, especially in smaller filters.\n"
"\n"
" * `filter`: The `BloomFilter` for which to estimate\n"
).
-spec estimate_cardinality(bloom_filter(any())) -> integer().
estimate_cardinality(Filter) ->
Set_bits = iv:fold(
erlang:element(2, Filter),
0,
fun(Total_set_bits, Word) -> Total_set_bits + count_set_bits(Word) end
),
Partial_calc@1 = case gleam@float:logarithm(
1.0 - (case erlang:float(erlang:element(3, Filter)) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> erlang:float(Set_bits) / Gleam@denominator
end)
) of
{ok, Partial_calc} -> Partial_calc;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"gauzy/bloom_filter"/utf8>>,
function => <<"estimate_cardinality"/utf8>>,
line => 196,
value => _assert_fail,
start => 6703,
'end' => 6829,
pattern_start => 6714,
pattern_end => 6730})
end,
_pipe = (case erlang:float(erlang:element(4, Filter)) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator@1 -> -1.0 * erlang:float(erlang:element(3, Filter)) / Gleam@denominator@1
end) * Partial_calc@1,
erlang:round(_pipe).
-file("src/gauzy/bloom_filter.gleam", 331).
?DOC(
" Groups bit indices by their word position and combines them into masks.\n"
" Returns a `Dict` with bits grouped by word index.\n"
" \n"
" * `word_masks`: Existing word masks to merge with\n"
" * `indices`: List of bit indices to group\n"
).
-spec group_bits_by_word(gleam@dict:dict(integer(), integer()), list(integer())) -> gleam@dict:dict(integer(), integer()).
group_bits_by_word(Word_masks, Indices) ->
gleam@list:fold(
Indices,
Word_masks,
fun(Acc, Idx) ->
Word_idx = case 52 of
0 -> 0;
Gleam@denominator -> Idx div Gleam@denominator
end,
Bit_mask = erlang:'bsl'(1, (case 52 of
0 -> 0;
Gleam@denominator@1 -> Idx rem Gleam@denominator@1
end)),
case gleam_stdlib:map_get(Acc, Word_idx) of
{ok, Existing_mask} ->
gleam@dict:insert(
Acc,
Word_idx,
erlang:'bor'(Existing_mask, Bit_mask)
);
{error, _} ->
gleam@dict:insert(Acc, Word_idx, Bit_mask)
end
end
).
-file("src/gauzy/bloom_filter.gleam", 317).
?DOC(
" Calculates the bit masks needed to insert a list of items into the filter.\n"
" Returns a `Dict` mapping word indices to combined bit masks.\n"
" \n"
" * `filter`: The Bloom filter containing hash functions and configuration\n"
" * `items`: List of items to insert\n"
).
-spec calculate_insertion_masks(bloom_filter(INL), list(INL)) -> gleam@dict:dict(integer(), integer()).
calculate_insertion_masks(Filter, Items) ->
gleam@list:fold(
Items,
maps:new(),
fun(Acc, Item) ->
Indices = get_bit_indices(Filter, Item),
group_bits_by_word(Acc, Indices)
end
).
-file("src/gauzy/bloom_filter.gleam", 138).
?DOC(
" Bulk inserts multiple items into the `BloomFilter`.\n"
" This can be more efficient than inserting items one by one.\n"
"\n"
" * `filter`: The `BloomFilter` to insert into.\n"
" * `items`: The list of items to insert.\n"
).
-spec insert_many(bloom_filter(IMP), list(IMP)) -> bloom_filter(IMP).
insert_many(Filter, Items) ->
Word_masks = calculate_insertion_masks(Filter, Items),
Array = set_bits_in_array(erlang:element(2, Filter), Word_masks),
{bloom_filter,
Array,
erlang:element(3, Filter),
erlang:element(4, Filter),
erlang:element(5, Filter),
erlang:element(6, Filter),
erlang:element(7, Filter)}.