From 19cb6e7f8c890fd3c9b1fa563a54a80129843bd4 Mon Sep 17 00:00:00 2001 From: Matthew Sackman Date: Sun, 2 Oct 2011 15:13:35 +0100 Subject: Drop unneeded queue impls, tidy lqueue, add specs etc --- src/bpqueue.erl | 273 ------------------------------------------ src/finger_tree.erl | 264 ---------------------------------------- src/fqueue.erl | 141 ---------------------- src/lqueue.erl | 24 ++++ src/rabbit_tests.erl | 138 --------------------- src/rabbit_variable_queue.erl | 8 +- 6 files changed, 28 insertions(+), 820 deletions(-) delete mode 100644 src/bpqueue.erl delete mode 100644 src/finger_tree.erl delete mode 100644 src/fqueue.erl diff --git a/src/bpqueue.erl b/src/bpqueue.erl deleted file mode 100644 index c7d89998..00000000 --- a/src/bpqueue.erl +++ /dev/null @@ -1,273 +0,0 @@ -%% The contents of this file are subject to the Mozilla Public License -%% Version 1.1 (the "License"); you may not use this file except in -%% compliance with the License. You may obtain a copy of the License -%% at http://www.mozilla.org/MPL/ -%% -%% Software distributed under the License is distributed on an "AS IS" -%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See -%% the License for the specific language governing rights and -%% limitations under the License. -%% -%% The Original Code is RabbitMQ. -%% -%% The Initial Developer of the Original Code is VMware, Inc. -%% Copyright (c) 2007-2011 VMware, Inc. All rights reserved. -%% - --module(bpqueue). - -%% Block-prefixed queue. From the perspective of the queue interface -%% the datastructure acts like a regular queue where each value is -%% paired with the prefix. -%% -%% This is implemented as a queue of queues, which is more space and -%% time efficient, whilst supporting the normal queue interface. Each -%% inner queue has a prefix, which does not need to be unique, and it -%% is guaranteed that no two consecutive blocks have the same -%% prefix. len/1 returns the flattened length of the queue and is -%% O(1). - --export([new/0, is_empty/1, len/1, in/3, in_r/3, out/1, out_r/1, join/2, - foldl/3, foldr/3, from_list/1, to_list/1, map_fold_filter_l/4, - map_fold_filter_r/4]). - -%%---------------------------------------------------------------------------- - --ifdef(use_specs). - --export_type([bpqueue/0]). - --type(bpqueue() :: {non_neg_integer(), queue()}). --type(prefix() :: any()). --type(value() :: any()). --type(result() :: ({'empty', bpqueue()} | - {{'value', prefix(), value()}, bpqueue()})). - --spec(new/0 :: () -> bpqueue()). --spec(is_empty/1 :: (bpqueue()) -> boolean()). --spec(len/1 :: (bpqueue()) -> non_neg_integer()). --spec(in/3 :: (prefix(), value(), bpqueue()) -> bpqueue()). --spec(in_r/3 :: (prefix(), value(), bpqueue()) -> bpqueue()). --spec(out/1 :: (bpqueue()) -> result()). --spec(out_r/1 :: (bpqueue()) -> result()). --spec(join/2 :: (bpqueue(), bpqueue()) -> bpqueue()). --spec(foldl/3 :: (fun ((prefix(), value(), B) -> B), B, bpqueue()) -> B). --spec(foldr/3 :: (fun ((prefix(), value(), B) -> B), B, bpqueue()) -> B). --spec(from_list/1 :: ([{prefix(), [value()]}]) -> bpqueue()). --spec(to_list/1 :: (bpqueue()) -> [{prefix(), [value()]}]). --spec(map_fold_filter_l/4 :: ((fun ((prefix()) -> boolean())), - (fun ((value(), B) -> - ({prefix(), value(), B} | 'stop'))), - B, - bpqueue()) -> - {bpqueue(), B}). --spec(map_fold_filter_r/4 :: ((fun ((prefix()) -> boolean())), - (fun ((value(), B) -> - ({prefix(), value(), B} | 'stop'))), - B, - bpqueue()) -> - {bpqueue(), B}). - --endif. - --define(QUEUE, finger_tree). - -%%---------------------------------------------------------------------------- - -new() -> {0, ?QUEUE:new()}. - -is_empty({0, _Q}) -> true; -is_empty(_BPQ) -> false. - -len({N, _Q}) -> N. - -in(Prefix, Value, {0, Q}) -> - {1, ?QUEUE:in({Prefix, ?QUEUE:from_list([Value])}, Q)}; -in(Prefix, Value, BPQ) -> - in1({fun ?QUEUE:in/2, fun ?QUEUE:out_r/1}, Prefix, Value, BPQ). - -in_r(Prefix, Value, BPQ = {0, _Q}) -> - in(Prefix, Value, BPQ); -in_r(Prefix, Value, BPQ) -> - in1({fun ?QUEUE:in_r/2, fun ?QUEUE:out/1}, Prefix, Value, BPQ). - -in1({In, Out}, Prefix, Value, {N, Q}) -> - {N+1, case Out(Q) of - {{value, {Prefix, InnerQ}}, Q1} -> - In({Prefix, In(Value, InnerQ)}, Q1); - {{value, {_Prefix, _InnerQ}}, _Q1} -> - In({Prefix, ?QUEUE:in(Value, ?QUEUE:new())}, Q) - end}. - -in_q(Prefix, Queue, BPQ = {0, Q}) -> - case ?QUEUE:len(Queue) of - 0 -> BPQ; - N -> {N, ?QUEUE:in({Prefix, Queue}, Q)} - end; -in_q(Prefix, Queue, BPQ) -> - in_q1({fun ?QUEUE:in/2, fun ?QUEUE:out_r/1, - fun ?QUEUE:join/2}, - Prefix, Queue, BPQ). - -in_q_r(Prefix, Queue, BPQ = {0, _Q}) -> - in_q(Prefix, Queue, BPQ); -in_q_r(Prefix, Queue, BPQ) -> - in_q1({fun ?QUEUE:in_r/2, fun ?QUEUE:out/1, - fun (T, H) -> ?QUEUE:join(H, T) end}, - Prefix, Queue, BPQ). - -in_q1({In, Out, Join}, Prefix, Queue, BPQ = {N, Q}) -> - case ?QUEUE:len(Queue) of - 0 -> BPQ; - M -> {N + M, case Out(Q) of - {{value, {Prefix, InnerQ}}, Q1} -> - In({Prefix, Join(InnerQ, Queue)}, Q1); - {{value, {_Prefix, _InnerQ}}, _Q1} -> - In({Prefix, Queue}, Q) - end} - end. - -out({0, _Q} = BPQ) -> {empty, BPQ}; -out(BPQ) -> out1({fun ?QUEUE:in_r/2, fun ?QUEUE:out/1}, BPQ). - -out_r({0, _Q} = BPQ) -> {empty, BPQ}; -out_r(BPQ) -> out1({fun ?QUEUE:in/2, fun ?QUEUE:out_r/1}, BPQ). - -out1({In, Out}, {N, Q}) -> - {{value, {Prefix, InnerQ}}, Q1} = Out(Q), - {{value, Value}, InnerQ1} = Out(InnerQ), - Q2 = case ?QUEUE:is_empty(InnerQ1) of - true -> Q1; - false -> In({Prefix, InnerQ1}, Q1) - end, - {{value, Prefix, Value}, {N-1, Q2}}. - -join({0, _Q}, BPQ) -> - BPQ; -join(BPQ, {0, _Q}) -> - BPQ; -join({NHead, QHead}, {NTail, QTail}) -> - {{value, {Prefix, InnerQHead}}, QHead1} = ?QUEUE:out_r(QHead), - {NHead + NTail, - case ?QUEUE:out(QTail) of - {{value, {Prefix, InnerQTail}}, QTail1} -> - ?QUEUE:join( - ?QUEUE:in({Prefix, ?QUEUE:join(InnerQHead, InnerQTail)}, QHead1), - QTail1); - {{value, {_Prefix, _InnerQTail}}, _QTail1} -> - ?QUEUE:join(QHead, QTail) - end}. - -foldl(_Fun, Init, {0, _Q}) -> Init; -foldl( Fun, Init, {_N, Q}) -> fold1(fun ?QUEUE:out/1, Fun, Init, Q). - -foldr(_Fun, Init, {0, _Q}) -> Init; -foldr( Fun, Init, {_N, Q}) -> fold1(fun ?QUEUE:out_r/1, Fun, Init, Q). - -fold1(Out, Fun, Init, Q) -> - case Out(Q) of - {empty, _Q} -> - Init; - {{value, {Prefix, InnerQ}}, Q1} -> - fold1(Out, Fun, fold1(Out, Fun, Prefix, Init, InnerQ), Q1) - end. - -fold1(Out, Fun, Prefix, Init, InnerQ) -> - case Out(InnerQ) of - {empty, _Q} -> - Init; - {{value, Value}, InnerQ1} -> - fold1(Out, Fun, Prefix, Fun(Prefix, Value, Init), InnerQ1) - end. - -from_list(List) -> - {FinalPrefix, FinalInnerQ, ListOfPQs1, Len} = - lists:foldl( - fun ({_Prefix, []}, Acc) -> - Acc; - ({Prefix, InnerList}, {Prefix, InnerQ, ListOfPQs, LenAcc}) -> - {Prefix, ?QUEUE:join(InnerQ, ?QUEUE:from_list(InnerList)), - ListOfPQs, LenAcc + length(InnerList)}; - ({Prefix1, InnerList}, {Prefix, InnerQ, ListOfPQs, LenAcc}) -> - {Prefix1, ?QUEUE:from_list(InnerList), - [{Prefix, InnerQ} | ListOfPQs], LenAcc + length(InnerList)} - end, {undefined, ?QUEUE:new(), [], 0}, List), - ListOfPQs2 = [{FinalPrefix, FinalInnerQ} | ListOfPQs1], - [{undefined, InnerQ1} | Rest] = All = lists:reverse(ListOfPQs2), - {Len, ?QUEUE:from_list(case ?QUEUE:is_empty(InnerQ1) of - true -> Rest; - false -> All - end)}. - -to_list({0, _Q}) -> []; -to_list({_N, Q}) -> [{Prefix, ?QUEUE:to_list(InnerQ)} || - {Prefix, InnerQ} <- ?QUEUE:to_list(Q)]. - -%% map_fold_filter_[lr](FilterFun, Fun, Init, BPQ) -> {BPQ, Init} -%% where FilterFun(Prefix) -> boolean() -%% Fun(Value, Init) -> {Prefix, Value, Init} | stop -%% -%% The filter fun allows you to skip very quickly over blocks that -%% you're not interested in. Such blocks appear in the resulting bpq -%% without modification. The Fun is then used both to map the value, -%% which also allows you to change the prefix (and thus block) of the -%% value, and also to modify the Init/Acc (just like a fold). If the -%% Fun returns 'stop' then it is not applied to any further items. -map_fold_filter_l(_PFilter, _Fun, Init, BPQ = {0, _Q}) -> - {BPQ, Init}; -map_fold_filter_l(PFilter, Fun, Init, {N, Q}) -> - map_fold_filter1({fun ?QUEUE:out/1, fun ?QUEUE:in/2, - fun in_q/3, fun join/2}, - N, PFilter, Fun, Init, Q, new()). - -map_fold_filter_r(_PFilter, _Fun, Init, BPQ = {0, _Q}) -> - {BPQ, Init}; -map_fold_filter_r(PFilter, Fun, Init, {N, Q}) -> - map_fold_filter1({fun ?QUEUE:out_r/1, fun ?QUEUE:in_r/2, - fun in_q_r/3, fun (T, H) -> join(H, T) end}, - N, PFilter, Fun, Init, Q, new()). - -map_fold_filter1(Funs = {Out, _In, InQ, Join}, Len, PFilter, Fun, - Init, Q, QNew) -> - case Out(Q) of - {empty, _Q} -> - {QNew, Init}; - {{value, {Prefix, InnerQ}}, Q1} -> - case PFilter(Prefix) of - true -> - {Init1, QNew1, Cont} = - map_fold_filter2(Funs, Fun, Prefix, Prefix, - Init, InnerQ, QNew, ?QUEUE:new()), - case Cont of - false -> {Join(QNew1, {Len - len(QNew1), Q1}), Init1}; - true -> map_fold_filter1(Funs, Len, PFilter, Fun, - Init1, Q1, QNew1) - end; - false -> - map_fold_filter1(Funs, Len, PFilter, Fun, - Init, Q1, InQ(Prefix, InnerQ, QNew)) - end - end. - -map_fold_filter2(Funs = {Out, In, InQ, _Join}, Fun, OrigPrefix, Prefix, - Init, InnerQ, QNew, InnerQNew) -> - case Out(InnerQ) of - {empty, _Q} -> - {Init, InQ(OrigPrefix, InnerQ, - InQ(Prefix, InnerQNew, QNew)), true}; - {{value, Value}, InnerQ1} -> - case Fun(Value, Init) of - stop -> - {Init, InQ(OrigPrefix, InnerQ, - InQ(Prefix, InnerQNew, QNew)), false}; - {Prefix1, Value1, Init1} -> - {Prefix2, QNew1, InnerQNew1} = - case Prefix1 =:= Prefix of - true -> {Prefix, QNew, In(Value1, InnerQNew)}; - false -> {Prefix1, InQ(Prefix, InnerQNew, QNew), - In(Value1, ?QUEUE:new())} - end, - map_fold_filter2(Funs, Fun, OrigPrefix, Prefix2, - Init1, InnerQ1, QNew1, InnerQNew1) - end - end. diff --git a/src/finger_tree.erl b/src/finger_tree.erl deleted file mode 100644 index a48a5fc7..00000000 --- a/src/finger_tree.erl +++ /dev/null @@ -1,264 +0,0 @@ -%% The contents of this file are subject to the Mozilla Public License -%% Version 1.1 (the "License"); you may not use this file except in -%% compliance with the License. You may obtain a copy of the License -%% at http://www.mozilla.org/MPL/ -%% -%% Software distributed under the License is distributed on an "AS IS" -%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See -%% the License for the specific language governing rights and -%% limitations under the License. -%% -%% The Original Code is RabbitMQ. -%% -%% The Initial Developer of the Original Code is VMware, Inc. -%% Copyright (c) 2011-2011 VMware, Inc. All rights reserved. -%% - --module(finger_tree). - -%% This is an Erlang implementation of 2-3 finger trees, as defined by -%% Ralf Hinze and Ross Paterson in their "Finger Trees: A Simple -%% General-purpose Data Structure" paper[0]. -%% -%% As usual with a queue-like thing, adding and removing from either -%% end is O(1) amortized. -%% -%% On the whole, nearly everything else is O(log_2(N)), including -%% join. Whilst there are instances of list append (++) in the code, -%% it's only lists that are bounded in length to four items. -%% -%% Because Erlang lacks type classes, it's currently forced to cache -%% sizes. This allows len to be O(1), and permits split_at based on -%% index, which still remains O(log_2(N)) which demonstrates we're -%% able to take advantage of the tree structure. However, it's not -%% difficult to imagine a callback mechanism to allow the monoid -%% implementation to vary. See the paper[0] for examples of other -%% things that could be implemented. -%% -%% [0]: http://www.soi.city.ac.uk/~ross/papers/FingerTree.html - - --compile([export_all]). - --record(finger_tree_single, {elem}). --record(finger_tree_deep, {measured, prefix, middle, suffix}). --record(node, {measured, tuple}). --record(digit, {list}). - -%% queue interface -new() -> finger_tree_empty. - -in(A, FT) -> cons_l(A, FT). -in_r(A, FT) -> cons_r(A, FT). - -out(FT) -> uncons_r(FT). -out_r(FT) -> uncons_l(FT). - -len(FT) -> measure(FT). - -%% To/From list -cons(A, L) -> [A | L]. -to_list(FT) -> reduce_r(fun cons/2, FT, []). -from_list(L) -> reduce_r_in(L, finger_tree_empty). - -is_empty(finger_tree_empty) -> true; -is_empty(#finger_tree_single {}) -> false; -is_empty(#finger_tree_deep {}) -> false. - -%% Smart constructors -digit(A) -> #digit { list = A }. - -node2(A, B) -> - #node { tuple = {A, B}, measured = add(measure(A), measure(B)) }. -node3(A, B, C) -> - #node { tuple = {A, B, C}, - measured = add(add(measure(A), measure(B)), measure(C)) }. - -deep(Prefix, Middle, Suffix) -> - #finger_tree_deep { measured = add(add(measure(Prefix), - measure(Middle)), - measure(Suffix)), - prefix = Prefix, middle = Middle, suffix = Suffix }. - -deep_r(#digit { list = [] }, M, S) -> - case uncons_r(M) of - {empty, _ } -> from_list(S); - {{value, A}, M1} -> deep(digit(to_list(A)), M1, S) - end; -deep_r(P, M, S) -> - deep(P, M, S). - -deep_l(P, M, #digit { list = [] }) -> - case uncons_l(M) of - {empty, _} -> from_list(P); - {{value, A}, M1} -> deep(P, M1, digit(to_list(A))) - end; -deep_l(P, M, S) -> - deep(P, M, S). - -%% Monoid -measure(finger_tree_empty) -> null(); -measure(#finger_tree_single { elem = E }) -> measure(E); -measure(#finger_tree_deep{ measured = V }) -> V; - -measure(#node { measured = V }) -> V; - -measure(#digit { list = Xs }) -> - reduce_l(fun (A, I) -> add(I, measure(A)) end, Xs, null()); - -%% Size implementation of monoid -measure(_) -> 1. - -null() -> 0. -add(A, B) -> A + B. - - -%% Reduce primitives -reduce_r(_Fun, finger_tree_empty, Z) -> Z; -reduce_r(Fun, #finger_tree_single { elem = E }, Z) -> Fun(E, Z); -reduce_r(Fun, #finger_tree_deep { prefix = P, middle = M, suffix = S }, Z) -> - R = reduce_r(fun (A, B) -> reduce_r(Fun, A, B) end, M, reduce_r(Fun, S, Z)), - reduce_r(Fun, P, R); - -reduce_r(Fun, #node { tuple = {A, B} }, Z) -> Fun(A, Fun(B, Z)); -reduce_r(Fun, #node { tuple = {A, B, C} }, Z) -> Fun(A, Fun(B, Fun(C, Z))); - -reduce_r(Fun, #digit { list = List }, Z) -> lists:foldr(Fun, Z, List); - -reduce_r(Fun, X, Z) when is_list(X) -> lists:foldr(Fun, Z, X). - -reduce_l(_Fun, finger_tree_empty, Z) -> Z; -reduce_l(Fun, #finger_tree_single { elem = E }, Z) -> Fun(Z, E); -reduce_l(Fun, #finger_tree_deep { prefix = P, middle = M, suffix = S }, Z) -> - L = reduce_l(fun (A, B) -> reduce_l(Fun, A, B) end, reduce_l(Fun, Z, P), M), - reduce_l(Fun, L, S); - -reduce_l(Fun, #node { tuple = {A, B} }, Z) -> Fun(Fun(Z, B), A); -reduce_l(Fun, #node { tuple = {A, B, C} }, Z) -> Fun(Fun(Fun(Z, C), B), A); - -reduce_l(Fun, #digit { list = List }, Z) -> lists:foldl(Fun, Z, List); - -reduce_l(Fun, X, Z) when is_list(X) -> lists:foldl(Fun, Z, X). - -reduce_r_in(X, FT) -> reduce_r(fun cons_r/2, X, FT). -reduce_l_in(X, FT) -> reduce_l(fun cons_l/2, X, FT). - - -%% Consing -cons_r(A, finger_tree_empty) -> - #finger_tree_single { elem = A }; -cons_r(A, #finger_tree_single { elem = B }) -> - deep(digit([A]), finger_tree_empty, digit([B])); -cons_r(A, #finger_tree_deep { prefix = #digit { list = [B, C, D, E] }, middle = M, suffix = S }) -> - deep(digit([A, B]), cons_r(node3(C, D, E), M), S); -cons_r(A, #finger_tree_deep { prefix = #digit { list = P }, middle = M, suffix = S }) -> - deep(digit([A | P]), M, S). - -cons_l(A, finger_tree_empty) -> - #finger_tree_single { elem = A }; -cons_l(A, #finger_tree_single { elem = B }) -> - deep(digit([B]), finger_tree_empty, digit([A])); -cons_l(A, #finger_tree_deep { prefix = P, middle = M, suffix = #digit { list = [E, D, C, B] } }) -> - deep(P, cons_l(node3(E, D, C), M), digit([B, A])); -cons_l(A, #finger_tree_deep { prefix = P, middle = M, suffix = #digit { list = S } }) -> - deep(P, M, digit(S ++ [A])). - -%% Unconsing -uncons_r(finger_tree_empty = FT) -> - {empty, FT}; -uncons_r(#finger_tree_single { elem = E }) -> - {{value, E}, finger_tree_empty}; -uncons_r(#finger_tree_deep { prefix = #digit { list = [A | P] }, middle = M, suffix = S }) -> - {{value, A}, deep_r(digit(P), M, S)}. - -uncons_l(finger_tree_empty = FT) -> - {empty, FT}; -uncons_l(#finger_tree_single { elem = E }) -> - {{value, E}, finger_tree_empty}; -uncons_l(#finger_tree_deep { prefix = P, middle = M, suffix = #digit { list = S } }) -> - case S of - [A] -> {{value, A}, deep_l(P, M, digit([]))}; - _ -> [A | S1] = lists:reverse(S), - {{value, A}, deep_l(P, M, digit(lists:reverse(S1)))} - end. - -%% Joining -ft_nodes([A, B]) -> [node2(A, B)]; -ft_nodes([A, B, C]) -> [node3(A, B, C)]; -ft_nodes([A, B, C, D]) -> [node2(A, B), node2(C, D)]; -ft_nodes([A, B, C | Xs]) -> [node3(A, B, C) | ft_nodes(Xs)]. - -app3(finger_tree_empty, Ts, Xs) -> - reduce_r_in(Ts, Xs); -app3(Xs, Ts, finger_tree_empty) -> - reduce_l_in(Ts, Xs); -app3(#finger_tree_single { elem = E }, Ts, Xs) -> - cons_r(E, reduce_r_in(Ts, Xs)); -app3(Xs, Ts, #finger_tree_single { elem = E }) -> - cons_l(E, reduce_l_in(Ts, Xs)); -app3(#finger_tree_deep { prefix = P1, middle = M1, suffix = #digit { list = S1 } }, #digit { list = Ts }, - #finger_tree_deep { prefix = #digit { list = P2 }, middle = M2, suffix = S2 }) -> - deep(P1, app3(M1, digit(ft_nodes(S1 ++ (Ts ++ P2))), M2), S2). - -join(FT1, FT2) -> app3(FT1, digit([]), FT2). - -%% Splitting -split_digit(_Pred, _Init, #digit { list = [A] }) -> - {split, digit([]), A, digit([])}; -split_digit(Pred, Init, #digit { list = [A | List] }) -> - Init1 = add(Init, measure(A)), - case Pred(Init1) of - true -> {split, digit([]), A, digit(List)}; - false -> {split, #digit { list = L }, X, R} = split_digit(Pred, Init1, digit(List)), - {split, digit([A | L]), X, R} - end. - -split_node(Pred, Init, #node { tuple = {A, B} }) -> - Init1 = add(Init, measure(A)), - case Pred(Init1) of - true -> {split, digit([]), A, digit([B])}; - false -> {split, digit([A]), B, digit([])} - end; -split_node(Pred, Init, #node { tuple = {A, B, C} }) -> - Init1 = add(Init, measure(A)), - case Pred(Init1) of - true -> {split, digit([]), A, digit([B, C])}; - false -> Init2 = add(Init1, measure(B)), - case Pred(Init2) of - true -> {split, digit([A]), B, digit([C])}; - false -> {split, digit([A, B]), C, digit([])} - end - end. - -split_tree(_Pred, _Init, #finger_tree_single { elem = E }) -> - {split, finger_tree_empty, E, finger_tree_empty}; -split_tree(Pred, Init, #finger_tree_deep { prefix = P, middle = M, suffix = S }) -> - VP = add(Init, measure(P)), - case Pred(VP) of - true -> - {split, #digit { list = L }, X, R} = split_digit(Pred, Init, P), - {split, from_list(L), X, deep_r(R, M, S)}; - false -> - VM = add(VP, measure(M)), - case VM /= VP andalso Pred(VM) of - true -> - {split, ML, Xs, MR} = split_tree(Pred, VP, M), - Init1 = add(VP, measure(ML)), - {split, L, X, R} = split_node(Pred, Init1, Xs), - {split, deep_l(P, ML, L), X, deep_r(R, MR, S)}; - false -> - {split, L, X, #digit { list = R }} = split_digit(Pred, VM, S), - {split, deep_l(P, M, L), X, from_list(R)} - end - end. - -split(_Pred, finger_tree_empty) -> - {finger_tree_empty, finger_tree_empty}; -split(Pred, FT) -> - {split, L, X, R} = split_tree(Pred, null(), FT), - case Pred(measure(FT)) of - true -> {L, cons_r(X, R)}; - false -> {FT, finger_tree_empty} - end. - -split_at(N, FT) -> split(fun (E) -> N < E end, FT). diff --git a/src/fqueue.erl b/src/fqueue.erl deleted file mode 100644 index 6337dea9..00000000 --- a/src/fqueue.erl +++ /dev/null @@ -1,141 +0,0 @@ -%% The contents of this file are subject to the Mozilla Public License -%% Version 1.1 (the "License"); you may not use this file except in -%% compliance with the License. You may obtain a copy of the License -%% at http://www.mozilla.org/MPL/ -%% -%% Software distributed under the License is distributed on an "AS IS" -%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See -%% the License for the specific language governing rights and -%% limitations under the License. -%% -%% The Original Code is RabbitMQ. -%% -%% The Initial Developer of the Original Code is VMware, Inc. -%% Copyright (c) 2011-2011 VMware, Inc. All rights reserved. -%% - --module(fqueue). - -%% This is a queue module, but optimised so that join is O(1). This -%% forces the queue to go deep and then there are some neat pivotting -%% tricks on out and out_r such that we ensure that we don't -%% constantly have to dive deep into the structure. However, in a deep -%% queue case, repeated out and out_r applications will be more -%% expensive. This is the pathological case. - -%% Creation, inspection and conversion --export([new/0,is_queue/1,is_empty/1,len/1,to_list/1,from_list/1,member/2]). -%% Original style API --export([in/2,in_r/2,out/1,out_r/1]). -%% Less garbage style API -%%-export([get/1,get_r/1,peek/1,peek_r/1,drop/1,drop_r/1]). - -%% Higher level API -%%-export([reverse/1,join/2,split/2,filter/2]). --export([join/2]). - --record(fq, {len, head, tail}). - -new() -> #fq { len = 0, head = [], tail = [] }. - -is_queue(#fq { len = L, head = H, tail = T }) - when is_integer(L) andalso is_list(H) andalso is_list(T) -> - true; -is_queue(_) -> - false. - -is_empty(#fq { len = 0 }) -> - true; -is_empty(_) -> - false. - -len(FQ) -> FQ#fq.len. - -to_list(FQ) -> - to_list(false, FQ). - -to_list(true, List) when is_list(List) -> - lists:foldl(fun (#fq{} = Q, Acc) -> to_list(false, Q) ++ Acc; - (V, Acc) -> [unescape(V) | Acc] - end, [], List); -to_list(false, List) when is_list(List) -> - lists:foldr(fun (#fq{} = Q, Acc) -> to_list(true, Q) ++ Acc; - (V, Acc) -> [unescape(V) | Acc] - end, [], List); -to_list(Reverse, #fq { head = H, tail = T }) -> - to_list(Reverse, H) ++ to_list(not Reverse, T). - -from_list(L) -> #fq { len = length(L), head = [escape(V) || V <- L], tail = [] }. - -member(X, #fq { head = H, tail = T }) -> - member(X, H) orelse member(X, T); -member(X, List) when is_list(List) -> - lists:any(fun (E) -> member(X, unescape(E)) end, List); -member(X, X) -> true. - -in(X, #fq { len = 0 } = Q) -> - Q #fq { len = 1, head = [escape(X)] }; -in(X, #fq { len = L, tail = T } = Q) -> - Q #fq { len = L+1, tail = [escape(X) | T] }. - -in_r(X, #fq { len = 0 } = Q) -> - Q #fq { len = 1, tail = [escape(X)] }; -in_r(X, #fq { len = L, head = H } = Q) -> - Q #fq { len = L+1, head = [escape(X) | H] }. - -out(#fq { len = 0 } = Q) -> - {empty, Q}; -out(#fq { head = [#fq{} = IQ], tail = [] }) -> - out(IQ); -out(#fq { tail = [#fq{} = IQ], head = [] }) -> - out(IQ); -out(#fq { len = L, head = [#fq{ len = L1, tail = T1 } = IQ | H], tail = T }) -> - %% Essentially we pivot so that the IQ becomes the outer, and we - %% stuff ourselves at the end - out(IQ #fq { len = L, tail = [#fq { len = L - L1, head = H, tail = T } | T1] }); -out(#fq { len = L, head = [V], tail = T }) -> - {{value, unescape(V)}, #fq { len = L-1, head = lists:reverse(T), tail = [] }}; -out(#fq { len = L, head = [V | H] } = Q) -> - {{value, unescape(V)}, Q #fq { len = L-1, head = H }}; -out(#fq { head = [], tail = T } = Q) -> - out(Q #fq { head = lists:reverse(T), tail = [] }). - -out_r(#fq { len = 0 } = Q) -> - {empty, Q}; -out_r(#fq { tail = [#fq{} = IQ], head = [] }) -> - out_r(IQ); -out_r(#fq { head = [#fq{} = IQ], tail = [] }) -> - out_r(IQ); -out_r(#fq { len = L, tail = [#fq{ len = L1, head = H1 } = IQ | T], head = H }) -> - %% Essentially we pivot so that the IQ becomes the outer, and we - %% stuff ourselves at the start - out_r(IQ #fq { len = L, head = [#fq { len = L - L1, tail = T, head = H } | H1] }); -out_r(#fq { len = L, tail = [V], head = H }) -> - {{value, unescape(V)}, #fq { len = L-1, tail = lists:reverse(H), head = [] }}; -out_r(#fq { len = L, tail = [V | T] } = Q) -> - {{value, unescape(V)}, Q #fq { len = L-1, tail = T }}; -out_r(#fq { tail = [], head = H } = Q) -> - out_r(Q #fq { tail = lists:reverse(H), head = [] }). - -join(Q, #fq { len = 0 }) -> - Q; -join(#fq { len = 0 }, Q) -> - Q; -join(Q, #fq { len = 1 } = Q1) -> - {{value, V}, _} = out(Q1), - in(V, Q); -join(#fq { len = 1 } = Q, Q1) -> - {{value, V}, _} = out(Q), - in_r(V, Q1); -join(#fq { len = L, tail = T } = Q, #fq { len = L1 } = Q1) -> - Q #fq { len = L+L1, tail = [Q1 | T] }. - - --compile({inline, [{escape,1},{unescape,1}]}). - -escape(#fq{} = V) -> {escaped, V}; -escape({escaped, _} = V) -> {escaped, V}; -escape(V) -> V. - -unescape({escaped, V}) -> V; -unescape(V) -> V. diff --git a/src/lqueue.erl b/src/lqueue.erl index ea54ffd4..3ab8c9f0 100644 --- a/src/lqueue.erl +++ b/src/lqueue.erl @@ -21,6 +21,30 @@ -define(QUEUE, queue). +-ifdef(use_specs). + +-export_type([?MODULE/0]). + +-type(?MODULE() :: {non_neg_integer(), ?MODULE()}). +-type(value() :: any()). +-type(result() :: ({'empty', ?MODULE()} | + {{'value', value()}, ?MODULE()})). + +-spec(new/0 :: () -> ?MODULE()). +-spec(is_empty/1 :: (?MODULE()) -> boolean()). +-spec(len/1 :: (?MODULE()) -> non_neg_integer()). +-spec(in/2 :: (value(), ?MODULE()) -> ?MODULE()). +-spec(in_r/2 :: (value(), ?MODULE()) -> ?MODULE()). +-spec(out/1 :: (?MODULE()) -> result()). +-spec(out_r/1 :: (?MODULE()) -> result()). +-spec(join/2 :: (?MODULE(), ?MODULE()) -> ?MODULE()). +-spec(foldl/3 :: (fun ((value(), B) -> B), B, ?MODULE()) -> B). +-spec(foldr/3 :: (fun ((value(), B) -> B), B, ?MODULE()) -> B). +-spec(from_list/1 :: ([value()]) -> ?MODULE()). +-spec(to_list/1 :: (?MODULE()) -> [value()]). + +-endif. + new() -> {0, ?QUEUE:new()}. is_empty({0, _Q}) -> true; diff --git a/src/rabbit_tests.erl b/src/rabbit_tests.erl index e5d6a737..a0d07493 100644 --- a/src/rabbit_tests.erl +++ b/src/rabbit_tests.erl @@ -44,7 +44,6 @@ all_tests() -> passed = test_file_handle_cache(), passed = test_backing_queue(), passed = test_priority_queue(), - passed = test_bpqueue(), passed = test_pg_local(), passed = test_unfold(), passed = test_supervisor_delayed_restart(), @@ -262,143 +261,6 @@ test_priority_queue(Q) -> priority_queue:to_list(Q), priority_queue_out_all(Q)}. -test_bpqueue() -> - Q = bpqueue:new(), - true = bpqueue:is_empty(Q), - 0 = bpqueue:len(Q), - [] = bpqueue:to_list(Q), - - Q1 = bpqueue_test(fun bpqueue:in/3, fun bpqueue:out/1, - fun bpqueue:to_list/1, - fun bpqueue:foldl/3, fun bpqueue:map_fold_filter_l/4), - Q2 = bpqueue_test(fun bpqueue:in_r/3, fun bpqueue:out_r/1, - fun (QR) -> lists:reverse( - [{P, lists:reverse(L)} || - {P, L} <- bpqueue:to_list(QR)]) - end, - fun bpqueue:foldr/3, fun bpqueue:map_fold_filter_r/4), - - [{foo, [1, 2]}, {bar, [3]}] = bpqueue:to_list(bpqueue:join(Q, Q1)), - [{bar, [3]}, {foo, [2, 1]}] = bpqueue:to_list(bpqueue:join(Q2, Q)), - [{foo, [1, 2]}, {bar, [3, 3]}, {foo, [2,1]}] = - bpqueue:to_list(bpqueue:join(Q1, Q2)), - - [{foo, [1, 2]}, {bar, [3]}, {foo, [1, 2]}, {bar, [3]}] = - bpqueue:to_list(bpqueue:join(Q1, Q1)), - - [{foo, [1, 2]}, {bar, [3]}] = - bpqueue:to_list( - bpqueue:from_list( - [{x, []}, {foo, [1]}, {y, []}, {foo, [2]}, {bar, [3]}, {z, []}])), - - [{undefined, [a]}] = bpqueue:to_list(bpqueue:from_list([{undefined, [a]}])), - - {4, [a,b,c,d]} = - bpqueue:foldl( - fun (Prefix, Value, {Prefix, Acc}) -> - {Prefix + 1, [Value | Acc]} - end, - {0, []}, bpqueue:from_list([{0,[d]}, {1,[c]}, {2,[b]}, {3,[a]}])), - - [{bar,3}, {foo,2}, {foo,1}] = - bpqueue:foldr(fun (P, V, I) -> [{P,V} | I] end, [], Q2), - - BPQL = [{foo,[1,2,2]}, {bar,[3,4,5]}, {foo,[5,6,7]}], - BPQ = bpqueue:from_list(BPQL), - - %% no effect - {BPQL, 0} = bpqueue_mffl([none], {none, []}, BPQ), - {BPQL, 0} = bpqueue_mffl([foo,bar], {none, [1]}, BPQ), - {BPQL, 0} = bpqueue_mffl([bar], {none, [3]}, BPQ), - {BPQL, 0} = bpqueue_mffr([bar], {foo, [5]}, BPQ), - - %% process 1 item - {[{foo,[-1,2,2]}, {bar,[3,4,5]}, {foo,[5,6,7]}], 1} = - bpqueue_mffl([foo,bar], {foo, [2]}, BPQ), - {[{foo,[1,2,2]}, {bar,[-3,4,5]}, {foo,[5,6,7]}], 1} = - bpqueue_mffl([bar], {bar, [4]}, BPQ), - {[{foo,[1,2,2]}, {bar,[3,4,5]}, {foo,[5,6,-7]}], 1} = - bpqueue_mffr([foo,bar], {foo, [6]}, BPQ), - {[{foo,[1,2,2]}, {bar,[3,4]}, {baz,[-5]}, {foo,[5,6,7]}], 1} = - bpqueue_mffr([bar], {baz, [4]}, BPQ), - - %% change prefix - {[{bar,[-1,-2,-2,-3,-4,-5,-5,-6,-7]}], 9} = - bpqueue_mffl([foo,bar], {bar, []}, BPQ), - {[{bar,[-1,-2,-2,3,4,5]}, {foo,[5,6,7]}], 3} = - bpqueue_mffl([foo], {bar, [5]}, BPQ), - {[{bar,[-1,-2,-2,3,4,5,-5,-6]}, {foo,[7]}], 5} = - bpqueue_mffl([foo], {bar, [7]}, BPQ), - {[{foo,[1,2,2,-3,-4]}, {bar,[5]}, {foo,[5,6,7]}], 2} = - bpqueue_mffl([bar], {foo, [5]}, BPQ), - {[{bar,[-1,-2,-2,3,4,5,-5,-6,-7]}], 6} = - bpqueue_mffl([foo], {bar, []}, BPQ), - {[{foo,[1,2,2,-3,-4,-5,5,6,7]}], 3} = - bpqueue_mffl([bar], {foo, []}, BPQ), - - %% edge cases - {[{foo,[-1,-2,-2]}, {bar,[3,4,5]}, {foo,[5,6,7]}], 3} = - bpqueue_mffl([foo], {foo, [5]}, BPQ), - {[{foo,[1,2,2]}, {bar,[3,4,5]}, {foo,[-5,-6,-7]}], 3} = - bpqueue_mffr([foo], {foo, [2]}, BPQ), - - passed. - -bpqueue_test(In, Out, List, Fold, MapFoldFilter) -> - Q = bpqueue:new(), - {empty, _Q} = Out(Q), - - ok = Fold(fun (Prefix, Value, ok) -> {error, Prefix, Value} end, ok, Q), - {Q1M, 0} = MapFoldFilter(fun(_P) -> throw(explosion) end, - fun(_V, _N) -> throw(explosion) end, 0, Q), - [] = bpqueue:to_list(Q1M), - - Q1 = In(bar, 3, In(foo, 2, In(foo, 1, Q))), - false = bpqueue:is_empty(Q1), - 3 = bpqueue:len(Q1), - [{foo, [1, 2]}, {bar, [3]}] = List(Q1), - - {{value, foo, 1}, Q3} = Out(Q1), - {{value, foo, 2}, Q4} = Out(Q3), - {{value, bar, 3}, _Q5} = Out(Q4), - - F = fun (QN) -> - MapFoldFilter(fun (foo) -> true; - (_) -> false - end, - fun (2, _Num) -> stop; - (V, Num) -> {bar, -V, V - Num} end, - 0, QN) - end, - {Q6, 0} = F(Q), - [] = bpqueue:to_list(Q6), - {Q7, 1} = F(Q1), - [{bar, [-1]}, {foo, [2]}, {bar, [3]}] = List(Q7), - - Q1. - -bpqueue_mffl(FF1A, FF2A, BPQ) -> - bpqueue_mff(fun bpqueue:map_fold_filter_l/4, FF1A, FF2A, BPQ). - -bpqueue_mffr(FF1A, FF2A, BPQ) -> - bpqueue_mff(fun bpqueue:map_fold_filter_r/4, FF1A, FF2A, BPQ). - -bpqueue_mff(Fold, FF1A, FF2A, BPQ) -> - FF1 = fun (Prefixes) -> - fun (P) -> lists:member(P, Prefixes) end - end, - FF2 = fun ({Prefix, Stoppers}) -> - fun (Val, Num) -> - case lists:member(Val, Stoppers) of - true -> stop; - false -> {Prefix, -Val, 1 + Num} - end - end - end, - Queue_to_list = fun ({LHS, RHS}) -> {bpqueue:to_list(LHS), RHS} end, - - Queue_to_list(Fold(FF1(FF1A), FF2(FF2A), 0, BPQ)). - test_simple_n_element_queue(N) -> Items = lists:seq(1, N), Q = priority_queue_in_all(priority_queue:new(), Items), diff --git a/src/rabbit_variable_queue.erl b/src/rabbit_variable_queue.erl index 310d9357..4712a620 100644 --- a/src/rabbit_variable_queue.erl +++ b/src/rabbit_variable_queue.erl @@ -316,11 +316,11 @@ end_seq_id :: non_neg_integer() }). -type(state() :: #vqstate { - q1 :: queue(), - q2 :: queue(), + q1 :: ?QUEUE:?QUEUE(), + q2 :: ?QUEUE:?QUEUE(), delta :: delta(), - q3 :: queue(), - q4 :: queue(), + q3 :: ?QUEUE:?QUEUE(), + q4 :: ?QUEUE:?QUEUE(), next_seq_id :: seq_id(), pending_ack :: gb_tree(), ram_ack_index :: gb_tree(), -- cgit v1.2.1