Modified: branches/safari-537-branch/Source/WTF/ChangeLog (152467 => 152468)
--- branches/safari-537-branch/Source/WTF/ChangeLog 2013-07-08 22:57:27 UTC (rev 152467)
+++ branches/safari-537-branch/Source/WTF/ChangeLog 2013-07-08 23:02:14 UTC (rev 152468)
@@ -1,3 +1,26 @@
+2013-07-08 Lucas Forschler <[email protected]>
+
+ Merge r152306
+
+ 2013-07-02 Geoffrey Garen <[email protected]>
+
+ plainText() is O(N^2)
+ https://bugs.webkit.org/show_bug.cgi?id=118282
+ <rdar://problem/14284360>
+
+ Reviewed by Alexey Proskuryakov.
+
+ * wtf/text/StringBuilder.cpp:
+ (WTF::expandCapacity): Factored out this helper function to simplify
+ some code that was duplicated in four places.
+
+ (WTF::StringBuilder::appendUninitializedSlow):
+ (WTF::StringBuilder::append): Use expandCapacity(). One of the cases
+ was not doing anything special, and so was O(N^2).
+
+ Also, always call expandCapacity() it in a standard way, calling
+ capacity() first, so it's easy to tell at a glance that you got it right.
+
2013-06-27 Lucas Forschler <[email protected]>
Merge r152038
Modified: branches/safari-537-branch/Source/WTF/wtf/text/StringBuilder.cpp (152467 => 152468)
--- branches/safari-537-branch/Source/WTF/wtf/text/StringBuilder.cpp 2013-07-08 22:57:27 UTC (rev 152467)
+++ branches/safari-537-branch/Source/WTF/wtf/text/StringBuilder.cpp 2013-07-08 23:02:14 UTC (rev 152468)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2010 Apple Inc. All rights reserved.
+ * Copyright (C) 2010, 2013 Apple Inc. All rights reserved.
* Copyright (C) 2012 Google Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -32,7 +32,11 @@
namespace WTF {
-static const unsigned minimumCapacity = 16;
+static size_t expandedCapacity(size_t capacity, size_t newLength)
+{
+ static const size_t minimumCapacity = 16;
+ return std::max(capacity, std::max(minimumCapacity, newLength * 2));
+}
void StringBuilder::reifyString() const
{
@@ -224,10 +228,10 @@
// If the buffer is valid it must be at least as long as the current builder contents!
ASSERT(m_buffer->length() >= m_length);
- reallocateBuffer<CharType>(std::max(requiredLength, std::max(minimumCapacity, m_buffer->length() * 2)));
+ reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
} else {
ASSERT(m_string.length() == m_length);
- allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
+ allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
}
CharType* result = getBufferCharacters<CharType>() + m_length;
@@ -259,10 +263,10 @@
// If the buffer is valid it must be at least as long as the current builder contents!
ASSERT(m_buffer->length() >= m_length);
- allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
+ allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
} else {
ASSERT(m_string.length() == m_length);
- allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
+ allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
}
memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));
Modified: branches/safari-537-branch/Source/WebCore/ChangeLog (152467 => 152468)
--- branches/safari-537-branch/Source/WebCore/ChangeLog 2013-07-08 22:57:27 UTC (rev 152467)
+++ branches/safari-537-branch/Source/WebCore/ChangeLog 2013-07-08 23:02:14 UTC (rev 152468)
@@ -1,5 +1,22 @@
2013-07-08 Lucas Forschler <[email protected]>
+ Merge r152306
+
+ 2013-07-02 Geoffrey Garen <[email protected]>
+
+ plainText() is O(N^2)
+ https://bugs.webkit.org/show_bug.cgi?id=118282
+ <rdar://problem/14284360>
+
+ Reviewed by Alexey Proskuryakov.
+
+ * editing/TextIterator.cpp:
+ (WebCore::plainText): Linear growth for a vector data type is O(N^2).
+ Don't do that. Luckily, StringBuilder does the right thing automatically,
+ so we can just delete code.
+
+2013-07-08 Lucas Forschler <[email protected]>
+
Merge r151737
2013-06-19 Robert Hogan <[email protected]>
Modified: branches/safari-537-branch/Source/WebCore/editing/TextIterator.cpp (152467 => 152468)
--- branches/safari-537-branch/Source/WebCore/editing/TextIterator.cpp 2013-07-08 22:57:27 UTC (rev 152467)
+++ branches/safari-537-branch/Source/WebCore/editing/TextIterator.cpp 2013-07-08 23:02:14 UTC (rev 152468)
@@ -2500,19 +2500,16 @@
String plainText(const Range* r, TextIteratorBehavior defaultBehavior, bool isDisplayString)
{
// The initial buffer size can be critical for performance: https://bugs.webkit.org/show_bug.cgi?id=81192
- static const unsigned cMaxSegmentSize = 1 << 15;
+ static const unsigned initialCapacity = 1 << 15;
unsigned bufferLength = 0;
StringBuilder builder;
- builder.reserveCapacity(cMaxSegmentSize);
+ builder.reserveCapacity(initialCapacity);
TextIteratorBehavior behavior = defaultBehavior;
if (!isDisplayString)
behavior = static_cast<TextIteratorBehavior>(behavior | TextIteratorEmitsTextsWithoutTranscoding);
for (TextIterator it(r, behavior); !it.atEnd(); it.advance()) {
- if (builder.capacity() < builder.length() + it.length())
- builder.reserveCapacity(builder.capacity() + cMaxSegmentSize);
-
it.appendTextToStringBuilder(builder);
bufferLength += it.length();
}
