bsearch.c

   1 #include "libctiny.h"
   2 #include <windows.h>
   3
   4 /***
   5 *bsearch.c - do a binary search
   6 *
   7 *       Copyright (c) Microsoft Corporation. All rights reserved.
   8 *
   9 *Purpose:
  10 *       defines bsearch() - do a binary search an an array
  11 *
  12 *******************************************************************************/
  13
  14 // #include <cruntime.h>
  15 // #include <stdlib.h>
  16 // #include <search.h>
  17
  18 /***
  19 *char *bsearch() - do a binary search on an array
  20 *
  21 *Purpose:
  22 *       Does a binary search of a sorted array for a key.
  23 *
  24 *Entry:
  25 *       const char *key    - key to search for
  26 *       const char *base   - base of sorted array to search
  27 *       unsigned int num   - number of elements in array
  28 *       unsigned int width - number of bytes per element
  29 *       int (*compare)()   - pointer to function that compares two array
  30 *               elements, returning neg when #1 < #2, pos when #1 > #2, and
  31 *               0 when they are equal. Function is passed pointers to two
  32 *               array elements.
  33 *
  34 *Exit:
  35 *       if key is found:
  36 *               returns pointer to occurrence of key in array
  37 *       if key is not found:
  38 *               returns NULL
  39 *
  40 *Exceptions:
  41 *
  42 *******************************************************************************/
  43
  44 void * __cdecl bsearch (
  45         const void *key,
  46         const void *base,
  47         size_t num,
  48         size_t width,
  49         int (__cdecl *compare)(const void *, const void *)
  50         )
  51 {
  52         register char *lo = (char *)base;
  53         register char *hi = (char *)base + (num - 1) * width;
  54         register char *mid;
  55         size_t half;
  56         int result;
  57
  58         while (lo <= hi)
  59                 if (half = num / 2)
  60                 {
  61                         mid = lo + (num & 1 ? half : (half - 1)) * width;
  62                         if (!(result = (*compare)(key,mid)))
  63                                 return(mid);
  64                         else if (result < 0)
  65                         {
  66                                 hi = mid - width;
  67                                 num = num & 1 ? half : half-1;
  68                         }
  69                         else    {
  70                                 lo = mid + width;
  71                                 num = half;
  72                         }
  73                 }
  74                 else if (num)
  75                         return((*compare)(key,lo) ? NULL : lo);
  76                 else
  77                         break;
  78
  79         return(NULL);
  80 }