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/08/06 12:03:07 UTC
[couchdb] branch prototype/fdb-layer-ebtree-enhance created (now
ff5b457)
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a change to branch prototype/fdb-layer-ebtree-enhance
in repository https://gitbox.apache.org/repos/asf/couchdb.git.
at ff5b457 Tighten expectation of members format by level
This branch includes the following new commits:
new fd199f3 Merge pull request #3060 from apache/prototype/fdb-layer-ebtree-speedy-tests
new ff5b457 Tighten expectation of members format by level
The 2 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] 02/02: Tighten expectation of members format by level
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-ebtree-enhance
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit ff5b4570196fd110cc650cbd996d9045f3fa41a8
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Aug 6 12:58:46 2020 +0100
Tighten expectation of members format by level
---
src/ebtree/src/ebtree.erl | 25 +++++++++++++------------
1 file changed, 13 insertions(+), 12 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 6a46ae8..c8cdb83 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -542,8 +542,8 @@ split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
Parent1 = Parent0#node{
members =
- umerge_members(Tree, [{FirstLeftKey, LastLeftKey, LeftId, LeftReduction}],
- umerge_members(Tree, [{FirstRightKey, LastRightKey, RightId, RightReduction}],
+ umerge_members(Tree, Parent0#node.level, [{FirstLeftKey, LastLeftKey, LeftId, LeftReduction}],
+ umerge_members(Tree, Parent0#node.level, [{FirstRightKey, LastRightKey, RightId, RightReduction}],
lists:keydelete(Child#node.id, 3, Parent0#node.members)))
},
clear_node(Tx, Tree, Child),
@@ -569,7 +569,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_members(Tree, [{Key, Value}], Node0#node.members)
+ members = umerge_members(Tree, 0, [{Key, Value}], Node0#node.members)
},
set_node(Tx, Tree, Node0, Node1),
reduce_node(Tree, Node1);
@@ -658,7 +658,8 @@ 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_members(Tree, [{first_key(N), last_key(N), N#node.id, reduce_node(Tree, N)}], Acc)
+ umerge_members(Tree, Parent0#node.level,
+ [{first_key(N), last_key(N), N#node.id, reduce_node(Tree, N)}], Acc)
end, Members2, NewNodes),
Parent1 = Parent0#node{
@@ -842,8 +843,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_members(Tree, Node#node.members),
- Duplicates = Node#node.members /= usort_members(Tree, Node#node.members),
+ OutOfOrder = Node#node.members /= sort_members(Tree, Node#node.level, Node#node.members),
+ Duplicates = Node#node.members /= usort_members(Tree, Node#node.level, Node#node.members),
if
Node#node.id == undefined ->
erlang:error({node_without_id, Node});
@@ -940,9 +941,9 @@ collate(#tree{} = Tree, A, B, Allowed) ->
lists:member(collate(Tree, A, B), Allowed).
-umerge_members(#tree{} = Tree, List1, List2) ->
+umerge_members(#tree{} = Tree, Level, List1, List2) ->
CollateWrapper = fun
- ({K1, _V1}, {K2, _V2}) ->
+ ({K1, _V1}, {K2, _V2}) when Level == 0 ->
collate(Tree, K1, K2, [lt, eq]);
({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) ->
collate(Tree, L1, L2, [lt, eq])
@@ -966,9 +967,9 @@ sort_nodes(#tree{} = Tree, List) ->
lists:sort(CollateWrapper, List).
-sort_members(#tree{} = Tree, List) ->
+sort_members(#tree{} = Tree, Level, List) ->
CollateWrapper = fun
- ({K1, _V1}, {K2, _V2}) ->
+ ({K1, _V1}, {K2, _V2}) when Level == 0 ->
collate(Tree, K1, K2, [lt, eq]);
({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) ->
collate(Tree, L1, L2, [lt, eq])
@@ -976,9 +977,9 @@ sort_members(#tree{} = Tree, List) ->
lists:sort(CollateWrapper, List).
-usort_members(#tree{} = Tree, List) ->
+usort_members(#tree{} = Tree, Level, List) ->
CollateWrapper = fun
- ({K1, _V1}, {K2, _V2}) ->
+ ({K1, _V1}, {K2, _V2}) when Level == 0 ->
collate(Tree, K1, K2, [lt, eq]);
({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) ->
collate(Tree, L1, L2, [lt, eq])
[couchdb] 01/02: Merge pull request #3060 from
apache/prototype/fdb-layer-ebtree-speedy-tests
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-ebtree-enhance
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit fd199f3b808b46f1b11220e63e58654357df7960
Merge: 29d6498 31b467c
Author: Robert Newson <rn...@apache.org>
AuthorDate: Wed Aug 5 21:12:39 2020 +0100
Merge pull request #3060 from apache/prototype/fdb-layer-ebtree-speedy-tests
Speed up ebtree test suite without losing coverage
src/ebtree/src/ebtree.erl | 106 +++++++++++++++++++++++++++++-----------------
1 file changed, 66 insertions(+), 40 deletions(-)
diff --cc src/ebtree/src/ebtree.erl
index 15a21a6,6a4f4a8..6a46ae8
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@@ -1110,6 -1110,6 +1110,25 @@@ collate_validation_test() -
?assertError(invalid_collation_result, collate(Tree, 1, 2)).
++order_is_preserved_test() ->
++ Db = erlfdb_util:get_test_db([empty]),
++ open(Db, <<1,2,3>>, 4),
++ Tree = open(Db, <<1,2,3>>, 8),
++ ?assertEqual(4, Tree#tree.max).
++
++
++min_not_allowed_test() ->
++ Db = erlfdb_util:get_test_db([empty]),
++ Tree = open(Db, <<1,2,3>>, 4),
++ ?assertError(min_not_allowed, ebtree:insert(Db, Tree, ebtree:min(), foo)).
++
++
++max_not_allowed_test() ->
++ Db = erlfdb_util:get_test_db([empty]),
++ Tree = open(Db, <<1,2,3>>, 4),
++ ?assertError(max_not_allowed, ebtree:insert(Db, Tree, ebtree:max(), foo)).
++
++
lookup_test() ->
Db = erlfdb_util:get_test_db([empty]),
Tree = open(Db, <<1,2,3>>, 4),
@@@ -1405,7 -1385,4 +1404,34 @@@ custom_collation_reverse_range_test_()
end}.
- msec(Native) ->
- erlang:max(1, erlang:convert_time_unit(Native, native, millisecond)).
++validate_tree_test() ->
++ Db = erlfdb_util:get_test_db([empty]),
++ Tree = open(Db, <<1,2,3>>, 4),
++ [ebtree:insert(Db, Tree, I, I) || I <- lists:seq(1, 16)],
++ validate_tree(Db, Tree).
++
++
++validate_node_test_() ->
++ [
++ ?_test(?assertError({node_without_id, _}, validate_node(
++ #tree{}, #node{id = undefined}))),
++ ?_test(?assertError({too_few_keys, _}, validate_node(
++ #tree{collate_fun = fun collate_raw/2, min = 2},
++ #node{id = 1, members = [{1, 1}]}))),
++ ?_test(?assertError({too_many_keys, _}, validate_node(
++ #tree{collate_fun = fun collate_raw/2, min = 2, max = 2},
++ #node{id = 1, members = [{1, 1}, {2, 2}, {3, 3}]}))),
++ ?_test(?assertError({non_leaf_with_prev, _}, validate_node(
++ #tree{min = 0}, #node{id = 1, level = 1, prev = 1}))),
++ ?_test(?assertError({non_leaf_with_next, _}, validate_node(
++ #tree{min = 0}, #node{id = 1, level = 1, next = 1}))),
++ ?_test(?assertError({out_of_order, _}, validate_node(
++ #tree{min = 0, collate_fun = fun collate_raw/2},
++ #node{id = 1, members = [{2, 2}, {1, 1}]}))),
++ ?_test(?assertError({duplicates, _}, validate_node(
++ #tree{min = 0, collate_fun = fun collate_raw/2},
++ #node{id = 1, members = [{1, 1}, {1, 1}]})))
++ ].
++
+
-endif.