Commit | Line | Data |
---|---|---|
2ba45a60 DM |
1 | /* |
2 | * copyright (c) 2012 Michael Niedermayer <michaelni@gmx.at> | |
3 | * | |
4 | * This file is part of FFmpeg. | |
5 | * | |
6 | * FFmpeg is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU Lesser General Public | |
8 | * License as published by the Free Software Foundation; either | |
9 | * version 2.1 of the License, or (at your option) any later version. | |
10 | * | |
11 | * FFmpeg is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * Lesser General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU Lesser General Public | |
17 | * License along with FFmpeg; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
19 | */ | |
20 | ||
21 | #include "common.h" | |
22 | ||
23 | ||
24 | /** | |
25 | * Quicksort | |
26 | * This sort is fast, and fully inplace but not stable and it is possible | |
27 | * to construct input that requires O(n^2) time but this is very unlikely to | |
28 | * happen with non constructed input. | |
29 | */ | |
30 | #define AV_QSORT(p, num, type, cmp) {\ | |
31 | void *stack[64][2];\ | |
32 | int sp= 1;\ | |
33 | stack[0][0] = p;\ | |
34 | stack[0][1] = (p)+(num)-1;\ | |
35 | while(sp){\ | |
36 | type *start= stack[--sp][0];\ | |
37 | type *end = stack[ sp][1];\ | |
38 | while(start < end){\ | |
39 | if(start < end-1) {\ | |
40 | int checksort=0;\ | |
41 | type *right = end-2;\ | |
42 | type *left = start+1;\ | |
43 | type *mid = start + ((end-start)>>1);\ | |
44 | if(cmp(start, end) > 0) {\ | |
45 | if(cmp( end, mid) > 0) FFSWAP(type, *start, *mid);\ | |
46 | else FFSWAP(type, *start, *end);\ | |
47 | }else{\ | |
48 | if(cmp(start, mid) > 0) FFSWAP(type, *start, *mid);\ | |
49 | else checksort= 1;\ | |
50 | }\ | |
51 | if(cmp(mid, end) > 0){ \ | |
52 | FFSWAP(type, *mid, *end);\ | |
53 | checksort=0;\ | |
54 | }\ | |
55 | if(start == end-2) break;\ | |
56 | FFSWAP(type, end[-1], *mid);\ | |
57 | while(left <= right){\ | |
58 | while(left<=right && cmp(left, end-1) < 0)\ | |
59 | left++;\ | |
60 | while(left<=right && cmp(right, end-1) > 0)\ | |
61 | right--;\ | |
62 | if(left <= right){\ | |
63 | FFSWAP(type, *left, *right);\ | |
64 | left++;\ | |
65 | right--;\ | |
66 | }\ | |
67 | }\ | |
68 | FFSWAP(type, end[-1], *left);\ | |
69 | if(checksort && (mid == left-1 || mid == left)){\ | |
70 | mid= start;\ | |
71 | while(mid<end && cmp(mid, mid+1) <= 0)\ | |
72 | mid++;\ | |
73 | if(mid==end)\ | |
74 | break;\ | |
75 | }\ | |
76 | if(end-left < left-start){\ | |
77 | stack[sp ][0]= start;\ | |
78 | stack[sp++][1]= right;\ | |
79 | start = left+1;\ | |
80 | }else{\ | |
81 | stack[sp ][0]= left+1;\ | |
82 | stack[sp++][1]= end;\ | |
83 | end = right;\ | |
84 | }\ | |
85 | }else{\ | |
86 | if(cmp(start, end) > 0)\ | |
87 | FFSWAP(type, *start, *end);\ | |
88 | break;\ | |
89 | }\ | |
90 | }\ | |
91 | }\ | |
92 | } | |
93 | ||
94 | /** | |
95 | * Merge sort, this sort requires a temporary buffer and is stable, its worst | |
96 | * case time is O(n log n) | |
97 | * @param p must be a lvalue pointer, this function may exchange it with tmp | |
98 | * @param tmp must be a lvalue pointer, this function may exchange it with p | |
99 | */ | |
100 | #define AV_MSORT(p, tmp, num, type, cmp) {\ | |
101 | unsigned i, j, step;\ | |
102 | for(step=1; step<(num); step+=step){\ | |
103 | for(i=0; i<(num); i+=2*step){\ | |
104 | unsigned a[2] = {i, i+step};\ | |
105 | unsigned end = FFMIN(i+2*step, (num));\ | |
106 | for(j=i; a[0]<i+step && a[1]<end; j++){\ | |
107 | int idx= cmp(p+a[0], p+a[1]) > 0;\ | |
108 | tmp[j] = p[ a[idx]++ ];\ | |
109 | }\ | |
110 | if(a[0]>=i+step) a[0] = a[1];\ | |
111 | for(; j<end; j++){\ | |
112 | tmp[j] = p[ a[0]++ ];\ | |
113 | }\ | |
114 | }\ | |
115 | FFSWAP(type*, p, tmp);\ | |
116 | }\ | |
117 | } |