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|.

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

I believe this should this be "starting from the closest keyframe before
|timestamp|".

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

Done.

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

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

s/fufill/fulfill

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

Done.

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

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

How about calling this SourceBufferRange and placing this in the .cc file?
You'll have to update the forward declaration above too. That way you don't have
to expose implementation details of this class to other code.

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

Done.

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

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

Any reason this and CanMerge can't be const Range& ?

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

Changed things to const Range& where it made sense!

In Merge(), I'm modifying |range| by removing all its elements. I don't actually
have to do that since SouceBufferStream deletes Range immediately after Merge(),
but I thought it made more sense logically. Let me know if you want me to change
the behavior.

+    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

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

Any reason not to use -1 & 1 instead of the whole negative and positive ranges?

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

Changed to -1 and 1.

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

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

The method name and comment don't seem consistent. Is this supposed to tell me
whether the range has enough data to allow me to seek to the specified timestamp
or whether the range contains a buffer that has the specified timestamp?

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

The former. Fixed comment.

+
+    // Returns true if the end of this range contains buffers that overlaps with
+    // the beginning of |range|.
+    bool EndOverlaps(const Range* range) const;

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

const Range& ?

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

Done.

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

[acolwell GONE FROM CHROMIUM, 2012/04/26 00:52:34]

You should probably just change this to a static function within the .cc since
it is only used to DCHECK the sorted list invariant. It doesn't really need to
be a member method.

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

Done.

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