Optimize QUIC's EntropyTracker in QuicReceivedPacketManager by using a

net/quic/quic_received_packet_manager.h

Index: net/quic/quic_received_packet_manager.h
diff --git a/net/quic/quic_received_packet_manager.h b/net/quic/quic_received_packet_manager.h
index 43f6b5583f9057252bb4d68e20dc8a7db80d3065..92c08f55c14113d182e388df2a352fc1e3e90156 100644
--- a/net/quic/quic_received_packet_manager.h
+++ b/net/quic/quic_received_packet_manager.h
@@ -8,6 +8,8 @@
 #ifndef NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
 #define NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
 
+#include <deque>
+
 #include "net/quic/congestion_control/receive_algorithm_interface.h"
 #include "net/quic/quic_framer.h"
 #include "net/quic/quic_protocol.h"
@@ -59,22 +61,20 @@ class NET_EXPORT_PRIVATE QuicReceivedPacketManager :
    private:
     friend class test::EntropyTrackerPeer;
 
-    typedef std::map<QuicPacketSequenceNumber,
-                     QuicPacketEntropyHash> ReceivedEntropyMap;
+    // A deque indexed by sequence number storing the packet's hash and whether
+    // a hash was recorded for that sequence number.
+    typedef std::deque<std::pair<QuicPacketEntropyHash, bool>>
+        ReceivedEntropyHashes;
 
     // Recomputes first_gap_ and removes packets_entropy_ entries that are no
     // longer needed to compute EntropyHash.
     void AdvanceFirstGapAndGarbageCollectEntropyMap();
 
-    // TODO(satyamshekhar): Can be optimized using an interval set like data
-    // structure.
     // Map of received sequence numbers to their corresponding entropy.
     // Stores an entry for every received packet whose sequence_number is larger
     // than first_gap_.  Packets without the entropy bit set have an entropy
     // value of 0.
-    // TODO(ianswett): When the entropy flag is off, the entropy
-    // should not be 0.
-    ReceivedEntropyMap packets_entropy_;
+    ReceivedEntropyHashes packets_entropy_;
 
     // Cumulative hash of entropy of all received packets.
     QuicPacketEntropyHash packets_entropy_hash_;
@@ -135,9 +135,6 @@ class NET_EXPORT_PRIVATE QuicReceivedPacketManager :
   void UpdatePacketInformationSentByPeer(
       const QuicStopWaitingFrame& stop_waiting);
 
-  // Returns whether the peer is missing packets.
-  bool HasMissingPackets();
-
   // Returns true when there are new missing packets to be reported within 3
   // packets of the largest observed.
   bool HasNewMissingPackets();