diff options
| author | Aleksandr Erofeev <[email protected]> | 2013-01-17 18:21:23 +0400 |
|---|---|---|
| committer | Aleksandr Erofeev <[email protected]> | 2013-01-17 18:21:23 +0400 |
| commit | f4916887e09a2bc9b0301ce0751e2e5b057cb592 (patch) | |
| tree | 221b38014a5ad16d8d8da84b1732057010803106 /lib/stdlib | |
| parent | 1cbd897c43f0dab1275392a3736e4629c1f80243 (diff) | |
| download | otp-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
Diffstat (limited to 'lib/stdlib')
| -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}. |