Modified: trunk/Source/WTF/wtf/RangeSet.h (195419 => 195420)
--- trunk/Source/WTF/wtf/RangeSet.h 2016-01-21 20:16:01 UTC (rev 195419)
+++ trunk/Source/WTF/wtf/RangeSet.h 2016-01-21 21:37:56 UTC (rev 195420)
@@ -92,15 +92,8 @@
return false;
unsigned index = findRange(range);
- if (index + 1 < m_ranges.size()
- && subsumesNonEmpty(m_ranges[index + 1], range))
- return true;
- if (index < m_ranges.size()
- && subsumesNonEmpty(m_ranges[index], range))
- return true;
- if (static_cast<unsigned>(index - 1) < m_ranges.size()
- && subsumesNonEmpty(m_ranges[index - 1], range))
- return true;
+ if (index != UINT_MAX)
+ return subsumesNonEmpty(m_ranges[index], range);
return false;
}
@@ -109,17 +102,7 @@
if (range.begin() == range.end())
return false;
- unsigned index = findRange(range);
- if (index + 1 < m_ranges.size()
- && overlapsNonEmpty(m_ranges[index + 1], range))
- return true;
- if (index < m_ranges.size()
- && overlapsNonEmpty(m_ranges[index], range))
- return true;
- if (static_cast<unsigned>(index - 1) < m_ranges.size()
- && overlapsNonEmpty(m_ranges[index - 1], range))
- return true;
- return false;
+ return findRange(range) != UINT_MAX;
}
void clear()
@@ -191,14 +174,13 @@
{
const_cast<RangeSet*>(this)->compact();
- const Range* found = approximateBinarySearch<const Range, Type>(
- m_ranges, m_ranges.size(), range.begin(), [&] (const Range* range) -> Type {
- return range->begin();
- });
- if (!found)
- return UINT_MAX;
-
- return found - m_ranges.begin();
+ // FIXME: Once we start using this in anger, we will want this to be a binary search.
+ for (unsigned i = 0; i < m_ranges.size(); ++i) {
+ if (overlapsNonEmpty(m_ranges[i], range))
+ return i;
+ }
+
+ return UINT_MAX;
}
Vector<Range, 8> m_ranges;
Modified: trunk/Source/WTF/wtf/StdLibExtras.h (195419 => 195420)
--- trunk/Source/WTF/wtf/StdLibExtras.h 2016-01-21 20:16:01 UTC (rev 195419)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2016-01-21 21:37:56 UTC (rev 195420)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
+ * Copyright (C) 2008 Apple Inc. All Rights Reserved.
* Copyright (C) 2013 Patrick Gansterer <par...@paroga.com>
*
* Redistribution and use in source and binary forms, with or without
@@ -212,7 +212,7 @@
ASSERT(mode != KeyMustBePresentInArray || size);
}
- if (mode != KeyMustBePresentInArray && !size)
+ if (mode == KeyMightNotBePresentInArray && !size)
return 0;
ArrayElementType* result = &array[offset];
@@ -230,38 +230,38 @@
// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
}
// Return zero if the element is not found.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
}
// Return the element that is either to the left, or the right, of where the element would have been found.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
}
// Variants of the above that use const.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
}
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
}
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
}