home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / misc / emu / AROSdev.lha / AROS / compiler / clib / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-09  |  2.1 KB  |  99 lines
  1. /*
  2.     (C) 1995-96 AROS - The Amiga Replacement OS
  3.     $Id: bsearch.c,v 1.1 1996/12/12 16:07:05 aros Exp $
  4.  
  5.     Desc: ANSI C function bsearch()
  6.     Lang: english
  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.     HISTORY
  55.  
  56. ******************************************************************************/
  57. {
  58.     char * base2 = (char *)base;
  59.     size_t a     = 0;
  60.     size_t b     = count;
  61.     size_t c;
  62.     int    d;
  63.  
  64.     /* Any elements to search ? */
  65.     if (count != 0)
  66.     {
  67.     for (;;)
  68.     {
  69.         /* Find the middle element between a and b */
  70.         c = (a + b) / 2;
  71.  
  72.         /* Look if key is equal to this element */
  73.         if ((d = (*comparefunction)(key, &base2[size * c])) == 0)
  74.         return &base2[size * c];
  75.  
  76.         /*
  77.         If the middle element equals the lower seach bounds, then
  78.         there are no more elements in the array which could be
  79.         searched (c wouldn't change anymore).
  80.         */
  81.         if (c == a)
  82.         break;
  83.  
  84.         /*
  85.         The middle element is not equal to the key. Is it smaller
  86.         or larger than the key ? If it's smaller, then c is our
  87.         new lower bounds, otherwise c is our new upper bounds.
  88.         */
  89.         if (d < 0)
  90.         b = c;
  91.         else
  92.         a = c;
  93.     }
  94.     }
  95.  
  96.     /* Nothing found */
  97.     return NULL;
  98. } /* bsearch */
  99.