aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/gpu/GrTBSearch.h
blob: 2697f3733b2aa6fdb195fdc4ded37b66224788e9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
 * Copyright 2010 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */



#ifndef GrTBSearch_DEFINED
#define GrTBSearch_DEFINED

template <typename ELEM, typename KEY>
int GrTBSearch(const ELEM array[], int count, KEY target) {
    GrAssert(count >= 0);
    if (0 == count) {
        // we should insert it at 0
        return ~0;
    }
    
    int high = count - 1;
    int low = 0;
    while (high > low) {
        int index = (low + high) >> 1;
        if (LT(array[index], target)) {
            low = index + 1;
        } else {
            high = index;
        }
    }
    
    // check if we found it
    if (EQ(array[high], target)) {
        return high;
    }
    
    // now return the ~ of where we should insert it
    if (LT(array[high], target)) {
        high += 1;
    }
    return ~high;
}

#endif