Project import generated by Copybara.
PiperOrigin-RevId: 237361882
Change-Id: I109a68f44db867b20f8c6a7732b0ce657133e52a
diff --git a/quic/core/packet_number_indexed_queue.h b/quic/core/packet_number_indexed_queue.h
new file mode 100644
index 0000000..ab2e20b
--- /dev/null
+++ b/quic/core/packet_number_indexed_queue.h
@@ -0,0 +1,211 @@
+// Copyright (c) 2017 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 QUICHE_QUIC_CORE_PACKET_NUMBER_INDEXED_QUEUE_H_
+#define QUICHE_QUIC_CORE_PACKET_NUMBER_INDEXED_QUEUE_H_
+
+#include "net/third_party/quiche/src/quic/core/quic_constants.h"
+#include "net/third_party/quiche/src/quic/core/quic_types.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_containers.h"
+
+namespace quic {
+
+// PacketNumberIndexedQueue is a queue of mostly continuous numbered entries
+// which supports the following operations:
+// - adding elements to the end of the queue, or at some point past the end
+// - removing elements in any order
+// - retrieving elements
+// If all elements are inserted in order, all of the operations above are
+// amortized O(1) time.
+//
+// Internally, the data structure is a deque where each element is marked as
+// present or not. The deque starts at the lowest present index. Whenever an
+// element is removed, it's marked as not present, and the front of the deque is
+// cleared of elements that are not present.
+//
+// The tail of the queue is not cleared due to the assumption of entries being
+// inserted in order, though removing all elements of the queue will return it
+// to its initial state.
+//
+// Note that this data structure is inherently hazardous, since an addition of
+// just two entries will cause it to consume all of the memory available.
+// Because of that, it is not a general-purpose container and should not be used
+// as one.
+template <typename T>
+class PacketNumberIndexedQueue {
+ public:
+ PacketNumberIndexedQueue() : number_of_present_entries_(0) {}
+
+ // Retrieve the entry associated with the packet number. Returns the pointer
+ // to the entry in case of success, or nullptr if the entry does not exist.
+ T* GetEntry(QuicPacketNumber packet_number);
+ const T* GetEntry(QuicPacketNumber packet_number) const;
+
+ // Inserts data associated |packet_number| into (or past) the end of the
+ // queue, filling up the missing intermediate entries as necessary. Returns
+ // true if the element has been inserted successfully, false if it was already
+ // in the queue or inserted out of order.
+ template <typename... Args>
+ bool Emplace(QuicPacketNumber packet_number, Args&&... args);
+
+ // Removes data associated with |packet_number| and frees the slots in the
+ // queue as necessary.
+ bool Remove(QuicPacketNumber packet_number);
+
+ bool IsEmpty() const { return number_of_present_entries_ == 0; }
+
+ // Returns the number of entries in the queue.
+ size_t number_of_present_entries() const {
+ return number_of_present_entries_;
+ }
+
+ // Returns the number of entries allocated in the underlying deque. This is
+ // proportional to the memory usage of the queue.
+ size_t entry_slots_used() const { return entries_.size(); }
+
+ // Packet number of the first entry in the queue.
+ QuicPacketNumber first_packet() const { return first_packet_; }
+
+ // Packet number of the last entry ever inserted in the queue. Note that the
+ // entry in question may have already been removed. Zero if the queue is
+ // empty.
+ QuicPacketNumber last_packet() const {
+ if (IsEmpty()) {
+ return QuicPacketNumber();
+ }
+ return first_packet_ + entries_.size() - 1;
+ }
+
+ private:
+ // Wrapper around T used to mark whether the entry is actually in the map.
+ struct EntryWrapper : T {
+ bool present;
+
+ EntryWrapper() : present(false) {}
+
+ template <typename... Args>
+ explicit EntryWrapper(Args&&... args)
+ : T(std::forward<Args>(args)...), present(true) {}
+ };
+
+ // Cleans up unused slots in the front after removing an element.
+ void Cleanup();
+
+ const EntryWrapper* GetEntryWrapper(QuicPacketNumber offset) const;
+ EntryWrapper* GetEntryWrapper(QuicPacketNumber offset) {
+ const auto* const_this = this;
+ return const_cast<EntryWrapper*>(const_this->GetEntryWrapper(offset));
+ }
+
+ QuicDeque<EntryWrapper> entries_;
+ size_t number_of_present_entries_;
+ QuicPacketNumber first_packet_;
+};
+
+template <typename T>
+T* PacketNumberIndexedQueue<T>::GetEntry(QuicPacketNumber packet_number) {
+ EntryWrapper* entry = GetEntryWrapper(packet_number);
+ if (entry == nullptr) {
+ return nullptr;
+ }
+ return entry;
+}
+
+template <typename T>
+const T* PacketNumberIndexedQueue<T>::GetEntry(
+ QuicPacketNumber packet_number) const {
+ const EntryWrapper* entry = GetEntryWrapper(packet_number);
+ if (entry == nullptr) {
+ return nullptr;
+ }
+ return entry;
+}
+
+template <typename T>
+template <typename... Args>
+bool PacketNumberIndexedQueue<T>::Emplace(QuicPacketNumber packet_number,
+ Args&&... args) {
+ if (!packet_number.IsInitialized()) {
+ QUIC_BUG << "Try to insert an uninitialized packet number";
+ return false;
+ }
+
+ if (IsEmpty()) {
+ DCHECK(entries_.empty());
+ DCHECK(!first_packet_.IsInitialized());
+
+ entries_.emplace_back(std::forward<Args>(args)...);
+ number_of_present_entries_ = 1;
+ first_packet_ = packet_number;
+ return true;
+ }
+
+ // Do not allow insertion out-of-order.
+ if (packet_number <= last_packet()) {
+ return false;
+ }
+
+ // Handle potentially missing elements.
+ size_t offset = packet_number - first_packet_;
+ if (offset > entries_.size()) {
+ entries_.resize(offset);
+ }
+
+ number_of_present_entries_++;
+ entries_.emplace_back(std::forward<Args>(args)...);
+ DCHECK_EQ(packet_number, last_packet());
+ return true;
+}
+
+template <typename T>
+bool PacketNumberIndexedQueue<T>::Remove(QuicPacketNumber packet_number) {
+ EntryWrapper* entry = GetEntryWrapper(packet_number);
+ if (entry == nullptr) {
+ return false;
+ }
+ entry->present = false;
+ number_of_present_entries_--;
+
+ if (packet_number == first_packet()) {
+ Cleanup();
+ }
+ return true;
+}
+
+template <typename T>
+void PacketNumberIndexedQueue<T>::Cleanup() {
+ while (!entries_.empty() && !entries_.front().present) {
+ entries_.pop_front();
+ first_packet_++;
+ }
+ if (entries_.empty()) {
+ first_packet_.Clear();
+ }
+}
+
+template <typename T>
+auto PacketNumberIndexedQueue<T>::GetEntryWrapper(
+ QuicPacketNumber packet_number) const -> const EntryWrapper* {
+ if (!packet_number.IsInitialized() || IsEmpty() ||
+ packet_number < first_packet_) {
+ return nullptr;
+ }
+
+ uint64_t offset = packet_number - first_packet_;
+ if (offset >= entries_.size()) {
+ return nullptr;
+ }
+
+ const EntryWrapper* entry = &entries_[offset];
+ if (!entry->present) {
+ return nullptr;
+ }
+
+ return entry;
+}
+
+} // namespace quic
+
+#endif // QUICHE_QUIC_CORE_PACKET_NUMBER_INDEXED_QUEUE_H_
