+// Quick Sort algorithm adapted from public domain code by Darel Rex Finley
+static inline void quickSort(void *base, uintsize nel, uintsize w, char * piv, int (*compare)(void *, const void *, const void *), void *arg)
+{
+ #define MAX_LEVELS 300
+ uintsize beg[MAX_LEVELS], end[MAX_LEVELS];
+ int frame = 0;
+
+ beg[0] = 0;
+ end[0] = nel;
+ while(frame >= 0)
+ {
+ uintsize L = beg[frame], R = end[frame]-1;
+ if(L < R)
+ {
+ memcpy(piv, (char *)base + L*w, w);
+ while(L < R)
+ {
+ while(compare(arg, (char *)base + (R*w), piv) >= 0 && L < R) R--;
+ if(L < R)
+ {
+ memcpy((char *)base + L*w, (char *)base + R*w, w);
+ L++;
+ }
+ while(compare(arg, (char *)base + (L*w), piv) <= 0 && L < R) L++;
+ if(L < R)
+ {
+ memcpy((char *)base + R*w, (char *)base + L*w, w);
+ R--;
+ }
+ }
+ memcpy((char *)base + L*w, piv, w);
+ beg[frame+1] = L+1;
+ end[frame+1] = end[frame];
+ end[frame++] = L;
+
+ // Process smaller partition first
+ if(end[frame]-beg[frame] > end[frame-1]-beg[frame-1])
+ {
+ uintsize swap;
+ swap = beg[frame]; beg[frame] = beg[frame-1]; beg[frame-1] = swap;
+ swap = end[frame]; end[frame] = end[frame-1]; end[frame-1] = swap;
+ }
+ }
+ else
+ frame--;
+ }
+ #undef MAX_LEVELS
+}
+
+static struct SortRData { void *arg; int (*compare)(void *, const void *, const void *); };
+
+static inline int compareDeref (SortRData cs, const void **a, const void **b) { return cs.compare(cs.arg, *a, *b); }
+static inline int compareDescDeref (SortRData cs, const void **a, const void **b) { return -cs.compare(cs.arg, *a, *b); }
+static inline int compareDesc (SortRData cs, const void * a, const void * b) { return -cs.compare(cs.arg, a, b); }
+
+static inline int compareArgLast (const void * a, const void * b, SortRData cs) { return cs.compare(cs.arg, a, b); }
+static inline int compareDerefArgLast (const void **a, const void **b, SortRData cs) { return cs.compare(cs.arg, *a, *b); }
+static inline int compareDescDerefArgLast (const void **a, const void **b, SortRData cs) { return -cs.compare(cs.arg, *a, *b); }
+static inline int compareDescArgLast (const void * a, const void * b, SortRData cs) { return -cs.compare(cs.arg, a, b); }
+
+static inline void _qsortrx(void *base, uintsize nel, uintsize width,
+ int (*compare)(void *arg, const void *a, const void *b),
+ int (*optCompareArgLast)(const void *a, const void *b, void *arg),
+ void *arg,
+ bool deref, bool ascending)
+{
+#if defined(GLIBC) && !defined(ECERE_BOOTSTRAP)
+ if(!deref && ascending && optCompareArgLast)
+ qsort_r(base, nel, width, optCompareArgLast, arg);
+ else
+ {
+ SortRData s { arg, compare };
+ #define compare_fn !deref && ascending ? compareArgLast : !deref ? compareDescArgLast : ascending ? compareDerefArgLast : compareDescDerefArgLast
+ qsort_r(base, nel, width, compare_fn, s);
+ #undef compare_fn
+ }
+#else
+ if(!deref && ascending)
+ {
+ #if defined(BSD) && !defined(ECERE_BOOTSTRAP)
+ qsort_r(base, nel, width, arg, compare);
+ #elif defined(__WIN32__) && !defined(ECERE_BOOTSTRAP)
+ qsort_s(base, nel, width, compare, arg);
+ #else
+ {
+ char * buf = new char[width];
+ quickSort(base, nel, width, buf, compare, arg);
+ delete buf;
+ }
+ #endif
+ }
+ else
+ {
+ SortRData s { arg, compare };
+ #define compare_fn !deref ? compareDesc : ascending ? compareDeref : compareDescDeref
+ #if defined(BSD) && !defined(ECERE_BOOTSTRAP)
+ qsort_r(base, nel, width, s, compare_fn);
+ #elif defined(__WIN32__) && !defined(ECERE_BOOTSTRAP)
+ qsort_s(base, nel, width, compare_fn, s);
+ #else
+ {
+ char * buf = new char[width];
+ quickSort(base, nel, width, buf, compare_fn, s);
+ delete buf;
+ }
+ #endif
+ #undef compare_fn
+ }
+#endif
+}
+
+public void qsortrx(void *base, uintsize nel, uintsize width,
+ int (*compare)(void *arg, const void *a, const void *b),
+ int (*optCompareArgLast)(const void *a, const void *b, void *arg),
+ void *arg,
+ bool deref, bool ascending)
+{
+ _qsortrx(base, nel, width, compare, optCompareArgLast, arg, deref, ascending);
+}
+
+public void qsortr(void *base, uintsize nel, uintsize width, int (*compare)(void *arg, const void *a, const void *b), void *arg)
+{
+ _qsortrx(base, nel, width, compare, null, arg, false, true);
+}
+