OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2008 Apple Inc. All Rights Reserved. | 2 * Copyright (C) 2008 Apple Inc. All Rights Reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
11 * documentation and/or other materials provided with the distribution. | 11 * documentation and/or other materials provided with the distribution. |
12 * | 12 * |
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY | 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR | 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 */ | 24 */ |
25 | 25 |
26 #ifndef WTF_StdLibExtras_h | 26 #ifndef WTF_StdLibExtras_h |
27 #define WTF_StdLibExtras_h | 27 #define WTF_StdLibExtras_h |
28 | 28 |
29 #include "wtf/Assertions.h" | 29 #include "wtf/Assertions.h" |
30 #include "wtf/CPU.h" | 30 #include "wtf/CPU.h" |
31 #include "wtf/CheckedArithmetic.h" | 31 #include "wtf/CheckedArithmetic.h" |
32 | 32 |
33 // Use these to declare and define a static local variable (static T;) so that | 33 // Use these to declare and define a static local variable (static T;) so that |
(...skipping 149 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
183 ReturnAdjacentElementIfKeyIsNotPresent | 183 ReturnAdjacentElementIfKeyIsNotPresent |
184 }; | 184 }; |
185 | 185 |
186 template<typename ArrayElementType, typename KeyType, typename ArrayType, typena
me ExtractKey, BinarySearchMode mode> | 186 template<typename ArrayElementType, typename KeyType, typename ArrayType, typena
me ExtractKey, BinarySearchMode mode> |
187 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType
key, const ExtractKey& extractKey = ExtractKey()) | 187 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType
key, const ExtractKey& extractKey = ExtractKey()) |
188 { | 188 { |
189 size_t offset = 0; | 189 size_t offset = 0; |
190 while (size > 1) { | 190 while (size > 1) { |
191 size_t pos = (size - 1) >> 1; | 191 size_t pos = (size - 1) >> 1; |
192 KeyType val = extractKey(&array[offset + pos]); | 192 KeyType val = extractKey(&array[offset + pos]); |
193 | 193 |
194 if (val == key) | 194 if (val == key) |
195 return &array[offset + pos]; | 195 return &array[offset + pos]; |
196 // The item we are looking for is smaller than the item being check; red
uce the value of 'size', | 196 // The item we are looking for is smaller than the item being check; red
uce the value of 'size', |
197 // chopping off the right hand half of the array. | 197 // chopping off the right hand half of the array. |
198 if (key < val) | 198 if (key < val) |
199 size = pos; | 199 size = pos; |
200 // Discard all values in the left hand half of the array, up to and incl
uding the item at pos. | 200 // Discard all values in the left hand half of the array, up to and incl
uding the item at pos. |
201 else { | 201 else { |
202 size -= (pos + 1); | 202 size -= (pos + 1); |
203 offset += (pos + 1); | 203 offset += (pos + 1); |
204 } | 204 } |
205 | 205 |
206 ASSERT(mode != KeyMustBePresentInArray || size); | 206 ASSERT(mode != KeyMustBePresentInArray || size); |
207 } | 207 } |
208 | 208 |
209 if (mode == KeyMightNotBePresentInArray && !size) | 209 if (mode == KeyMightNotBePresentInArray && !size) |
210 return 0; | 210 return 0; |
211 | 211 |
212 ArrayElementType* result = &array[offset]; | 212 ArrayElementType* result = &array[offset]; |
213 | 213 |
214 if (mode == KeyMightNotBePresentInArray && key != extractKey(result)) | 214 if (mode == KeyMightNotBePresentInArray && key != extractKey(result)) |
215 return 0; | 215 return 0; |
216 | 216 |
217 if (mode == KeyMustBePresentInArray) { | 217 if (mode == KeyMustBePresentInArray) { |
218 ASSERT(size == 1); | 218 ASSERT(size == 1); |
219 ASSERT(key == extractKey(result)); | 219 ASSERT(key == extractKey(result)); |
220 } | 220 } |
221 | 221 |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
274 using WTF::MB; | 274 using WTF::MB; |
275 using WTF::isPointerAligned; | 275 using WTF::isPointerAligned; |
276 using WTF::is8ByteAligned; | 276 using WTF::is8ByteAligned; |
277 using WTF::binarySearch; | 277 using WTF::binarySearch; |
278 using WTF::tryBinarySearch; | 278 using WTF::tryBinarySearch; |
279 using WTF::approximateBinarySearch; | 279 using WTF::approximateBinarySearch; |
280 using WTF::bitwise_cast; | 280 using WTF::bitwise_cast; |
281 using WTF::safeCast; | 281 using WTF::safeCast; |
282 | 282 |
283 #endif // WTF_StdLibExtras_h | 283 #endif // WTF_StdLibExtras_h |
OLD | NEW |