# Commits

committed 06d1907

backing up work.

• Participants
• Parent commits df51a08

# Files changed (55)

There are two primary subdirectories to look  at:

1. usort - contains optimized sorting routines for each of the basic c numeric types.  The "u" is
-for universal... where the universe refers to the set of basic c numeric types.
-2. qsort - a general purpose quicksort routine.
+for universal... where the universe refers to the set of basic c numeric types.
+2. qsort - a general purpose comparison based routine.

To use the code, simply #include the appropriate function.

# File TODO

-check for loose macros
+probogate isort to qsort.

# File common/defs.c

+/* c 2009 Andrew I. Schein
+CSORT -- defs for comparison sorting.  Includer should undef all the macros
+*/
+
+#ifndef CSORT_DEFS
+
+# ifndef CS_
+# error __FILE__ " included without defining CS_ macro."
+# endif
+# ifndef CSORT_TY
+#  error __FILE__ " included without defining CSORT_TY macro."
+# endif
+
+# ifndef CSORT_EQ
+#  define CSORT_EQ(a,b) (*(a) == *(b))
+# endif
+# ifndef CSORT_LT
+#  define CSORT_LT(a,b) (*(a) < *(b))
+# endif
+# ifndef CSORT_LE
+#  define CSORT_LE(a,b) (*(a) <= *(b))
+# endif
+
+static inline void CS_(csort_swap)(CSORT_TY *a, CSORT_TY *b) {
+    /* would like to make a macro--but caller tends to increment args. */
+    CSORT_TY swap = *a;
+    *a            = *b;
+    *b            = swap;
+}
+
+static inline void CS_(ins_sort)(CSORT_TY* a, const long long len) {
+    CSORT_TY *x=a+1,*y;
+    for (;x < a + len;x++)
+        for ( y=x; y>a && CSORT_LT(y,(y-1)); y-- )
+            CS_(csort_swap)(y,y-1);
+}
+
+#else
+/* this checks ensures that undefs are complete-- will be important when using multiple
+   includes */
+#  error __FILE__ " included more than once without explicit undefs. "
+#endif /* CSORT */

# File hsort/hsort.c

#  define HSORT_LE(a,b) (*(a) <= *(b))
#endif

-#define HSORT_MIN(a,b) ((a) < (b) ? (a) : (b))

static inline void HS_(SWAP)(HSORT_TY *a, HSORT_TY *b) {
/* made a function since arguments tend to be incremented by caller */

# File isort/isort.c

-   A fast general-purpose insertion sort implemention.
-*/
-
-#include "../common/defs.c" /* comparisons
-
-
-#if !defined LIBBING_AS_ISORT
-#  define ISORT_LKG static inline
-#else
-#  define ISORT_LKG
-#endif
-
-
-#ifndef IS_
-#  define IS_(name) IS_##name
-#endif
-
-#ifndef ISORT_SWAP
-/* swap is implemented as local macro to avoid pollution of name space */
-#define ISORT_SWAP(y) { swap = *(y); *(y) = *((y)-1) ; *((y)-1) = swap; }
-#endif
-
-#include <stdlib.h>
-
-static inline void IS_(isort)(ISORT_TY* a, const long long n) {
-    ISORT_TY *x=a+1,*y=NULL,swap;
-    for (;x < a + n; x++) {
-        for ( y=x; y>a && ISORT_LT(y,(y-1)); y-- )
-            ISORT_SWAP(y);
-    }
-}
-
-#undef ISORT_LT
-#undef ISORT_TY
-#undef ISORT_SWAP
-#undef IS_
-

# File isort/t/s2.c

#define TY short
#define TY_FMT "%i"
#include "../ufunc/s2_isort.c"
-#define QS s2_isort
+#define QS s2_ins_sort
#include "isort-cmp.c"
+

# File isort/t/s8.c

#define TY long long
#define TY_FMT "%lli"
#include "../ufunc/s8_isort.c"
-#define QS s8_isort
+#define QS s8_ins_sort
#include "isort-cmp.c"

# File isort/ufunc/s1_isort.c

-#define ISORT_LT(a,b) (*(a) < *(b))
-#define ISORT_TY char
-#define IS_(name) s1_##name
-#include "isort/isort.c"
+
+#define CSORT_TY signed char
+#define CS_(name) s1_##name
+
+#include "../../common/defs.c"

# File isort/ufunc/s2_isort.c

-#define ISORT_LT(a,b) (*(a) < *(b))
-#define ISORT_TY signed short
-#define IS_(name) s2_##name
-#include "isort/isort.c"
+
+#define CSORT_TY signed short
+#define CS_(name) s2_##name
+
+#include "../../common/defs.c"

# File isort/ufunc/s8_isort.c

-#define ISORT_LT(a,b) (*(a) < *(b))
-#define ISORT_TY long long
-#define IS_(name) s8_##name
-#include "isort/isort.c"
+#define CSORT_TY long long
+#define CS_(name) s8_##name
+#include "../../common/defs.c"

# File isort/ufunc/u1_isort.c

-#define ISORT_LT(a,b) (*(a) < *(b))
-#define ISORT_TY unsigned char
-#define IS_(name) u1_##name
-#include "isort/isort.c"
+
+#define CSORT_TY unsigned char
+#define CS_(name) u1_##name
+
+#include "../../common/defs.c"

# File qsort/csort.c

of quicksort.

Caller defines a few macros:
-   Required: QSORT_TY, QSORT_LT
+   Required: CSORT_TY, CSORT_LT
Recommended:
-   1. #define QS_(name) ty_##name, e.g. QS_(sort) -> u4_qsort
+   1. #define CS_(name) ty_##name, e.g. CS_(sort) -> u4_qsort
To do:
1. handle keys within structs.
2. define optional mode using comparison operators wrt a single CMP a la python, ocaml.

*/

-#ifndef QSORT
-#define QSORT
-#if !defined LIBBING_AS_QSORT
-#  define QSORT_LKG static inline
+#include "../common/defs.c"
+
+#ifndef CSORT
+#define CSORT
+#if !defined LIBBING_AS_CSORT
+#  define CSORT_LKG static inline
#else
-#  define QSORT_LKG
+#  define CSORT_LKG
#endif

-#ifndef QSORT_TY
-#  error "qsort.c imported without QSORT_TY definition."
+
+#ifndef CSORT_TY
+#  error "qsort.c imported without CSORT_TY definition."
#endif

/* can redefine with type_ */
-#ifndef QS_
-#  define QS_(name) QS_##name
+#ifndef CS_
+#  define CS_(name) CS_##name
#endif

#include "swap.c"
/* smaller than this value => insertion sort */
-#define QSORT_ISORT_SWITCH 32
-#define QSORT_NINTHER_SWITCH 64
+#define CSORT_ISORT_SWITCH 32
+#define CSORT_NINTHER_SWITCH 64

/* Comparisons... default to arithmatic */
-#ifndef QSORT_EQ
-#  define QSORT_EQ(a,b) (*(a) == *(b))
+#ifndef CSORT_EQ
+#  define CSORT_EQ(a,b) (*(a) == *(b))
#endif
-#ifndef QSORT_LT
-#  define QSORT_LT(a,b) (*(a) < *(b))
+#ifndef CSORT_LT
+#  define CSORT_LT(a,b) (*(a) < *(b))
#endif
-#ifndef QSORT_LE
-#  define QSORT_LE(a,b) (*(a) <= *(b))
+#ifndef CSORT_LE
+#  define CSORT_LE(a,b) (*(a) <= *(b))
#endif

-#define QSORT_MIN(a,b) ((a) < (b) ? (a) : (b))
+#define CSORT_MIN(a,b) ((a) < (b) ? (a) : (b))

/* implements median of 3 "the ninther." Argumments are addresses. */
-#define QSORT_NINTHER(a,b,c)                                            \
-    (QSORT_LT((a),(b)) ? (QSORT_LT((b),(c)) ? (b) :                     \
-                          QSORT_LT((a),(c)) ? (c) : (a))                \
-     : (QSORT_LT((c),(b)) ? (b) : QSORT_LT((c),(a)) ? (c) : (a)))
+#define CSORT_NINTHER(a,b,c)                                            \
+    (CSORT_LT((a),(b)) ? (CSORT_LT((b),(c)) ? (b) :                     \
+                          CSORT_LT((a),(c)) ? (c) : (a))                \
+     : (CSORT_LT((c),(b)) ? (b) : CSORT_LT((c),(a)) ? (c) : (a)))

-static inline void QS_(SWAP)(QSORT_TY *a, QSORT_TY *b) {
+static inline void CS_(SWAP)(CSORT_TY *a, CSORT_TY *b) {
/* made a function since arguments tend to be incremented by caller */
-    QSORT_TY swap = *a;
+    CSORT_TY swap = *a;
*a            = *b;
*b            = swap;
}

-static inline void QS_(isort)(QSORT_TY* a, const long long len) {
-    QSORT_TY *x=a+1,*y;
-    for (;x < a + len;x++)
-        for ( y=x; y>a && QSORT_LT(y,(y-1)); y-- )
-            QS_(SWAP)(y,y-1);
-}

-static inline void QS_(sort)(QSORT_TY *x, const long long orig_n) {
+/* static inline void CS_(isort)(CSORT_TY* a, const long long len) {     */
+/*     CSORT_TY *x=a+1,*y; */
+/*     for (;x < a + len;x++) */
+/*         for ( y=x; y>a && CSORT_LT(y,(y-1)); y-- ) */
+/*             CS_(SWAP)(y,y-1); */
+/* } */
+
+static inline void CS_(sort)(CSORT_TY *x, const long long orig_n) {
long long n = orig_n,s;
long long ty_sz; /* ,l,h; */
-    QSORT_TY *p0,*pm,*p1;
-    QSORT_TY *a,*b,*c,*d; /* ,*t; */ /* indices within array */
-    QSORT_TY pivot;
+    CSORT_TY *p0,*pm,*p1;
+    CSORT_TY *a,*b,*c,*d; /* ,*t; */ /* indices within array */
+    CSORT_TY pivot;
ssort_start:
if (n < 0) fprintf(stderr,"sort error: n < 0: %lld\n",n),exit(1);
-    if (n <= QSORT_ISORT_SWITCH) return QS_(isort)(x,n);
-    s=(n>>3), ty_sz=sizeof(QSORT_TY);
+    if (n <= CSORT_ISORT_SWITCH) return CS_(ins_sort)(x,n);
+    s=(n>>3), ty_sz=sizeof(CSORT_TY);
p0=x;pm=x+(n>>1);p1=x+n-1; /* pivot candidates 0,1 from calculus, m for median */
-    if (n >= QSORT_NINTHER_SWITCH) {
-        p0    = QSORT_NINTHER(p0    , p0+s, p0+2*s);
-        pm    = QSORT_NINTHER(pm-s  , pm  , pm+s);
-        p1    = QSORT_NINTHER(p1-2*s, p1-s, p1);
+    if (n >= CSORT_NINTHER_SWITCH) {
+        p0    = CSORT_NINTHER(p0    , p0+s, p0+2*s);
+        pm    = CSORT_NINTHER(pm-s  , pm  , pm+s);
+        p1    = CSORT_NINTHER(p1-2*s, p1-s, p1);
}
-    pm    = QSORT_NINTHER(p0,pm,p1); /* now pm contains the pivot */
+    pm    = CSORT_NINTHER(p0,pm,p1); /* now pm contains the pivot */
pivot = *pm;
a     = b = x;
c     = d = x + (n-1);
for (;;) {
-        while (b <= c && QSORT_LE(b, &pivot)) {
-            if (QSORT_EQ(b,&pivot)) QS_(SWAP)(a++,b);  /* repeated pivots treated separately */
+        while (b <= c && CSORT_LE(b, &pivot)) {
+            if (CSORT_EQ(b,&pivot)) CS_(SWAP)(a++,b);  /* repeated pivots treated separately */
b++;
}
-        while (c >= b && QSORT_LE(&pivot,c)) {
-            if (QSORT_EQ(c,&pivot)) QS_(SWAP)(d--,c);
+        while (c >= b && CSORT_LE(&pivot,c)) {
+            if (CSORT_EQ(c,&pivot)) CS_(SWAP)(d--,c);
c--;
}
if (b > c) break;
-        QS_(SWAP)(b++,c--);
+        CS_(SWAP)(b++,c--);
}
-    s = QSORT_MIN(a-x,b-a); /* repeat pivot movement */
-    //for (l=0,h=(b-x)-s; s ; s--) QS_(SWAP)(&x[l++],&x[h++]);
-    swap(x , b - s     , s * sizeof(QSORT_TY));
-    s = QSORT_MIN(d-c, (x + n - 1) - d);
-    //for (l=b-x,h=n-s;s;s--) QS_(SWAP)(&x[l++],&x[h++]);
-    swap(b, x + (n - s), s * sizeof(QSORT_TY));
+    s = CSORT_MIN(a-x,b-a); /* repeat pivot movement */
+    //for (l=0,h=(b-x)-s; s ; s--) CS_(SWAP)(&x[l++],&x[h++]);
+    swap(x , b - s     , s * sizeof(CSORT_TY));
+    s = CSORT_MIN(d-c, (x + n - 1) - d);
+    //for (l=b-x,h=n-s;s;s--) CS_(SWAP)(&x[l++],&x[h++]);
+    swap(b, x + (n - s), s * sizeof(CSORT_TY));
if ((b-a) < n-(d-c)) {  /* recurse on smaller first to bound memory usage. */
-        if ((b-a) > 1) QS_(sort)(x, (b-a));
+        if ((b-a) > 1) CS_(sort)(x, (b-a));
if ((n-(d-c)) > 1) { /* avoid procedure call on second recursion. */
x = x+n-(d-c);
n = d-c;
}
}
else {
-        if ((d-c) > 1) QS_(sort)(x + n-(d-c), d-c);
+        if ((d-c) > 1) CS_(sort)(x + n-(d-c), d-c);
if ((b - a) > 1) {
n = (b-a);
goto ssort_start; /* avoid procedure call on second recursion. */
}
}

-#undef QS_
-#undef QSORT_MIN
-#undef QSORT_LKG
-#undef QSORT_LT
-#undef QSORT_LE
-#undef QSORT_EQ
-#undef QSORT_TY
-#undef QSORT_SWITCH
-#undef QSORT_NINTHER
+#undef CS_
+#undef CSORT_MIN
+#undef CSORT_LKG
+#undef CSORT_LT
+#undef CSORT_LE
+#undef CSORT_EQ
+#undef CSORT_TY
+#undef CSORT_SWITCH
+#undef CSORT_NINTHER
#endif

# File qsort/t/csort-cmp.c

Uses macros for polymorphism.
To use, define macro TY (e.g. #define TY float) then #include this file. */

-#ifndef QSORT_CMP
-#define QSORT_CMP
+#ifndef CSORT_CMP
+#define CSORT_CMP

#include <stdio.h>
#include <stdlib.h>
for (i = 0; i < num_trials; i++) {
fill(argv[2],array1,n);
start = TIME();
-        QS(array1,n);
+        CS(array1,n);
end   = TIME();
if (i) {
m_tot += end - start;

# File qsort/t/f4.c

#define TY float
#define TY_FMT "%f"
#include "../ufunc/f4_sort.c"
-#define QS f4_sort
+#define CS f4_sort
#include "csort-cmp.c"

# File qsort/t/f8.c

#define TY double
#define TY_FMT "%lf"
#include "../ufunc/f8_sort.c"
-#define QS f8_sort
+#define CS f8_sort
#include "csort-cmp.c"

# File qsort/t/s1.c

#define TY signed char
#define TY_FMT "%c"
#include "../ufunc/s1_sort.c"
-#define QS s1_sort
+#define CS s1_sort
#include "csort-cmp.c"

# File qsort/t/s2.c

#define TY short
#define TY_FMT "%i"
#include "../ufunc/s2_sort.c"
-#define QS s2_sort
+#define CS s2_sort
#include "csort-cmp.c"

# File qsort/t/s4.c

#define TY int
#define TY_FMT "%d"
#include "../ufunc/s4_sort.c"
-#define QS s4_sort
+#define CS s4_sort
#include "csort-cmp.c"

# File qsort/t/s8.c

#define TY long long
#define TY_FMT "%lld"
#include "../ufunc/s8_sort.c"
-#define QS s8_sort
+#define CS s8_sort
#include "csort-cmp.c"

# File qsort/t/u1.c

#define TY unsigned char
#define TY_FMT "%d"
#include "../ufunc/u1_sort.c"
-#define QS u1_sort
+#define CS u1_sort
#include "csort-cmp.c"

# File qsort/t/u2.c

#define TY unsigned short
#define TY_FMT "%ui"
#include "../ufunc/u2_sort.c"
-#define QS u2_sort
+#define CS u2_sort
#include "csort-cmp.c"

# File qsort/t/u4.c

#define TY unsigned
#define TY_FMT "%u"
#include "../ufunc/u4_sort.c"
-#define QS u4_sort
+#define CS u4_sort
#include "csort-cmp.c"

# File qsort/t/u8.c

#define TY unsigned long long
#define TY_FMT "%llu"
#include "../ufunc/u8_sort.c"
-#define QS u8_sort
+#define CS u8_sort
#include "csort-cmp.c"

# File qsort/ufunc/f4_sort.c

/* the <= and == tests for floats are extremely slow for certain distributions of numbers
exhibited in the test harness.  So we turn off sections of the sorting alg that use this
-with QSORT_SKIP_EQUALITY */
+with CSORT_SKIP_EQUALITY */

-#ifndef F4_QSORT
-#define F4_QSORT
-#define QSORT_TY float
-#define QS_(name) f4_## name
+#ifndef F4_CSORT
+#define F4_CSORT
+#define CSORT_TY float
+#define CS_(name) f4_## name

#include "../csort.c"
#endif

# File qsort/ufunc/f8_sort.c

-#ifndef F8_QSORT
-#define F8_QSORT
-#define QSORT_TY double
-#define QS_(name) f8_## name
+#ifndef F8_CSORT
+#define F8_CSORT
+#define CSORT_TY double
+#define CS_(name) f8_## name
#include "../csort.c"
#endif

# File qsort/ufunc/s1_sort.c

-#ifndef S1_QSORT
-#define S1_QSORT
-#define QSORT_TY signed char
-#define QS_(name) s1_## name
+#ifndef S1_CSORT
+#define S1_CSORT
+#define CSORT_TY signed char
+#define CS_(name) s1_## name
#include "csort.c"
#endif

# File qsort/ufunc/s2_sort.c

-#ifndef S2_QSORT
-#define S2_QSORT
-#define QSORT_TY signed short
-#define QS_(name) s2_## name
+#ifndef S2_CSORT
+#define S2_CSORT
+#define CSORT_TY signed short
+#define CS_(name) s2_## name
#include "csort.c"
#endif

# File qsort/ufunc/s4_sort.c

-#ifndef S4_QSORT
-#define S4_QSORT
-#define QSORT_TY int
-#define QS_(name) s4_## name
+#ifndef S4_CSORT
+#define S4_CSORT
+#define CSORT_TY int
+#define CS_(name) s4_## name
#include "../csort.c"
#endif

# File qsort/ufunc/s8_sort.c

-#ifndef S8_QSORT
-#define S8_QSORT
-#define QSORT_TY long long
-#define QS_(name) s8_## name
+#ifndef S8_CSORT
+#define S8_CSORT
+#define CSORT_TY long long
+#define CS_(name) s8_## name
#include "../csort.c"
#endif

# File qsort/ufunc/u1_sort.c

-#ifndef U1_QSORT
-#define U1_QSORT
-#define QS_(name) u1_## name
-#define QSORT_TY unsigned char
+#ifndef U1_CSORT
+#define U1_CSORT
+#define CS_(name) u1_## name
+#define CSORT_TY unsigned char
#include "csort.c"
#endif

# File qsort/ufunc/u2_sort.c

-#ifndef U2_QSORT
-#define U2_QSORT
-#define QSORT_TY unsigned short
-#define QS_(name) u2_## name
+#ifndef U2_CSORT
+#define U2_CSORT
+#define CSORT_TY unsigned short
+#define CS_(name) u2_## name
#include "csort.c"
#endif

# File qsort/ufunc/u4_sort.c

-#ifndef U4_QSORT
-#define U4_QSORT
-#define QSORT_TY uint32_t
-#define QS_(name) u4_##name
+#ifndef U4_CSORT
+#define U4_CSORT
+#define CSORT_TY unsigned
+#define CS_(name) u4_##name
#include "../csort.c"
#endif

# File qsort/ufunc/u8_sort.c

-#ifndef U8_QSORT
-#define U8_QSORT
-#define QSORT_TY unsigned long long
-#define QS_(name) u8_## name
+#ifndef U8_CSORT
+#define U8_CSORT
+#define CSORT_TY unsigned long long
+#define CS_(name) u8_## name
#include "../csort.c"
#endif

# File usort/f4_sort.c

#if __BYTE_ORDER == __LITTLE_ENDIAN
#  include <stdlib.h>
-#  define QSORT_TY float
-#  define QS_(name) f4_q##name
+#  define CSORT_TY float
+#  define CS_(name) f4_q##name
#  include "../qsort/csort.c"

#  define _0(v) ( (v)         & 0x7FF)
b1 = b0 + F4_SORT_HIST_SIZE;
b2 = b1 + F4_SORT_HIST_SIZE;
memset(b0,0,F4_SORT_HIST_SIZE*3*sizeof(unsigned long));
-
+
for (n=0; n < sz; n++) {

buf1[n] = f4_sort_FloatFlip(a[n]);
#  undef _1
#  undef _2
#else /* endian */
-#  define QS_(name) f4_## name
-#  define QSORT_TY float
+#  define CS_(name) f4_## name
+#  define CSORT_TY float
#  include "../qsort/csort.c"
#endif

# File usort/f8_sort.c

#if __BYTE_ORDER == __LITTLE_ENDIAN
#  include <stdlib.h>
-#  define QSORT_TY double
-#  define QS_(name) f8_q##name
+#  define CSORT_TY double
+#  define CS_(name) f8_q##name
#  include "../qsort/csort.c"

#define _0(v) ( (v)         & 0x7FF)
# undef _4
# undef _5
#else /* endian */
-# define QS_(name) f8_## name
-# define QSORT_TY double
+# define CS_(name) f8_## name
+# define CSORT_TY double
# include "../qsort/csort.c"
#endif

# File usort/s1_sort.c

#define S1_HIST_MIN  -128
#define S1_HIST_MAX  127

-#include "isort/ufunc/s1_isort.c"
+
+#define CSORT_TY char
+#define CS_(name) s1_##name
+#include "../common/defs.c"

/* implements in place u1 bucket sort. */

long n;
char *writer=a;
long b0[S1_HIST_SIZE];
-    if (sz < 32) { return s1_isort(a,sz);}
+    if (sz < 32) { return CS_(ins_sort)(a,sz);}
memset(b0,0,S1_HIST_SIZE * sizeof(long));
for (n=0; n < sz; n++) {
b0[(unsigned char)a[n]]++;
}
-
for (j = S1_HIST_MIN; j <= S1_HIST_MAX; j++) {
while (b0[(unsigned char)j]-- > 0) {
*writer = j;

#undef REFRESH
#undef S1_HIST_SIZE
+#undef CSORT_TY
+#undef CS_

# File usort/s2_sort.c

#if __BYTE_ORDER == __BIG_ENDIAN
#include <stdlib.h>

-#include "isort/ufunc/s2_isort.c"
+#define CSORT_TY short
+#define CS_(name) s2_##name
+#include "../common/defs.c"
+

#define _0(v) (unsigned) ((v)         & 0xFF)
#define _1(v) (unsigned) (( ((v) >> 8)  & 0xFF) ^ 0x80)
long n, sum0=0 , sum1=0 , tsum=0;
long *b0, *b1;
-    if (sz < 32) { return s2_isort(a,sz);}
+    if (sz < 16) { return CS_(ins_sort)(a,sz);}
buf  = (signed short*) malloc(sz * sizeof(signed short));
b0   = calloc(HIST_SIZE * 2, sizeof(long));
b1   = b0 + HIST_SIZE;
#undef _0
#undef _1
#undef HIST_SIZE
+#undef CSORT_TY
+#undef CS_

#else /* endian */
-#define QS_(name) s2_## name
-#define QSORT_TY short
+#define CS_(name) s2_## name
+#define CSORT_TY short
#include "../qsort/csort.c"
#endif

# File usort/s4_sort.c

#if __BYTE_ORDER == __LITTLE_ENDIAN

#include <stdlib.h>
-#define QSORT_TY int
-#define QS_(name) s4_q##name
+#define CSORT_TY int
+#define CS_(name) s4_q##name
#include "../qsort/csort.c"

#define _0(v) ((unsigned)(v)         & 0x7FF)
#undef HIST_SIZE
#else
/* endian */
-#define QS_(name) s4_## name
-#define QSORT_TY int
+#define CS_(name) s4_## name
+#define CSORT_TY int
#include "../qsort/csort.c"
#endif

# File usort/s8_sort.c

#if __BYTE_ORDER == __LITTLE_ENDIAN
#include <stdlib.h>

-#define QS_(name) s8_q##name
-#define QSORT_TY long long
+#define CS_(name) s8_q##name
+#define CSORT_TY long long
#include "../qsort/csort.c"

#define _0(v) ((v)         & 0x7FF)
#undef HIST_SIZE

#else /* big endian */
-#define QS_(name) s8_## name
-#define QSORT_TY long long
+#define CS_(name) s8_## name
+#define CSORT_TY long long
#include "../qsort/csort.c"
#endif

# File usort/t/ctype-cmp.c

//fprintf(stderr,"GNU: %llx %llx\n",u1.ull,u2.ull);

start = TIME();
-        QS(array_m,n);
+        CS(array_m,n);
end   = TIME();
if (i) {
m_tot += end - start;

# File usort/t/f4-cmp.c

Uses macros for polymorphism.
To use, define macro TY (e.g. #define TY float) then #include this file. */

-#ifndef QSORT_CMP
-#define QSORT_CMP
+#ifndef CSORT_CMP
+#define CSORT_CMP

#include <stdio.h>
#include <stdlib.h>
checkWork("GNU",array_g,n);

start = TIME();
-        QS(array_m,n);
+        CS(array_m,n);
end   = TIME();
if (i) {
m_tot += end - start;

# File usort/t/f4.c

#define TY float
#define TY_FMT "%f"
#include "../f4_sort.c"
-#define QS f4_sort
+#define CS f4_sort
#define ISFINITE(x) isfinite((x))
#include "ctype-cmp.c"

# File usort/t/f8.c

#define TY double
#define TY_FMT "%20.20lf"
#include "../f8_sort.c"
-#define QS f8_sort
+#define CS f8_sort
#define ISFINITE(x) isfinite((x))
#include "ctype-cmp.c"

# File usort/t/s1.c

#define TY char
#define TY_FMT "%d"
#include "../s1_sort.c"
-#define QS s1_sort
+#define CS s1_sort
#include "ctype-cmp.c"

# File usort/t/s2.c

#define TY signed short
#define TY_FMT "%o"
#include "../s2_sort.c"
-#define QS s2_sort
+#define CS s2_sort
#include "ctype-cmp.c"

# File usort/t/s4.c

#define TY int32_t
#define TY_FMT "%d"
#include "../s4_sort.c"
-#define QS s4_sort
+#define CS s4_sort
#include "ctype-cmp.c"

# File usort/t/s8.c

#define TY long long
#define TY_FMT "%lld"
#include "../s8_sort.c"
-#define QS s8_sort
+#define CS s8_sort
#include "ctype-cmp.c"

# File usort/t/u1.c

#define TY unsigned char
#define TY_FMT "%d"
#include "../u1_sort.c"
-#define QS u1_sort
+#define CS u1_sort
#include "ctype-cmp.c"

# File usort/t/u2.c

#define TY unsigned short
#define TY_FMT "%hu"
#include "../u2_sort.c"
-#define QS u2_sort
+#define CS u2_sort
#include "ctype-cmp.c"

# File usort/t/u4.c

#define TY uint32_t
#define TY_FMT "%u"
#include "../u4_sort.c"
-#define QS u4_sort
+#define CS u4_sort
#include "ctype-cmp.c"

# File usort/t/u8.c

#define TY long long unsigned
#define TY_FMT "%llu"
#include "../u8_sort.c"
-#define QS u8_sort
+#define CS u8_sort
#include "ctype-cmp.c"

# File usort/u1_sort.c

#include <assert.h>
#include "u1_sort.h"
#define U1_HIST_SIZE 256
-#include "isort/ufunc/u1_isort.c"
+
+#define CSORT_TY unsigned char
+#define CS_(name) u1_##name
+#include "../common/defs.c"
+
+

/* implements in place u1 bucket sort. */

long n;
unsigned char *writer=a;
long b0[U1_HIST_SIZE];
-    if (sz < 32) { return u1_isort(a,sz);}
+    if (sz < 32) { return CS_(ins_sort)(a,sz);}
memset(b0,0,U1_HIST_SIZE * sizeof(long));
for (n=0; n < sz; n++) {
b0[a[n]]++;

#undef REFRESH
#undef U1_HIST_SIZE
+#undef CSORT_TY
+#undef CS_

# File usort/u2_sort.c

#if __BYTE_ORDER == __BIG_ENDIAN
#include <stdlib.h> /* malloc among others */

-#include "isort/ufunc/u2_isort.c"
+#define CSORT_TY unsigned short
+#define CS_(name) u2_##name
+#include "../common/defs.c"
+
#define _0(v) ((v)         & 0xFF)
#define _1(v) (((v) >> 8)  & 0xFF)
#define HIST_SIZE 256
#undef _0
#undef _1
#undef HIST_SIZE
+#undef CS_
+#undef CSORT_TY

/* endian */
#else
-#define QS_(name) u2_## name
-#define QSORT_TY unsigned short
+#define CS_(name) u2_## name
+#define CSORT_TY unsigned short
#include "../qsort/csort.c"
#endif

# File usort/u4_sort.c

#if __BYTE_ORDER == __LITTLE_ENDIAN

#include <stdlib.h>
-#define QSORT_TY unsigned
-#define QS_(name) u4_q##name
+#define CSORT_TY unsigned
+#define CS_(name) u4_q##name
#include "../qsort/csort.c"

#define _0(v) (unsigned) ((v)         & 0x7FF)
#undef _2
#undef HIST_SIZE
#else /* endian */
-#define QS_(name) u4_## name
-#define QSORT_TY unsigned
+#define CS_(name) u4_## name
+#define CSORT_TY unsigned
#include "../qsort/csort.c"
#endif

# File usort/u8_sort.c

#include <stdlib.h>

-#define QSORT_TY unsigned long long
-#define QS_(name) u8_q##name
+#define CSORT_TY unsigned long long
+#define CS_(name) u8_q##name
#include "../qsort/csort.c"

#define _0(v) ((v)         & 0x7FF)
#undef HIST_SIZE

#else  /* endian */
-#define QS_(name) u8_## name
-#define QSORT_TY unsigned long long
+#define CS_(name) u8_## name
+#define CSORT_TY unsigned long long
#include "../qsort/csort.c"
#endif