epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 2 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 3 | * Copyright 2006 The Android Open Source Project |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 4 | * |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 7 | */ |
| 8 | |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 9 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 10 | #ifndef SkTSearch_DEFINED |
| 11 | #define SkTSearch_DEFINED |
| 12 | |
| 13 | #include "SkTypes.h" |
| 14 | |
reed@google.com | 8790fc6 | 2012-04-30 17:17:21 +0000 | [diff] [blame] | 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 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 33 | |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 34 | // The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is |
| 35 | // used to perform comparisons. It has two function operators: |
| 36 | // bool operator() (const T& t, const K& k) |
| 37 | // bool operator() (const K& t, const T& k) |
| 38 | template <typename T, typename K, typename LESS> |
| 39 | int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less) |
bsalomon@google.com | 44f7c4a | 2012-07-03 15:03:10 +0000 | [diff] [blame] | 40 | { |
| 41 | SkASSERT(count >= 0); |
| 42 | if (count <= 0) { |
| 43 | return ~0; |
| 44 | } |
| 45 | |
Ben Wagner | a93a14a | 2017-08-28 10:34:05 -0400 | [diff] [blame] | 46 | SkASSERT(base != nullptr); // base may be nullptr if count is zero |
bsalomon@google.com | 44f7c4a | 2012-07-03 15:03:10 +0000 | [diff] [blame] | 47 | |
| 48 | int lo = 0; |
| 49 | int hi = count - 1; |
| 50 | |
| 51 | while (lo < hi) { |
mdempsky | 07ed41f | 2015-09-22 10:32:02 -0700 | [diff] [blame] | 52 | int mid = lo + ((hi - lo) >> 1); |
bsalomon@google.com | 44f7c4a | 2012-07-03 15:03:10 +0000 | [diff] [blame] | 53 | const T* elem = (const T*)((const char*)base + mid * elemSize); |
| 54 | |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 55 | if (less(*elem, key)) |
bsalomon@google.com | 44f7c4a | 2012-07-03 15:03:10 +0000 | [diff] [blame] | 56 | lo = mid + 1; |
| 57 | else |
| 58 | hi = mid; |
| 59 | } |
| 60 | |
| 61 | const T* elem = (const T*)((const char*)base + hi * elemSize); |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 62 | if (less(*elem, key)) { |
| 63 | hi += 1; |
| 64 | hi = ~hi; |
| 65 | } else if (less(key, *elem)) { |
bsalomon@google.com | 44f7c4a | 2012-07-03 15:03:10 +0000 | [diff] [blame] | 66 | hi = ~hi; |
| 67 | } |
| 68 | return hi; |
| 69 | } |
| 70 | |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 71 | // Adapts a less-than function to a functor. |
| 72 | template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor { |
| 73 | bool operator()(const T& a, const T& b) { return LESS(a, b); } |
| 74 | }; |
| 75 | |
| 76 | // Specialization for case when T==K and the caller wants to use a function rather than functor. |
| 77 | template <typename T, bool (LESS)(const T&, const T&)> |
| 78 | int SkTSearch(const T base[], int count, const T& target, size_t elemSize) { |
| 79 | static SkTLessFunctionToFunctorAdaptor<T, LESS> functor; |
| 80 | return SkTSearch(base, count, target, elemSize, functor); |
| 81 | } |
| 82 | |
| 83 | // Adapts operator < to a functor. |
| 84 | template <typename T> struct SkTLessFunctor { |
| 85 | bool operator()(const T& a, const T& b) { return a < b; } |
| 86 | }; |
| 87 | |
| 88 | // Specialization for T==K, compare using op <. |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 89 | template <typename T> |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 90 | int SkTSearch(const T base[], int count, const T& target, size_t elemSize) { |
| 91 | static SkTLessFunctor<T> functor; |
| 92 | return SkTSearch(base, count, target, elemSize, functor); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 93 | } |
| 94 | |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 95 | // Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T. |
| 96 | template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor { |
| 97 | bool operator() (const T* t, const T* k) { return LESS(*t, *k); } |
| 98 | }; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 99 | |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 100 | // Specialization for case where domain is an array of T* and the key value is a T*, and you want |
| 101 | // to compare the T objects, not the pointers. |
| 102 | template <typename T, bool (LESS)(const T&, const T&)> |
| 103 | int SkTSearch(T* base[], int count, T* target, size_t elemSize) { |
| 104 | static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor; |
| 105 | return SkTSearch(base, count, target, elemSize, functor); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 106 | } |
| 107 | |
| 108 | int SkStrSearch(const char*const* base, int count, const char target[], |
| 109 | size_t target_len, size_t elemSize); |
| 110 | int SkStrSearch(const char*const* base, int count, const char target[], |
| 111 | size_t elemSize); |
| 112 | |
| 113 | /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that |
| 114 | base points to a table of lower-case strings. |
| 115 | */ |
| 116 | int SkStrLCSearch(const char*const* base, int count, const char target[], |
| 117 | size_t target_len, size_t elemSize); |
| 118 | int SkStrLCSearch(const char*const* base, int count, const char target[], |
| 119 | size_t elemSize); |
| 120 | |
| 121 | /** Helper class to convert a string to lower-case, but only modifying the ascii |
| 122 | characters. This makes the routine very fast and never changes the string |
| 123 | length, but it is not suitable for linguistic purposes. Normally this is |
| 124 | used for buiding and searching string tables. |
| 125 | */ |
| 126 | class SkAutoAsciiToLC { |
| 127 | public: |
| 128 | SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1); |
| 129 | ~SkAutoAsciiToLC(); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 130 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 131 | const char* lc() const { return fLC; } |
| 132 | size_t length() const { return fLength; } |
| 133 | |
| 134 | private: |
| 135 | char* fLC; // points to either the heap or fStorage |
| 136 | size_t fLength; |
| 137 | enum { |
| 138 | STORAGE = 64 |
| 139 | }; |
| 140 | char fStorage[STORAGE+1]; |
| 141 | }; |
| 142 | |
reed@google.com | c7a67cb | 2012-05-07 14:52:12 +0000 | [diff] [blame] | 143 | // Helper when calling qsort with a compare proc that has typed its arguments |
| 144 | #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 145 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 146 | #endif |