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/21 16:02:11 UTC
[couchdb] 01/01: switch from erlfdb to fabric2_fdb
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a commit to branch prototype/fdb-layer-ebtree-fabric-style
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit 3602eafd0684aa6add73ccc06d4d3690ccfb585c
Author: Robert Newson <rn...@apache.org>
AuthorDate: Tue Jul 21 16:43:12 2020 +0100
switch from erlfdb to fabric2_fdb
---
src/ebtree/src/ebtree.app.src | 3 +-
src/ebtree/src/ebtree.erl | 316 +++++++++++++++++++++++-------------------
2 files changed, 177 insertions(+), 142 deletions(-)
diff --git a/src/ebtree/src/ebtree.app.src b/src/ebtree/src/ebtree.app.src
index d4966f6..10dc514 100644
--- a/src/ebtree/src/ebtree.app.src
+++ b/src/ebtree/src/ebtree.app.src
@@ -17,7 +17,8 @@
{applications,
[kernel,
stdlib,
- erlfdb
+ erlfdb,
+ fabric
]},
{env,[]},
{modules, []},
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index ccfd414..042873c 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -80,13 +80,14 @@ open(Db, Prefix, Order, Options) when is_binary(Prefix), is_integer(Order), Orde
ReduceFun = proplists:get_value(reduce_fun, Options, fun reduce_noop/2),
CollateFun = proplists:get_value(collate_fun, Options, fun collate_raw/2),
- erlfdb:transactional(Db, fun(Tx) ->
- case get_meta(Tx, Prefix, ?META_ORDER) of
+ fabric2_fdb:transactional(Db, fun(TxDb) ->
+ #{tx := Tx} = TxDb,
+ case get_meta(TxDb, Prefix, ?META_ORDER) of
not_found ->
erlfdb:clear_range_startswith(Tx, Prefix),
- set_meta(Tx, Prefix, ?META_ORDER, Order),
- set_meta(Tx, Prefix, ?META_NEXT_ID, 1),
- set_node(Tx, init_tree(Prefix, Order), #node{id = ?NODE_ROOT_ID});
+ set_meta(TxDb, Prefix, ?META_ORDER, Order),
+ set_meta(TxDb, Prefix, ?META_NEXT_ID, 1),
+ set_node(TxDb, init_tree(Prefix, Order), #node{id = ?NODE_ROOT_ID});
Order ->
ok;
Else ->
@@ -167,8 +168,8 @@ fold(Db, #tree{} = Tree, Fun, Acc) ->
Options :: [fold_option()],
Acc1 :: term().
fold(Db, #tree{} = Tree, Fun, Acc, Options) ->
- {_, Reduce} = erlfdb:transactional(Db, fun(Tx) ->
- Root = get_node(Tx, Tree, ?NODE_ROOT_ID),
+ {_, Reduce} = fabric2_fdb:transactional(Db, fun(TxDb) ->
+ Root = get_node(TxDb, Tree, ?NODE_ROOT_ID),
fold(Db, Tree, Root, Fun, Acc, Options)
end),
Reduce.
@@ -375,26 +376,26 @@ group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, User
-spec range(Db :: term(), Tree :: #tree{}, StartKey :: term(), EndKey :: term(),
AccFun :: fun(), Acc0 :: term()) -> term().
range(Db, #tree{} = Tree, StartKey, EndKey, AccFun, Acc0) ->
- erlfdb:transactional(Db, fun(Tx) ->
- range(Tx, Tree, get_node(Tx, Tree, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
+ fabric2_fdb:transactional(Db, fun(TxDb) ->
+ range(TxDb, Tree, get_node(TxDb, Tree, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
end).
-range(Tx, #tree{} = Tree, #node{level = 0} = Node, StartKey, EndKey, AccFun, Acc0) ->
+range(TxDb, #tree{} = Tree, #node{level = 0} = Node, StartKey, EndKey, AccFun, Acc0) ->
InRange = [{K, V} || {K, V} <- Node#node.members,
less_than_or_equal(Tree, StartKey, K), less_than_or_equal(Tree, K, EndKey)],
Acc1 = AccFun(InRange, Acc0),
LastKey = last_key(Node),
case Node#node.next /= undefined andalso less_than_or_equal(Tree, LastKey, EndKey) of
true ->
- range(Tx, Tree, get_node(Tx, Tree, Node#node.next), StartKey, EndKey, AccFun, Acc1);
+ range(TxDb, Tree, get_node(TxDb, Tree, Node#node.next), StartKey, EndKey, AccFun, Acc1);
false ->
Acc1
end;
-range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
+range(TxDb, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
ChildId = find_child_id(Tree, Node, StartKey),
- range(Tx, Tree, get_node(Tx, Tree, ChildId), StartKey, EndKey, AccFun, Acc).
+ range(TxDb, Tree, get_node(TxDb, Tree, ChildId), StartKey, EndKey, AccFun, Acc).
%% @doc Finds all key-value pairs for the specified range in reverse order.
@@ -408,26 +409,26 @@ range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
-spec reverse_range(Db :: term(), Tree :: #tree{}, StartKey :: term(), EndKey :: term(),
AccFun :: fun(), Acc0 :: term()) -> term().
reverse_range(Db, #tree{} = Tree, StartKey, EndKey, AccFun, Acc0) ->
- erlfdb:transactional(Db, fun(Tx) ->
- reverse_range(Tx, Tree, get_node(Tx, Tree, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
+ fabric2_fdb:transactional(Db, fun(TxDb) ->
+ reverse_range(TxDb, Tree, get_node(TxDb, Tree, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
end).
-reverse_range(Tx, #tree{} = Tree, #node{level = 0} = Node, StartKey, EndKey, AccFun, Acc0) ->
+reverse_range(TxDb, #tree{} = Tree, #node{level = 0} = Node, StartKey, EndKey, AccFun, Acc0) ->
InRange = [{K, V} || {K, V} <- Node#node.members,
less_than_or_equal(Tree, StartKey, K), less_than_or_equal(Tree, K, EndKey)],
Acc1 = AccFun(lists:reverse(InRange), Acc0),
FirstKey = first_key(Node),
case Node#node.prev /= undefined andalso less_than_or_equal(Tree, StartKey, FirstKey) of
true ->
- reverse_range(Tx, Tree, get_node(Tx, Tree, Node#node.prev), StartKey, EndKey, AccFun, Acc1);
+ reverse_range(TxDb, Tree, get_node(TxDb, Tree, Node#node.prev), StartKey, EndKey, AccFun, Acc1);
false ->
Acc1
end;
-reverse_range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
+reverse_range(TxDb, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
ChildId = find_child_id(Tree, Node, EndKey),
- reverse_range(Tx, Tree, get_node(Tx, Tree, ChildId), StartKey, EndKey, AccFun, Acc).
+ reverse_range(TxDb, Tree, get_node(TxDb, Tree, ChildId), StartKey, EndKey, AccFun, Acc).
%% @doc Inserts or updates a value in the ebtree
@@ -444,31 +445,31 @@ insert(_Db, #tree{} = _Tree, ?MAX, _Value) ->
erlang:error(max_not_allowed);
insert(Db, #tree{} = Tree, Key, Value) ->
- erlfdb:transactional(Db, fun(Tx) ->
- Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID),
+ fabric2_fdb:transactional(Db, fun(TxDb) ->
+ Root0 = get_node(TxDb, Tree, ?NODE_ROOT_ID),
case ?is_full(Tree, Root0) of
true ->
- OldRoot = Root0#node{id = new_node_id(Tx, Tree)},
+ OldRoot = Root0#node{id = new_node_id(TxDb, Tree)},
FirstKey = first_key(OldRoot),
LastKey = last_key(OldRoot),
Root1 = #node{
id = ?NODE_ROOT_ID,
level = Root0#node.level + 1,
members = [{FirstKey, LastKey, OldRoot#node.id, []}]},
- {Root2, _, _} = split_child(Tx, Tree, Root1, OldRoot),
- insert_nonfull(Tx, Tree, Root2, Key, Value);
+ {Root2, _, _} = split_child(TxDb, Tree, Root1, OldRoot),
+ insert_nonfull(TxDb, Tree, Root2, Key, Value);
false ->
- insert_nonfull(Tx, Tree, Root0, Key, Value)
+ insert_nonfull(TxDb, Tree, Root0, Key, Value)
end
end),
Tree.
-split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
+split_child(TxDb, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
{LeftMembers, RightMembers} = lists:split(Tree#tree.min, Child#node.members),
- LeftId = new_node_id(Tx, Tree),
- RightId = new_node_id(Tx, Tree),
+ LeftId = new_node_id(TxDb, Tree),
+ RightId = new_node_id(TxDb, Tree),
LeftChild = remove_pointers_if_not_leaf(#node{
id = LeftId,
@@ -486,8 +487,8 @@ split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
members = RightMembers
}),
- update_prev_neighbour(Tx, Tree, LeftChild),
- update_next_neighbour(Tx, Tree, RightChild),
+ update_prev_neighbour(TxDb, Tree, LeftChild),
+ update_next_neighbour(TxDb, Tree, RightChild),
%% adjust parent members
FirstLeftKey = first_key(LeftMembers),
@@ -505,40 +506,40 @@ split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
umerge(Tree, [{FirstRightKey, LastRightKey, RightId, RightReduction}],
lists:keydelete(Child#node.id, 3, Parent0#node.members)))
},
- clear_node(Tx, Tree, Child),
- set_nodes(Tx, Tree, [LeftChild, RightChild, Parent1]),
+ clear_node(TxDb, Tree, Child),
+ set_nodes(TxDb, Tree, [LeftChild, RightChild, Parent1]),
{Parent1, LeftChild, RightChild}.
-update_prev_neighbour(_Tx, #tree{} = _Tree, #node{prev = undefined} = _Node) ->
+update_prev_neighbour(_TxDb, #tree{} = _Tree, #node{prev = undefined} = _Node) ->
ok;
-update_prev_neighbour(Tx, #tree{} = Tree, #node{} = Node) ->
- Left = get_node(Tx, Tree, Node#node.prev),
- set_node(Tx, Tree, Left#node{next = Node#node.id}).
+update_prev_neighbour(TxDb, #tree{} = Tree, #node{} = Node) ->
+ Left = get_node(TxDb, Tree, Node#node.prev),
+ set_node(TxDb, Tree, Left#node{next = Node#node.id}).
-update_next_neighbour(_Tx, #tree{} = _Tree, #node{next = undefined} = _Node) ->
+update_next_neighbour(_TxDb, #tree{} = _Tree, #node{next = undefined} = _Node) ->
ok;
-update_next_neighbour(Tx, #tree{} = Tree, #node{} = Node) ->
- Left = get_node(Tx, Tree, Node#node.next),
- set_node(Tx, Tree, Left#node{prev = Node#node.id}).
+update_next_neighbour(TxDb, #tree{} = Tree, #node{} = Node) ->
+ Left = get_node(TxDb, Tree, Node#node.next),
+ set_node(TxDb, Tree, Left#node{prev = Node#node.id}).
-insert_nonfull(Tx, #tree{} = Tree, #node{level = 0} = Node0, Key, Value) ->
+insert_nonfull(TxDb, #tree{} = Tree, #node{level = 0} = Node0, Key, Value) ->
Node1 = Node0#node{
members = umerge(Tree, [{Key, Value}], Node0#node.members)
},
- set_node(Tx, Tree, Node1),
+ set_node(TxDb, Tree, Node1),
reduce_node(Tree, Node1);
-insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
+insert_nonfull(TxDb, #tree{} = Tree, #node{} = Node0, Key, Value) ->
ChildId0 = find_child_id(Tree, Node0, Key),
- Child0 = get_node(Tx, Tree, ChildId0),
+ Child0 = get_node(TxDb, Tree, ChildId0),
{Node1, Child1} = case ?is_full(Tree, Child0) of
true ->
- {Parent, LeftChild, RightChild} = split_child(Tx, Tree, Node0, Child0),
+ {Parent, LeftChild, RightChild} = split_child(TxDb, Tree, Node0, Child0),
ChildId = find_child_id(Tree, Parent, Key),
Child = if
ChildId =:= LeftChild#node.id ->
@@ -551,7 +552,7 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
{Node0, Child0}
end,
ChildId1 = Child1#node.id,
- NewReduction = insert_nonfull(Tx, Tree, Child1, Key, Value),
+ NewReduction = insert_nonfull(TxDb, 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]),
@@ -559,7 +560,7 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
members = lists:keyreplace(ChildId1, 3, Node1#node.members,
{NewFirstKey, NewLastKey, ChildId1, NewReduction})
},
- set_node(Tx, Tree, Node2),
+ set_node(TxDb, Tree, Node2),
reduce_node(Tree, Node2).
@@ -570,45 +571,45 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
%% @returns the tree.
-spec delete(Db :: term(), Tree :: #tree{}, Key :: term()) -> #tree{}.
delete(Db, #tree{} = Tree, Key) ->
- erlfdb:transactional(Db, fun(Tx) ->
- Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID),
- case delete(Tx, Tree, Root0, Key) of
+ fabric2_fdb:transactional(Db, fun(TxDb) ->
+ Root0 = get_node(TxDb, Tree, ?NODE_ROOT_ID),
+ case delete(TxDb, Tree, Root0, Key) of
% if only one child, make it the new root.
#node{level = L, members = [_]} = Root1 when L > 0 ->
[{_, _, ChildId, _}] = Root1#node.members,
- Root2 = get_node(Tx, Tree, ChildId),
- clear_node(Tx, Tree, Root2),
- set_node(Tx, Tree, Root2#node{id = ?NODE_ROOT_ID});
+ Root2 = get_node(TxDb, Tree, ChildId),
+ clear_node(TxDb, Tree, Root2),
+ set_node(TxDb, Tree, Root2#node{id = ?NODE_ROOT_ID});
Root1 ->
- set_node(Tx, Tree, Root1)
+ set_node(TxDb, Tree, Root1)
end
end),
Tree.
-delete(_Tx, #tree{} = _Tree, #node{level = 0} = Node, Key) ->
+delete(_TxDb, #tree{} = _Tree, #node{level = 0} = Node, Key) ->
Node#node{
members = lists:keydelete(Key, 1, Node#node.members)
};
-delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
+delete(TxDb, #tree{} = Tree, #node{} = Parent0, Key) ->
ChildId0 = find_child_id(Tree, Parent0, Key),
- Child0 = get_node(Tx, Tree, ChildId0),
- Child1 = delete(Tx, Tree, Child0, Key),
+ Child0 = get_node(TxDb, Tree, ChildId0),
+ Child1 = delete(TxDb, Tree, Child0, Key),
case ?underflow(Tree, Child1) of
true ->
SiblingId = find_sibling_id(Tree, Parent0, ChildId0, Key),
- Sibling = get_node(Tx, Tree, SiblingId),
+ Sibling = get_node(TxDb, Tree, SiblingId),
NewNodes = case ?at_min(Tree, Sibling) of
true ->
- Merged = merge(Tx, Tree, Child1, Sibling),
- update_prev_neighbour(Tx, Tree, Merged),
- update_next_neighbour(Tx, Tree, Merged),
+ Merged = merge(TxDb, Tree, Child1, Sibling),
+ update_prev_neighbour(TxDb, Tree, Merged),
+ update_next_neighbour(TxDb, Tree, Merged),
[Merged];
false ->
- {Left, Right} = rebalance(Tx, Tree, Child1, Sibling),
- update_prev_neighbour(Tx, Tree, Left),
- update_next_neighbour(Tx, Tree, Right),
+ {Left, Right} = rebalance(TxDb, Tree, Child1, Sibling),
+ update_prev_neighbour(TxDb, Tree, Left),
+ update_next_neighbour(TxDb, Tree, Right),
[Left, Right]
end,
@@ -625,11 +626,11 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
members = Members3
},
- clear_nodes(Tx, Tree, [Child0, Sibling]),
- set_nodes(Tx, Tree, NewNodes),
+ clear_nodes(TxDb, Tree, [Child0, Sibling]),
+ set_nodes(TxDb, Tree, NewNodes),
Parent1;
false ->
- set_node(Tx, Tree, Child1),
+ set_node(TxDb, Tree, Child1),
{_OldFirstKey, _OldLastKey, ChildId0, _OldReduction} = lists:keyfind(ChildId0, 3, Parent0#node.members),
Parent0#node{
members = lists:keyreplace(ChildId0, 3, Parent0#node.members,
@@ -638,11 +639,11 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
end.
-merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
+merge(TxDb, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
[Left, Right] = sort(Tree, [Node1, Node2]),
#node{
- id = new_node_id(Tx, Tree),
+ id = new_node_id(TxDb, Tree),
level = Level,
prev = Left#node.prev,
next = Right#node.next,
@@ -650,14 +651,14 @@ merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = N
}.
-rebalance(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
+rebalance(TxDb, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
[Left0, Right0] = sort(Tree, [Node1, Node2]),
Members = lists:append(Left0#node.members, Right0#node.members),
{LeftMembers, RightMembers} = lists:split(length(Members) div 2, Members),
- Left1Id = new_node_id(Tx, Tree),
- Right1Id = new_node_id(Tx, Tree),
+ Left1Id = new_node_id(TxDb, Tree),
+ Right1Id = new_node_id(TxDb, Tree),
Left1 = remove_pointers_if_not_leaf(Left0#node{
id = Left1Id,
@@ -701,12 +702,12 @@ find_child_int(#tree{} = Tree, [{_F, L, _P, _R} = Child| Rest], Key) ->
%% metadata functions
-get_meta(Tx, #tree{} = Tree, MetaKey) ->
- get_meta(Tx, Tree#tree.prefix, MetaKey);
+get_meta(TxDb, #tree{} = Tree, MetaKey) ->
+ get_meta(TxDb, Tree#tree.prefix, MetaKey);
-get_meta(Tx, Prefix, MetaKey) when is_binary(Prefix) ->
- Future = get_meta_future(Tx, Prefix, MetaKey),
+get_meta(TxDb, Prefix, MetaKey) when is_binary(Prefix) ->
+ Future = get_meta_future(TxDb, Prefix, MetaKey),
case erlfdb:wait(Future) of
not_found ->
not_found;
@@ -715,11 +716,13 @@ get_meta(Tx, Prefix, MetaKey) when is_binary(Prefix) ->
end.
-get_meta_future(Tx, Prefix, MetaKey) ->
+get_meta_future(TxDb, Prefix, MetaKey) ->
+ #{tx := Tx} = TxDb,
erlfdb:get(Tx, meta_key(Prefix, MetaKey)).
-set_meta(Tx, Prefix, MetaKey, MetaValue) ->
+set_meta(TxDb, Prefix, MetaKey, MetaValue) ->
+ #{tx := Tx} = TxDb,
erlfdb:set(
Tx,
meta_key(Prefix, MetaKey),
@@ -731,37 +734,40 @@ meta_key(Prefix, MetaKey) when is_binary(Prefix) ->
%% node persistence functions
-get_node(Tx, #tree{} = Tree, Id) ->
- get_node_wait(Id, get_node_future(Tx, Tree, Id)).
+get_node(TxDb, #tree{} = Tree, Id) ->
+ get_node_wait(Id, get_node_future(TxDb, Tree, Id)).
get_node_wait(Id, Future) ->
decode_node(Id, erlfdb:wait(Future)).
-get_node_future(Tx, #tree{} = Tree, Id) ->
+get_node_future(TxDb, #tree{} = Tree, Id) ->
+ #{tx := Tx} = TxDb,
Key = node_key(Tree#tree.prefix, Id),
erlfdb:get(Tx, Key).
-clear_nodes(Tx, #tree{} = Tree, Nodes) ->
+clear_nodes(TxDb, #tree{} = Tree, Nodes) ->
lists:foreach(fun(Node) ->
- clear_node(Tx, Tree, Node)
+ clear_node(TxDb, Tree, Node)
end, Nodes).
-clear_node(Tx, #tree{} = Tree, #node{} = Node) ->
- Key = node_key(Tree#tree.prefix, Node#node.id),
- erlfdb:clear(Tx, Key).
+clear_node(TxDb, #tree{} = Tree, #node{} = Node) ->
+ #{tx := Tx} = TxDb,
+ Key = node_key(Tree#tree.prefix, Node#node.id),
+ erlfdb:clear(Tx, Key).
-set_nodes(Tx, #tree{} = Tree, Nodes) ->
+set_nodes(TxDb, #tree{} = Tree, Nodes) ->
lists:foreach(fun(Node) ->
- set_node(Tx, Tree, Node)
+ set_node(TxDb, Tree, Node)
end, Nodes).
-set_node(Tx, #tree{} = Tree, #node{} = Node) ->
+set_node(TxDb, #tree{} = Tree, #node{} = Node) ->
+ #{tx := Tx} = TxDb,
validate_node(Tree, Node),
Key = node_key(Tree#tree.prefix, Node#node.id),
Value = encode_node(Node),
@@ -775,28 +781,28 @@ node_key(Prefix, Id) when is_binary(Prefix), is_integer(Id) ->
%% @doc Walks the whole tree and checks it for consistency.
%% It also prints it to screen.
validate_tree(Db, #tree{} = Tree) ->
- erlfdb:transactional(Db, fun(Tx) ->
+ fabric2_fdb:transactional(Db, fun(TxDb) ->
Root = get_node(Db, Tree, ?NODE_ROOT_ID),
- validate_tree(Tx, Tree, Root)
+ validate_tree(TxDb, Tree, Root)
end).
-validate_tree(_Tx, #tree{} = Tree, #node{level = 0} = Node) ->
+validate_tree(_TxDb, #tree{} = Tree, #node{level = 0} = Node) ->
print_node(Node),
validate_node(Tree, Node);
-validate_tree(Tx, #tree{} = Tree, #node{} = Node) ->
+validate_tree(TxDb, #tree{} = Tree, #node{} = Node) ->
print_node(Node),
validate_node(Tree, Node),
- validate_tree(Tx, Tree, Node#node.members);
+ validate_tree(TxDb, Tree, Node#node.members);
-validate_tree(_Tx, #tree{} = _Tree, []) ->
+validate_tree(_TxDb, #tree{} = _Tree, []) ->
ok;
-validate_tree(Tx, #tree{} = Tree, [{_F, _L, P, _R} | Rest]) ->
- Node = get_node(Tx, Tree, P),
- validate_tree(Tx, Tree, Node),
- validate_tree(Tx, Tree, Rest).
+validate_tree(TxDb, #tree{} = Tree, [{_F, _L, P, _R} | Rest]) ->
+ Node = get_node(TxDb, Tree, P),
+ validate_tree(TxDb, Tree, Node),
+ validate_tree(TxDb, Tree, Rest).
validate_node(#tree{} = Tree, #node{} = Node) ->
@@ -980,9 +986,9 @@ last_key(Members) when is_list(Members) ->
end.
-new_node_id(Tx, Tree) ->
- NextId = get_meta(Tx, Tree, ?META_NEXT_ID),
- set_meta(Tx, Tree#tree.prefix, ?META_NEXT_ID, NextId + 1),
+new_node_id(TxDb, Tree) ->
+ NextId = get_meta(TxDb, Tree, ?META_NEXT_ID),
+ set_meta(TxDb, Tree#tree.prefix, ?META_NEXT_ID, NextId + 1),
NextId.
@@ -1002,6 +1008,8 @@ print_node(#node{} = Node) ->
%% tests
-ifdef(TEST).
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch/include/couch_eunit.hrl").
-include_lib("eunit/include/eunit.hrl").
reduce_sum(KVs, false) ->
@@ -1058,17 +1066,58 @@ collation_fun_test_() ->
].
-lookup_test() ->
- Db = erlfdb_util:get_test_db([empty]),
+ebtree_test_() ->
+ {
+ "Test ebtree functionality",
+ {
+ foreach,
+ fun setup/0,
+ fun cleanup/1,
+ [
+ fun test_lookup/1,
+ fun test_delete/1,
+ fun test_range_after_delete/1,
+ fun test_full_reduce/1,
+ fun test_full_reduce_after_delete/1,
+ fun test_count_reduce/1,
+ fun test_sum_reduce/1,
+ fun test_stats_reduce/1,
+ fun test_group_reduce_level/1,
+ fun test_group_reduce_int/1,
+ fun test_raw_collation/1,
+ fun test_custom_collation/1,
+ fun test_intense_lookup/1,
+ fun test_range/1,
+ fun test_reverse_range/1,
+ fun test_custom_collation_range/1,
+ fun test_custom_collation_reverse_range/1
+ ]
+ }
+ }.
+
+
+setup() ->
+ Ctx = test_util:start_couch([fabric]),
+ {ok, Db} = fabric2_db:create(?tempdb(), [{user_ctx, ?ADMIN_USER}]),
+ {Db, Ctx}.
+
+
+cleanup({Db, Ctx}) ->
+ ok = fabric2_db:delete(fabric2_db:name(Db), []),
+ test_util:stop_couch(Ctx).
+
+
+test_lookup({Db, _}) ->
+ ?debugFmt("lookup 1", []),
Tree = open(Db, <<1,2,3>>, 4),
+ ?debugFmt("lookup 2: ~p", [Tree]),
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, 100)])],
lists:foreach(fun(Key) -> insert(Db, Tree, Key, Key + 1) end, Keys),
lists:foreach(fun(Key) -> ?assertEqual({Key, Key + 1}, lookup(Db, Tree, Key)) end, Keys),
?assertEqual(false, lookup(Db, Tree, 101)).
-delete_test() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_delete({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4),
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, 100)])],
lists:foreach(fun(Key) -> insert(Db, Tree, Key, Key + 1) end, Keys),
@@ -1077,8 +1126,7 @@ delete_test() ->
lists:foreach(fun(Key) -> ?assertEqual(false, lookup(Db, Tree, Key)) end, Keys).
-range_after_delete_test() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_range_after_delete({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4),
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, 100)])],
lists:foreach(fun(Key) -> insert(Db, Tree, Key, Key + 1) end, Keys),
@@ -1088,8 +1136,7 @@ range_after_delete_test() ->
?assertEqual(50, reverse_range(Db, Tree, 1, 100, fun(E, A) -> length(E) + A end, 0)).
-full_reduce_test_() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_full_reduce({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_sum/2}]),
TestFun = fun(Max) ->
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1102,8 +1149,7 @@ full_reduce_test_() ->
].
-full_reduce_after_delete_test() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_full_reduce_after_delete({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_sum/2}]),
Max = 100,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1113,8 +1159,7 @@ full_reduce_after_delete_test() ->
?assertEqual(0, full_reduce(Db, Tree)).
-count_reduce_test_() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_count_reduce({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_count/2}]),
Max = 100,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1129,8 +1174,7 @@ count_reduce_test_() ->
?_test(?assertEqual(Expected(5, 7), reduce(Db, Tree, 5, 7)))
].
-sum_reduce_test_() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_sum_reduce({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_sum/2}]),
Max = 100,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1146,8 +1190,7 @@ sum_reduce_test_() ->
].
-stats_reduce_test_() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_stats_reduce({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_stats/2}]),
Max = 100,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1162,8 +1205,7 @@ stats_reduce_test_() ->
].
-group_reduce_level_test_() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_group_reduce_level({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_sum/2}]),
Max = 100,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1186,8 +1228,7 @@ group_reduce_level_test_() ->
].
-group_reduce_int_test_() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_group_reduce_int({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4, [{reduce_fun, fun reduce_count/2}]),
Max = 100,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
@@ -1202,16 +1243,14 @@ group_reduce_int_test_() ->
].
-raw_collation_test() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_raw_collation({Db, _}) ->
Tree = open(Db, <<1,2,3>>, 4),
insert(Db, Tree, null, null),
insert(Db, Tree, 1, 1),
?assertEqual([{1, 1}, {null, null}], range(Db, Tree, 1, null, fun(E, A) -> A ++ E end, [])).
-custom_collation_test() ->
- Db = erlfdb_util:get_test_db([empty]),
+test_custom_collation({Db, _}) ->
CollateFun = fun(A, B) -> B =< A end,
Tree = open(Db, <<1,2,3>>, 4, [{collate_fun, CollateFun}]),
insert(Db, Tree, 1, 1),
@@ -1219,16 +1258,15 @@ custom_collation_test() ->
?assertEqual([{2, 2}, {1, 1}], range(Db, Tree, 3, 0, fun(E, A) -> A ++ E end, [])).
-intense_lookup_test_() ->
+test_intense_lookup({Db, _}) ->
[
- {timeout, 1000, fun() -> lookup_test_fun(1000, 20) end},
- {timeout, 1000, fun() -> lookup_test_fun(1000, 50) end},
- {timeout, 1000, fun() -> lookup_test_fun(1000, 500) end}
+ {timeout, 1000, fun() -> lookup_test_fun(Db, 1000, 20) end},
+ {timeout, 1000, fun() -> lookup_test_fun(Db, 1000, 50) end},
+ {timeout, 1000, fun() -> lookup_test_fun(Db, 1000, 500) end}
].
-lookup_test_fun(Max, Order) ->
- Db = erlfdb_util:get_test_db([empty]),
+lookup_test_fun(Db, Max, Order) ->
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max, 2)])],
T0 = erlang:monotonic_time(),
Tree = lists:foldl(fun(Key, T) -> insert(Db, T, Key, Key + 1) end, open(Db, <<1,2,3>>, Order), Keys),
@@ -1239,9 +1277,8 @@ lookup_test_fun(Max, Order) ->
[Order, Max, 1000 * (Max / msec(T1 - T0)), 1000 * (Max / msec(T2 - T1))]).
-range_test_() ->
+test_range({Db, _}) ->
{timeout, 1000, fun() ->
- Db = erlfdb_util:get_test_db([empty]),
Max = 1000,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
Tree = lists:foldl(fun(Key, T) -> insert(Db, T, Key, Key + 1) end, open(Db, <<1,2,3>>, 10), Keys),
@@ -1255,9 +1292,8 @@ range_test_() ->
end}.
-reverse_range_test_() ->
+test_reverse_range({Db, _}) ->
{timeout, 1000, fun() ->
- Db = erlfdb_util:get_test_db([empty]),
Max = 1000,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
Tree = lists:foldl(fun(Key, T) -> insert(Db, T, Key, Key + 1) end, open(Db, <<1,2,3>>, 10), Keys),
@@ -1271,9 +1307,8 @@ reverse_range_test_() ->
end}.
-custom_collation_range_test_() ->
+test_custom_collation_range({Db, _}) ->
{timeout, 1000, fun() ->
- Db = erlfdb_util:get_test_db([empty]),
Max = 1000,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
CollateFun = fun(A, B) -> B =< A end,
@@ -1295,9 +1330,8 @@ custom_collation_range_test_() ->
end}.
-custom_collation_reverse_range_test_() ->
+test_custom_collation_reverse_range({Db, _}) ->
{timeout, 1000, fun() ->
- Db = erlfdb_util:get_test_db([empty]),
Max = 1000,
Keys = [X || {_, X} <- lists:sort([ {rand:uniform(), N} || N <- lists:seq(1, Max)])],
CollateFun = fun(A, B) -> B =< A end,