compiler/clib/bsearch.c

   1 /*
   2     Copyright © 1995-2012, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     C99 function bsearch().
   6 */
   7
   8 /*****************************************************************************
   9
  10     NAME */
  11 #include <stdlib.h>
  12
  13         void * bsearch (
  14
  15
  16 /*  SYNOPSIS */
  17         const void * key,
  18         const void * base,
  19         size_t       count,
  20         size_t       size,
  21         int       (* comparefunction)(const void *, const void *))
  22
  23 /*  FUNCTION
  24         Search in a sorted array for an entry key.
  25
  26     INPUTS
  27         key - Look for this key.
  28         base - This is the address of the first element in the array
  29                 to be searched. Note that the array *must* be sorted.
  30         count - The number of elements in the array
  31         size - The size of one element
  32         comparefunction - The function which is called when two elements
  33                 must be compared. The function gets the addresses of two
  34                 elements of the array and must return 0 is both are equal,
  35                 < 0 if the first element is less than the second and > 0
  36                 otherwise.
  37
  38     RESULT
  39         A pointer to the element which equals key in the array or NULL if
  40         no such element could be found.
  41
  42     NOTES
  43
  44     EXAMPLE
  45
  46     BUGS
  47
  48     SEE ALSO
  49
  50     INTERNALS
  51
  52 ******************************************************************************/
  53 {
  54     char * base2 = (char *)base;
  55     size_t a     = 0;
  56     size_t b     = count;
  57     size_t c;
  58     int    d;
  59
  60     /* Any elements to search ? */
  61     if (count != 0)
  62     {
  63         for (;;)
  64         {
  65             /* Find the middle element between a and b */
  66             c = (a + b) / 2;
  67
  68             /* Look if key is equal to this element */
  69             if ((d = (*comparefunction)(key, &base2[size * c])) == 0)
  70                 return &base2[size * c];
  71
  72             /*
  73                 If the middle element equals the lower seach bounds, then
  74                 there are no more elements in the array which could be
  75                 searched (c wouldn't change anymore).
  76             */
  77             if (c == a)
  78                 break;
  79
  80             /*
  81                 The middle element is not equal to the key. Is it smaller
  82                 or larger than the key ? If it's smaller, then c is our
  83                 new lower bounds, otherwise c is our new upper bounds.
  84             */
  85             if (d < 0)
  86                 b = c;
  87             else
  88                 a = c;
  89         }
  90     }
  91
  92     /* Nothing found */
  93     return NULL;
  94 } /* bsearch */