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