/* * 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);\ }\ }