Introduce RtpSequenceNumberMap
The video encoder should be informed of incoming LossNotification
RTCP messages. Since it is unaware of RTP sequence numbers,
or anything else RTP-related, the sequence numbers mentioned
in the RTCP message must first be mapped to timestamps,
since those are meaningful to the encoder.
This CL introduces RtpSequenceNumberMap, which maps RTP sequence
numbers to timestamps, while providing:
1. Capping the number of entries.
2. Wrap-around handling.
RtpSequenceNumberMap also remembers which packets were first
and/or last in the frame.
Later CLs will wire this up.
Bug: webrtc:10501
Change-Id: Ie0662cdb5706a3bcf63aa2934816a9df88439357
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/130497
Commit-Queue: Elad Alon <eladalon@webrtc.org>
Reviewed-by: Danil Chapovalov <danilchap@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#27448}diff --git a/modules/rtp_rtcp/BUILD.gn b/modules/rtp_rtcp/BUILD.gn
index 0424a7a..6c2e09e 100644
--- a/modules/rtp_rtcp/BUILD.gn
+++ b/modules/rtp_rtcp/BUILD.gn
@@ -173,6 +173,8 @@
"source/rtp_sender_audio.h",
"source/rtp_sender_video.cc",
"source/rtp_sender_video.h",
+ "source/rtp_sequence_number_map.cc",
+ "source/rtp_sequence_number_map.h",
"source/rtp_utility.cc",
"source/rtp_utility.h",
"source/time_util.cc",
@@ -423,6 +425,7 @@
"source/rtp_sender_audio_unittest.cc",
"source/rtp_sender_unittest.cc",
"source/rtp_sender_video_unittest.cc",
+ "source/rtp_sequence_number_map_unittest.cc",
"source/rtp_utility_unittest.cc",
"source/time_util_unittest.cc",
"source/ulpfec_generator_unittest.cc",
@@ -456,6 +459,7 @@
"../../rtc_base:rate_limiter",
"../../rtc_base:rtc_base_approved",
"../../rtc_base:rtc_base_tests_utils",
+ "../../rtc_base:rtc_numerics",
"../../rtc_base:task_queue_for_test",
"../../system_wrappers",
"../../test:field_trial",
diff --git a/modules/rtp_rtcp/source/rtp_sequence_number_map.cc b/modules/rtp_rtcp/source/rtp_sequence_number_map.cc
new file mode 100644
index 0000000..95eafce
--- /dev/null
+++ b/modules/rtp_rtcp/source/rtp_sequence_number_map.cc
@@ -0,0 +1,114 @@
+/*
+ * Copyright (c) 2019 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.
+ */
+
+#include "modules/rtp_rtcp/source/rtp_sequence_number_map.h"
+
+#include <algorithm>
+#include <iterator>
+
+#include "absl/algorithm/container.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/logging.h"
+#include "rtc_base/numerics/sequence_number_util.h"
+
+namespace webrtc {
+
+RtpSequenceNumberMap::RtpSequenceNumberMap(size_t max_entries)
+ : max_entries_(max_entries) {
+ RTC_DCHECK_GT(max_entries_, 4); // See code paring down to |max_entries_|.
+ RTC_DCHECK_LE(max_entries_, 1 << 15);
+}
+
+RtpSequenceNumberMap::~RtpSequenceNumberMap() = default;
+
+void RtpSequenceNumberMap::Insert(uint16_t sequence_number, Info info) {
+ RTC_DCHECK(associations_.size() < 2 ||
+ AheadOf(associations_.back().sequence_number,
+ associations_.front().sequence_number));
+
+ if (associations_.empty()) {
+ associations_.emplace_back(sequence_number, info);
+ return;
+ }
+
+ if (AheadOrAt(sequence_number, associations_.front().sequence_number) &&
+ AheadOrAt(associations_.back().sequence_number, sequence_number)) {
+ // The sequence number has wrapped around and is within the range
+ // currently held by |associations_| - we should invalidate all entries.
+ RTC_LOG(LS_WARNING) << "Sequence number wrapped-around unexpectedly.";
+ associations_.clear();
+ associations_.emplace_back(sequence_number, info);
+ return;
+ }
+
+ std::deque<Association>::iterator erase_to = associations_.begin();
+
+ RTC_DCHECK_LE(associations_.size(), max_entries_);
+ if (associations_.size() == max_entries_) {
+ // Pare down the container so that inserting some additional elements
+ // would not exceed the maximum size.
+ const size_t new_size = 3 * max_entries_ / 4;
+ erase_to = std::next(erase_to, max_entries_ - new_size);
+ }
+
+ // It is guaranteed that |associations_| can be split into two partitions,
+ // either partition possibly empty, such that:
+ // * In the first partition, all elements are AheadOf the new element.
+ // This is the partition of the obsolete elements.
+ // * In the second partition, the new element is AheadOf all the elements.
+ // The elements of this partition may stay.
+ auto cmp = [](const Association& a, uint16_t sequence_number) {
+ return AheadOf(a.sequence_number, sequence_number);
+ };
+ RTC_DCHECK(erase_to != associations_.end());
+ erase_to =
+ std::lower_bound(erase_to, associations_.end(), sequence_number, cmp);
+ associations_.erase(associations_.begin(), erase_to);
+
+ associations_.emplace_back(sequence_number, info);
+
+ RTC_DCHECK(associations_.size() == 1 ||
+ AheadOf(associations_.back().sequence_number,
+ associations_.front().sequence_number));
+}
+
+absl::optional<RtpSequenceNumberMap::Info> RtpSequenceNumberMap::Get(
+ uint16_t sequence_number) const {
+ // To make the binary search easier to understand, we use the fact that
+ // adding a constant offset to all elements, as well as to the searched
+ // element, does not change the relative ordering. This way, we can find
+ // an offset that would make all of the elements strictly ascending according
+ // to normal integer comparison.
+ // Finding such an offset is easy - the offset that would map the oldest
+ // element to 0 would serve this purpose.
+
+ if (associations_.empty()) {
+ return absl::nullopt;
+ }
+
+ const uint16_t offset =
+ static_cast<uint16_t>(0) - associations_.front().sequence_number;
+
+ auto cmp = [offset](const Association& a, uint16_t sequence_number) {
+ return static_cast<uint16_t>(a.sequence_number + offset) <
+ static_cast<uint16_t>(sequence_number + offset);
+ };
+ const auto elem = absl::c_lower_bound(associations_, sequence_number, cmp);
+
+ return elem != associations_.end() && elem->sequence_number == sequence_number
+ ? absl::optional<Info>(elem->info)
+ : absl::nullopt;
+}
+
+size_t RtpSequenceNumberMap::AssociationCountForTesting() const {
+ return associations_.size();
+}
+
+} // namespace webrtc
diff --git a/modules/rtp_rtcp/source/rtp_sequence_number_map.h b/modules/rtp_rtcp/source/rtp_sequence_number_map.h
new file mode 100644
index 0000000..1f6a304
--- /dev/null
+++ b/modules/rtp_rtcp/source/rtp_sequence_number_map.h
@@ -0,0 +1,83 @@
+/*
+ * Copyright (c) 2019 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_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
+#define MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
+
+#include <cstddef>
+#include <cstdint>
+
+#include <deque>
+
+#include "absl/types/optional.h"
+
+namespace webrtc {
+
+// Records the association of RTP sequence numbers to timestamps and to whether
+// the packet was first and/or last in the frame.
+//
+// 1. Limits number of entries. Whenever |max_entries| is about to be exceeded,
+// the size is reduced by approximately 25%.
+// 2. RTP sequence numbers wrap around relatively infrequently.
+// This class therefore only remembers at most the last 2^15 RTP packets,
+// so that the newest packet's sequence number is still AheadOf the oldest
+// packet's sequence number.
+// 3. Media frames are sometimes split into several RTP packets.
+// In such a case, Insert() is expected to be called once for each packet.
+// The timestamp is not expected to change between those calls.
+class RtpSequenceNumberMap final {
+ public:
+ struct Info final {
+ Info(uint32_t timestamp, bool is_first, bool is_last)
+ : timestamp(timestamp), is_first(is_first), is_last(is_last) {}
+
+ friend bool operator==(const Info& lhs, const Info& rhs) {
+ return lhs.timestamp == rhs.timestamp && lhs.is_first == rhs.is_first &&
+ lhs.is_last == rhs.is_last;
+ }
+
+ uint32_t timestamp;
+ bool is_first;
+ bool is_last;
+ };
+
+ explicit RtpSequenceNumberMap(size_t max_entries);
+ RtpSequenceNumberMap(const RtpSequenceNumberMap& other) = delete;
+ RtpSequenceNumberMap& operator=(const RtpSequenceNumberMap& other) = delete;
+ ~RtpSequenceNumberMap();
+
+ void Insert(uint16_t sequence_number, Info info);
+
+ absl::optional<Info> Get(uint16_t sequence_number) const;
+
+ size_t AssociationCountForTesting() const;
+
+ private:
+ struct Association {
+ explicit Association(uint16_t sequence_number)
+ : Association(sequence_number, Info(0, false, false)) {}
+
+ Association(uint16_t sequence_number, Info info)
+ : sequence_number(sequence_number), info(info) {}
+
+ uint16_t sequence_number;
+ Info info;
+ };
+
+ const size_t max_entries_;
+
+ // The non-transitivity of AheadOf() would be problematic with a map,
+ // so we use a deque instead.
+ std::deque<Association> associations_;
+};
+
+} // namespace webrtc
+
+#endif // MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
diff --git a/modules/rtp_rtcp/source/rtp_sequence_number_map_unittest.cc b/modules/rtp_rtcp/source/rtp_sequence_number_map_unittest.cc
new file mode 100644
index 0000000..5cb9d73
--- /dev/null
+++ b/modules/rtp_rtcp/source/rtp_sequence_number_map_unittest.cc
@@ -0,0 +1,457 @@
+/*
+ * Copyright (c) 2019 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.
+ */
+
+#include "modules/rtp_rtcp/source/rtp_sequence_number_map.h"
+
+#include <algorithm>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <tuple>
+#include <vector>
+
+#include "absl/memory/memory.h"
+#include "absl/types/optional.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/sequence_number_util.h"
+#include "rtc_base/random.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+using Info = RtpSequenceNumberMap::Info;
+
+constexpr uint16_t kUint16Max = std::numeric_limits<uint16_t>::max();
+constexpr size_t kMaxPossibleMaxEntries = 1 << 15;
+
+// Just a named pair.
+struct Association final {
+ Association(uint16_t sequence_number, Info info)
+ : sequence_number(sequence_number), info(info) {}
+
+ uint16_t sequence_number;
+ Info info;
+};
+
+class RtpSequenceNumberMapTest : public ::testing::Test {
+ protected:
+ RtpSequenceNumberMapTest() : random_(1983) {}
+ ~RtpSequenceNumberMapTest() override = default;
+
+ Association CreateAssociation(uint16_t sequence_number, uint32_t timestamp) {
+ return Association(sequence_number,
+ {timestamp, random_.Rand<bool>(), random_.Rand<bool>()});
+ }
+
+ void VerifyAssociations(const RtpSequenceNumberMap& uut,
+ const std::vector<Association>& associations) {
+ return VerifyAssociations(uut, associations.begin(), associations.end());
+ }
+
+ void VerifyAssociations(
+ const RtpSequenceNumberMap& uut,
+ std::vector<Association>::const_iterator associations_begin,
+ std::vector<Association>::const_iterator associations_end) {
+ RTC_DCHECK(associations_begin < associations_end);
+ ASSERT_EQ(static_cast<size_t>(associations_end - associations_begin),
+ uut.AssociationCountForTesting());
+ for (auto association = associations_begin; association != associations_end;
+ ++association) {
+ EXPECT_EQ(uut.Get(association->sequence_number), association->info);
+ }
+ }
+
+ // Allows several variations of the same test; definition next to the tests.
+ void GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+ bool with_wrap_around,
+ bool last_element_kept);
+
+ // Allows several variations of the same test; definition next to the tests.
+ void RepeatedSequenceNumberInvalidatesAll(size_t index_of_repeated);
+
+ // Allows several variations of the same test; definition next to the tests.
+ void MaxEntriesReachedAtSameTimeAsObsoletionOfItem(size_t max_entries,
+ size_t obsoleted_count);
+
+ Random random_;
+};
+
+class RtpSequenceNumberMapTestWithParams
+ : public RtpSequenceNumberMapTest,
+ public ::testing::WithParamInterface<std::tuple<size_t, uint16_t>> {
+ protected:
+ RtpSequenceNumberMapTestWithParams() = default;
+ ~RtpSequenceNumberMapTestWithParams() override = default;
+
+ std::vector<Association> ProduceRandomAssociationSequence(
+ size_t association_count,
+ uint16_t first_sequence_number,
+ bool allow_obsoletion) {
+ std::vector<Association> associations;
+ associations.reserve(association_count);
+
+ if (association_count == 0) {
+ return associations;
+ }
+
+ associations.emplace_back(
+ first_sequence_number,
+ Info(0, random_.Rand<bool>(), random_.Rand<bool>()));
+
+ for (size_t i = 1; i < association_count; ++i) {
+ const uint16_t sequence_number =
+ associations[i - 1].sequence_number + random_.Rand(1, 100);
+ RTC_DCHECK(allow_obsoletion ||
+ AheadOf(sequence_number, associations[0].sequence_number));
+
+ const uint32_t timestamp =
+ associations[i - 1].info.timestamp + random_.Rand(1, 10000);
+
+ associations.emplace_back(
+ sequence_number,
+ Info(timestamp, random_.Rand<bool>(), random_.Rand<bool>()));
+ }
+
+ return associations;
+ }
+};
+
+INSTANTIATE_TEST_SUITE_P(,
+ RtpSequenceNumberMapTestWithParams,
+ ::testing::Combine(
+ // Association count.
+ ::testing::Values(1, 2, 100),
+ // First sequence number.
+ ::testing::Values(0,
+ 100,
+ kUint16Max - 100,
+ kUint16Max - 1,
+ kUint16Max)));
+
+TEST_F(RtpSequenceNumberMapTest, GetBeforeAssociationsRecordedReturnsNullOpt) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+ constexpr uint16_t kArbitrarySequenceNumber = 321;
+ EXPECT_FALSE(uut.Get(kArbitrarySequenceNumber));
+}
+
+// Version #1 - any old unknown sequence number.
+TEST_F(RtpSequenceNumberMapTest, GetUnknownSequenceNumberReturnsNullOpt1) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ constexpr uint16_t kKnownSequenceNumber = 10;
+ constexpr uint32_t kArbitrary = 987;
+ uut.Insert(kKnownSequenceNumber, {kArbitrary, false, false});
+
+ constexpr uint16_t kUnknownSequenceNumber = kKnownSequenceNumber + 1;
+ EXPECT_FALSE(uut.Get(kUnknownSequenceNumber));
+}
+
+// Version #2 - intentionally pick a value in the range of currently held
+// values, so as to trigger lower_bound / upper_bound.
+TEST_F(RtpSequenceNumberMapTest, GetUnknownSequenceNumberReturnsNullOpt2) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ const std::vector<Association> setup = {CreateAssociation(1000, 500), //
+ CreateAssociation(1020, 501)};
+ for (const Association& association : setup) {
+ uut.Insert(association.sequence_number, association.info);
+ }
+
+ EXPECT_FALSE(uut.Get(1001));
+}
+
+TEST_P(RtpSequenceNumberMapTestWithParams,
+ GetKnownSequenceNumberReturnsCorrectValue) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ const size_t association_count = std::get<0>(GetParam());
+ const uint16_t first_sequence_number = std::get<1>(GetParam());
+
+ const std::vector<Association> associations =
+ ProduceRandomAssociationSequence(association_count, first_sequence_number,
+ /*allow_obsoletion=*/false);
+
+ for (const Association& association : associations) {
+ uut.Insert(association.sequence_number, association.info);
+ }
+
+ VerifyAssociations(uut, associations);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ GetObsoleteSequenceNumberReturnsNullOptSingleValueObsoleted) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ const std::vector<Association> associations = {
+ CreateAssociation(0, 10), //
+ CreateAssociation(0x8000, 20), //
+ CreateAssociation(0x8001u, 30)};
+
+ uut.Insert(associations[0].sequence_number, associations[0].info);
+
+ // First association not yet obsolete, and therefore remembered.
+ RTC_DCHECK(AheadOf(associations[1].sequence_number,
+ associations[0].sequence_number));
+ uut.Insert(associations[1].sequence_number, associations[1].info);
+ VerifyAssociations(uut, {associations[0], associations[1]});
+
+ // Test focus - new entry obsoletes first entry.
+ RTC_DCHECK(!AheadOf(associations[2].sequence_number,
+ associations[0].sequence_number));
+ uut.Insert(associations[2].sequence_number, associations[2].info);
+ VerifyAssociations(uut, {associations[1], associations[2]});
+}
+
+void RtpSequenceNumberMapTest::
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+ bool with_wrap_around,
+ bool last_element_kept) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ std::vector<Association> associations;
+ if (with_wrap_around) {
+ associations = {CreateAssociation(kUint16Max - 1, 10), //
+ CreateAssociation(kUint16Max, 20), //
+ CreateAssociation(0, 30), //
+ CreateAssociation(1, 40), //
+ CreateAssociation(2, 50)};
+ } else {
+ associations = {CreateAssociation(1, 10), //
+ CreateAssociation(2, 20), //
+ CreateAssociation(3, 30), //
+ CreateAssociation(4, 40), //
+ CreateAssociation(5, 50)};
+ }
+
+ for (auto association : associations) {
+ uut.Insert(association.sequence_number, association.info);
+ }
+ VerifyAssociations(uut, associations);
+
+ // Define a new association that will obsolete either all previous entries,
+ // or all previous entries except for the last one, depending on the
+ // parameter instantiation of this test.
+ RTC_DCHECK_EQ(
+ static_cast<uint16_t>(
+ associations[associations.size() - 1].sequence_number),
+ static_cast<uint16_t>(
+ associations[associations.size() - 2].sequence_number + 1u));
+ uint16_t new_sequence_number;
+ if (last_element_kept) {
+ new_sequence_number =
+ associations[associations.size() - 1].sequence_number + 0x8000;
+ RTC_DCHECK(AheadOf(new_sequence_number,
+ associations[associations.size() - 1].sequence_number));
+ } else {
+ new_sequence_number =
+ associations[associations.size() - 1].sequence_number + 0x8001;
+ RTC_DCHECK(!AheadOf(new_sequence_number,
+ associations[associations.size() - 1].sequence_number));
+ }
+ RTC_DCHECK(!AheadOf(new_sequence_number,
+ associations[associations.size() - 2].sequence_number));
+
+ // Record the new association.
+ const Association new_association =
+ CreateAssociation(new_sequence_number, 60);
+ uut.Insert(new_association.sequence_number, new_association.info);
+
+ // Make sure all obsoleted elements were removed.
+ const size_t obsoleted_count =
+ associations.size() - (last_element_kept ? 1 : 0);
+ for (size_t i = 0; i < obsoleted_count; ++i) {
+ EXPECT_FALSE(uut.Get(associations[i].sequence_number));
+ }
+
+ // Make sure the expected elements were not removed, and return the
+ // expected value.
+ if (last_element_kept) {
+ EXPECT_EQ(uut.Get(associations.back().sequence_number),
+ associations.back().info);
+ }
+ EXPECT_EQ(uut.Get(new_association.sequence_number), new_association.info);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted0) {
+ const bool with_wrap_around = false;
+ const bool last_element_kept = false;
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+ with_wrap_around, last_element_kept);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted1) {
+ const bool with_wrap_around = true;
+ const bool last_element_kept = false;
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+ with_wrap_around, last_element_kept);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted2) {
+ const bool with_wrap_around = false;
+ const bool last_element_kept = true;
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+ with_wrap_around, last_element_kept);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted3) {
+ const bool with_wrap_around = true;
+ const bool last_element_kept = true;
+ GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+ with_wrap_around, last_element_kept);
+}
+
+void RtpSequenceNumberMapTest::RepeatedSequenceNumberInvalidatesAll(
+ size_t index_of_repeated) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ const std::vector<Association> setup = {CreateAssociation(100, 500), //
+ CreateAssociation(101, 501), //
+ CreateAssociation(102, 502)};
+ RTC_DCHECK_LT(index_of_repeated, setup.size());
+ for (const Association& association : setup) {
+ uut.Insert(association.sequence_number, association.info);
+ }
+
+ const Association new_association =
+ CreateAssociation(setup[index_of_repeated].sequence_number, 503);
+ uut.Insert(new_association.sequence_number, new_association.info);
+
+ // All entries from setup invalidated.
+ // New entry valid and mapped to new value.
+ for (size_t i = 0; i < setup.size(); ++i) {
+ if (i == index_of_repeated) {
+ EXPECT_EQ(uut.Get(new_association.sequence_number), new_association.info);
+ } else {
+ EXPECT_FALSE(uut.Get(setup[i].sequence_number));
+ }
+ }
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ RepeatedSequenceNumberInvalidatesAllRepeatFirst) {
+ RepeatedSequenceNumberInvalidatesAll(0);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ RepeatedSequenceNumberInvalidatesAllRepeatMiddle) {
+ RepeatedSequenceNumberInvalidatesAll(1);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ RepeatedSequenceNumberInvalidatesAllRepeatLast) {
+ RepeatedSequenceNumberInvalidatesAll(2);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+ SequenceNumberInsideMemorizedRangeInvalidatesAll) {
+ RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+ const std::vector<Association> setup = {CreateAssociation(1000, 500), //
+ CreateAssociation(1020, 501), //
+ CreateAssociation(1030, 502)};
+ for (const Association& association : setup) {
+ uut.Insert(association.sequence_number, association.info);
+ }
+
+ const Association new_association = CreateAssociation(1010, 503);
+ uut.Insert(new_association.sequence_number, new_association.info);
+
+ // All entries from setup invalidated.
+ // New entry valid and mapped to new value.
+ for (size_t i = 0; i < setup.size(); ++i) {
+ EXPECT_FALSE(uut.Get(setup[i].sequence_number));
+ }
+ EXPECT_EQ(uut.Get(new_association.sequence_number), new_association.info);
+}
+
+TEST_F(RtpSequenceNumberMapTest, MaxEntriesObserved) {
+ constexpr size_t kMaxEntries = 100;
+ RtpSequenceNumberMap uut(kMaxEntries);
+
+ std::vector<Association> associations;
+ associations.reserve(kMaxEntries);
+ uint32_t timestamp = 789;
+ for (size_t i = 0; i < kMaxEntries; ++i) {
+ associations.push_back(CreateAssociation(i, ++timestamp));
+ uut.Insert(associations[i].sequence_number, associations[i].info);
+ }
+ VerifyAssociations(uut, associations); // Sanity.
+
+ const Association new_association =
+ CreateAssociation(kMaxEntries, ++timestamp);
+ uut.Insert(new_association.sequence_number, new_association.info);
+ associations.push_back(new_association);
+
+ // The +1 is for |new_association|.
+ const size_t kExpectedAssociationCount = 3 * kMaxEntries / 4 + 1;
+ const auto expected_begin =
+ std::prev(associations.end(), kExpectedAssociationCount);
+ VerifyAssociations(uut, expected_begin, associations.end());
+}
+
+void RtpSequenceNumberMapTest::MaxEntriesReachedAtSameTimeAsObsoletionOfItem(
+ size_t max_entries,
+ size_t obsoleted_count) {
+ RtpSequenceNumberMap uut(max_entries);
+
+ std::vector<Association> associations;
+ associations.reserve(max_entries);
+ uint32_t timestamp = 789;
+ for (size_t i = 0; i < max_entries; ++i) {
+ associations.push_back(CreateAssociation(i, ++timestamp));
+ uut.Insert(associations[i].sequence_number, associations[i].info);
+ }
+ VerifyAssociations(uut, associations); // Sanity.
+
+ const uint16_t new_association_sequence_number =
+ static_cast<uint16_t>(obsoleted_count) + (1 << 15);
+ const Association new_association =
+ CreateAssociation(new_association_sequence_number, ++timestamp);
+ uut.Insert(new_association.sequence_number, new_association.info);
+ associations.push_back(new_association);
+
+ // The +1 is for |new_association|.
+ const size_t kExpectedAssociationCount =
+ std::min(3 * max_entries / 4, max_entries - obsoleted_count) + 1;
+ const auto expected_begin =
+ std::prev(associations.end(), kExpectedAssociationCount);
+ VerifyAssociations(uut, expected_begin, associations.end());
+}
+
+// Version #1 - #(obsoleted entries) < #(entries after paring down below max).
+TEST_F(RtpSequenceNumberMapTest,
+ MaxEntriesReachedAtSameTimeAsObsoletionOfItem1) {
+ constexpr size_t kMaxEntries = 100;
+ constexpr size_t kObsoletionTarget = (kMaxEntries / 4) - 1;
+ MaxEntriesReachedAtSameTimeAsObsoletionOfItem(kMaxEntries, kObsoletionTarget);
+}
+
+// Version #2 - #(obsoleted entries) == #(entries after paring down below max).
+TEST_F(RtpSequenceNumberMapTest,
+ MaxEntriesReachedAtSameTimeAsObsoletionOfItem2) {
+ constexpr size_t kMaxEntries = 100;
+ constexpr size_t kObsoletionTarget = kMaxEntries / 4;
+ MaxEntriesReachedAtSameTimeAsObsoletionOfItem(kMaxEntries, kObsoletionTarget);
+}
+
+// Version #3 - #(obsoleted entries) > #(entries after paring down below max).
+TEST_F(RtpSequenceNumberMapTest,
+ MaxEntriesReachedAtSameTimeAsObsoletionOfItem3) {
+ constexpr size_t kMaxEntries = 100;
+ constexpr size_t kObsoletionTarget = (kMaxEntries / 4) + 1;
+ MaxEntriesReachedAtSameTimeAsObsoletionOfItem(kMaxEntries, kObsoletionTarget);
+}
+
+} // namespace
+} // namespace webrtc
