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

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