Path: csiph.com!x330-a1.tempe.blueboxinc.net!aioe.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: Tue, 10 May 2011 03:42:54 -0500
Message-ID: <4DC8FA8D.7E98@mindspring.com>
Date: Tue, 10 May 2011 04:42:53 -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> <rubrum-B22B70.17115409052011@news.albasani.net> <92reltF51pU8@mid.individual.net> <4DC8EEED.139F@mindspring.com> <92salqFggcU1@mid.individual.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 126
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.220.173
X-Trace: sv3-HpiguLtzPXssLH0jFiG+9WCUSfMmdhkZNyVH70p0dZrNcuKnoOfsSJbhyEzfXyJkoZHZJUxLs0w1Ttd!8Si4mRB3Xmfpd+YTOJlRBmpS2+Xgn42BqQMizV6tLrUG8V5zd8AcjQQot/0n1sB9/5pun2nGdGf3!0FoLYGSOg+4=
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: 4903
Xref: x330-a1.tempe.blueboxinc.net comp.unix.programmer:473 comp.lang.c:3673

Ian Collins wrote:
> 
> On 05/10/11 07:53 PM, pete wrote:
> > Ian Collins wrote:
> >>
> >> On 05/10/11 12:11 PM, Michael Press wrote:
> >>
> >>> Does the library return
> >>> a value in exactly the form I want?
> >>
> >> How many forms of true and false are there?
> >
> > bsearch either
> > returns NULL or
> > returns a pointer to an element of an array.
> >
> > It is also possible to want a binary search
> > which returns a pointer to the first occurance in the array
> > or to want a binary search
> > which returns a pointer to the last occurance in the array.
> 
> All of those are supplied by the C++ standard library (plus the option
> of returning the range of matching elements).

I can still write them in less time than it takes me to learn C++.

/* BEGIN lo_hisearch.c */

#include <stddef.h>

struct lo_hi {
    void *lo;
    void *hi;
};

struct lo_hi lo_hisearch(const void *key, const void *base,
               size_t nmemb, size_t size,
               int (*compar)(const void *, const void *));
void *losearch(const void *key, const void *base,
               size_t nmemb, size_t size,
               int (*compar)(const void *, const void *));
void *hisearch(const void *key, const void *base,
               size_t nmemb, size_t size,
               int (*compar)(const void *, const void *));

struct lo_hi 
lo_hisearch(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    struct lo_hi found;

    found.lo = losearch(key, base, nmemb, size, compar);
    found.hi = hisearch(key, base, nmemb, size, compar);
    return found;
}

void *
losearch(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    int comp;
    size_t low, middle, high;
    const void *found = NULL;

    if (nmemb != 0) {
        const char *const array = base;   
        
        low = 0;    
        high = nmemb;
        do {
            nmemb = high - low;
            middle = nmemb / 2 + low;
            base = middle * size + array;
            comp = compar(key, base);
            if (comp > 0) {
                low = middle;
            } else {
                high = middle;
                if (comp == 0) {
                    found = base;
                } 
            }
        } while (nmemb != 1);
    }
    return (void *)found;
}

void *
hisearch(const void *key, const void *base,
         size_t nmemb, size_t size,
         int (*compar)(const void *, const void *))
{
    int comp;
    size_t low, middle, high;
    const void *found = NULL;

    if (nmemb != 0) {
        const char *const array = base;   
        
        low = 0;    
        high = nmemb;
        do {
            nmemb = high - low;
            middle = nmemb / 2 + low;
            base = middle * size + array;
            comp = compar(key, base);
            if (0 > comp) {
                high = middle;
            } else {
                low = middle;
                if (comp == 0) {
                    found = base;
                } 
            }
        } while (nmemb != 1);
    }
    return (void *)found;
}

/* END lo_hisearch.c */


-- 
pete