aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorFredrik Gustafsson <[email protected]>2013-01-22 14:17:39 +0100
committerFredrik Gustafsson <[email protected]>2013-01-22 14:17:39 +0100
commitf7059ffbf0d9e7767eba1d4d96b291bfc96ef767 (patch)
tree7431eae34b47c8137a07c0ec09de951d9d2a89c4
parentb2db56fb68f24b6438e55972297c77728d2cb6a5 (diff)
parentf4916887e09a2bc9b0301ce0751e2e5b057cb592 (diff)
downloadotp-f7059ffbf0d9e7767eba1d4d96b291bfc96ef767.tar.gz
otp-f7059ffbf0d9e7767eba1d4d96b291bfc96ef767.tar.bz2
otp-f7059ffbf0d9e7767eba1d4d96b291bfc96ef767.zip
Merge branch 'ae/stdlib/faster_queue/OTP-10722'
* ae/stdlib/faster_queue/OTP-10722: Fix bug in queue:out/1, queue:out_r/1 that makes it O(N^2) in worst case
-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}.