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

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