diff options
author | Robert Newson <rnewson@apache.org> | 2020-07-14 20:42:47 +0100 |
---|---|---|
committer | Robert Newson <rnewson@apache.org> | 2020-07-20 09:21:18 +0100 |
commit | 3f1e6a5339f9081a7eadef99a0313f1ac2123acd (patch) | |
tree | d6d68ac877f9f955ea94ea2c18e5eedf3bac9362 | |
parent | 0a2eca50dc29cb3a8f9048e734e61857a475868a (diff) | |
download | couchdb-3f1e6a5339f9081a7eadef99a0313f1ac2123acd.tar.gz |
Allow fold in fwd and rev direction
-rw-r--r-- | src/ebtree.erl | 38 |
1 files changed, 26 insertions, 12 deletions
diff --git a/src/ebtree.erl b/src/ebtree.erl index b37963a18..ca020cc07 100644 --- a/src/ebtree.erl +++ b/src/ebtree.erl @@ -11,6 +11,7 @@ range/6, reverse_range/6, fold/4, + fold/5, reduce/4, full_reduce/2, group_reduce/7, @@ -126,47 +127,60 @@ lookup(Db, #tree{} = Tree, Key) -> fold(Db, Tree, Fun, false). +%% @equiv fold(Db, Tree, Fun, Acc, []) +-spec fold(Db :: term(), Tree :: #tree{}, Fun :: fun(), Acc :: term()) -> term(). +fold(Db, #tree{} = Tree, Fun, Acc) -> + fold(Db, Tree, Fun, Acc, []). + + %% @doc Custom traversal of the ebtree. %% @param Db An erlfdb database or transaction. %% @param Tree the ebtree. %% @param Fun A callback function as nodes are loaded that directs the traversal. %% @param Acc The initial accumulator. +%% @param Options Currently supported options are [{dir, fwd}] and [{dir, rev}] %% @returns the final accumulator. --spec fold(Db :: term(), Tree :: #tree{}, Fun :: fun(), Acc :: term()) -> term(). -fold(Db, #tree{} = Tree, Fun, Acc) -> +-spec fold(Db :: term(), Tree :: #tree{}, Fun :: fun(), Acc :: term(), Options :: list()) -> term(). +fold(Db, #tree{} = Tree, Fun, Acc, Options) -> {_, Reduce} = erlfdb:transactional(Db, fun(Tx) -> Root = get_node(Tx, Tree, ?NODE_ROOT_ID), - fold(Db, Tree, Root, Fun, Acc) + fold(Db, Tree, Root, Fun, Acc, Options) end), Reduce. -fold(Db, #tree{} = Tree, #node{} = Node, Fun, Acc) -> - fold(Db, #tree{} = Tree, Node#node.members, Fun, Acc); + +fold(Db, #tree{} = Tree, #node{} = Node, Fun, Acc, Options) -> + Dir = proplists:get_value(dir, Options, fwd), + Members = case Dir of + fwd -> Node#node.members; + rev -> lists:reverse(Node#node.members) + end, + fold(Db, #tree{} = Tree, Members, Fun, Acc, Options); -fold(_Db, #tree{} = _Tree, [], _Fun, Acc) -> +fold(_Db, #tree{} = _Tree, [], _Fun, Acc, _Options) -> {ok, Acc}; -fold(Db, #tree{} = Tree, [{K, V} | Rest], Fun, Acc0) -> +fold(Db, #tree{} = Tree, [{K, V} | Rest], Fun, Acc0, Options) -> case Fun({visit, K, V}, Acc0) of {ok, Acc1} -> - fold(Db, Tree, Rest, Fun, Acc1); + fold(Db, Tree, Rest, Fun, Acc1, Options); {stop, Acc1} -> {stop, Acc1} end; -fold(Db, #tree{} = Tree, [{F, L, P, R} | Rest], Fun, Acc0) -> +fold(Db, #tree{} = Tree, [{F, L, P, R} | Rest], Fun, Acc0, Options) -> case Fun({traverse, F, L, R}, Acc0) of {ok, Acc1} -> Node = get_node(Db, Tree, P), - case fold(Db, Tree, Node, Fun, Acc1) of + case fold(Db, Tree, Node, Fun, Acc1, Options) of {ok, Acc2} -> - fold(Db, Tree, Rest, Fun, Acc2); + fold(Db, Tree, Rest, Fun, Acc2, Options); {stop, Acc2} -> {stop, Acc2} end; {skip, Acc1} -> - fold(Db, Tree, Rest, Fun, Acc1); + fold(Db, Tree, Rest, Fun, Acc1, Options); {stop, Acc1} -> {stop, Acc1} end. |