1 2 /* 3 * Copyright 2006 The Android Open Source Project 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 #ifndef SkTSearch_DEFINED 11 #define SkTSearch_DEFINED 12 13 #include "SkTypes.h" 14 15 template <typename T> 16 int SkTSearch(const T* base, int count, const T& target, size_t elemSize) 17 { 18 SkASSERT(count >= 0); 19 if (count <= 0) 20 return ~0; 21 22 SkASSERT(base != NULL); // base may be NULL if count is zero 23 24 int lo = 0; 25 int hi = count - 1; 26 27 while (lo < hi) 28 { 29 int mid = (hi + lo) >> 1; 30 const T* elem = (const T*)((const char*)base + mid * elemSize); 31 32 if (*elem < target) 33 lo = mid + 1; 34 else 35 hi = mid; 36 } 37 38 const T* elem = (const T*)((const char*)base + hi * elemSize); 39 if (*elem != target) 40 { 41 if (*elem < target) 42 hi += 1; 43 hi = ~hi; 44 } 45 return hi; 46 } 47 48 template <typename T> 49 int SkTSearch(const T* base, int count, const T& target, size_t elemSize, 50 int (*compare)(const T&, const T&)) 51 { 52 SkASSERT(count >= 0); 53 if (count <= 0) { 54 return ~0; 55 } 56 57 SkASSERT(base != NULL); // base may be NULL if count is zero 58 59 int lo = 0; 60 int hi = count - 1; 61 62 while (lo < hi) { 63 int mid = (hi + lo) >> 1; 64 const T* elem = (const T*)((const char*)base + mid * elemSize); 65 66 if ((*compare)(*elem, target) < 0) 67 lo = mid + 1; 68 else 69 hi = mid; 70 } 71 72 const T* elem = (const T*)((const char*)base + hi * elemSize); 73 int pred = (*compare)(*elem, target); 74 if (pred != 0) { 75 if (pred < 0) 76 hi += 1; 77 hi = ~hi; 78 } 79 return hi; 80 } 81 82 template <typename T> 83 int SkTSearch(const T** base, int count, const T* target, size_t elemSize, 84 int (*compare)(const T*, const T*)) 85 { 86 SkASSERT(count >= 0); 87 if (count <= 0) 88 return ~0; 89 90 SkASSERT(base != NULL); // base may be NULL if count is zero 91 92 int lo = 0; 93 int hi = count - 1; 94 95 while (lo < hi) 96 { 97 int mid = (hi + lo) >> 1; 98 const T* elem = *(const T**)((const char*)base + mid * elemSize); 99 100 if ((*compare)(elem, target) < 0) 101 lo = mid + 1; 102 else 103 hi = mid; 104 } 105 106 const T* elem = *(const T**)((const char*)base + hi * elemSize); 107 int pred = (*compare)(elem, target); 108 if (pred != 0) 109 { 110 if (pred < 0) 111 hi += 1; 112 hi = ~hi; 113 } 114 return hi; 115 } 116 117 int SkStrSearch(const char*const* base, int count, const char target[], 118 size_t target_len, size_t elemSize); 119 int SkStrSearch(const char*const* base, int count, const char target[], 120 size_t elemSize); 121 122 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that 123 base points to a table of lower-case strings. 124 */ 125 int SkStrLCSearch(const char*const* base, int count, const char target[], 126 size_t target_len, size_t elemSize); 127 int SkStrLCSearch(const char*const* base, int count, const char target[], 128 size_t elemSize); 129 130 /** Helper class to convert a string to lower-case, but only modifying the ascii 131 characters. This makes the routine very fast and never changes the string 132 length, but it is not suitable for linguistic purposes. Normally this is 133 used for buiding and searching string tables. 134 */ 135 class SkAutoAsciiToLC { 136 public: 137 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); 138 ~SkAutoAsciiToLC(); 139 140 const char* lc() const { return fLC; } 141 size_t length() const { return fLength; } 142 143 private: 144 char* fLC; // points to either the heap or fStorage 145 size_t fLength; 146 enum { 147 STORAGE = 64 148 }; 149 char fStorage[STORAGE+1]; 150 }; 151 152 extern "C" { 153 typedef int (*SkQSortCompareProc)(const void*, const void*); 154 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc); 155 } 156 157 #endif 158 159