diff options
| author | Fredrik Gustafsson <[email protected]> | 2013-01-22 14:17:39 +0100 |
|---|---|---|
| committer | Fredrik Gustafsson <[email protected]> | 2013-01-22 14:17:39 +0100 |
| commit | f7059ffbf0d9e7767eba1d4d96b291bfc96ef767 (patch) | |
| tree | 7431eae34b47c8137a07c0ec09de951d9d2a89c4 /lib/stdlib/src | |
| parent | b2db56fb68f24b6438e55972297c77728d2cb6a5 (diff) | |
| parent | f4916887e09a2bc9b0301ce0751e2e5b057cb592 (diff) | |
| download | otp-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
Diffstat (limited to 'lib/stdlib/src')
| -rw-r--r-- | lib/stdlib/src/queue.erl | 14 |
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}. |