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

Groups > comp.lang.c > #5590

Re: efficient or clever way

Cross-posted to 2 groups.

Show all headers | 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.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

efficient or clever way "dr.oktopus" <blindwilly@freeonline.zzn.com> - 2011-06-06 01:29 -0700
  Re: efficient or clever way China Blue Angels <chine.bleu@yahoo.com> - 2011-06-06 02:12 -0700
    Re: efficient or clever way Chris H <chris@phaedsys.org> - 2011-06-06 12:50 +0100
      Re: efficient or clever way "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-06 11:38 -0700
    Re: efficient or clever way Anand Hariharan <mailto.anand.hariharan@gmail.com> - 2011-06-08 13:48 -0700
      Re: efficient or clever way China Blue Angels <chine.bleu@yahoo.com> - 2011-06-08 16:16 -0700
      Re: efficient or clever way "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-06-12 01:10 -0700
  Re: efficient or clever way pete <pfiland@mindspring.com> - 2011-06-06 08:21 -0400
    Re: efficient or clever way Voice Of Truth <oops@uhm.wow> - 2011-06-06 20:48 +0200
      Re: efficient or clever way Keith Thompson <kst-u@mib.org> - 2011-06-06 11:55 -0700
        Re: efficient or clever way Voice Of Truth <oops@uhm.wow> - 2011-06-06 20:58 +0200
      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
  Re: efficient or clever way cri@tiac.net (Richard Harter) - 2011-06-06 15:13 +0000
  Re: efficient or clever way Keith Thompson <kst-u@mib.org> - 2011-06-06 09:35 -0700
  Re: efficient or clever way Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-06-08 20:34 +0000

csiph-web