relnote: Convert the map into a list in QuicStreamSequencer.

net/quic/quic_stream_sequencer.h

 // 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 NET_QUIC_QUIC_STREAM_SEQUENCER_H_
 #define NET_QUIC_QUIC_STREAM_SEQUENCER_H_
 
 #include <map>
 #include <string>
 
 #include "base/basictypes.h"
 #include "net/base/iovec.h"
 #include "net/quic/quic_protocol.h"
 
 namespace net {
 
 namespace test {
 class QuicStreamSequencerPeer;
 }  // namespace test
 
 class QuicSession;
 class ReliableQuicStream;
 
 // Buffers frames until we have something which can be passed
 // up to the next layer.
 class NET_EXPORT_PRIVATE QuicStreamSequencer {
  public:
+  // A contiguous segment received by a QUIC stream.
+  struct FrameData {
+    FrameData(QuicStreamOffset offset, std::string segment);
+
+    const QuicStreamOffset offset;
+    std::string segment;
+  };
+
+  // TODO(alyssar) use something better than strings.
+  // Maybe write new frames into a ring buffer, and keep track of consumed
+  // bytes, and gaps.
+  typedef std::list<FrameData> FrameList;
+
   explicit QuicStreamSequencer(ReliableQuicStream* quic_stream);
   virtual ~QuicStreamSequencer();
 
   // If the frame is the next one we need in order to process in-order data,
   // ProcessData will be immediately called on the stream until all buffered
   // data is processed or the stream fails to consume data.  Any unconsumed
   // data will be buffered. If the frame is not the next in line, it will be
   // buffered.
   void OnStreamFrame(const QuicStreamFrame& frame);
 
@@ skipping 32 matching lines @@
 
   int num_duplicate_frames_received() const {
     return num_duplicate_frames_received_;
   }
 
   int num_early_frames_received() const { return num_early_frames_received_; }
 
  private:
   friend class test::QuicStreamSequencerPeer;
 
+  // Finds the place the frame should be inserted.  If an identical frame is
+  // present, stops on the identical frame.
+  FrameList::iterator FindInsertionPoint(const QuicStreamFrame& frame);
+
   // Returns true if |frame| contains data which overlaps buffered data
   // (indicating an invalid stream frame has been received).
-  bool FrameOverlapsBufferedData(const QuicStreamFrame& frame) const;
+  bool FrameOverlapsBufferedData(
+      const QuicStreamFrame& frame,
+      FrameList::const_iterator insertion_point) const;
 
   // Returns true if the sequencer has received this frame before.
-  bool IsDuplicate(const QuicStreamFrame& frame) const;
+  bool IsDuplicate(const QuicStreamFrame& frame,
+                   FrameList::const_iterator insertion_point) const;
 
   // Wait until we've seen 'offset' bytes, and then terminate the stream.
   void CloseStreamAtOffset(QuicStreamOffset offset);
 
   // If we've received a FIN and have processed all remaining data, then inform
   // the stream of FIN, and clear buffers.
   bool MaybeCloseStream();
 
   // Called whenever bytes are consumed by the stream. Updates
   // num_bytes_consumed_ and num_bytes_buffered_.
   void RecordBytesConsumed(size_t bytes_consumed);
 
   // The stream which owns this sequencer.
   ReliableQuicStream* stream_;
 
   // The last data consumed by the stream.
   QuicStreamOffset num_bytes_consumed_;
 
-  // TODO(alyssar) use something better than strings.
-  // TODO(rjshade): In future we may support retransmission of partial stream
-  // frames, in which case we will have to allow receipt of overlapping frames.
-  // Maybe write new frames into a ring buffer, and keep track of consumed
-  // bytes, and gaps.
-  typedef std::map<QuicStreamOffset, std::string> FrameMap;
-
-  // Stores buffered frames (maps from byte offset -> frame data as string).
-  FrameMap buffered_frames_;
+  // Stores buffered frames in offset order.
+  FrameList buffered_frames_;
 
   // The offset, if any, we got a stream termination for.  When this many bytes
   // have been processed, the sequencer will be closed.
   QuicStreamOffset close_offset_;
 
   // If true, the sequencer is blocked from passing data to the stream and will
   // buffer all new incoming data until FlushBufferedFrames is called.
   bool blocked_;
 
   // Tracks how many bytes the sequencer has buffered.
   size_t num_bytes_buffered_;
 
   // Count of the number of frames received.
   int num_frames_received_;
 
   // Count of the number of duplicate frames received.
   int num_duplicate_frames_received_;
 
   // Count of the number of frames received before all previous frames were
   // received.
   int num_early_frames_received_;
 
   DISALLOW_COPY_AND_ASSIGN(QuicStreamSequencer);
 };
 
 }  // namespace net
 
 #endif  // NET_QUIC_QUIC_STREAM_SEQUENCER_H_