cde/lib/tt/mini_isam/isbsearch.c

   1 /*%%  (c) Copyright 1993, 1994 Hewlett-Packard Company                   */
   2 /*%%  (c) Copyright 1993, 1994 International Business Machines Corp.     */
   3 /*%%  (c) Copyright 1993, 1994 Sun Microsystems, Inc.                    */
   4 /*%%  (c) Copyright 1993, 1994 Novell, Inc.                              */
   5 /*%%  $XConsortium: isbsearch.c /main/3 1995/10/23 11:35:44 rswiston $                                                   */
   6 #ifndef lint
   7 static char sccsid[] = "@(#)isbsearch.c 1.3 89/07/17 Copyr 1988 Sun Micro";
   8 #endif
   9
  10 /*
  11  * Copyright (c) 1988 by Sun Microsystems, Inc.
  12  */
  13
  14 /*
  15  * isbsearch.c
  16  *
  17  * Description:
  18  *      Binary search function.
  19  *      If differs from bsearch(3) in that if an exact match is not found,
  20  *      the next lower key is returned. If key is lower than any key in table,
  21  *      NULL value is returned.
  22  *
  23  */
  24
  25
  26 char *_isbsearch (key,table,nelems,keylen,cmpf)
  27     char *key;
  28     char *table;
  29     int nelems;
  30     int keylen;
  31     int (*cmpf) ();
  32 {
  33     register int len,l1,result;              /* current length of array to search */
  34     register char *p,*low;
  35
  36     if (nelems <= 0) return (char *) 0;
  37
  38     /* Check if key is lower than any key in the table. */
  39     result = (*cmpf) (key,table);
  40     if (result < 0 ) return (char *) 0;      /* Key is lower */
  41     else if (result == 0) return table;      /* Exact match */
  42
  43     for (low = table,len = nelems; len > 0;) {
  44         l1 = len >> 1;
  45         p = low + keylen * l1;
  46         if ((result = (*cmpf) (key,p)) == 0)    /* Exact match found */
  47             return p;
  48
  49         if (result > 0 )        {                    /* Key is in higher half */
  50             len -= l1 + 1;
  51             low = p + keylen;
  52         }
  53         else   {                             /* Key is in lower half */
  54             len = l1 ;
  55         }
  56     }
  57
  58     /* No matching key found, return next lower key */
  59     return (result>0)?p:(p-keylen);
  60 }
  61
  62