qsort.h (4315B)
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 #ifndef AVUTIL_QSORT_H 22 #define AVUTIL_QSORT_H 23 24 #include "macros.h" 25 26 27 /** 28 * Quicksort 29 * This sort is fast, and fully inplace but not stable and it is possible 30 * to construct input that requires O(n^2) time but this is very unlikely to 31 * happen with non constructed input. 32 */ 33 #define AV_QSORT(p, num, type, cmp) do {\ 34 void *stack[64][2];\ 35 int sp= 1;\ 36 stack[0][0] = p;\ 37 stack[0][1] = (p)+(num)-1;\ 38 while(sp){\ 39 type *start= stack[--sp][0];\ 40 type *end = stack[ sp][1];\ 41 while(start < end){\ 42 if(start < end-1) {\ 43 int checksort=0;\ 44 type *right = end-2;\ 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);\ 50 }else{\ 51 if(cmp(start, mid) > 0) FFSWAP(type, *start, *mid);\ 52 else checksort= 1;\ 53 }\ 54 if(cmp(mid, end) > 0){ \ 55 FFSWAP(type, *mid, *end);\ 56 checksort=0;\ 57 }\ 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)\ 62 left++;\ 63 while(left<=right && cmp(right, end-1) > 0)\ 64 right--;\ 65 if(left <= right){\ 66 FFSWAP(type, *left, *right);\ 67 left++;\ 68 right--;\ 69 }\ 70 }\ 71 FFSWAP(type, end[-1], *left);\ 72 if(checksort && (mid == left-1 || mid == left)){\ 73 mid= start;\ 74 while(mid<end && cmp(mid, mid+1) <= 0)\ 75 mid++;\ 76 if(mid==end)\ 77 break;\ 78 }\ 79 if(end-left < left-start){\ 80 stack[sp ][0]= start;\ 81 stack[sp++][1]= right;\ 82 start = left+1;\ 83 }else{\ 84 stack[sp ][0]= left+1;\ 85 stack[sp++][1]= end;\ 86 end = right;\ 87 }\ 88 }else{\ 89 if(cmp(start, end) > 0)\ 90 FFSWAP(type, *start, *end);\ 91 break;\ 92 }\ 93 }\ 94 }\ 95 } while (0) 96 97 /** 98 * Merge sort, this sort requires a temporary buffer and is stable, its worst 99 * case time is O(n log n) 100 * @param p must be a lvalue pointer, this function may exchange it with tmp 101 * @param tmp must be a lvalue pointer, this function may exchange it with p 102 */ 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]++ ];\ 112 }\ 113 if(a[0]>=i+step) a[0] = a[1];\ 114 for(; j<end; j++){\ 115 tmp[j] = p[ a[0]++ ];\ 116 }\ 117 }\ 118 FFSWAP(type*, p, tmp);\ 119 }\ 120 } while (0) 121 122 #endif /* AVUTIL_QSORT_H */