bs_sindx.c

Go to the documentation of this file.

/*****************************************************************************\
*  bs_sindx                                                                   *
*******************************************************************************
*  Bs_sindx() performs a binary search on a sorted array of sindx structures. * 
*  The sorted array of num structures is pointed to by sdx. Bs_sindx() tries  *
*  to match id with a sdx.sid member in the array of sindx structures.   It   *
*  returns the index of the element in the sdx array whose sdx.sid member     *
*  matches id. If no match is found, NOT_USED is returned.                    *
*                                           Wayne Martin - CNRFC  09/21/94    *
\*****************************************************************************/
 
#include  <stdio.h>
 
#include  "database.h"
#include  "dbsearch.h"
 
#define   NO   0x00
#define  YES   0x01
 
unsigned long int bs_sindx(struct sindx *sdx, unsigned long int id,
            unsigned long int num) {
 
    unsigned char found;              /* Search flag; found = NO or YES          */
    unsigned long int  lower, upper;  /* Lower and upper bounds of current array */
    unsigned long int  i;             /* Current array position to be tested     */
    unsigned long int  match;         /* Return value                            */
 
    lower = 0x00000000;
    upper = num - 0x00000001;
    match = NOT_USED;
    found = NO;
 
    /* return NOT_USED immediately if no ID's in list to be searched */
    if(num < 1L)  {
        return(match);
    }
 
    while(found == NO)  {
 
        /* Find midpoint of remaining sdx array */
        i = (upper + lower) / 2L;
        
        /* Found sdx.sid match for id */
        if(sdx[i].sid == id)  {
            match = i;
            found = YES;
        }
        else  {
            /* Take upper half of sdx array */
            if(id > sdx[i].sid)  {
                lower = i + 1L;
            }
            /* Take lower half of sdx array */
            else  {
                upper = i - 1L;
            }
        }
        /* id not in sdx array */
        if(upper < lower)  {
            found = YES;
        }
        if(upper == NOT_USED)  {
            found = YES;
        }
    }
    return(match);
}