/* I though this was _genius_ ... with a capital GENIUS ... ... I was wrong Try as I might, I cannot beat Linux's qsort() :/ For blocksize == 500k, my time was 1.2 sec. qsort's time was half that*/#include <stdlib.h>#include <string.h>#include <stdio.h> // temporary?#include "globals.h" // "//#define USEQSORT//#define DOSORTTEST/* -------- Constants -------- */#define SORTBLOCK_OKAY 0#define SORTBLOCK_NOMEM 1#define SORT_DIVIDER 200/* -------- Macros -------- */#define WOFFSET(x) (((x) + (G_Woffset)) % G_N)/* -------- Typedefs -------- */typedef int (*QSCompare)(const void *, const void *);/* -------- "Global" variables -------- */u_char * G_S;u_int G_N;u_int * G_W;u_int G_Woffset;//u_int * Vcopy;/* -------- Function prototypes -------- */void SortIndexes (u_int [], u_int);/* -------- Local procedures -------- */int CompareByString(const u_int * a, const u_int * b){ u_char * L_Sa = G_S + *a, * L_Sb = G_S + *b; u_int i; for (i = 0; i < G_N; i++) { if (L_Sa[i] != L_Sb[i]) return ( L_Sa[i] < L_Sb[i] ? -1 : 1); } return (0);}int CompareByUInt(const u_int * a, const u_int * b){ u_int oa = WOFFSET(*a), ob = WOFFSET(*b); if (G_W[oa] == G_W[ob]) return (0); return ( G_W[oa] < G_W[ob] ? -1 : 1 );}/* Wrote this off the top of my head. It doesn't work (still has bugs), but it's enough to see that it slows it down by another factor of 2void RadixSort(u_int V[], u_int N){#define GETWBYTE(w) ((G_W[WOFFSET(w)] >> bitshift) & 0xFF) u_int Vsize = sizeof(u_int) * N; u_int tablesize = sizeof(u_int) * ALPHABET_SIZE; u_int offsets[ALPHABET_SIZE], counts[ALPHABET_SIZE]; u_int bitshift, i, j, b; bitshift = 0; for (;;) { memmove (Vcopy, V, Vsize); memset (offsets, 0, tablesize); memset (counts, 0, tablesize); for (i = 0; i < N; i++) for (j = GETWBYTE(Vcopy[i])+1; j < ALPHABET_SIZE; j++) offsets[j]++; for (i = 0; i < N; i++) { b = GETWBYTE(Vcopy[i]); V[i] = offsets[b] + counts[b]++; } if (bitshift == 24) break; bitshift += 8; }}*/void MySort(u_int V[], u_int N){ u_int a, b, vala, valb; qsort (V, N, sizeof(u_int), (QSCompare)CompareByUInt);// RadixSort (V, N); a = 0, b = 1; do { vala = G_W[WOFFSET(V[a])]; do valb = G_W[WOFFSET(V[b])]; while (valb == vala && ++b < N); G_Woffset += 4; SortIndexes (V + a, b - a); G_Woffset -= 4; a = b++; } while (b < N);}void SortIndexes(u_int V[], u_int N){ if (N > 1) {#ifndef USEQSORT if (N >= SORT_DIVIDER) MySort (V, N); else#endif qsort(V, N, sizeof(u_int), (QSCompare)CompareByString); }}/* -------- Exported procedures -------- */u_int SortBlock(u_char S[], u_int N, u_int V[]){ // S = string to sort as a block twice, back to back; N = length of string // Example, if string is "example", S = "exampleexample", N = 7 (not 14) // Strictly speaking, the last character (the 'e' in this case) is optional // Assume V is allocated to at least N uninitialized elements // and that |S| >= 2*N-1 u_int i; for (i = 0; i < N; i++) V[i] = i; // These _have_ to be global so that the quicksort compare // procedures can find them G_S = S; G_N = N; G_Woffset = 0; G_W = malloc(N * sizeof(u_int)); if (G_W == 0) return (SORTBLOCK_NOMEM);// Vcopy = malloc(N * sizeof(u_int));// if (Vcopy == 0) return (SORTBLOCK_NOMEM); for (i = 0; i < N; i++) G_W[i] = (S[V[i]] << 24) | (S[V[i]+1] << 16) | (S[V[i]+2] << 8) | S[V[i]+3]; SortIndexes (V, N);#ifdef DOSORTTEST { // DAT u_int * Vcheck = malloc(sizeof(u_int) * N); for (i = 0; i < N; i++) Vcheck[i] = i; qsort (Vcheck, N, sizeof(u_int), (QSCompare)CompareByString); for (i = 0; i < N; i++) if (Vcheck[i] != V[i]) { printf ("Block didn't sort correctly (%u:%u,%u)\n", i, V[i], Vcheck[i]); break; } if (i == N) printf ("Sorted %u bytes perfectly\n", N); free (Vcheck); }#endif// free (Vcopy); free (G_W); return (SORTBLOCK_OKAY);}int main(){ FILE * file = fopen("test/read2m", "rb"); if (!file) { WARNING ("Bad file name"); return (-1); } u_int length = 500 * 1024; u_char * block = malloc(length * 2 - 1); if (!block) WARNING ("malloc() failed in main"); u_int * V = malloc(length * sizeof(u_int)); /// alocate memory if (!V) { free (block); WARNING ("malloc() (2) failed in main"); } if (fread(block, length, 1, file) != 1) WARNING ("fread() failed") fclose (file); memmove (block+length, block, length-1); /// write it twice (almost) if (SortBlock(block, length, V) != SORTBLOCK_OKAY) WARNING ("SortBlock() failed"); // should never happen unless your // PC is in desperate need of a RAM upgrade or your block size // (length) is absurdly large (or you're playing a game thru cedega) printf ("SortBlock() succeeded\n"); free (V); free (block); return (0);}