1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkTSearch_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkTSearch_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTypes.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 158790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com/** 168790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * All of the SkTSearch variants want to return the index (0...N-1) of the 178790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * found element, or the bit-not of where to insert the element. 188790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * 198790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * At a simple level, if the return value is negative, it was not found. 208790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * 218790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * For clients that want to insert the new element if it was not found, use 228790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * the following logic: 238790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * 248790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * int index = SkTSearch(...); 258790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * if (index >= 0) { 268790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * // found at index 278790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * } else { 288790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * index = ~index; // now we are positive 298790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * // insert at index 308790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com * } 318790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com */ 328790fc635e5a9f24d1fa6291449efe436324fefdreed@google.com 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is 3520f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// used to perform comparisons. It has two function operators: 3620f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// bool operator() (const T& t, const K& k) 3720f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// bool operator() (const K& t, const T& k) 3820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T, typename K, typename LESS> 3920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comint SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less) 4044f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com{ 4144f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com SkASSERT(count >= 0); 4244f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com if (count <= 0) { 4344f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com return ~0; 4444f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com } 4544f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 4644f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com SkASSERT(base != NULL); // base may be NULL if count is zero 4744f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 4844f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com int lo = 0; 4944f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com int hi = count - 1; 5044f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 5144f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com while (lo < hi) { 5244f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com int mid = (hi + lo) >> 1; 5344f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com const T* elem = (const T*)((const char*)base + mid * elemSize); 5444f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 5520f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com if (less(*elem, key)) 5644f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com lo = mid + 1; 5744f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com else 5844f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com hi = mid; 5944f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com } 6044f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 6144f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com const T* elem = (const T*)((const char*)base + hi * elemSize); 6220f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com if (less(*elem, key)) { 6320f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com hi += 1; 6444f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com hi = ~hi; 6520f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com } else if (less(key, *elem)) { 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com hi = ~hi; 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return hi; 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7120f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// Adapts a less-than function to a functor. 7220f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor { 7320f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com bool operator()(const T& a, const T& b) { return LESS(a, b); } 7420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com}; 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7620f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// Specialization for case when T==K and the caller wants to use a function rather than functor. 7720f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> 7820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comint SkTSearch(const T base[], int count, const T& target, size_t elemSize) { 7920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com static SkTLessFunctionToFunctorAdaptor<T, LESS> functor; 8020f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return SkTSearch(base, count, target, elemSize, functor); 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8320f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// Adapts operator < to a functor. 8420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T> struct SkTLessFunctor { 8520f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com bool operator()(const T& a, const T& b) { return a < b; } 8620f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com}; 8744f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 8820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// Specialization for T==K, compare using op <. 8920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T> 9020f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comint SkTSearch(const T base[], int count, const T& target, size_t elemSize) { 9120f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com static SkTLessFunctor<T> functor; 9220f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return SkTSearch(base, count, target, elemSize, functor); 9320f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com} 9444f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com 9520f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T. 9620f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor { 9720f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com bool operator() (const T* t, const T* k) { return LESS(*t, *k); } 9820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com}; 9920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com 10020f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// Specialization for case where domain is an array of T* and the key value is a T*, and you want 10120f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com// to compare the T objects, not the pointers. 10220f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> 10320f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.comint SkTSearch(T* base[], int count, T* target, size_t elemSize) { 10420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor; 10520f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return SkTSearch(base, count, target, elemSize, functor); 10644f7c4a6f871f94e119783e91978b7a1430fb407bsalomon@google.com} 10720f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t target_len, size_t elemSize); 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t elemSize); 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base points to a table of lower-case strings. 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t target_len, size_t elemSize); 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t elemSize); 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Helper class to convert a string to lower-case, but only modifying the ascii 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com characters. This makes the routine very fast and never changes the string 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com length, but it is not suitable for linguistic purposes. Normally this is 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com used for buiding and searching string tables. 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comclass SkAutoAsciiToLC { 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ~SkAutoAsciiToLC(); 130fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const char* lc() const { return fLC; } 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t length() const { return fLength; } 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fLC; // points to either the heap or fStorage 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t fLength; 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com STORAGE = 64 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char fStorage[STORAGE+1]; 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 143c7a67cb57e43f8e140c7bd21318b5ad3e2db6b2freed@google.com// Helper when calling qsort with a compare proc that has typed its arguments 144c7a67cb57e43f8e140c7bd21318b5ad3e2db6b2freed@google.com#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare) 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 147