OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (C) 2011 Google Inc. All rights reserved. | 2 * Copyright (C) 2011 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
11 * documentation and/or other materials provided with the distribution. | 11 * documentation and/or other materials provided with the distribution. |
12 * | 12 * |
13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY | 13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY |
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR | 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR |
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 */ | 24 */ |
25 | 25 |
26 #include "config.h" | 26 #include "config.h" |
27 #include "core/html/track/TextTrackCueList.h" | |
27 | 28 |
28 #include "core/html/track/TextTrackCueList.h" | 29 #include "wtf/StdLibExtras.h" |
29 | 30 |
30 namespace blink { | 31 namespace blink { |
31 | 32 |
32 TextTrackCueList::TextTrackCueList() | 33 TextTrackCueList::TextTrackCueList() |
33 { | 34 { |
34 } | 35 } |
35 | 36 |
36 DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(TextTrackCueList); | 37 DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(TextTrackCueList); |
37 | 38 |
38 unsigned long TextTrackCueList::length() const | 39 unsigned long TextTrackCueList::length() const |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
73 m_activeCues->add(cue); | 74 m_activeCues->add(cue); |
74 } | 75 } |
75 return m_activeCues.get(); | 76 return m_activeCues.get(); |
76 } | 77 } |
77 | 78 |
78 bool TextTrackCueList::add(PassRefPtrWillBeRawPtr<TextTrackCue> cue) | 79 bool TextTrackCueList::add(PassRefPtrWillBeRawPtr<TextTrackCue> cue) |
79 { | 80 { |
80 ASSERT(cue->startTime() >= 0); | 81 ASSERT(cue->startTime() >= 0); |
81 ASSERT(cue->endTime() >= 0); | 82 ASSERT(cue->endTime() >= 0); |
82 | 83 |
83 return add(cue, 0, m_list.size()); | 84 // Maintain text track cue order: |
85 // 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.
| |
86 size_t index = findInsertionIndex(cue.get()); | |
87 | |
88 // FIXME: The cue should not exist in the list in the first place. | |
89 if (!m_list.isEmpty() && (index > 0) && (m_list[index - 1].get() == cue.get( ))) | |
90 return false; | |
91 | |
92 m_list.insert(index, cue); | |
93 invalidateCueIndexes(index); | |
94 return true; | |
84 } | 95 } |
85 | 96 |
86 bool TextTrackCueList::add(PassRefPtrWillBeRawPtr<TextTrackCue> prpCue, size_t s tart, size_t end) | 97 static bool cueIsBefore(const TextTrackCue* cue, PassRefPtrWillBeRawPtr<TextTrac kCue> otherCue) |
87 { | 98 { |
88 ASSERT_WITH_SECURITY_IMPLICATION(start <= m_list.size()); | 99 if (cue->startTime() < otherCue->startTime()) |
89 ASSERT_WITH_SECURITY_IMPLICATION(end <= m_list.size()); | 100 return true; |
90 | 101 |
91 // Maintain text track cue order: | 102 return cue->startTime() == otherCue->startTime() && cue->endTime() > otherCu e->endTime(); |
92 // http://www.whatwg.org/specs/web-apps/current-work/#text-track-cue-order | 103 } |
93 RefPtrWillBeRawPtr<TextTrackCue> cue = prpCue; | |
94 if (start == end) { | |
95 if (!m_list.isEmpty() && (start > 0) && (m_list[start - 1].get() == cue. get())) | |
96 return false; | |
97 | 104 |
98 m_list.insert(start, cue); | 105 size_t TextTrackCueList::findInsertionIndex(const TextTrackCue* cueToInsert) con st |
99 invalidateCueIndexes(start); | 106 { |
100 return true; | 107 auto it = std::upper_bound(m_list.begin(), m_list.end(), cueToInsert, cueIsB efore); |
101 } | 108 size_t index = safeCast<size_t>(it - m_list.begin()); |
102 | 109 ASSERT_WITH_SECURITY_IMPLICATION(index <= m_list.size()); |
103 size_t index = (start + end) / 2; | 110 return index; |
104 if (cue->startTime() < m_list[index]->startTime() || (cue->startTime() == m_ list[index]->startTime() && cue->endTime() > m_list[index]->endTime())) | |
105 return add(cue.release(), start, index); | |
106 | |
107 return add(cue.release(), index + 1, end); | |
108 } | 111 } |
109 | 112 |
110 bool TextTrackCueList::remove(TextTrackCue* cue) | 113 bool TextTrackCueList::remove(TextTrackCue* cue) |
111 { | 114 { |
112 size_t index = m_list.find(cue); | 115 size_t index = m_list.find(cue); |
113 if (index == kNotFound) | 116 if (index == kNotFound) |
114 return false; | 117 return false; |
115 | 118 |
116 m_list.remove(index); | 119 m_list.remove(index); |
117 return true; | 120 return true; |
118 } | 121 } |
119 | 122 |
120 bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) | 123 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.
| |
121 { | 124 { |
122 size_t index = m_list.find(cue); | 125 size_t oldIndex = m_list.find(cue); |
123 if (index == kNotFound) | 126 if (oldIndex == kNotFound) |
124 return false; | 127 return false; |
125 | 128 |
126 cue->setIsActive(false); | 129 cue->setIsActive(false); |
127 cue->removeDisplayTree(); | 130 cue->removeDisplayTree(); |
128 | 131 |
129 m_list.remove(index); | 132 m_list.remove(oldIndex); |
133 size_t newIndex = findInsertionIndex(cue); | |
134 m_list.insert(newIndex, cue); | |
130 | 135 |
131 return add(cue); | 136 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.
| |
137 if (indexChanged) { | |
138 // 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.
| |
139 // then what happens with the cached index on cues in the range | |
140 // [oldIndex, newIndex)? (Some of the indices will be "safe", but | |
141 // there'll be a risk that the lazy update via cueIndex() yields | |
142 // duplicates/incorrect order.) | |
143 invalidateCueIndexes(newIndex); | |
144 } | |
145 return indexChanged; | |
132 } | 146 } |
133 | 147 |
134 void TextTrackCueList::clear() | 148 void TextTrackCueList::clear() |
135 { | 149 { |
136 m_list.clear(); | 150 m_list.clear(); |
137 } | 151 } |
138 | 152 |
139 void TextTrackCueList::invalidateCueIndexes(size_t start) | 153 void TextTrackCueList::invalidateCueIndexes(size_t start) |
140 { | 154 { |
155 // FIXME: When iterating cues we could as well update their cached indices t oo. | |
philipj_slow
2015/02/25 02:28:40
Heh, yeah :)
| |
141 for (size_t i = start; i < m_list.size(); ++i) | 156 for (size_t i = start; i < m_list.size(); ++i) |
142 m_list[i]->invalidateCueIndex(); | 157 m_list[i]->invalidateCueIndex(); |
143 } | 158 } |
144 | 159 |
145 DEFINE_TRACE(TextTrackCueList) | 160 DEFINE_TRACE(TextTrackCueList) |
146 { | 161 { |
147 visitor->trace(m_list); | 162 visitor->trace(m_list); |
148 visitor->trace(m_activeCues); | 163 visitor->trace(m_activeCues); |
149 } | 164 } |
150 | 165 |
151 } // namespace blink | 166 } // namespace blink |
OLD | NEW |