compiler/clib/bsearch.c

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