lib/libmytinfo/bsearch.c

   1 /*
   2  * bsearch.c
   3  *
   4  * This is something I found on watmath. I've made some minor changes for use
   5  * in this package.
   6  *
   7  * 92/06/04 11:35:15
   8  */
   9
  10 #if 0
  11 #ifndef lint
  12 static char *RCSid = "$OHeader: /usr/mfcf/src/accounts/libuw/RCS/bsearch.c,v 1.1 88/06/11 20:41:48 root Exp $";
  13 #endif
  14 #endif
  15
  16 #include "defs.h"
  17
  18 #ifdef USE_MYBSEARCH
  19
  20 #ifdef USE_SCCS_IDS
  21 static char const SCCSid[] = "@(#) mytinfo bsearch.c 3.4 92/06/04 public domain, By Ross Ridge";
  22 #endif
  23
  24 #ifdef USE_SHORT_BSEARCH
  25 #define fast_int short
  26 #else
  27 #define fast_int mysize_t
  28 #endif
  29
  30 /*
  31  * bsearch - find an element of a sorted vector
  32  *
  33  *      found = bsearch(key, array, dimension, width, compare)
  34  *              returns a pointer to the specified element in the array,
  35  *              or (char*)0 if the element can't be found.
  36  *      key
  37  *              pointer to the element to be searched for in the array
  38  *      array
  39  *              address of an array of elements
  40  *      dimension
  41  *              number of elements in the array
  42  *      width
  43  *              sizeof(type) of each element
  44  *      compare
  45  *              pointer to a function taking (char *) pointers to two elements
  46  *              and returning <0, 0, or >0 as the first element comes before,
  47  *              at, or after the second element.  A compare function is provided
  48  *              for comparing strings.
  49 */
  50 #if 0
  51 /*
  52  * $OLog:       bsearch.c,v $
  53  * Revision 1.1  88/06/11  20:41:48  root
  54  * Initial revision
  55  *
  56 */
  57 #endif
  58
  59         static anyptr
  60 bsearch(key, array, dimension, iwidth, compare)
  61         anyptr key;
  62         anyptr array;
  63         int dimension;
  64         mysize_t iwidth;
  65         compar_fn compare;
  66 {
  67         register fast_int start;   /* offset to start of current interval */
  68         register fast_int end;     /* offset to end+1 of current interval */
  69         register fast_int middle;  /* offset to middle of current interval */
  70         auto int status;
  71         register fast_int width;
  72
  73         width = iwidth / sizeof(char);
  74
  75         start = 0;
  76         middle = 0;
  77         end = dimension;
  78
  79         while (start < end) {
  80
  81                 middle = (start + end) / 2;
  82
  83                 status = (*compare)(key, ((char *)array + middle*width));
  84
  85                 if (status < 0)
  86                         end = middle;
  87
  88                 else if (status > 0)
  89                         start = middle + 1;
  90
  91                 else return (anyptr)(((char *)array) + middle*width);
  92         }
  93
  94         return  0;
  95 }
  96
  97 #endif /* USE_MYBSEARCH */