git.sur5r.net Git - cc65/blob - libsrc/common/bsearch.c

   1 /*
   2  * bsearch.c
   3  *
   4  * Ullrich von Bassewitz, 17.06.1998
   5  */
   6
   7
   8
   9 #include <stdlib.h>
  10
  11
  12
  13 void* __fastcall__ bsearch (const void* key, const void* base, size_t n,
  14                             size_t size, int (*cmp) (const void*, const void*))
  15 {
  16     int current;
  17     int result;
  18     int found = 0;
  19     int first = 0;
  20     int last = n - 1;
  21
  22     /* Binary search */
  23     while (first <= last) {
  24
  25         /* Set current to mid of range */
  26         current = (last + first) / 2;
  27
  28         /* Do a compare */
  29         result = cmp ((void*) (((int) base) + current*size), key);
  30         if (result < 0) {
  31             first = current + 1;
  32         } else {
  33             last = current - 1;
  34             if (result == 0) {
  35                 /* Found one entry that matches the search key. However there may be
  36                  * more than one entry with the same key value and ANSI guarantees
  37                  * that we return the first of a row of items with the same key.
  38                  */
  39                 found = 1;
  40             }
  41         }
  42     }
  43
  44     /* Did we find the entry? */
  45     return (void*) (found? ((int) base) + first*size : 0);
  46 }
  47
  48
  49