Add initial implementation of SourceBufferStream

media/filters/source_buffer_stream.cc

Index: media/filters/source_buffer_stream.cc
diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
new file mode 100644
index 0000000000000000000000000000000000000000..59bec9cf6bbc7968ae75e652dc2b6377b5efd05e
--- /dev/null
+++ b/media/filters/source_buffer_stream.cc
@@ -0,0 +1,346 @@
+// 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"
+
+// Comparison function for two Buffers based on timestamp.
+static bool BufferComparator(scoped_refptr<media::Buffer> first,
+                             scoped_refptr<media::Buffer> second) {
+  return first->GetTimestamp() < second->GetTimestamp();
+}
+
+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<Buffer> > BufferQueue;
+
+  SourceBufferRange();
+  void Append(const BufferQueue& buffers);

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

nit: add documentation for these methods.

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done.

+  void Seek(base::TimeDelta timestamp);
+  bool GetNextBuffer(scoped_refptr<Buffer>* out_buffer);
+  SourceBufferStream::Timespan GetBufferedTime() const;
+
+  // Moves 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 Merge(SourceBufferRange* range, bool transfer_current_position);
+  bool CanMerge(const SourceBufferRange& range) 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;

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

nit: This is really minor, but mind if we switch the values? 1 for before and -1
for after seems backwards to me. Either that or change the comment text to "1 if
this range is after |timestamp|". I slightly prefer the former just because it
indicates how the parameter relates to the range instead of the other way
around.

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Yeah, now that I've explained it outloud, it makes more sense the other way
around :) changed!

+
+  // 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 the end of this range contains buffers that overlaps with
+  // the beginning of |range|.
+  bool EndOverlaps(const SourceBufferRange& range) const;
+
+ private:
+  void AppendToEnd(const BufferQueue& buffers);

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

docs for these methods. 

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done.

+  base::TimeDelta BufferedStart() const;
+  base::TimeDelta BufferedEnd() const;
+  base::TimeDelta MaxNextTimestamp() const;
+  void Reset();
+
+  // 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();
+  int next_buffer_index_;
+
+  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;
+}
+
+namespace media {
+
+SourceBufferStream::SourceBufferStream()
+    : seek_pending_(false),
+      selected_range_(NULL) {

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

seek_buffer_timestamp_(kNoTimestamp()) ?

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Yes, thanks for the catch! Done.

+}
+
+SourceBufferStream::~SourceBufferStream() {
+  while (!ranges_.empty()) {
+    delete ranges_.front();
+    ranges_.pop_front();
+  }
+}
+
+bool SourceBufferStream::Append(
+    const SourceBufferStream::BufferQueue& buffers) {
+  DCHECK(!buffers.empty());
+  base::TimeDelta start_timestamp = buffers.front()->GetTimestamp();
+  base::TimeDelta end_timestamp = buffers.back()->GetTimestamp();
+
+  // Check to see if |buffers| will overlap the currently |selected_range_|,
+  // and if so, ignore this Append() request.
+  // TODO(vrk): Support end overlap properly. (crbug.com/125072)
+  if (selected_range_) {
+    Timespan selected_range_span = selected_range_->GetBufferedTime();
+    if (selected_range_span.second > start_timestamp &&
+        selected_range_span.first <= end_timestamp) {
+      return false;
+    }
+  }
+
+  bool create_new_range = true;
+  RangeList::iterator itr = ranges_.end();
+  for (itr = ranges_.begin(); itr != ranges_.end();itr++) {

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

nit: space after ;

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done.

+    int range_value = (*itr)->BelongsToRange(start_timestamp);
+    if (range_value > 0)

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

Please add a comment why we are breaking here. I'm assuming it's because we've
discovered that the timestamp is actually before the current range.

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done.

+      break;
+
+    if (range_value == 0) {
+      // Found an existing range into which we can append buffers.
+      create_new_range = false;
+      break;
+    }
+  }
+
+  if (create_new_range)

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

I think you might be able to reduce the subtlety of what is going on here by
replacing the create_new_range declaration with "SourceBufferRange* range =
NULL;" and then basing the create & insert on whether range is still NULL after
the loop exits.

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Good idea! Done.

+    itr = ranges_.insert(itr, new SourceBufferRange());

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

Before creating the new range object you should add a check here to make sure
that the first buffer is a keyframe . If it isn't this function should fail
return false. We definitely want a test case for this code path.

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done and modified/added test.

+  SourceBufferRange* range = *itr;
+
+  // Append buffers to the appropriate range.
+  range->Append(buffers);
+
+  // Increment |itr| to be the range after |range|.
+  itr++;
+
+  // Handle overlaps if they were created.
+  while (itr != ranges_.end() && range->EndOverlaps(*(*itr))) {
+    DCHECK_NE(*itr, selected_range_);
+    delete *itr;
+    itr = ranges_.erase(itr);
+  }
+
+  // Merge with neighbor if necessary.
+  if (itr != ranges_.end() && range->CanMerge(*(*itr))) {
+    bool transfer_current_position = selected_range_ == *itr;
+    range->Merge(*itr, transfer_current_position);
+    // Update |selected_range_| pointer if |range| has become selected after
+    // merges.
+    if (transfer_current_position)
+      selected_range_ = range;
+
+    delete *itr;
+    ranges_.erase(itr);
+  }
+
+  // Finally, try to complete pending seek if one exists.
+  if (seek_pending_)
+    Seek(seek_buffer_timestamp_);
+
+  DCHECK(IsRangeListSorted(ranges_));
+  return true;
+}
+
+void SourceBufferStream::Seek(base::TimeDelta timestamp) {
+  if (selected_range_)
+    selected_range_ = NULL;
+
+  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;
+  }
+
+  if (itr == ranges_.end())
+    return;
+
+  selected_range_ = *itr;
+  selected_range_->Seek(timestamp);
+  seek_pending_ = false;
+}
+
+bool SourceBufferStream::GetNextBuffer(scoped_refptr<Buffer>* out_buffer) {
+  return selected_range_ && selected_range_->GetNextBuffer(out_buffer);
+}
+
+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.
+  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));
+    }
+  }
+}
+
+void SourceBufferRange::Seek(base::TimeDelta timestamp) {
+  DCHECK(CanSeekTo(timestamp));
+  DCHECK(!keyframe_map_.empty());
+
+  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->first != timestamp) {
+    DCHECK(result != keyframe_map_.begin());
+    result--;
+  }
+  next_buffer_index_ = result->second;
+  DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
+}
+
+bool SourceBufferRange::GetNextBuffer(
+    scoped_refptr<Buffer>* out_buffer) {
+  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;
+}
+
+SourceBufferStream::Timespan
+SourceBufferRange::GetBufferedTime() const {
+  return std::make_pair<base::TimeDelta, base::TimeDelta>(

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

nit: Lint says you don't need the template parameters here. Is that true?

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

D'oh, yes, this is true! You can omit the template arguments if they can be
deduced. I omitted them above, actually! Removed.

+      BufferedStart(), BufferedEnd());
+}
+
+void SourceBufferRange::Merge(SourceBufferRange* range,

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

How about renaming this to AppendRange() instead of Merge()? That way making
range const SourceBufferRange& seems less awkward and we don't have to do the
unnecessary range->Reset() at the bottom. 

I think that's also the only call to Reset() so that method can go away too.

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done.

+                              bool transfer_current_position) {
+  DCHECK(CanMerge(*range));
+  DCHECK(!buffers_.empty());
+
+  if (transfer_current_position) {
+    next_buffer_index_ = range->next_buffer_index_;
+    next_buffer_index_ += buffers_.size();
+  }
+
+  AppendToEnd(range->buffers_);
+  range->Reset();
+}
+
+bool SourceBufferRange::CanMerge(const SourceBufferRange& range) const {
+  return range.BufferedStart() >= BufferedEnd() &&
+      range.BufferedStart() <= MaxNextTimestamp();
+}
+
+int SourceBufferRange::BelongsToRange(base::TimeDelta timestamp) const {
+  if (buffers_.empty() || MaxNextTimestamp() < timestamp)
+    return -1;
+  else if (BufferedStart() > timestamp)
+    return 1;
+  else
+    return 0;
+}
+
+bool SourceBufferRange::CanSeekTo(base::TimeDelta timestamp) const {
+  return BufferedStart() <= timestamp && BufferedEnd() > timestamp;

[acolwell GONE FROM CHROMIUM, 2012/04/29 18:13:06]

!keyframe_map_.empty() &&

[vrk (LEFT CHROMIUM), 2012/05/01 22:51:13]

Done.

+}
+
+bool SourceBufferRange::EndOverlaps(const SourceBufferRange& range) const {
+  return range.BufferedStart() < BufferedEnd();
+}
+
+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()->GetTimestamp() + buffers_.back()->GetDuration();
+}
+
+base::TimeDelta SourceBufferRange::MaxNextTimestamp() const {
+  DCHECK(!buffers_.empty());
+
+  // 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 the last buffer
+  // in the queue is considered the next buffer in this range.
+  return BufferedEnd() + buffers_.back()->GetDuration() / 3;
+}
+
+void SourceBufferRange::Reset() {
+  keyframe_map_.clear();
+  buffers_.clear();
+  next_buffer_index_ = -1;
+}
+
+}  // namespace media