From 1fc998d21aeb437064324b560f1ac84887e37d6f Mon Sep 17 00:00:00 2001 From: Adam Kocoloski Date: Tue, 19 Oct 2010 16:33:14 -0400 Subject: remove_ancestors/2 will be generally useful --- apps/fabric/src/fabric_doc_open_revs.erl | 51 ++------------------------------ apps/fabric/src/fabric_util.erl | 51 +++++++++++++++++++++++++++++++- 2 files changed, 52 insertions(+), 50 deletions(-) diff --git a/apps/fabric/src/fabric_doc_open_revs.erl b/apps/fabric/src/fabric_doc_open_revs.erl index 70b88722..d0aec6e4 100644 --- a/apps/fabric/src/fabric_doc_open_revs.erl +++ b/apps/fabric/src/fabric_doc_open_revs.erl @@ -64,7 +64,7 @@ handle_message({ok, RawReplies}, _Worker, #state{revs = all} = State) -> } = State, All = lists:foldl(fun(Reply,D) -> orddict:update_counter(Reply,1,D) end, All0, RawReplies), - Reduced = remove_ancestors(All, []), + Reduced = fabric_util:remove_ancestors(All, []), Complete = (ReplyCount =:= (WorkerCount - 1)), QuorumMet = lists:all(fun({_, C}) -> C >= R end, Reduced), case Reduced of All when QuorumMet andalso ReplyCount =:= (R-1) -> @@ -95,7 +95,7 @@ handle_message({ok, RawReplies0}, _Worker, State) -> {Rev, orddict:update_counter(Reply, 1, D)} end end, All0, RawReplies), - Reduced = [remove_ancestors(X, []) || {_, X} <- All], + Reduced = [fabric_util:remove_ancestors(X, []) || {_, X} <- All], FinalReplies = [choose_winner(X, R) || X <- Reduced], Complete = (ReplyCount =:= (WorkerCount - 1)), case is_repair_needed(All, FinalReplies) of @@ -151,35 +151,6 @@ is_repair_needed([{_Rev, [Reply]} | Tail1], [Reply | Tail2]) -> is_repair_needed(_, _) -> true. -% this presumes the incoming list is sorted, i.e. shorter revlists come first -remove_ancestors([], Acc) -> - lists:reverse(Acc); -remove_ancestors([{{not_found, _}, Count} = Head | Tail], Acc) -> - % any document is a descendant - case lists:filter(fun({{ok, #doc{}}, _}) -> true; (_) -> false end, Tail) of - [{{ok, #doc{}} = Descendant, _} | _] -> - remove_ancestors(orddict:update_counter(Descendant, Count, Tail), Acc); - [] -> - remove_ancestors(Tail, [Head | Acc]) - end; -remove_ancestors([{{ok, #doc{revs = {Pos, Revs}}}, Count} = Head | Tail], Acc) -> - Descendants = lists:dropwhile(fun - ({{ok, #doc{revs = {Pos2, Revs2}}}, _}) -> - case lists:nthtail(Pos2 - Pos, Revs2) of - [] -> - % impossible to tell if Revs2 is a descendant - assume no - true; - History -> - % if Revs2 is a descendant, History is a prefix of Revs - not lists:prefix(History, Revs) - end - end, Tail), - case Descendants of [] -> - remove_ancestors(Tail, [Head | Acc]); - [{Descendant, _} | _] -> - remove_ancestors(orddict:update_counter(Descendant, Count, Tail), Acc) - end. - maybe_execute_read_repair(_Db, false) -> ok; maybe_execute_read_repair(Db, Docs) -> @@ -205,24 +176,6 @@ unstrip_not_found_missing([{not_found, Rev} | Rest]) -> unstrip_not_found_missing([Else | Rest]) -> [Else | unstrip_not_found_missing(Rest)]. -remove_ancestors_test() -> - Foo1 = {ok, #doc{revs = {1, [<<"foo">>]}}}, - Foo2 = {ok, #doc{revs = {2, [<<"foo2">>, <<"foo">>]}}}, - Bar1 = {ok, #doc{revs = {1, [<<"bar">>]}}}, - Bar2 = {not_found, {1,<<"bar">>}}, - ?assertEqual( - [{Bar1,1}, {Foo1,1}], - remove_ancestors([{Bar1,1}, {Foo1,1}], []) - ), - ?assertEqual( - [{Bar1,1}, {Foo2,2}], - remove_ancestors([{Bar1,1}, {Foo1,1}, {Foo2,1}], []) - ), - ?assertEqual( - [{Bar1,2}], - remove_ancestors([{Bar2,1}, {Bar1,1}], []) - ). - all_revs_test() -> State0 = #state{worker_count = 3, r = 2, revs = all}, Foo1 = {ok, #doc{revs = {1, [<<"foo">>]}}}, diff --git a/apps/fabric/src/fabric_util.erl b/apps/fabric/src/fabric_util.erl index a3265010..4ae8e126 100644 --- a/apps/fabric/src/fabric_util.erl +++ b/apps/fabric/src/fabric_util.erl @@ -14,10 +14,12 @@ -module(fabric_util). --export([submit_jobs/3, cleanup/1, recv/4, get_db/1]). +-export([submit_jobs/3, cleanup/1, recv/4, get_db/1, remove_ancestors/2]). -include("fabric.hrl"). -include_lib("mem3/include/mem3.hrl"). +-include_lib("couch/include/couch_db.hrl"). +-include_lib("eunit/include/eunit.hrl"). submit_jobs(Shards, EndPoint, ExtraArgs) -> lists:map(fun(#shard{node=Node, name=ShardName} = Shard) -> @@ -46,3 +48,50 @@ get_db(DbName) -> % but don't require them rpc:call(Node, couch_db, open, [ShardName, []]) end. + +% this presumes the incoming list is sorted, i.e. shorter revlists come first +remove_ancestors([], Acc) -> + lists:reverse(Acc); +remove_ancestors([{{not_found, _}, Count} = Head | Tail], Acc) -> + % any document is a descendant + case lists:filter(fun({{ok, #doc{}}, _}) -> true; (_) -> false end, Tail) of + [{{ok, #doc{}} = Descendant, _} | _] -> + remove_ancestors(orddict:update_counter(Descendant, Count, Tail), Acc); + [] -> + remove_ancestors(Tail, [Head | Acc]) + end; +remove_ancestors([{{ok, #doc{revs = {Pos, Revs}}}, Count} = Head | Tail], Acc) -> + Descendants = lists:dropwhile(fun + ({{ok, #doc{revs = {Pos2, Revs2}}}, _}) -> + case lists:nthtail(Pos2 - Pos, Revs2) of + [] -> + % impossible to tell if Revs2 is a descendant - assume no + true; + History -> + % if Revs2 is a descendant, History is a prefix of Revs + not lists:prefix(History, Revs) + end + end, Tail), + case Descendants of [] -> + remove_ancestors(Tail, [Head | Acc]); + [{Descendant, _} | _] -> + remove_ancestors(orddict:update_counter(Descendant, Count, Tail), Acc) + end. + +remove_ancestors_test() -> + Foo1 = {ok, #doc{revs = {1, [<<"foo">>]}}}, + Foo2 = {ok, #doc{revs = {2, [<<"foo2">>, <<"foo">>]}}}, + Bar1 = {ok, #doc{revs = {1, [<<"bar">>]}}}, + Bar2 = {not_found, {1,<<"bar">>}}, + ?assertEqual( + [{Bar1,1}, {Foo1,1}], + remove_ancestors([{Bar1,1}, {Foo1,1}], []) + ), + ?assertEqual( + [{Bar1,1}, {Foo2,2}], + remove_ancestors([{Bar1,1}, {Foo1,1}, {Foo2,1}], []) + ), + ?assertEqual( + [{Bar1,2}], + remove_ancestors([{Bar2,1}, {Bar1,1}], []) + ). -- cgit v1.2.3