Current section
Files
Jump to
Current section
Files
src/trove@internal@btree.erl
-module(trove@internal@btree).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/trove/internal/btree.gleam").
-export([error_to_string/1, new/0, new_with_capacity/1, from_header/4, root/1, size/1, dirt/1, capacity/1, contains/5, load_from_yielder/6, add_dirt/2, load/6, mark_deleted/5, delete/5, insert/7, lookup/6]).
-export_type([btree_error/0, insert_result/1, insert_outcome/1, delete_result/1, mark_deleted_result/1, btree/2]).
-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(false).
-type btree_error() :: {store_error, trove@internal@store:store_error()} |
{decode_error, binary()} |
{validation_error, binary()}.
-type insert_result(HRM) :: {insert_result, insert_outcome(HRM), boolean()}.
-type insert_outcome(HRN) :: {single, integer(), HRN} |
{split, integer(), HRN, HRN, integer()}.
-type delete_result(HRO) :: {deleted_node, integer(), gleam@option:option(HRO)} |
delete_not_found |
delete_empty.
-type mark_deleted_result(HRP) :: {marked, integer(), gleam@option:option(HRP)} |
mark_not_found.
-opaque btree(HRQ, HRR) :: {empty, integer(), integer()} |
{non_empty, integer(), integer(), integer(), integer()} |
{gleam_phantom, HRQ, HRR}.
-file("src/trove/internal/btree.gleam", 22).
?DOC(false).
-spec error_to_string(btree_error()) -> binary().
error_to_string(Error) ->
case Error of
{store_error, E} ->
trove@internal@store:error_to_string(E);
{decode_error, Detail} ->
<<"decode error: "/utf8, Detail/binary>>;
{validation_error, Detail@1} ->
<<"validation error: "/utf8, Detail@1/binary>>
end.
-file("src/trove/internal/btree.gleam", 30).
?DOC(false).
-spec read_node(trove@internal@store:store(), integer()) -> {ok, bitstring()} |
{error, btree_error()}.
read_node(Store, Location) ->
_pipe = trove@internal@store:get_node(Store, Location),
gleam@result:map_error(_pipe, fun(Field@0) -> {store_error, Field@0} end).
-file("src/trove/internal/btree.gleam", 35).
?DOC(false).
-spec write_node(trove@internal@store:store(), bitstring()) -> {ok, integer()} |
{error, btree_error()}.
write_node(Store, Data) ->
_pipe = trove@internal@store:put_node(Store, Data),
gleam@result:map_error(_pipe, fun(Field@0) -> {store_error, Field@0} end).
-file("src/trove/internal/btree.gleam", 71).
?DOC(false).
-spec new() -> btree(any(), any()).
new() ->
{empty, 0, 32}.
-file("src/trove/internal/btree.gleam", 76).
?DOC(false).
-spec new_with_capacity(integer()) -> btree(any(), any()).
new_with_capacity(Capacity) ->
case Capacity >= 2 of
true -> nil;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"new_with_capacity"/utf8>>,
line => 77,
value => _assert_fail,
start => 2082,
'end' => 2113,
pattern_start => 2093,
pattern_end => 2097})
end,
{empty, 0, Capacity}.
-file("src/trove/internal/btree.gleam", 83).
?DOC(false).
-spec from_header(
gleam@option:option(integer()),
integer(),
integer(),
integer()
) -> {ok, btree(any(), any())} | {error, btree_error()}.
from_header(Root, Size, Dirt, Capacity) ->
gleam@bool:guard(
Capacity < 2,
{error, {validation_error, <<"capacity must be at least 2"/utf8>>}},
fun() ->
gleam@bool:guard(
Dirt < 0,
{error,
{validation_error,
<<"inconsistent header: negative dirt"/utf8>>}},
fun() -> case {Root, Size} of
{none, 0} ->
{ok, {empty, Dirt, Capacity}};
{{some, R}, S} when S > 0 ->
{ok, {non_empty, R, S, Dirt, Capacity}};
{none, _} ->
{error,
{validation_error,
<<"inconsistent header: None root with non-zero size"/utf8>>}};
{{some, _}, _} ->
{error,
{validation_error,
<<"inconsistent header: Some root with zero or negative size"/utf8>>}}
end end
)
end
).
-file("src/trove/internal/btree.gleam", 111).
?DOC(false).
-spec root(btree(any(), any())) -> gleam@option:option(integer()).
root(Tree) ->
case Tree of
{empty, _, _} ->
none;
{non_empty, Root, _, _, _} ->
{some, Root}
end.
-file("src/trove/internal/btree.gleam", 119).
?DOC(false).
-spec size(btree(any(), any())) -> integer().
size(Tree) ->
case Tree of
{empty, _, _} ->
0;
{non_empty, _, Size, _, _} ->
Size
end.
-file("src/trove/internal/btree.gleam", 127).
?DOC(false).
-spec dirt(btree(any(), any())) -> integer().
dirt(Tree) ->
case Tree of
{empty, Dirt, _} ->
Dirt;
{non_empty, _, _, Dirt@1, _} ->
Dirt@1
end.
-file("src/trove/internal/btree.gleam", 135).
?DOC(false).
-spec capacity(btree(any(), any())) -> integer().
capacity(Tree) ->
case Tree of
{empty, _, Capacity} ->
Capacity;
{non_empty, _, _, _, Capacity@1} ->
Capacity@1
end.
-file("src/trove/internal/btree.gleam", 225).
?DOC(false).
-spec resolve_data(
trove@internal@store:store(),
integer(),
trove@codec:codec(HUD)
) -> {ok, gleam@option:option(HUD)} | {error, btree_error()}.
resolve_data(Store, Location, Value_codec) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_data_node(Data, Value_codec) of
{ok, {value, Value}} ->
{ok, {some, Value}};
{ok, deleted} ->
{ok, none};
{error, nil} ->
{error,
{decode_error,
<<"data node at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}}
end
end
).
-file("src/trove/internal/btree.gleam", 239).
?DOC(false).
-spec lookup_in_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({HUI, integer()}),
HUI,
trove@codec:codec(HUK),
fun((HUI, HUI) -> gleam@order:order())
) -> {ok, gleam@option:option(HUK)} | {error, btree_error()}.
lookup_in_leaf(Store, Children, Key, Value_codec, Compare) ->
case non_empty_list:find(
Children,
fun(Entry) -> Compare(erlang:element(1, Entry), Key) =:= eq end
) of
{ok, {_, Value_loc}} ->
resolve_data(Store, Value_loc, Value_codec);
{error, nil} ->
{ok, none}
end.
-file("src/trove/internal/btree.gleam", 504).
?DOC(false).
-spec do_insert_into_sorted(
list({HWB, integer()}),
HWB,
integer(),
fun((HWB, HWB) -> gleam@order:order())
) -> {list({HWB, integer()}), boolean()}.
do_insert_into_sorted(Children, Key, Location, Compare) ->
case Children of
[] ->
{[{Key, Location}], true};
[{Child_key, Child_loc} | Rest] ->
case Compare(Key, Child_key) of
lt ->
{[{Key, Location}, {Child_key, Child_loc} | Rest], true};
eq ->
{[{Key, Location} | Rest], false};
gt ->
{New_rest, Is_new} = do_insert_into_sorted(
Rest,
Key,
Location,
Compare
),
{[{Child_key, Child_loc} | New_rest], Is_new}
end
end.
-file("src/trove/internal/btree.gleam", 487).
?DOC(false).
-spec insert_into_sorted(
non_empty_list:non_empty_list({HVY, integer()}),
HVY,
integer(),
fun((HVY, HVY) -> gleam@order:order())
) -> {non_empty_list:non_empty_list({HVY, integer()}), boolean()}.
insert_into_sorted(Children, Key, Location, Compare) ->
{Result_list, Is_new} = do_insert_into_sorted(
non_empty_list:to_list(Children),
Key,
Location,
Compare
),
Nel@1 = case non_empty_list:from_list(Result_list) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"insert_into_sorted"/utf8>>,
line => 500,
value => _assert_fail,
start => 13907,
'end' => 13965,
pattern_start => 13918,
pattern_end => 13925})
end,
{Nel@1, Is_new}.
-file("src/trove/internal/btree.gleam", 525).
?DOC(false).
-spec split_children(non_empty_list:non_empty_list({HWE, integer()})) -> {non_empty_list:non_empty_list({HWE,
integer()}),
HWE,
HWE,
non_empty_list:non_empty_list({HWE, integer()})}.
split_children(Children) ->
Count = non_empty_list:length(Children),
Mid = Count div 2,
Left = non_empty_list:take(Children, Mid),
Right = non_empty_list:drop(Children, Mid),
Left_nel@1 = case non_empty_list:from_list(Left) of
{ok, Left_nel} -> Left_nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"split_children"/utf8>>,
line => 537,
value => _assert_fail,
start => 14988,
'end' => 15044,
pattern_start => 14999,
pattern_end => 15011})
end,
Right_nel@1 = case non_empty_list:from_list(Right) of
{ok, Right_nel} -> Right_nel;
_assert_fail@1 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"split_children"/utf8>>,
line => 538,
value => _assert_fail@1,
start => 15047,
'end' => 15105,
pattern_start => 15058,
pattern_end => 15071})
end,
{Left_min, _} = non_empty_list:first(Left_nel@1),
{Right_min, _} = non_empty_list:first(Right_nel@1),
{Left_nel@1, Left_min, Right_min, Right_nel@1}.
-file("src/trove/internal/btree.gleam", 559).
?DOC(false).
-spec do_find_branch_child_index(
list({HWK, integer()}),
HWK,
fun((HWK, HWK) -> gleam@order:order()),
integer(),
{integer(), integer()}
) -> {integer(), integer()}.
do_find_branch_child_index(Children, Key, Compare, Index, Best) ->
case Children of
[] ->
Best;
[{Child_key, Child_loc} | Rest] ->
case Compare(Child_key, Key) of
lt ->
do_find_branch_child_index(
Rest,
Key,
Compare,
Index + 1,
{Index, Child_loc}
);
eq ->
do_find_branch_child_index(
Rest,
Key,
Compare,
Index + 1,
{Index, Child_loc}
);
gt ->
Best
end
end.
-file("src/trove/internal/btree.gleam", 544).
?DOC(false).
-spec find_branch_child_index(
non_empty_list:non_empty_list({HWI, integer()}),
HWI,
fun((HWI, HWI) -> gleam@order:order())
) -> {integer(), integer()}.
find_branch_child_index(Children, Key, Compare) ->
{_, First_loc} = non_empty_list:first(Children),
do_find_branch_child_index(
non_empty_list:to_list(Children),
Key,
Compare,
0,
{0, First_loc}
).
-file("src/trove/internal/btree.gleam", 175).
?DOC(false).
-spec contains_at(
trove@internal@store:store(),
integer(),
HTS,
trove@codec:codec(HTS),
fun((HTS, HTS) -> gleam@order:order())
) -> {ok, boolean()} | {error, btree_error()}.
contains_at(Store, Location, Key, Key_codec, Compare) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
{ok, {leaf, Children}} ->
case non_empty_list:find(
Children,
fun(Entry) ->
Compare(erlang:element(1, Entry), Key) =:= eq
end
) of
{ok, {_, Data_loc}} ->
gleam@result:'try'(
read_node(Store, Data_loc),
fun(Data@1) ->
{ok,
not trove@internal@btree@node:is_tombstone(
Data@1
)}
end
);
{error, nil} ->
{ok, false}
end;
{ok, {branch, Children@1}} ->
{_, Child_loc} = find_branch_child_index(
Children@1,
Key,
Compare
),
contains_at(Store, Child_loc, Key, Key_codec, Compare);
{error, nil} ->
{error,
{decode_error,
<<"tree node at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}}
end
end
).
-file("src/trove/internal/btree.gleam", 161).
?DOC(false).
-spec contains(
btree(HTL, any()),
trove@internal@store:store(),
HTL,
trove@codec:codec(HTL),
fun((HTL, HTL) -> gleam@order:order())
) -> {ok, boolean()} | {error, btree_error()}.
contains(Tree, Store, Key, Key_codec, Compare) ->
case Tree of
{empty, _, _} ->
{ok, false};
{non_empty, Location, _, _, _} ->
contains_at(Store, Location, Key, Key_codec, Compare)
end.
-file("src/trove/internal/btree.gleam", 580).
?DOC(false).
-spec replace_child(
non_empty_list:non_empty_list({HWM, integer()}),
integer(),
HWM,
integer()
) -> non_empty_list:non_empty_list({HWM, integer()}).
replace_child(Children, Index, New_key, New_loc) ->
Children_list = non_empty_list:to_list(Children),
Before = gleam@list:take(Children_list, Index),
After = gleam@list:drop(Children_list, Index + 1),
Result = lists:append(Before, [{New_key, New_loc} | After]),
Nel@1 = case non_empty_list:from_list(Result) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"replace_child"/utf8>>,
line => 590,
value => _assert_fail,
start => 16439,
'end' => 16492,
pattern_start => 16450,
pattern_end => 16457})
end,
Nel@1.
-file("src/trove/internal/btree.gleam", 594).
?DOC(false).
-spec splice_split(
non_empty_list:non_empty_list({HWP, integer()}),
integer(),
HWP,
integer(),
HWP,
integer()
) -> non_empty_list:non_empty_list({HWP, integer()}).
splice_split(Children, Index, Left_key, Left_loc, Right_key, Right_loc) ->
Children_list = non_empty_list:to_list(Children),
Before = gleam@list:take(Children_list, Index),
After = gleam@list:drop(Children_list, Index + 1),
Result = lists:append(
Before,
[{Left_key, Left_loc}, {Right_key, Right_loc} | After]
),
Nel@1 = case non_empty_list:from_list(Result) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"splice_split"/utf8>>,
line => 611,
value => _assert_fail,
start => 16973,
'end' => 17026,
pattern_start => 16984,
pattern_end => 16991})
end,
Nel@1.
-file("src/trove/internal/btree.gleam", 815).
?DOC(false).
-spec write_tree_node(
trove@internal@store:store(),
trove@internal@btree@node:tree_node(HYU),
trove@codec:codec(HYU)
) -> {ok, integer()} | {error, btree_error()}.
write_tree_node(Store, Tree_node, Key_codec) ->
write_node(
Store,
trove@internal@btree@node:encode_tree_node(Tree_node, Key_codec)
).
-file("src/trove/internal/btree.gleam", 378).
?DOC(false).
-spec insert_into_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({HVM, integer()}),
HVM,
integer(),
integer(),
trove@codec:codec(HVM),
fun((HVM, HVM) -> gleam@order:order())
) -> {ok, insert_result(HVM)} | {error, btree_error()}.
insert_into_leaf(Store, Children, Key, Value_loc, Capacity, Key_codec, Compare) ->
{New_children, Is_new} = insert_into_sorted(
Children,
Key,
Value_loc,
Compare
),
{Min_key, _} = non_empty_list:first(New_children),
Count = non_empty_list:length(New_children),
gleam@bool:lazy_guard(
Count =< Capacity,
fun() ->
gleam@result:'try'(
write_tree_node(Store, {leaf, New_children}, Key_codec),
fun(Loc) ->
{ok, {insert_result, {single, Loc, Min_key}, Is_new}}
end
)
end,
fun() ->
{Left_children, Left_min, Right_min, Right_children} = split_children(
New_children
),
gleam@result:'try'(
write_tree_node(Store, {leaf, Left_children}, Key_codec),
fun(Left_loc) ->
gleam@result:'try'(
write_tree_node(
Store,
{leaf, Right_children},
Key_codec
),
fun(Right_loc) ->
{ok,
{insert_result,
{split,
Left_loc,
Left_min,
Right_min,
Right_loc},
Is_new}}
end
)
end
)
end
).
-file("src/trove/internal/btree.gleam", 781).
?DOC(false).
-spec flush_chunk(
list({HYI, integer()}),
trove@internal@store:store(),
trove@codec:codec(HYI),
fun((non_empty_list:non_empty_list({HYI, integer()})) -> trove@internal@btree@node:tree_node(HYI))
) -> {ok, {HYI, integer()}} | {error, btree_error()}.
flush_chunk(Children, Store, Key_codec, Make_node) ->
Nel@1 = case non_empty_list:from_list(Children) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"flush_chunk"/utf8>>,
line => 787,
value => _assert_fail,
start => 22163,
'end' => 22218,
pattern_start => 22174,
pattern_end => 22181})
end,
{First_key, _} = non_empty_list:first(Nel@1),
gleam@result:'try'(
write_tree_node(Store, Make_node(Nel@1), Key_codec),
fun(Loc) -> {ok, {First_key, Loc}} end
).
-file("src/trove/internal/btree.gleam", 772).
?DOC(false).
-spec write_chunks(
list(list({HXZ, integer()})),
trove@internal@store:store(),
trove@codec:codec(HXZ),
fun((non_empty_list:non_empty_list({HXZ, integer()})) -> trove@internal@btree@node:tree_node(HXZ))
) -> {ok, list({HXZ, integer()})} | {error, btree_error()}.
write_chunks(Chunks, Store, Key_codec, Make_node) ->
gleam@list:try_map(
Chunks,
fun(_capture) -> flush_chunk(_capture, Store, Key_codec, Make_node) end
).
-file("src/trove/internal/btree.gleam", 761).
?DOC(false).
-spec write_level(
list({HXR, integer()}),
integer(),
trove@internal@store:store(),
trove@codec:codec(HXR),
fun((non_empty_list:non_empty_list({HXR, integer()})) -> trove@internal@btree@node:tree_node(HXR))
) -> {ok, list({HXR, integer()})} | {error, btree_error()}.
write_level(Pairs, Capacity, Store, Key_codec, Make_node) ->
Chunks = gleam@list:sized_chunk(Pairs, Capacity),
write_chunks(Chunks, Store, Key_codec, Make_node).
-file("src/trove/internal/btree.gleam", 793).
?DOC(false).
-spec build_branches(
list({HYP, integer()}),
integer(),
trove@internal@store:store(),
trove@codec:codec(HYP)
) -> {ok, integer()} | {error, btree_error()}.
build_branches(Pairs, Capacity, Store, Key_codec) ->
case Pairs of
[] ->
{error,
{validation_error,
<<"build_branches called with empty pairs"/utf8>>}};
[{_, Loc}] ->
{ok, Loc};
[_, _ | _] ->
gleam@result:'try'(
write_level(
Pairs,
Capacity,
Store,
Key_codec,
fun(Field@0) -> {branch, Field@0} end
),
fun(Branch_pairs) ->
build_branches(Branch_pairs, Capacity, Store, Key_codec)
end
)
end.
-file("src/trove/internal/btree.gleam", 826).
?DOC(false).
-spec write_data_node(
trove@internal@store:store(),
trove@internal@btree@node:data_node(HYZ),
trove@codec:codec(HYZ)
) -> {ok, integer()} | {error, btree_error()}.
write_data_node(Store, Data_node, Value_codec) ->
write_node(
Store,
trove@internal@btree@node:encode_data_node(Data_node, Value_codec)
).
-file("src/trove/internal/btree.gleam", 660).
?DOC(false).
-spec load_from_yielder(
gleam@yielder:yielder({HXB, HXC}),
trove@internal@store:store(),
integer(),
trove@codec:codec(HXB),
trove@codec:codec(HXC),
fun((HXB, HXB) -> gleam@order:order())
) -> {ok, btree(HXB, HXC)} | {error, btree_error()}.
load_from_yielder(Entries, Store, Capacity, Key_codec, Value_codec, Compare) ->
gleam@bool:guard(
Capacity < 2,
{error, {validation_error, <<"capacity must be at least 2"/utf8>>}},
fun() ->
Initial = {[], [], 0, 0, none},
gleam@result:'try'(
gleam@yielder:try_fold(
Entries,
Initial,
fun(State, Entry) ->
{Chunk_rev, Leaves_rev, Chunk_size, Count, Prev_key} = State,
{Key, Value} = Entry,
gleam@result:'try'(case Prev_key of
none ->
{ok, nil};
{some, Prev} ->
case Compare(Prev, Key) of
lt ->
{ok, nil};
eq ->
{error,
{validation_error,
<<"duplicate key in bulk load input"/utf8>>}};
gt ->
{error,
{validation_error,
<<"unsorted key in bulk load input"/utf8>>}}
end
end, fun(_use0) ->
nil = _use0,
gleam@result:'try'(
write_data_node(
Store,
{value, Value},
Value_codec
),
fun(Data_loc) ->
Chunk_rev@1 = [{Key, Data_loc} |
Chunk_rev],
Chunk_size@1 = Chunk_size + 1,
Count@1 = Count + 1,
case Chunk_size@1 >= Capacity of
true ->
Leaf_children = lists:reverse(
Chunk_rev@1
),
gleam@result:'try'(
flush_chunk(
Leaf_children,
Store,
Key_codec,
fun(Field@0) -> {leaf, Field@0} end
),
fun(Leaf_pair) ->
{ok,
{[],
[Leaf_pair |
Leaves_rev],
0,
Count@1,
{some, Key}}}
end
);
false ->
{ok,
{Chunk_rev@1,
Leaves_rev,
Chunk_size@1,
Count@1,
{some, Key}}}
end
end
)
end)
end
),
fun(_use0@1) ->
{Remaining, Leaf_pairs_rev, _, Total_count, _} = _use0@1,
gleam@result:'try'(case Remaining of
[] ->
{ok, lists:reverse(Leaf_pairs_rev)};
_ ->
Leaf_children@1 = lists:reverse(Remaining),
gleam@result:'try'(
flush_chunk(
Leaf_children@1,
Store,
Key_codec,
fun(Field@0) -> {leaf, Field@0} end
),
fun(Leaf_pair@1) ->
{ok,
lists:reverse(
[Leaf_pair@1 | Leaf_pairs_rev]
)}
end
)
end, fun(Leaf_pairs) -> case Total_count of
0 ->
{ok, {empty, 0, Capacity}};
_ ->
gleam@result:'try'(
build_branches(
Leaf_pairs,
Capacity,
Store,
Key_codec
),
fun(Root_loc) ->
{ok,
{non_empty,
Root_loc,
Total_count,
0,
Capacity}}
end
)
end end)
end
)
end
).
-file("src/trove/internal/btree.gleam", 749).
?DOC(false).
-spec write_values(
list({HXK, HXL}),
trove@internal@store:store(),
trove@codec:codec(HXL)
) -> {ok, list({HXK, integer()})} | {error, btree_error()}.
write_values(Entries, Store, Value_codec) ->
gleam@list:try_map(
Entries,
fun(Entry) ->
{Key, Value} = Entry,
gleam@result:'try'(
write_data_node(Store, {value, Value}, Value_codec),
fun(Loc) -> {ok, {Key, Loc}} end
)
end
).
-file("src/trove/internal/btree.gleam", 837).
?DOC(false).
-spec write_tombstone(trove@internal@store:store()) -> {ok, integer()} |
{error, btree_error()}.
write_tombstone(Store) ->
write_node(Store, trove@internal@btree@node:encode_tombstone()).
-file("src/trove/internal/btree.gleam", 881).
?DOC(false).
-spec collapse_root(
trove@internal@store:store(),
integer(),
trove@codec:codec(any())
) -> {ok, integer()} | {error, btree_error()}.
collapse_root(Store, Location, Key_codec) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
{ok, {branch, Children}} ->
case non_empty_list:rest(Children) of
[] ->
{_, Child_loc} = non_empty_list:first(Children),
collapse_root(Store, Child_loc, Key_codec);
_ ->
{ok, Location}
end;
{ok, {leaf, _}} ->
{ok, Location};
{error, nil} ->
{error,
{decode_error,
<<"node during root collapse at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}}
end
end
).
-file("src/trove/internal/btree.gleam", 922).
?DOC(false).
-spec delete_from_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({HZY, integer()}),
HZY,
trove@codec:codec(HZY),
fun((HZY, HZY) -> gleam@order:order())
) -> {ok, delete_result(HZY)} | {error, btree_error()}.
delete_from_leaf(Store, Children, Key, Key_codec, Compare) ->
Children_list = non_empty_list:to_list(Children),
{Rev_children, Found} = gleam@list:fold(
Children_list,
{[], false},
fun(Acc, Entry) -> case Compare(erlang:element(1, Entry), Key) =:= eq of
true ->
{erlang:element(1, Acc), true};
false ->
{[Entry | erlang:element(1, Acc)], erlang:element(2, Acc)}
end end
),
case Found of
false ->
{ok, delete_not_found};
true ->
case lists:reverse(Rev_children) of
[] ->
{ok, delete_empty};
[{Min_key, _} | _] = New_children ->
Nel@1 = case non_empty_list:from_list(New_children) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"delete_from_leaf"/utf8>>,
line => 943,
value => _assert_fail,
start => 26421,
'end' => 26480,
pattern_start => 26432,
pattern_end => 26439})
end,
gleam@result:'try'(
write_tree_node(Store, {leaf, Nel@1}, Key_codec),
fun(Loc) ->
{ok, {deleted_node, Loc, {some, Min_key}}}
end
)
end
end.
-file("src/trove/internal/btree.gleam", 1007).
?DOC(false).
-spec resolve_child_key(
non_empty_list:non_empty_list({IAK, integer()}),
integer(),
gleam@option:option(IAK)
) -> {ok, IAK} | {error, btree_error()}.
resolve_child_key(Children, Child_index, New_min) ->
_pipe = New_min,
_pipe@1 = gleam@option:to_result(_pipe, nil),
_pipe@3 = gleam@result:lazy_or(
_pipe@1,
fun() ->
_pipe@2 = gleam@list:first(
gleam@list:drop(non_empty_list:to_list(Children), Child_index)
),
gleam@result:map(_pipe@2, fun gleam@pair:first/1)
end
),
gleam@result:replace_error(
_pipe@3,
{validation_error, <<"invalid child index"/utf8>>}
).
-file("src/trove/internal/btree.gleam", 1021).
?DOC(false).
-spec remove_child(non_empty_list:non_empty_list({IAP, integer()}), integer()) -> list({IAP,
integer()}).
remove_child(Children, Index) ->
Children_list = non_empty_list:to_list(Children),
lists:append(
gleam@list:take(Children_list, Index),
gleam@list:drop(Children_list, Index + 1)
).
-file("src/trove/internal/btree.gleam", 1121).
?DOC(false).
-spec replace_child_value(
non_empty_list:non_empty_list({IBM, integer()}),
IBM,
integer(),
fun((IBM, IBM) -> gleam@order:order())
) -> {boolean(), non_empty_list:non_empty_list({IBM, integer()})}.
replace_child_value(Children, Key, New_loc, Compare) ->
Fold_result = non_empty_list:fold(
Children,
{false, []},
fun(Acc, Entry) -> case Compare(erlang:element(1, Entry), Key) =:= eq of
true ->
{true,
[{erlang:element(1, Entry), New_loc} |
erlang:element(2, Acc)]};
false ->
{erlang:element(1, Acc), [Entry | erlang:element(2, Acc)]}
end end
),
Nel@1 = case non_empty_list:from_list(
lists:reverse(erlang:element(2, Fold_result))
) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"replace_child_value"/utf8>>,
line => 1138,
value => _assert_fail,
start => 31814,
'end' => 31888,
pattern_start => 31825,
pattern_end => 31832})
end,
{erlang:element(1, Fold_result), Nel@1}.
-file("src/trove/internal/btree.gleam", 1093).
?DOC(false).
-spec mark_deleted_in_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({IBG, integer()}),
IBG,
trove@codec:codec(IBG),
fun((IBG, IBG) -> gleam@order:order())
) -> {ok, mark_deleted_result(IBG)} | {error, btree_error()}.
mark_deleted_in_leaf(Store, Children, Key, Key_codec, Compare) ->
case non_empty_list:any(
Children,
fun(Entry) -> Compare(erlang:element(1, Entry), Key) =:= eq end
) of
false ->
{ok, mark_not_found};
true ->
gleam@result:'try'(
write_tombstone(Store),
fun(Tombstone_loc) ->
{_, New_children} = replace_child_value(
Children,
Key,
Tombstone_loc,
Compare
),
{Min_key, _} = non_empty_list:first(New_children),
gleam@result:'try'(
write_tree_node(Store, {leaf, New_children}, Key_codec),
fun(Loc) -> {ok, {marked, Loc, {some, Min_key}}} end
)
end
)
end.
-file("src/trove/internal/btree.gleam", 1180).
?DOC(false).
-spec add_dirt(btree(IBV, IBW), integer()) -> btree(IBV, IBW).
add_dirt(Tree, Amount) ->
case Tree of
{empty, Dirt, Capacity} ->
{empty, Dirt + Amount, Capacity};
{non_empty, Root, Size, Dirt@1, Capacity@1} ->
{non_empty, Root, Size, Dirt@1 + Amount, Capacity@1}
end.
-file("src/trove/internal/btree.gleam", 1188).
?DOC(false).
-spec validate_sorted_unique(
list({ICB, any()}),
fun((ICB, ICB) -> gleam@order:order())
) -> {ok, nil} | {error, btree_error()}.
validate_sorted_unique(Entries, Compare) ->
case Entries of
[] ->
{ok, nil};
[_] ->
{ok, nil};
[{K1, _}, {K2, _} = Next | Rest] ->
case Compare(K1, K2) of
lt ->
validate_sorted_unique([Next | Rest], Compare);
eq ->
{error,
{validation_error,
<<"duplicate key in bulk load input"/utf8>>}};
gt ->
{error,
{validation_error,
<<"unsorted key in bulk load input"/utf8>>}}
end
end.
-file("src/trove/internal/btree.gleam", 616).
?DOC(false).
-spec load(
list({HWS, HWT}),
trove@internal@store:store(),
integer(),
trove@codec:codec(HWS),
trove@codec:codec(HWT),
fun((HWS, HWS) -> gleam@order:order())
) -> {ok, btree(HWS, HWT)} | {error, btree_error()}.
load(Entries, Store, Capacity, Key_codec, Value_codec, Compare) ->
gleam@bool:guard(
Capacity < 2,
{error, {validation_error, <<"capacity must be at least 2"/utf8>>}},
fun() -> case Entries of
[] ->
{ok, {empty, 0, Capacity}};
[_ | _] ->
gleam@result:'try'(
validate_sorted_unique(Entries, Compare),
fun(_use0) ->
nil = _use0,
Entry_count = erlang:length(Entries),
gleam@result:'try'(
write_values(Entries, Store, Value_codec),
fun(Value_pairs) ->
gleam@result:'try'(
write_level(
Value_pairs,
Capacity,
Store,
Key_codec,
fun(Field@0) -> {leaf, Field@0} end
),
fun(Leaf_pairs) ->
gleam@result:'try'(
build_branches(
Leaf_pairs,
Capacity,
Store,
Key_codec
),
fun(Root_loc) ->
{ok,
{non_empty,
Root_loc,
Entry_count,
0,
Capacity}}
end
)
end
)
end
)
end
)
end end
).
-file("src/trove/internal/btree.gleam", 1142).
?DOC(false).
-spec mark_deleted_in_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({IBP, integer()}),
IBP,
trove@codec:codec(IBP),
fun((IBP, IBP) -> gleam@order:order())
) -> {ok, mark_deleted_result(IBP)} | {error, btree_error()}.
mark_deleted_in_branch(Store, Children, Key, Key_codec, Compare) ->
{Child_index, Child_loc} = find_branch_child_index(Children, Key, Compare),
gleam@result:'try'(
do_mark_deleted(Store, Child_loc, Key, Key_codec, Compare),
fun(Child_result) -> case Child_result of
mark_not_found ->
{ok, mark_not_found};
{marked, New_child_loc, New_min} ->
gleam@result:'try'(
resolve_child_key(Children, Child_index, New_min),
fun(Existing_key) ->
New_children = replace_child(
Children,
Child_index,
Existing_key,
New_child_loc
),
{Branch_min, _} = non_empty_list:first(New_children),
gleam@result:'try'(
write_tree_node(
Store,
{branch, New_children},
Key_codec
),
fun(Loc) ->
{ok, {marked, Loc, {some, Branch_min}}}
end
)
end
)
end end
).
-file("src/trove/internal/btree.gleam", 1075).
?DOC(false).
-spec do_mark_deleted(
trove@internal@store:store(),
integer(),
IBB,
trove@codec:codec(IBB),
fun((IBB, IBB) -> gleam@order:order())
) -> {ok, mark_deleted_result(IBB)} | {error, btree_error()}.
do_mark_deleted(Store, Location, Key, Key_codec, Compare) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
{error, nil} ->
{error,
{decode_error,
<<"tree node at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}};
{ok, {leaf, Children}} ->
mark_deleted_in_leaf(
Store,
Children,
Key,
Key_codec,
Compare
);
{ok, {branch, Children@1}} ->
mark_deleted_in_branch(
Store,
Children@1,
Key,
Key_codec,
Compare
)
end
end
).
-file("src/trove/internal/btree.gleam", 1039).
?DOC(false).
-spec mark_deleted(
btree(IAS, IAT),
trove@internal@store:store(),
IAS,
trove@codec:codec(IAS),
fun((IAS, IAS) -> gleam@order:order())
) -> {ok, btree(IAS, IAT)} | {error, btree_error()}.
mark_deleted(Tree, Store, Key, Key_codec, Compare) ->
case Tree of
{empty, _, _} ->
{ok, Tree};
{non_empty, Root_loc, Tree_size, Tree_dirt, Tree_capacity} ->
gleam@result:'try'(
do_mark_deleted(Store, Root_loc, Key, Key_codec, Compare),
fun(Mark_result) -> case Mark_result of
mark_not_found ->
{ok, Tree};
{marked, New_loc, _} ->
{ok,
{non_empty,
New_loc,
Tree_size - 1,
Tree_dirt + 1,
Tree_capacity}}
end end
)
end.
-file("src/trove/internal/btree.gleam", 955).
?DOC(false).
-spec delete_from_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({IAE, integer()}),
IAE,
trove@codec:codec(IAE),
fun((IAE, IAE) -> gleam@order:order())
) -> {ok, delete_result(IAE)} | {error, btree_error()}.
delete_from_branch(Store, Children, Key, Key_codec, Compare) ->
{Child_index, Child_loc} = find_branch_child_index(Children, Key, Compare),
gleam@result:'try'(
do_delete(Store, Child_loc, Key, Key_codec, Compare),
fun(Child_result) -> case Child_result of
delete_not_found ->
{ok, delete_not_found};
delete_empty ->
New_children = remove_child(Children, Child_index),
case New_children of
[] ->
{ok, delete_empty};
[{Min_key, _} | _] ->
Nel@1 = case non_empty_list:from_list(New_children) of
{ok, Nel} -> Nel;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"delete_from_branch"/utf8>>,
line => 978,
value => _assert_fail,
start => 27348,
'end' => 27407,
pattern_start => 27359,
pattern_end => 27366})
end,
gleam@result:'try'(
write_tree_node(
Store,
{branch, Nel@1},
Key_codec
),
fun(Loc) ->
{ok, {deleted_node, Loc, {some, Min_key}}}
end
)
end;
{deleted_node, New_child_loc, New_min} ->
gleam@result:'try'(
resolve_child_key(Children, Child_index, New_min),
fun(Existing_key) ->
New_children@1 = replace_child(
Children,
Child_index,
Existing_key,
New_child_loc
),
{Branch_min, _} = non_empty_list:first(
New_children@1
),
gleam@result:'try'(
write_tree_node(
Store,
{branch, New_children@1},
Key_codec
),
fun(Loc@1) ->
{ok,
{deleted_node,
Loc@1,
{some, Branch_min}}}
end
)
end
)
end end
).
-file("src/trove/internal/btree.gleam", 904).
?DOC(false).
-spec do_delete(
trove@internal@store:store(),
integer(),
HZT,
trove@codec:codec(HZT),
fun((HZT, HZT) -> gleam@order:order())
) -> {ok, delete_result(HZT)} | {error, btree_error()}.
do_delete(Store, Location, Key, Key_codec, Compare) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
{error, nil} ->
{error,
{decode_error,
<<"tree node at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}};
{ok, {leaf, Children}} ->
delete_from_leaf(Store, Children, Key, Key_codec, Compare);
{ok, {branch, Children@1}} ->
delete_from_branch(
Store,
Children@1,
Key,
Key_codec,
Compare
)
end
end
).
-file("src/trove/internal/btree.gleam", 842).
?DOC(false).
-spec delete(
btree(HZG, HZH),
trove@internal@store:store(),
HZG,
trove@codec:codec(HZG),
fun((HZG, HZG) -> gleam@order:order())
) -> {ok, btree(HZG, HZH)} | {error, btree_error()}.
delete(Tree, Store, Key, Key_codec, Compare) ->
case Tree of
{empty, _, _} ->
{ok, Tree};
{non_empty, Root_loc, Tree_size, Tree_dirt, Tree_capacity} ->
gleam@result:'try'(
do_delete(Store, Root_loc, Key, Key_codec, Compare),
fun(Delete_result) -> case Delete_result of
delete_not_found ->
{ok, Tree};
delete_empty ->
{ok, {empty, Tree_dirt + 1, Tree_capacity}};
{deleted_node, New_loc, _} ->
gleam@result:'try'(
collapse_root(Store, New_loc, Key_codec),
fun(Final_root) ->
{ok,
{non_empty,
Final_root,
Tree_size - 1,
Tree_dirt + 1,
Tree_capacity}}
end
)
end end
)
end.
-file("src/trove/internal/btree.gleam", 414).
?DOC(false).
-spec insert_into_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({HVS, integer()}),
HVS,
integer(),
integer(),
trove@codec:codec(HVS),
fun((HVS, HVS) -> gleam@order:order())
) -> {ok, insert_result(HVS)} | {error, btree_error()}.
insert_into_branch(
Store,
Children,
Key,
Value_loc,
Capacity,
Key_codec,
Compare
) ->
{Child_index, Child_loc} = find_branch_child_index(Children, Key, Compare),
gleam@result:'try'(
do_insert(
Store,
Child_loc,
Key,
Value_loc,
Capacity,
Key_codec,
Compare
),
fun(Child_result) ->
{insert_result, Child_outcome, Is_new} = Child_result,
case Child_outcome of
{single, New_child_loc, New_min} ->
New_children = replace_child(
Children,
Child_index,
New_min,
New_child_loc
),
{Branch_min, _} = non_empty_list:first(New_children),
gleam@result:'try'(
write_tree_node(
Store,
{branch, New_children},
Key_codec
),
fun(Loc) ->
{ok,
{insert_result,
{single, Loc, Branch_min},
Is_new}}
end
);
{split, Left_loc, Left_min, Right_min, Right_loc} ->
New_children@1 = splice_split(
Children,
Child_index,
Left_min,
Left_loc,
Right_min,
Right_loc
),
{Branch_min@1, _} = non_empty_list:first(New_children@1),
Count = non_empty_list:length(New_children@1),
gleam@bool:lazy_guard(
Count =< Capacity,
fun() ->
gleam@result:'try'(
write_tree_node(
Store,
{branch, New_children@1},
Key_codec
),
fun(Loc@1) ->
{ok,
{insert_result,
{single, Loc@1, Branch_min@1},
Is_new}}
end
)
end,
fun() ->
{Left_children,
Branch_left_min,
Branch_right_min,
Right_children} = split_children(New_children@1),
gleam@result:'try'(
write_tree_node(
Store,
{branch, Left_children},
Key_codec
),
fun(New_left) ->
gleam@result:'try'(
write_tree_node(
Store,
{branch, Right_children},
Key_codec
),
fun(New_right) ->
{ok,
{insert_result,
{split,
New_left,
Branch_left_min,
Branch_right_min,
New_right},
Is_new}}
end
)
end
)
end
)
end
end
).
-file("src/trove/internal/btree.gleam", 342).
?DOC(false).
-spec do_insert(
trove@internal@store:store(),
integer(),
HVH,
integer(),
integer(),
trove@codec:codec(HVH),
fun((HVH, HVH) -> gleam@order:order())
) -> {ok, insert_result(HVH)} | {error, btree_error()}.
do_insert(Store, Location, Key, Value_loc, Capacity, Key_codec, Compare) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
{error, nil} ->
{error,
{decode_error,
<<"tree node at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}};
{ok, {leaf, Children}} ->
insert_into_leaf(
Store,
Children,
Key,
Value_loc,
Capacity,
Key_codec,
Compare
);
{ok, {branch, Children@1}} ->
insert_into_branch(
Store,
Children@1,
Key,
Value_loc,
Capacity,
Key_codec,
Compare
)
end
end
).
-file("src/trove/internal/btree.gleam", 270).
?DOC(false).
-spec insert(
btree(HUX, HUY),
trove@internal@store:store(),
HUX,
HUY,
trove@codec:codec(HUX),
trove@codec:codec(HUY),
fun((HUX, HUX) -> gleam@order:order())
) -> {ok, btree(HUX, HUY)} | {error, btree_error()}.
insert(Tree, Store, Key, Value, Key_codec, Value_codec, Compare) ->
Tree_dirt = dirt(Tree),
Tree_capacity = capacity(Tree),
gleam@result:'try'(
write_data_node(Store, {value, Value}, Value_codec),
fun(Value_loc) -> case Tree of
{empty, _, _} ->
gleam@result:'try'(
write_tree_node(
Store,
{leaf, non_empty_list:single({Key, Value_loc})},
Key_codec
),
fun(Leaf_loc) ->
{ok,
{non_empty,
Leaf_loc,
1,
Tree_dirt,
Tree_capacity}}
end
);
{non_empty, Root_loc, Tree_size, _, _} ->
gleam@result:'try'(
do_insert(
Store,
Root_loc,
Key,
Value_loc,
Tree_capacity,
Key_codec,
Compare
),
fun(Insert_result) ->
{insert_result, Outcome, Is_new} = Insert_result,
New_root_loc = case Outcome of
{single, Loc, _} ->
{ok, Loc};
{split,
Left_loc,
Left_min,
Right_min,
Right_loc} ->
write_tree_node(
Store,
{branch,
non_empty_list:new(
{Left_min, Left_loc},
[{Right_min, Right_loc}]
)},
Key_codec
)
end,
New_size = case Is_new of
true ->
Tree_size + 1;
false ->
Tree_size
end,
gleam@result:'try'(
New_root_loc,
fun(Root) ->
{ok,
{non_empty,
Root,
New_size,
case Is_new of
true ->
Tree_dirt;
false ->
Tree_dirt + 1
end,
Tree_capacity}}
end
)
end
)
end end
).
-file("src/trove/internal/btree.gleam", 256).
?DOC(false).
-spec lookup_in_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({HUP, integer()}),
HUP,
trove@codec:codec(HUP),
trove@codec:codec(HUS),
fun((HUP, HUP) -> gleam@order:order())
) -> {ok, gleam@option:option(HUS)} | {error, btree_error()}.
lookup_in_branch(Store, Children, Key, Key_codec, Value_codec, Compare) ->
{_, Child_loc} = find_branch_child_index(Children, Key, Compare),
lookup_tree_at(Store, Child_loc, Key, Key_codec, Value_codec, Compare).
-file("src/trove/internal/btree.gleam", 206).
?DOC(false).
-spec lookup_tree_at(
trove@internal@store:store(),
integer(),
HTW,
trove@codec:codec(HTW),
trove@codec:codec(HTY),
fun((HTW, HTW) -> gleam@order:order())
) -> {ok, gleam@option:option(HTY)} | {error, btree_error()}.
lookup_tree_at(Store, Location, Key, Key_codec, Value_codec, Compare) ->
gleam@result:'try'(
read_node(Store, Location),
fun(Data) ->
case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
{ok, {leaf, Children}} ->
lookup_in_leaf(Store, Children, Key, Value_codec, Compare);
{ok, {branch, Children@1}} ->
lookup_in_branch(
Store,
Children@1,
Key,
Key_codec,
Value_codec,
Compare
);
{error, nil} ->
{error,
{decode_error,
<<"tree node at offset "/utf8,
(erlang:integer_to_binary(Location))/binary>>}}
end
end
).
-file("src/trove/internal/btree.gleam", 144).
?DOC(false).
-spec lookup(
btree(HTC, HTD),
trove@internal@store:store(),
HTC,
trove@codec:codec(HTC),
trove@codec:codec(HTD),
fun((HTC, HTC) -> gleam@order:order())
) -> {ok, gleam@option:option(HTD)} | {error, btree_error()}.
lookup(Tree, Store, Key, Key_codec, Value_codec, Compare) ->
case Tree of
{empty, _, _} ->
{ok, none};
{non_empty, Location, _, _, _} ->
lookup_tree_at(
Store,
Location,
Key,
Key_codec,
Value_codec,
Compare
)
end.