The Tor Browser / file comparison
comparison: gfx/skia/trunk/include/core/SkTSearch.h
gfx/skia/trunk/include/core/SkTSearch.h
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:326924fd8ef2 |
|---|---|
| 1 | |
| 2 /* | |
| 3 * Copyright 2006 The Android Open Source Project | |
| 4 * | |
| 5 * Use of this source code is governed by a BSD-style license that can be | |
| 6 * found in the LICENSE file. | |
| 7 */ | |
| 8 | |
| 9 | |
| 10 #ifndef SkTSearch_DEFINED | |
| 11 #define SkTSearch_DEFINED | |
| 12 | |
| 13 #include "SkTypes.h" | |
| 14 | |
| 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 | |
| 33 | |
| 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) | |
| 40 { | |
| 41 SkASSERT(count >= 0); | |
| 42 if (count <= 0) { | |
| 43 return ~0; | |
| 44 } | |
| 45 | |
| 46 SkASSERT(base != NULL); // base may be NULL if count is zero | |
| 47 | |
| 48 int lo = 0; | |
| 49 int hi = count - 1; | |
| 50 | |
| 51 while (lo < hi) { | |
| 52 int mid = (hi + lo) >> 1; | |
| 53 const T* elem = (const T*)((const char*)base + mid * elemSize); | |
| 54 | |
| 55 if (less(*elem, key)) | |
| 56 lo = mid + 1; | |
| 57 else | |
| 58 hi = mid; | |
| 59 } | |
| 60 | |
| 61 const T* elem = (const T*)((const char*)base + hi * elemSize); | |
| 62 if (less(*elem, key)) { | |
| 63 hi += 1; | |
| 64 hi = ~hi; | |
| 65 } else if (less(key, *elem)) { | |
| 66 hi = ~hi; | |
| 67 } | |
| 68 return hi; | |
| 69 } | |
| 70 | |
| 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 <. | |
| 89 template <typename T> | |
| 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); | |
| 93 } | |
| 94 | |
| 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 }; | |
| 99 | |
| 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); | |
| 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(); | |
| 130 | |
| 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 | |
| 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) | |
| 145 | |
| 146 #endif |
