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 template <typename T>
SkTSearch(const T * base,int count,const T & target,size_t elemSize)34 int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
35 {
36 SkASSERT(count >= 0);
37 if (count <= 0)
38 return ~0;
39
40 SkASSERT(base != NULL); // base may be NULL if count is zero
41
42 int lo = 0;
43 int hi = count - 1;
44
45 while (lo < hi)
46 {
47 int mid = (hi + lo) >> 1;
48 const T* elem = (const T*)((const char*)base + mid * elemSize);
49
50 if (*elem < target)
51 lo = mid + 1;
52 else
53 hi = mid;
54 }
55
56 const T* elem = (const T*)((const char*)base + hi * elemSize);
57 if (*elem != target)
58 {
59 if (*elem < target)
60 hi += 1;
61 hi = ~hi;
62 }
63 return hi;
64 }
65
66 template <typename T, int (COMPARE)(const T*, const T*)>
SkTSearch(const T * base,int count,const T & target,size_t elemSize)67 int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
68 {
69 SkASSERT(count >= 0);
70 if (count <= 0) {
71 return ~0;
72 }
73
74 SkASSERT(base != NULL); // base may be NULL if count is zero
75
76 int lo = 0;
77 int hi = count - 1;
78
79 while (lo < hi) {
80 int mid = (hi + lo) >> 1;
81 const T* elem = (const T*)((const char*)base + mid * elemSize);
82
83 if (COMPARE(elem, &target) < 0)
84 lo = mid + 1;
85 else
86 hi = mid;
87 }
88
89 const T* elem = (const T*)((const char*)base + hi * elemSize);
90 int pred = COMPARE(elem, &target);
91 if (pred != 0) {
92 if (pred < 0)
93 hi += 1;
94 hi = ~hi;
95 }
96 return hi;
97 }
98
99 template <typename T>
SkTSearch(const T * base,int count,const T & target,size_t elemSize,int (* compare)(const T *,const T *))100 int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
101 int (*compare)(const T*, const T*))
102 {
103 SkASSERT(count >= 0);
104 if (count <= 0) {
105 return ~0;
106 }
107
108 SkASSERT(base != NULL); // base may be NULL if count is zero
109
110 int lo = 0;
111 int hi = count - 1;
112
113 while (lo < hi) {
114 int mid = (hi + lo) >> 1;
115 const T* elem = (const T*)((const char*)base + mid * elemSize);
116
117 if ((*compare)(elem, &target) < 0)
118 lo = mid + 1;
119 else
120 hi = mid;
121 }
122
123 const T* elem = (const T*)((const char*)base + hi * elemSize);
124 int pred = (*compare)(elem, &target);
125 if (pred != 0) {
126 if (pred < 0)
127 hi += 1;
128 hi = ~hi;
129 }
130 return hi;
131 }
132
133 template <typename T>
SkTSearch(const T ** base,int count,const T * target,size_t elemSize,int (* compare)(const T *,const T *))134 int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
135 int (*compare)(const T*, const T*))
136 {
137 SkASSERT(count >= 0);
138 if (count <= 0)
139 return ~0;
140
141 SkASSERT(base != NULL); // base may be NULL if count is zero
142
143 int lo = 0;
144 int hi = count - 1;
145
146 while (lo < hi)
147 {
148 int mid = (hi + lo) >> 1;
149 const T* elem = *(const T**)((const char*)base + mid * elemSize);
150
151 if ((*compare)(elem, target) < 0)
152 lo = mid + 1;
153 else
154 hi = mid;
155 }
156
157 const T* elem = *(const T**)((const char*)base + hi * elemSize);
158 int pred = (*compare)(elem, target);
159 if (pred != 0)
160 {
161 if (pred < 0)
162 hi += 1;
163 hi = ~hi;
164 }
165 return hi;
166 }
167
168 template <typename T, int (COMPARE)(const T*, const T*)>
SkTSearch(const T ** base,int count,const T * target,size_t elemSize)169 int SkTSearch(const T** base, int count, const T* target, size_t elemSize)
170 {
171 SkASSERT(count >= 0);
172 if (count <= 0)
173 return ~0;
174
175 SkASSERT(base != NULL); // base may be NULL if count is zero
176
177 int lo = 0;
178 int hi = count - 1;
179
180 while (lo < hi)
181 {
182 int mid = (hi + lo) >> 1;
183 const T* elem = *(const T**)((const char*)base + mid * elemSize);
184
185 if (COMPARE(elem, target) < 0)
186 lo = mid + 1;
187 else
188 hi = mid;
189 }
190
191 const T* elem = *(const T**)((const char*)base + hi * elemSize);
192 int pred = COMPARE(elem, target);
193 if (pred != 0)
194 {
195 if (pred < 0)
196 hi += 1;
197 hi = ~hi;
198 }
199 return hi;
200 }
201 int SkStrSearch(const char*const* base, int count, const char target[],
202 size_t target_len, size_t elemSize);
203 int SkStrSearch(const char*const* base, int count, const char target[],
204 size_t elemSize);
205
206 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
207 base points to a table of lower-case strings.
208 */
209 int SkStrLCSearch(const char*const* base, int count, const char target[],
210 size_t target_len, size_t elemSize);
211 int SkStrLCSearch(const char*const* base, int count, const char target[],
212 size_t elemSize);
213
214 /** Helper class to convert a string to lower-case, but only modifying the ascii
215 characters. This makes the routine very fast and never changes the string
216 length, but it is not suitable for linguistic purposes. Normally this is
217 used for buiding and searching string tables.
218 */
219 class SkAutoAsciiToLC {
220 public:
221 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
222 ~SkAutoAsciiToLC();
223
lc()224 const char* lc() const { return fLC; }
length()225 size_t length() const { return fLength; }
226
227 private:
228 char* fLC; // points to either the heap or fStorage
229 size_t fLength;
230 enum {
231 STORAGE = 64
232 };
233 char fStorage[STORAGE+1];
234 };
235
236 // Helper when calling qsort with a compare proc that has typed its arguments
237 #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
238
239 #endif
240