6 #if !defined(ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS) 11 #error Do not compile openurbs_qsort_template.c directly. 14 #define ON_QSORT_CUTOFF 8 22 #define ON_QSORT_STKSIZ (8*sizeof(void*) - 2) 26 #if !defined(ON_SORT_TEMPLATE_TYPE) 27 #error Define ON_SORT_TEMPLATE_TYPE macro before including opennurbs_qsort_template.c 30 #if !defined(ON_QSORT_FNAME) 31 #error Define ON_QSORT_FNAME macro before including opennurbs_qsort_template.c 34 #if defined(ON_SORT_TEMPLATE_COMPARE) 36 #define ON_QSORT_GT(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) > 0 37 #define ON_QSORT_LE(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) <= 0 38 #define ON_QSORT_EQ(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) == 0 41 #define ON_QSORT_GT(A,B) *A > *B 42 #define ON_QSORT_LE(A,B) *A <= *B 43 #define ON_QSORT_EQ(A,B) *A == *B 46 #if defined(ON_SORT_TEMPLATE_USE_MEMCPY) 47 #define ON_QSORT_SWAP(A,B) memcpy(&tmp,A,sizeof(tmp));memcpy(A,B,sizeof(tmp));memcpy(B,&tmp,sizeof(tmp)) 49 #define ON_QSORT_SWAP(A,B) tmp = *A; *A = *B; *B = tmp 52 static void ON_shortsort(ON_SORT_TEMPLATE_TYPE *, ON_SORT_TEMPLATE_TYPE *);
53 static void ON_shortsort(ON_SORT_TEMPLATE_TYPE *lo, ON_SORT_TEMPLATE_TYPE *hi)
55 ON_SORT_TEMPLATE_TYPE *p;
56 ON_SORT_TEMPLATE_TYPE *max;
57 ON_SORT_TEMPLATE_TYPE tmp;
66 for (p = lo+1; p <= hi; p++)
69 if ( ON_QSORT_GT(p,max) )
78 ON_QSORT_SWAP(max,hi);
94 #if defined(ON_SORT_TEMPLATE_STATIC_FUNCTION) 99 ON_SORT_TEMPLATE_TYPE *base,
103 ON_SORT_TEMPLATE_TYPE *lo;
104 ON_SORT_TEMPLATE_TYPE *hi;
105 ON_SORT_TEMPLATE_TYPE *mid;
106 ON_SORT_TEMPLATE_TYPE *loguy;
107 ON_SORT_TEMPLATE_TYPE *higuy;
108 ON_SORT_TEMPLATE_TYPE *lostk[ON_QSORT_STKSIZ];
109 ON_SORT_TEMPLATE_TYPE *histk[ON_QSORT_STKSIZ];
112 ON_SORT_TEMPLATE_TYPE tmp;
114 if ( 0 == base || num < 2 )
127 size = (hi - lo) + 1;
130 if (size <= ON_QSORT_CUTOFF)
132 ON_shortsort(lo, hi);
144 mid = lo + (size / 2);
147 if ( ON_QSORT_GT(lo,mid) ) {ON_QSORT_SWAP(lo,mid);}
148 if ( ON_QSORT_GT(lo,hi) ) {ON_QSORT_SWAP(lo,hi);}
149 if ( ON_QSORT_GT(mid,hi) ) {ON_QSORT_SWAP(mid,hi);}
176 }
while (loguy < mid && ON_QSORT_LE(loguy,mid));
182 }
while (loguy <= hi && ON_QSORT_LE(loguy,mid));
190 }
while (higuy > mid && ON_QSORT_GT(higuy,mid));
202 ON_QSORT_SWAP(loguy,higuy);
232 }
while (higuy > mid && ON_QSORT_EQ(higuy,mid));
237 }
while (higuy > lo && ON_QSORT_EQ(higuy,mid));
253 if ( higuy - lo >= hi - loguy ) {
256 histk[stkptr] = higuy;
267 lostk[stkptr] = loguy;
296 #undef ON_QSORT_CUTOFF 297 #undef ON_QSORT_STKSIZ