Index: Source/core/dom/DocumentMarkerController.cpp |
diff --git a/Source/core/dom/DocumentMarkerController.cpp b/Source/core/dom/DocumentMarkerController.cpp |
index 0682b64d971844063c2305a976fcfb79acb7c53b..659d292b96107417202500ef698b2b0ba5d54cab 100644 |
--- a/Source/core/dom/DocumentMarkerController.cpp |
+++ b/Source/core/dom/DocumentMarkerController.cpp |
@@ -133,6 +133,16 @@ void DocumentMarkerController::removeMarkers(Range* range, DocumentMarker::Marke |
} |
} |
+static bool startsFurther(const DocumentMarker& lhv, const DocumentMarker& rhv) |
groby-ooo-7-16
2013/09/13 18:05:48
Chromium preference is putting helper functions in
tony
2013/09/13 18:18:49
Most blink code uses static functions, but I don't
|
+{ |
+ return lhv.startOffset() < rhv.startOffset(); |
+} |
+ |
+static bool doesNotOverlap(const DocumentMarker& lhv, const DocumentMarker& rhv) |
groby-ooo-7-16
2013/09/17 11:52:42
I just woke up at 4am to realize this does not wor
pstanek
2013/09/17 12:46:30
I thought about the same but I convinced myself it
groby-ooo-7-16
2013/09/17 14:20:26
Do-while is fine - but in line 194, you use doesNo
pstanek
2013/09/17 14:48:05
But with lower_bound() we find the first overlappi
groby-ooo-7-16
2013/09/17 17:14:09
Yes, but the vector is unsorted with respect to en
pstanek
2013/09/17 17:30:41
Ah :/
On 2013/09/17 17:14:09, groby wrote:
pstanek
2013/09/17 17:39:45
Then to make this efficient markers would have to
groby-ooo-7-16
2013/09/17 18:39:37
Separating them by type would certainly be helpful
pstanek
2013/09/18 10:49:46
Yes. The assumptions seem to be right but I fear u
groby-ooo-7-16
2013/09/18 18:24:08
Postponing this seems fine to me. (If you do, you
|
+{ |
+ 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. |
@@ -151,42 +161,19 @@ void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMa |
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()) { |
groby-ooo-7-16
2013/09/13 18:05:48
Isn't that covered by lower_bound already?
pstanek
2013/09/14 08:18:50
Yes, but the point was to avoid searching if no me
groby-ooo-7-16
2013/09/17 02:23:47
You probably want '>', though. if last.end == new.
pstanek
2013/09/17 13:54:00
But this if controls entering merging block so we'
groby-ooo-7-16
2013/09/17 14:34:41
Sigh. I misread that, sorry.
Done.
On 2013/09/17
|
+ if (toInsert.type() != DocumentMarker::TextMatch) { |
+ mergeOverlapping(list.get(), toInsert); |
+ } else { |
+ MarkerList::iterator pos = std::lower_bound(list->begin(), list->end(), toInsert, startsFurther); |
+ if (pos != list->end()) |
groby-ooo-7-16
2013/09/13 18:05:48
AFAIK, insert works for pos == list->end()-list->b
pstanek
2013/09/17 16:57:00
Done.
|
+ list->insert(pos - list->begin(), RenderedDocumentMarker(toInsert)); |
+ else |
+ list->append(RenderedDocumentMarker(toInsert)); |
} |
+ } else { |
+ list->append(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 |
@@ -194,6 +181,51 @@ void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMa |
node->renderer()->repaint(); |
} |
+void DocumentMarkerController::mergeOverlapping(MarkerList* list, DocumentMarker& toInsert) |
groby-ooo-7-16
2013/09/13 18:05:48
I think this can be simplified - find the first ov
pstanek
2013/09/14 08:18:50
This is exactly what it does. upper_bound is used
groby-ooo-7-16
2013/09/17 02:23:47
Caveat:I might be missing something and all this m
pstanek
2013/09/17 16:20:38
I'll try to combine your approach with the origina
pstanek
2013/09/17 16:57:00
Done. (at least partially)
|
+{ |
+ // 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. |
+ size_t numMarkers = list->size(); |
+ MarkerList::iterator end = std::upper_bound(list->begin(), list->end(), toInsert, startsFurther); |
+ MarkerList::iterator overlapping = list->begin(); |
+ size_t offset = 0; |
+ do { |
+ overlapping = std::lower_bound(overlapping + offset, end, toInsert, doesNotOverlap); |
+ offset = 1; |
+ } while (overlapping != end && overlapping->type() != toInsert.type()); |
+ |
+ size_t index = numMarkers; |
+ if (overlapping != list->end()) |
+ index = overlapping - list->begin(); |
+ if (overlapping != end) { |
+ toInsert.setStartOffset(overlapping->startOffset()); |
+ list->remove(index); |
+ --numMarkers; |
+ } |
+ |
+ // 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. |
+ for (size_t i = index; i < numMarkers;) { |
+ DocumentMarker marker = list->at(i); |
groby-ooo-7-16
2013/09/17 02:23:47
Calling at() will bounds-check each element - iter
pstanek
2013/09/17 16:57:00
Done.
|
+ if (marker.startOffset() > toInsert.endOffset()) |
+ break; |
+ if (marker.type() == toInsert.type()) { |
+ list->remove(i); |
+ if (toInsert.endOffset() <= marker.endOffset()) { |
+ toInsert.setEndOffset(marker.endOffset()); |
+ break; |
groby-ooo-7-16
2013/09/17 02:23:47
Why break here? Couldn't we potentially have more
pstanek
2013/09/17 16:57:00
Done.
|
+ } |
+ --numMarkers; |
+ } else { |
+ ++i; |
+ } |
+ } |
+ // At this point index points to the node before which we want to insert. |
+ list->insert(index, RenderedDocumentMarker(toInsert)); |
+} |
+ |
// 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) |