OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2006 The Android Open Source Project | 3 * Copyright 2006 The Android Open Source Project |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 | 9 |
10 #ifndef SkTSearch_DEFINED | 10 #ifndef SkTSearch_DEFINED |
(...skipping 12 matching lines...) Expand all Loading... |
23 * | 23 * |
24 * int index = SkTSearch(...); | 24 * int index = SkTSearch(...); |
25 * if (index >= 0) { | 25 * if (index >= 0) { |
26 * // found at index | 26 * // found at index |
27 * } else { | 27 * } else { |
28 * index = ~index; // now we are positive | 28 * index = ~index; // now we are positive |
29 * // insert at index | 29 * // insert at index |
30 * } | 30 * } |
31 */ | 31 */ |
32 | 32 |
33 template <typename T> | |
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 | 33 |
40 SkASSERT(base != NULL); // base may be NULL if count is zero | 34 // The most general form of SkTSearch takes an array of T and a key of type K. A
functor, less, is |
41 | 35 // used to perform comparisons. It has two function operators: |
42 int lo = 0; | 36 // bool operator() (const T& t, const K& k) |
43 int hi = count - 1; | 37 // bool operator() (const K& t, const T& k) |
44 | 38 template <typename T, typename K, typename LESS> |
45 while (lo < hi) | 39 int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& le
ss) |
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*)> | |
67 int SkTSearch(const T* base, int count, const T& target, size_t elemSize) | |
68 { | 40 { |
69 SkASSERT(count >= 0); | 41 SkASSERT(count >= 0); |
70 if (count <= 0) { | 42 if (count <= 0) { |
71 return ~0; | 43 return ~0; |
72 } | 44 } |
73 | 45 |
74 SkASSERT(base != NULL); // base may be NULL if count is zero | 46 SkASSERT(base != NULL); // base may be NULL if count is zero |
75 | 47 |
76 int lo = 0; | 48 int lo = 0; |
77 int hi = count - 1; | 49 int hi = count - 1; |
78 | 50 |
79 while (lo < hi) { | 51 while (lo < hi) { |
80 int mid = (hi + lo) >> 1; | 52 int mid = (hi + lo) >> 1; |
81 const T* elem = (const T*)((const char*)base + mid * elemSize); | 53 const T* elem = (const T*)((const char*)base + mid * elemSize); |
82 | 54 |
83 if (COMPARE(elem, &target) < 0) | 55 if (less(*elem, key)) |
84 lo = mid + 1; | 56 lo = mid + 1; |
85 else | 57 else |
86 hi = mid; | 58 hi = mid; |
87 } | 59 } |
88 | 60 |
89 const T* elem = (const T*)((const char*)base + hi * elemSize); | 61 const T* elem = (const T*)((const char*)base + hi * elemSize); |
90 int pred = COMPARE(elem, &target); | 62 if (less(*elem, key)) { |
91 if (pred != 0) { | 63 hi += 1; |
92 if (pred < 0) | 64 hi = ~hi; |
93 hi += 1; | 65 } else if (less(key, *elem)) { |
94 hi = ~hi; | 66 hi = ~hi; |
95 } | 67 } |
96 return hi; | 68 return hi; |
97 } | 69 } |
98 | 70 |
99 template <typename T> | 71 // Adapts a less-than function to a functor. |
100 int SkTSearch(const T* base, int count, const T& target, size_t elemSize, | 72 template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToF
unctorAdaptor { |
101 int (*compare)(const T*, const T*)) | 73 bool operator()(const T& a, const T& b) { return LESS(a, b); } |
102 { | 74 }; |
103 SkASSERT(count >= 0); | |
104 if (count <= 0) { | |
105 return ~0; | |
106 } | |
107 | 75 |
108 SkASSERT(base != NULL); // base may be NULL if count is zero | 76 // Specialization for case when T==K and the caller wants to use a function rath
er than functor. |
109 | 77 template <typename T, bool (LESS)(const T&, const T&)> |
110 int lo = 0; | 78 int SkTSearch(const T base[], int count, const T& target, size_t elemSize) { |
111 int hi = count - 1; | 79 static SkTLessFunctionToFunctorAdaptor<T, LESS> functor; |
112 | 80 return SkTSearch(base, count, target, elemSize, functor); |
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 } | 81 } |
132 | 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 <. |
133 template <typename T> | 89 template <typename T> |
134 int SkTSearch(const T** base, int count, const T* target, size_t elemSize, | 90 int SkTSearch(const T base[], int count, const T& target, size_t elemSize) { |
135 int (*compare)(const T*, const T*)) | 91 static SkTLessFunctor<T> functor; |
136 { | 92 return SkTSearch(base, count, target, elemSize, functor); |
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 } | 93 } |
167 | 94 |
168 template <typename T, int (COMPARE)(const T*, const T*)> | 95 // Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface tak
e T* rather than T. |
169 int SkTSearch(const T** base, int count, const T* target, size_t elemSize) | 96 template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToP
trFunctorAdaptor { |
170 { | 97 bool operator() (const T* t, const T* k) { return LESS(*t, *k); } |
171 SkASSERT(count >= 0); | 98 }; |
172 if (count <= 0) | |
173 return ~0; | |
174 | 99 |
175 SkASSERT(base != NULL); // base may be NULL if count is zero | 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 } |
176 | 107 |
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[], | 108 int SkStrSearch(const char*const* base, int count, const char target[], |
202 size_t target_len, size_t elemSize); | 109 size_t target_len, size_t elemSize); |
203 int SkStrSearch(const char*const* base, int count, const char target[], | 110 int SkStrSearch(const char*const* base, int count, const char target[], |
204 size_t elemSize); | 111 size_t elemSize); |
205 | 112 |
206 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes th
at | 113 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes th
at |
207 base points to a table of lower-case strings. | 114 base points to a table of lower-case strings. |
208 */ | 115 */ |
209 int SkStrLCSearch(const char*const* base, int count, const char target[], | 116 int SkStrLCSearch(const char*const* base, int count, const char target[], |
210 size_t target_len, size_t elemSize); | 117 size_t target_len, size_t elemSize); |
(...skipping 19 matching lines...) Expand all Loading... |
230 enum { | 137 enum { |
231 STORAGE = 64 | 138 STORAGE = 64 |
232 }; | 139 }; |
233 char fStorage[STORAGE+1]; | 140 char fStorage[STORAGE+1]; |
234 }; | 141 }; |
235 | 142 |
236 // Helper when calling qsort with a compare proc that has typed its arguments | 143 // 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) | 144 #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void
*)>(compare) |
238 | 145 |
239 #endif | 146 #endif |
OLD | NEW |