relnote: Refactor QuicAckFrame::missing_packets to support a change to a

net/quic/quic_protocol.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_PROTOCOL_H_
 #define NET_QUIC_QUIC_PROTOCOL_H_
 
 #include <stddef.h>
 #include <stdint.h>
 #include <limits>
@@ skipping 704 matching lines @@
 
   NET_EXPORT_PRIVATE friend std::ostream& operator<<(
       std::ostream& os, const QuicStopWaitingFrame& s);
   // Entropy hash of all packets up to, but not including, the least unacked
   // packet.
   QuicPacketEntropyHash entropy_hash;
   // The lowest packet we've sent which is unacked, and we expect an ack for.
   QuicPacketNumber least_unacked;
 };
 
+// A sequence of packet numbers where each number is unique. Intended to be used
+// in a sliding window fashion, where smaller old packet numbers are removed and
+// larger new packet numbers are added, with the occasional random access.
+class NET_EXPORT_PRIVATE PacketNumberQueue {
+ public:
+  PacketNumberQueue();
+  ~PacketNumberQueue();
+
+  using iterator = PacketNumberSet::iterator;
+  using const_iterator = PacketNumberSet::const_iterator;
+
+  // Adds |packet_number| to the set of packets in the queue.
+  void Add(QuicPacketNumber packet_number);
+
+  // Adds packets between [lower, higher) to the set of packets in the queue.
+  void Add(QuicPacketNumber lower, QuicPacketNumber higher);
+
+  // Removes |packet_number| from the set of packets in the queue.
+  void Remove(QuicPacketNumber packet_number);
+
+  // Removes packets with values less than |higher| from the set of packets in
+  // the queue. Returns true if packets were removed.
+  bool RemoveUpTo(QuicPacketNumber higher);
+
+  // Returns true if the queue contains |packet_number|.
+  bool Contains(QuicPacketNumber packet_number) const;
+
+  // Returns true if the queue is empty.
+  bool Empty() const;
+
+  // Returns the minimum packet number stored in the queue. It is undefined
+  // behavior to call this if the queue is empty.
+  QuicPacketNumber Min() const;
+
+  // Returns the maximum packet number stored in the queue. It is undefined
+  // behavior to call this if the queue is empty.
+  QuicPacketNumber Max() const;
+
+  // Returns the number of unique packets stored in the queue.
+  size_t NumPackets() const;
+
+  const_iterator begin() const;
+  const_iterator end() const;
+  const_iterator lower_bound(QuicPacketNumber packet_number) const;
+  const_iterator upper_bound(QuicPacketNumber packet_number) const;
+
+  NET_EXPORT_PRIVATE friend std::ostream& operator<<(
+      std::ostream& os,
+      const PacketNumberQueue& q);
+
+ private:
+  // TODO(jdorfman): Can be optimized using an interval set like data structure.
+  PacketNumberSet packet_numbers_;
+};
+
 struct NET_EXPORT_PRIVATE QuicAckFrame {
   QuicAckFrame();
   ~QuicAckFrame();
 
   NET_EXPORT_PRIVATE friend std::ostream& operator<<(
       std::ostream& os, const QuicAckFrame& s);
 
   // Entropy hash of all packets up to largest observed not including missing
   // packets.
   QuicPacketEntropyHash entropy_hash;
 
   // The highest packet number we've observed from the peer.
   //
   // In general, this should be the largest packet number we've received.  In
   // the case of truncated acks, we may have to advertise a lower "upper bound"
   // than largest received, to avoid implicitly acking missing packets that
   // don't fit in the missing packet list due to size limitations.  In this
   // case, largest_observed may be a packet which is also in the missing packets
   // list.
   QuicPacketNumber largest_observed;
 
   // Time elapsed since largest_observed was received until this Ack frame was
   // sent.
   QuicTime::Delta delta_time_largest_observed;
 
-  // TODO(satyamshekhar): Can be optimized using an interval set like data
-  // structure.
   // The set of packets which we're expecting and have not received.
-  PacketNumberSet missing_packets;
+  PacketNumberQueue missing_packets;
 
   // Whether the ack had to be truncated when sent.
   bool is_truncated;
 
   // Packets which have been revived via FEC.
   // All of these must also be in missing_packets.
   PacketNumberSet revived_packets;
 
   // List of <packet_number, time> for when packets arrived.
   PacketTimeList received_packet_times;
 };
 
 // True if the packet number is greater than largest_observed or is listed
 // as missing.
 // Always returns false for packet numbers less than least_unacked.
 bool NET_EXPORT_PRIVATE IsAwaitingPacket(const QuicAckFrame& ack_frame,
                                          QuicPacketNumber packet_number);
 
-// Inserts missing packets between [lower, higher).
-void NET_EXPORT_PRIVATE InsertMissingPacketsBetween(QuicAckFrame* ack_frame,
-                                                    QuicPacketNumber lower,
-                                                    QuicPacketNumber higher);
-
 // Defines for all types of congestion control algorithms that can be used in
 // QUIC. Note that this is separate from the congestion feedback type -
 // some congestion control algorithms may use the same feedback type
 // (Reno and Cubic are the classic example for that).
 enum CongestionControlType {
   kCubic,
   kCubicBytes,
   kReno,
   kRenoBytes,
   kBBR,
@@ skipping 310 matching lines @@
       : iov(iov), iov_count(iov_count), total_length(total_length) {}
 
   const struct iovec* iov;
   const int iov_count;
   const size_t total_length;
 };
 
 }  // namespace net
 
 #endif  // NET_QUIC_QUIC_PROTOCOL_H_