1 files changed, 64 insertions, 81 deletions

diff --git a/Source/WebCore/html/track/TextTrackCueList.cpp b/Source/WebCore/html/track/TextTrackCueList.cpp
index f5451f5f0..03827c8a7 100644
--- a/Source/WebCore/html/track/TextTrackCueList.cpp
+++ b/Source/WebCore/html/track/TextTrackCueList.cpp
@@ -1,5 +1,6 @@
 /*
- * Copyright (C) 2011 Google Inc.  All rights reserved.
+ * Copyright (C) 2011 Google Inc. All rights reserved.
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -10,10 +11,10 @@
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
- * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
@@ -29,118 +30,100 @@
 
 #include "TextTrackCueList.h"
 
-namespace WebCore {
+// Checking sorting is too slow for general use; turn it on explicitly when working on this class.
+#undef CHECK_SORTING
 
-TextTrackCueList::TextTrackCueList()
-{
-}
+#ifdef CHECK_SORTING
+#define ASSERT_SORTED(begin, end) ASSERT(std::is_sorted(begin, end, compareCues))
+#else
+#define ASSERT_SORTED(begin, end) ((void)0)
+#endif
+
+namespace WebCore {
 
-unsigned long TextTrackCueList::length() const
+static inline bool compareCues(const RefPtr<TextTrackCue>& a, const RefPtr<TextTrackCue>& b)
 {
-    return m_list.size();
+    return a->isOrderedBefore(b.get());
 }
 
-unsigned long TextTrackCueList::getCueIndex(TextTrackCue* cue) const
+unsigned TextTrackCueList::cueIndex(TextTrackCue& cue) const
 {
-    return m_list.find(cue);
+    ASSERT(m_vector.contains(&cue));
+    return m_vector.find(&cue);
 }
 
 TextTrackCue* TextTrackCueList::item(unsigned index) const
 {
-    if (index < m_list.size())
-        return m_list[index].get();
-    return 0;
+    if (index >= m_vector.size())
+        return nullptr;
+    return m_vector[index].get();
 }
 
 TextTrackCue* TextTrackCueList::getCueById(const String& id) const
 {
-    for (size_t i = 0; i < m_list.size(); ++i) {
-        if (m_list[i]->id() == id)
-            return m_list[i].get();
+    for (auto& cue : m_vector) {
+        if (cue->id() == id)
+            return cue.get();
     }
-    return 0;
+    return nullptr;
 }
 
-TextTrackCueList* TextTrackCueList::activeCues()
+TextTrackCueList& TextTrackCueList::activeCues()
 {
     if (!m_activeCues)
         m_activeCues = create();
 
-    m_activeCues->clear();
-    for (size_t i = 0; i < m_list.size(); ++i) {
-        RefPtr<TextTrackCue> cue = m_list[i];
+    Vector<RefPtr<TextTrackCue>> activeCuesVector;
+    for (auto& cue : m_vector) {
         if (cue->isActive())
-            m_activeCues->add(cue);
-    }
-    return m_activeCues.get();
-}
-
-bool TextTrackCueList::add(PassRefPtr<TextTrackCue> cue)
-{
-    ASSERT(cue->startTime() >= 0);
-    ASSERT(cue->endTime() >= 0);
-
-    return add(cue, 0, m_list.size());
-}
-
-bool TextTrackCueList::add(PassRefPtr<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
-    RefPtr<TextTrackCue> cue = prpCue;
-    if (start == end) {
-        if (!m_list.isEmpty() && (start > 0) && (m_list[start - 1].get() == cue.get()))
-            return false;
-
-        m_list.insert(start, cue);
-        invalidateCueIndexes(start);
-        return true;
+            activeCuesVector.append(cue);
     }
+    ASSERT_SORTED(activeCuesVector.begin(), activeCuesVector.end());
+    m_activeCues->m_vector = WTFMove(activeCuesVector);
 
-    size_t index = (start + end) / 2;
-    if (cue->isOrderedBefore(m_list[index].get()))
-        return add(cue.release(), start, index);
-
-    return add(cue.release(), index + 1, end);
+    // FIXME: This list of active cues is not updated as cues are added, removed, become active, and become inactive.
+    // Instead it is only updated each time this function is called again. That is not consistent with other dynamic DOM lists.
+    return *m_activeCues;
 }
 
-bool TextTrackCueList::remove(TextTrackCue* cue)
+void TextTrackCueList::add(Ref<TextTrackCue>&& cue)
 {
-    size_t index = m_list.find(cue);
-    if (index == notFound)
-        return false;
-
-    cue->setIsActive(false);
-    m_list.remove(index);
-    return true;
+    ASSERT(!m_vector.contains(cue.ptr()));
+    ASSERT(cue->startMediaTime() >= MediaTime::zeroTime());
+    ASSERT(cue->endMediaTime() >= MediaTime::zeroTime());
+
+    RefPtr<TextTrackCue> cueRefPtr { WTFMove(cue) };
+    unsigned insertionPosition = std::upper_bound(m_vector.begin(), m_vector.end(), cueRefPtr, compareCues) - m_vector.begin();
+    ASSERT_SORTED(m_vector.begin(), m_vector.end());
+    m_vector.insert(insertionPosition, WTFMove(cueRefPtr));
+    ASSERT_SORTED(m_vector.begin(), m_vector.end());
 }
 
-bool TextTrackCueList::contains(TextTrackCue* cue) const
+void TextTrackCueList::remove(TextTrackCue& cue)
 {
-    return m_list.contains(cue);
+    ASSERT_SORTED(m_vector.begin(), m_vector.end());
+    m_vector.remove(cueIndex(cue));
+    ASSERT_SORTED(m_vector.begin(), m_vector.end());
 }
 
-bool TextTrackCueList::updateCueIndex(TextTrackCue* cue)
+void TextTrackCueList::updateCueIndex(TextTrackCue& cue)
 {
-    if (!contains(cue))
-        return false;
-    
-    remove(cue);
-    return add(cue);
-}
-
-void TextTrackCueList::clear()
-{
-    m_list.clear();
-}
+    auto cuePosition = m_vector.begin() + cueIndex(cue);
+    auto afterCuePosition = cuePosition + 1;
+
+    ASSERT_SORTED(m_vector.begin(), cuePosition);
+    ASSERT_SORTED(afterCuePosition, m_vector.end());
+
+    auto reinsertionPosition = std::upper_bound(m_vector.begin(), cuePosition, *cuePosition, compareCues);
+    if (reinsertionPosition != cuePosition)
+        std::rotate(reinsertionPosition, cuePosition, afterCuePosition);
+    else {
+        reinsertionPosition = std::upper_bound(afterCuePosition, m_vector.end(), *cuePosition, compareCues);
+        if (reinsertionPosition != afterCuePosition)
+            std::rotate(cuePosition, afterCuePosition, reinsertionPosition);
+    }
 
-void TextTrackCueList::invalidateCueIndexes(size_t start)
-{
-    for (size_t i = start; i < m_list.size(); ++i)
-        m_list[i]->invalidateCueIndex();
+    ASSERT_SORTED(m_vector.begin(), m_vector.end());
 }
 
 } // namespace WebCore