1// Copyright 2016 The Fuchsia Authors
2// Copyright (c) 2014, Google Inc.
3//
4// Use of this source code is governed by a MIT-style
5// license that can be found in the LICENSE file or at
6// https://opensource.org/licenses/MIT
7
8
9#include <stdlib.h>
10
11void *bsearch(const void *key, const void *base, size_t num_elems, size_t size,
12              int (*compare)(const void *, const void *))
13{
14    size_t low = 0, high = num_elems - 1;
15
16    if (num_elems == 0) {
17        return NULL;
18    }
19
20    for (;;) {
21        size_t mid = low + ((high - low) / 2);
22        const void *mid_elem = ((unsigned char *) base) + mid*size;
23        int r = compare(key, mid_elem);
24
25        if (r < 0) {
26            if (mid == 0) {
27                return NULL;
28            }
29            high = mid - 1;
30        } else if (r > 0) {
31            low = mid + 1;
32            if (low < mid || low > high) {
33                return NULL;
34            }
35        } else {
36            return (void *) mid_elem;
37        }
38    }
39}
40