aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAleksandr Erofeev <[email protected]>2013-01-17 18:21:23 +0400
committerAleksandr Erofeev <[email protected]>2013-01-17 18:21:23 +0400
commitf4916887e09a2bc9b0301ce0751e2e5b057cb592 (patch)
tree221b38014a5ad16d8d8da84b1732057010803106
parent1cbd897c43f0dab1275392a3736e4629c1f80243 (diff)
downloadotp-f4916887e09a2bc9b0301ce0751e2e5b057cb592.tar.gz
otp-f4916887e09a2bc9b0301ce0751e2e5b057cb592.tar.bz2
otp-f4916887e09a2bc9b0301ce0751e2e5b057cb592.zip
Fix bug in queue:out/1, queue:out_r/1 that makes it O(N^2) in worst case
Running out and out_r one after another many times will copy one list back and forth if another is empty. Change r2f and f2r to copy only half of big list so such cases will happen more rarely
-rw-r--r--lib/stdlib/src/queue.erl14
1 files changed, 8 insertions, 6 deletions
diff --git a/lib/stdlib/src/queue.erl b/lib/stdlib/src/queue.erl
index afe917b151..bc1bd06534 100644
--- a/lib/stdlib/src/queue.erl
+++ b/lib/stdlib/src/queue.erl
@@ -472,22 +472,24 @@ init(Q) -> drop_r(Q).
-compile({inline, [{r2f,1},{f2r,1}]}).
-%% Move all but two from R to F, if there are at least three
+%% Move half of elements from R to F, if there are at least three
r2f([]) ->
{[],[]};
r2f([_]=R) ->
{[],R};
r2f([X,Y]) ->
{[X],[Y]};
-r2f([X,Y|R]) ->
- {[X,Y],lists:reverse(R, [])}.
+r2f(List) ->
+ {FF,RR} = lists:split(length(List) div 2 + 1, List),
+ {FF,lists:reverse(RR, [])}.
-%% Move all but two from F to R, if there are enough
+%% Move half of elements from F to R, if there are enough
f2r([]) ->
{[],[]};
f2r([_]=F) ->
{F,[]};
f2r([X,Y]) ->
{[Y],[X]};
-f2r([X,Y|F]) ->
- {lists:reverse(F, []),[X,Y]}.
+f2r(List) ->
+ {FF,RR} = lists:split(length(List) div 2 + 1, List),
+ {lists:reverse(RR, []),FF}.