diff options
Diffstat (limited to 'ffmpeg1/libavutil/qsort.h')
| -rw-r--r-- | ffmpeg1/libavutil/qsort.h | 117 |
1 files changed, 0 insertions, 117 deletions
diff --git a/ffmpeg1/libavutil/qsort.h b/ffmpeg1/libavutil/qsort.h deleted file mode 100644 index 30edcc8..0000000 --- a/ffmpeg1/libavutil/qsort.h +++ /dev/null @@ -1,117 +0,0 @@ -/* - * copyright (c) 2012 Michael Niedermayer <michaelni@gmx.at> - * - * This file is part of FFmpeg. - * - * FFmpeg is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * FFmpeg is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with FFmpeg; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#include "common.h" - - -/** - * Quicksort - * This sort is fast, and fully inplace but not stable and it is possible - * to construct input that requires O(n^2) time but this is very unlikely to - * happen with non constructed input. - */ -#define AV_QSORT(p, num, type, cmp) {\ - void *stack[64][2];\ - int sp= 1;\ - stack[0][0] = p;\ - stack[0][1] = (p)+(num)-1;\ - while(sp){\ - type *start= stack[--sp][0];\ - type *end = stack[ sp][1];\ - while(start < end){\ - if(start < end-1) {\ - int checksort=0;\ - type *right = end-2;\ - type *left = start+1;\ - type *mid = start + ((end-start)>>1);\ - if(cmp(start, end) > 0) {\ - if(cmp( end, mid) > 0) FFSWAP(type, *start, *mid);\ - else FFSWAP(type, *start, *end);\ - }else{\ - if(cmp(start, mid) > 0) FFSWAP(type, *start, *mid);\ - else checksort= 1;\ - }\ - if(cmp(mid, end) > 0){ \ - FFSWAP(type, *mid, *end);\ - checksort=0;\ - }\ - if(start == end-2) break;\ - FFSWAP(type, end[-1], *mid);\ - while(left <= right){\ - while(left<=right && cmp(left, end-1) < 0)\ - left++;\ - while(left<=right && cmp(right, end-1) > 0)\ - right--;\ - if(left <= right){\ - FFSWAP(type, *left, *right);\ - left++;\ - right--;\ - }\ - }\ - FFSWAP(type, end[-1], *left);\ - if(checksort && (mid == left-1 || mid == left)){\ - mid= start;\ - while(mid<end && cmp(mid, mid+1) <= 0)\ - mid++;\ - if(mid==end)\ - break;\ - }\ - if(end-left < left-start){\ - stack[sp ][0]= start;\ - stack[sp++][1]= right;\ - start = left+1;\ - }else{\ - stack[sp ][0]= left+1;\ - stack[sp++][1]= end;\ - end = right;\ - }\ - }else{\ - if(cmp(start, end) > 0)\ - FFSWAP(type, *start, *end);\ - break;\ - }\ - }\ - }\ -} - -/** - * Merge sort, this sort requires a temporary buffer and is stable, its worst - * case time is O(n log n) - * @param p must be a lvalue pointer, this function may exchange it with tmp - * @param tmp must be a lvalue pointer, this function may exchange it with p - */ -#define AV_MSORT(p, tmp, num, type, cmp) {\ - unsigned i, j, step;\ - for(step=1; step<(num); step+=step){\ - for(i=0; i<(num); i+=2*step){\ - unsigned a[2] = {i, i+step};\ - unsigned end = FFMIN(i+2*step, (num));\ - for(j=i; a[0]<i+step && a[1]<end; j++){\ - int idx= cmp(p+a[0], p+a[1]) > 0;\ - tmp[j] = p[ a[idx]++ ];\ - }\ - if(a[0]>=i+step) a[0] = a[1];\ - for(; j<end; j++){\ - tmp[j] = p[ a[0]++ ];\ - }\ - }\ - FFSWAP(type*, p, tmp);\ - }\ -} |