addMarker() optimizations.

Source/core/dom/DocumentMarkerController.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  *           (C) 2006 Alexey Proskuryakov (ap@webkit.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
@@ skipping 22 matching lines @@
 #include "core/dom/RenderedDocumentMarker.h"
 #include "core/editing/TextIterator.h"
 #include "core/rendering/RenderObject.h"
 
 #ifndef NDEBUG
 #include <stdio.h>
 #endif
 
 namespace WebCore {
 
+namespace {
+
+DocumentMarker::MarkerTypeIndex MarkerTypeToMarkerIndex(DocumentMarker::MarkerType type)
+{
+    switch (type) {
+    default:
+    case DocumentMarker::Spelling:
+        return DocumentMarker::SpellingMarkerIndex;
+    case DocumentMarker::Grammar:
+        return DocumentMarker::GramarMarkerIndex;
+    case DocumentMarker::TextMatch:
+        return DocumentMarker::TextMatchMarkerIndex;
+    }
+}
+
+} // namespace
+
 inline bool DocumentMarkerController::possiblyHasMarkers(DocumentMarker::MarkerTypes types)
 {
     return m_possiblyExistingMarkerTypes.intersects(types);
 }
 
 DocumentMarkerController::DocumentMarkerController()
     : m_possiblyExistingMarkerTypes(0)
 {
 }
 
@@ skipping 73 matching lines @@
             return;
         ASSERT(!m_markers.isEmpty());
 
         RefPtr<Range> textPiece = markedText.range();
         int startOffset = textPiece->startOffset();
         int endOffset = textPiece->endOffset();
         removeMarkers(textPiece->startContainer(), startOffset, endOffset - startOffset, markerTypes, shouldRemovePartiallyOverlappingMarker);
     }
 }
 
+static bool startsFurther(const DocumentMarker& lhv, const DocumentMarker& rhv)
+{
+    return lhv.startOffset() < rhv.startOffset();
+}
+
+static bool doesNotOverlap(const DocumentMarker& lhv, const DocumentMarker& rhv)
+{
+    return lhv.endOffset() < rhv.startOffset();
+}
+
 // Markers are stored in order sorted by their start offset.
 // Markers of the same type do not overlap each other.
 
 void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMarker)
 {
     ASSERT(newMarker.endOffset() >= newMarker.startOffset());
     if (newMarker.endOffset() == newMarker.startOffset())
         return;
 
     m_possiblyExistingMarkerTypes.add(newMarker.type());
 
-    OwnPtr<MarkerList>& list = m_markers.add(node, nullptr).iterator->value;
-
-    if (!list) {
-        list = adoptPtr(new MarkerList);
+    OwnPtr<MarkerLists>& markers = m_markers.add(node, nullptr).iterator->value;
+    if (!markers) {
+        markers = adoptPtr(new MarkerLists);
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {

[groby-ooo-7-16, 2013/09/19 18:17:09]

I'd suggest only adding a MarkerList for the needed index.

[pstanek, 2013/09/21 21:09:59]

Done.

+            markers->insert(markerListIndex, adoptPtr(new MarkerList));
+        }
+    }
+    OwnPtr<MarkerList>& list = markers->at(MarkerTypeToMarkerIndex(newMarker.type()));
+    if (list->isEmpty()) {
         list->append(RenderedDocumentMarker(newMarker));
     } else {
         RenderedDocumentMarker toInsert(newMarker);
-        size_t numMarkers = list->size();
-        size_t i;
-        // Iterate over all markers whose start offset is less than or equal to the new marker's.
-        // If one of them is of the same type as the new marker and touches it or intersects with it
-        // (there is at most one), remove it and adjust the new marker's start offset to encompass it.
-        for (i = 0; i < numMarkers; ++i) {
-            DocumentMarker marker = list->at(i);
-            if (marker.startOffset() > toInsert.startOffset())
-                break;
-            if (marker.type() == toInsert.type() && marker.type() != DocumentMarker::TextMatch && marker.endOffset() >= toInsert.startOffset()) {
-                toInsert.setStartOffset(marker.startOffset());
-                list->remove(i);
-                numMarkers--;
-                break;
+        if (list->last().endOffset() >= newMarker.startOffset()) {
+            if (toInsert.type() != DocumentMarker::TextMatch) {
+                mergeOverlapping(list.get(), toInsert);
+            } else {
+                MarkerList::iterator pos = std::lower_bound(list->begin(), list->end(), toInsert, startsFurther);
+                list->insert(pos - list->begin(), RenderedDocumentMarker(toInsert));
             }
+        } else {
+            list->append(RenderedDocumentMarker(toInsert));

[groby-ooo-7-16, 2013/09/19 18:17:09]

I'd combine that into the list->empty branch() i.e. 
if( list->isEmpty() || list->last().endOffset() >= newMarker.startOffset()) {
  list->append...

[pstanek, 2013/09/21 21:09:59]

Done.

         }
-        size_t j = i;
-        // Iterate over all markers whose end offset is less than or equal to the new marker's,
-        // removing markers of the same type as the new marker which touch it or intersect with it,
-        // adjusting the new marker's end offset to cover them if necessary.
-        while (j < numMarkers) {
-            DocumentMarker marker = list->at(j);
-            if (marker.startOffset() > toInsert.endOffset())
-                break;
-            if (marker.type() == toInsert.type() && marker.type() != DocumentMarker::TextMatch) {
-                list->remove(j);
-                if (toInsert.endOffset() <= marker.endOffset()) {
-                    toInsert.setEndOffset(marker.endOffset());
-                    break;
-                }
-                numMarkers--;
-            } else
-                j++;
-        }
-        // At this point i points to the node before which we want to insert.
-        list->insert(i, RenderedDocumentMarker(toInsert));
     }
 

[groby-ooo-7-16, 2013/09/19 18:17:09]

Side note: I'm surprised this doesn't set docDirty

     // repaint the affected node
     if (node->renderer())
         node->renderer()->repaint();
 }
 
+void DocumentMarkerController::mergeOverlapping(MarkerList* list, DocumentMarker& toInsert)
+{
+    // Iterate over all markers whose start offset is less than or equal to the new marker's.
+    // If one of them is of the same type as the new marker and touches it or intersects with it
+    // (there is at most one), remove it and adjust the new marker's start offset to encompass it.
+    MarkerList::iterator firstOverlapping = list->begin();

[groby-ooo-7-16, 2013/09/19 18:17:09]

I think this can now be simplified significantly. Since we know all markers for
a given type are merged, we're sorted by startOffset AND endOffset

So I think this would work:

* find lower bound for toInsert.start < node.end - all nodes that potentially
need merging come after that point
* insert toInsert at that point
* keep merging until merged.end < node.start

If you want to be more efficient, determine if the node after the insertion
point overlaps with toInsert at all. If it doesn't, insert and be done. If it
does, merge that node in place with toInsert, then continue merging right. (That
means one insertion less in the merge case, and with that, one bulk element move
less)

This should result in _much_ shorter code

[pstanek, 2013/09/21 21:09:59]

Done.

+    size_t offset = 0;
+    do {
+        firstOverlapping = std::lower_bound(firstOverlapping + offset, list->end(), toInsert, doesNotOverlap);
+        offset = 1;
+    } while (firstOverlapping != list->end() && firstOverlapping->type() != toInsert.type());
+
+    size_t index = firstOverlapping - list->begin();
+    list->insert(index, RenderedDocumentMarker(toInsert));
+    MarkerList::iterator inserted = firstOverlapping;
+    ++firstOverlapping;
+    if (firstOverlapping != list->end() && !startsFurther(*inserted, *firstOverlapping)) {
+        inserted->setStartOffset(firstOverlapping->startOffset());
+        list->remove(firstOverlapping - list->begin());
+    }
+
+    // Iterate over all markers whose end offset is less than or equal to the new marker's.
+    // If one of them is of the same type as the new marker and touches it or intersects with it
+    // adjust the new marker's end offset to cover it if necessary.
+    for (MarkerList::iterator i = inserted + 1; i != list->end(); ) {
+        if (i->startOffset() > inserted->endOffset())
+            break;
+        list->remove(i - list->begin());
+        if (inserted->endOffset() <= i->endOffset()) {
+            inserted->setEndOffset(i->endOffset());
+            break;
+        }
+    }
+}
+
 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies.  The shift is
 // useful if, e.g., the caller has created the dstNode from a non-prefix substring of the srcNode.
 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta)
 {
     if (length <= 0)
         return;
 
     if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
         return;
     ASSERT(!m_markers.isEmpty());
 
-    MarkerList* list = m_markers.get(srcNode);
-    if (!list)
+    MarkerLists* markers = m_markers.get(srcNode);
+    if (!markers)
         return;
 
     bool docDirty = false;
-    unsigned endOffset = startOffset + length - 1;
-    for (size_t i = 0; i != list->size(); ++i) {
-        DocumentMarker marker = list->at(i);
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
 
-        // stop if we are now past the specified range
-        if (marker.startOffset() > endOffset)
-            break;
+        unsigned endOffset = startOffset + length - 1;
+        for (size_t i = 0; i != list->size(); ++i) {
+            DocumentMarker marker = list->at(i);
 
-        // skip marker that is before the specified range or is the wrong type
-        if (marker.endOffset() < startOffset)
-            continue;
+            // stop if we are now past the specified range
+            if (marker.startOffset() > endOffset)
+                break;
 
-        // pin the marker to the specified range and apply the shift delta
-        docDirty = true;
-        if (marker.startOffset() < startOffset)
-            marker.setStartOffset(startOffset);
-        if (marker.endOffset() > endOffset)
-            marker.setEndOffset(endOffset);
-        marker.shiftOffsets(delta);
+            // skip marker that is before the specified range
+            if (marker.endOffset() < startOffset)

[groby-ooo-7-16, 2013/09/19 18:17:09]

We can lower_bound this.

[pstanek, 2013/09/21 21:09:59]

Done.

+                continue;
 
-        addMarker(dstNode, marker);
+            // pin the marker to the specified range and apply the shift delta
+            docDirty = true;
+            if (marker.startOffset() < startOffset)
+                marker.setStartOffset(startOffset);
+            if (marker.endOffset() > endOffset)
+                marker.setEndOffset(endOffset);
+            marker.shiftOffsets(delta);
+
+            addMarker(dstNode, marker);
+        }
     }
 
     // repaint the affected node
     if (docDirty && dstNode->renderer())
         dstNode->renderer()->repaint();
 }
 
 void DocumentMarkerController::removeMarkers(Node* node, unsigned startOffset, int length, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
 {
     if (length <= 0)
         return;
 
     if (!possiblyHasMarkers(markerTypes))
         return;
     ASSERT(!(m_markers.isEmpty()));
 
-    MarkerList* list = m_markers.get(node);
-    if (!list)
+    MarkerLists* markers = m_markers.get(node);
+    if (!markers)
         return;
 
     bool docDirty = false;
-    unsigned endOffset = startOffset + length;
-    for (size_t i = 0; i < list->size();) {
-        DocumentMarker marker = list->at(i);
-
-        // markers are returned in order, so stop if we are now past the specified range
-        if (marker.startOffset() >= endOffset)
-            break;
-
-        // skip marker that is wrong type or before target
-        if (marker.endOffset() <= startOffset || !markerTypes.contains(marker.type())) {
-            i++;
+    size_t emptyListsCount = 0;
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+        if (list->isEmpty()) {
+            ++emptyListsCount;
             continue;
         }
+        if (!markerTypes.contains(list->begin()->type())) {

[groby-ooo-7-16, 2013/09/19 18:17:09]

Personal nit: No need for curlies on single-line branches.

[pstanek, 2013/09/21 21:09:59]

Done.

+            continue;
+        }
+        unsigned endOffset = startOffset + length;
+        for (size_t i = 0; i < list->size();) {
+            DocumentMarker marker = list->at(i);
 
-        // at this point we know that marker and target intersect in some way
-        docDirty = true;
+            // markers are returned in order, so stop if we are now past the specified range
+            if (marker.startOffset() >= endOffset)
+                break;
 
-        // pitch the old marker
-        list->remove(i);
+            // skip marker that is before target
+            if (marker.endOffset() <= startOffset) {

[groby-ooo-7-16, 2013/09/19 18:17:09]

I suppose we could upper_bound this, saving us iteration.

[pstanek, 2013/09/21 21:09:59]

Done.

+                i++;
+                continue;
+            }
 
-        if (shouldRemovePartiallyOverlappingMarker)
-            // Stop here. Don't add resulting slices back.
-            continue;
+            // at this point we know that marker and target intersect in some way
+            docDirty = true;
 
-        // add either of the resulting slices that are left after removing target
-        if (startOffset > marker.startOffset()) {
-            DocumentMarker newLeft = marker;
-            newLeft.setEndOffset(startOffset);
-            list->insert(i, RenderedDocumentMarker(newLeft));
-            // i now points to the newly-inserted node, but we want to skip that one
-            i++;
-        }
-        if (marker.endOffset() > endOffset) {
-            DocumentMarker newRight = marker;
-            newRight.setStartOffset(endOffset);
-            list->insert(i, RenderedDocumentMarker(newRight));
-            // i now points to the newly-inserted node, but we want to skip that one
-            i++;
+            // pitch the old marker
+            list->remove(i);
+
+            if (shouldRemovePartiallyOverlappingMarker) {
+                // Stop here. Don't add resulting slices back.
+                continue;
+            }
+
+            // add either of the resulting slices that are left after removing target
+            if (startOffset > marker.startOffset()) {
+                DocumentMarker newLeft = marker;
+                newLeft.setEndOffset(startOffset);
+                list->insert(i, RenderedDocumentMarker(newLeft));
+                // i now points to the newly-inserted node, but we want to skip that one
+                i++;
+            }
+            if (marker.endOffset() > endOffset) {
+                DocumentMarker newRight = marker;
+                newRight.setStartOffset(endOffset);
+                list->insert(i, RenderedDocumentMarker(newRight));
+                // i now points to the newly-inserted node, but we want to skip that one
+                i++;
+            }
         }
     }
 
-    if (list->isEmpty()) {
+    if (emptyListsCount == DocumentMarker::MarkerTypeIndexesCount) {

[groby-ooo-7-16, 2013/09/19 18:17:09]

If we do ad-hoc creation for individual lists, we need to add the list->isEmpty
check back, too.

[pstanek, 2013/09/21 21:09:59]

Done.

         m_markers.remove(node);
         if (m_markers.isEmpty())
             m_possiblyExistingMarkerTypes = 0;
     }
 
     // repaint the affected node
     if (docDirty && node->renderer())
         node->renderer()->repaint();
 }
 
 DocumentMarker* DocumentMarkerController::markerContainingPoint(const LayoutPoint& point, DocumentMarker::MarkerType markerType)
 {
     if (!possiblyHasMarkers(markerType))
         return 0;
     ASSERT(!(m_markers.isEmpty()));
 
     // outer loop: process each node that contains any markers
     MarkerMap::iterator end = m_markers.end();
     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
         // inner loop; process each marker in this node
-        MarkerList* list = nodeIterator->value.get();
+        MarkerLists* markers = nodeIterator->value.get();
+        OwnPtr<MarkerList>& list = (*markers)[MarkerTypeToMarkerIndex(markerType)];
         unsigned markerCount = list->size();
         for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
             RenderedDocumentMarker& marker = list->at(markerIndex);
 
-            // skip marker that is wrong type
-            if (marker.type() != markerType)
-                continue;
-
             if (marker.contains(point))
                 return &marker;
         }
     }
 
     return 0;
 }
 
 Vector<DocumentMarker*> DocumentMarkerController::markersFor(Node* node, DocumentMarker::MarkerTypes markerTypes)
 {
     Vector<DocumentMarker*> result;
-    MarkerList* list = m_markers.get(node);
-    if (!list)
+
+    MarkerLists* markers = m_markers.get(node);
+    if (!markers)
         return result;
 
-    for (size_t i = 0; i < list->size(); ++i) {
-        if (markerTypes.contains(list->at(i).type()))
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+        if (list->isEmpty() || !markerTypes.contains(list->begin()->type()))
+            continue;
+
+        for (size_t i = 0; i < list->size(); ++i) {

[groby-ooo-7-16, 2013/09/19 18:17:09]

nit: no curlies on single-line statements.

[pstanek, 2013/09/21 21:09:59]

Done.

             result.append(&(list->at(i)));
+        }
     }
 
     return result;
 }
 
 Vector<DocumentMarker*> DocumentMarkerController::markers()

[groby-ooo-7-16, 2013/09/19 18:17:09]

I'm wondering if the callers of this expect the markers' sort order to be across
types. 

[pstanek, 2013/09/20 15:07:40]

Good point. it seems they has to.

[groby-ooo-7-16, 2013/09/20 15:35:58]

A quick code search actually reveals no callers? 

On 2013/09/20 15:07:40, pstanek wrote:

[pstanek, 2013/09/21 21:09:59]

Done.

 {
     Vector<DocumentMarker*> result;
     for (MarkerMap::iterator i = m_markers.begin(); i != m_markers.end(); ++i) {
-        for (size_t j = 0; j < i->value->size(); ++j)
-            result.append(&(i->value->at(j)));
+        MarkerLists* markers = i->value.get();
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+            OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+            for (size_t j = 0; j < list->size(); ++j)

[groby-ooo-7-16, 2013/09/19 18:17:09]

I believe Vector has appendVector, which does just what this loop does.

[pstanek, 2013/09/20 15:07:40]

Type mismatch. MarkerList is Vector<DocumentMarker> where the result is
Vector<DocumentMarker*>.

+                result.append(&(list->at(j)));
+        }
     }
     return result;
 }
 
 Vector<DocumentMarker*> DocumentMarkerController::markersInRange(Range* range, DocumentMarker::MarkerTypes markerTypes)

[groby-ooo-7-16, 2013/09/19 18:17:09]

Same as above: Do they need to be sorted?

[groby-ooo-7-16, 2013/09/20 15:35:58]

WebFrameImpl::replaceMisspelledRange does - but maybe you'd want the sort there.
SpellCheckRequest::create _might_ need that. Probably not, but ping rouslan.
(Actually, just checked - it doesn't)
And HitTestResult::isMisspelled pains me because it doesn't - all it wants to
know if there's _any_ marker in the range. Expensive way to test :)

On 2013/09/19 18:17:09, groby wrote:

[pstanek, 2013/09/21 21:09:59]

Done.

 {
     if (!possiblyHasMarkers(markerTypes))
         return Vector<DocumentMarker*>();
 
     Vector<DocumentMarker*> foundMarkers;
 
     Node* startContainer = range->startContainer();
     ASSERT(startContainer);
     Node* endContainer = range->endContainer();
     ASSERT(endContainer);
 
     Node* pastLastNode = range->pastLastNode();
     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(node)) {
         Vector<DocumentMarker*> markers = markersFor(node);
         Vector<DocumentMarker*>::const_iterator end = markers.end();
         for (Vector<DocumentMarker*>::const_iterator it = markers.begin(); it != end; ++it) {
             DocumentMarker* marker = *it;
             if (!markerTypes.contains(marker->type()))
                 continue;
             if (node == startContainer && marker->endOffset() <= static_cast<unsigned>(range->startOffset()))

[groby-ooo-7-16, 2013/09/19 18:17:09]

I suppose we could do a lower bounds check and just use appendRange, that'd
simplify this function.

[pstanek, 2013/09/20 15:07:40]

This calls makersFor() returning one vector with all markers so it'd have to
rewritten completely.

[groby-ooo-7-16, 2013/09/20 15:35:58]

Yes, that's why I suggested filing those as separate bugs :)

markersFor is an interesting beast anyways - it seems most calls to it want only
a range of markers, so that should be part of the API... As I said, it's better
off separate.

On 2013/09/20 15:07:40, pstanek wrote:

                 continue;
             if (node == endContainer && marker->startOffset() >= static_cast<unsigned>(range->endOffset()))
                 continue;
             foundMarkers.append(marker);
         }
     }
     return foundMarkers;
 }
 
 Vector<IntRect> DocumentMarkerController::renderedRectsForMarkers(DocumentMarker::MarkerType markerType)
 {
     Vector<IntRect> result;
 
     if (!possiblyHasMarkers(markerType))
         return result;
     ASSERT(!(m_markers.isEmpty()));
 
     // outer loop: process each node
     MarkerMap::iterator end = m_markers.end();
     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
         // inner loop; process each marker in this node
-        MarkerList* list = nodeIterator->value.get();
-        unsigned markerCount = list->size();
-        for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
-            const RenderedDocumentMarker& marker = list->at(markerIndex);
+        MarkerLists* markers = nodeIterator->value.get();
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+            OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+            if (list->isEmpty() || list->begin()->type() != markerType)
+                continue;
+            for (unsigned markerIndex = 0; markerIndex < list->size(); ++markerIndex) {
+                const RenderedDocumentMarker& marker = list->at(markerIndex);
 
-            // skip marker that is wrong type
-            if (marker.type() != markerType)
-                continue;
+                if (!marker.isRendered())
+                    continue;
 
-            if (!marker.isRendered())
-                continue;
-
-            result.append(marker.renderedRect());
+                result.append(marker.renderedRect());
+            }
         }
     }
 
     return result;
 }
 
 void DocumentMarkerController::removeMarkers(Node* node, DocumentMarker::MarkerTypes markerTypes)
 {
     if (!possiblyHasMarkers(markerTypes))
         return;
@@ skipping 18 matching lines @@
         if (iterator != m_markers.end())
             removeMarkersFromList(iterator, markerTypes);
     }
 
     m_possiblyExistingMarkerTypes.remove(markerTypes);
 }
 
 void DocumentMarkerController::removeMarkersFromList(MarkerMap::iterator iterator, DocumentMarker::MarkerTypes markerTypes)
 {
     bool needsRepainting = false;
-    bool listCanBeRemoved;
+    bool nodeCanBeRemoved;
 
+    size_t emptyListsCount = 0;
     if (markerTypes == DocumentMarker::AllMarkers()) {
         needsRepainting = true;
-        listCanBeRemoved = true;
+        nodeCanBeRemoved = true;
     } else {
-        MarkerList* list = iterator->value.get();
+        MarkerLists* markers = iterator->value.get();
 
-        for (size_t i = 0; i != list->size(); ) {
-            DocumentMarker marker = list->at(i);
-
-            // skip nodes that are not of the specified type
-            if (!markerTypes.contains(marker.type())) {
-                ++i;
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+            OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+            if (list->isEmpty()) {
+                ++emptyListsCount;
                 continue;
             }
-
-            // pitch the old marker
-            list->remove(i);
-            needsRepainting = true;
-            // i now is the index of the next marker
+            if (markerTypes.contains(list->begin()->type())) {
+                list->clear();
+                ++emptyListsCount;
+                needsRepainting = true;
+            }
         }
 
-        listCanBeRemoved = list->isEmpty();
+        nodeCanBeRemoved = emptyListsCount == DocumentMarker::MarkerTypeIndexesCount;
     }
 
     if (needsRepainting) {
         if (RenderObject* renderer = iterator->key->renderer())
             renderer->repaint();
     }
 
-    if (listCanBeRemoved) {
+    if (nodeCanBeRemoved) {
         m_markers.remove(iterator);
         if (m_markers.isEmpty())
             m_possiblyExistingMarkerTypes = 0;
     }
 }
 
 void DocumentMarkerController::repaintMarkers(DocumentMarker::MarkerTypes markerTypes)
 {
     if (!possiblyHasMarkers(markerTypes))
         return;
     ASSERT(!m_markers.isEmpty());
 
     // outer loop: process each markered node in the document
     MarkerMap::iterator end = m_markers.end();
     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
         Node* node = i->key.get();
 
         // inner loop: process each marker in the current node
-        MarkerList* list = i->value.get();
-        bool nodeNeedsRepaint = false;
-        for (size_t i = 0; i != list->size(); ++i) {
-            DocumentMarker marker = list->at(i);
+        MarkerLists* markers = i->value.get();
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+            OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+            if (list->isEmpty() || !markerTypes.contains(list->begin()->type()))
+                continue;
 
-            // skip nodes that are not of the specified type
-            if (markerTypes.contains(marker.type())) {
-                nodeNeedsRepaint = true;
-                break;
-            }
+            // cause the node to be redrawn
+            if (RenderObject* renderer = node->renderer())
+                renderer->repaint();

[groby-ooo-7-16, 2013/09/19 18:17:09]

I believe this needs a break - otherwise, this can trigger multiple repaints.

[pstanek, 2013/09/21 21:09:59]

Done.

         }
-
-        if (!nodeNeedsRepaint)
-            continue;
-
-        // cause the node to be redrawn
-        if (RenderObject* renderer = node->renderer())
-            renderer->repaint();
     }
 }
 
 void DocumentMarkerController::invalidateRenderedRectsForMarkersInRect(const LayoutRect& r)
 {
     // outer loop: process each markered node in the document
     MarkerMap::iterator end = m_markers.end();
     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
 
         // inner loop: process each rect in the current node
-        MarkerList* list = i->value.get();
-        for (size_t listIndex = 0; listIndex < list->size(); ++listIndex)
-            list->at(listIndex).invalidate(r);
+        MarkerLists* markers = i->value.get();
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+            OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+            for (size_t markerIndex = 0; markerIndex < list->size(); ++markerIndex)
+                list->at(markerIndex).invalidate(r);
+        }
     }
 }
 
 void DocumentMarkerController::shiftMarkers(Node* node, unsigned startOffset, int delta)
 {
     if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
         return;
     ASSERT(!m_markers.isEmpty());
 
-    MarkerList* list = m_markers.get(node);
-    if (!list)
+    MarkerLists* markers = m_markers.get(node);
+    if (!markers)
         return;
 
     bool docDirty = false;
-    for (size_t i = 0; i != list->size(); ++i) {
-        RenderedDocumentMarker& marker = list->at(i);
-        if (marker.startOffset() >= startOffset) {
-            ASSERT((int)marker.startOffset() + delta >= 0);
-            marker.shiftOffsets(delta);
-            docDirty = true;
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+        for (size_t i = 0; i != list->size(); ++i) {
+            RenderedDocumentMarker& marker = list->at(i);
+            if (marker.startOffset() >= startOffset) {

[groby-ooo-7-16, 2013/09/19 18:17:09]

upper_bound

[pstanek, 2013/09/20 18:56:00]

"Unlike lower_bound, the value pointed by the iterator returned by this function
cannot be equivalent to val, only greater."

[pstanek, 2013/09/21 21:09:59]

Done.

+                ASSERT((int)marker.startOffset() + delta >= 0);
+                marker.shiftOffsets(delta);
+                docDirty = true;
 
-            // Marker moved, so previously-computed rendered rectangle is now invalid
-            marker.invalidate();
+                // Marker moved, so previously-computed rendered rectangle is now invalid
+                marker.invalidate();
+            }
         }
     }
 
     // repaint the affected node
     if (docDirty && node->renderer())
         node->renderer()->repaint();
 }
 
 void DocumentMarkerController::setMarkersActive(Range* range, bool active)
 {
     if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
         return;
     ASSERT(!m_markers.isEmpty());
 
     Node* startContainer = range->startContainer();
     Node* endContainer = range->endContainer();
 
     Node* pastLastNode = range->pastLastNode();
 
     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(node)) {
         int startOffset = node == startContainer ? range->startOffset() : 0;
         int endOffset = node == endContainer ? range->endOffset() : INT_MAX;
         setMarkersActive(node, startOffset, endOffset, active);
     }
 }
 
 void DocumentMarkerController::setMarkersActive(Node* node, unsigned startOffset, unsigned endOffset, bool active)
 {
-    MarkerList* list = m_markers.get(node);
-    if (!list)
+    MarkerLists* markers = m_markers.get(node);
+    if (!markers)
         return;
 
     bool docDirty = false;
-    for (size_t i = 0; i != list->size(); ++i) {
-        DocumentMarker& marker = list->at(i);
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+        for (size_t i = 0; i != list->size(); ++i) {
+            DocumentMarker& marker = list->at(i);
 
-        // Markers are returned in order, so stop if we are now past the specified range.
-        if (marker.startOffset() >= endOffset)
-            break;
+            // Markers are returned in order, so stop if we are now past the specified range.
+            if (marker.startOffset() >= endOffset)
+                break;
 
-        // Skip marker that is wrong type or before target.
-        if (marker.endOffset() <= startOffset || marker.type() != DocumentMarker::TextMatch)
-            continue;
+            // Skip marker that is before target.
+            if (marker.endOffset() <= startOffset || marker.type() != DocumentMarker::TextMatch)

[groby-ooo-7-16, 2013/09/19 18:17:09]

upper_bound

[pstanek, 2013/09/20 15:17:33]

Oh. this does anything for TextMatch markers only so it may be simplified a lot.

[groby-ooo-7-16, 2013/09/20 15:35:58]

Well, a tiny bit at least :)
On 2013/09/20 15:17:33, pstanek wrote:

[pstanek, 2013/09/21 21:09:59]

Done.

+                continue;
 
-        marker.setActiveMatch(active);
-        docDirty = true;
+            marker.setActiveMatch(active);
+            docDirty = true;
+        }
     }
 
     // repaint the affected node
     if (docDirty && node->renderer())
         node->renderer()->repaint();
 }
 
 bool DocumentMarkerController::hasMarkers(Range* range, DocumentMarker::MarkerTypes markerTypes)
 {
     if (!possiblyHasMarkers(markerTypes))
         return false;
     ASSERT(!m_markers.isEmpty());
 
     Node* startContainer = range->startContainer();
     ASSERT(startContainer);
     Node* endContainer = range->endContainer();
     ASSERT(endContainer);
 
     Node* pastLastNode = range->pastLastNode();
     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(node)) {
         Vector<DocumentMarker*> markers = markersFor(node);
         Vector<DocumentMarker*>::const_iterator end = markers.end();
         for (Vector<DocumentMarker*>::const_iterator it = markers.begin(); it != end; ++it) {
             DocumentMarker* marker = *it;
             if (!markerTypes.contains(marker->type()))
                 continue;
             if (node == startContainer && marker->endOffset() <= static_cast<unsigned>(range->startOffset()))

[groby-ooo-7-16, 2013/09/19 18:17:09]

upper/lower_bound

[pstanek, 2013/09/20 15:07:40]

markersFor() again

                 continue;
             if (node == endContainer && marker->startOffset() >= static_cast<unsigned>(range->endOffset()))
                 continue;
             return true;
         }
     }
     return false;
 }
 
 #ifndef NDEBUG
 void DocumentMarkerController::showMarkers() const
 {
     fprintf(stderr, "%d nodes have markers:\n", m_markers.size());
     MarkerMap::const_iterator end = m_markers.end();
     for (MarkerMap::const_iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
         Node* node = nodeIterator->key.get();
         fprintf(stderr, "%p", node);
-        MarkerList* list = nodeIterator->value.get();
-        for (unsigned markerIndex = 0; markerIndex < list->size(); ++markerIndex) {
-            const DocumentMarker& marker = list->at(markerIndex);
-            fprintf(stderr, " %d:[%d:%d](%d)", marker.type(), marker.startOffset(), marker.endOffset(), marker.activeMatch());
+        MarkerLists* markers = m_markers.get(node);
+        for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+            OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+            for (unsigned markerIndex = 0; markerIndex < list->size(); ++markerIndex) {
+                const DocumentMarker& marker = list->at(markerIndex);
+                fprintf(stderr, " %d:[%d:%d](%d)", marker.type(), marker.startOffset(), marker.endOffset(), marker.activeMatch());
+            }
         }
 
         fprintf(stderr, "\n");
     }
 }
 #endif
 
 } // namespace WebCore
 
 #ifndef NDEBUG
 void showDocumentMarkers(const WebCore::DocumentMarkerController* controller)
 {
     if (controller)
         controller->showMarkers();
 }
 #endif