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 /** 16 * All of the SkTSearch variants want to return the index (0...N-1) of the 17 * found element, or the bit-not of where to insert the element. 18 * 19 * At a simple level, if the return value is negative, it was not found. 20 * 21 * For clients that want to insert the new element if it was not found, use 22 * the following logic: 23 * 24 * int index = SkTSearch(...); 25 * if (index >= 0) { 26 * // found at index 27 * } else { 28 * index = ~index; // now we are positive 29 * // insert at index 30 * } 31 */ 32 33 template <typename T> 34 int SkTSearch(const T* base, int count, const T& target, size_t elemSize) 35 { 36 SkASSERT(count >= 0); 37 if (count <= 0) 38 return ~0; 39 40 SkASSERT(base != NULL); // base may be NULL if count is zero 41 42 int lo = 0; 43 int hi = count - 1; 44 45 while (lo < hi) 46 { 47 int mid = (hi + lo) >> 1; 48 const T* elem = (const T*)((const char*)base + mid * elemSize); 49 50 if (*elem < target) 51 lo = mid + 1; 52 else 53 hi = mid; 54 } 55 56 const T* elem = (const T*)((const char*)base + hi * elemSize); 57 if (*elem != target) 58 { 59 if (*elem < target) 60 hi += 1; 61 hi = ~hi; 62 } 63 return hi; 64 } 65 66 template <typename T, int (COMPARE)(const T*, const T*)> 67 int SkTSearch(const T* base, int count, const T& target, size_t elemSize) 68 { 69 SkASSERT(count >= 0); 70 if (count <= 0) { 71 return ~0; 72 } 73 74 SkASSERT(base != NULL); // base may be NULL if count is zero 75 76 int lo = 0; 77 int hi = count - 1; 78 79 while (lo < hi) { 80 int mid = (hi + lo) >> 1; 81 const T* elem = (const T*)((const char*)base + mid * elemSize); 82 83 if (COMPARE(elem, &target) < 0) 84 lo = mid + 1; 85 else 86 hi = mid; 87 } 88 89 const T* elem = (const T*)((const char*)base + hi * elemSize); 90 int pred = COMPARE(elem, &target); 91 if (pred != 0) { 92 if (pred < 0) 93 hi += 1; 94 hi = ~hi; 95 } 96 return hi; 97 } 98 99 template <typename T> 100 int SkTSearch(const T* base, int count, const T& target, size_t elemSize, 101 int (*compare)(const T*, const T*)) 102 { 103 SkASSERT(count >= 0); 104 if (count <= 0) { 105 return ~0; 106 } 107 108 SkASSERT(base != NULL); // base may be NULL if count is zero 109 110 int lo = 0; 111 int hi = count - 1; 112 113 while (lo < hi) { 114 int mid = (hi + lo) >> 1; 115 const T* elem = (const T*)((const char*)base + mid * elemSize); 116 117 if ((*compare)(elem, &target) < 0) 118 lo = mid + 1; 119 else 120 hi = mid; 121 } 122 123 const T* elem = (const T*)((const char*)base + hi * elemSize); 124 int pred = (*compare)(elem, &target); 125 if (pred != 0) { 126 if (pred < 0) 127 hi += 1; 128 hi = ~hi; 129 } 130 return hi; 131 } 132 133 template <typename T> 134 int SkTSearch(const T** base, int count, const T* target, size_t elemSize, 135 int (*compare)(const T*, const T*)) 136 { 137 SkASSERT(count >= 0); 138 if (count <= 0) 139 return ~0; 140 141 SkASSERT(base != NULL); // base may be NULL if count is zero 142 143 int lo = 0; 144 int hi = count - 1; 145 146 while (lo < hi) 147 { 148 int mid = (hi + lo) >> 1; 149 const T* elem = *(const T**)((const char*)base + mid * elemSize); 150 151 if ((*compare)(elem, target) < 0) 152 lo = mid + 1; 153 else 154 hi = mid; 155 } 156 157 const T* elem = *(const T**)((const char*)base + hi * elemSize); 158 int pred = (*compare)(elem, target); 159 if (pred != 0) 160 { 161 if (pred < 0) 162 hi += 1; 163 hi = ~hi; 164 } 165 return hi; 166 } 167 168 template <typename T, int (COMPARE)(const T*, const T*)> 169 int SkTSearch(const T** base, int count, const T* target, size_t elemSize) 170 { 171 SkASSERT(count >= 0); 172 if (count <= 0) 173 return ~0; 174 175 SkASSERT(base != NULL); // base may be NULL if count is zero 176 177 int lo = 0; 178 int hi = count - 1; 179 180 while (lo < hi) 181 { 182 int mid = (hi + lo) >> 1; 183 const T* elem = *(const T**)((const char*)base + mid * elemSize); 184 185 if (COMPARE(elem, target) < 0) 186 lo = mid + 1; 187 else 188 hi = mid; 189 } 190 191 const T* elem = *(const T**)((const char*)base + hi * elemSize); 192 int pred = COMPARE(elem, target); 193 if (pred != 0) 194 { 195 if (pred < 0) 196 hi += 1; 197 hi = ~hi; 198 } 199 return hi; 200 } 201 int SkStrSearch(const char*const* base, int count, const char target[], 202 size_t target_len, size_t elemSize); 203 int SkStrSearch(const char*const* base, int count, const char target[], 204 size_t elemSize); 205 206 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that 207 base points to a table of lower-case strings. 208 */ 209 int SkStrLCSearch(const char*const* base, int count, const char target[], 210 size_t target_len, size_t elemSize); 211 int SkStrLCSearch(const char*const* base, int count, const char target[], 212 size_t elemSize); 213 214 /** Helper class to convert a string to lower-case, but only modifying the ascii 215 characters. This makes the routine very fast and never changes the string 216 length, but it is not suitable for linguistic purposes. Normally this is 217 used for buiding and searching string tables. 218 */ 219 class SkAutoAsciiToLC { 220 public: 221 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); 222 ~SkAutoAsciiToLC(); 223 224 const char* lc() const { return fLC; } 225 size_t length() const { return fLength; } 226 227 private: 228 char* fLC; // points to either the heap or fStorage 229 size_t fLength; 230 enum { 231 STORAGE = 64 232 }; 233 char fStorage[STORAGE+1]; 234 }; 235 236 // Helper when calling qsort with a compare proc that has typed its arguments 237 #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare) 238 239 #endif 240
