bsearch.c revision 1.2.4.2
1 1.2.4.2 yamt /* 2 1.2.4.2 yamt * Copyright (c) 1990, 1993 3 1.2.4.2 yamt * The Regents of the University of California. All rights reserved. 4 1.2.4.2 yamt * 5 1.2.4.2 yamt * Redistribution and use in source and binary forms, with or without 6 1.2.4.2 yamt * modification, are permitted provided that the following conditions 7 1.2.4.2 yamt * are met: 8 1.2.4.2 yamt * 1. Redistributions of source code must retain the above copyright 9 1.2.4.2 yamt * notice, this list of conditions and the following disclaimer. 10 1.2.4.2 yamt * 2. Redistributions in binary form must reproduce the above copyright 11 1.2.4.2 yamt * notice, this list of conditions and the following disclaimer in the 12 1.2.4.2 yamt * documentation and/or other materials provided with the distribution. 13 1.2.4.2 yamt * 3. All advertising materials mentioning features or use of this software 14 1.2.4.2 yamt * must display the following acknowledgement: 15 1.2.4.2 yamt * This product includes software developed by the University of 16 1.2.4.2 yamt * California, Berkeley and its contributors. 17 1.2.4.2 yamt * 4. Neither the name of the University nor the names of its contributors 18 1.2.4.2 yamt * may be used to endorse or promote products derived from this software 19 1.2.4.2 yamt * without specific prior written permission. 20 1.2.4.2 yamt * 21 1.2.4.2 yamt * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 1.2.4.2 yamt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 1.2.4.2 yamt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 1.2.4.2 yamt * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 1.2.4.2 yamt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 1.2.4.2 yamt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 1.2.4.2 yamt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 1.2.4.2 yamt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 1.2.4.2 yamt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 1.2.4.2 yamt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 1.2.4.2 yamt * SUCH DAMAGE. 32 1.2.4.2 yamt */ 33 1.2.4.2 yamt 34 1.2.4.2 yamt #include "config.h" 35 1.2.4.2 yamt 36 1.2.4.2 yamt #if defined(LIBC_SCCS) && !defined(lint) 37 1.2.4.2 yamt static const char sccsid[] = "@(#)bsearch.c 8.1 (Berkeley) 6/4/93"; 38 1.2.4.2 yamt #endif /* LIBC_SCCS and not lint */ 39 1.2.4.2 yamt #else 40 1.2.4.2 yamt __RCSID("$NetBSD: bsearch.c,v 1.2.4.2 2014/05/22 15:50:33 yamt Exp $"); 41 1.2.4.2 yamt #endif 42 1.2.4.2 yamt 43 1.2.4.2 yamt #include <stddef.h> 44 1.2.4.2 yamt #include <stdlib.h> 45 1.2.4.2 yamt 46 1.2.4.2 yamt #include "port.h" 47 1.2.4.2 yamt 48 1.2.4.2 yamt /* 49 1.2.4.2 yamt * Perform a binary search. 50 1.2.4.2 yamt * 51 1.2.4.2 yamt * The code below is a bit sneaky. After a comparison fails, we 52 1.2.4.2 yamt * divide the work in half by moving either left or right. If lim 53 1.2.4.2 yamt * is odd, moving left simply involves halving lim: e.g., when lim 54 1.2.4.2 yamt * is 5 we look at item 2, so we change lim to 2 so that we will 55 1.2.4.2 yamt * look at items 0 & 1. If lim is even, the same applies. If lim 56 1.2.4.2 yamt * is odd, moving right again involes halving lim, this time moving 57 1.2.4.2 yamt * the base up one item past p: e.g., when lim is 5 we change base 58 1.2.4.2 yamt * to item 3 and make lim 2 so that we will look at items 3 and 4. 59 1.2.4.2 yamt * If lim is even, however, we have to shrink it by one before 60 1.2.4.2 yamt * halving: e.g., when lim is 4, we still looked at item 2, so we 61 1.2.4.2 yamt * have to make lim 3, then halve, obtaining 1, so that we will only 62 1.2.4.2 yamt * look at item 3. 63 1.2.4.2 yamt * 64 1.2.4.2 yamt * PUBLIC: #ifndef HAVE_BSEARCH 65 1.2.4.2 yamt * PUBLIC: void *bsearch __P((const void *, const void *, size_t, 66 1.2.4.2 yamt * PUBLIC: size_t, int (*)(const void *, const void *))); 67 1.2.4.2 yamt * PUBLIC: #endif 68 1.2.4.2 yamt */ 69 1.2.4.2 yamt void * 70 1.2.4.2 yamt bsearch(register const void *key, const void *base0, size_t nmemb, register size_t size, register int (*compar) (const void *, const void *)) 71 1.2.4.2 yamt { 72 1.2.4.2 yamt register const char *base = base0; 73 1.2.4.2 yamt register size_t lim; 74 1.2.4.2 yamt register int cmp; 75 1.2.4.2 yamt register const void *p; 76 1.2.4.2 yamt 77 1.2.4.2 yamt for (lim = nmemb; lim != 0; lim >>= 1) { 78 1.2.4.2 yamt p = base + (lim >> 1) * size; 79 1.2.4.2 yamt cmp = (*compar)(key, p); 80 1.2.4.2 yamt if (cmp == 0) 81 1.2.4.2 yamt return ((void *)p); 82 1.2.4.2 yamt if (cmp > 0) { /* key > p: move right */ 83 1.2.4.2 yamt base = (char *)p + size; 84 1.2.4.2 yamt lim--; 85 1.2.4.2 yamt } /* else move left */ 86 1.2.4.2 yamt } 87 1.2.4.2 yamt return (NULL); 88 1.2.4.2 yamt } 89
Indexes created Wed Aug 05 00:25:39 UTC 2026