Add initial implementation of SourceBufferStream

media/filters/source_buffer_stream.h

Index: media/filters/source_buffer_stream.h
diff --git a/media/filters/source_buffer_stream.h b/media/filters/source_buffer_stream.h
new file mode 100644
index 0000000000000000000000000000000000000000..5a5f9167e218ead73f91e0b8d97b303b51bcce37
--- /dev/null
+++ b/media/filters/source_buffer_stream.h
@@ -0,0 +1,144 @@
+// 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.
+
+#ifndef MEDIA_FILTERS_SOURCE_BUFFER_STREAM_H_
+#define MEDIA_FILTERS_SOURCE_BUFFER_STREAM_H_
+
+#include <deque>
+#include <list>
+#include <map>
+
+#include "base/basictypes.h"
+#include "base/memory/ref_counted.h"
+#include "media/base/buffers.h"
+#include "media/base/media_export.h"
+
+namespace media {
+
+class Range;
+
+// SourceBufferStream is a data structure that stores media Buffers in ranges.
+// Buffers can be appended out of presentation order. Buffers are retrieved by
+// seeking to the desired start point and calling GetNextBuffer(). Buffers are
+// returned in sequential presentation order.
+class MEDIA_EXPORT SourceBufferStream {
+ public:
+  typedef std::deque<scoped_refptr<Buffer> > BufferQueue;
+  typedef std::pair<base::TimeDelta, base::TimeDelta> Timespan;
+  typedef std::list<Timespan> TimespanList;
+
+  SourceBufferStream();
+  ~SourceBufferStream();
+
+  // Add the |buffers| to the SourceBufferStream. Buffers within the queue are
+  // expected to be in order, but multiple calls to Append() may add buffers out
+  // of order or overlapping.
+  // TODO(vrk): Implement proper end-overlapping. (crbug.com/125072)
+  // This may trigger garbage collection.
+  // TODO(vrk): Implement garbage collection. (crbug.com/125070)
+  void Append(const BufferQueue& buffers);
+
+  // Changes the SourceBufferStream's state so that it will start returning
+  // buffers starting from |timestamp|.
+  void Seek(base::TimeDelta timestamp);
+
+  // Fills |out_buffer| with a new buffer. Buffers are presented in order from
+  // the last call to Seek(). |out_buffer|'s timestamp may be earlier than the
+  // |timestamp| passed to the last Seek() call.
+  // Returns true if |out_buffer| is filled with a valid buffer, false if
+  // no Seek() has been called yet or if there is not enough data buffered to
+  // fufill the request.
+  bool GetNextBuffer(scoped_refptr<Buffer>* out_buffer);
+
+  // Returns a list of the buffered time ranges.
+  TimespanList GetBufferedTime() const;
+
+ private:
+  // Helper class representing a range of buffered data. All buffers in a Range
+  // are ordered sequentially in presentation order with no gaps.
+  class Range {
+   public:
+    Range();
+    void Append(const BufferQueue& buffers);
+    void Seek(base::TimeDelta timestamp);
+    bool GetNextBuffer(scoped_refptr<Buffer>* out_buffer);
+    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.
+    void Merge(Range* range);
+    bool CanMerge(const Range* 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, a negative value if
+    // |timestamp| appears before this range, or a positive value if |timestamp|
+    // appears after this range.
+    int BelongsToRange(base::TimeDelta timestamp) const;
+
+    // Returns true if a buffer with a starting timestamp of |timestamp| is
+    // buffered in this range, 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 Range* range) const;
+
+    void set_selected_range(bool is_current) {
+      is_selected_range_ = is_current;
+    }
+
+    bool is_selected_range() const {
+      return is_selected_range_;
+    }
+
+   private:
+    void AppendToEnd(const BufferQueue& buffers);
+    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_;
+
+    // True if the last call to Seek() was is in this Range, false otherwise.
+    bool is_selected_range_;
+
+    // Index into |buffers_| for the next buffer to be returned by
+    // GetBufferedTime();
+    int next_buffer_index_;
+
+    DISALLOW_COPY_AND_ASSIGN(Range);
+  };
+
+  bool IsRangeListSorted() const;
+
+  typedef std::list<Range*> RangeList;
+  // List of disjoint buffered ranges, ordered by start time.
+  RangeList ranges_;
+
+  // True if more data needs to be appended before the Seek() can complete,
+  // false if no Seek() has been requested or the Seek() is completed.
+  bool seek_pending_;
+
+  // Timestamp of the last request to Seek().
+  base::TimeDelta seek_buffer_timestamp_;
+
+  // Pointer to the seeked-to Range. This is the Range from which
+  // GetNextBuffer() calls are fulfilled.
+  Range* selected_range_;
+
+  DISALLOW_COPY_AND_ASSIGN(SourceBufferStream);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_FILTERS_SOURCE_BUFFER_STREAM_H_