rtp_sequence_number_map.cc (5035B)
1 /* 2 * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #include "modules/rtp_rtcp/source/rtp_sequence_number_map.h" 12 13 #include <algorithm> 14 #include <cstddef> 15 #include <cstdint> 16 #include <deque> 17 #include <iterator> 18 #include <limits> 19 #include <optional> 20 21 #include "absl/algorithm/container.h" 22 #include "rtc_base/checks.h" 23 #include "rtc_base/logging.h" 24 #include "rtc_base/numerics/sequence_number_util.h" 25 26 namespace webrtc { 27 28 RtpSequenceNumberMap::RtpSequenceNumberMap(size_t max_entries) 29 : max_entries_(max_entries) { 30 RTC_DCHECK_GT(max_entries_, 4); // See code paring down to `max_entries_`. 31 RTC_DCHECK_LE(max_entries_, 1 << 15); 32 } 33 34 RtpSequenceNumberMap::~RtpSequenceNumberMap() = default; 35 36 void RtpSequenceNumberMap::InsertPacket(uint16_t sequence_number, Info info) { 37 RTC_DCHECK(associations_.size() < 2 || 38 AheadOf(associations_.back().sequence_number, 39 associations_.front().sequence_number)); 40 41 if (associations_.empty()) { 42 associations_.emplace_back(sequence_number, info); 43 return; 44 } 45 46 if (AheadOrAt(sequence_number, associations_.front().sequence_number) && 47 AheadOrAt(associations_.back().sequence_number, sequence_number)) { 48 // The sequence number has wrapped around and is within the range 49 // currently held by `associations_` - we should invalidate all entries. 50 RTC_LOG(LS_WARNING) << "Sequence number wrapped-around unexpectedly."; 51 associations_.clear(); 52 associations_.emplace_back(sequence_number, info); 53 return; 54 } 55 56 std::deque<Association>::iterator erase_to = associations_.begin(); 57 58 RTC_DCHECK_LE(associations_.size(), max_entries_); 59 if (associations_.size() == max_entries_) { 60 // Pare down the container so that inserting some additional elements 61 // would not exceed the maximum size. 62 const size_t new_size = 3 * max_entries_ / 4; 63 erase_to = std::next(erase_to, max_entries_ - new_size); 64 } 65 66 // It is guaranteed that `associations_` can be split into two partitions, 67 // either partition possibly empty, such that: 68 // * In the first partition, all elements are AheadOf the new element. 69 // This is the partition of the obsolete elements. 70 // * In the second partition, the new element is AheadOf all the elements. 71 // The elements of this partition may stay. 72 auto cmp = [](const Association& a, uint16_t sequence_number) { 73 return AheadOf(a.sequence_number, sequence_number); 74 }; 75 RTC_DCHECK(erase_to != associations_.end()); 76 erase_to = 77 std::lower_bound(erase_to, associations_.end(), sequence_number, cmp); 78 associations_.erase(associations_.begin(), erase_to); 79 80 associations_.emplace_back(sequence_number, info); 81 82 RTC_DCHECK(associations_.size() == 1 || 83 AheadOf(associations_.back().sequence_number, 84 associations_.front().sequence_number)); 85 } 86 87 void RtpSequenceNumberMap::InsertFrame(uint16_t first_sequence_number, 88 size_t packet_count, 89 uint32_t timestamp) { 90 RTC_DCHECK_GT(packet_count, 0); 91 RTC_DCHECK_LE(packet_count, std::numeric_limits<size_t>::max()); 92 93 for (size_t i = 0; i < packet_count; ++i) { 94 const bool is_first = (i == 0); 95 const bool is_last = (i == packet_count - 1); 96 InsertPacket(static_cast<uint16_t>(first_sequence_number + i), 97 Info(timestamp, is_first, is_last)); 98 } 99 } 100 101 std::optional<RtpSequenceNumberMap::Info> RtpSequenceNumberMap::Get( 102 uint16_t sequence_number) const { 103 // To make the binary search easier to understand, we use the fact that 104 // adding a constant offset to all elements, as well as to the searched 105 // element, does not change the relative ordering. This way, we can find 106 // an offset that would make all of the elements strictly ascending according 107 // to normal integer comparison. 108 // Finding such an offset is easy - the offset that would map the oldest 109 // element to 0 would serve this purpose. 110 111 if (associations_.empty()) { 112 return std::nullopt; 113 } 114 115 const uint16_t offset = 116 static_cast<uint16_t>(0) - associations_.front().sequence_number; 117 118 auto cmp = [offset](const Association& a, uint16_t sequence_number) { 119 return static_cast<uint16_t>(a.sequence_number + offset) < 120 static_cast<uint16_t>(sequence_number + offset); 121 }; 122 const auto elem = absl::c_lower_bound(associations_, sequence_number, cmp); 123 124 return elem != associations_.end() && elem->sequence_number == sequence_number 125 ? std::optional<Info>(elem->info) 126 : std::nullopt; 127 } 128 129 size_t RtpSequenceNumberMap::AssociationCountForTesting() const { 130 return associations_.size(); 131 } 132 133 } // namespace webrtc