21 #ifndef AVUTIL_QSORT_H 22 #define AVUTIL_QSORT_H 33 #define AV_QSORT(p, num, type, cmp) do {\ 37 stack[0][1] = (p)+(num)-1;\ 39 type *start= stack[--sp][0];\ 40 type *end = stack[ sp][1];\ 45 type *left = start+1;\ 46 type *mid = start + ((end-start)>>1);\ 47 if(cmp(start, end) > 0) {\ 48 if(cmp( end, mid) > 0) FFSWAP(type, *start, *mid);\ 49 else FFSWAP(type, *start, *end);\ 51 if(cmp(start, mid) > 0) FFSWAP(type, *start, *mid);\ 54 if(cmp(mid, end) > 0){ \ 55 FFSWAP(type, *mid, *end);\ 58 if(start == end-2) break;\ 59 FFSWAP(type, end[-1], *mid);\ 60 while(left <= right){\ 61 while(left<=right && cmp(left, end-1) < 0)\ 63 while(left<=right && cmp(right, end-1) > 0)\ 66 FFSWAP(type, *left, *right);\ 71 FFSWAP(type, end[-1], *left);\ 72 if(checksort && (mid == left-1 || mid == left)){\ 74 while(mid<end && cmp(mid, mid+1) <= 0)\ 79 if(end-left < left-start){\ 80 stack[sp ][0]= start;\ 81 stack[sp++][1]= right;\ 84 stack[sp ][0]= left+1;\ 89 if(cmp(start, end) > 0)\ 90 FFSWAP(type, *start, *end);\ 103 #define AV_MSORT(p, tmp, num, type, cmp) do {\ 104 unsigned i, j, step;\ 105 for(step=1; step<(num); step+=step){\ 106 for(i=0; i<(num); i+=2*step){\ 107 unsigned a[2] = {i, i+step};\ 108 unsigned end = FFMIN(i+2*step, (num));\ 109 for(j=i; a[0]<i+step && a[1]<end; j++){\ 110 int idx= cmp(p+a[0], p+a[1]) > 0;\ 111 tmp[j] = p[ a[idx]++ ];\ 113 if(a[0]>=i+step) a[0] = a[1];\ 115 tmp[j] = p[ a[0]++ ];\ 118 FFSWAP(type*, p, tmp);\ common internal and external API header