Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!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: Wed, 11 May 2011 06:59:59 -0500
Message-ID: <4DCA7A40.3C76@mindspring.com>
Date: Wed, 11 May 2011 08:00:00 -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.unix.programmer,comp.lang.c
Subject: Re: Avoiding recursive stack overflow in C on Unix/Linux?
References: <iptr5l$tkb$1@speranza.aioe.org> <ce8a87e8-fffa-4287-84ee-271f0766c304@24g2000yqk.googlegroups.com> <e154ec52-5ee3-41de-ad60-37f604e594f6@b19g2000yqg.googlegroups.com> <iq8j7v$28f$1@speranza.aioe.org> <cdc2bce7-4168-4bad-92b7-fdaa78e556e9@b19g2000yqg.googlegroups.com> <rubrum-F1F569.15051809052011@news.albasani.net> <2f33e674-b127-4c35-89b5-dcbf564f3aab@h36g2000pro.googlegroups.com> <yw1x7h9zebob.fsf@unicorn.mansr.com> <92rabuF51pU6@mid.individual.net> <yw1x39kneagb.fsf@unicorn.mansr.com> <87zkmvhyqm.fsf@temporary-address.org.uk> <rubrum-624DB0.12245510052011@news.albasani.net> <87aaeui0ic.fsf@temporary-address.org.uk> <rubrum-EEAAFC.19360310052011@news.albasani.net> <4DCA00CF.3150@mindspring.com> <87sjslhiqa.fsf@temporary-address.org.uk>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 96
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.223.42
X-Trace: sv3-wVAtANcb5a8z1lJ6JwQoJws1R9nDQBlt8GVbqEx+qpBdOBgGdgl96iuZ6fm0RCC03TXs7gOzh6GUn4S!xW7+XeyvxaEC0ZultkeE/u06UecKsOYU3uU0100tCf6/H545skvBWuJDHMezVWT4YWA+0ccqYPZg!FRPGL+W6Pg==
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: 4422
Xref: x330-a1.tempe.blueboxinc.net comp.unix.programmer:524 comp.lang.c:3743

Dr Nick wrote:
> 
> pete <pfiland@mindspring.com> writes:
> 
> > Michael Press wrote:
> >
> >> I could dash off qsort. Its only advantage is speed.
> >> When I want an O(n.log n) search I write heapsort.
> >>
> >> By the way, qsort(3) has an irremediable security hole.
> >
> > I like to write sort functions with a qsort interface.
> >
> > http://www.mindspring.com/~pfilandr/C/q_sort/
> 
> There's a flaw in qsort that I make sure I don't put in my qsort-like
> functions: it needs to take another void pointer and pass it to the
> comparison function.

I don't understand what you mean.
qsort can pass any object type pointer 
to the comparison function.

In all of the sort functions that I've written
which are of the same function type as qsort,
a pointer to unsigned char, 
is the type that gets passed to the comparison function.

When I want to write a fast sort function,
I use what I refer to as "the e_type interface".

The user defines three macros,

something like:

#define E_TYPE          long unsigned e_type
#define MOV(A, B)       ((void)(*(A) = *(B)))
#define GT(A, B)        (*(A) > *(B))

or maybe even something like:

#define E_TYPE          char e_type[sizeof "seven"]
#include <string.h>
#define MOV(A, B)       ((void)memcpy((A), (B), sizeof *(A)))
#define GT(A, B)        (strlen(*(A)) > strlen(*(B)))

and then the form of the sort function will be something like this:

#include <stddef.h>

typedef E_TYPE;

void 
spsort(e_type *array, size_t nmemb)
{
    size_t h, t;
    e_type *i, *j, *k, *after, temp;
    
    if (nmemb > 1) {
        after = array + nmemb;
        nmemb /= 4;
        h = nmemb + 1;
        for (t = 1; nmemb != 0; nmemb /= 4) {
            t *= 2;
        }
        do {
            i = h + array;
            do {
                k = i - h;
                if (GT(k, i)) {
                    j = i;
                    MOV(&temp, j);
                    do {
                        MOV(j, k);
                        j  = k;
                        if (h + array > k) {
                            break;
                        }
                        k -= h;
                    } while (GT(k, &temp));
                    MOV(j, &temp);
                }
            } while (++i != after);
            t /= 2;
            h = t * t - t * 3 / 2 + 1;
        } while (t != 0);
    }
}

I have faster functions than that Shell sort one,
but most of them might be a little long to post.

http://www.mindspring.com/~pfilandr/C/e_driver/

-- 
pete