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([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 error() :: {store_error, trove@internal@store:error()} |
{decode_error, binary()} |
{validation_error, binary()}.
-type insert_result(HWF) :: {insert_result, insert_outcome(HWF), boolean()}.
-type insert_outcome(HWG) :: {single, integer(), HWG} |
{split, integer(), HWG, HWG, integer()}.
-type delete_result(HWH) :: {deleted_node, integer(), HWH} |
delete_not_found |
delete_empty.
-type mark_deleted_result(HWI) :: {marked, integer(), HWI} | mark_not_found.
-opaque btree(HWJ, HWK) :: {empty, integer(), integer()} |
{non_empty, integer(), integer(), integer(), integer()} |
{gleam_phantom, HWJ, HWK}.
-file("src/trove/internal/btree.gleam", 21).
?DOC(false).
-spec error_to_string(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", 29).
?DOC(false).
-spec read_node(trove@internal@store:store(), integer()) -> {ok, bitstring()} |
{error, 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", 34).
?DOC(false).
-spec write_node(trove@internal@store:store(), bitstring()) -> {ok, integer()} |
{error, 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", 70).
?DOC(false).
-spec new() -> btree(any(), any()).
new() ->
{empty, 0, 32}.
-file("src/trove/internal/btree.gleam", 75).
?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 => 76,
value => _assert_fail,
start => 2029,
'end' => 2060,
pattern_start => 2040,
pattern_end => 2044})
end,
{empty, 0, Capacity}.
-file("src/trove/internal/btree.gleam", 82).
?DOC(false).
-spec from_header(
gleam@option:option(integer()),
integer(),
integer(),
integer()
) -> {ok, btree(any(), any())} | {error, 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", 110).
?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", 118).
?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", 126).
?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", 134).
?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", 224).
?DOC(false).
-spec resolve_data(
trove@internal@store:store(),
integer(),
trove@codec:codec(HYW)
) -> {ok, gleam@option:option(HYW)} | {error, 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", 238).
?DOC(false).
-spec lookup_in_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({HZB, integer()}),
HZB,
trove@codec:codec(HZD),
fun((HZB, HZB) -> gleam@order:order())
) -> {ok, gleam@option:option(HZD)} | {error, 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", 508).
?DOC(false).
-spec do_insert_into_sorted(
list({IAU, integer()}),
IAU,
integer(),
fun((IAU, IAU) -> gleam@order:order())
) -> {list({IAU, 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", 486).
?DOC(false).
-spec insert_into_sorted(
non_empty_list:non_empty_list({IAR, integer()}),
IAR,
integer(),
fun((IAR, IAR) -> gleam@order:order())
) -> {non_empty_list:non_empty_list({IAR, integer()}), boolean()}.
insert_into_sorted(Children, Key, Location, Compare) ->
{Child_key, Child_loc} = non_empty_list:first(Children),
Rest = non_empty_list:rest(Children),
case Compare(Key, Child_key) of
lt ->
{non_empty_list:new(
{Key, Location},
[{Child_key, Child_loc} | Rest]
),
true};
eq ->
{non_empty_list:new({Key, Location}, Rest), false};
gt ->
{New_rest, Is_new} = do_insert_into_sorted(
Rest,
Key,
Location,
Compare
),
{non_empty_list:new({Child_key, Child_loc}, New_rest), Is_new}
end.
-file("src/trove/internal/btree.gleam", 529).
?DOC(false).
-spec split_children(non_empty_list:non_empty_list({IAX, integer()})) -> {non_empty_list:non_empty_list({IAX,
integer()}),
IAX,
IAX,
non_empty_list:non_empty_list({IAX, integer()})}.
split_children(Children) ->
Count = non_empty_list:length(Children),
Mid = Count div 2,
{Left, Right} = gleam@list:split(non_empty_list:to_list(Children), Mid),
case {Left, Right} of
{[Lh | Lt], [Rh | Rt]} ->
{Left_min, _} = Lh,
{Right_min, _} = Rh,
{non_empty_list:new(Lh, Lt),
Left_min,
Right_min,
non_empty_list:new(Rh, Rt)};
{_, _} ->
erlang:error(#{gleam_error => panic,
message => <<"split_children: caller invariant (length > capacity >= 2) violated"/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"trove/internal/btree"/utf8>>,
function => <<"split_children"/utf8>>,
line => 549})
end.
-file("src/trove/internal/btree.gleam", 568).
?DOC(false).
-spec do_find_branch_child_index(
list({IBD, integer()}),
IBD,
fun((IBD, IBD) -> 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", 553).
?DOC(false).
-spec find_branch_child_index(
non_empty_list:non_empty_list({IBB, integer()}),
IBB,
fun((IBB, IBB) -> 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", 174).
?DOC(false).
-spec contains_at(
trove@internal@store:store(),
integer(),
HYL,
trove@codec:codec(HYL),
fun((HYL, HYL) -> gleam@order:order())
) -> {ok, boolean()} | {error, 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", 160).
?DOC(false).
-spec contains(
btree(HYE, any()),
trove@internal@store:store(),
HYE,
trove@codec:codec(HYE),
fun((HYE, HYE) -> gleam@order:order())
) -> {ok, boolean()} | {error, 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", 615).
?DOC(false).
-spec nel_splice_one(list(IBL), IBL, list(IBL)) -> non_empty_list:non_empty_list(IBL).
nel_splice_one(Before, Middle, After) ->
case Before of
[] ->
non_empty_list:new(Middle, After);
[H | T] ->
non_empty_list:new(H, lists:append(T, [Middle | After]))
end.
-file("src/trove/internal/btree.gleam", 589).
?DOC(false).
-spec replace_child(
non_empty_list:non_empty_list({IBF, integer()}),
integer(),
IBF,
integer()
) -> non_empty_list:non_empty_list({IBF, 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),
nel_splice_one(Before, {New_key, New_loc}, After).
-file("src/trove/internal/btree.gleam", 622).
?DOC(false).
-spec nel_splice_two(list(IBP), IBP, IBP, list(IBP)) -> non_empty_list:non_empty_list(IBP).
nel_splice_two(Before, First, Second, After) ->
case Before of
[] ->
non_empty_list:new(First, [Second | After]);
[H | T] ->
non_empty_list:new(H, lists:append(T, [First, Second | After]))
end.
-file("src/trove/internal/btree.gleam", 601).
?DOC(false).
-spec splice_split(
non_empty_list:non_empty_list({IBI, integer()}),
integer(),
IBI,
integer(),
IBI,
integer()
) -> non_empty_list:non_empty_list({IBI, 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),
nel_splice_two(Before, {Left_key, Left_loc}, {Right_key, Right_loc}, After).
-file("src/trove/internal/btree.gleam", 816).
?DOC(false).
-spec chunk_non_empty(non_empty_list:non_empty_list(IDA), integer()) -> non_empty_list:non_empty_list(non_empty_list:non_empty_list(IDA)).
chunk_non_empty(Items, Capacity) ->
First = non_empty_list:first(Items),
Rest = non_empty_list:rest(Items),
Head_rest = gleam@list:take(Rest, Capacity - 1),
Tail = gleam@list:drop(Rest, Capacity - 1),
Head_chunk = non_empty_list:new(First, Head_rest),
case Tail of
[] ->
non_empty_list:single(Head_chunk);
[H | T] ->
non_empty_list:prepend(
chunk_non_empty(non_empty_list:new(H, T), Capacity),
Head_chunk
)
end.
-file("src/trove/internal/btree.gleam", 870).
?DOC(false).
-spec write_tree_node(
trove@internal@store:store(),
trove@internal@btree@node:tree_node(IDQ),
trove@codec:codec(IDQ)
) -> {ok, integer()} | {error, 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", 377).
?DOC(false).
-spec insert_into_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({IAF, integer()}),
IAF,
integer(),
integer(),
trove@codec:codec(IAF),
fun((IAF, IAF) -> gleam@order:order())
) -> {ok, insert_result(IAF)} | {error, 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", 835).
?DOC(false).
-spec flush_chunk(
non_empty_list:non_empty_list({IDE, integer()}),
trove@internal@store:store(),
trove@codec:codec(IDE),
fun((non_empty_list:non_empty_list({IDE, integer()})) -> trove@internal@btree@node:tree_node(IDE))
) -> {ok, {IDE, integer()}} | {error, error()}.
flush_chunk(Children, Store, Key_codec, Make_node) ->
{First_key, _} = non_empty_list:first(Children),
gleam@result:'try'(
write_tree_node(Store, Make_node(Children), Key_codec),
fun(Loc) -> {ok, {First_key, Loc}} end
).
-file("src/trove/internal/btree.gleam", 804).
?DOC(false).
-spec write_level(
non_empty_list:non_empty_list({ICS, integer()}),
integer(),
trove@internal@store:store(),
trove@codec:codec(ICS),
fun((non_empty_list:non_empty_list({ICS, integer()})) -> trove@internal@btree@node:tree_node(ICS))
) -> {ok, non_empty_list:non_empty_list({ICS, integer()})} | {error, error()}.
write_level(Pairs, Capacity, Store, Key_codec, Make_node) ->
_pipe = chunk_non_empty(Pairs, Capacity),
_pipe@1 = non_empty_list:map(
_pipe,
fun(_capture) -> flush_chunk(_capture, Store, Key_codec, Make_node) end
),
non_empty_list:all(_pipe@1).
-file("src/trove/internal/btree.gleam", 846).
?DOC(false).
-spec build_branches(
non_empty_list:non_empty_list({IDL, integer()}),
integer(),
trove@internal@store:store(),
trove@codec:codec(IDL)
) -> {ok, integer()} | {error, error()}.
build_branches(Pairs, Capacity, Store, Key_codec) ->
case non_empty_list:rest(Pairs) of
[] ->
{_, Loc} = non_empty_list:first(Pairs),
{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", 881).
?DOC(false).
-spec write_data_node(
trove@internal@store:store(),
trove@internal@btree@node:data_node(IDV),
trove@codec:codec(IDV)
) -> {ok, integer()} | {error, 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", 684).
?DOC(false).
-spec load_from_yielder(
gleam@yielder:yielder({ICC, ICD}),
trove@internal@store:store(),
integer(),
trove@codec:codec(ICC),
trove@codec:codec(ICD),
fun((ICC, ICC) -> gleam@order:order())
) -> {ok, btree(ICC, ICD)} | {error, 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 = {none, [], 0, 0, none},
gleam@result:'try'(
gleam@yielder:try_fold(
Entries,
Initial,
fun(State, Entry) ->
{Chunk_opt, 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) ->
New_entry = {Key, Data_loc},
Chunk_with_entry = case Chunk_opt of
none ->
non_empty_list:single(New_entry);
{some, Nel} ->
non_empty_list:prepend(
Nel,
New_entry
)
end,
Chunk_size@1 = Chunk_size + 1,
Count@1 = Count + 1,
case Chunk_size@1 >= Capacity of
true ->
Leaf_children = non_empty_list:reverse(
Chunk_with_entry
),
gleam@result:'try'(
flush_chunk(
Leaf_children,
Store,
Key_codec,
fun(Field@0) -> {leaf, Field@0} end
),
fun(Leaf_pair) ->
{ok,
{none,
[Leaf_pair |
Leaves_rev],
0,
Count@1,
{some, Key}}}
end
);
false ->
{ok,
{{some, Chunk_with_entry},
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
none ->
{ok, lists:reverse(Leaf_pairs_rev)};
{some, Chunk} ->
Leaf_children@1 = non_empty_list:reverse(Chunk),
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 Leaf_pairs of
[] ->
{ok, {empty, 0, Capacity}};
[First_leaf | Rest_leaves] ->
Leaf_nel = non_empty_list:new(
First_leaf,
Rest_leaves
),
gleam@result:'try'(
build_branches(
Leaf_nel,
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", 791).
?DOC(false).
-spec write_values(
non_empty_list:non_empty_list({ICL, ICM}),
trove@internal@store:store(),
trove@codec:codec(ICM)
) -> {ok, non_empty_list:non_empty_list({ICL, integer()})} | {error, error()}.
write_values(Entries, Store, Value_codec) ->
_pipe@1 = non_empty_list:map(
Entries,
fun(Entry) ->
{Key, Value} = Entry,
_pipe = write_data_node(Store, {value, Value}, Value_codec),
gleam@result:map(_pipe, fun(Loc) -> {Key, Loc} end)
end
),
non_empty_list:all(_pipe@1).
-file("src/trove/internal/btree.gleam", 892).
?DOC(false).
-spec write_tombstone(trove@internal@store:store()) -> {ok, integer()} |
{error, error()}.
write_tombstone(Store) ->
write_node(Store, trove@internal@btree@node:encode_tombstone()).
-file("src/trove/internal/btree.gleam", 936).
?DOC(false).
-spec collapse_root(
trove@internal@store:store(),
integer(),
trove@codec:codec(any())
) -> {ok, integer()} | {error, 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", 977).
?DOC(false).
-spec delete_from_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({IEU, integer()}),
IEU,
trove@codec:codec(IEU),
fun((IEU, IEU) -> gleam@order:order())
) -> {ok, delete_result(IEU)} | {error, 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, _} = Head | Tail] ->
Nel = non_empty_list:new(Head, Tail),
gleam@result:'try'(
write_tree_node(Store, {leaf, Nel}, Key_codec),
fun(Loc) -> {ok, {deleted_node, Loc, Min_key}} end
)
end
end.
-file("src/trove/internal/btree.gleam", 1057).
?DOC(false).
-spec remove_child(non_empty_list:non_empty_list({IFG, integer()}), integer()) -> list({IFG,
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", 1156).
?DOC(false).
-spec replace_child_value(
non_empty_list:non_empty_list({IGD, integer()}),
IGD,
integer(),
fun((IGD, IGD) -> gleam@order:order())
) -> {boolean(), non_empty_list:non_empty_list({IGD, integer()})}.
replace_child_value(Children, Key, New_loc, Compare) ->
non_empty_list:map_fold(
Children,
false,
fun(Found, Entry) ->
case Compare(erlang:element(1, Entry), Key) =:= eq of
true ->
{true, {erlang:element(1, Entry), New_loc}};
false ->
{Found, Entry}
end
end
).
-file("src/trove/internal/btree.gleam", 1128).
?DOC(false).
-spec mark_deleted_in_leaf(
trove@internal@store:store(),
non_empty_list:non_empty_list({IFX, integer()}),
IFX,
trove@codec:codec(IFX),
fun((IFX, IFX) -> gleam@order:order())
) -> {ok, mark_deleted_result(IFX)} | {error, 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, Min_key}} end
)
end
)
end.
-file("src/trove/internal/btree.gleam", 1203).
?DOC(false).
-spec add_dirt(btree(IGM, IGN), integer()) -> btree(IGM, IGN).
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", 1211).
?DOC(false).
-spec validate_sorted_unique(
list({IGS, any()}),
fun((IGS, IGS) -> gleam@order:order())
) -> {ok, nil} | {error, 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", 635).
?DOC(false).
-spec load(
list({IBT, IBU}),
trove@internal@store:store(),
integer(),
trove@codec:codec(IBT),
trove@codec:codec(IBU),
fun((IBT, IBT) -> gleam@order:order())
) -> {ok, btree(IBT, IBU)} | {error, 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}};
[First | Rest] ->
gleam@result:'try'(
validate_sorted_unique(Entries, Compare),
fun(_use0) ->
nil = _use0,
Entry_count = erlang:length(Entries),
Entries_nel = non_empty_list:new(First, Rest),
gleam@result:'try'(
write_values(Entries_nel, 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", 1170).
?DOC(false).
-spec mark_deleted_in_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({IGG, integer()}),
IGG,
trove@codec:codec(IGG),
fun((IGG, IGG) -> gleam@order:order())
) -> {ok, mark_deleted_result(IGG)} | {error, 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} ->
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, {marked, Loc, Branch_min}} end
)
end end
).
-file("src/trove/internal/btree.gleam", 1110).
?DOC(false).
-spec do_mark_deleted(
trove@internal@store:store(),
integer(),
IFS,
trove@codec:codec(IFS),
fun((IFS, IFS) -> gleam@order:order())
) -> {ok, mark_deleted_result(IFS)} | {error, 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", 1074).
?DOC(false).
-spec mark_deleted(
btree(IFJ, IFK),
trove@internal@store:store(),
IFJ,
trove@codec:codec(IFJ),
fun((IFJ, IFJ) -> gleam@order:order())
) -> {ok, btree(IFJ, IFK)} | {error, 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", 1010).
?DOC(false).
-spec delete_from_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({IFA, integer()}),
IFA,
trove@codec:codec(IFA),
fun((IFA, IFA) -> gleam@order:order())
) -> {ok, delete_result(IFA)} | {error, 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, _} = Head | Tail] ->
Nel = non_empty_list:new(Head, Tail),
gleam@result:'try'(
write_tree_node(Store, {branch, Nel}, Key_codec),
fun(Loc) ->
{ok, {deleted_node, Loc, Min_key}}
end
)
end;
{deleted_node, New_child_loc, New_min} ->
New_children@1 = replace_child(
Children,
Child_index,
New_min,
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, Branch_min}}
end
)
end end
).
-file("src/trove/internal/btree.gleam", 959).
?DOC(false).
-spec do_delete(
trove@internal@store:store(),
integer(),
IEP,
trove@codec:codec(IEP),
fun((IEP, IEP) -> gleam@order:order())
) -> {ok, delete_result(IEP)} | {error, 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", 897).
?DOC(false).
-spec delete(
btree(IEC, IED),
trove@internal@store:store(),
IEC,
trove@codec:codec(IEC),
fun((IEC, IEC) -> gleam@order:order())
) -> {ok, btree(IEC, IED)} | {error, 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", 413).
?DOC(false).
-spec insert_into_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({IAL, integer()}),
IAL,
integer(),
integer(),
trove@codec:codec(IAL),
fun((IAL, IAL) -> gleam@order:order())
) -> {ok, insert_result(IAL)} | {error, 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", 341).
?DOC(false).
-spec do_insert(
trove@internal@store:store(),
integer(),
IAA,
integer(),
integer(),
trove@codec:codec(IAA),
fun((IAA, IAA) -> gleam@order:order())
) -> {ok, insert_result(IAA)} | {error, 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", 269).
?DOC(false).
-spec insert(
btree(HZQ, HZR),
trove@internal@store:store(),
HZQ,
HZR,
trove@codec:codec(HZQ),
trove@codec:codec(HZR),
fun((HZQ, HZQ) -> gleam@order:order())
) -> {ok, btree(HZQ, HZR)} | {error, 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", 255).
?DOC(false).
-spec lookup_in_branch(
trove@internal@store:store(),
non_empty_list:non_empty_list({HZI, integer()}),
HZI,
trove@codec:codec(HZI),
trove@codec:codec(HZL),
fun((HZI, HZI) -> gleam@order:order())
) -> {ok, gleam@option:option(HZL)} | {error, 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", 205).
?DOC(false).
-spec lookup_tree_at(
trove@internal@store:store(),
integer(),
HYP,
trove@codec:codec(HYP),
trove@codec:codec(HYR),
fun((HYP, HYP) -> gleam@order:order())
) -> {ok, gleam@option:option(HYR)} | {error, 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", 143).
?DOC(false).
-spec lookup(
btree(HXV, HXW),
trove@internal@store:store(),
HXV,
trove@codec:codec(HXV),
trove@codec:codec(HXW),
fun((HXV, HXV) -> gleam@order:order())
) -> {ok, gleam@option:option(HXW)} | {error, 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.