Source

usort / usort / u4_sort.c

/* c 2008 Andrew I. Schein */

/* reference:
 *
 * http://www.stereopsis.com/radix.html
 * (was possibly buggy wrt to prefetching)
 */

#include "u4_sort.h"
#include <string.h> /* __BYTE_ORDER */

#ifndef __BYTE_ORDER
#error __FILE__ ": __BYTE_ORDER is not defined!"
#endif
#if __BYTE_ORDER == __LITTLE_ENDIAN

#include <stdlib.h>
#define CSORT_TY unsigned
#define CS_(name) u4_c##name
#include "../csort/csort.c"

#define _0(v) (unsigned) ((v)         & 0x7FF)
#define _1(v) (unsigned) (((v) >> 11) & 0x7FF)
#define _2(v) (unsigned) ((v)  >> 22)
#define HIST_SIZE 2048

/* implements in place u4 radix sort. */

U4_SORT_LKG void u4_sort(unsigned *a, const long sz) {
    long j;
    unsigned pos;
    long n, sum0=0 , sum1=0 , sum2=0 , tsum=0;
    unsigned *reader, *writer, *buf = (unsigned*) malloc(sz * sizeof(unsigned));
    size_t *b0, *b1, *b2;
    if (sz < 256) { free(buf) ; return u4_csort(a,sz);  }
    b0   = malloc(HIST_SIZE * 3 * sizeof(size_t));
    b1   = b0 + HIST_SIZE;
    b2   = b1 + HIST_SIZE;
    
    memset(b0,0,3 * HIST_SIZE*sizeof(size_t));
    for (n=0; n < sz; n++) {
        b0[_0(a[n])]++; 
        b1[_1(a[n])]++; 
        b2[_2(a[n])]++; 
    }
    for (j = 0; j < HIST_SIZE; j++) { 
        tsum  = b0[j] + sum0;
        b0[j] = sum0 - 1;
        sum0  = tsum;
        
        tsum  = b1[j] + sum1;
        b1[j] = sum1 - 1;
        sum1  = tsum;
        
        tsum  = b2[j] + sum2;
        b2[j] = sum2 - 1;
        sum2  = tsum;
    }   
    
    writer = buf;
    reader = a;
    for (n=0; n < sz; n++) {
        pos = _0(reader[n]);
        writer[++b0[pos]] = reader[n];
    }
    writer = a;
    reader = buf;
    for (n=0; n < sz; n++) {
        pos = _1(reader[n]); 
        writer[++b1[pos]] = reader[n];
    }
    writer = buf;
    reader = a;
    for (n=0; n < sz; n++) {
        pos = _2(reader[n]);
        writer[++b2[pos]] = reader[n];
    }
    memcpy(a,buf,sz * sizeof(unsigned));
    free(buf);  
    free(b0);
}



#undef _0
#undef _1
#undef _2
#undef HIST_SIZE
#else /* endian */
#define CS_(name) u4_## name 
#define CSORT_TY unsigned
#include "../csort/csort.c"
#endif
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.