packet_number_indexed_queue.h | Explore in Territory

// 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 "quiche/quic/core/quic_constants.h"
#include "quiche/quic/core/quic_packet_number.h"
#include "quiche/quic/core/quic_types.h"
#include "quiche/quic/platform/api/quic_bug_tracker.h"
#include "quiche/common/quiche_circular_deque.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.
// TODO(wub): Update the comments when deprecating
// --quic_bw_sampler_remove_packets_once_per_congestion_event.
template <typename T>
class QUICHE_NO_EXPORT PacketNumberIndexedQueue { … };

template <typename T>
T* PacketNumberIndexedQueue<T>::GetEntry(QuicPacketNumber packet_number) { … }

template <typename T>
const T* PacketNumberIndexedQueue<T>::GetEntry(
    QuicPacketNumber packet_number) const { … }

template <typename T>
template <typename... Args>
bool PacketNumberIndexedQueue<T>::Emplace(QuicPacketNumber packet_number,
                                          Args&&... args) { … }

template <typename T>
bool PacketNumberIndexedQueue<T>::Remove(QuicPacketNumber packet_number) { … }

template <typename T>
template <typename Function>
bool PacketNumberIndexedQueue<T>::Remove(QuicPacketNumber packet_number,
                                         Function f) { … }

template <typename T>
void PacketNumberIndexedQueue<T>::RemoveUpTo(QuicPacketNumber packet_number) { … }

template <typename T>
void PacketNumberIndexedQueue<T>::Cleanup() { … }

template <typename T>
auto PacketNumberIndexedQueue<T>::GetEntryWrapper(
    QuicPacketNumber packet_number) const -> const EntryWrapper* { … }

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_PACKET_NUMBER_INDEXED_QUEUE_H_
chromium/net/third_party/quiche/src/quiche/quic/core/packet_number_indexed_queue.h
