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) {
+    case DocumentMarker::Spelling:
+        return DocumentMarker::SpellingMarkerIndex;
+    case DocumentMarker::Grammar:
+        return DocumentMarker::GramarMarkerIndex;
+    case DocumentMarker::TextMatch:
+        return DocumentMarker::TextMatchMarkerIndex;
+    }
+
+    ASSERT_NOT_REACHED();
+    return DocumentMarker::SpellingMarkerIndex;
+}
+
+} // 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 startsAfter(const DocumentMarker& marker, size_t startOffset)
+{
+    return marker.startOffset() < startOffset;
+}
+
+static bool endsBefore(size_t startOffset, const DocumentMarker& rhv)
+{
+    return startOffset < rhv.endOffset();
+}
+
+static bool compareByStart(const DocumentMarker* lhv, const DocumentMarker* rhv)
+{
+    return startsFurther(*lhv, *rhv);
+}
+
+static bool doesNotOverlap(const DocumentMarker& lhv, const DocumentMarker& rhv)
+{
+    return lhv.endOffset() < rhv.startOffset();
+}
+
+static bool doesNotInclude(const DocumentMarker& marker, size_t startOffset)
+{
+    return marker.endOffset() < 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;
+    OwnPtr<MarkerLists>& markers = m_markers.add(node, nullptr).iterator->value;
+    if (!markers) {
+        markers = adoptPtr(new MarkerLists);
+        markers->grow(DocumentMarker::MarkerTypeIndexesCount);
+    }
 
-    if (!list) {
-        list = adoptPtr(new MarkerList);
+    DocumentMarker::MarkerTypeIndex markerListIndex = MarkerTypeToMarkerIndex(newMarker.type());
+    if (!markers->at(markerListIndex)) {
+        markers->insert(markerListIndex, adoptPtr(new MarkerList));
+    }
+
+    OwnPtr<MarkerList>& list = markers->at(markerListIndex);
+    if (list->isEmpty() || list->last().endOffset() < newMarker.startOffset()) {
         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 (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));
         }
-        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));
     }
 
     // repaint the affected node
     if (node->renderer())
         node->renderer()->repaint();
 }
 
+void DocumentMarkerController::mergeOverlapping(MarkerList* list, DocumentMarker& toInsert)
+{
+    MarkerList::iterator firstOverlapping = std::lower_bound(list->begin(), list->end(), toInsert, doesNotOverlap);
+    size_t index = firstOverlapping - list->begin();
+    list->insert(index, RenderedDocumentMarker(toInsert));
+    MarkerList::iterator inserted = list->begin() + index;
+    firstOverlapping = inserted + 1;
+    for (MarkerList::iterator i = firstOverlapping; i != list->end() && i->startOffset() <= inserted->endOffset(); ) {
+        inserted->setStartOffset(std::min(inserted->startOffset(), i->startOffset()));
+        inserted->setEndOffset(std::max(inserted->endOffset(), i->endOffset()));
+        list->remove(i - list->begin());
+    }
+}
+
 // 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);
-
-        // stop if we are now past the specified range
-        if (marker.startOffset() > endOffset)
-            break;
-
-        // skip marker that is before the specified range or is the wrong type
-        if (marker.endOffset() < startOffset)
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+        if (!list)
             continue;
 
-        // 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);
+        unsigned endOffset = startOffset + length - 1;
+        MarkerList::iterator startPos = std::lower_bound(list->begin(), list->end(), startOffset, doesNotInclude);
+        for (MarkerList::iterator i = startPos; i != list->end(); ++i) {
+            DocumentMarker marker = *i;
 
-        addMarker(dstNode, marker);
+            // 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);
+
+            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 || list->isEmpty()) {
+            if (list.get() && list->isEmpty())
+                list.clear();
+            ++emptyListsCount;
             continue;
         }
+        if (!markerTypes.contains(list->begin()->type()))
+            continue;
+        unsigned endOffset = startOffset + length;
+        MarkerList::iterator startPos = std::upper_bound(list->begin(), list->end(), startOffset, endsBefore);
+        for (MarkerList::iterator i = startPos; i != list->end(); ) {
+            DocumentMarker marker = *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);
+            // at this point we know that marker and target intersect in some way
+            docDirty = true;
 
-        if (shouldRemovePartiallyOverlappingMarker)
-            // Stop here. Don't add resulting slices back.
-            continue;
+            // pitch the old marker
+            list->remove(i - list->begin());
 
-        // 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 (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);
+                size_t insertIndex = i - list->begin();
+                list->insert(insertIndex , RenderedDocumentMarker(newLeft));
+                // Move to the marker after the inserted one.
+                i = list->begin() + insertIndex + 1;
+            }
+            if (marker.endOffset() > endOffset) {
+                DocumentMarker newRight = marker;
+                newRight.setStartOffset(endOffset);
+                size_t insertIndex = i - list->begin();
+                list->insert(insertIndex, RenderedDocumentMarker(newRight));
+                // Move to the marker after the inserted one.
+                i = list->begin() + insertIndex + 1;
+            }
         }
-        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()) {
+            list.clear();
+            ++emptyListsCount;
         }
     }
 
-    if (list->isEmpty()) {
+    if (emptyListsCount == DocumentMarker::MarkerTypeIndexesCount) {
         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();
-        unsigned markerCount = list->size();
+        MarkerLists* markers = nodeIterator->value.get();
+        OwnPtr<MarkerList>& list = (*markers)[MarkerTypeToMarkerIndex(markerType)];
+        unsigned markerCount = list.get() ? list->size() : 0;
         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 || list->isEmpty() || !markerTypes.contains(list->begin()->type()))
+            continue;
+
+        for (size_t i = 0; i < list->size(); ++i)
             result.append(&(list->at(i)));
     }
 
+    std::sort(result.begin(), result.end(), compareByStart);
     return result;
 }
 
 Vector<DocumentMarker*> DocumentMarkerController::markers()
 {
     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; list.get() && j < list->size(); ++j)
+                result.append(&(list->at(j)));
+        }
     }
+    std::sort(result.begin(), result.end(), compareByStart);
     return result;
 }
 
 Vector<DocumentMarker*> DocumentMarkerController::markersInRange(Range* range, DocumentMarker::MarkerTypes markerTypes)
 {
     if (!possiblyHasMarkers(markerTypes))
         return Vector<DocumentMarker*>();
 
     Vector<DocumentMarker*> foundMarkers;
 
@@ skipping 25 matching lines @@
     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 || 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 || list->isEmpty()) {
+                if (list.get() && list->isEmpty())
+                    list.clear();
+                ++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();
+                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 || list->isEmpty() || !markerTypes.contains(list->begin()->type()))
+                continue;
 
-            // skip nodes that are not of the specified type
-            if (markerTypes.contains(marker.type())) {
-                nodeNeedsRepaint = true;
+            // cause the node to be redrawn
+            if (RenderObject* renderer = node->renderer()) {
+                renderer->repaint();
                 break;
             }
         }
-
-        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; list.get() && 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);
+    for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
+        OwnPtr<MarkerList>& list = (*markers)[markerListIndex];
+        if (!list)
+            continue;
+        MarkerList::iterator startPos = std::lower_bound(list->begin(), list->end(), startOffset, startsAfter);
+        for (MarkerList::iterator marker = startPos; marker != list->end(); ++marker) {
+            ASSERT((int)marker->startOffset() + delta >= 0);
+            marker->shiftOffsets(delta);
             docDirty = true;
 
             // Marker moved, so previously-computed rendered rectangle is now invalid
-            marker.invalidate();
+            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);
+    OwnPtr<MarkerList>& list = (*markers)[MarkerTypeToMarkerIndex(DocumentMarker::TextMatch)];
+    if (!list)
+        return;
+    MarkerList::iterator startPos = std::upper_bound(list->begin(), list->end(), startOffset, endsBefore);
+    for (MarkerList::iterator marker = startPos; marker != list->end(); ++marker) {
 
         // Markers are returned in order, so stop if we are now past the specified range.
-        if (marker.startOffset() >= endOffset)
+        if (marker->startOffset() >= endOffset)
             break;
 
-        // Skip marker that is wrong type or before target.
-        if (marker.endOffset() <= startOffset || marker.type() != DocumentMarker::TextMatch)
-            continue;
-
-        marker.setActiveMatch(active);
+        marker->setActiveMatch(active);
         docDirty = true;
     }
 
     // repaint the affected node
     if (docDirty && node->renderer())
         node->renderer()->repaint();
 }
 
 bool DocumentMarkerController::hasMarkers(Range* range, DocumentMarker::MarkerTypes markerTypes)
 {
@@ skipping 25 matching lines @@
 }
 
 #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; list.get() && 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