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>
GrTBSearch(const ELEM array[],int count,KEY target)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
45