Replace open-coded binary search in TextTrackCueList::add with upper_bound

Source/core/html/track/TextTrackCueList.cpp

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 dropped, it isn't used.

[fs, 2015/02/25 13:09:49]

Yes, it's a bit strange both that it wasn't used... I might as well drop it in
this CL. I want to conditionalize calling this on whether the cue order could
actually have changed at all (this method is O(n) after all).

[philipj_slow, 2015/02/25 15:38:54]

Thanks, I think that may make things a bit clearer, as it currently appears as
if some effort is spent trying to return the right thing, but it sounds like
avoiding O(n) is the real reason.

[fs, 2015/02/25 16:39:49]

Return-value dropped. "Avoiding" O(n) here can only be achieved by not calling
this method at all =) (all actions on m_list in this method - find, remove,
insert - are worst/average-case O(n)).

[philipj_slow, 2015/02/26 01:54:34]

OK, looks like I'm still confused. Specifically, why can't updateCueIndex() call
add() like it did before? Is it because you want add() to eventually call
updateCueIndex() directly or indirectly via invalidateCueIndexes()?

[fs, 2015/02/26 09:37:57]

It's more because I want to be able to use oldIndex when invalidating cue
indices, so this just "lifting" the carpet to show that someone forgot to clean
there. So what I'll do here in a follow-up is essentially:

invalidateCueIndex(std::min(oldIndex, newIndex));

but I suppose I could also do:

m_list.remove(...);
invalidateCueIndex(oldIndex);
...
m_list.insert(...);
invalidateCueIndex(newIndex);

and hence just use remove() and add directly. So let me re-add add() here and
adjust the FIXME a bit, and hopefully you'll end up less confused...

[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) is going to be. Is there
anything other than getting the return value right that matters?

[fs, 2015/02/25 13:09:49]

The main reason would be the comment below - i.e. it make sense to have both of
the index-values available when invalidating the cue index. Did not intend to
actually fix anything in this CL though.

+    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, right?

[fs, 2015/02/25 13:09:49]

In a sense, yes. Theoretically remove() does not invalidate the cue order
property though (cueIndex(list[i]) < cueIndex(list[i+2]) still hold etc.).
You're quite likely to end up in a bad place eventually though. I have some
plans for how to change the "cue index" management that ought to address all the
FIXMEs in this CL - just putting the spotlight on them here basically.

[philipj_slow, 2015/02/25 15:38:54]

Throw a FIXME in remove as well to make this class appear maximally in need of
fixing? :)

[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();
 }