bsearch.c (348238dbd42306d9fb5d89ab393b840572cfeb0f) bsearch.c (4a8dea8cf97aab33f4e6a11afcc64dd9562f3bfd)
1/*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 39 unchanged lines hidden (view full) ---

48 * the base up one item past p: e.g., when lim is 5 we change base
49 * to item 3 and make lim 2 so that we will look at items 3 and 4.
50 * If lim is even, however, we have to shrink it by one before
51 * halving: e.g., when lim is 4, we still looked at item 2, so we
52 * have to make lim 3, then halve, obtaining 1, so that we will only
53 * look at item 3.
54 */
55void *
1/*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 39 unchanged lines hidden (view full) ---

48 * the base up one item past p: e.g., when lim is 5 we change base
49 * to item 3 and make lim 2 so that we will look at items 3 and 4.
50 * If lim is even, however, we have to shrink it by one before
51 * halving: e.g., when lim is 4, we still looked at item 2, so we
52 * have to make lim 3, then halve, obtaining 1, so that we will only
53 * look at item 3.
54 */
55void *
56bsearch(key, base0, nmemb, size, compar)
57 const void *key;
58 const void *base0;
59 size_t nmemb;
60 size_t size;
61 int (*compar)(const void *, const void *);
56bsearch(const void *key, const void *base0, size_t nmemb, size_t size,
57 int (*compar)(const void *, const void *))
62{
63 const char *base = base0;
64 size_t lim;
65 int cmp;
66 const void *p;
67
68 for (lim = nmemb; lim != 0; lim >>= 1) {
69 p = base + (lim >> 1) * size;
70 cmp = (*compar)(key, p);
71 if (cmp == 0)
72 return ((void *)(uintptr_t)p);
73 if (cmp > 0) { /* key > p: move right */
74 base = (const char *)p + size;
75 lim--;
76 } /* else move left */
77 }
78 return (NULL);
79}
58{
59 const char *base = base0;
60 size_t lim;
61 int cmp;
62 const void *p;
63
64 for (lim = nmemb; lim != 0; lim >>= 1) {
65 p = base + (lim >> 1) * size;
66 cmp = (*compar)(key, p);
67 if (cmp == 0)
68 return ((void *)(uintptr_t)p);
69 if (cmp > 0) { /* key > p: move right */
70 base = (const char *)p + size;
71 lim--;
72 } /* else move left */
73 }
74 return (NULL);
75}