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