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