Factor out PtsHeap into a reusable class.

Review URL: http://codereview.chromium.org/459009

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@33605 0039d316-1c4b-4281-b951-d872f2087c98

2 files changed, 106 insertions, 0 deletions

diff --git a/media/base/pts_heap.h b/media/base/pts_heap.h
new file mode 100644
index 0000000..7795d68
--- /dev/null
+++ b/media/base/pts_heap.h
@@ -0,0 +1,67 @@
+// Copyright (c) 2009 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_BASE_PTS_HEAP_H_
+#define MEDIA_BASE_PTS_HEAP_H_
+
+// The compressed frame are often in decode timestamp (dts) order, which
+// may not always be in presentation timestamp (pts) order. However, the
+// decoded frames will always be returned in pts order. Ideally, the pts could
+// be attached as metadata to each comprsesed frame, and the decoder would
+// pass it along in the uncompressed frame so that it can be used in render.
+// Some decoders, like FFmpeg, do not have this facility, so we use PtsHeap to
+// pass along this information and simulate the reodering.
+//
+// Here is an  illustration of why the reordering might be necessary.
+//
+//  Decode       PTS of         PTS of
+//  Call #      Buffer In     Buffer Out
+//    1             1             1
+//    2             3            --- <--- frame 3 buffered by Decoder
+//    3             2             2
+//    4             4             3  <--- copying timestamp 4 and 6 would be
+//    5             6             4  <-'  incorrect, which is why we sort and
+//    6             5             5       queue incoming timestamps
+//
+// The PtsHeap expects that for every Pop(), there was a corresponding Push().
+// It will CHECK fail otherwise.
+
+#include <queue>
+#include <vector>
+
+#include "base/time.h"
+
+namespace media {
+
+class PtsHeap {
+ public:
+  PtsHeap() {}
+
+  void Push(const base::TimeDelta& pts) { queue_.push(pts); }
+  void Pop() { queue_.pop(); }
+
+  const base::TimeDelta& Top() const { return queue_.top(); }
+  bool IsEmpty() const { return queue_.empty(); }
+
+ private:
+  struct PtsHeapOrdering {
+    bool operator()(const base::TimeDelta& lhs,
+                    const base::TimeDelta& rhs) const {
+      // std::priority_queue is a max-heap. We want lower timestamps to show up
+      // first so reverse the natural less-than comparison.
+      return rhs < lhs;
+    }
+  };
+  typedef std::priority_queue<base::TimeDelta,
+                              std::vector<base::TimeDelta>,
+                              PtsHeapOrdering> TimeQueue;
+
+  TimeQueue queue_;
+
+  DISALLOW_COPY_AND_ASSIGN(PtsHeap);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_BASE_PTS_HEAP_H_
diff --git a/media/base/pts_heap_unittest.cc b/media/base/pts_heap_unittest.cc
new file mode 100644
index 0000000..9bc919c
--- /dev/null
+++ b/media/base/pts_heap_unittest.cc
@@ -0,0 +1,39 @@
+// Copyright (c) 2009 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 "base/time.h"
+#include "media/base/pts_heap.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace media {
+
+TEST(PtsHeapTest, IsEmpty) {
+  const base::TimeDelta kTestPts1 = base::TimeDelta::FromMicroseconds(123);
+
+  PtsHeap heap;
+  ASSERT_TRUE(heap.IsEmpty());
+  heap.Push(kTestPts1);
+  ASSERT_FALSE(heap.IsEmpty());
+  heap.Pop();
+  ASSERT_TRUE(heap.IsEmpty());
+}
+
+TEST(PtsHeapTest, Ordering) {
+  const base::TimeDelta kTestPts1 = base::TimeDelta::FromMicroseconds(123);
+  const base::TimeDelta kTestPts2 = base::TimeDelta::FromMicroseconds(456);
+
+  PtsHeap heap;
+  heap.Push(kTestPts1);
+  heap.Push(kTestPts2);
+  heap.Push(kTestPts1);
+
+  EXPECT_TRUE(kTestPts1 == heap.Top());
+  heap.Pop();
+  EXPECT_TRUE(kTestPts1 == heap.Top());
+  heap.Pop();
+  EXPECT_TRUE(kTestPts2 == heap.Top());
+  heap.Pop();
+}
+
+}  // namespace media