BugzID:9995 Add a tree foldl function to couch_key_tree.

This function can be used by many of the existing functions
in couch_key_tree that need to walk the revision tree, apply
a function at each branch or leaf, and then accumulate results.

1 files changed, 27 insertions, 0 deletions

diff --git a/apps/couch/src/couch_key_tree.erl b/apps/couch/src/couch_key_tree.erl
index 6701da58..9ec444ac 100644
--- a/apps/couch/src/couch_key_tree.erl
+++ b/apps/couch/src/couch_key_tree.erl
@@ -278,6 +278,33 @@ count_leafs_simple([{_Key, _Value, SubTree} | RestTree]) ->
     count_leafs_simple(SubTree) + count_leafs_simple(RestTree).
 
 
+foldl(_Fun, Acc, []) ->
+    Acc;
+
+foldl(Fun, Acc, [{Pos, Branch} | Rest]) ->
+    Acc1 = foldl_simple(Fun, Pos, [Branch], Acc),
+    foldl(Fun, Acc1, Rest).
+
+foldl_simple(_Fun, _Pos, [], Acc) ->
+    Acc;
+
+foldl_simple(Fun, Pos, [{Key, Value, []} | RestTree], Acc) ->
+    case Fun({Pos, Key, Value}, leaf, Acc) of
+    {ok, Acc1} ->
+        foldl_simple(Fun, Pos, RestTree, Acc1);
+    {stop, Acc1} ->
+        Acc1
+    end;
+
+foldl_simple(Fun, Pos, [{Key, Value, SubTree} | RestTree], Acc) ->
+    Acc1 = foldl_simple(Fun, Pos + 1, SubTree, Acc),
+    case Fun({Pos, Key, Value}, branch, Acc1) of
+    {ok, Acc2} ->
+        foldl_simple(Fun, Pos, RestTree, Acc2);
+    {stop, Acc2} ->
+        Acc2
+    end.
+
 map(_Fun, []) ->
     [];
 map(Fun, [{Pos, Tree}|Rest]) ->