Revert "Decrease complexity of RtpPacketHistory::GetBestFittingPacket."

This reverts commit 54caa4b68a0acb81c7f6ef60ffec45b473a7e1a2.

Reason for revert: Crashes on some perf tests.
https://logs.chromium.org/v/?s=chromium%2Fbb%2Fclient.webrtc.perf%2FLinux_Trusty%2F7170%2F%2B%2Frecipes%2Fsteps%2Fwebrtc_perf_tests%2F0%2Fstdout



Original change's description:
> Decrease complexity of RtpPacketHistory::GetBestFittingPacket.
> Use a map of packet sizes in RtpPacketHistory instead of looping through the whole history for every call.
> 
> Bug: webrtc:9731
> Change-Id: I44a4f6221e261a6cb3d5039edfa7556a102ee6f1
> Reviewed-on: https://webrtc-review.googlesource.com/98882
> Reviewed-by: Erik Språng <sprang@webrtc.org>
> Reviewed-by: Danil Chapovalov <danilchap@webrtc.org>
> Commit-Queue: Per Kjellander <perkj@webrtc.org>
> Cr-Commit-Position: refs/heads/master@{#24662}

TBR=danilchap@webrtc.org,sprang@webrtc.org,perkj@webrtc.org

Change-Id: Id183cd31a67117e9614d163e4388131fd88de07d
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: webrtc:9731
Reviewed-on: https://webrtc-review.googlesource.com/99440
Reviewed-by: Per Kjellander <perkj@webrtc.org>
Commit-Queue: Per Kjellander <perkj@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#24665}

3 files changed, 15 insertions, 106 deletions

diff --git a/modules/rtp_rtcp/source/rtp_packet_history.cc b/modules/rtp_rtcp/source/rtp_packet_history.cc
index c1bbbaf452..62f1c824dc 100644
--- a/modules/rtp_rtcp/source/rtp_packet_history.cc
+++ b/modules/rtp_rtcp/source/rtp_packet_history.cc
@@ -27,7 +27,8 @@ constexpr size_t kMinPacketRequestBytes = 50;
 
 // Utility function to get the absolute difference in size between the provided
 // target size and the size of packet.
-size_t SizeDiff(size_t packet_size, size_t size) {
+size_t SizeDiff(const std::unique_ptr<RtpPacketToSend>& packet, size_t size) {
+  size_t packet_size = packet->size();
   if (packet_size > size) {
     return packet_size - size;
   }
@@ -109,8 +110,6 @@ void RtpPacketHistory::PutRtpPacket(std::unique_ptr<RtpPacketToSend> packet,
   if (!start_seqno_) {
     start_seqno_ = rtp_seq_no;
   }
-  // Store the sequence number of the last send packet with this size.
-  packet_size_[stored_packet.packet->size()] = rtp_seq_no;
 }
 
 std::unique_ptr<RtpPacketToSend> RtpPacketHistory::GetPacketAndSetSendTime(
@@ -187,34 +186,28 @@ std::unique_ptr<RtpPacketToSend> RtpPacketHistory::GetBestFittingPacket(
     size_t packet_length) const {
   // TODO(sprang): Make this smarter, taking retransmit count etc into account.
   rtc::CritScope cs(&lock_);
-  if (packet_length < kMinPacketRequestBytes || packet_size_.empty()) {
+  if (packet_length < kMinPacketRequestBytes || packet_history_.empty()) {
     return nullptr;
   }
 
-  auto size_iter_upper = packet_size_.upper_bound(packet_length);
-  auto size_iter_lower = size_iter_upper;
-  if (size_iter_upper == packet_size_.end()) {
-    --size_iter_upper;
-  }
-  if (size_iter_lower != packet_size_.begin()) {
-    --size_iter_lower;
+  size_t min_diff = std::numeric_limits<size_t>::max();
+  RtpPacketToSend* best_packet = nullptr;
+  for (auto& it : packet_history_) {
+    size_t diff = SizeDiff(it.second.packet, packet_length);
+    if (!min_diff || diff < min_diff) {
+      min_diff = diff;
+      best_packet = it.second.packet.get();
+      if (diff == 0) {
+        break;
+      }
+    }
   }
-  const size_t upper_bound_diff =
-      SizeDiff(size_iter_upper->first, packet_length);
-  const size_t lower_bound_diff =
-      SizeDiff(size_iter_lower->first, packet_length);
-
-  const uint16_t seq_no = upper_bound_diff < lower_bound_diff
-                              ? size_iter_upper->second
-                              : size_iter_lower->second;
-  RtpPacketToSend* best_packet =
-      packet_history_.find(seq_no)->second.packet.get();
+
   return absl::make_unique<RtpPacketToSend>(*best_packet);
 }
 
 void RtpPacketHistory::Reset() {
   packet_history_.clear();
-  packet_size_.clear();
   start_seqno_.reset();
 }
 
@@ -279,12 +272,6 @@ std::unique_ptr<RtpPacketToSend> RtpPacketHistory::RemovePacket(
     start_seqno_.reset();
   }
 
-  auto size_iterator = packet_size_.find(rtp_packet->size());
-  RTC_CHECK(size_iterator != packet_size_.end());
-  if (size_iterator->second == rtp_packet->SequenceNumber()) {
-    packet_size_.erase(size_iterator);
-  }
-
   return rtp_packet;
 }
 
diff --git a/modules/rtp_rtcp/source/rtp_packet_history.h b/modules/rtp_rtcp/source/rtp_packet_history.h
index 1646ba7c76..433da0e7ee 100644
--- a/modules/rtp_rtcp/source/rtp_packet_history.h
+++ b/modules/rtp_rtcp/source/rtp_packet_history.h
@@ -136,7 +136,6 @@ class RtpPacketHistory {
 
   // Map from rtp sequence numbers to stored packet.
   std::map<uint16_t, StoredPacket> packet_history_ RTC_GUARDED_BY(lock_);
-  std::map<size_t, uint16_t> packet_size_ RTC_GUARDED_BY(lock_);
 
   // The earliest packet in the history. This might not be the lowest sequence
   // number, in case there is a wraparound.
diff --git a/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc b/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc
index 6df21e85b4..ab5aeb0be6 100644
--- a/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc
+++ b/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc
@@ -16,7 +16,6 @@
 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
 #include "modules/rtp_rtcp/source/rtp_packet_to_send.h"
 #include "system_wrappers/include/clock.h"
-#include "test/gmock.h"
 #include "test/gtest.h"
 
 namespace webrtc {
@@ -489,80 +488,4 @@ TEST_F(RtpPacketHistoryTest, GetBestFittingPacket) {
   EXPECT_EQ(target_packet_size,
             hist_.GetBestFittingPacket(target_packet_size)->size());
 }
-
-TEST_F(RtpPacketHistoryTest,
-       GetBestFittingPacketReturnsNextPacketWhenBestPacketHasBeenCulled) {
-  hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
-  std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
-  packet->SetPayloadSize(50);
-  const size_t target_packet_size = packet->size();
-  hist_.PutRtpPacket(std::move(packet), kAllowRetransmission,
-                     fake_clock_.TimeInMilliseconds());
-
-  packet = hist_.GetBestFittingPacket(target_packet_size + 2);
-  ASSERT_THAT(packet.get(), ::testing::NotNull());
-
-  // Send the packet and advance time past where packet expires.
-  ASSERT_THAT(hist_.GetPacketAndSetSendTime(kStartSeqNum, false),
-              ::testing::NotNull());
-  fake_clock_.AdvanceTimeMilliseconds(
-      RtpPacketHistory::kPacketCullingDelayFactor *
-      RtpPacketHistory::kMinPacketDurationMs);
-
-  packet = CreateRtpPacket(kStartSeqNum + 1);
-  packet->SetPayloadSize(100);
-  hist_.PutRtpPacket(std::move(packet), kAllowRetransmission,
-                     fake_clock_.TimeInMilliseconds());
-  ASSERT_FALSE(hist_.GetPacketState(kStartSeqNum, false));
-
-  auto best_packet = hist_.GetBestFittingPacket(target_packet_size + 2);
-  ASSERT_THAT(best_packet.get(), ::testing::NotNull());
-  EXPECT_EQ(best_packet->SequenceNumber(), kStartSeqNum + 1);
-}
-
-TEST_F(RtpPacketHistoryTest, GetBestFittingPacketReturnLastPacketWhenSameSize) {
-  const size_t kTargetSize = 500;
-  hist_.SetStorePacketsStatus(StorageMode::kStore, 10);
-
-  // Add two packets of same size.
-  std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
-  packet->SetPayloadSize(kTargetSize);
-  hist_.PutRtpPacket(std::move(packet), kAllowRetransmission,
-                     fake_clock_.TimeInMilliseconds());
-  packet = CreateRtpPacket(kStartSeqNum + 1);
-  packet->SetPayloadSize(kTargetSize);
-  hist_.PutRtpPacket(std::move(packet), kAllowRetransmission,
-                     fake_clock_.TimeInMilliseconds());
-
-  auto best_packet = hist_.GetBestFittingPacket(123);
-  ASSERT_THAT(best_packet.get(), ::testing::NotNull());
-  EXPECT_EQ(best_packet->SequenceNumber(), kStartSeqNum + 1);
-}
-
-TEST_F(RtpPacketHistoryTest,
-       GetBestFittingPacketReturnsPacketWithSmallestDiff) {
-  const size_t kTargetSize = 500;
-  hist_.SetStorePacketsStatus(StorageMode::kStore, 10);
-
-  // Add two packets of very different size.
-  std::unique_ptr<RtpPacketToSend> small_packet = CreateRtpPacket(kStartSeqNum);
-  small_packet->SetPayloadSize(kTargetSize);
-  hist_.PutRtpPacket(std::move(small_packet), kAllowRetransmission,
-                     fake_clock_.TimeInMilliseconds());
-
-  auto large_packet = CreateRtpPacket(kStartSeqNum + 1);
-  large_packet->SetPayloadSize(kTargetSize * 2);
-  hist_.PutRtpPacket(std::move(large_packet), kAllowRetransmission,
-                     fake_clock_.TimeInMilliseconds());
-
-  ASSERT_THAT(hist_.GetBestFittingPacket(kTargetSize), ::testing::NotNull());
-  EXPECT_EQ(hist_.GetBestFittingPacket(kTargetSize)->SequenceNumber(),
-            kStartSeqNum);
-
-  ASSERT_THAT(hist_.GetBestFittingPacket(kTargetSize * 2),
-              ::testing::NotNull());
-  EXPECT_EQ(hist_.GetBestFittingPacket(kTargetSize * 2)->SequenceNumber(),
-            kStartSeqNum + 1);
-}
-
 }  // namespace webrtc