You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by rn...@apache.org on 2020/07/24 16:28:26 UTC
[couchdb] branch prototype/fdb-layer-collation-bugs created (now
90158ea)
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a change to branch prototype/fdb-layer-collation-bugs
in repository https://gitbox.apache.org/repos/asf/couchdb.git.
at 90158ea separate out collation wrapper to avoid spurious comparisons
This branch includes the following new commits:
new 90158ea separate out collation wrapper to avoid spurious comparisons
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[couchdb] 01/01: separate out collation wrapper to avoid spurious
comparisons
Posted by rn...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a commit to branch prototype/fdb-layer-collation-bugs
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit 90158eaadc6a67dd2d522121f8257fc409c8168b
Author: Robert Newson <rn...@apache.org>
AuthorDate: Fri Jul 24 17:25:59 2020 +0100
separate out collation wrapper to avoid spurious comparisons
Ensure we only collate nodes, members and k/v's as intended.
---
src/ebtree/src/ebtree.erl | 71 ++++++++++++++++++++++++++++++-----------------
1 file changed, 45 insertions(+), 26 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 38a3289..f08e1e9 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,7 +532,7 @@ 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, Node0, Node1),
reduce_node(Tree, Node1);
@@ -557,8 +557,8 @@ 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})
@@ -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{
@@ -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),
@@ -805,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});
@@ -915,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) ->
@@ -1285,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);
@@ -1309,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);