180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkTSearch_DEFINED 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkTSearch_DEFINED 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * All of the SkTSearch variants want to return the index (0...N-1) of the 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found element, or the bit-not of where to insert the element. 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * At a simple level, if the return value is negative, it was not found. 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * For clients that want to insert the new element if it was not found, use 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * the following logic: 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * int index = SkTSearch(...); 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * if (index >= 0) { 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * // found at index 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * } else { 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * index = ~index; // now we are positive 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * // insert at index 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * } 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is 357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// used to perform comparisons. It has two function operators: 367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// bool operator() (const T& t, const K& k) 377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// bool operator() (const K& t, const T& k) 387839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T, typename K, typename LESS> 397839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerint SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less) 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(count >= 0); 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count <= 0) { 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ~0; 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(base != NULL); // base may be NULL if count is zero 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int lo = 0; 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int hi = count - 1; 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (lo < hi) { 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int mid = (hi + lo) >> 1; 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const T* elem = (const T*)((const char*)base + mid * elemSize); 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 557839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (less(*elem, key)) 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo = mid + 1; 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = mid; 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const T* elem = (const T*)((const char*)base + hi * elemSize); 627839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (less(*elem, key)) { 637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger hi += 1; 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = ~hi; 657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } else if (less(key, *elem)) { 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = ~hi; 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return hi; 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 717839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// Adapts a less-than function to a functor. 727839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor { 737839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool operator()(const T& a, const T& b) { return LESS(a, b); } 747839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger}; 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 767839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// Specialization for case when T==K and the caller wants to use a function rather than functor. 777839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T, bool (LESS)(const T&, const T&)> 787839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerint SkTSearch(const T base[], int count, const T& target, size_t elemSize) { 797839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger static SkTLessFunctionToFunctorAdaptor<T, LESS> functor; 807839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return SkTSearch(base, count, target, elemSize, functor); 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 837839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// Adapts operator < to a functor. 847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T> struct SkTLessFunctor { 857839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool operator()(const T& a, const T& b) { return a < b; } 867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger}; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// Specialization for T==K, compare using op <. 897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T> 907839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerint SkTSearch(const T base[], int count, const T& target, size_t elemSize) { 917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger static SkTLessFunctor<T> functor; 927839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return SkTSearch(base, count, target, elemSize, functor); 937839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 957839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T. 967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor { 977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger bool operator() (const T* t, const T* k) { return LESS(*t, *k); } 987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger}; 997839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 1007839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// Specialization for case where domain is an array of T* and the key value is a T*, and you want 1017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// to compare the T objects, not the pointers. 1027839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergertemplate <typename T, bool (LESS)(const T&, const T&)> 1037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerint SkTSearch(T* base[], int count, T* target, size_t elemSize) { 1047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor; 1057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return SkTSearch(base, count, target, elemSize, functor); 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 1077839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrSearch(const char*const* base, int count, const char target[], 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t target_len, size_t elemSize); 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrSearch(const char*const* base, int count, const char target[], 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t elemSize); 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru base points to a table of lower-case strings. 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrLCSearch(const char*const* base, int count, const char target[], 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t target_len, size_t elemSize); 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrLCSearch(const char*const* base, int count, const char target[], 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t elemSize); 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Helper class to convert a string to lower-case, but only modifying the ascii 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru characters. This makes the routine very fast and never changes the string 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru length, but it is not suitable for linguistic purposes. Normally this is 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru used for buiding and searching string tables. 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkAutoAsciiToLC { 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ~SkAutoAsciiToLC(); 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const char* lc() const { return fLC; } 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t length() const { return fLength; } 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* fLC; // points to either the heap or fStorage 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t fLength; 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru enum { 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru STORAGE = 64 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char fStorage[STORAGE+1]; 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Helper when calling qsort with a compare proc that has typed its arguments 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare) 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 147