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 45
