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..3d182bf45b6b7c23d335954d37f4ca847de52911
--- /dev/null
+++ b/media/filters/source_buffer_stream.cc
@@ -0,0 +1,290 @@
+// 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>
+
+namespace {

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

We don't do anonymous namespaces in the media code. The static below is
sufficient to narrow the scope to this file.

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+
+// Comparison function for two Buffers based on timestamp.
+static bool BufferComparitor(scoped_refptr<media::Buffer> first,

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Comparator

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+                             scoped_refptr<media::Buffer> second) {
+  return first->GetTimestamp() < second->GetTimestamp();
+}
+
+}  // namespace
+
+namespace media {
+
+SourceBufferStream::SourceBufferStream()
+    : seek_pending_(false),
+      selected_range_(NULL) {
+}
+
+SourceBufferStream::~SourceBufferStream() {
+  while (!ranges_.empty()) {
+    delete ranges_.front();
+    ranges_.pop_front();
+  }
+}
+
+void SourceBufferStream::Append(
+    const SourceBufferStream::BufferQueue& buffers) {
+  base::TimeDelta start_timestamp = buffers.front()->GetTimestamp();

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

DCHECK(!buffers.empty())?

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+  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;

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Do we really want to silently drop this data? Perhaps add a bool return value so
that an error can be propagated to JavaScript?

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Good idea. Bool added!

+    }
+  }
+
+  bool create_new_range = true;
+  RangeList::iterator itr = ranges_.begin();
+  while (itr != ranges_.end()) {

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

nit: consider using for instead of while here

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+    int range_value = (*itr)->BelongsToRange(start_timestamp);
+    if (range_value > 0)
+      break;
+
+    if (range_value == 0) {
+      // Found an existing range into which we can append buffers.
+      create_new_range = false;
+      break;
+    }
+    itr++;
+  }
+
+  RangeList::iterator current = itr;

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

I don't think current & next actually make things clearer since when next gets
assigned, it is equal to current. How about just using itr everywhere since you
only care about one iterator position this whole time.

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+  if (create_new_range)
+    current = ranges_.insert(itr, new Range());
+  Range* range = *current;
+  RangeList::iterator next = ++current;
+
+  // Append buffers to the appropriate range.
+  range->Append(buffers);
+
+  // Handle overlaps if they were created.
+  while (next != ranges_.end() && range->EndOverlaps(*next)) {
+    DCHECK(!(*next)->is_selected_range());
+    delete *next;
+    next = ranges_.erase(next);
+  }
+
+  // Merge with neighbor if necessary.
+  if (next != ranges_.end() && range->CanMerge(*next)) {
+    range->Merge(*next);
+    // Update |selected_range_| pointer if |range| has become selected after
+    // merges.
+    if (range->is_selected_range())

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Do we really need is_selected_range()? Can't we just do a (selected_range_ ==
*next) here? Putting this in Range feels like an encapsulation leak.

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Yeah I didn't like that either! Removed, thanks!

+      selected_range_ = range;
+
+    delete *next;
+    ranges_.erase(next);
+  }
+
+  // Finally, try to complete pending seek if one exists.
+  if (seek_pending_)
+    Seek(seek_buffer_timestamp_);
+
+  DCHECK(IsRangeListSorted());
+}
+
+void SourceBufferStream::Seek(base::TimeDelta timestamp) {
+  if (selected_range_) {
+    selected_range_->set_selected_range(false);
+    selected_range_ = NULL;
+  }
+
+  seek_buffer_timestamp_ = timestamp;
+  seek_pending_ = true;
+
+  RangeList::iterator itr = ranges_.begin();
+  bool range_found = false;
+  while (itr != ranges_.end()) {

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

nit: use for here

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done, and cleaned up some surrounding logic.

+    if ((*itr)->CanSeekTo(timestamp)) {
+      range_found = true;
+      break;
+    }
+    itr++;
+  }
+
+  if (!range_found)
+    return;
+
+  selected_range_ = *itr;
+  selected_range_->set_selected_range(true);
+  selected_range_->Seek(timestamp);
+  seek_pending_ = false;
+}
+
+bool SourceBufferStream::GetNextBuffer(scoped_refptr<Buffer>* out_buffer) {
+  if (!selected_range_)

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

nit: Can combine with the return below. 
selected_range_ && selected_range_->GetNextBuffer(out_buffer);

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+    return false;
+  return 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;
+}
+
+bool SourceBufferStream::IsRangeListSorted() const {
+  base::TimeDelta prev = kNoTimestamp();
+  for (RangeList::const_iterator itr = ranges_.begin();
+       itr != ranges_.end(); itr++) {
+    Timespan buffered = (*itr)->GetBufferedTime();
+    if (prev != kNoTimestamp() && prev > buffered.first)
+      return false;
+    prev = buffered.second;
+  }
+  return true;
+}
+
+SourceBufferStream::Range::Range()
+    : is_selected_range_(false),
+      next_buffer_index_(-1) {
+}
+
+void SourceBufferStream::Range::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(),
+                         BufferComparitor);
+
+    // Remove everything from |starting_point| onward.
+    buffers_.erase(starting_point, buffers_.end());
+  }
+
+  // Append data.
+  AppendToEnd(new_buffers);
+}
+
+void SourceBufferStream::Range::AppendToEnd(const BufferQueue& new_buffers) {
+  for (BufferQueue::const_iterator itr = new_buffers.begin();
+       itr != new_buffers.end(); itr++) {
+    buffers_.push_back(*itr);
+    if ((*itr)->IsKeyframe()) {
+      keyframe_map_.insert(
+          std::make_pair((*itr)->GetTimestamp(), buffers_.size() - 1));
+    }
+  }
+}
+
+void SourceBufferStream::Range::Seek(base::TimeDelta timestamp) {
+  DCHECK(is_selected_range_);
+  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());

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Shouldn't this be before the if? Putting it here assumes that
keyframe_map_.begin()->first can never match timestamp. It isn't clear to me
that's a valid assumption.

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Talked offline!

BTW, I confirmed that if there's only one element, and |timestamp| is after that
element, then result is keyframe_map_.end(), and result-- gets you to the right
place.

For example:
keyframe_map_ = { (t=4, 0) }
result = keyframe_map_.lower_bound(t=5)  // result is keyframe_map_.end()
result--;  // result is (t=4, 0)

Of course, in this case:

keyframe_map_ = { (t=4, 0) }
result = keyframe_map_.lower_bound(t=3)  // result is (t=4, 0)

But this should never happen since the client should have appended the keyframe
for t=3 before appending t=3, which is why there's a DCHECK.

+    result--;
+  }
+  next_buffer_index_ = result->second;
+  DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
+}
+
+bool SourceBufferStream::Range::GetNextBuffer(
+    scoped_refptr<Buffer>* out_buffer) {
+  if (next_buffer_index_ >= static_cast<int>(buffers_.size()))

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

I think you need a next_buffer_index_ < 0 check here. Should this and the
existing check be DCHECKs?

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Yes, thanks! Done.
Chatted offline; the < 0 should be a DCHECK, he "next_buffer_index_ >=
static_cast<int>(buffers_.size()" should *not* be a DCHECK, since this is our
indication that we're stalling.

+    return false;
+
+  *out_buffer = buffers_.at(next_buffer_index_);
+  next_buffer_index_++;
+  return true;
+}
+
+SourceBufferStream::Timespan
+SourceBufferStream::Range::GetBufferedTime() const {
+  return std::make_pair<base::TimeDelta, base::TimeDelta>(
+      BufferedStart(), BufferedEnd());
+}
+
+void SourceBufferStream::Range::Merge(Range* range) {
+  DCHECK(CanMerge(range));
+
+  if (range->is_selected_range_) {
+    next_buffer_index_ = range->next_buffer_index_;
+    if (!buffers_.empty())

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Is it possible for buffers_.empty() to be true? It seems weird to merge into an
empty range.

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

You're right, shouldn't be true. I'll DCHECK instead.

+      next_buffer_index_ += buffers_.size() - 1;
+    is_selected_range_ = true;
+  }
+
+  AppendToEnd(range->buffers_);
+  range->Reset();
+}
+
+bool SourceBufferStream::Range::CanMerge(const Range* range) const {
+  return range->BufferedStart() >= BufferedEnd() &&
+      range->BufferedStart() <= MaxNextTimestamp();
+}
+
+int SourceBufferStream::Range::BelongsToRange(base::TimeDelta timestamp) const {
+  if (buffers_.empty() || MaxNextTimestamp() < timestamp)
+    return -1;

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

This and the line below seems reversed from what the comment in .h says.

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Oops, you're right! Originally I had done this backwards, then fixed the code
but not the comment :) fixed!

+  else if (BufferedStart() > timestamp)
+    return 1;
+  else
+    return 0;
+}
+
+bool SourceBufferStream::Range::CanSeekTo(base::TimeDelta timestamp) const {
+  if (buffers_.empty())
+    return false;
+
+  return buffers_.front()->GetTimestamp() <= timestamp &&

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Use BufferedStart() & BufferedEnd() here & drop the condition above?

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+      buffers_.back()->GetTimestamp() >= timestamp;
+}
+
+bool SourceBufferStream::Range::EndOverlaps(const Range* range) const {
+  return range->BufferedStart() < BufferedEnd();
+}
+
+base::TimeDelta SourceBufferStream::Range::BufferedStart() const {
+  if (buffers_.empty())
+    return kNoTimestamp();
+
+  return buffers_.front()->GetTimestamp();
+}
+
+base::TimeDelta SourceBufferStream::Range::BufferedEnd() const {
+  if (buffers_.empty())
+    return kNoTimestamp();
+
+  return buffers_.back()->GetTimestamp() + buffers_.back()->GetDuration();
+}
+
+base::TimeDelta SourceBufferStream::Range::MaxNextTimestamp() const {
+  if (buffers_.empty())

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

Should this be a DCHECK?

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+    return kNoTimestamp();
+
+  return BufferedEnd() + buffers_.back()->GetDuration() / 3;

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

You might want to add a comment here. I realize this is a made up value, but it
wasn't clear to me initially that this is actually 1/3 of a duration past the
end of the last buffer in the queue.

You should also probably put a DCHECK in the append code somewhere that makes
sure the the GetDuration() always returns something  > 0 & != kNoTimestamp().

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Tried to write a comment, let me know if it doesn't make sense!
Done.

+}
+
+void SourceBufferStream::Range::Reset() {
+  keyframe_map_.clear();
+  buffers_.clear();
+  is_selected_range_ = false;

[acolwell GONE FROM CHROMIUM, 2012/04/26 19:51:38]

reset next_buffer_index_ too?

[vrk (LEFT CHROMIUM), 2012/04/27 23:19:30]

Done.

+}
+
+}  // namespace media