blob: 8bda4a86e1f7d7132a9f5c457c564ea5f4efba68 [file] [log] [blame]
/*
* Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
*
* Use of this source code is governed by a BSD-style license
* that can be found in the LICENSE file in the root of the source
* tree. An additional intellectual property rights grant can be found
* in the file PATENTS. All contributing project authors may
* be found in the AUTHORS file in the root of the source tree.
*/
#ifndef MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
#define MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
#include <cstddef>
#include <cstdint>
#include <deque>
#include "api/units/timestamp.h"
#include "rtc_base/checks.h"
namespace webrtc {
// PacketArrivalTimeMap is an optimized map of packet sequence number to arrival
// time, limited in size to never exceed `kMaxNumberOfPackets`. It will grow as
// needed, and remove old packets, and will expand to allow earlier packets to
// be added (out-of-order).
//
// Not yet received packets have the arrival time zero. The queue will not span
// larger than necessary and the last packet should always be received. The
// first packet in the queue doesn't have to be received in case of receiving
// packets out-of-order.
class PacketArrivalTimeMap {
public:
// Impossible to request feedback older than what can be represented by 15
// bits.
static constexpr size_t kMaxNumberOfPackets = (1 << 15);
// Indicates if the packet with `sequence_number` has already been received.
bool has_received(int64_t sequence_number) const;
// Returns the sequence number of the first entry in the map, i.e. the
// sequence number that a `begin()` iterator would represent.
int64_t begin_sequence_number() const { return begin_sequence_number_; }
// Returns the sequence number of the element just after the map, i.e. the
// sequence number that an `end()` iterator would represent.
int64_t end_sequence_number() const {
return begin_sequence_number_ + arrival_times_.size();
}
// Returns an element by `sequence_number`, which must be valid, i.e.
// between [begin_sequence_number, end_sequence_number).
Timestamp get(int64_t sequence_number) {
int64_t pos = sequence_number - begin_sequence_number_;
RTC_DCHECK(pos >= 0 && pos < static_cast<int64_t>(arrival_times_.size()));
return arrival_times_[pos];
}
// Clamps `sequence_number` between [begin_sequence_number,
// end_sequence_number].
int64_t clamp(int64_t sequence_number) const;
// Erases all elements from the beginning of the map until `sequence_number`.
void EraseTo(int64_t sequence_number);
// Records the fact that a packet with `sequence_number` arrived at
// `arrival_time_ms`.
void AddPacket(int64_t sequence_number, Timestamp arrival_time);
// Removes packets from the beginning of the map as long as they are received
// before `sequence_number` and with an age older than `arrival_time_limit`
void RemoveOldPackets(int64_t sequence_number, Timestamp arrival_time_limit);
private:
// Deque representing unwrapped sequence number -> time, where the index +
// `begin_sequence_number_` represents the packet's sequence number.
std::deque<Timestamp> arrival_times_;
// The unwrapped sequence number for the first element in
// `arrival_times_`.
int64_t begin_sequence_number_ = 0;
// Indicates if this map has had any packet added to it. The first packet
// decides the initial sequence number.
bool has_seen_packet_ = false;
};
} // namespace webrtc
#endif // MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_