macro and text revision (-mdoc version 3)

[unix-history] / usr / src / lib / libc / stdlib / bsearch.c

diff --git a/usr/src/lib/libc/stdlib/bsearch.c b/usr/src/lib/libc/stdlib/bsearch.c
index 2354bce..af8b0dc 100644 (file)
--- a/usr/src/lib/libc/stdlib/bsearch.c
+++ b/usr/src/lib/libc/stdlib/bsearch.c
@@ -1,46 +1,54 @@
 /*
 /*

- * Copyright (c) 1989 The Regents of the University of California.
+ * Copyright (c) 1990 Regents of the University of California.

  * All rights reserved.
  *
  * All rights reserved.
  *

- * Redistribution and use in source and binary forms are permitted
- * provided that the above copyright notice and this paragraph are
- * duplicated in all such forms and that any documentation,
- * advertising materials, and other materials related to such
- * distribution and use acknowledge that the software was developed
- * by the University of California, Berkeley.  The name of the
- * University may not be used to endorse or promote products derived
- * from this software without specific prior written permission.
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ * %sccs.include.redist.c%

  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)

-static char sccsid[] = "@(#)bsearch.c  5.1 (Berkeley) %G%";
+static char sccsid[] = "@(#)bsearch.c  5.4 (Berkeley) %G%";

 #endif /* LIBC_SCCS and not lint */
 
 #endif /* LIBC_SCCS and not lint */
 

-#include <sys/types.h>
-#include <stdio.h>
+#include <stddef.h>            /* size_t */
+#include <stdlib.h>

 
 

-char *
-bsearch(key, base, nmemb, size, compar)
-       register char *key, *base;
+/*
+ * Perform a binary search.
+ *
+ * The code below is a bit sneaky.  After a comparison fails, we
+ * divide the work in half by moving either left or right. If lim
+ * is odd, moving left simply involves halving lim: e.g., when lim
+ * is 5 we look at item 2, so we change lim to 2 so that we will
+ * look at items 0 & 1.  If lim is even, the same applies.  If lim
+ * is odd, moving right again involes halving lim, this time moving
+ * the base up one item past p: e.g., when lim is 5 we change base
+ * to item 3 and make lim 2 so that we will look at items 3 and 4.
+ * If lim is even, however, we have to shrink it by one before
+ * halving: e.g., when lim is 4, we still looked at item 2, so we
+ * have to make lim 3, then halve, obtaining 1, so that we will only
+ * look at item 3.
+ */
+void *
+bsearch(key, base0, nmemb, size, compar)
+       register const void *key;
+       const void *base0;

        size_t nmemb;
        register size_t size;
        size_t nmemb;
        register size_t size;

-       register int (*compar)();
+       register int (*compar) __P((const void *, const void *));

 {
 {

-       register int bottom, middle, result, top;
-       register char *p;
+       register const char *base = base0;
+       register int lim, cmp;
+       register const void *p;

 
 

-       for (bottom = 0, top = nmemb - 1; bottom <= top;) {
-               middle = (bottom + top) >> 1;
-               p = base + middle * size;
-               if (!(result = (*compar)(key, p)))
-                       return(p);
-               if (result > 0)
-                       bottom = middle + 1;
-               else
-                       top = middle - 1;
+       for (lim = nmemb; lim != 0; lim >>= 1) {
+               p = base + (lim >> 1) * size;
+               cmp = (*compar)(key, p);
+               if (cmp == 0)
+                       return ((void *)p);
+               if (cmp > 0) {  /* key > p: move right */
+                       base = (char *)p + size;
+                       lim--;
+               } /* else move left */

        }
        }

-       return(NULL);
+       return (NULL);

 }
 }