Implement start, end, and middle overlaps for SourceBufferStream

media/filters/source_buffer_stream.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "media/filters/source_buffer_stream.h"
 
 #include <algorithm>
 #include <map>
 
 #include "base/logging.h"
 
 namespace media {
 
 // Helper class representing a range of buffered data. All buffers in a
 // SourceBufferRange are ordered sequentially in presentation order with no
 // gaps.
 class SourceBufferRange {
  public:
   typedef std::deque<scoped_refptr<StreamParserBuffer> > BufferQueue;
 
-  SourceBufferRange();
+  // Creates a source buffer range with |new_buffers|. |new_buffers| cannot be
+  // empty and the front of |new_buffers| must be a keyframe.
+  SourceBufferRange(const BufferQueue& new_buffers);

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

add explicit

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Good catch, done.

 
-  // Adds |new_buffers| into this range. |new_buffers| must belong to this
-  // range. Garbage collection may occur after Append().
-  void Append(const BufferQueue& new_buffers);
+  // Appends |buffers| to the end of the range and updates |keyframe_map_| as
+  // it encounters new keyframes. Assumes |buffers| belongs at the end of the
+  // range.
+  void AppendToEnd(const BufferQueue& buffers);
+  bool CanAppendToEnd(const BufferQueue& buffers) const;
+
+  // Appends the buffers from |range| into this range.
+  // The first buffer in |range| must come directly after the last buffer
+  // in this range.
+  // If |transfer_current_position| is true, |range|'s |next_buffer_position_|

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

next_buffer_position_ -> next_buffer_index_?

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Done.

+  // is transfered to this SourceBufferRange.
+  void AppendToEnd(const SourceBufferRange& range,
+                   bool transfer_current_position);
+  bool CanAppendToEnd(const SourceBufferRange& range) const;
 
   // Updates |next_buffer_index_| to point to the Buffer containing |timestamp|.
   // Assumes |timestamp| is valid and in this range.
   void Seek(base::TimeDelta timestamp);
 
   // Updates |next_buffer_index_| to point to next keyframe after or equal to
-  // |timestamp|. If there is no such keyframe, then this range will seek to
-  // the end and return kNoTimestamp().
-  // Assumes |timestamp| is valid and in this range.
-  base::TimeDelta SeekAfter(base::TimeDelta timestamp);
+  // |timestamp|.
+  void SeekAfter(base::TimeDelta timestamp);
+
+  // Finds the next keyframe from |buffers_| after |timestamp|, and creates and
+  // returns a new SourceBufferRange with the buffers from that keyframe onward.
+  // The buffers in the new SourceBufferRange are moved out of this range. If
+  // there is no keyframe after |timestamp|, SplitRange() returns null and this
+  // range is unmodified.
+  SourceBufferRange* SplitRange(base::TimeDelta timestamp);
+
+  // Deletes the buffers from this range whose timestamps are greater than or
+  // equal to |buffer|'s timestamp.
+  // Resets |next_buffer_index_| if the buffer after |next_buffer_index_| was
+  // deleted.
+  // If |deleted_buffers| or |next_buffer| are null, they are ignored.
+  // Otherwise, |deleted_buffers| contains the buffers that were deleted from
+  // this range, and |next_buffer| points to the deleted next buffer or to

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

nit: Perhaps reword "deleted next buffer" to something like "buffer in
|deleted_buffers| that |next_buffer_index_| pointed to."

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Did some rewording, and also deleted the other comments for DeleteAll and the
private version of DeleteAfter to reduce mistakes from copy/paste.

+  // |deleted_buffers.end()| if the next buffer was not deleted.

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

nit: "the next buffer was not deleted" -> "|next_buffer_index_| did not point to
any buffer added to |deleted_buffers|"

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Done.

+  void DeleteAfter(scoped_refptr<StreamParserBuffer> buffer,

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

nit: It might be good to mention that keyframe_map_ entries for the deleted
buffers are also removed.

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Done.

+                   BufferQueue* deleted_buffers,
+                   BufferQueue::iterator* next_buffer);
+
+  // Deletes all buffers in range.
+  // If |deleted_buffers| or |next_buffer| are null, they are ignored.
+  // Otherwise, |deleted_buffers| contains the buffers that were deleted from
+  // this range, and |next_buffer| points to the deleted next buffer or to
+  // |deleted_buffers.end()| if the next buffer was not deleted.
+  void DeleteAll(BufferQueue* deleted_buffers,
+                 BufferQueue::iterator* next_buffer);
 
   // Updates |out_buffer| with the next buffer in presentation order. Seek()
   // must be called before calls to GetNextBuffer(), and buffers are returned
   // in order from the last call to Seek(). Returns true if |out_buffer| is
   // filled with a valid buffer, false if there is not enough data to fulfill
   // the request.
   bool GetNextBuffer(scoped_refptr<StreamParserBuffer>* out_buffer);
+
+  // Returns the timestamp of the next buffer that will be returned from
+  // GetNextBuffer(). Returns kNoTimestamp() if Seek() has never been called or
+  // if this range does not have the next buffer yet.
   base::TimeDelta GetNextTimestamp() const;
 
+  // Returns the end timestamp of the buffered data. (Note that this is equal to
+  // the last buffer's timestamp + its duration.) Returns kNoTimestamp if the

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

nit: Can we have an empty range? If not remove that part of the comment please.

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

It is possible (e.g. after completely overlapping a Range and DeleteAll() is
called), but the expectation is that an empty Range will be immediately deleted,
and there should be no empty Ranges in |ranges_|.

Anyway, you're right that the comment should be deleted and the method should
DCHECK instead of doing the if statement. Done.

+  // range is empty.
+  base::TimeDelta GetEndTimestamp() const;
+
   // Returns the Timespan of buffered time in this range.
   SourceBufferStream::Timespan GetBufferedTime() const;
 
-  // Appends the buffers from |range| into this range.
-  // The first buffer in |range| must come directly after the last buffer
-  // in this range.
-  // If |transfer_current_position| is true, |range|'s |next_buffer_position_|
-  // is transfered to this SourceBufferRange.
-  void AppendToEnd(const SourceBufferRange& range,
-                   bool transfer_current_position);
-  bool CanAppendToEnd(const SourceBufferRange& range) const;
-  bool CanAppendToEnd(const BufferQueue& buffers) const;
-
   // Returns whether a buffer with a starting timestamp of |timestamp| would
   // belong in this range. This includes a buffer that would be appended to
   // the end of the range.
   // Returns 0 if |timestamp| is in this range, -1 if |timestamp| appears
   // before this range, or 1 if |timestamp| appears after this range.
   int BelongsToRange(base::TimeDelta timestamp) const;
 
   // Returns true if the range has enough data to seek to the specified
   // |timestamp|, false otherwise.
   bool CanSeekTo(base::TimeDelta timestamp) const;
 
   // Returns true if this range's buffered timespan completely overlaps the
   // buffered timespan of |range|.
   bool CompletelyOverlaps(const SourceBufferRange& range) const;
 
   // Returns true if the end of this range contains buffers that overlaps with
   // the beginning of |range|.
   bool EndOverlaps(const SourceBufferRange& range) const;
 
-  // Functions that tell how |buffers| intersects with this range.
-  // TODO(vrk): These functions should be unnecessary when overlapping the
-  // selected range is implemented properly. (crbug.com/126560)
-  bool IsStartOverlappedBy(const BufferQueue& buffers) const;
-  bool IsEndOverlappedBy(const BufferQueue& buffers) const;
-  bool IsCompletelyOverlappedBy(const BufferQueue& buffers) const;
-
  private:
-  // Appends |buffers| to the end of the range and updates |keyframe_map_| as
-  // it encounters new keyframes. Assumes |buffers| belongs at the end of the
-  // range.
-  void AppendToEnd(const BufferQueue& buffers);
+  // Helper method to delete buffers in |buffers_| starting from
+  // |starting_point|, an iterator in |buffers_|.
+  // If |deleted_buffers| or |next_buffer| are null, they are ignored.
+  // Otherwise, |deleted_buffers| contains the buffers that were deleted from
+  // this range, and |next_buffer| points to the deleted next buffer or to
+  // |deleted_buffers.end()| if the next buffer was not deleted.
+  void DeleteAfter(BufferQueue::iterator starting_point,
+                   BufferQueue* deleted_buffers,
+                   BufferQueue::iterator* next_buffer);
 
   // Returns the start timestamp of the range, or kNoTimestamp if the range is
   // empty.
   base::TimeDelta BufferedStart() const;
 
   // Returns the end timestamp of the buffered data. (Note that this is equal to
   // the last buffer's timestamp + its duration.) Returns kNoTimestamp if the
   // range is empty.
   base::TimeDelta BufferedEnd() const;
 
   // An ordered list of buffers in this range.
   BufferQueue buffers_;
 
   // Maps keyframe timestamps to its index position in |buffers_|.
   typedef std::map<base::TimeDelta, size_t> KeyframeMap;
   KeyframeMap keyframe_map_;
 
   // Index into |buffers_| for the next buffer to be returned by
   // GetBufferedTime(), set to -1 before Seek().
   int next_buffer_index_;
 
+  // True if the range needs to wait for the next keyframe to be appended before
+  // returning buffers from GetNextBuffer().
+  bool waiting_for_keyframe_;
+
+  // If |waiting_for_keyframe_| is true, this range will wait for the next
+  // keyframe with timestamp >= |next_keyframe_timestamp_|.
+  base::TimeDelta next_keyframe_timestamp_;
+
   DISALLOW_COPY_AND_ASSIGN(SourceBufferRange);
 };
 
 }  // namespace media
 
 // Helper method that returns true if |ranges| is sorted in increasing order,
 // false otherwise.
 static bool IsRangeListSorted(
     const std::list<media::SourceBufferRange*>& ranges) {
   base::TimeDelta prev = media::kNoTimestamp();
   for (std::list<media::SourceBufferRange*>::const_iterator itr =
        ranges.begin(); itr != ranges.end(); itr++) {
     media::SourceBufferStream::Timespan buffered = (*itr)->GetBufferedTime();
     if (prev != media::kNoTimestamp() && prev >= buffered.first)
       return false;
     prev = buffered.second;
   }
   return true;
 }
 
 // Comparison function for two Buffers based on timestamp.
-static bool BufferComparator(scoped_refptr<media::Buffer> first,
-                             scoped_refptr<media::Buffer> second) {
+static bool BufferComparator(
+    const scoped_refptr<media::StreamParserBuffer>& first,
+    const scoped_refptr<media::StreamParserBuffer>& second) {
   return first->GetTimestamp() < second->GetTimestamp();
 }
 
 // Returns the upper bound for the starting timestamp for the next buffer
 // in sequence after |buffer|. Assumes |buffer|'s timestamp and
 // duration are valid.
 static base::TimeDelta MaxNextTimestamp(
     const scoped_refptr<media::StreamParserBuffer>& buffer) {
   // Because we do not know exactly when is the next timestamp, any buffer
   // that starts within 1/3 of the duration past the end of this buffer
   // is considered the next buffer in the sequence.
   return buffer->GetEndTimestamp() + buffer->GetDuration() / 3;
 }
 
 // Returns true if |timestamp| is the timestamp of the next buffer in
 // sequence after |buffer|, false otherwise.
 static bool IsNextInSequence(
     const scoped_refptr<media::StreamParserBuffer>& buffer,
     base::TimeDelta timestamp) {
   return timestamp >= buffer->GetEndTimestamp() &&
       timestamp <= MaxNextTimestamp(buffer);
 }
 
 namespace media {
 
 SourceBufferStream::SourceBufferStream()
     : seek_pending_(false),
       seek_buffer_timestamp_(kNoTimestamp()),
-      selected_range_(NULL),
-      waiting_for_keyframe_(false) {
+      selected_range_(NULL) {
 }
 
 SourceBufferStream::~SourceBufferStream() {
   while (!ranges_.empty()) {
     delete ranges_.front();
     ranges_.pop_front();
   }
 }
 
 bool SourceBufferStream::Append(
     const SourceBufferStream::BufferQueue& buffers) {
   DCHECK(!buffers.empty());
 
-  // Check to see if |buffers| will overlap the currently |selected_range_|,
-  // and if so, ignore this Append() request.
-  // TODO(vrk): Support overlapping selected range properly. (crbug.com/126560)
-  if (selected_range_ &&
-      (selected_range_->IsEndOverlappedBy(buffers) ||
-       selected_range_->IsStartOverlappedBy(buffers))) {
-    return false;
-  }
-
-  SourceBufferRange* range = NULL;
+  RangeList::iterator range_for_new_buffers = ranges_.end();
   RangeList::iterator itr = ranges_.end();
   base::TimeDelta start_timestamp = buffers.front()->GetTimestamp();
   for (itr = ranges_.begin(); itr != ranges_.end(); itr++) {
     int range_value = (*itr)->BelongsToRange(start_timestamp);
-
-    // |start_timestamp| is before the current range in this loop. Because
-    // |ranges_| is sorted, this means that we need to create a new range and it
-    // should be placed before |itr|.
-    // TODO(vrk): We also break out of the loop if |buffers| completely overlaps
-    // the current range. This is to cover the case when |buffers| belongs to
-    // the current range, but also completely overlaps it. This should be
-    // removed when start overlap is handled properly.
-    if (range_value < 0 || (*itr)->IsCompletelyOverlappedBy(buffers))
+    if (range_value < 0)
       break;
 
     if (range_value == 0) {
       // Found an existing range into which we can append buffers.
-      range = *itr;
-
-      if (range->CanAppendToEnd(buffers) && waiting_for_keyframe_) {
-        // Currently we do not support the case where the next buffer after the
-        // buffers in the track buffer is not a keyframe.
-        if (!buffers.front()->IsKeyframe())
-          return false;
-        waiting_for_keyframe_ = false;
-      }
+      range_for_new_buffers = itr;
       break;
     }
   }
 
-  if (!range) {
+  if (range_for_new_buffers == ranges_.end()) {
     // Ranges must begin with a keyframe.
     if (!buffers.front()->IsKeyframe())
       return false;
-
-    range = new SourceBufferRange();
-    itr = ranges_.insert(itr, range);
+    range_for_new_buffers =
+        ranges_.insert(itr, new SourceBufferRange(buffers));
+  } else {
+    InsertIntoExistingRange(range_for_new_buffers, buffers);
   }
 
-  // Append buffers to the appropriate range.
-  range->Append(buffers);
-
-  // Increment |itr| to be the range after |range|.
-  itr++;
-
   // Resolve overlaps.
-  itr = ResolveCompleteOverlaps(itr, range);
-  itr = ResolveEndOverlaps(itr, range);
-  MergeWithAdjacentRangeIfNecessary(itr, range);
+  ResolveCompleteOverlaps(range_for_new_buffers);
+  ResolveEndOverlap(range_for_new_buffers);
+  MergeWithAdjacentRangeIfNecessary(range_for_new_buffers);
 
   // Finally, try to complete pending seek if one exists.
   if (seek_pending_)
     Seek(seek_buffer_timestamp_);
 
   DCHECK(IsRangeListSorted(ranges_));
   return true;
 }
 
-SourceBufferStream::RangeList::iterator
-SourceBufferStream::ResolveCompleteOverlaps(
-    const RangeList::iterator& range_itr, SourceBufferRange* new_range) {
-  RangeList::iterator itr = range_itr;
-  while (itr != ranges_.end() && new_range->CompletelyOverlaps(**itr)) {
-    if (*itr == selected_range_) {
-      // Get the timestamp for the next buffer in the sequence.
-      base::TimeDelta next_timestamp = selected_range_->GetNextTimestamp();
-      // Then seek to the next keyframe after (or equal to) |next_timestamp|.
-      // This will allow us to transition from the old buffers to the new
-      // buffers seamlessly.
-      base::TimeDelta next_keyframe_timestamp =
-          new_range->SeekAfter(next_timestamp);
+void SourceBufferStream::InsertIntoExistingRange(
+    const RangeList::iterator& range_for_new_buffers_itr,
+    const BufferQueue& new_buffers) {
+  SourceBufferRange* range_for_new_buffers = *range_for_new_buffers_itr;
+  RangeList::iterator next_range_itr = range_for_new_buffers_itr;
+  next_range_itr++;
 
-      // If there's no keyframe after |next_timestamp|, then set flag to wait
-      // for the next keyframe in this range to be appended.
-      if (next_keyframe_timestamp == kNoTimestamp())
-        waiting_for_keyframe_ = true;
+  // In case this is a middle overlap, save the buffers that come after the end
+  // of |new_buffers|, and add them into a new range.
+  SourceBufferRange* new_portion =
+      range_for_new_buffers->SplitRange(new_buffers.back()->GetEndTimestamp());
 
-      // Add all the old buffers up until |next_keyframe_timestamp| into
-      // |track_buffer_|. If there was no keyframe, then we add all buffers into
-      // |track_buffer_|.
-      scoped_refptr<StreamParserBuffer> next_buffer;
-      while (selected_range_->GetNextBuffer(&next_buffer) &&
-             (waiting_for_keyframe_ ||
-             next_buffer->GetTimestamp() < next_keyframe_timestamp)) {
-        track_buffer_.push_back(next_buffer);
-      }
+  if (new_portion) {
+    next_range_itr = ranges_.insert(next_range_itr, new_portion);
+    // If |range_for_new_buffers| was selected and the next buffer was in the
+    // |new_portion| half, update |selected_range_|.
+    if (selected_range_ == range_for_new_buffers &&
+        new_portion->GetNextTimestamp() != kNoTimestamp()) {
+      selected_range_ = new_portion;
+    }
+  }
 
-      selected_range_ = new_range;
-    }
-    delete *itr;
-    itr = ranges_.erase(itr);
+  BufferQueue deleted_buffers;
+  BufferQueue::iterator next_buffer;
+  range_for_new_buffers->DeleteAfter(
+      new_buffers.front(), &deleted_buffers, &next_buffer);
+  range_for_new_buffers->AppendToEnd(new_buffers);
+
+  if (selected_range_ == range_for_new_buffers &&
+      !deleted_buffers.empty() && next_buffer != deleted_buffers.end()) {
+    UpdateTrackBuffer(range_for_new_buffers_itr, deleted_buffers, next_buffer);
   }
-  return itr;
 }
 
-SourceBufferStream::RangeList::iterator
-SourceBufferStream::ResolveEndOverlaps(
-    const RangeList::iterator& range_itr, SourceBufferRange* new_range) {
-  RangeList::iterator itr = range_itr;
-  while (itr != ranges_.end() && new_range->EndOverlaps(**itr)) {
-    DCHECK_NE(*itr, selected_range_);
-    delete *itr;
-    itr = ranges_.erase(itr);
+void SourceBufferStream::ResolveCompleteOverlaps(
+    const RangeList::iterator& range_with_new_buffers_itr) {
+  SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
+  RangeList::iterator next_range_itr = range_with_new_buffers_itr;
+  next_range_itr++;
+
+  while (next_range_itr != ranges_.end() &&
+         range_with_new_buffers->CompletelyOverlaps(**next_range_itr)) {
+    if (*next_range_itr == selected_range_) {
+      // Delete everything from the selected range that |new_range| overlaps,
+      // and save the next buffers.
+      BufferQueue deleted_buffers;
+      BufferQueue::iterator next_buffer;
+      (*next_range_itr)->DeleteAll(&deleted_buffers, &next_buffer);
+
+      // Update |selected_range_| then update the track buffer.
+      selected_range_ = range_with_new_buffers;

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

This might not be necessary. It looks like UpdateTrackBuffer() does this.

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Yes, you're right, removed and added DCHECK_NE(selected_range_, *next_range_itr)

+      UpdateTrackBuffer(range_with_new_buffers_itr,
+                        deleted_buffers, next_buffer);
+    }
+    delete *next_range_itr;
+    next_range_itr = ranges_.erase(next_range_itr);
   }
-  return itr;
+}
+
+void SourceBufferStream::ResolveEndOverlap(
+    const RangeList::iterator& range_with_new_buffers_itr) {
+  SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
+  RangeList::iterator next_range_itr = range_with_new_buffers_itr;
+  next_range_itr++;
+
+  if (next_range_itr == ranges_.end() ||
+      !range_with_new_buffers->EndOverlaps(**next_range_itr)) {
+    return;
+  }
+
+  // Split the overlapped range after |range_with_new_buffers|'s last buffer
+  // overlaps. Now |overlapped_range| contains only the buffers that do not
+  // belong in |ranges_| anymore, and |new_next_range| contains buffers that
+  // go after |range_with_new_buffers| (without overlap).
+  scoped_ptr<SourceBufferRange> overlapped_range(*next_range_itr);
+  SourceBufferRange* new_next_range =
+      overlapped_range->SplitRange(range_with_new_buffers->GetEndTimestamp());
+
+  // Remove |overlapped_range| from the range list, since it now contains only
+  // buffers that are redundant with |range_with_new_buffers|.
+  next_range_itr = ranges_.erase(next_range_itr);

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

I think it would be better to put this above the previous line so that it is
closer to the ownership transfer.

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Good idea, done.

+
+  // If there were non-overlapped buffers, add the new range to |ranges_|.
+  if (new_next_range)
+    ranges_.insert(next_range_itr, new_next_range);
+
+  // If we didn't overlap a selected range, return.
+  if (selected_range_ != overlapped_range.get())
+    return;
+
+  // If the next buffer was in the |new_next_range| half of the overlapped
+  // range, then the |selected_range_| is now |new_next_range|.
+  if (new_next_range &&
+      new_next_range->GetNextTimestamp() != kNoTimestamp()) {
+    selected_range_ = new_next_range;
+    return;
+  }
+
+  // Otherwise, update track buffer with overlapped buffers.
+  BufferQueue deleted_buffers;
+  scoped_refptr<StreamParserBuffer> buffer;
+  while (overlapped_range->GetNextBuffer(&buffer)) {
+    deleted_buffers.push_back(buffer);
+  }
+  BufferQueue::iterator next_buffer = deleted_buffers.begin();
+  UpdateTrackBuffer(range_with_new_buffers_itr, deleted_buffers, next_buffer);

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

You might want to add a comment here indicating that selected_range_ gets
overridden in this call so it doesn't look like we are keeping a pointer to
overlapped_range around.

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Added a DCHECK and comment.

+}
+
+void SourceBufferStream::UpdateTrackBuffer(
+    const RangeList::iterator& range_with_new_buffers_itr,
+    const BufferQueue& deleted_buffers,
+    const BufferQueue::iterator& next_buffer) {
+  DCHECK(!deleted_buffers.empty() && next_buffer != deleted_buffers.end());
+
+  SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
+
+  // Seek to the next keyframe after (or equal to) the timestamp of the next
+  // buffer being overlapped.
+  range_with_new_buffers->SeekAfter((*next_buffer)->GetTimestamp());
+  selected_range_ = range_with_new_buffers;
+
+  base::TimeDelta next_keyframe_timestamp =
+      range_with_new_buffers->GetNextTimestamp();
+
+  if (track_buffer_.empty()) {
+    // Add all the old buffers up until |next_keyframe_timestamp| into
+    // |track_buffer_|. If there was no next keyframe, then we add all buffers
+    // into |track_buffer_|.
+    BufferQueue::iterator next_buffer_itr = next_buffer;
+    while (next_buffer_itr != deleted_buffers.end() &&
+           (next_keyframe_timestamp == kNoTimestamp() ||
+            (*next_buffer_itr)->GetTimestamp() < next_keyframe_timestamp)) {
+      track_buffer_.push_back(*next_buffer_itr);
+      next_buffer_itr++;
+    }
+  }
+
+  // See if the next range contains the keyframe after the end of the
+  // |track_buffer_|, and if so, change |selected_range_|.
+  if (next_keyframe_timestamp == kNoTimestamp()) {
+    DCHECK(!track_buffer_.empty());
+    RangeList::iterator next_range_itr = range_with_new_buffers_itr;
+    next_range_itr++;
+    if (next_range_itr != ranges_.end()) {

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

I don't think I really understand what is going on here. Is this where the track
buffer goes off the end of the old range, there is a gap, but overlaps with the
next range?

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Close: the track buffer should never overlap with the next range, but it might
be adjacent to it. This logic is used in between
End_Overlap_Selected_OverlappedByNew_2. Let me copy/paste that example:
 
 index:  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
 old  :           |A*a*a a a A a a a a|
 new  :  B b b b b B b
 after: |B b b b b B b|     |A a a a a|
 track:             |a a a a|

So in this beginning of this method, we set |selected_range_| to
|range_with_new_buffers|, which is the left-most range with the B's in it. The
while loop adds the A's in the track buffer.  

Now this weird logic from lines 396-407 is checking to see if the track buffer
ends where the next range begins. In the EOS_OBN_2 example, this block is all
true, and we set the |selected_range_| to the right-most range with the A's in
it, so that the track buffer seamlessly transitions to the existing data.

If lines 396-407 were omitted, then the |selected_range_| is the left-most
range. Because it doesn't have a keyframe after the end of the track buffer,  it
is in the "waiting for next keyframe" mode. After the track buffer has been
depleted, you'd stall until you get the next keyframe in the left-most range...
which will be overlapping the right-most range.

Hope that makes sense... btw, it could make sense to delete lines 396-407 if we
did some conveniently placed garbage collecting. We should nail down the
simplifications, possibly in a follow-up CL.

+      (*next_range_itr)->SeekAfter(track_buffer_.back()->GetEndTimestamp());
+      if (IsNextInSequence(track_buffer_.back(),
+                           (*next_range_itr)->GetNextTimestamp())) {
+        selected_range_ = *next_range_itr;
+      }
+    }
+  }
 }
 
 void SourceBufferStream::MergeWithAdjacentRangeIfNecessary(
-    const RangeList::iterator& itr, SourceBufferRange* new_range) {
-  if (itr != ranges_.end() && new_range->CanAppendToEnd(**itr)) {
-    bool transfer_current_position = selected_range_ == *itr;
-    new_range->AppendToEnd(**itr, transfer_current_position);
+    const RangeList::iterator& range_with_new_buffers_itr) {
+  SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
+  RangeList::iterator next_range_itr = range_with_new_buffers_itr;
+  next_range_itr++;
+
+  if (next_range_itr != ranges_.end() &&
+      range_with_new_buffers->CanAppendToEnd(**next_range_itr)) {
+    bool transfer_current_position = selected_range_ == *next_range_itr;
+    range_with_new_buffers->AppendToEnd(**next_range_itr,
+                                        transfer_current_position);
     // Update |selected_range_| pointer if |range| has become selected after
     // merges.
     if (transfer_current_position)
-      selected_range_ = new_range;
+      selected_range_ = range_with_new_buffers;
 
-    delete *itr;
-    ranges_.erase(itr);
+    delete *next_range_itr;
+    ranges_.erase(next_range_itr);
   }
 }
 
 void SourceBufferStream::Seek(base::TimeDelta timestamp) {
   selected_range_ = NULL;
   track_buffer_.clear();
-  waiting_for_keyframe_ = false;
 
   seek_buffer_timestamp_ = timestamp;
   seek_pending_ = true;
 
   RangeList::iterator itr = ranges_.end();
   for (itr = ranges_.begin(); itr != ranges_.end(); itr++) {
     if ((*itr)->CanSeekTo(timestamp))
       break;
   }
 
@@ skipping 18 matching lines @@
 std::list<SourceBufferStream::Timespan>
 SourceBufferStream::GetBufferedTime() const {
   std::list<Timespan> timespans;
   for (RangeList::const_iterator itr = ranges_.begin();
        itr != ranges_.end(); itr++) {
     timespans.push_back((*itr)->GetBufferedTime());
   }
   return timespans;
 }
 
-SourceBufferRange::SourceBufferRange()
-    : next_buffer_index_(-1) {
-}
-
-void SourceBufferRange::Append(const BufferQueue& new_buffers) {
-  base::TimeDelta start_timestamp = new_buffers.front()->GetTimestamp();
-
-  if (!buffers_.empty() && start_timestamp < BufferedEnd()) {
-    // We are overwriting existing data, so find the starting point where
-    // things will get overwritten.
-    BufferQueue::iterator starting_point =
-        std::lower_bound(buffers_.begin(), buffers_.end(),
-                         new_buffers.front(),
-                         BufferComparator);
-
-    // Remove everything from |starting_point| onward.
-    buffers_.erase(starting_point, buffers_.end());
-  }
-
-  // Append data.
+SourceBufferRange::SourceBufferRange(const BufferQueue& new_buffers)
+    : next_buffer_index_(-1),
+      waiting_for_keyframe_(false),
+      next_keyframe_timestamp_(kNoTimestamp()) {
+  DCHECK(!new_buffers.empty());
+  DCHECK(new_buffers.front()->IsKeyframe());
   AppendToEnd(new_buffers);
 }
 
 void SourceBufferRange::AppendToEnd(const BufferQueue& new_buffers) {
   for (BufferQueue::const_iterator itr = new_buffers.begin();
        itr != new_buffers.end(); itr++) {
     DCHECK((*itr)->GetDuration() > base::TimeDelta());
     DCHECK((*itr)->GetTimestamp() != kNoTimestamp());
     buffers_.push_back(*itr);
     if ((*itr)->IsKeyframe()) {
       keyframe_map_.insert(
           std::make_pair((*itr)->GetTimestamp(), buffers_.size() - 1));
+
+      if (waiting_for_keyframe_ &&
+          (*itr)->GetTimestamp() >= next_keyframe_timestamp_) {
+        next_buffer_index_ = buffers_.size() - 1;
+        next_keyframe_timestamp_ = base::TimeDelta();
+        waiting_for_keyframe_ = false;
+      }
     }
   }
 }
 
 void SourceBufferRange::Seek(base::TimeDelta timestamp) {
   DCHECK(CanSeekTo(timestamp));
   DCHECK(!keyframe_map_.empty());
 
+  next_keyframe_timestamp_ = base::TimeDelta();
+  waiting_for_keyframe_ = false;
+
   KeyframeMap::iterator result = keyframe_map_.lower_bound(timestamp);
   // lower_bound() returns the first element >= |timestamp|, so we want the
   // previous element if it did not return the element exactly equal to
   // |timestamp|.
   if (result == keyframe_map_.end() || result->first != timestamp) {
     DCHECK(result != keyframe_map_.begin());
     result--;
   }
   next_buffer_index_ = result->second;
   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
 }
 
-base::TimeDelta SourceBufferRange::SeekAfter(base::TimeDelta timestamp) {
-  DCHECK_EQ(BelongsToRange(timestamp), 0);
+void SourceBufferRange::SeekAfter(base::TimeDelta timestamp) {
   DCHECK(!keyframe_map_.empty());
 
   // lower_bound() returns the first element >= |timestamp|, so |result| is the
   // value that we want.
   KeyframeMap::iterator result = keyframe_map_.lower_bound(timestamp);
 
   // If there isn't a keyframe after |timestamp|, then seek to end and return
   // kNoTimestamp to signal such.
   if (result == keyframe_map_.end()) {
-    next_buffer_index_ = buffers_.size();
-    return kNoTimestamp();
+    waiting_for_keyframe_ = true;
+    next_buffer_index_ = -1;
+    next_keyframe_timestamp_ = timestamp;
+    return;
   }
 
   next_buffer_index_ = result->second;
   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
-  return result->first;
 }
 
+SourceBufferRange* SourceBufferRange::SplitRange(base::TimeDelta timestamp) {
+  // Find the first keyframe after |timestamp|.
+  KeyframeMap::iterator new_beginning_keyframe =
+      keyframe_map_.lower_bound(timestamp);
+
+  // If there is no keyframe after |timestamp|, we can't split the range.
+  if (new_beginning_keyframe == keyframe_map_.end())
+    return NULL;
+
+  int keyframe_index = new_beginning_keyframe->second;
+  DCHECK_LT(keyframe_index, static_cast<int>(buffers_.size()));
+
+  BufferQueue removed_buffers;
+  BufferQueue::iterator next_buffer;
+  DeleteAfter(
+      buffers_.begin() + keyframe_index, &removed_buffers, &next_buffer);
+
+  SourceBufferRange* split_range = new SourceBufferRange(removed_buffers);
+  if (next_buffer != removed_buffers.end()) {
+    split_range->next_buffer_index_ = next_buffer - removed_buffers.begin();
+  }
+  return split_range;
+}
+
+void SourceBufferRange::DeleteAll(BufferQueue* removed_buffers,
+                                  BufferQueue::iterator* next_buffer) {
+  DeleteAfter(buffers_.begin(), removed_buffers, next_buffer);
+}
+
+void SourceBufferRange::DeleteAfter(
+    scoped_refptr<StreamParserBuffer> buffer,
+    BufferQueue* removed_buffers,
+    BufferQueue::iterator* next_buffer) {
+  // Find the place in |buffers_| where we will begin deleting data.
+  BufferQueue::iterator starting_point =
+      std::lower_bound(buffers_.begin(), buffers_.end(),
+                       buffer,
+                       BufferComparator);
+  DeleteAfter(starting_point, removed_buffers, next_buffer);
+}
+
+void SourceBufferRange::DeleteAfter(
+    BufferQueue::iterator starting_point,
+    BufferQueue* removed_buffers,
+    BufferQueue::iterator* next_buffer) {
+  // Return if we're not deleting anything.
+  if (starting_point == buffers_.end())
+    return;
+
+  // Find the first keyframe after |starting_point|.
+  KeyframeMap::iterator starting_point_keyframe =
+      keyframe_map_.lower_bound((*starting_point)->GetTimestamp());
+
+  // Save the buffers we're about to delete.
+  if (removed_buffers) {
+    BufferQueue saved(starting_point, buffers_.end());
+    removed_buffers->swap(saved);
+    if (next_buffer)
+      *next_buffer = removed_buffers->end();
+  }
+
+  // Reset the next buffer index if we will be deleting the buffer that's next
+  // in sequence.
+  base::TimeDelta next_buffer_timestamp = GetNextTimestamp();
+  if (next_buffer_timestamp != kNoTimestamp() &&
+      next_buffer_timestamp >= (*starting_point)->GetTimestamp()) {
+    if (removed_buffers && next_buffer) {
+      int starting_offset = starting_point - buffers_.begin();
+      int next_buffer_offset = next_buffer_index_ - starting_offset;
+      DCHECK_GE(next_buffer_offset, 0);
+      *next_buffer = removed_buffers->begin() + next_buffer_offset;
+    }
+    next_buffer_index_ = -1;
+  }
+
+  // Remove keyframes from |starting_point| onward.
+  keyframe_map_.erase(starting_point_keyframe, keyframe_map_.end());
+
+  // Remove everything from |starting_point| onward.
+  buffers_.erase(starting_point, buffers_.end());
+}
 
 bool SourceBufferRange::GetNextBuffer(
     scoped_refptr<StreamParserBuffer>* out_buffer) {
+  if (waiting_for_keyframe_ ||
+      next_buffer_index_ >= static_cast<int>(buffers_.size())) {
+    return false;
+  }
+
   DCHECK_GE(next_buffer_index_, 0);
-  if (next_buffer_index_ >= static_cast<int>(buffers_.size()))
-    return false;
-
   *out_buffer = buffers_.at(next_buffer_index_);
   next_buffer_index_++;
   return true;
 }
 
 base::TimeDelta SourceBufferRange::GetNextTimestamp() const {
-  DCHECK_GE(next_buffer_index_, 0);
   DCHECK(!buffers_.empty());
 
-  if (next_buffer_index_ >= static_cast<int>(buffers_.size()))
-    return buffers_.back()->GetEndTimestamp();
+  if (next_buffer_index_ >= static_cast<int>(buffers_.size()) ||
+      next_buffer_index_ < 0 || waiting_for_keyframe_) {
+    return kNoTimestamp();
+  }
 
   return buffers_.at(next_buffer_index_)->GetTimestamp();
 }
 
+base::TimeDelta SourceBufferRange::GetEndTimestamp() const {
+  return BufferedEnd();

[acolwell GONE FROM CHROMIUM, 2012/05/22 19:35:23]

nit: One of these two methods should be removed since they are doing the same
thing.

[vrk (LEFT CHROMIUM), 2012/05/24 20:06:30]

Done.

+}
+
 SourceBufferStream::Timespan
 SourceBufferRange::GetBufferedTime() const {
   return std::make_pair(BufferedStart(), BufferedEnd());
 }
 
 void SourceBufferRange::AppendToEnd(const SourceBufferRange& range,
                                     bool transfer_current_position) {
   DCHECK(CanAppendToEnd(range));
   DCHECK(!buffers_.empty());
 
@@ skipping 37 matching lines @@
     const SourceBufferRange& range) const {
   return BufferedStart() <= range.BufferedStart() &&
       BufferedEnd() >= range.BufferedEnd();
 }
 
 bool SourceBufferRange::EndOverlaps(const SourceBufferRange& range) const {
   return range.BufferedStart() < BufferedEnd() &&
       BufferedEnd() < range.BufferedEnd();
 }
 
-bool SourceBufferRange::IsStartOverlappedBy(const BufferQueue& buffers) const {
-  base::TimeDelta start_timestamp = buffers.front()->GetTimestamp();
-  return BufferedStart() < start_timestamp && start_timestamp < BufferedEnd();
-}
-
-bool SourceBufferRange::IsEndOverlappedBy(const BufferQueue& buffers) const {
-  base::TimeDelta end_timestamp = buffers.back()->GetEndTimestamp();
-  return BufferedStart() < end_timestamp && end_timestamp < BufferedEnd();
-}
-
-bool SourceBufferRange::IsCompletelyOverlappedBy(
-    const BufferQueue& buffers) const {
-  base::TimeDelta start_timestamp = buffers.front()->GetTimestamp();
-  base::TimeDelta end_timestamp = buffers.back()->GetEndTimestamp();
-  return start_timestamp <= BufferedStart() && BufferedEnd() <= end_timestamp;
-}
-
 base::TimeDelta SourceBufferRange::BufferedStart() const {
   if (buffers_.empty())
     return kNoTimestamp();
-
   return buffers_.front()->GetTimestamp();
 }
 
 base::TimeDelta SourceBufferRange::BufferedEnd() const {
   if (buffers_.empty())
     return kNoTimestamp();
-
   return buffers_.back()->GetEndTimestamp();
 }
 
 }  // namespace media