You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by da...@apache.org on 2020/07/24 18:53:20 UTC
[couchdb] 02/04: Fix ebtree collation
This is an automated email from the ASF dual-hosted git repository.
davisp pushed a commit to branch prototype/fdb-layer-ebtree-views
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit 8cc45a8c6d7446e114fd1b4df867996cf1d66fe2
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Fri Jul 24 11:04:26 2020 -0500
Fix ebtree collation
---
src/ebtree/src/ebtree.erl | 88 ++++++++++++++++++++++++++++++-----------------
1 file changed, 57 insertions(+), 31 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index cb5e805..353e466 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -505,8 +505,8 @@ split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
Parent1 = Parent0#node{
members =
- umerge(Tree, [{FirstLeftKey, LastLeftKey, LeftId, LeftReduction}],
- umerge(Tree, [{FirstRightKey, LastRightKey, RightId, RightReduction}],
+ umerge_members(Tree, [{FirstLeftKey, LastLeftKey, LeftId, LeftReduction}],
+ umerge_members(Tree, [{FirstRightKey, LastRightKey, RightId, RightReduction}],
lists:keydelete(Child#node.id, 3, Parent0#node.members)))
},
clear_node(Tx, Tree, Child),
@@ -532,9 +532,9 @@ update_next_neighbour(Tx, #tree{} = Tree, #node{} = Node) ->
insert_nonfull(Tx, #tree{} = Tree, #node{level = 0} = Node0, Key, Value) ->
Node1 = Node0#node{
- members = umerge(Tree, [{Key, Value}], Node0#node.members)
+ members = umerge_members(Tree, [{Key, Value}], Node0#node.members)
},
- set_node(Tx, Tree, Node1),
+ set_node(Tx, Tree, Node0, Node1),
reduce_node(Tree, Node1);
insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
@@ -557,13 +557,13 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
ChildId1 = Child1#node.id,
NewReduction = insert_nonfull(Tx, Tree, Child1, Key, Value),
{CurrentFirstKey, CurrentLastKey, ChildId1, _OldReduction} = lists:keyfind(ChildId1, 3, Node1#node.members),
- [NewFirstKey, _] = sort(Tree, [Key, CurrentFirstKey]),
- [_, NewLastKey] = sort(Tree, [Key, CurrentLastKey]),
+ [NewFirstKey, _] = sort_keys(Tree, [Key, CurrentFirstKey]),
+ [_, NewLastKey] = sort_keys(Tree, [Key, CurrentLastKey]),
Node2 = Node1#node{
members = lists:keyreplace(ChildId1, 3, Node1#node.members,
{NewFirstKey, NewLastKey, ChildId1, NewReduction})
},
- set_node(Tx, Tree, Node2),
+ set_node(Tx, Tree, Node0, Node2),
reduce_node(Tree, Node2).
@@ -584,7 +584,7 @@ delete(Db, #tree{} = Tree, Key) ->
clear_node(Tx, Tree, Root2),
set_node(Tx, Tree, Root2#node{id = ?NODE_ROOT_ID});
Root1 ->
- set_node(Tx, Tree, Root1)
+ set_node(Tx, Tree, Root0, Root1)
end
end),
Tree.
@@ -621,7 +621,7 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
Members1 = lists:keydelete(ChildId0, 3, Members0),
Members2 = lists:keydelete(Sibling#node.id, 3, Members1),
Members3 = lists:foldl(fun(N, Acc) ->
- umerge(Tree, [{first_key(N), last_key(N), N#node.id, reduce_node(Tree, N)}], Acc)
+ umerge_members(Tree, [{first_key(N), last_key(N), N#node.id, reduce_node(Tree, N)}], Acc)
end, Members2, NewNodes),
Parent1 = Parent0#node{
@@ -633,7 +633,7 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
set_nodes(Tx, Tree, NewNodes),
Parent1;
false ->
- set_node(Tx, Tree, Child1),
+ set_node(Tx, Tree, Child0, Child1),
{_OldFirstKey, _OldLastKey, ChildId0, _OldReduction} = lists:keyfind(ChildId0, 3, Parent0#node.members),
Parent0#node{
members = lists:keyreplace(ChildId0, 3, Parent0#node.members,
@@ -643,7 +643,7 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
- [Left, Right] = sort(Tree, [Node1, Node2]),
+ [Left, Right] = sort_nodes(Tree, [Node1, Node2]),
#node{
id = new_node_id(Tx, Tree),
@@ -655,7 +655,7 @@ merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = N
rebalance(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
- [Left0, Right0] = sort(Tree, [Node1, Node2]),
+ [Left0, Right0] = sort_nodes(Tree, [Node1, Node2]),
Members = lists:append(Left0#node.members, Right0#node.members),
{LeftMembers, RightMembers} = lists:split(length(Members) div 2, Members),
@@ -756,6 +756,13 @@ set_nodes(Tx, #tree{} = Tree, Nodes) ->
end, Nodes).
+set_node(_Tx, #tree{} = _Tree, #node{} = Same, #node{} = Same) ->
+ ok;
+
+set_node(Tx, #tree{} = Tree, #node{} = _From, #node{} = To) ->
+ set_node(Tx, Tree, To).
+
+
set_node(Tx, #tree{} = Tree, #node{} = Node) ->
validate_node(Tree, Node),
Key = node_key(Tree#tree.prefix, Node#node.id),
@@ -798,8 +805,8 @@ validate_node(#tree{} = Tree, #node{} = Node) ->
NumKeys = length(Node#node.members),
IsLeaf = Node#node.level =:= 0,
IsRoot = ?NODE_ROOT_ID == Node#node.id,
- OutOfOrder = Node#node.members /= sort(Tree, Node#node.members),
- Duplicates = Node#node.members /= usort(Tree, Node#node.members),
+ OutOfOrder = Node#node.members /= sort_members(Tree, Node#node.members),
+ Duplicates = Node#node.members /= usort_members(Tree, Node#node.members),
if
Node#node.id == undefined ->
erlang:error({node_without_id, Node});
@@ -908,32 +915,51 @@ less_than_or_equal(#tree{} = Tree, A, B) ->
CollateFun(A, B).
-umerge(#tree{} = Tree, List1, List2) ->
+umerge_members(#tree{} = Tree, List1, List2) ->
#tree{collate_fun = CollateFun} = Tree,
- lists:umerge(collation_wrapper_fun(CollateFun), List1, List2).
+ CollateWrapper = fun
+ ({K1, _V1}, {K2, _V2}) ->
+ CollateFun(K1, K2);
+ ({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) ->
+ CollateFun(L1, L2)
+ end,
+ lists:umerge(CollateWrapper, List1, List2).
-sort(#tree{} = Tree, List) ->
+sort_keys(#tree{} = Tree, List) ->
#tree{collate_fun = CollateFun} = Tree,
- lists:sort(collation_wrapper_fun(CollateFun), List).
+ lists:sort(CollateFun, List).
-usort(#tree{} = Tree, List) ->
+sort_nodes(#tree{} = Tree, List) ->
#tree{collate_fun = CollateFun} = Tree,
- lists:usort(collation_wrapper_fun(CollateFun), List).
+ CollateWrapper = fun
+ (#node{} = N1, #node{} = N2) ->
+ CollateFun(first_key(N1), first_key(N2))
+ end,
+ lists:sort(CollateWrapper, List).
-collation_wrapper_fun(CollateFun) ->
- fun
- (#node{} = N1, #node{} = N2) ->
- CollateFun(first_key(N1), first_key(N2));
+sort_members(#tree{} = Tree, List) ->
+ #tree{collate_fun = CollateFun} = Tree,
+ CollateWrapper = fun
({K1, _V1}, {K2, _V2}) ->
CollateFun(K1, K2);
({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) ->
- CollateFun(L1, L2);
- (K1, K2) ->
- CollateFun(K1, K2)
- end.
+ CollateFun(L1, L2)
+ end,
+ lists:sort(CollateWrapper, List).
+
+
+usort_members(#tree{} = Tree, List) ->
+ #tree{collate_fun = CollateFun} = Tree,
+ CollateWrapper = fun
+ ({K1, _V1}, {K2, _V2}) ->
+ CollateFun(K1, K2);
+ ({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) ->
+ CollateFun(L1, L2)
+ end,
+ lists:usort(CollateWrapper, List).
collate_raw(K1, K2) ->
@@ -1278,7 +1304,7 @@ custom_collation_range_test_() ->
lists:foldl(fun(Key, T) -> insert(Db, T, Key, Key + 1) end, Tree, Keys),
lists:foreach(
fun(_) ->
- [StartKey, EndKey] = sort(Tree, [rand:uniform(Max), rand:uniform(Max)]),
+ [StartKey, EndKey] = sort_keys(Tree, [rand:uniform(Max), rand:uniform(Max)]),
Seq = if
StartKey < EndKey ->
lists:seq(StartKey, EndKey);
@@ -1302,7 +1328,7 @@ custom_collation_reverse_range_test_() ->
lists:foldl(fun(Key, T) -> insert(Db, T, Key, Key + 1) end, Tree, Keys),
lists:foreach(
fun(_) ->
- [StartKey, EndKey] = sort(Tree, [rand:uniform(Max), rand:uniform(Max)]),
+ [StartKey, EndKey] = sort_keys(Tree, [rand:uniform(Max), rand:uniform(Max)]),
Seq = if
StartKey < EndKey ->
lists:seq(StartKey, EndKey);
@@ -1319,4 +1345,4 @@ custom_collation_reverse_range_test_() ->
msec(Native) ->
erlang:max(1, erlang:convert_time_unit(Native, native, millisecond)).
--endif.
+-endif.
\ No newline at end of file