• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
14 template <typename ELEM, typename KEY>
GrTBSearch(const ELEM array[],int count,KEY target)15 int GrTBSearch(const ELEM array[], int count, KEY target) {
16     SkASSERT(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