Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (137708 => 137709)
--- trunk/Source/_javascript_Core/ChangeLog 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/ChangeLog 2012-12-14 04:41:58 UTC (rev 137709)
@@ -1,5 +1,38 @@
2012-12-13 Filip Pizlo <[email protected]>
+ Attempt to rationalize and simplify WTF::binarySearch
+ https://bugs.webkit.org/show_bug.cgi?id=104890
+
+ Reviewed by Maciej Stachowiak.
+
+ Switch to using the new binarySearch() API. No change in behavior.
+
+ * bytecode/CodeBlock.cpp:
+ (JSC::CodeBlock::bytecodeOffset):
+ (JSC::CodeBlock::codeOriginForReturn):
+ * bytecode/CodeBlock.h:
+ (JSC::CodeBlock::getStubInfo):
+ (JSC::CodeBlock::getByValInfo):
+ (JSC::CodeBlock::getCallLinkInfo):
+ (JSC::CodeBlock::dfgOSREntryDataForBytecodeIndex):
+ (JSC::CodeBlock::valueProfileForBytecodeOffset):
+ (JSC::CodeBlock::rareCaseProfileForBytecodeOffset):
+ (JSC::CodeBlock::specialFastCaseProfileForBytecodeOffset):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::blockIndexForBytecodeOffset):
+ * dfg/DFGMinifiedGraph.h:
+ (JSC::DFG::MinifiedGraph::at):
+ * dfg/DFGOSRExitCompiler32_64.cpp:
+ (JSC::DFG::OSRExitCompiler::compileExit):
+ * dfg/DFGOSRExitCompiler64.cpp:
+ (JSC::DFG::OSRExitCompiler::compileExit):
+ * llint/LLIntSlowPaths.cpp:
+ (JSC::LLInt::LLINT_SLOW_PATH_DECL):
+ * profiler/ProfilerBytecodeSequence.cpp:
+ (JSC::Profiler::BytecodeSequence::indexForBytecodeIndex):
+
+2012-12-13 Filip Pizlo <[email protected]>
+
Don't assert that flags <= 0x3ff in JSTypeInfo
https://bugs.webkit.org/show_bug.cgi?id=104988
Modified: trunk/Source/_javascript_Core/bytecode/CodeBlock.cpp (137708 => 137709)
--- trunk/Source/_javascript_Core/bytecode/CodeBlock.cpp 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/bytecode/CodeBlock.cpp 2012-12-14 04:41:58 UTC (rev 137709)
@@ -2791,7 +2791,8 @@
if (getJITCode().getExecutableMemory()->contains(returnAddress.value())) {
unsigned callReturnOffset = getJITCode().offsetOf(returnAddress.value());
CallReturnOffsetToBytecodeOffset* result =
- binarySearch<CallReturnOffsetToBytecodeOffset, unsigned, getCallReturnOffset>(callIndices.begin(), callIndices.size(), callReturnOffset);
+ binarySearch<CallReturnOffsetToBytecodeOffset, unsigned>(
+ callIndices, callIndices.size(), callReturnOffset, getCallReturnOffset);
ASSERT(result->callReturnOffset == callReturnOffset);
return result->bytecodeOffset;
}
@@ -2816,8 +2817,11 @@
}
unsigned offset = getJITCode().offsetOf(returnAddress.value());
- CodeOriginAtCallReturnOffset* entry = binarySearch<CodeOriginAtCallReturnOffset, unsigned, getCallReturnOffsetForCodeOrigin>(codeOrigins().begin(), codeOrigins().size(), offset, WTF::KeyMustNotBePresentInArray);
- if (entry->callReturnOffset != offset)
+ CodeOriginAtCallReturnOffset* entry =
+ tryBinarySearch<CodeOriginAtCallReturnOffset, unsigned>(
+ codeOrigins(), codeOrigins().size(), offset,
+ getCallReturnOffsetForCodeOrigin);
+ if (!entry)
return false;
codeOrigin = entry->codeOrigin;
return true;
Modified: trunk/Source/_javascript_Core/bytecode/CodeBlock.h (137708 => 137709)
--- trunk/Source/_javascript_Core/bytecode/CodeBlock.h 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/bytecode/CodeBlock.h 2012-12-14 04:41:58 UTC (rev 137709)
@@ -238,30 +238,30 @@
StructureStubInfo& getStubInfo(ReturnAddressPtr returnAddress)
{
- return *(binarySearch<StructureStubInfo, void*, getStructureStubInfoReturnLocation>(m_structureStubInfos.begin(), m_structureStubInfos.size(), returnAddress.value()));
+ return *(binarySearch<StructureStubInfo, void*>(m_structureStubInfos, m_structureStubInfos.size(), returnAddress.value(), getStructureStubInfoReturnLocation));
}
StructureStubInfo& getStubInfo(unsigned bytecodeIndex)
{
- return *(binarySearch<StructureStubInfo, unsigned, getStructureStubInfoBytecodeIndex>(m_structureStubInfos.begin(), m_structureStubInfos.size(), bytecodeIndex));
+ return *(binarySearch<StructureStubInfo, unsigned>(m_structureStubInfos, m_structureStubInfos.size(), bytecodeIndex, getStructureStubInfoBytecodeIndex));
}
void resetStub(StructureStubInfo&);
ByValInfo& getByValInfo(unsigned bytecodeIndex)
{
- return *(binarySearch<ByValInfo, unsigned, getByValInfoBytecodeIndex>(m_byValInfos.begin(), m_byValInfos.size(), bytecodeIndex));
+ return *(binarySearch<ByValInfo, unsigned>(m_byValInfos, m_byValInfos.size(), bytecodeIndex, getByValInfoBytecodeIndex));
}
CallLinkInfo& getCallLinkInfo(ReturnAddressPtr returnAddress)
{
- return *(binarySearch<CallLinkInfo, void*, getCallLinkInfoReturnLocation>(m_callLinkInfos.begin(), m_callLinkInfos.size(), returnAddress.value()));
+ return *(binarySearch<CallLinkInfo, void*>(m_callLinkInfos, m_callLinkInfos.size(), returnAddress.value(), getCallLinkInfoReturnLocation));
}
CallLinkInfo& getCallLinkInfo(unsigned bytecodeIndex)
{
ASSERT(JITCode::isBaselineCode(getJITType()));
- return *(binarySearch<CallLinkInfo, unsigned, getCallLinkInfoBytecodeIndex>(m_callLinkInfos.begin(), m_callLinkInfos.size(), bytecodeIndex));
+ return *(binarySearch<CallLinkInfo, unsigned>(m_callLinkInfos, m_callLinkInfos.size(), bytecodeIndex, getCallLinkInfoBytecodeIndex));
}
#endif // ENABLE(JIT)
@@ -359,15 +359,9 @@
{
if (!m_dfgData)
return 0;
- if (m_dfgData->osrEntry.isEmpty())
- return 0;
- DFG::OSREntryData* result = binarySearch<
- DFG::OSREntryData, unsigned, DFG::getOSREntryDataBytecodeIndex>(
- m_dfgData->osrEntry.begin(), m_dfgData->osrEntry.size(),
- bytecodeIndex, WTF::KeyMustNotBePresentInArray);
- if (result->m_bytecodeIndex != bytecodeIndex)
- return 0;
- return result;
+ return tryBinarySearch<DFG::OSREntryData, unsigned>(
+ m_dfgData->osrEntry, m_dfgData->osrEntry.size(), bytecodeIndex,
+ DFG::getOSREntryDataBytecodeIndex);
}
unsigned appendOSRExit(const DFG::OSRExit& osrExit)
@@ -678,7 +672,9 @@
}
ValueProfile* valueProfileForBytecodeOffset(int bytecodeOffset)
{
- ValueProfile* result = WTF::genericBinarySearch<ValueProfile, int, getValueProfileBytecodeOffset>(m_valueProfiles, m_valueProfiles.size(), bytecodeOffset);
+ ValueProfile* result = binarySearch<ValueProfile, int>(
+ m_valueProfiles, m_valueProfiles.size(), bytecodeOffset,
+ getValueProfileBytecodeOffset<ValueProfile>);
ASSERT(result->m_bytecodeOffset != -1);
ASSERT(instructions()[bytecodeOffset + opcodeLength(
m_globalData->interpreter->getOpcodeID(
@@ -711,7 +707,9 @@
RareCaseProfile* rareCaseProfile(int index) { return &m_rareCaseProfiles[index]; }
RareCaseProfile* rareCaseProfileForBytecodeOffset(int bytecodeOffset)
{
- return WTF::genericBinarySearch<RareCaseProfile, int, getRareCaseProfileBytecodeOffset>(m_rareCaseProfiles, m_rareCaseProfiles.size(), bytecodeOffset);
+ return binarySearch<RareCaseProfile, int>(
+ m_rareCaseProfiles, m_rareCaseProfiles.size(), bytecodeOffset,
+ getRareCaseProfileBytecodeOffset);
}
bool likelyToTakeSlowCase(int bytecodeOffset)
@@ -739,7 +737,9 @@
RareCaseProfile* specialFastCaseProfile(int index) { return &m_specialFastCaseProfiles[index]; }
RareCaseProfile* specialFastCaseProfileForBytecodeOffset(int bytecodeOffset)
{
- return WTF::genericBinarySearch<RareCaseProfile, int, getRareCaseProfileBytecodeOffset>(m_specialFastCaseProfiles, m_specialFastCaseProfiles.size(), bytecodeOffset);
+ return binarySearch<RareCaseProfile, int>(
+ m_specialFastCaseProfiles, m_specialFastCaseProfiles.size(), bytecodeOffset,
+ getRareCaseProfileBytecodeOffset);
}
bool likelyToTakeSpecialFastCase(int bytecodeOffset)
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (137708 => 137709)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2012-12-14 04:41:58 UTC (rev 137709)
@@ -769,7 +769,7 @@
inline BlockIndex Graph::blockIndexForBytecodeOffset(Vector<BlockIndex>& linkingTargets, unsigned bytecodeBegin)
{
- return *WTF::binarySearchWithFunctor<BlockIndex, unsigned>(linkingTargets.begin(), linkingTargets.size(), bytecodeBegin, WTF::KeyMustBePresentInArray, GetBytecodeBeginForBlock(*this));
+ return *binarySearch<BlockIndex, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, GetBytecodeBeginForBlock(*this));
}
} } // namespace JSC::DFG
Modified: trunk/Source/_javascript_Core/dfg/DFGMinifiedGraph.h (137708 => 137709)
--- trunk/Source/_javascript_Core/dfg/DFGMinifiedGraph.h 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/dfg/DFGMinifiedGraph.h 2012-12-14 04:41:58 UTC (rev 137709)
@@ -43,14 +43,8 @@
MinifiedNode* at(NodeIndex nodeIndex)
{
- if (!m_list.size())
- return 0;
- MinifiedNode* entry =
- binarySearch<MinifiedNode, NodeIndex, MinifiedNode::getIndex>(
- m_list.begin(), m_list.size(), nodeIndex, WTF::KeyMustNotBePresentInArray);
- if (entry->index() != nodeIndex)
- return 0;
- return entry;
+ return tryBinarySearch<MinifiedNode, NodeIndex>(
+ m_list, m_list.size(), nodeIndex, MinifiedNode::getIndex);
}
void append(const MinifiedNode& node)
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRExitCompiler32_64.cpp (137708 => 137709)
--- trunk/Source/_javascript_Core/dfg/DFGOSRExitCompiler32_64.cpp 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRExitCompiler32_64.cpp 2012-12-14 04:41:58 UTC (rev 137709)
@@ -640,7 +640,7 @@
CodeBlock* baselineCodeBlockForCaller = m_jit.baselineCodeBlockFor(inlineCallFrame->caller);
Vector<BytecodeAndMachineOffset>& decodedCodeMap = m_jit.decodedCodeMapFor(baselineCodeBlockForCaller);
unsigned returnBytecodeIndex = inlineCallFrame->caller.bytecodeIndex + OPCODE_LENGTH(op_call);
- BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned, BytecodeAndMachineOffset::getBytecodeIndex>(decodedCodeMap.begin(), decodedCodeMap.size(), returnBytecodeIndex);
+ BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned>(decodedCodeMap, decodedCodeMap.size(), returnBytecodeIndex, BytecodeAndMachineOffset::getBytecodeIndex);
ASSERT(mapping);
ASSERT(mapping->m_bytecodeIndex == returnBytecodeIndex);
@@ -749,7 +749,7 @@
CodeBlock* baselineCodeBlock = m_jit.baselineCodeBlockFor(exit.m_codeOrigin);
Vector<BytecodeAndMachineOffset>& decodedCodeMap = m_jit.decodedCodeMapFor(baselineCodeBlock);
- BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned, BytecodeAndMachineOffset::getBytecodeIndex>(decodedCodeMap.begin(), decodedCodeMap.size(), exit.m_codeOrigin.bytecodeIndex);
+ BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned>(decodedCodeMap, decodedCodeMap.size(), exit.m_codeOrigin.bytecodeIndex, BytecodeAndMachineOffset::getBytecodeIndex);
ASSERT(mapping);
ASSERT(mapping->m_bytecodeIndex == exit.m_codeOrigin.bytecodeIndex);
Modified: trunk/Source/_javascript_Core/dfg/DFGOSRExitCompiler64.cpp (137708 => 137709)
--- trunk/Source/_javascript_Core/dfg/DFGOSRExitCompiler64.cpp 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/dfg/DFGOSRExitCompiler64.cpp 2012-12-14 04:41:58 UTC (rev 137709)
@@ -608,7 +608,7 @@
CodeBlock* baselineCodeBlockForCaller = m_jit.baselineCodeBlockFor(inlineCallFrame->caller);
Vector<BytecodeAndMachineOffset>& decodedCodeMap = m_jit.decodedCodeMapFor(baselineCodeBlockForCaller);
unsigned returnBytecodeIndex = inlineCallFrame->caller.bytecodeIndex + OPCODE_LENGTH(op_call);
- BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned, BytecodeAndMachineOffset::getBytecodeIndex>(decodedCodeMap.begin(), decodedCodeMap.size(), returnBytecodeIndex);
+ BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned>(decodedCodeMap, decodedCodeMap.size(), returnBytecodeIndex, BytecodeAndMachineOffset::getBytecodeIndex);
ASSERT(mapping);
ASSERT(mapping->m_bytecodeIndex == returnBytecodeIndex);
@@ -696,7 +696,7 @@
CodeBlock* baselineCodeBlock = m_jit.baselineCodeBlockFor(exit.m_codeOrigin);
Vector<BytecodeAndMachineOffset>& decodedCodeMap = m_jit.decodedCodeMapFor(baselineCodeBlock);
- BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned, BytecodeAndMachineOffset::getBytecodeIndex>(decodedCodeMap.begin(), decodedCodeMap.size(), exit.m_codeOrigin.bytecodeIndex);
+ BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned>(decodedCodeMap, decodedCodeMap.size(), exit.m_codeOrigin.bytecodeIndex, BytecodeAndMachineOffset::getBytecodeIndex);
ASSERT(mapping);
ASSERT(mapping->m_bytecodeIndex == exit.m_codeOrigin.bytecodeIndex);
Modified: trunk/Source/_javascript_Core/llint/LLIntSlowPaths.cpp (137708 => 137709)
--- trunk/Source/_javascript_Core/llint/LLIntSlowPaths.cpp 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/llint/LLIntSlowPaths.cpp 2012-12-14 04:41:58 UTC (rev 137709)
@@ -378,7 +378,7 @@
Vector<BytecodeAndMachineOffset> map;
codeBlock->jitCodeMap()->decode(map);
- BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned, BytecodeAndMachineOffset::getBytecodeIndex>(map.begin(), map.size(), pc - codeBlock->instructions().begin());
+ BytecodeAndMachineOffset* mapping = binarySearch<BytecodeAndMachineOffset, unsigned>(map, map.size(), pc - codeBlock->instructions().begin(), BytecodeAndMachineOffset::getBytecodeIndex);
ASSERT(mapping);
ASSERT(mapping->m_bytecodeIndex == static_cast<unsigned>(pc - codeBlock->instructions().begin()));
Modified: trunk/Source/_javascript_Core/profiler/ProfilerBytecodeSequence.cpp (137708 => 137709)
--- trunk/Source/_javascript_Core/profiler/ProfilerBytecodeSequence.cpp 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/_javascript_Core/profiler/ProfilerBytecodeSequence.cpp 2012-12-14 04:41:58 UTC (rev 137709)
@@ -64,7 +64,7 @@
unsigned BytecodeSequence::indexForBytecodeIndex(unsigned bytecodeIndex) const
{
- return binarySearch<Bytecode, unsigned, getBytecodeIndexForBytecode>(const_cast<Bytecode*>(m_sequence.begin()), m_sequence.size(), bytecodeIndex) - m_sequence.begin();
+ return binarySearch<Bytecode, unsigned>(m_sequence, m_sequence.size(), bytecodeIndex, getBytecodeIndexForBytecode) - m_sequence.begin();
}
const Bytecode& BytecodeSequence::forBytecodeIndex(unsigned bytecodeIndex) const
Modified: trunk/Source/WTF/ChangeLog (137708 => 137709)
--- trunk/Source/WTF/ChangeLog 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/WTF/ChangeLog 2012-12-14 04:41:58 UTC (rev 137709)
@@ -1,3 +1,31 @@
+2012-12-13 Filip Pizlo <[email protected]>
+
+ Attempt to rationalize and simplify WTF::binarySearch
+ https://bugs.webkit.org/show_bug.cgi?id=104890
+
+ Reviewed by Maciej Stachowiak.
+
+ Binary search now has three modes:
+
+ The default: assert that the key was found, but return an adjacent element if it
+ wasn't found, if asserts are turned off.
+
+ tryBinarySearch: return 0 if the key wasn't found.
+
+ approximateBinarySearch: if the key is not found, return an adjacent element (either
+ the left or right; no guarantee which).
+
+ This also reduces the number of variants of binarySearch. The functor variant is now
+ gone because binarySearch now always uses a functor for the key extractor. The
+ generic variant is now gone because binarySearch always expects an array type that
+ can do operator[].
+
+ * wtf/StdLibExtras.h:
+ (WTF::binarySearchImpl):
+ (WTF::binarySearch):
+ (WTF::tryBinarySearch):
+ (WTF::approximateBinarySearch):
+
2012-12-13 Ilya Tikhonovsky <[email protected]>
Web Inspector: Native Memory Instrumentation: do not validate pointers to objects in RenderArena agains tcmalloc data.
Modified: trunk/Source/WTF/wtf/StdLibExtras.h (137708 => 137709)
--- trunk/Source/WTF/wtf/StdLibExtras.h 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2012-12-14 04:41:58 UTC (rev 137709)
@@ -178,126 +178,86 @@
enum BinarySearchMode {
KeyMustBePresentInArray,
- KeyMustNotBePresentInArray
+ KeyMightNotBePresentInArray,
+ ReturnAdjacentElementIfKeyIsNotPresent
};
-// Binary search algorithm, calls extractKey on pre-sorted elements in array,
-// compares result with key (KeyTypes should be comparable with '==', and '<').
-template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*)>
-inline ArrayElementType* binarySearch(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
+template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
+inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
- // The array must contain at least one element (pre-condition, array does contain key).
- // If the array contains only one element, no need to do the comparison.
+ size_t offset = 0;
while (size > 1) {
- // Pick an element to check, half way through the array, and read the value.
int pos = (size - 1) >> 1;
- KeyType val = extractKey(&array[pos]);
-
- // If the key matches, success!
+ KeyType val = extractKey(&array[offset + pos]);
+
if (val == key)
- return &array[pos];
+ return &array[offset + pos];
// The item we are looking for is smaller than the item being check; reduce the value of 'size',
// chopping off the right hand half of the array.
- else if (key < val)
+ if (key < val)
size = pos;
// Discard all values in the left hand half of the array, up to and including the item at pos.
else {
size -= (pos + 1);
- array += (pos + 1);
+ offset += (pos + 1);
}
- // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
- if (mode == KeyMustBePresentInArray)
- ASSERT(size);
+ ASSERT(mode != KeyMustBePresentInArray || size);
}
+
+ if (mode == KeyMightNotBePresentInArray && !size)
+ return 0;
+
+ ArrayElementType* result = &array[offset];
- // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
- // we've chopped down to one element, no need to check it matches
+ if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
+ return 0;
+
if (mode == KeyMustBePresentInArray) {
ASSERT(size == 1);
- ASSERT(key == extractKey(&array[0]));
+ ASSERT(key == extractKey(result));
}
- return &array[0];
+ return result;
}
-// Modified binary search algorithm that uses a functor. Note that this is strictly
-// more powerful than the above, but results in somewhat less template specialization.
-// Hence, depending on inlining heuristics, it might be slower.
-template<typename ArrayElementType, typename KeyType, typename ExtractKey>
-inline ArrayElementType* binarySearchWithFunctor(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray, const ExtractKey& extractKey = ExtractKey())
+// 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())
{
- // The array must contain at least one element (pre-condition, array does contain key).
- // If the array contains only one element, no need to do the comparison.
- while (size > 1) {
- // Pick an element to check, half way through the array, and read the value.
- int pos = (size - 1) >> 1;
- KeyType val = extractKey(&array[pos]);
+ return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
+}
- // If the key matches, success!
- if (val == key)
- return &array[pos];
- // The item we are looking for is smaller than the item being check; reduce the value of 'size',
- // chopping off the right hand half of the array.
- else if (key < val)
- size = pos;
- // Discard all values in the left hand half of the array, up to and including the item at pos.
- else {
- size -= (pos + 1);
- array += (pos + 1);
- }
-
- // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
- if (mode == KeyMustBePresentInArray)
- ASSERT(size);
- }
-
- // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
- // we've chopped down to one element, no need to check it matches
- if (mode == KeyMustBePresentInArray) {
- ASSERT(size == 1);
- ASSERT(key == extractKey(&array[0]));
- }
-
- return &array[0];
+// 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())
+{
+ return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
}
-// Modified binarySearch() algorithm designed for array-like classes that support
-// operator[] but not operator+=. One example of a class that qualifies is
-// SegmentedVector.
-template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*), typename ArrayType>
-inline ArrayElementType* genericBinarySearch(ArrayType& array, size_t size, KeyType key)
+// 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 ExtractKey, typename ArrayType>
+inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
- // The array must contain at least one element (pre-condition, array does conatin key).
- // If the array only contains one element, no need to do the comparison.
- size_t offset = 0;
- while (size > 1) {
- // Pick an element to check, half way through the array, and read the value.
- int pos = (size - 1) >> 1;
- KeyType val = extractKey(&array[offset + pos]);
-
- // If the key matches, success!
- if (val == key)
- return &array[offset + pos];
- // The item we are looking for is smaller than the item being check; reduce the value of 'size',
- // chopping off the right hand half of the array.
- if (key < val)
- size = pos;
- // Discard all values in the left hand half of the array, up to and including the item at pos.
- else {
- size -= (pos + 1);
- offset += (pos + 1);
- }
+ return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
+}
- // 'size' should never reach zero.
- ASSERT(size);
- }
-
- // If we reach this point we've chopped down to one element, no need to check it matches
- ASSERT(size == 1);
- ASSERT(key == extractKey(&array[offset]));
- return &array[offset];
+// 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())
+{
+ 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())
+{
+ return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
+}
+template<typename ArrayElementType, typename KeyType, typename ExtractKey, typename ArrayType>
+inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
+{
+ return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
+}
} // namespace WTF
@@ -314,6 +274,8 @@
using WTF::isPointerAligned;
using WTF::is8ByteAligned;
using WTF::binarySearch;
+using WTF::tryBinarySearch;
+using WTF::approximateBinarySearch;
using WTF::bitwise_cast;
using WTF::safeCast;
Modified: trunk/Source/WebCore/ChangeLog (137708 => 137709)
--- trunk/Source/WebCore/ChangeLog 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/WebCore/ChangeLog 2012-12-14 04:41:58 UTC (rev 137709)
@@ -1,3 +1,15 @@
+2012-12-13 Filip Pizlo <[email protected]>
+
+ Attempt to rationalize and simplify WTF::binarySearch
+ https://bugs.webkit.org/show_bug.cgi?id=104890
+
+ Reviewed by Maciej Stachowiak.
+
+ Switch to using the new binarySearch() API. No change in behavior, so no new tests.
+
+ * svg/animation/SVGSMILElement.cpp:
+ (WebCore::SVGSMILElement::findInstanceTime):
+
2012-12-13 Takashi Sakamoto <[email protected]>
[Shadow DOM]: scoped styles are not applied in the cascade order.
Modified: trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp (137708 => 137709)
--- trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2012-12-14 04:40:47 UTC (rev 137708)
+++ trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2012-12-14 04:41:58 UTC (rev 137709)
@@ -742,7 +742,7 @@
if (!sizeOfList)
return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
- const SMILTimeWithOrigin* result = binarySearch<const SMILTimeWithOrigin, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime, WTF::KeyMustNotBePresentInArray);
+ const SMILTimeWithOrigin* result = approximateBinarySearch<const SMILTimeWithOrigin, SMILTime>(list, sizeOfList, minimumTime, extractTimeFromVector);
int indexOfResult = result - list.begin();
ASSERT(indexOfResult < sizeOfList);
const SMILTime& currentTime = list[indexOfResult].time();
