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 {
+
+// Comparison function for two Buffers based on timestamp.
+static bool BufferComparitor(scoped_refptr<media::Buffer> first,
+                             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();
+  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;
+    }
+  }
+
+  bool create_new_range = true;
+  RangeList::iterator itr = ranges_.begin();
+  while (itr != ranges_.end()) {
+    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;
+  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())
+      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()) {
+    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_)
+    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());
+    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()))
+    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())
+      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;
+  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 &&
+      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())
+    return kNoTimestamp();
+
+  return BufferedEnd() + buffers_.back()->GetDuration() / 3;
+}
+
+void SourceBufferStream::Range::Reset() {
+  keyframe_map_.clear();
+  buffers_.clear();
+  is_selected_range_ = false;
+}
+
+}  // namespace media