Changeset 179510 in webkit


Ignore:
Timestamp:
Feb 2, 2015 3:53:26 PM (9 years ago)
Author:
Alan Bujtas
Message:

Simple line layout: use std::upper_bound in splitFragmentToFitLine()
https://bugs.webkit.org/show_bug.cgi?id=141146

Reviewed by Antti Koivisto.

Replace the custom binary search implementation with std::upper_bound and
move splitting functionality to TextFragment.

No change in functionality.

  • rendering/SimpleLineLayout.cpp:

(WebCore::SimpleLineLayout::FragmentForwardIterator::FragmentForwardIterator):
(WebCore::SimpleLineLayout::FragmentForwardIterator::operator++):
(WebCore::SimpleLineLayout::FragmentForwardIterator::operator!=):
(WebCore::SimpleLineLayout::FragmentForwardIterator::operator*):
(WebCore::SimpleLineLayout::begin):
(WebCore::SimpleLineLayout::end):
(WebCore::SimpleLineLayout::splitFragmentToFitLine):

  • rendering/SimpleLineLayoutFlowContentsIterator.cpp:

(WebCore::SimpleLineLayout::FlowContentsIterator::runWidth):

  • rendering/SimpleLineLayoutFlowContentsIterator.h:

(WebCore::SimpleLineLayout::FlowContentsIterator::TextFragment::split):

Location:
trunk/Source/WebCore
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r179500 r179510  
     12015-02-02  Zalan Bujtas  <zalan@apple.com>
     2
     3        Simple line layout: use std::upper_bound in splitFragmentToFitLine()
     4        https://bugs.webkit.org/show_bug.cgi?id=141146
     5
     6        Reviewed by Antti Koivisto.
     7
     8        Replace the custom binary search implementation with std::upper_bound and
     9        move splitting functionality to TextFragment.
     10
     11        No change in functionality.
     12
     13        * rendering/SimpleLineLayout.cpp:
     14        (WebCore::SimpleLineLayout::FragmentForwardIterator::FragmentForwardIterator):
     15        (WebCore::SimpleLineLayout::FragmentForwardIterator::operator++):
     16        (WebCore::SimpleLineLayout::FragmentForwardIterator::operator!=):
     17        (WebCore::SimpleLineLayout::FragmentForwardIterator::operator*):
     18        (WebCore::SimpleLineLayout::begin):
     19        (WebCore::SimpleLineLayout::end):
     20        (WebCore::SimpleLineLayout::splitFragmentToFitLine):
     21        * rendering/SimpleLineLayoutFlowContentsIterator.cpp:
     22        (WebCore::SimpleLineLayout::FlowContentsIterator::runWidth):
     23        * rendering/SimpleLineLayoutFlowContentsIterator.h:
     24        (WebCore::SimpleLineLayout::FlowContentsIterator::TextFragment::split):
     25
    1262015-02-02  Geoffrey Garen  <ggaren@apple.com>
    227
  • trunk/Source/WebCore/rendering/SimpleLineLayout.cpp

    r179444 r179510  
    298298};
    299299
     300class FragmentForwardIterator : public std::iterator<std::forward_iterator_tag, unsigned> {
     301public:
     302    FragmentForwardIterator(unsigned fragmentIndex)
     303        : m_fragmentIndex(fragmentIndex)
     304    {
     305    }
     306
     307    FragmentForwardIterator& operator++()
     308    {
     309        ++m_fragmentIndex;
     310        return *this;
     311    }
     312
     313    bool operator!=(const FragmentForwardIterator& other) const { return m_fragmentIndex != other.m_fragmentIndex; }
     314    unsigned operator*() const { return m_fragmentIndex; }
     315
     316private:
     317    unsigned m_fragmentIndex { 0 };
     318};
     319
     320static FragmentForwardIterator begin(const FlowContentsIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.start()); }
     321static FragmentForwardIterator end(const FlowContentsIterator::TextFragment& fragment)  { return FragmentForwardIterator(fragment.end()); }
     322
    300323static bool preWrap(const FlowContentsIterator::Style& style)
    301324{
     
    331354static FlowContentsIterator::TextFragment splitFragmentToFitLine(FlowContentsIterator::TextFragment& fragmentToSplit, float availableWidth, bool keepAtLeastOneCharacter, const FlowContentsIterator& flowContentsIterator)
    332355{
    333     // Fast path for single char fragments.
    334     if (fragmentToSplit.start() + 1 == fragmentToSplit.end()) {
    335         if (keepAtLeastOneCharacter)
    336             return FlowContentsIterator::TextFragment();
    337 
    338         FlowContentsIterator::TextFragment fragmentForNextLine(fragmentToSplit);
    339         // Make it empty fragment.
    340         fragmentToSplit = FlowContentsIterator::TextFragment(fragmentToSplit.start(), fragmentToSplit.start(), 0, fragmentToSplit.type());
    341         return fragmentForNextLine;
    342     }
    343     // Simple binary search to find out what fits the current line.
    344356    // FIXME: add surrogate pair support.
    345     unsigned left = fragmentToSplit.start();
    346     unsigned right = fragmentToSplit.end() - 1; // We can ignore the last character. It surely does not fit.
    347     float width = 0;
    348     while (left < right) {
    349         unsigned middle = (left + right) / 2;
    350         width = flowContentsIterator.textWidth(fragmentToSplit.start(), middle + 1, 0);
    351         if (availableWidth > width)
    352             left = middle + 1;
    353         else if (availableWidth < width)
    354             right = middle;
    355         else {
    356             right = middle + 1;
    357             break;
    358         }
    359     }
    360 
    361     if (keepAtLeastOneCharacter && right == fragmentToSplit.start())
    362         ++right;
    363 
    364     // Fragment for next line.
    365     unsigned nextLineStart = right;
    366     unsigned nextLineEnd = fragmentToSplit.end();
    367     float nextLineWidth = flowContentsIterator.textWidth(nextLineStart, nextLineEnd, 0);
    368 
    369     unsigned thisLineStart = fragmentToSplit.start();
    370     unsigned thisLineEnd = right;
    371     ASSERT(thisLineStart <= thisLineEnd);
    372     float thisLineWidth = thisLineStart < thisLineEnd ? flowContentsIterator.textWidth(thisLineStart, thisLineEnd, 0) : 0;
    373     fragmentToSplit = FlowContentsIterator::TextFragment(thisLineStart, thisLineEnd, thisLineWidth, fragmentToSplit.type(), fragmentToSplit.isCollapsed(), fragmentToSplit.isBreakable());
    374     return FlowContentsIterator::TextFragment(nextLineStart, nextLineEnd, nextLineWidth, fragmentToSplit.type(), fragmentToSplit.isCollapsed(), fragmentToSplit.isBreakable());
     357    unsigned start = fragmentToSplit.start();
     358    auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&flowContentsIterator, start](float availableWidth, unsigned index) {
     359        // FIXME: use the actual left position of the line (instead of 0) to calculated width. It might give false width for tab characters.
     360        return availableWidth < flowContentsIterator.textWidth(start, index + 1, 0);
     361    });
     362    unsigned splitPosition = (*it);
     363    if (keepAtLeastOneCharacter && splitPosition == fragmentToSplit.start())
     364        ++splitPosition;
     365    return fragmentToSplit.split(splitPosition, flowContentsIterator);
    375366}
    376367
  • trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.cpp

    r179438 r179510  
    172172float FlowContentsIterator::runWidth(const String& text, unsigned from, unsigned to, float xPosition) const
    173173{
    174     ASSERT(from < to);
     174    ASSERT(from <= to);
     175    if (from == to)
     176        return 0;
    175177    bool measureWithEndSpace = m_style.collapseWhitespace && to < text.length() && text[to] == ' ';
    176178    if (measureWithEndSpace)
  • trunk/Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h

    r179438 r179510  
    6060        bool isCollapsed() const { return m_isCollapsed; }
    6161        bool isBreakable() const { return m_isBreakable; }
     62
    6263        bool isEmpty() const { return start() == end(); }
     64        TextFragment split(unsigned splitPosition, const FlowContentsIterator&);
    6365
    6466    private:
     
    104106};
    105107
     108inline FlowContentsIterator::TextFragment FlowContentsIterator::TextFragment::split(unsigned splitPosition, const FlowContentsIterator& flowContentsIterator)
     109{
     110    auto updateFragmentProperties = [&flowContentsIterator] (TextFragment& fragment)
     111    {
     112        fragment.m_width = 0;
     113        if (fragment.start() != fragment.end())
     114            fragment.m_width = flowContentsIterator.textWidth(fragment.start(), fragment.end(), 0);
     115        if (fragment.start() + 1 > fragment.end())
     116            return;
     117        fragment.m_isCollapsed = false;
     118        fragment.m_isBreakable = false;
     119    };
     120
     121    TextFragment newFragment(*this);
     122    m_end = splitPosition;
     123    updateFragmentProperties(*this);
     124
     125    newFragment.m_start = splitPosition;
     126    updateFragmentProperties(newFragment);
     127    return newFragment;
     128}
     129
    106130inline UChar FlowContentsIterator::characterAt(unsigned position) const
    107131{
Note: See TracChangeset for help on using the changeset viewer.