Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #415

Re: efficient or clever way

Cross-posted to 2 groups.

Show key headers only | View raw

Voice Of Truth wrote:
 
> Pete, your answers are always as short as irritating.

sfsort is my latest microoptimization of
a Leapfrogging Samplesort function
with a qsort type interface.

http://www.springerlink.com/content/p70564506802n575/

/* BEGIN sfsort.h */

#ifndef H_SFSORT_H
#define H_SFSORT_H

#include <stddef.h>

void sfsort(void *base, size_t nmemb, size_t size, 
            int (*compar)(const void *, const void *));

#endif

/* END sfsort.h */



/* BEGIN sfsort.c */

#include "sfsort.h"

static void sfrog(size_t s1, 
                  size_t ss, 
                  unsigned char *A, 
                  size_t u,
                  size_t size, 
                  int (*compar)(const void *, const void *));

void            
sfsort(void *base, size_t nmemb, size_t size, 
       int (*compar)(const void *, const void *))
{
    size_t s;

    if (nmemb > 1) {
        for (s = 1; nmemb - s > s; s += s + 1) {
            sfrog(0, s - 1, base, s + s, size, compar);
        }
        sfrog(0, s - 1, base, nmemb - 1, size, compar);
    } 
}

static void 
sfrog(size_t s1, size_t ss, 
     unsigned char *A, size_t u, size_t size, 
     int (*compar)(const void *, const void *))
{
    if (s1 - ss != 1) {
        if (u > ss) {
            unsigned char *p1, *p2, *end, swap;
            const size_t  sm = (ss - s1) / 2 + s1;
            const size_t sms = sm * size;
                  size_t   j = (u + 1) * size;
                  size_t   i = ss * size;

            do {
                i += size;
            } while (j > i && compar(A + sms, A + i) > 0);
            do {
                j -= size;
            } while (j > i && compar(A + j, A + sms) > 0);
            while (j > i) {
                p1  = A + j;
                p2  = A + i;
                end = p2 + size;
                do {
                    swap  = *p1;
                    *p1++ = *p2;
                    *p2++ = swap;
                } while (p2 != end);
                do {
                    i += size;
                } while (j > i && compar(A + sms, A + i) > 0);
                do {
                    j -= size;
                } while (j > i && compar(A + j, A + sms) > 0);
            } 
            if (j == i) {
                j -= size;
            }        
            i = ss * size;
            if (j > i) {
                end = A + sms;
                p1  = A + j + size;
                p2  = A + i + size;
                do {
                    swap = *--p2;
                    *p2  = *--p1;
                    *p1  = swap;
                } while (p2 != end);
                j /= size;
                i = sm + j - ss + 1;
                sfrog(s1, sm - 1, A, i - 2, size, compar);
            } else {
                j = ss;
                i = sm + 1;
            }
            sfrog(i, j, A, u, size, compar);
        }
    } else {
        sfsort(A + s1 * size, u - ss, size, compar);
    }
}

/* END sfsort.c */


-- 
pete

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: efficient or clever way pete <pfiland@mindspring.com> - 2011-06-06 19:10 -0400
  Re: efficient or clever way Voice Of Truth <oops@uhm.wow> - 2011-06-07 05:54 +0200

csiph-web