Frame continuity is now tested as soon as a frame is inserted into the FrameBuffer.

webrtc/modules/video_coding/frame_buffer2.h

Index: webrtc/modules/video_coding/frame_buffer2.h
diff --git a/webrtc/modules/video_coding/frame_buffer2.h b/webrtc/modules/video_coding/frame_buffer2.h
index d0f896133f116cecef7491070c1ebd6508ae28ff..62ba8ae7af443913ed43b1ce7c905260193acb1e 100644
--- a/webrtc/modules/video_coding/frame_buffer2.h
+++ b/webrtc/modules/video_coding/frame_buffer2.h
@@ -14,15 +14,16 @@
 #include <array>
 #include <map>
 #include <memory>
-#include <set>
 #include <utility>
 
 #include "webrtc/base/constructormagic.h"
 #include "webrtc/base/criticalsection.h"
 #include "webrtc/base/event.h"
 #include "webrtc/base/thread_annotations.h"
+#include "webrtc/modules/video_coding/frame_object.h"
 #include "webrtc/modules/video_coding/include/video_coding_defines.h"
 #include "webrtc/modules/video_coding/inter_frame_delay.h"
+#include "webrtc/modules/video_coding/sequence_number_util.h"
 
 namespace webrtc {
 
@@ -32,8 +33,6 @@ class VCMTiming;
 
 namespace video_coding {
 
-class FrameObject;
-
 class FrameBuffer {
  public:
   enum ReturnReason { kFrameFound, kTimeout, kStopped };
@@ -42,12 +41,13 @@ class FrameBuffer {
               VCMJitterEstimator* jitter_estimator,
               VCMTiming* timing);
 
-  // Insert a frame into the frame buffer.
-  void InsertFrame(std::unique_ptr<FrameObject> frame);
+  // Insert a frame into the frame buffer. Returns the picture id
+  // of the last continuous frame or -1 if there is no continuous frame.
+  int InsertFrame(std::unique_ptr<FrameObject> frame);
 
   // Get the next frame for decoding. Will return at latest after
   // |max_wait_time_ms|.
-  //  - If a frame is availiable within |max_wait_time_ms| it will return
+  //  - If a frame is available within |max_wait_time_ms| it will return
   //    kFrameFound and set |frame_out| to the resulting frame.
   //  - If no frame is available after |max_wait_time_ms| it will return
   //    kTimeout.
@@ -70,33 +70,83 @@ class FrameBuffer {
   void Stop();
 
  private:
-  // FrameKey is a pair of (picture id, spatial layer).
-  using FrameKey = std::pair<uint16_t, uint8_t>;
+  struct FrameKey {
+    FrameKey() : picture_id(0), spatial_layer(0) {}
+    FrameKey(uint16_t picture_id, uint8_t spatial_layer)
+        : picture_id(picture_id), spatial_layer(spatial_layer) {}
+
+    bool operator<(const FrameKey& other) const {
+      if (picture_id == other.picture_id)
+        return spatial_layer < other.spatial_layer;
+      return AheadOf(other.picture_id, picture_id);
+    }
+
+    bool operator<=(const FrameKey& other) const { return !(other < *this); }
+
+    uint16_t picture_id;
+    uint8_t spatial_layer;
+  };
+
+  struct FrameInfo {
+    static constexpr size_t kMaxNumDependentFrames = 5;
+
+    // Which other frames that have unfulfilled dependencies on this frame.
+    FrameKey dependent_frames[kMaxNumDependentFrames];
+    size_t num_dependent_frames = 0;
+
+    // A frame is continiuous if have all its referenced/indirectly referenced
+    // frames.
+    //
+    // How many unfulfilled frames this frame have to become continuous.
+    size_t num_missing_continuous = 0;
 
-  // Comparator used to sort frames, first on their picture id, and second
-  // on their spatial layer.
-  struct FrameComp {
-    bool operator()(const FrameKey& f1, const FrameKey& f2) const;
+    // A frame is decodable if all its referenced frames have been decoded.
+    //
+    // How many unfulfilled frames this frame have to become decodable.
+    size_t num_missing_decodable = 0;
+
+    // If this frame is continuous or not.
+    bool continuous = false;
+
+    // The actual FrameObject.
+    std::unique_ptr<FrameObject> frame;
   };
 
-  // Determines whether a frame is continuous.
-  bool IsContinuous(const FrameObject& frame) const
+  using FrameMap = std::map<FrameKey, FrameInfo>;
+
+  // Update all directly dependent and indirectly dependent frames and mark
+  // them as continuous if all their references has been fulfilled.
+  void PropagateContinuity(const FrameMap::iterator start)

[danilchap, 2016/09/19 17:44:48]

remove const

[philipel, 2016/09/20 09:30:25]

Done.

+      EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+  // Mark the frame as decoded and updates all directly dependent frames.
+  void PropagateDecodability(const FrameInfo& info)
+      EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+  // Update the corresponding FrameInfo of |frame| and all FrameInfos that
+  // |frame| references.
+  // Return false if |frame| will never be decodable, true otherwise.
+  bool UpdateFrameInfoWithIncomingFrame(const FrameObject& frame,
+                                        FrameMap::iterator info)
       EXCLUSIVE_LOCKS_REQUIRED(crit_);
 
-  // Keep track of decoded frames.
-  std::set<FrameKey, FrameComp> decoded_frames_ GUARDED_BY(crit_);
+  // Advances |last_decoded_frame_it_| to |decoded| and remove old
+  // frame info.
+  void AdvanceLastDecodedFrame(const FrameMap::iterator decoded)

[danilchap, 2016/09/19 17:44:48]

ditto

[philipel, 2016/09/20 09:30:25]

Done.

+      EXCLUSIVE_LOCKS_REQUIRED(crit_);
 
-  // The actual buffer that holds the FrameObjects.
-  std::map<FrameKey, std::unique_ptr<FrameObject>, FrameComp> frames_
-      GUARDED_BY(crit_);
+  FrameMap frames_ GUARDED_BY(crit_);
 
   rtc::CriticalSection crit_;
   Clock* const clock_;
-  rtc::Event frame_inserted_event_;
+  rtc::Event new_countinuous_frame_event_;
   VCMJitterEstimator* const jitter_estimator_ GUARDED_BY(crit_);
   VCMTiming* const timing_ GUARDED_BY(crit_);
   VCMInterFrameDelay inter_frame_delay_ GUARDED_BY(crit_);
-  int newest_picture_id_ GUARDED_BY(crit_);
+  FrameMap::iterator last_decoded_frame_it_ GUARDED_BY(crit_);

[danilchap, 2016/09/19 17:44:48]

the logic might be simplified if instead of keeping border line between decoded
and might be decoded frames you would keep
std::set<FrameKey> decoded_; (for those frames no FrameInfo member is relevant)
and buffed frames_ separately. That would eat num_frames_history variable too
(== decoded_.size()).

[philipel, 2016/09/20 09:30:25]

Well, that is how it worked in PS3, and then I changed so that we only use one
map to store both history and buffered frames.

I think it's cleaner for two reasons:
 - We don't have to look in both history and buffered frames to test whether a
frame is continuous or not.
 - We don't have to perform as many finds in the two different maps to get the
information we need to insert/extract a frame.

[danilchap, 2016/09/20 11:15:08]

no, PS3 did it differently than what I propose here:
once frame has been decoded, i.e. returned by NextFrame, you do not need to keep
FrameInfo about it: it is continous, have no missing references, FrameObject is
gone and since PropogateDecodability just called, back references are not needed
either. All you need is FrameKey. And, sometimes, last_decoded_key =
*decoded_.rbegin();
So you can add it to decoded_ and remove from frames_.

Whenever you search, you treat decoded frames and not yet decoded frames
differently. If found in decoded (for num_missing_decodable update), no point to
search in frames_.
PropagateContinuity can't find already decoded frames because they do not have
any missing frames for continuity.

This is just a suggestion, if you find current way cleaner, keep it.

[philipel, 2016/09/20 11:44:44]

I'm not sure I understand your suggestion.

[philipel, 2016/09/20 13:11:08]

Unfortunately it required a few more changes since an iterator can't be used to
describe the last continuous frame, which would have to be replaced by a
FrameKey and a bool to describe if the FrameKey is valid or not, and also a few
more finds.

[danilchap, 2016/09/20 13:45:24]

Hm, yes, sorry, missed scenario last_continuous_frame == last_decoded_frame.
replacing last_continuous_frame with rtc::Optional<FrameKey> doesn't make code
that much cleaner.

+  FrameMap::iterator last_continuous_frame_it_ GUARDED_BY(crit_);
+  int num_frames_history_ GUARDED_BY(crit_);
+  int num_frames_buffered_ GUARDED_BY(crit_);
   bool stopped_ GUARDED_BY(crit_);
   VCMVideoProtection protection_mode_ GUARDED_BY(crit_);