Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 23 Oct 2012 15:03:49 -0500
Message-ID: <5086F827.596E@mindspring.com>
Date: Tue, 23 Oct 2012 16:03:51 -0400
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: How to apply qsort() with a parameter?
References: <k6413q$l7u$1@news.albasani.net> <k6549r$sdr$1@news.albasani.net> <lny5ixeo5k.fsf@nuthaus.mib.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 77
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.221.243
X-Trace: sv3-QWCz2U28ilSpexG8jzmaRrwKeYavHHdj36FdMgCXqhBjU773gmkg3+ylD+q/ABKg5ELWjN/64VwFmay!zJQXZEH4sj+ow7TV9JFs1jrMs8lJaS64cI9s63mN0y7jqbKE/gqDaCu8Z7edH1kyDL4J9rf7uccO!Vuw19zAaXdo=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3329
Xref: csiph.com comp.lang.c:27602

Keith Thompson wrote:
> 
> rouben@shady.(none) (Rouben Rostamian) writes:
> [...]
> > Thank you everyone for your suggestions and comments.
> > I knew about GNU's qsort_r() with its extra parameter.
> > It does exactly what I need.  The reason I asked the
> > question here is that I was holding out hope that
> > there may be a way of doing something similar in
> > standard C.  From the responses it appears that it is
> > not possible.
> 
> If qsort_r() isn't already written in standard C,
> I'm sure it could be.

qsortR,
1   is usable in the same way that qsort_r is
2   is small
3   and has subquadratic worst case behavior.

I could easily come up with a faster
but larger function of the same type, 
if anyone wants to see one.

Here's qsortR:

#include <stddef.h>

void 
qsortR(void *base, size_t nmemb, size_t size, void *thunk, 
       int (*compar)(void *, const void *, const void *))
{
    size_t bytes, h, t;
    unsigned char *array, *after, *i, *j, *k;
    unsigned char *p1, *p2, *end, swap;

    if (nmemb > 1) {
        array = base;
        after = nmemb * size + array;
        nmemb /= 4; 
        h = nmemb + 1;  
        for (t = 1; nmemb != 0; nmemb /= 4) {
            t *= 2;
        }
        do {
            bytes = h * size;
            i = bytes + array;
            do {
                j = i - bytes;
                if (compar(thunk, j, i) > 0) {
                    k = i;
                    do {
                        p1  = j;
                        p2  = k;
                        end = p2 + size;
                        do {
                            swap  = *p1;
                            *p1++ = *p2;
                            *p2++ = swap;
                        } while (p2 != end);
                        if (bytes + array > j) {
                            break;
                        }
                        k = j;
                        j -= bytes;
                    } while (compar(thunk, j, k) > 0);
                }
                i += size;
            } while (i != after);
            t /= 2;
            h = t * t - t * 3 / 2 + 1;
        } while (t != 0);
    }
}

-- 
pete