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 "include/private/base/SkAssert.h"
14
15 #include <cstddef>
16
17 /**
18 * All of the SkTSearch variants want to return the index (0...N-1) of the
19 * found element, or the bit-not of where to insert the element.
20 *
21 * At a simple level, if the return value is negative, it was not found.
22 *
23 * For clients that want to insert the new element if it was not found, use
24 * the following logic:
25 *
26 * int index = SkTSearch(...);
27 * if (index >= 0) {
28 * // found at index
29 * } else {
30 * index = ~index; // now we are positive
31 * // insert at index
32 * }
33 */
34
35
36 // The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
37 // used to perform comparisons. It has two function operators:
38 // bool operator() (const T& t, const K& k)
39 // bool operator() (const K& t, const T& k)
40 template <typename T, typename K, typename LESS>
SkTSearch(const T base[],int count,const K & key,size_t elemSize,const LESS & less)41 int SkTSearch(const T base[], int count, const K& key, size_t elemSize, const LESS& less)
42 {
43 SkASSERT(count >= 0);
44 if (count <= 0) {
45 return ~0;
46 }
47
48 SkASSERT(base != nullptr); // base may be nullptr if count is zero
49
50 int lo = 0;
51 int hi = count - 1;
52
53 while (lo < hi) {
54 int mid = lo + ((hi - lo) >> 1);
55 const T* elem = (const T*)((const char*)base + mid * elemSize);
56
57 if (less(*elem, key))
58 lo = mid + 1;
59 else
60 hi = mid;
61 }
62
63 const T* elem = (const T*)((const char*)base + hi * elemSize);
64 if (less(*elem, key)) {
65 hi += 1;
66 hi = ~hi;
67 } else if (less(key, *elem)) {
68 hi = ~hi;
69 }
70 return hi;
71 }
72
73 // Specialization for case when T==K and the caller wants to use a function rather than functor.
74 template <typename T, bool (LESS)(const T&, const T&)>
SkTSearch(const T base[],int count,const T & target,size_t elemSize)75 int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
76 return SkTSearch(base, count, target, elemSize,
77 [](const T& a, const T& b) { return LESS(a, b); });
78 }
79
80 // Specialization for T==K, compare using op <.
81 template <typename T>
SkTSearch(const T base[],int count,const T & target,size_t elemSize)82 int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
83 return SkTSearch(base, count, target, elemSize, [](const T& a, const T& b) { return a < b; });
84 }
85
86 // Specialization for case where domain is an array of T* and the key value is a T*, and you want
87 // to compare the T objects, not the pointers.
88 template <typename T, bool (LESS)(const T&, const T&)>
SkTSearch(T * base[],int count,T * target,size_t elemSize)89 int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
90 return SkTSearch(base, count, target, elemSize,
91 [](const T* t, const T* k) { return LESS(*t, *k); });
92 }
93
94 int SkStrSearch(const char*const* base, int count, const char target[],
95 size_t target_len, size_t elemSize);
96 int SkStrSearch(const char*const* base, int count, const char target[],
97 size_t elemSize);
98
99 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
100 base points to a table of lower-case strings.
101 */
102 int SkStrLCSearch(const char*const* base, int count, const char target[],
103 size_t target_len, size_t elemSize);
104 int SkStrLCSearch(const char*const* base, int count, const char target[],
105 size_t elemSize);
106
107 /** Helper class to convert a string to lower-case, but only modifying the ascii
108 characters. This makes the routine very fast and never changes the string
109 length, but it is not suitable for linguistic purposes. Normally this is
110 used for buiding and searching string tables.
111 */
112 class SkAutoAsciiToLC {
113 public:
114 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
115 ~SkAutoAsciiToLC();
116
lc()117 const char* lc() const { return fLC; }
length()118 size_t length() const { return fLength; }
119
120 private:
121 char* fLC; // points to either the heap or fStorage
122 size_t fLength;
123 enum {
124 STORAGE = 64
125 };
126 char fStorage[STORAGE+1];
127 };
128
129 // Helper when calling qsort with a compare proc that has typed its arguments
130 #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
131
132 #endif
133