| 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 |