| 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 |