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