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

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}.