1
2/*
3 * Copyright 2010 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10
11#ifndef GrTBSearch_DEFINED
12#define GrTBSearch_DEFINED
13
14template <typename ELEM, typename KEY>
15int GrTBSearch(const ELEM array[], int count, KEY target) {
16    GrAssert(count >= 0);
17    if (0 == count) {
18        // we should insert it at 0
19        return ~0;
20    }
21
22    int high = count - 1;
23    int low = 0;
24    while (high > low) {
25        int index = (low + high) >> 1;
26        if (LT(array[index], target)) {
27            low = index + 1;
28        } else {
29            high = index;
30        }
31    }
32
33    // check if we found it
34    if (EQ(array[high], target)) {
35        return high;
36    }
37
38    // now return the ~ of where we should insert it
39    if (LT(array[high], target)) {
40        high += 1;
41    }
42    return ~high;
43}
44
45#endif
46
47