Commits

asc...@andrewschein.com  committed 38aef92

I think I got introsort working. testing as I do backup commit to
central repo.

  • Participants
  • Parent commits cbdaec0

Comments (0)

Files changed (86)

 
 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 comparison based routine.
+2. csort - a general purpose comparison based routine.
 
 To use the code, simply #include the appropriate function.
 

File common/defs.c

 */
 
 #ifndef CSORT_DEFS
-
+# define CSORT_DEFS
 # ifndef CS_
 # error __FILE__ " included without defining CS_ macro."
 # endif
             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 csort/Makefile

+include defs.mk
+
+.PHONY : clean all cmp sample 
+
+all :
+	cd t/ ; make all
+
+clean : 
+	cd t/ ; make clean
+	rm -f code_sample.tar
+	rm -f code_sample.tar.gz
+
+cmp   : all
+	cd t ; ./cmp-all.sh
+
+1.  Add support for keys within structs.
+

File csort/csort.c

+/* c 2008 Andrew I. Schein.  All rights reserved.
+   
+   A fast general-purpose sorting smplemention based on Bentley and McIlroy, 1993's discussion
+   of quicksort... altered into an introsort.
+   
+   Caller defines a few macros:
+   Required: CSORT_TY, CSORT_LT
+   Recommended: 
+   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.
+   
+   This implementation achieves a speedup compared to GLIBC 2.7 qsort by using the following
+   strategies:
+
+   1. Static definitions of comparions ensure inlining of this operation.  This is accomplished
+   through C macros.
+   2. Switch to insertion sort (GLIBC does this much later in the recursion tree than my impl.)
+   3. Smart treatment of duplicate pivots.  Useful for arrays containing very low entropy elements.
+   
+   In addition, this implementation differs from GLIBC 2.7 qsort in the use of recursion.
+   GLIB 2.7 manually manages a stack in order to bypass the more conventional decision of using 
+   the C runtime stack.  My implementation allows the C runtime to manage the
+   recursion stack for the non-tail first recursion call of quicksort, but performs the second
+   recursion in tail fashion by performing a goto. 
+
+   Something this implementation shares with the GLIBC implementation is recursing on the smaller 
+   partition first.  This ensures a O(N*log(N)) bound on memory usage. Another commonality is the
+   use of a smart median selection procedure the, "Tukey Ninther" method.
+   
+   The speedup compared to GLIBC is documented through a test harness located in the same 
+   directory as this file.
+
+*/
+
+#include "../common/defs.c"
+#include <math.h>
+
+#ifndef CSORT
+#define CSORT
+#if !defined LIBBING_AS_CSORT
+#  define CSORT_LKG static inline
+#else
+#  define CSORT_LKG 
+#endif
+
+#ifndef CSORT_TY
+#  error "qsort.c imported without CSORT_TY definition."
+#endif
+
+
+/* can redefine with type_ */
+#ifndef CS_
+#  define CS_(name) CS_##name
+#endif
+
+/*
+#define HSORT_TY CSORT_TY 
+#define HS_(name) HS_##name
+*/
+
+#define CS_KEEP
+#include "../hsort/hsort.c"  
+#undef CS_KEEP
+#include "swap.c" 
+
+/* smaller than this value => insertion sort */
+#define CSORT_ISORT_SWITCH 32
+#define CSORT_NINTHER_SWITCH 64
+
+/* Comparisons... default to arithmatic */
+#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
+
+#define CSORT_MIN(a,b) ((a) < (b) ? (a) : (b))
+
+/* implements median of 3 "the ninther." Argumments are addresses. */
+#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 CS_(intro_sort)(CSORT_TY *x, const long long orig_n, long intro_limit) {
+    long long n = orig_n,s;
+    long long ty_sz; /* ,l,h; */ 
+    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 <= CSORT_ISORT_SWITCH) return CS_(ins_sort) (x,n); 
+    if (intro_limit <= 0)        return CS_(heap_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 >= 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    = CSORT_NINTHER(p0,pm,p1); /* now pm contains the pivot */
+    pivot = *pm;
+    a     = b = x;
+    c     = d = x + (n-1);
+    for (;;) { 
+        while (b <= c && CSORT_LE(b, &pivot)) { 
+            if (CSORT_EQ(b,&pivot)) CS_(csort_swap)(a++,b); /* repeated pivots treated separately */
+            b++; 
+        }  
+        while (c >= b && CSORT_LE(&pivot,c)) { 
+            if (CSORT_EQ(c,&pivot)) CS_(csort_swap)(d--,c);  
+            c--; 
+        }
+        if (b > c) break;
+        CS_(csort_swap)(b++,c--);
+    }
+    s = CSORT_MIN(a-x,b-a); /* repeat pivot movement */
+    swap(x , b - s     , s * sizeof(CSORT_TY));
+    s = CSORT_MIN(d-c, (x + n - 1) - d);
+    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) CS_(intro_sort)(x, (b-a),intro_limit-1);
+        if ((n-(d-c)) > 1) { /* avoid procedure call on second recursion. */
+            x = x+n-(d-c);
+            n = d-c;
+            intro_limit--;
+            goto ssort_start;
+        }
+    }
+    else {
+        if ((d-c) > 1) CS_(intro_sort)(x + n-(d-c), d-c,intro_limit-1);
+        if ((b - a) > 1) {
+            n = (b-a); 
+            intro_limit--;
+            goto ssort_start; /* avoid procedure call on second recursion. */
+        }
+    }
+}
+
+static inline void CS_(sort)(CSORT_TY *x, const long long orig_n) {
+    CS_(intro_sort)(x, orig_n, log(orig_n) + 3);
+}
+
+#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 csort/datetime

+../../datetime

File csort/defs.mk

+I=-L/usr/lib/gcc/i486-linux-gnu/4.2/ -I../  -I/usr/include 
+W=-Wall
+#O=-fmudflap -lmudflap
+LIB=-lm
+O=-O9 -g
+CC=gcc#/usr/bin/colorgcc
+OBJS=$(patsubst %.c,%.o,$(wildcard *.c))
+
+%.o : %.c
+	$(CC) $(I) $(W) $(O) -o $@ -c $<

File csort/swap.c

+/* c 2008 Andrew I. Schein */
+
+#ifndef AS_SWAP
+#define AS_SWAP
+#include <string.h>
+#include <stdint.h> /* C99 defs for int_fastN_t */
+#include <stdio.h>
+#include <stdlib.h>
+#define SWAPCPY(x,y,sz) {memcpy((buf.c),(x),(sz)); memcpy((x),(y),(sz)); memcpy((y),(buf.c),(sz));}
+
+#define SWAPASS(ty) {*((ty*)buf.c)=*((ty*)x); *((ty*)x)=*((ty*)y); *((ty*)y)=*((ty*)buf.c);}
+#define SWAPINT32 (buf.d=*(int_fast32_t*)x, \
+                   *((int_fast32_t*)x)=*((int_fast32_t*)y), *((int_fast32_t*)y)= buf.d)
+#define SWAPINT64 (buf.f=*(int_fast64_t*)x, \
+                   *((int_fast64_t*)x)=*((int_fast64_t*)y), *((int_fast64_t*)y)= buf.f)
+#define SWAP_MIN(x,y)  ((x) < (y) ? (x) : (y))
+
+    
+void *swap(void *_x,void *_y,size_t sz) {
+    union swap_buf_t { char c[sizeof(int_fast64_t)] ; int_fast32_t d ; int_fast64_t f; } buf; 
+    size_t n; 
+    char *x=_x, *y=_y;
+    switch (sz) {
+    case             0 : return NULL;
+    case             sizeof(char)         :  SWAPASS(char);           return _x;
+    case             sizeof(short)        :  SWAPASS(short);          return _x;
+    case             sizeof(int32_t)      :  SWAPASS(int32_t);        return _x;
+    case             sizeof(int_fast64_t) :  SWAPASS(int_fast64_t);   return _x;
+    default : 
+        do {
+            n = SWAP_MIN(sz,sizeof(int_fast64_t));
+            if (n == sizeof(int_fast64_t))
+                (SWAPINT64);
+            else 
+                SWAPCPY(x,y,n);
+            sz -= n;
+            x  += n;
+            y  += n;
+        } while (sz > 0);
+        return _x;
+    }   
+    fprintf(stderr,"error in %s\n",__func__); 
+    exit(1);
+}
+
+#undef SWAPCPY
+#undef SWAP_MIN
+#undef SWAP_ASS
+#endif

File csort/t/Makefile

+include ../defs.mk
+
+APPS=u1 s1 u2 s2 f4 f8 u4 s4 u8 s8
+SRC=$(patsubst %,%.c,$(wildcard $(APPS)))
+
+all : $(APPS)
+
+u1  : csort-cmp.c ../swap.c ../csort.c $(SRC)  
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o u1 u1.c 
+
+s1  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o s1 s1.c 
+
+u2  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o u2 u2.c 
+
+s2  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o s2 s2.c 
+
+f4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o f4 f4.c 
+
+s4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o s4 s4.c 
+
+u4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o u4 u4.c 
+
+f8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o f8 f8.c 
+
+u8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o u8 u8.c 
+
+s8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(LIB) $(O) -o s8 s8.c 
+
+
+clean :
+	rm -f $(APPS) csort-cmp 

File csort/t/cmp-all.sh

+#!/bin/bash -e
+
+apps="u1 s1 u2 s2 u4 s4 s8 u8 f4 f8"
+
+for app in $apps ; do
+    export app
+    ./cmp.sh
+done
+

File csort/t/cmp.sh

+#!/usr/bin/zsh -e
+
+echo "TESTING APP: " ${app:="f8"}
+APP=$app
+
+i=(10 100 1000 10000 100000 1000000 10000000 100000000 )
+t=(10000000 1000000 100000 10000 1000 100 10 3 1 )
+sz=${#i[@]}
+c=1
+echo "Sort Comparison of unsigned integers on N numbers generating according to:"
+echo "RANDOM:    random integers"
+echo "BOUNDED:   random() % (N/4)"
+echo "SORTED:    sorted integers 1...N"
+echo "REVERSED:  sorted integers N...1"
+echo "IDENT:     all values of the array are \"1\""
+
+echo "\nRANDOM"
+echo "N               mysort (secs)   GLIBC (secs)    x-fold speedup"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} RAND ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+exit 0
+if [ ! $app = "f4" -a ! $app = "f8" ] ; then
+    echo "BOUNDED"
+    c=1
+    while [ $c -lt $sz ] ; do
+        ./${APP} ${i[$c]} BOUNDED ${t[$c]}  
+        c=$(( $c + 1 ))
+    done;
+fi;
+echo "SORTED"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} SORTED ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+echo "REVERSED"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} REVERSE ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+echo "IDENT"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} IDENT ${t[$c]}  
+    c=$(( $c + 1 ))
+done;

File csort/t/csort-cmp.c

+/* Test harness for csort.c, useful for all C base types up to 64 bits.  
+   Uses macros for polymorphism.
+   To use, define macro TY (e.g. #define TY float) then #include this file. */
+
+#ifndef CSORT_CMP
+#define CSORT_CMP
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <time.h>
+#include <string.h>
+#include <sys/time.h>
+#include "datetime/TIME.c"
+#include <unistd.h>
+#ifndef ISNAN
+#define CHECKNAN(x) (x)
+#else 
+#define CHECKNAN(x) (ISNAN((x)) ? 0 : (x)) 
+#endif
+
+enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
+
+long long k,j;
+const char* usage="csort-cmp dist N trials\n"
+"dist is one of: RAND, BOUNDED , SORTED, REVSORTED, IDENT\n"
+"N:              size of the array.\n"
+"trials:         how many trials to do.  Necessary for small N.\n";
+
+int parseDist(char* dist_str) {
+    if (!strcmp("BOUNDED",dist_str)) 
+        return BOUNDED;
+    else if (!strcmp("RAND",dist_str)) 
+        return RAND;
+    else if (!strcmp("SORTED",dist_str))
+        return SORTED;
+    else if (!strcmp("REVERSE",dist_str))
+        return REVERSE;
+    else if (!strcmp("IDENT",dist_str))
+        return IDENT;
+    else fprintf(stderr,"dist argument mismatch.\n%s\n",usage),exit(1);
+}
+
+void randomized(TY *x, long long n) {
+    long long i; 
+    union { char l[8]; TY t; } u;
+    for (i = 0; i < n; i++) {
+        u.l[0] =  random();
+        u.l[1] =  random();
+        u.l[2] =  random();
+        u.l[3] =  random();
+	u.l[4] =  random();
+        u.l[5] =  random();
+        u.l[6] =  random();
+        u.l[7] =  random();
+        
+	x[i]   =  u.t; 
+        x[i]   =  CHECKNAN(x[i]);
+    }
+}
+
+void bounded(TY *x, long long n) {
+    long long i;
+    union { long l[2]; TY t;} u;
+    for (i = 0; i < n; i++) {
+        u.l[0] = (random() % (n/4));
+        u.l[1] = (random() % (n/4));
+        x[i]   = u.t;
+        x[i]   = CHECKNAN(x[i]);
+    }
+}
+
+void identity(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) {
+        x[i] = 1;
+    }
+}
+
+void reverse(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) 
+        x[i] = n - i - 1;
+}
+
+void sorted(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) 
+        x[i] = i;
+}
+
+int compare(const void *a, const void *b) {
+    TY A = *(const TY *)a, B = *(const TY *)b;
+    if (A > B) return 1;
+    if (B < A) return -1;
+    return 0;
+}
+
+void fill(char* dist, TY* array1,long n) {
+    switch (parseDist(dist)) {
+    case RAND : 
+        randomized(array1,n) ; break;
+    case BOUNDED :
+        bounded(array1,n) ;    break;
+    case SORTED :
+        sorted(array1,n)  ;    break;
+    case REVERSE :
+        reverse(array1,n) ;    break;
+    case IDENT :
+        identity(array1,n) ;    break;
+    default :
+        fprintf(stderr,"dist match error.\n"), exit(1);
+    }
+}
+
+void checkWork(const char *name, TY *a, long long n ) {
+    long long i,j;
+    for (i = 1; i < n; i++) {
+        if (a[i-1] > a[i]) {
+            fprintf (stderr,"%s: %lld x %zd: failure at offset %lld\n", name, n,
+                     sizeof(TY), i);
+            for (j=0; j < n;j++) {
+                if (j != i) fprintf(stderr,TY_FMT " ",a[j]);
+                else { fprintf(stderr,TY_FMT "* ", a[j]); }
+            }
+            
+            fprintf(stderr,"\n"); 
+            free(a);
+            exit(1);
+        }
+    }
+}
+
+int main (int argc, char **argv)
+{
+    if (argc < 4) fprintf(stderr,"too few arguments: %d\n%s",argc,usage) , exit(1);
+    long i=j=0; long n=strtoul(argv[1],NULL,10);
+    long num_trials = strtoul(argv[3],NULL,10);
+    double start, end, m_tot=0, g_tot=0;
+    TY *array1 = (TY*) malloc (n * sizeof(TY));
+    if (array1 == NULL)
+        {
+            fprintf (stderr,"%d x %zd: no memory\n", argc, sizeof(TY));
+            return 1;
+        }
+    if (getenv("SEED")) srand(time(NULL)); /* default is debugging mode. */
+    for (i = 0; i < num_trials; i++) {
+        fill(argv[2],array1,n);
+        start = TIME();
+        qsort (array1,n,sizeof(TY),&compare);
+        end   = TIME();
+        if (i) {
+            g_tot += end-start;
+        }  
+        checkWork("GNU",array1,n);
+    }
+    g_tot /= (double) (num_trials - 1);
+        
+    for (i = 0; i < num_trials; i++) {
+        fill(argv[2],array1,n);
+        start = TIME();
+        CS(array1,n);
+        end   = TIME();
+        if (i) {
+            m_tot += end - start;
+        }    
+        checkWork("schein",array1,n);
+    
+    }
+    m_tot /= (double) (num_trials - 1);
+    
+        
+    
+    fprintf(stdout,"%10ld\t%5.10f\t%5.10f\t%2.2f\n",n,m_tot,g_tot,
+            (g_tot/m_tot));
+    free (array1);
+    return 0; 
+}
+#endif
+
+
+
+
+

File csort/t/f4.c

+#include <math.h>
+#define ISNAN(x)  isnan((x))
+#define TY float
+#define TY_FMT "%f"
+#include "../ufunc/f4_sort.c"
+#define CS f4_sort
+#include "csort-cmp.c"

File csort/t/f8.c

+#include <math.h>
+#define ISNAN(x) isnan((x))
+#define TY double
+#define TY_FMT "%lf"
+#include "../ufunc/f8_sort.c"
+#define CS f8_sort
+#include "csort-cmp.c"

File csort/t/s1.c

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

File csort/t/s2.c

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

File csort/t/s4.c

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

File csort/t/s8.c

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

File csort/t/u1.c

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

File csort/t/u2.c

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

File csort/t/u4.c

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

File csort/t/u8.c

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

File csort/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 CSORT_SKIP_EQUALITY */
+
+#ifndef F4_CSORT
+#define F4_CSORT
+#define CSORT_TY float
+#define CS_(name) f4_## name
+
+#include "../csort.c"
+#endif

File csort/ufunc/f8_sort.c

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

File csort/ufunc/s1_sort.c

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

File csort/ufunc/s2_sort.c

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

File csort/ufunc/s4_sort.c

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

File csort/ufunc/s8_sort.c

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

File csort/ufunc/u1_sort.c

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

File csort/ufunc/u2_sort.c

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

File csort/ufunc/u4_sort.c

+#ifndef U4_CSORT
+#define U4_CSORT
+#define CSORT_TY unsigned
+#define CS_(name) u4_##name
+#include "../csort.c"
+#endif
+
+

File csort/ufunc/u8_sort.c

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

File hsort/hsort.c

 
 #ifndef HSORT
 #define HSORT
-#if !defined LIBBING_AS_HSORT
-#  define HSORT_LKG static inline
-#else
-#  define HSORT_LKG 
-#endif
-
-#ifndef HSORT_TY
+#include "../common/defs.c"
+#ifndef CSORT_TY
 #  error "hsort.c imported without HSORT_TY definition."
 #endif
 
-
 /* can redefine with type_ */
-#ifndef HS_
-#  define HS_(name) HS_##name
+#ifndef CS_
+#  define CS_(name) CS_##name
 #endif
 
 /* Comparisons... default to arithmatic */
-#ifndef HSORT_EQ
-#  define HSORT_EQ(a,b) (*(a) == *(b))
+#ifndef CSORT_EQ
+#  define CSORT_EQ(a,b) (*(a) == *(b))
 #endif
-#ifndef HSORT_LT
-#  define HSORT_LT(a,b) (*(a) < *(b))
+#ifndef CSORT_LT
+#  define CSORT_LT(a,b) (*(a) < *(b))
 #endif
-#ifndef HSORT_LE
-#  define HSORT_LE(a,b) (*(a) <= *(b))
+#ifndef CSORT_LE
+#  define CSORT_LE(a,b) (*(a) <= *(b))
 #endif
 
-
-static inline void HS_(SWAP)(HSORT_TY *a, HSORT_TY *b) {
-    /* made a function since arguments tend to be incremented by caller */
-    HSORT_TY swap = *a;
-    *a            = *b;
-    *b            = swap;
-}
-
-static inline void HS_(siftdown)(HSORT_TY *a, const long start, const long end) {
+static inline void CS_(siftdown)(CSORT_TY *a, const long start, const long end) {
     long child, root = start;
     while (root * 2 + 1 <= end) {
         child = root * 2 + 1;
-        if ((child + 1) <= end && HSORT_LT(&a[child],&a[child+1])) ++child;           
-        if (HSORT_LT(&a[root],&a[child])) HS_(SWAP)(&a[root],&a[child]), root=child; 
+        if ((child + 1) <= end && CSORT_LT(&a[child],&a[child+1])) ++child;           
+        if (CSORT_LT(&a[root],&a[child])) CS_(csort_swap)(&a[root],&a[child]), root=child; 
         else return;      
     }
 }
 
-static inline void HS_(heapify)(HSORT_TY *a, const long count) {
+static inline void CS_(heapify)(CSORT_TY *a, const long count) {
     long start = (count-2) / 2; 
-    while ( start >= 0 ) HS_(siftdown)(a,start--,count-1);
+    while ( start >= 0 ) CS_(siftdown)(a,start--,count-1);
 }
 
-static inline void HS_(sort)(HSORT_TY *a, const long count) {
+static inline void CS_(heap_sort)(CSORT_TY *a, const long count) {
     long end;
-    HS_(heapify)(a, count);
+    CS_(heapify)(a, count);
     end = count - 1;
     while (end > 0) {
-        HS_(SWAP)(&a[end], &a[0]);
-        HS_(siftdown)(a, 0, end-1);
+        CS_(csort_swap)(&a[end], &a[0]);
+        CS_(siftdown)(a, 0, end-1);
         --end;   
     }
 }
 
-#undef HS_
-#undef HSORT_MIN
-#undef HSORT_LKG 
-#undef HSORT_LT
-#undef HSORT_LE
-#undef HSORT_EQ
-#undef HSORT_TY
+  #ifndef CS_KEEP
+    #undef CS_
+    #undef CSORT_LT
+    #undef CSORT_LE
+    #undef CSORT_EQ
+    #undef CSORT_TY
+  #endif
 #endif

File hsort/t/Makefile

 all : $(APPS)
 	echo $(SRC)
 
-
 u1  : hsort-cmp.c  ../hsort.c $(SRC)  
 	gcc $(G) $(W) $(I) $(O) -o u1 u1.c 
 

File hsort/t/f4.c

 #define TY float
 #define TY_FMT "%f"
 #include "../ufunc/f4_hsort.c"
-#define HS f4_hsort
+#define CS f4_heap_sort
 #include "hsort-cmp.c"

File hsort/t/f8.c

 #define TY double
 #define TY_FMT "%lf"
 #include "../ufunc/f8_hsort.c"
-#define HS f8_hsort
+#define CS f8_heap_sort
 #include "hsort-cmp.c"

File hsort/t/hsort-cmp.c

    Uses macros for polymorphism.
    To use, define macro TY (e.g. #define TY float) then #include this file. */
 
-#ifndef HSORT_CMP
-#define HSORT_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();
-        HS(array1,n);
+        CS(array1,n);
         end   = TIME();
         if (i) {
             m_tot += end - start;

File hsort/t/s1.c

 #define TY signed char
 #define TY_FMT "%c"
 #include "../ufunc/s1_hsort.c"
-#define HS s1_hsort
+#define CS s1_heap_sort
 #include "hsort-cmp.c"

File hsort/t/s2.c

 #define TY short
 #define TY_FMT "%i"
 #include "../ufunc/s2_hsort.c"
-#define HS s2_hsort
+#define CS s2_heap_sort
 #include "hsort-cmp.c"

File hsort/t/s4.c

 #define TY int
 #define TY_FMT "%d"
 #include "../ufunc/s4_hsort.c"
-#define HS s4_hsort
+#define CS s4_heap_sort
 #include "hsort-cmp.c"

File hsort/t/s8.c

 #define TY long long
 #define TY_FMT "%lld"
 #include "../ufunc/s8_hsort.c"
-#define HS s8_hsort
+#define CS s8_heap_sort
 #include "hsort-cmp.c"

File hsort/t/u1.c

 #define TY unsigned char
 #define TY_FMT "%d"
 #include "../ufunc/u1_hsort.c"
-#define HS u1_hsort
+#define CS u1_heap_sort
 #include "hsort-cmp.c"

File hsort/t/u2.c

 #define TY unsigned short
 #define TY_FMT "%ui"
 #include "../ufunc/u2_hsort.c"
-#define HS u2_hsort
+#define CS u2_heap_sort
 #include "hsort-cmp.c"

File hsort/t/u4.c

 #define TY unsigned int
 #define TY_FMT "%u"
 #include "../ufunc/u4_hsort.c"
-#define HS u4_hsort
+#define CS u4_heap_sort
 #include "hsort-cmp.c"
 

File hsort/t/u8.c

 #define TY unsigned long long
 #define TY_FMT "%llu"
 #include "../ufunc/u8_hsort.c"
-#define HS u8_hsort
+#define CS u8_heap_sort
 #include "hsort-cmp.c"

File hsort/ufunc/f4_hsort.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 HSORT_SKIP_EQUALITY */
+with CSORT_SKIP_EQUALITY */
 
-#ifndef F4_HSORT
-#define F4_HSORT
-#define HSORT_TY float
-#define HS_(name) f4_h## name
+#ifndef F4_CSORT
+#define F4_CSORT
+#define CSORT_TY float
+#define CS_(name) f4_## name
 
 #include "../hsort.c"
 #endif

File hsort/ufunc/f8_hsort.c

-#ifndef F8_HSORT
-#define F8_HSORT
-#define HSORT_TY double
-#define HS_(name) f8_h## name
+#ifndef F8_CSORT
+#define F8_CSORT
+#define CSORT_TY double
+#define CS_(name) f8_## name
 #include "../hsort.c"
 #endif

File hsort/ufunc/s1_hsort.c

-#ifndef S1_HSORT
-#define S1_HSORT
-#define HSORT_TY signed char
-#define HS_(name) s1_h## name
+#ifndef S1_CSORT
+#define S1_CSORT
+#define CSORT_TY signed char
+#define CS_(name) s1_## name
 #include "hsort.c"
 #endif

File hsort/ufunc/s2_hsort.c

-#ifndef S2_HSORT
-#define S2_HSORT
-#define HSORT_TY signed short
-#define HS_(name) s2_h## name
+#ifndef S2_CSORT
+#define S2_CSORT
+#define CSORT_TY signed short
+#define CS_(name) s2_## name
 #include "hsort.c"
 #endif

File hsort/ufunc/s4_hsort.c

-#ifndef S4_HSORT
-#define S4_HSORT
-#define HSORT_TY int
-#define HS_(name) s4_h## name
+#ifndef S4_CSORT
+#define S4_CSORT
+#define CSORT_TY int
+#define CS_(name) s4_## name
 #include "../hsort.c"
 #endif

File hsort/ufunc/s8_hsort.c

-#ifndef S8_HSORT
-#define S8_HSORT
-#define HSORT_TY long long
-#define HS_(name) s8_h## name
+#ifndef S8_CSORT
+#define S8_CSORT
+#define CSORT_TY long long
+#define CS_(name) s8_## name
 #include "../hsort.c"
 #endif

File hsort/ufunc/u1_hsort.c

-#ifndef U1_HSORT
-#define U1_HSORT
-#define HS_(name) u1_h## name
-#define HSORT_TY unsigned char
+#ifndef U1_CSORT
+#define U1_CSORT
+#define CS_(name) u1_##name
+#define CSORT_TY unsigned char
 #include "hsort.c"
 #endif

File hsort/ufunc/u2_hsort.c

-#ifndef U2_HSORT
-#define U2_HSORT
-#define HSORT_TY unsigned short
-#define HS_(name) u2_h## name
+#ifndef U2_CSORT
+#define U2_CSORT
+#define CSORT_TY unsigned short
+#define CS_(name) u2_## name
 #include "hsort.c"
 #endif

File hsort/ufunc/u4_hsort.c

-#ifndef U4_HSORT
-#define U4_HSORT
-#define HSORT_TY unsigned int
-#define HS_(name) u4_h## name
+#ifndef U4_CSORT
+#define U4_CSORT
+#define CSORT_TY unsigned int
+#define CS_(name) u4_## name
 #include "../hsort.c"
 #endif
 

File hsort/ufunc/u8_hsort.c

-#ifndef U8_HSORT
-#define U8_HSORT
-#define HSORT_TY unsigned long long
-#define HS_(name) u8_h## name
+#ifndef U8_CSORT
+#define U8_CSORT
+#define CSORT_TY unsigned long long
+#define CS_(name) u8_## name
 #include "../hsort.c"
 #endif

File qsort/Makefile

-include defs.mk
-
-.PHONY : clean all cmp sample 
-
-all :
-	cd t/ ; make all
-
-clean : 
-	cd t/ ; make clean
-	rm -f code_sample.tar
-	rm -f code_sample.tar.gz
-
-cmp   : all
-	cd t ; ./cmp-all.sh
-

File qsort/TODO

-1.  Add support for keys within structs.
-

File qsort/csort.c

-/* c 2008 Andrew I. Schein.  All rights reserved.
-   
-   A fast general-purpose sorting smplemention based on Bentley and McIlroy, 1993's discussion
-   of quicksort.
-   
-   Caller defines a few macros:
-   Required: CSORT_TY, CSORT_LT
-   Recommended: 
-   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.
-   
-   This implementation achieves a speedup compared to GLIBC 2.7 qsort by using the following
-   strategies:
-
-   1. Static definitions of comparions ensure inlining of this operation.  This is accomplished
-   through C macros.
-   2. Switch to insertion sort (GLIBC does this much later in the recursion tree than my impl.)
-   3. Smart treatment of duplicate pivots.  Useful for arrays containing very low entropy elements.
-   
-   In addition, this implementation differs from GLIBC 2.7 qsort in the use of recursion.
-   GLIB 2.7 manually manages a stack in order to bypass the more conventional decision of using 
-   the C runtime stack.  My implementation allows the C runtime to manage the
-   recursion stack for the non-tail first recursion call of quicksort, but performs the second
-   recursion in tail fashion by performing a goto. 
-
-   Something this implementation shares with the GLIBC implementation is recursing on the smaller 
-   partition first.  This ensures a O(N*log(N)) bound on memory usage. Another commonality is the
-   use of a smart median selection procedure the, "Tukey Ninther" method.
-   
-   The speedup compared to GLIBC is documented through a test harness located in the same 
-   directory as this file.
-
-*/
-
-#include "../common/defs.c"
-
-#ifndef CSORT
-#define CSORT
-#if !defined LIBBING_AS_CSORT
-#  define CSORT_LKG static inline
-#else
-#  define CSORT_LKG 
-#endif
-
-
-#ifndef CSORT_TY
-#  error "qsort.c imported without CSORT_TY definition."
-#endif
-
-/* can redefine with type_ */
-#ifndef CS_
-#  define CS_(name) CS_##name
-#endif
-
-#include "swap.c" 
-/* smaller than this value => insertion sort */
-#define CSORT_ISORT_SWITCH 32
-#define CSORT_NINTHER_SWITCH 64
-
-/* Comparisons... default to arithmatic */
-#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
-
-#define CSORT_MIN(a,b) ((a) < (b) ? (a) : (b))
-
-/* implements median of 3 "the ninther." Argumments are addresses. */
-#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 CS_(SWAP)(CSORT_TY *a, CSORT_TY *b) {
-    /* made a function since arguments tend to be incremented by caller */
-    CSORT_TY swap = *a;
-    *a            = *b;
-    *b            = swap;
-}
-
-
-/* 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; */ 
-    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 <= 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 >= 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    = CSORT_NINTHER(p0,pm,p1); /* now pm contains the pivot */
-    pivot = *pm;
-    a     = b = x;
-    c     = d = x + (n-1);
-    for (;;) { 
-        while (b <= c && CSORT_LE(b, &pivot)) { 
-            if (CSORT_EQ(b,&pivot)) CS_(SWAP)(a++,b);  /* repeated pivots treated separately */
-            b++; 
-        }  
-        while (c >= b && CSORT_LE(&pivot,c)) { 
-            if (CSORT_EQ(c,&pivot)) CS_(SWAP)(d--,c);  
-            c--; 
-        }
-        if (b > c) break;
-        CS_(SWAP)(b++,c--);
-    }
-    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) CS_(sort)(x, (b-a));
-        if ((n-(d-c)) > 1) { /* avoid procedure call on second recursion. */
-            x = x+n-(d-c);
-            n = d-c;
-            goto ssort_start;
-        }
-    }
-    else {
-        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 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/datetime

-../../datetime

File qsort/defs.mk

-I=-L/usr/lib/gcc/i486-linux-gnu/4.2/ -I../  -I/usr/include 
-W=-Wall
-#O=-fmudflap -lmudflap
-O=-O9 -g
-CC=gcc#/usr/bin/colorgcc
-OBJS=$(patsubst %.c,%.o,$(wildcard *.c))
-
-%.o : %.c
-	$(CC) $(I) $(W) $(O) -o $@ -c $<

File qsort/swap.c

-/* c 2008 Andrew I. Schein */
-
-#ifndef AS_SWAP
-#define AS_SWAP
-#include <string.h>
-#include <stdint.h> /* C99 defs for int_fastN_t */
-#include <stdio.h>
-#include <stdlib.h>
-#define SWAPCPY(x,y,sz) {memcpy((buf.c),(x),(sz)); memcpy((x),(y),(sz)); memcpy((y),(buf.c),(sz));}
-
-#define SWAPASS(ty) {*((ty*)buf.c)=*((ty*)x); *((ty*)x)=*((ty*)y); *((ty*)y)=*((ty*)buf.c);}
-#define SWAPINT32 (buf.d=*(int_fast32_t*)x, \
-                   *((int_fast32_t*)x)=*((int_fast32_t*)y), *((int_fast32_t*)y)= buf.d)
-#define SWAPINT64 (buf.f=*(int_fast64_t*)x, \
-                   *((int_fast64_t*)x)=*((int_fast64_t*)y), *((int_fast64_t*)y)= buf.f)
-#define SWAP_MIN(x,y)  ((x) < (y) ? (x) : (y))
-
-    
-void *swap(void *_x,void *_y,size_t sz) {
-    union swap_buf_t { char c[sizeof(int_fast64_t)] ; int_fast32_t d ; int_fast64_t f; } buf; 
-    size_t n; 
-    char *x=_x, *y=_y;
-    switch (sz) {
-    case             0 : return NULL;
-    case             sizeof(char)         :  SWAPASS(char);           return _x;
-    case             sizeof(short)        :  SWAPASS(short);          return _x;
-    case             sizeof(int32_t)      :  SWAPASS(int32_t);        return _x;
-    case             sizeof(int_fast64_t) :  SWAPASS(int_fast64_t);   return _x;
-    default : 
-        do {
-            n = SWAP_MIN(sz,sizeof(int_fast64_t));
-            if (n == sizeof(int_fast64_t))
-                (SWAPINT64);
-            else 
-                SWAPCPY(x,y,n);
-            sz -= n;
-            x  += n;
-            y  += n;
-        } while (sz > 0);
-        return _x;
-    }   
-    fprintf(stderr,"error in %s\n",__func__); 
-    exit(1);
-}
-
-#undef SWAPCPY
-#undef SWAP_MIN
-#undef SWAP_ASS
-#endif

File qsort/t/Makefile

-include ../defs.mk
-
-APPS=u1 s1 u2 s2 f4 f8 u4 s4 u8 s8
-SRC=$(patsubst %,%.c,$(wildcard $(APPS)))
-
-all : $(APPS)
-
-u1  : csort-cmp.c ../swap.c ../csort.c $(SRC)  
-	gcc $(G) $(W) $(I) $(O) -o u1 u1.c 
-
-s1  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o s1 s1.c 
-
-u2  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o u2 u2.c 
-
-s2  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o s2 s2.c 
-
-f4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o f4 f4.c 
-
-s4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o s4 s4.c 
-
-u4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o u4 u4.c 
-
-f8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o f8 f8.c 
-
-u8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o u8 u8.c 
-
-s8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
-	gcc $(G) $(W) $(I) $(O) -o s8 s8.c 
-
-
-clean :
-	rm -f $(APPS) csort-cmp 

File qsort/t/cmp-all.sh

-#!/bin/bash -e
-
-apps="u1 s1 u2 s2 u4 s4 s8 u8 f4 f8"
-
-for app in $apps ; do
-    export app
-    ./cmp.sh
-done
-

File qsort/t/cmp.sh

-#!/usr/bin/zsh -e
-
-echo "TESTING APP: " ${app:="f8"}
-APP=$app
-
-i=(10 100 1000 10000 100000 1000000 10000000 100000000 )
-t=(10000000 1000000 100000 10000 1000 100 10 3 1 )
-sz=${#i[@]}
-c=1
-echo "Sort Comparison of unsigned integers on N numbers generating according to:"
-echo "RANDOM:    random integers"
-echo "BOUNDED:   random() % (N/4)"
-echo "SORTED:    sorted integers 1...N"
-echo "REVERSED:  sorted integers N...1"
-echo "IDENT:     all values of the array are \"1\""
-
-echo "\nRANDOM"
-echo "N               mysort (secs)   GLIBC (secs)    %impr"
-c=1
-while [ $c -lt $sz ] ; do
-    ./${APP} ${i[$c]} RAND ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-exit 0
-if [ ! $app = "f4" -a ! $app = "f8" ] ; then
-    echo "BOUNDED"
-    c=1
-    while [ $c -lt $sz ] ; do
-        ./${APP} ${i[$c]} BOUNDED ${t[$c]}  
-        c=$(( $c + 1 ))
-    done;
-fi;
-echo "SORTED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./${APP} ${i[$c]} SORTED ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "REVERSED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./${APP} ${i[$c]} REVERSE ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "IDENT"
-c=1
-while [ $c -lt $sz ] ; do
-    ./${APP} ${i[$c]} IDENT ${t[$c]}  
-    c=$(( $c + 1 ))
-done;

File qsort/t/csort-cmp.c

-/* Test harness for csort.c, useful for all C base types up to 64 bits.  
-   Uses macros for polymorphism.
-   To use, define macro TY (e.g. #define TY float) then #include this file. */
-
-#ifndef CSORT_CMP
-#define CSORT_CMP
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <math.h>
-#include <time.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/TIME.c"
-#include <unistd.h>
-#ifndef ISNAN
-#define CHECKNAN(x) (x)
-#else 
-#define CHECKNAN(x) (ISNAN((x)) ? 0 : (x)) 
-#endif
-
-enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
-
-long long k,j;
-const char* usage="csort-cmp dist N trials\n"
-"dist is one of: RAND, BOUNDED , SORTED, REVSORTED, IDENT\n"
-"N:              size of the array.\n"
-"trials:         how many trials to do.  Necessary for small N.\n";
-
-int parseDist(char* dist_str) {
-    if (!strcmp("BOUNDED",dist_str)) 
-        return BOUNDED;
-    else if (!strcmp("RAND",dist_str)) 
-        return RAND;
-    else if (!strcmp("SORTED",dist_str))
-        return SORTED;
-    else if (!strcmp("REVERSE",dist_str))
-        return REVERSE;
-    else if (!strcmp("IDENT",dist_str))
-        return IDENT;
-    else fprintf(stderr,"dist argument mismatch.\n%s\n",usage),exit(1);
-}
-
-void randomized(TY *x, long long n) {
-    long long i; 
-    union { char l[8]; TY t; } u;
-    for (i = 0; i < n; i++) {
-        u.l[0] =  random();
-        u.l[1] =  random();
-        u.l[2] =  random();
-        u.l[3] =  random();
-	u.l[4] =  random();
-        u.l[5] =  random();
-        u.l[6] =  random();
-        u.l[7] =  random();
-        
-	x[i]   =  u.t; 
-        x[i]   =  CHECKNAN(x[i]);
-    }
-}
-
-void bounded(TY *x, long long n) {
-    long long i;
-    union { long l[2]; TY t;} u;
-    for (i = 0; i < n; i++) {
-        u.l[0] = (random() % (n/4));
-        u.l[1] = (random() % (n/4));
-        x[i]   = u.t;
-        x[i]   = CHECKNAN(x[i]);
-    }
-}
-
-void identity(TY *x, long long n) {
-    long long i;
-    for (i = 0; i < n; i++) {
-        x[i] = 1;
-    }
-}
-
-void reverse(TY *x, long long n) {
-    long long i;
-    for (i = 0; i < n; i++) 
-        x[i] = n - i - 1;
-}
-
-void sorted(TY *x, long long n) {
-    long long i;
-    for (i = 0; i < n; i++) 
-        x[i] = i;
-}
-
-int compare(const void *a, const void *b) {
-    TY A = *(const TY *)a, B = *(const TY *)b;
-    if (A > B) return 1;
-    if (B < A) return -1;
-    return 0;
-}
-
-void fill(char* dist, TY* array1,long n) {
-    switch (parseDist(dist)) {
-    case RAND : 
-        randomized(array1,n) ; break;
-    case BOUNDED :
-        bounded(array1,n) ;    break;
-    case SORTED :
-        sorted(array1,n)  ;    break;
-    case REVERSE :
-        reverse(array1,n) ;    break;
-    case IDENT :
-        identity(array1,n) ;    break;
-    default :
-        fprintf(stderr,"dist match error.\n"), exit(1);
-    }
-}
-
-void checkWork(const char *name, TY *a, long long n ) {
-    long long i,j;
-    for (i = 1; i < n; i++) {
-        if (a[i-1] > a[i]) {
-            fprintf (stderr,"%s: %lld x %zd: failure at offset %lld\n", name, n,
-                     sizeof(TY), i);
-            for (j=0; j < n;j++) {
-                if (j != i) fprintf(stderr,TY_FMT " ",a[j]);
-                else { fprintf(stderr,TY_FMT "* ", a[j]); }
-            }
-            
-            fprintf(stderr,"\n"); 
-            free(a);
-            exit(1);
-        }
-    }
-}
-
-int main (int argc, char **argv)
-{
-    if (argc < 4) fprintf(stderr,"too few arguments: %d\n%s",argc,usage) , exit(1);
-    long i=j=0; long n=strtoul(argv[1],NULL,10);
-    long num_trials = strtoul(argv[3],NULL,10);
-    double start, end, m_tot=0, g_tot=0;
-    TY *array1 = (TY*) malloc (n * sizeof(TY));
-    if (array1 == NULL)
-        {
-            fprintf (stderr,"%d x %zd: no memory\n", argc, sizeof(TY));
-            return 1;
-        }
-    if (getenv("SEED")) srand(time(NULL)); /* default is debugging mode. */
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        qsort (array1,n,sizeof(TY),&compare);
-        end   = TIME();
-        if (i) {
-            g_tot += end-start;
-        }  
-        checkWork("GNU",array1,n);
-    }
-    g_tot /= (double) (num_trials - 1);
-    
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        CS(array1,n);
-        end   = TIME();
-        if (i) {
-            m_tot += end - start;
-        }    
-        checkWork("schein",array1,n);
-    
-    }
-    m_tot /= (double) (num_trials - 1);
-    
-        
-    
-    fprintf(stdout,"%10ld\t%5.10f\t%5.10f\t%2.2f\n",n,m_tot,g_tot,
-            100*((g_tot/m_tot) - 1));
-    free (array1);
-    return 0; 
-}
-#endif
-
-
-
-
-

File qsort/t/f4.c

-#include <math.h>
-#define ISNAN(x)  isnan((x))
-#define TY float
-#define TY_FMT "%f"
-#include "../ufunc/f4_sort.c"
-#define CS f4_sort
-#include "csort-cmp.c"

File qsort/t/f8.c

-#include <math.h>
-#define ISNAN(x) isnan((x))
-#define TY double
-#define TY_FMT "%lf"
-#include "../ufunc/f8_sort.c"
-#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 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 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 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 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 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 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 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 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 CSORT_SKIP_EQUALITY */
-
-#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_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_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_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_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_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_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_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_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_CSORT
-#define U8_CSORT
-#define CSORT_TY unsigned long long
-#define CS_(name) u8_## name
-#include "../csort.c"
-#endif

File usort/t/cmp.sh

 echo "TESTING APP: " ${app:="f8"}
 APP=$app
 
-i=(8 128  1024 10000 100000 1000000 10000000 100000000 )
-t=(10000000 1000000 100000 10000 1000 100 10 3 1)
+i=(8 128  1024 10000 100000 1000000 10000000)
+t=(10000000 1000000 100000 10000 1000 100 10 3)
 
 sz=${#i[@]}
 c=1
 echo "N               usort (secs)    GLIBC qsort (secs)    x-fold speedup"
 c=1
 
-while [ $c -lt $sz ] ; do
+while [ $c -le $sz ] ; do
     ./${APP} ${i[$c]} RAND ${t[$c]}  
     c=$(( $c + 1 ))
 done;