1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/core/SkTSearch.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,146 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#ifndef SkTSearch_DEFINED
1.14 +#define SkTSearch_DEFINED
1.15 +
1.16 +#include "SkTypes.h"
1.17 +
1.18 +/**
1.19 + * All of the SkTSearch variants want to return the index (0...N-1) of the
1.20 + * found element, or the bit-not of where to insert the element.
1.21 + *
1.22 + * At a simple level, if the return value is negative, it was not found.
1.23 + *
1.24 + * For clients that want to insert the new element if it was not found, use
1.25 + * the following logic:
1.26 + *
1.27 + * int index = SkTSearch(...);
1.28 + * if (index >= 0) {
1.29 + * // found at index
1.30 + * } else {
1.31 + * index = ~index; // now we are positive
1.32 + * // insert at index
1.33 + * }
1.34 + */
1.35 +
1.36 +
1.37 +// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
1.38 +// used to perform comparisons. It has two function operators:
1.39 +// bool operator() (const T& t, const K& k)
1.40 +// bool operator() (const K& t, const T& k)
1.41 +template <typename T, typename K, typename LESS>
1.42 +int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
1.43 +{
1.44 + SkASSERT(count >= 0);
1.45 + if (count <= 0) {
1.46 + return ~0;
1.47 + }
1.48 +
1.49 + SkASSERT(base != NULL); // base may be NULL if count is zero
1.50 +
1.51 + int lo = 0;
1.52 + int hi = count - 1;
1.53 +
1.54 + while (lo < hi) {
1.55 + int mid = (hi + lo) >> 1;
1.56 + const T* elem = (const T*)((const char*)base + mid * elemSize);
1.57 +
1.58 + if (less(*elem, key))
1.59 + lo = mid + 1;
1.60 + else
1.61 + hi = mid;
1.62 + }
1.63 +
1.64 + const T* elem = (const T*)((const char*)base + hi * elemSize);
1.65 + if (less(*elem, key)) {
1.66 + hi += 1;
1.67 + hi = ~hi;
1.68 + } else if (less(key, *elem)) {
1.69 + hi = ~hi;
1.70 + }
1.71 + return hi;
1.72 +}
1.73 +
1.74 +// Adapts a less-than function to a functor.
1.75 +template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor {
1.76 + bool operator()(const T& a, const T& b) { return LESS(a, b); }
1.77 +};
1.78 +
1.79 +// Specialization for case when T==K and the caller wants to use a function rather than functor.
1.80 +template <typename T, bool (LESS)(const T&, const T&)>
1.81 +int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
1.82 + static SkTLessFunctionToFunctorAdaptor<T, LESS> functor;
1.83 + return SkTSearch(base, count, target, elemSize, functor);
1.84 +}
1.85 +
1.86 +// Adapts operator < to a functor.
1.87 +template <typename T> struct SkTLessFunctor {
1.88 + bool operator()(const T& a, const T& b) { return a < b; }
1.89 +};
1.90 +
1.91 +// Specialization for T==K, compare using op <.
1.92 +template <typename T>
1.93 +int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
1.94 + static SkTLessFunctor<T> functor;
1.95 + return SkTSearch(base, count, target, elemSize, functor);
1.96 +}
1.97 +
1.98 +// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
1.99 +template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor {
1.100 + bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
1.101 +};
1.102 +
1.103 +// Specialization for case where domain is an array of T* and the key value is a T*, and you want
1.104 +// to compare the T objects, not the pointers.
1.105 +template <typename T, bool (LESS)(const T&, const T&)>
1.106 +int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
1.107 + static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor;
1.108 + return SkTSearch(base, count, target, elemSize, functor);
1.109 +}
1.110 +
1.111 +int SkStrSearch(const char*const* base, int count, const char target[],
1.112 + size_t target_len, size_t elemSize);
1.113 +int SkStrSearch(const char*const* base, int count, const char target[],
1.114 + size_t elemSize);
1.115 +
1.116 +/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
1.117 + base points to a table of lower-case strings.
1.118 +*/
1.119 +int SkStrLCSearch(const char*const* base, int count, const char target[],
1.120 + size_t target_len, size_t elemSize);
1.121 +int SkStrLCSearch(const char*const* base, int count, const char target[],
1.122 + size_t elemSize);
1.123 +
1.124 +/** Helper class to convert a string to lower-case, but only modifying the ascii
1.125 + characters. This makes the routine very fast and never changes the string
1.126 + length, but it is not suitable for linguistic purposes. Normally this is
1.127 + used for buiding and searching string tables.
1.128 +*/
1.129 +class SkAutoAsciiToLC {
1.130 +public:
1.131 + SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
1.132 + ~SkAutoAsciiToLC();
1.133 +
1.134 + const char* lc() const { return fLC; }
1.135 + size_t length() const { return fLength; }
1.136 +
1.137 +private:
1.138 + char* fLC; // points to either the heap or fStorage
1.139 + size_t fLength;
1.140 + enum {
1.141 + STORAGE = 64
1.142 + };
1.143 + char fStorage[STORAGE+1];
1.144 +};
1.145 +
1.146 +// Helper when calling qsort with a compare proc that has typed its arguments
1.147 +#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
1.148 +
1.149 +#endif
