home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-19  |  1.9 KB  |  82 lines
  1. /* 
  2.  * bsearch.c --
  3.  *
  4.  *    Source code for the bsearch library routine.
  5.  *
  6.  * Copyright 1989 Regents of the University of California
  7.  * Permission to use, copy, modify, and distribute this
  8.  * software and its documentation for any purpose and without
  9.  * fee is hereby granted, provided that the above copyright
  10.  * notice appear in all copies.  The University of California
  11.  * makes no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without
  13.  * express or implied warranty.
  14.  */
  15.  
  16. #ifndef lint
  17. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/bsearch.c,v 1.4 89/05/18 17:09:12 rab Exp $";
  18. #endif /* not lint */
  19.  
  20.  
  21. #include <stdlib.h>
  22.  
  23. #include <stdio.h>
  24. #include <sys/types.h>
  25.  
  26. #ifndef __STDC__
  27. #define const   /**/
  28. #endif
  29.  
  30.  
  31. /*
  32.  *----------------------------------------------------------------------
  33.  *
  34.  * bsearch --
  35.  *
  36.  *    Bsearch searches base[0] to base[n - 1] for an item that
  37.  *      matches *key.  The function cmp must return negative if its first
  38.  *      argument (the search key) is less that its second (a table entry),
  39.  *      zero if equal, and positive if greater.  Items in the array must
  40.  *      be in ascending order.  
  41.  *
  42.  * Results:
  43.  *    Returns a pointer to a matching item, or NULL if none exits.
  44.  *
  45.  * Side effects:
  46.  *    None.
  47.  *
  48.  *----------------------------------------------------------------------
  49.  */
  50.  
  51. char *
  52. bsearch(key, base, n, size, cmp)
  53.     const char *key;
  54.     const char *base;
  55.     size_t n;
  56.     size_t size;
  57. #ifdef __STDC__
  58.     int (*cmp)(const void *, const void *);
  59. #else
  60.     int (*cmp)();
  61. #endif
  62. {
  63.     const char *middle;
  64.     int c;
  65.  
  66.  
  67.     for (middle = base; n != 0;) {
  68.     middle += (n/2) * size;
  69.     if ((c = (*cmp)(key, middle)) > 0) {
  70.         n = (n/2) - ((n&1) == 0);
  71.         base = (middle += size);
  72.     } else if (c < 0) {
  73.         n /= 2;
  74.         middle = base;
  75.     } else {
  76.         return (char *) middle;
  77.     }
  78.     }
  79.     return NULL;
  80. }
  81.  
  82.