15bb6825f10d64834ad1d1d967f590aebae285360epoger@google.com 2f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com/* 35bb6825f10d64834ad1d1d967f590aebae285360epoger@google.com * Copyright 2006 The Android Open Source Project 4f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com * 55bb6825f10d64834ad1d1d967f590aebae285360epoger@google.com * Use of this source code is governed by a BSD-style license that can be 65bb6825f10d64834ad1d1d967f590aebae285360epoger@google.com * found in the LICENSE file. 7f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com */ 8f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 95bb6825f10d64834ad1d1d967f590aebae285360epoger@google.com 10f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com#ifndef SkTSearch_DEFINED 11f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com#define SkTSearch_DEFINED 12f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 13f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com#include "SkTypes.h" 14f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 1591cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com/** 1691cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * All of the SkTSearch variants want to return the index (0...N-1) of the 1791cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * found element, or the bit-not of where to insert the element. 1891cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * 1991cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * At a simple level, if the return value is negative, it was not found. 2091cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * 2191cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * For clients that want to insert the new element if it was not found, use 2291cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * the following logic: 2391cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * 2491cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * int index = SkTSearch(...); 2591cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * if (index >= 0) { 2691cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * // found at index 2791cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * } else { 2891cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * index = ~index; // now we are positive 2991cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * // insert at index 3091cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com * } 3191cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com */ 3291cae6d131c91e87965ac8432b5d4a8ec71ffaedreed@google.com 33f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 34e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is 35e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// used to perform comparisons. It has two function operators: 36e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// bool operator() (const T& t, const K& k) 37e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// bool operator() (const K& t, const T& k) 38e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T, typename K, typename LESS> 39e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comint SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less) 402068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com{ 412068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com SkASSERT(count >= 0); 422068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com if (count <= 0) { 432068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com return ~0; 442068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com } 452068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 462068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com SkASSERT(base != NULL); // base may be NULL if count is zero 472068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 482068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com int lo = 0; 492068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com int hi = count - 1; 502068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 512068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com while (lo < hi) { 522068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com int mid = (hi + lo) >> 1; 532068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com const T* elem = (const T*)((const char*)base + mid * elemSize); 542068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 55e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com if (less(*elem, key)) 562068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com lo = mid + 1; 572068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com else 582068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com hi = mid; 592068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com } 602068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 612068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com const T* elem = (const T*)((const char*)base + hi * elemSize); 62e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com if (less(*elem, key)) { 63e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com hi += 1; 642068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com hi = ~hi; 65e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com } else if (less(key, *elem)) { 66f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com hi = ~hi; 67f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com } 68f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com return hi; 69f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com} 70f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 71e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// Adapts a less-than function to a functor. 72e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor { 73e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com bool operator()(const T& a, const T& b) { return LESS(a, b); } 74e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com}; 75f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 76e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// Specialization for case when T==K and the caller wants to use a function rather than functor. 77e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> 78e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comint SkTSearch(const T base[], int count, const T& target, size_t elemSize) { 79e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com static SkTLessFunctionToFunctorAdaptor<T, LESS> functor; 80e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com return SkTSearch(base, count, target, elemSize, functor); 81f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com} 82f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 83e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// Adapts operator < to a functor. 84e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T> struct SkTLessFunctor { 85e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com bool operator()(const T& a, const T& b) { return a < b; } 86e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com}; 872068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 88e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// Specialization for T==K, compare using op <. 89e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T> 90e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comint SkTSearch(const T base[], int count, const T& target, size_t elemSize) { 91e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com static SkTLessFunctor<T> functor; 92e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com return SkTSearch(base, count, target, elemSize, functor); 93e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com} 942068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com 95e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T. 96e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor { 97e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com bool operator() (const T* t, const T* k) { return LESS(*t, *k); } 98e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com}; 99e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com 100e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// Specialization for case where domain is an array of T* and the key value is a T*, and you want 101e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com// to compare the T objects, not the pointers. 102e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comtemplate <typename T, bool (LESS)(const T&, const T&)> 103e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.comint SkTSearch(T* base[], int count, T* target, size_t elemSize) { 104e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor; 105e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com return SkTSearch(base, count, target, elemSize, functor); 1062068eadae4be312c7d7c2b8492700091761d0185bsalomon@google.com} 107e3c3763e12e4e9163cc58c97343a6159d3fb1f90bsalomon@google.com 108f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 109f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com size_t target_len, size_t elemSize); 110f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 111f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com size_t elemSize); 112f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 113f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that 114f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com base points to a table of lower-case strings. 115f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com*/ 116f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 117f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com size_t target_len, size_t elemSize); 118f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 119f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com size_t elemSize); 120f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 121f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com/** Helper class to convert a string to lower-case, but only modifying the ascii 122f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com characters. This makes the routine very fast and never changes the string 123f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com length, but it is not suitable for linguistic purposes. Normally this is 124f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com used for buiding and searching string tables. 125f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com*/ 126f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.comclass SkAutoAsciiToLC { 127f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.compublic: 128f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); 129f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com ~SkAutoAsciiToLC(); 1301fde19f3b72345b473a1a9bd64729237a388813frmistry@google.com 131f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com const char* lc() const { return fLC; } 132f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com size_t length() const { return fLength; } 133f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 134f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.comprivate: 135f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com char* fLC; // points to either the heap or fStorage 136f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com size_t fLength; 137f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com enum { 138f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com STORAGE = 64 139f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com }; 140f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com char fStorage[STORAGE+1]; 141f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com}; 142f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 1439b7de68cda0dab0a0afebeef381923371316fe45reed@google.com// Helper when calling qsort with a compare proc that has typed its arguments 1449b7de68cda0dab0a0afebeef381923371316fe45reed@google.com#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare) 145f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com 146f0d6bf5df07d5ce620678074da0c05aacc28e44reed@android.com#endif 147