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
52static void ON_shortsort(ON_SORT_TEMPLATE_TYPE *, ON_SORT_TEMPLATE_TYPE *);
53static 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