blob: 01e97440a65135ab4511a537fb2767e2db865cfb (
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
|
/*
* 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
#include "SkTypes.h"
template <typename ELEM, typename KEY>
int GrTBSearch(const ELEM array[], int count, KEY target) {
SkASSERT(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
|
