Index: Source/core/html/track/TextTrackCueList.cpp |
diff --git a/Source/core/html/track/TextTrackCueList.cpp b/Source/core/html/track/TextTrackCueList.cpp |
index bb23faffddc60b7993baed665ab706571e53484d..a442ddad66f692506aa13b3fb9e4be18918a84d8 100644 |
--- a/Source/core/html/track/TextTrackCueList.cpp |
+++ b/Source/core/html/track/TextTrackCueList.cpp |
@@ -24,9 +24,10 @@ |
*/ |
#include "config.h" |
- |
#include "core/html/track/TextTrackCueList.h" |
+#include "wtf/StdLibExtras.h" |
+ |
namespace blink { |
TextTrackCueList::TextTrackCueList() |
@@ -80,31 +81,33 @@ bool TextTrackCueList::add(PassRefPtrWillBeRawPtr<TextTrackCue> cue) |
ASSERT(cue->startTime() >= 0); |
ASSERT(cue->endTime() >= 0); |
- return add(cue, 0, m_list.size()); |
-} |
- |
-bool TextTrackCueList::add(PassRefPtrWillBeRawPtr<TextTrackCue> prpCue, size_t start, size_t end) |
-{ |
- ASSERT_WITH_SECURITY_IMPLICATION(start <= m_list.size()); |
- ASSERT_WITH_SECURITY_IMPLICATION(end <= m_list.size()); |
- |
// Maintain text track cue order: |
// http://www.whatwg.org/specs/web-apps/current-work/#text-track-cue-order |
philipj_slow
2015/02/25 02:28:40
https://html.spec.whatwg.org/#text-track-cue-order
fs
2015/02/25 16:39:49
Done.
|
- RefPtrWillBeRawPtr<TextTrackCue> cue = prpCue; |
- if (start == end) { |
- if (!m_list.isEmpty() && (start > 0) && (m_list[start - 1].get() == cue.get())) |
- return false; |
+ size_t index = findInsertionIndex(cue.get()); |
+ |
+ // FIXME: The cue should not exist in the list in the first place. |
+ if (!m_list.isEmpty() && (index > 0) && (m_list[index - 1].get() == cue.get())) |
+ return false; |
+ |
+ m_list.insert(index, cue); |
+ invalidateCueIndexes(index); |
+ return true; |
+} |
- m_list.insert(start, cue); |
- invalidateCueIndexes(start); |
+static bool cueIsBefore(const TextTrackCue* cue, PassRefPtrWillBeRawPtr<TextTrackCue> otherCue) |
+{ |
+ if (cue->startTime() < otherCue->startTime()) |
return true; |
- } |
- size_t index = (start + end) / 2; |
- if (cue->startTime() < m_list[index]->startTime() || (cue->startTime() == m_list[index]->startTime() && cue->endTime() > m_list[index]->endTime())) |
- return add(cue.release(), start, index); |
+ return cue->startTime() == otherCue->startTime() && cue->endTime() > otherCue->endTime(); |
+} |
- return add(cue.release(), index + 1, end); |
+size_t TextTrackCueList::findInsertionIndex(const TextTrackCue* cueToInsert) const |
+{ |
+ auto it = std::upper_bound(m_list.begin(), m_list.end(), cueToInsert, cueIsBefore); |
+ size_t index = safeCast<size_t>(it - m_list.begin()); |
+ ASSERT_WITH_SECURITY_IMPLICATION(index <= m_list.size()); |
+ return index; |
} |
bool TextTrackCueList::remove(TextTrackCue* cue) |
@@ -119,16 +122,27 @@ bool TextTrackCueList::remove(TextTrackCue* cue) |
bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) |
philipj_slow
2015/02/25 02:28:40
Here or in another CL the return value can be drop
fs
2015/02/25 13:09:49
Yes, it's a bit strange both that it wasn't used..
philipj_slow
2015/02/25 15:38:54
Thanks, I think that may make things a bit clearer
fs
2015/02/25 16:39:49
Return-value dropped. "Avoiding" O(n) here can onl
philipj_slow
2015/02/26 01:54:34
OK, looks like I'm still confused. Specifically, w
fs
2015/02/26 09:37:57
It's more because I want to be able to use oldInde
fs
2015/02/26 09:43:36
Uploaded as PS3.
|
{ |
- size_t index = m_list.find(cue); |
- if (index == kNotFound) |
+ size_t oldIndex = m_list.find(cue); |
+ if (oldIndex == kNotFound) |
return false; |
cue->setIsActive(false); |
cue->removeDisplayTree(); |
- m_list.remove(index); |
- |
- return add(cue); |
+ m_list.remove(oldIndex); |
+ size_t newIndex = findInsertionIndex(cue); |
+ m_list.insert(newIndex, cue); |
+ |
+ bool indexChanged = newIndex != oldIndex; |
philipj_slow
2015/02/25 02:28:40
I'm not sure what the benefit of this over add(cue
fs
2015/02/25 13:09:49
The main reason would be the comment below - i.e.
|
+ if (indexChanged) { |
+ // FIXME: If moving from oldIndex to newIndex and newIndex > oldIndex, |
philipj_slow
2015/02/25 02:28:40
TextTrackCueList::remove has the same problem, rig
fs
2015/02/25 13:09:49
In a sense, yes. Theoretically remove() does not i
philipj_slow
2015/02/25 15:38:54
Throw a FIXME in remove as well to make this class
fs
2015/02/25 16:39:49
Done.
|
+ // then what happens with the cached index on cues in the range |
+ // [oldIndex, newIndex)? (Some of the indices will be "safe", but |
+ // there'll be a risk that the lazy update via cueIndex() yields |
+ // duplicates/incorrect order.) |
+ invalidateCueIndexes(newIndex); |
+ } |
+ return indexChanged; |
} |
void TextTrackCueList::clear() |
@@ -138,6 +152,7 @@ void TextTrackCueList::clear() |
void TextTrackCueList::invalidateCueIndexes(size_t start) |
{ |
+ // FIXME: When iterating cues we could as well update their cached indices too. |
philipj_slow
2015/02/25 02:28:40
Heh, yeah :)
|
for (size_t i = start; i < m_list.size(); ++i) |
m_list[i]->invalidateCueIndex(); |
} |