Commits

Anonymous committed 2cdbe9d

back up.

Comments (0)

Files changed (24)

qsort/.back/.hgignore~

-.back/

qsort/.back/Makefile~

-include defs.mk
-
-.PHONY : clean all
-
-all :
-	cd t/ ; make all
-
-clean : 
-	cd t/ ; make clean

qsort/.back/README~

-Key files :
-
-1. qsort.c - the quicksort template
-2. ufunc/* - #include variants for major C types
-3. t/*     - test files.
-

qsort/.back/TODO~

-1. complete ufunc test
-2. struct test.

qsort/.back/cb.sh~

-#!/bin/zsh -e
-
-i=(10 100 1000 10000 100000 1000000 10000000 100000000 )
-t[0]=10000000
-t[1]=1000000
-t[2]=100000
-t[3]=10000
-t[4]=1000
-t[5]=100
-t[6]=10
-t[7]=3
-t[8]=1
-sz=${#i[@]}
-c=1
-echo "\nRANDOM"
-while [ $c -lt $sz ] ; do
-    export TRIALS=${t[$c]}
-    ./a.out ${i[$c]}
-    c=$(( $c + 1 ))
-done;

qsort/.back/chump.sh~

-#!/usr/bin/zsh -e
-
-APP=qsort-cmp
-
-i=(10 100 1000 10000 100000 1000000 10000000 100000000 )
-t[0]=10000000
-t[1]=1000000
-t[2]=100000
-t[3]=10000
-t[4]=1000
-t[5]=100
-t[6]=10
-t[7]=3
-t[8]=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;
-echo "BOUNDED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./${APP} ${i[$c]} BOUNDED ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-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;

qsort/.back/cmp-3way.sh~

-#!/usr/bin/zsh -e
-
-i=(10 100 1000 10000 100000 1000000 10000000 100000000 )
-t[0]=10000000
-t[1]=1000000
-t[2]=100000
-t[3]=10000
-t[4]=1000
-t[5]=100
-t[6]=10
-t[7]=3
-t[8]=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"
-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  CB (secs) "
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-3way-cmp ${i[$c]} RAND ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "BOUNDED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-3way-cmp ${i[$c]} BOUNDED ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "SORTED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-3way-cmp ${i[$c]} SORTED ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "REVERSED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-3way-cmp ${i[$c]} REVERSE ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "IDENT"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-3way-cmp ${i[$c]} IDENT ${t[$c]}  
-    c=$(( $c + 1 ))
-done;

qsort/.back/cmp.sh~

-#!/usr/bin/zsh -e
-
-i=(10 100 1000 10000 100000 1000000 10000000 100000000 )
-t[0]=10000000
-t[1]=1000000
-t[2]=100000
-t[3]=10000
-t[4]=1000
-t[5]=100
-t[6]=10
-t[7]=3
-t[8]=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
-    ./qsort-cmp ${i[$c]} RAND ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "BOUNDED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-cmp ${i[$c]} BOUNDED ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "SORTED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-cmp ${i[$c]} SORTED ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "REVERSED"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-cmp ${i[$c]} REVERSE ${t[$c]}  
-    c=$(( $c + 1 ))
-done;
-echo "IDENT"
-c=1
-while [ $c -lt $sz ] ; do
-    ./qsort-cmp ${i[$c]} IDENT ${t[$c]}  
-    c=$(( $c + 1 ))
-done;

qsort/.back/defs.mk~

-I=-L/usr/lib/gcc/i486-linux-gnu/4.2/ -I../  -I/usr/include 
-W=-Wall
-#O=-fmudflap -lmudflap
-<<<<<<< /home/ais/src/open/sorting/qsort/defs.mk.orig.17898557
-O=-O9 -g
-||||||| /tmp/defs.mk~base.ky63Wr
-O=-O9
-=======
-O=-O2 -fno-inline-functions
-G=-g
->>>>>>> /tmp/defs.mk~other.lcXu6L
-LD_LIBRARY_PATH=/usr/lib/gcc/i486-linux-gnu/4.2:/usr/lib:/lib:$(LD_LIBRARY_PATH)
-CC=gcc#/usr/bin/colorgcc
-OBJS=$(patsubst %.c,%.o,$(wildcard *.c))
-
-%.o : %.c
-	$(CC) $(I) $(W) $(O) -o $@ -c $<

qsort/.back/f4-qsort-cmp.c~

-#include <stdio.h>
-#include <stdlib.h>
-
-#define  QSORT_TY TY
-#define  QS_(name) u4_##name
-#include "qsort.c"
-#include <time.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/gettimeofdayfp.c"
-#include <unistd.h>
-
-enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
-
-long k,j;
-const char* usage="qsort-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(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random();
-    }
-}
-
-void bounded(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random() % (n/4);
-    }
-}
-
-void identity(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = 1;
-    }
-}
-
-void reverse(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = n - i - 1;
-}
-
-void sorted(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = i;
-}
-
-
-int compare(const void *a, const void *b) {
-    unsigned A = *(const unsigned *)a, B = *(const unsigned *)b;
-    return (int) (A - B);
-}
-
-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(unsigned *a, long long n) {
-    long long i,j;
-    for (i = 1; i < n; i++) {
-        if (a[i-1] > a[i]) {
-            fprintf (stderr,"u4_sort: %lld x %zd: failure at offset %lld\n", n,
-                     sizeof(TY), i);
-            for (j=0; j < n;j++)
-                fprintf(stderr,"%d ",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,"%zd 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);
-        if (gettimeofdayfp(&start,NULL)) fprintf(stderr,"timeerror\n"), exit(1);
-        qsort (array1,n,4,&compare);
-        if (gettimeofdayfp(&end,NULL)) fprintf(stderr,"timeerror\n"), exit(1);
-        if (i) {
-            g_tot += end-start;
-        }  
-    }
-    g_tot /= (double) (num_trials - 1);
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        if (gettimeofdayfp(&start,NULL)) fprintf(stderr,"timeerror\n"), exit(1);
-        u4_sort (array1,n);
-        if (gettimeofdayfp(&end,NULL))   fprintf(stderr,"timeerror\n"), exit(1);
-        if (i) {
-            m_tot += end - start;
-        }    
-        checkWork(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; 
-}
-
-
-
-
-
-

qsort/.back/f4_sort.c~

-#ifndef F4_SORT
-#define F4_SORT
-#define QSORT_TY unsigned long
-#define QS_(name) f4_## name
-#include "qsort.c"
-#endif

qsort/.back/f8_sort.c~

-#ifndef F8_SORT
-#define F8_SORT
-#define QSORT_TY unsigned long
-#define QS_(name) f4_## name
-#include "qsort.c"
-#endif

qsort/.back/qsort-3way-cmp.c~

-#include <stdio.h>
-#include <stdlib.h>
-#define QSORT_TY unsigned
-#define TY unsigned
-#define  QS_(x)        u4_##x
-#include "qsort.c"
-#include <time.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/TIME.c"
-#include <unistd.h>
-
-#define  S_VAL_T unsigned
-#define  S_IDX_T unsigned long
-#define  S_LESS(x,y)   (*(x) <  *(y))
-#define  S_LESSEQ(x,y) (*(x) <= *(y))
-#define  S_EQ(x,y)     (*(x) == *(y))
-#include "cb/gen/sort.c"
-
-enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
-
-long k,j;
-const char* usage="qsort-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(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random();
-    }
-}
-
-void bounded(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random() % (n/4);
-    }
-}
-
-void identity(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = 1;
-    }
-}
-
-void reverse(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = n - i - 1;
-}
-
-void sorted(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = i;
-}
-
-
-int compare(const void *a, const void *b) {
-    unsigned A = *(const unsigned *)a, B = *(const unsigned *)b;
-    return (int) (A - B);
-}
-
-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);
-    }
-}
-
-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, c_tot=0;
-    TY *array1 = (TY*) malloc (n * sizeof(TY));
-    if (array1 == NULL)
-        {
-            fprintf (stderr,"%zd x %zd: no memory\n", argc, sizeof(TY));
-            return 1;
-        }
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        qsort (array1,n,4,&compare);
-        end   = TIME();
-        if (i) {
-            g_tot += end-start;
-        }  
-    }
-    g_tot /= (double) (num_trials - 1);
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        u4_sort (array1,n);
-        end   = TIME();
-        if (i) {
-            m_tot += end - start;
-        }    
-    }
-    m_tot /= (double) (num_trials - 1);
-    
-    for (i = 1; i < n; i++)
-        {
-            if (array1[i-1] > array1[i])
-                {
-                    fprintf (stderr,"ssort: %ld x %zd: failure at offset %ld\n", n,
-                             sizeof(TY), i);
-                    for (j=0; j < n;j++)
-                        fprintf(stderr,"%d ",array1[j]);
-                    fprintf(stderr,"\n"); 
-                    free(array1);
-                    exit(1);
-                }
-        }
-  
-        
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        S_SORT (array1,n);
-        end   = TIME();
-        if (i) {
-            c_tot += end - start;
-        }    
-    }
-    c_tot /= (double) (num_trials - 1);
-    
-    for (i = 1; i < n; i++)
-        {
-            if (array1[i-1] > array1[i])
-                {
-                    printf ("csort: %ld x %d: failure at offset %ld\n", n,
-                            sizeof(TY), i);
-                    for (j=0; j < n;j++)
-                        printf("%d ",array1[j]);
-                    printf("\n"); 
-                    free(array1);
-                    return 1;
-                }
-        }
-    
-    
-    
-    fprintf(stdout,"%10ld\t%5.10f\t%5.10f\t%2.2f\t%5.10f\t%2.2f\n",n,m_tot,g_tot,
-            100*((g_tot/m_tot) - 1), c_tot, 100 * ((g_tot/c_tot) - 1));
-    free (array1);
-    return 0; 
-}
-
-
-
-
-
-

qsort/.back/qsort-cmp.c~

-#include <stdio.h>
-#include <stdlib.h>
-
-#define  TY unsigned
-#define  QSORT_TY TY
-#define  QS_(name) u4_##name
-#include "qsort.c"
-#include <time.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/TIME.c"
-#include <unistd.h>
-
-enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
-
-long k,j;
-const char* usage="qsort-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(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random();
-    }
-}
-
-void bounded(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random() % (n/4);
-    }
-}
-
-void identity(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = 1;
-    }
-}
-
-void reverse(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = n - i - 1;
-}
-
-void sorted(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = i;
-}
-
-
-int compare(const void *a, const void *b) {
-    unsigned A = *(const unsigned *)a, B = *(const unsigned *)b;
-    return (int) (A - B);
-}
-
-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(unsigned *a, long long n) {
-    long long i,j;
-    for (i = 1; i < n; i++) {
-        if (a[i-1] > a[i]) {
-            fprintf (stderr,"u4_sort: %lld x %zd: failure at offset %lld\n", n,
-                     sizeof(TY), i);
-            for (j=0; j < n;j++)
-                fprintf(stderr,"%d ",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,"%zd 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,4,&compare);
-        end   = TIME();
-        if (i) {
-            g_tot += end-start;
-        }  
-    }
-    g_tot /= (double) (num_trials - 1);
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        u4_sort (array1,n);
-        end   = TIME();
-        if (i) {
-            m_tot += end - start;
-        }    
-        checkWork(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; 
-}
-
-
-
-
-
-

qsort/.back/qsort-test.c~

-#include <stdio.h>
-#include <stdlib.h>
-#define QSORT_TY unsigned
-#define TY unsigned
-#include "qsort.c"
-
-TY *array;
-TY *array_end;
-unsigned member_size;
-
-int
-test (size_t nmemb)
-{
-    int j=0;
-    array = malloc (nmemb * sizeof(TY));
-    if (array == NULL)
-        {
-            printf ("%zd x %zd: no memory", nmemb, sizeof(TY));
-            return 1;
-        }
-    
-    array_end = array + nmemb;
-    member_size = nmemb;
-    unsigned long i;
-    for (i = 0; i < nmemb; i++)
-        {
-            array[i] = (TY) random() % 64;
-        }
-    
-    ssort (array, nmemb);
-    
-    for (i = 1; i < nmemb; i++)
-        {
-            if (array[i-1] > array[i])
-                {
-                    
-                    printf ("%zd x %d: failure at offset %ld\n", nmemb,
-                            sizeof(TY), i);
-                    
-                    for (j=0; j < nmemb;j++)
-                        printf("%d ",array[j]);
-                        printf("\n"); 
-                    free (array);
-                    return 1;
-                }
-        }
-    
-    free (array);
-    return 0;
-}
-
-int main (int argc, char **argv)
-{
-    int ret = 0;
-    if (argc >= 2)
-        ret |= test (atoi (argv[1]));
-    else
-        {
-            ret |= test (10000);
-            ret |= test (200000);
-            ret |= test (2000000);
-            ret |= test (2132310);
-            ret |= test (1202730);
-            ret |= test (1184710);
-            ret |= test (272710);
-            ret |= test (14170);
-            ret |= test (4170);
-        }
-    
-    return ret;
-}
-
-
-
-
-
-

qsort/.back/qsort.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: QSORT_TY, QSORT_LT
-   Recommended: 
-   1. #define QS_(name) ty_##name, e.g. QS_(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.
-
-*/
-
-#ifndef QSORT
-#define QSORT
-#if !defined LIBBING_AS_QSORT
-#  define QSORT_LKG static inline
-#else
-#  define QSORT_LKG 
-#endif
-
-#ifndef QSORT_TY
-#  error "qsort.c imported without QSORT_TY definition."
-#endif
-
-/* can redefine with type_ */
-#ifndef QS_
-#  define QS_(name) QS_##name
-#endif
-
-#include "swap.c" 
-/* smaller than this value => insertion sort */
-#define QSORT_ISORT_SWITCH 32
-#define QSORT_NINTHER_SWITCH 64
-
-/* Comparisons... default to arithmatic */
-#ifndef QSORT_EQ
-#  define QSORT_EQ(a,b) (*(a) == *(b))
-#endif
-#ifndef QSORT_LT
-#  define QSORT_LT(a,b) (*(a) < *(b))
-#endif
-#ifndef QSORT_LE
-#  define QSORT_LE(a,b) (*(a) <= *(b))
-#endif
-
-#define QSORT_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)))
-
-
-static inline void QS_(SWAP)(QSORT_TY *a, QSORT_TY *b) {
-    /* made a function since arguments tend to be incremented by caller */
-    QSORT_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) {
-    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;
- 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);
-    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);    
-    } 
-    pm    = QSORT_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 */
-            b++; 
-        }  
-        while (c >= b && QSORT_LE(&pivot,c)) { 
-            if (QSORT_EQ(c,&pivot)) QS_(SWAP)(d--,c);  
-            c--; 
-        }
-        if (b > c) break;
-        QS_(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));
-    if ((b-a) < n-(d-c)) {  /* recurse on smaller first to bound memory usage. */
-        if ((b-a) > 1) QS_(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) QS_(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
-#endif

qsort/.back/s1_sort.c~

-#ifndef S1_SORT
-#define S1_SORT
-#define QSORT_TY signed char
-#define QS_(name) u1_## name
-#include "qsort.c"
-#endif

qsort/.back/s2-qsort-cmp.c~

-#include <stdio.h>
-#include <stdlib.h>
-
-#define  TY unsigned
-#define  QSORT_TY TY
-#define  QS_(name) u4_##name
-#include "qsort.c"
-#include <time.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/TIME.c"
-#include <unistd.h>
-
-enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
-
-long k,j;
-const char* usage="qsort-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(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random();
-    }
-}
-
-void bounded(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = random() % (n/4);
-    }
-}
-
-void identity(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) {
-        x[i] = 1;
-    }
-}
-
-void reverse(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = n - i - 1;
-}
-
-void sorted(unsigned *x, long n) {
-    long i;
-    for (i = 0; i < n; i++) 
-        x[i] = i;
-}
-
-
-int compare(const void *a, const void *b) {
-    unsigned A = *(const unsigned *)a, B = *(const unsigned *)b;
-    return (int) (A - B);
-}
-
-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(unsigned *a, long long n) {
-    long long i,j;
-    for (i = 1; i < n; i++) {
-        if (a[i-1] > a[i]) {
-            fprintf (stderr,"u4_sort: %lld x %zd: failure at offset %lld\n", n,
-                     sizeof(TY), i);
-            for (j=0; j < n;j++)
-                fprintf(stderr,"%d ",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,"%zd 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,4,&compare);
-        end   = TIME();
-        if (i) {
-            g_tot += end-start;
-        }  
-    }
-    g_tot /= (double) (num_trials - 1);
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        u4_sort (array1,n);
-        end   = TIME();
-        if (i) {
-            m_tot += end - start;
-        }    
-        checkWork(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; 
-}
-
-
-
-
-
-

qsort/.back/sort.c~

-/* Bentley,McIlroy: "Engineering a Sort Function".  #include'r MUST define: */
-/*   S_(name) S_IDX_T S_VAL_T {S_CMP|(S_LESS,S_LESSEQ,S_EQ)}(x,y) and MAY   */
-/* define S_RECV S_PASS S_SWAP, if desired. NOTE: CMP/SWAP take *ADDRS*.    */
-#include "cb/memswap.c"
-#ifndef S_LKG
-#define S_LKG  static inline
-#endif
-#ifndef S_ILKG
-#define S_ILKG static inline
-#endif
-#ifndef S_
-#define S_(x) S_##x
-#endif
-#ifdef S_CMP            /* Allow optimization to single comparison op */
-#ifndef S_LESS
-#define S_LESS(a,b)     (S_CMP(a,b) < 0)
-#endif
-#ifndef S_LESSEQ
-#define S_LESSEQ(a,b)   (S_CMP(a,b) <= 0)
-#endif
-#ifndef S_EQ
-#define S_EQ(a,b)       (S_CMP(a,b) == 0)
-#endif
-#endif
-#ifndef S_STRIDE   /* If the below S_SWAP funcs are inadequate (e.g. objects  */
-#define S_STRIDE 1 /* are not sized to be sizeof(S_VAL_T)), then the includer */
-#endif             /* will want to define STRIDE=sz/sizeof(VAL_T)&S_SWAP(i,j).*/
-#ifndef S_RECV     /* These defs may, in turn, require run-time metadata.     */
-#define S_RECV     /* So, we allow includer to define S_RECV to receive extra */
-#endif             /* function parameters at the entry point, S_SORT, and also*/
-#ifndef S_PASS     /* define S_PASS to propagate them to CMP/SWAP uses.       */
-#define S_PASS     /* Since these default to empty strings, these definitions */
-#endif             /* MUST include a leading ",".                             */
-#ifndef S_SWAP  /* This works when compiler knows how to copy an S_VAL_T */
-static inline void S_(swap)(S_VAL_T *i, S_VAL_T *j) {
-    S_VAL_T t = *i;
-    *i        = *j;
-    *j        =  t;
-}
-#define S_SWAP S_(swap)
-#endif /* S_SWAP */
-#ifndef S_VSWAP
-#define S_VSWAP(i,j,n)  memswap(i, j, (n)*sizeof *i)
-#endif /* S_VSWAP */
-#ifndef S_INSERTION
-#define S_INSERTION 23
-#endif
-#ifndef S_TUKEY9TH
-#define S_TUKEY9TH  64
-#endif
-#ifndef S_MIN
-#define S_MIN(x,y) ((x) < (y) ? (x) : (y))
-#endif
-      
-S_ILKG void S_(insort)(S_VAL_T *x, S_IDX_T N  S_RECV) {
-    S_VAL_T  *l = x, *m, *n = x + N*S_STRIDE; /* binsearch a bad optim */
-    for (m = x + S_STRIDE;  m < n;  l = m, m += S_STRIDE) {
-#ifdef S_BIGOBJ /* Up to 2+X faster for objects >>~ 64 Bytes w/gcc on core2 */
-        for (/**/; l >= x && S_LESS(m, l); l -= S_STRIDE)
-            /**/;
-        S_VAL_T t[S_STRIDE];    /*NOTE l=x and l=m matter for this branch */
-        memcpy (t, m, sizeof t);
-        memmove(l + 2*S_STRIDE, l + 1*S_STRIDE, (m - l - 1*S_STRIDE)*sizeof *x);
-        memcpy (l + 1*S_STRIDE, t, sizeof t);
-#else           /* Up to ~2X faster for objects <<~ 64 Bytes w/gcc on core2 */
-        for (l = m; l > x && S_LESS(l, l - S_STRIDE); l -= S_STRIDE)
-            S_SWAP(l, l - S_STRIDE);
-#endif
-    }
-}
-
-S_ILKG S_VAL_T *S_(med3)(S_VAL_T *a, S_VAL_T *b, S_VAL_T *c  S_RECV) {
-    return S_LESS(a,b) ? (S_LESS(b,c) ? b : (S_LESS(a,c) ? c : a) )
-                       : (S_LESS(c,b) ? b : (S_LESS(a,c) ? a : c) );
-}
-
-S_ILKG S_VAL_T *S_(pivot)(S_VAL_T *x, S_IDX_T N  S_RECV) {
-    S_VAL_T *l = x,
-            *m = x + (N >> 1)*S_STRIDE,
-            *n = x + (N - 1)*S_STRIDE;
-    if (N > S_TUKEY9TH) {
-        S_IDX_T D = (N >> 3)*S_STRIDE;
-        l = S_(med3)(    l    , l + D, l + 2 * D  S_PASS);
-        m = S_(med3)(  m - D  ,   m  ,   m + D    S_PASS);
-        n = S_(med3)(n - 2 * D, n - D,     n      S_PASS);
-    }
-    return S_(med3)(l, m, n  S_PASS);
-}
-
-S_LKG void S_SORT(S_VAL_T *x, S_IDX_T N  S_RECV) {
-    S_VAL_T *a, *b, *c, *d,  *m, *n;
-    long     r; int swap_flg;
-L:  swap_flg = 0;
-    if (N <= S_INSERTION) { S_(insort)(x, N  S_PASS); return; }
-    m = S_(pivot)(x, N  S_PASS);
-    S_SWAP(x, m);
-    a = b = x + S_STRIDE;
-    c = d = x + (N - 1) * S_STRIDE;
-    for (;;) {                          /* Fat partition (good w/many ties) */
-        for (/**/; b <= c && S_LESSEQ(b, x); b += S_STRIDE)
-            if (S_EQ(x, b))
-                { S_SWAP(a, b); a += S_STRIDE; swap_flg = 1; }
-        for (/**/; b <= c && S_LESS(x, c); c -= S_STRIDE)
-            if (S_EQ(x, c))
-                { S_SWAP(c, d); d -= S_STRIDE; swap_flg = 1; }
-        if (b > c)
-            break;
-        S_SWAP(b, c); b += S_STRIDE; c -= S_STRIDE; swap_flg = 1;
-    }
-    if (!swap_flg)                      /* No Swaps: switch to insort */
-        { S_(insort)(x, N  S_PASS); return; }
-    n = x + N*S_STRIDE;
-    r = S_MIN(a - x, b - a);            S_VSWAP(x, b - r, r / S_STRIDE);
-    r = S_MIN(d - c, n - d - S_STRIDE); S_VSWAP(b, n - r, r / S_STRIDE);
-    if ((r = b - a) > S_STRIDE)         /* Recurse */
-        S_SORT(x, r / S_STRIDE  S_PASS);
-    if ((r = d - c) > S_STRIDE) {       /* Iterate rather than recurse */
-        x = n - r;                      /*XXX should recurse on smaller side */
-        N = r / S_STRIDE;
-        goto L;
-    }
-}
-#ifndef S_PRESERVE
-#  undef S_IDX_T
-#  undef S_VAL_T
-#  undef S_LESS
-#  undef S_LESSEQ
-#  undef S_EQ
-#  undef S_CMP
-#  undef S_SORT
-#  undef S_INSERTION
-#  undef S_TUKEY9TH
-#  undef S_STRIDE
-#  undef S_RECV
-#  undef S_PASS
-#  undef S_SWAP
-#  undef S_VSWAP
-#  undef S_MIN
-#  undef S_
-#endif /* S_PRESERVE */

qsort/.back/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.d=*(int_fast64_t*)x, *((int_fast64_t*)x)=*((int_fast64_t*)y), *((int_fast64_t*)y)= buf.d)
-#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

qsort/.back/time_test.c~

-#include <stdio.h>
-#include <stdlib.h>
-#include <errno.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/gettimeofdayfp.c"
-#include <unistd.h>
-
-/* timing results testring. */
-
-int VERBOSE=0;
-float  start, end;
-
-int main(int ac, char **av) {
-    if (gettimeofdayfp(&start)) 
-        fprintf(stderr,"time error: %s.\n",strerror(errno)), exit(1);
-    sleep(3);
-    if (gettimeofdayfp(&end)) 
-        fprintf(stderr,"time error: %s.\n",strerror(errno)), exit(1);
-    printf("end: %f\n",end);
-    printf("elapsed time: %f",end-start); 
-}

qsort/.back/u1_sort.c~

-#define QSORT_TY char
-#define QS_(name) u1_## name

qsort/.back/u4-qsort.c~

-#include <stdio.h>
-#include <stdlib.h>
-#include <errno.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/gettimeofdayfp.c"
-
-
-int VERBOSE=0;
-double  start, end;
-double diff,g_tot=0, c_tot=0;
-typedef unsigned u4;
-
-#define  TY u4
-#define  S_VAL_T TY
-#define  S_IDX_T unsigned long
-#define  S_LESS(x,y)   ((x) < (y))
-#define  S_LESSEQ(x,y) ((x) <= (y))
-#define  S_EQ(x,y)     ((x) == (y))
-#define  S_(x)          u4_sort_ ## x
-#define  S_SORT         u4_sort
-#include "sort.c"
-
-int u4cmp(const void *a, const void *b) {
-    u4 A = *(const u4 *)a, B = *(const u4 *)b;
-    return (int) (A - B);
-}
-
-int checkWork(const TY *a, const size_t M, const char* label) {
-    int i=0,j=0;
-    for (i = 1; i < M; i++) {
-        if (a[i-1] > a[i]) {
-            fprintf (stderr,"%s: %zd -- failure at offset %zd\n", label , M, i);
-            for (j=0; j < M;j++)
-                printf("%d ",a[j]);
-            printf("\n"); 
-            return 1;
-        }
-    }
-    return 0;
-}
-
-int main(int ac, char **av) {
-    u4  i,j, trial, TRIALS = getenv("TRIALS") ? atoi(getenv("TRIALS")) : 21;
-    u4  *orig = (u4*)calloc(strtoul(av[1],NULL,10), 4);
-    u4  *a    = (u4*)calloc(strtoul(av[1],NULL,10), 4);
-    float dt = 0;
-    unsigned long  M = atoi(av[1]);
-    printf("testing: %ld\n", M);
-    for (trial = 0; trial < TRIALS; trial++) {
-        for (i = 0; i < M; i++) /* generate random data */
-            orig[i] = random();
-        
-        /* GNU qsort testing section */
-        memcpy(a,orig,sizeof(u4)*M);  
-        if (gettimeofdayfp(&start,NULL)) 
-            fprintf(stderr,"time error: %s.\n",strerror(errno)), exit(1);
-        qsort((void *)a, M, sizeof *a, u4cmp);
-        if (trial) { /* drop cold cache tm */
-            if (gettimeofdayfp(&end,NULL)) 
-                fprintf(stderr,"time error: %s.\n",strerror(errno)), exit(1);
-            g_tot += end - start;
-        }
-        if (checkWork(a,M,"GNU qsort\n")) exit(1);
-        
-        /* now for cb testing section */
-        memcpy(a,orig,sizeof(u4)*M); 
-        if (gettimeofdayfp(&start,NULL)) 
-            fprintf(stderr,"time error: %s.\n",strerror(errno)), exit(1);
-        u4_sort((void *)a, M);
-        if (trial) { /* drop cold cache tm */
-            if (gettimeofdayfp(&end,NULL)) 
-                fprintf(stderr,"time error: %s.\n",strerror(errno)), exit(1);
-            c_tot += end - start;
-            }
-        if (checkWork(a,M,"CB sort")) exit(2);
-    }
-    
-    printf("elts: %10d  GNU sec:%7.7f  CB sec:%7.7f\n", M, g_tot / (float)(TRIALS - 1), c_tot / (float)(TRIALS - 1));
-    
-    return 0;
-}

qsort/.back/u4_sort.c~

-#ifndef U4_SORT
-#define U4_SORT
-#define QSORT_TY unsigned long
-#define QS_(name) u4_## name
-#include "qsort.c"
-#endif