Add new FlatMap utility class

This patch adds a new FlatMap class in our utility component. This class
is intended as a drop-in replacement for
std::vector<std::pair<key,value>>, which ends up getting used as a
lower-cost std::map<key, value>, with some additional convenience
functions to make it behave more like a map.

This patch also replaces all std::vector<std::pair<>> declarations in
favor of FlatMap.

Change-Id: I1cbdc70998c9cc4754d20799ca0b4a6d30cb397a
Reviewed-on: https://chromium-review.googlesource.com/c/openscreen/+/2552695
Commit-Queue: Jordan Bayles <jophba@chromium.org>
Reviewed-by: Ryan Keane <rwkeane@google.com>
diff --git a/cast/streaming/receiver.h b/cast/streaming/receiver.h
index abdc185..4a927dd 100644
--- a/cast/streaming/receiver.h
+++ b/cast/streaming/receiver.h
@@ -29,6 +29,7 @@
 #include "cast/streaming/ssrc.h"
 #include "platform/api/time.h"
 #include "util/alarm.h"
+#include "util/flat_map.h"
 
 namespace openscreen {
 namespace cast {
@@ -321,8 +322,7 @@
   // The target playout delay is the amount of time between a frame's
   // capture/recording on the Sender and when it should be played-out at the
   // Receiver.
-  std::vector<std::pair<FrameId, std::chrono::milliseconds>>
-      playout_delay_changes_;
+  FlatMap<FrameId, std::chrono::milliseconds> playout_delay_changes_;
 
   // The consumer to notify when there are one or more frames completed and
   // ready to be consumed.
diff --git a/cast/streaming/receiver_packet_router.cc b/cast/streaming/receiver_packet_router.cc
index 0ac79d3..1ac4266 100644
--- a/cast/streaming/receiver_packet_router.cc
+++ b/cast/streaming/receiver_packet_router.cc
@@ -25,7 +25,7 @@
 
 void ReceiverPacketRouter::OnReceiverCreated(Ssrc sender_ssrc,
                                              Receiver* receiver) {
-  OSP_DCHECK(FindEntry(sender_ssrc) == receivers_.end());
+  OSP_DCHECK(receivers_.find(sender_ssrc) == receivers_.end());
   receivers_.emplace_back(sender_ssrc, receiver);
 
   // If there were no Receiver instances before, resume receiving packets for
@@ -38,10 +38,7 @@
 }
 
 void ReceiverPacketRouter::OnReceiverDestroyed(Ssrc sender_ssrc) {
-  const auto it = FindEntry(sender_ssrc);
-  OSP_DCHECK(it != receivers_.end());
-  receivers_.erase(it);
-
+  receivers_.erase_key(sender_ssrc);
   // If there are no longer any Receivers, suspend receiving packets.
   if (receivers_.empty()) {
     environment_->DropIncomingPackets();
@@ -82,29 +79,22 @@
                         0, kMaxPartiaHexDumpSize));
     return;
   }
-  const auto it = FindEntry(seems_like.second);
-  if (it != receivers_.end()) {
-    // At this point, a valid packet has been matched with a receiver. Lock-in
-    // the remote endpoint as the |source| of this |packet| so that only packets
-    // from the same source are permitted from here onwards.
-    if (environment_->remote_endpoint().port == 0) {
-      environment_->set_remote_endpoint(source);
-    }
-
-    if (seems_like.first == ApparentPacketType::RTP) {
-      it->second->OnReceivedRtpPacket(arrival_time, std::move(packet));
-    } else if (seems_like.first == ApparentPacketType::RTCP) {
-      it->second->OnReceivedRtcpPacket(arrival_time, std::move(packet));
-    }
+  auto it = receivers_.find(seems_like.second);
+  if (it == receivers_.end()) {
+    return;
   }
-}
+  // At this point, a valid packet has been matched with a receiver. Lock-in
+  // the remote endpoint as the |source| of this |packet| so that only packets
+  // from the same source are permitted from here onwards.
+  if (environment_->remote_endpoint().port == 0) {
+    environment_->set_remote_endpoint(source);
+  }
 
-ReceiverPacketRouter::ReceiverEntries::iterator ReceiverPacketRouter::FindEntry(
-    Ssrc sender_ssrc) {
-  return std::find_if(receivers_.begin(), receivers_.end(),
-                      [sender_ssrc](const ReceiverEntries::value_type& entry) {
-                        return entry.first == sender_ssrc;
-                      });
+  if (seems_like.first == ApparentPacketType::RTP) {
+    it->second->OnReceivedRtpPacket(arrival_time, std::move(packet));
+  } else if (seems_like.first == ApparentPacketType::RTCP) {
+    it->second->OnReceivedRtcpPacket(arrival_time, std::move(packet));
+  }
 }
 
 }  // namespace cast
diff --git a/cast/streaming/receiver_packet_router.h b/cast/streaming/receiver_packet_router.h
index d90e533..fe33d7d 100644
--- a/cast/streaming/receiver_packet_router.h
+++ b/cast/streaming/receiver_packet_router.h
@@ -13,6 +13,7 @@
 #include "absl/types/span.h"
 #include "cast/streaming/environment.h"
 #include "cast/streaming/ssrc.h"
+#include "util/flat_map.h"
 
 namespace openscreen {
 namespace cast {
@@ -44,20 +45,14 @@
   void SendRtcpPacket(absl::Span<const uint8_t> packet);
 
  private:
-  using ReceiverEntries = std::vector<std::pair<Ssrc, Receiver*>>;
-
   // Environment::PacketConsumer implementation.
   void OnReceivedPacket(const IPEndpoint& source,
                         Clock::time_point arrival_time,
                         std::vector<uint8_t> packet) final;
 
-  // Helper to return an iterator pointing to the entry corresponding to the
-  // given |sender_ssrc|, or "end" if not found.
-  ReceiverEntries::iterator FindEntry(Ssrc sender_ssrc);
-
   Environment* const environment_;
 
-  ReceiverEntries receivers_;
+  FlatMap<Ssrc, Receiver*> receivers_;
 };
 
 }  // namespace cast
diff --git a/cast/streaming/session_messager.cc b/cast/streaming/session_messager.cc
index af4dec1..e46f3b2 100644
--- a/cast/streaming/session_messager.cc
+++ b/cast/streaming/session_messager.cc
@@ -28,13 +28,8 @@
 
 void SessionMessager::SetHandler(std::string message_type,
                                  SessionMessager::MessageCallback cb) {
-  OSP_DCHECK(std::none_of(
-      callbacks_.begin(), callbacks_.end(),
-      [message_type](std::pair<std::string, MessageCallback> pair) {
-        return pair.first == message_type;
-      }));
-
-  callbacks_.emplace_back(message_type, std::move(cb));
+  OSP_DCHECK(callbacks_.find(message_type) == callbacks_.end());
+  callbacks_.emplace_back(std::move(message_type), std::move(cb));
 }
 
 Error SessionMessager::SendMessage(SessionMessager::Message message) {
@@ -96,22 +91,21 @@
     result.clear();
   }
 
-  for (const auto& pair : callbacks_) {
-    if (pair.first == type) {
-      // Currently all body keys are the lowercase version of the message type
-      // key. This may need to be refactored if this is no longer the case.
-      absl::AsciiStrToLower(&type);
-      Json::Value body;
-      if (result.empty() || result == kResultOk) {
-        body = message_json.value()[type];
-      } else {
-        body = message_json.value()[kErrorMessageBody];
-      }
-      pair.second(Message{source_id.data(), message_namespace.data(),
-                          sequence_number, std::move(body)});
-      return;
-    }
+  auto it = callbacks_.find(type);
+  if (it == callbacks_.end()) {
+    return;
   }
+  // Currently all body keys are the lowercase version of the message type
+  // key. This may need to be refactored if this is no longer the case.
+  absl::AsciiStrToLower(&type);
+  Json::Value body;
+  if (result.empty() || result == kResultOk) {
+    body = message_json.value()[type];
+  } else {
+    body = message_json.value()[kErrorMessageBody];
+  }
+  it->second(Message{source_id.data(), message_namespace.data(),
+                     sequence_number, std::move(body)});
 }
 
 void SessionMessager::OnError(Error error) {
diff --git a/cast/streaming/session_messager.h b/cast/streaming/session_messager.h
index eec8c01..ea39a4e 100644
--- a/cast/streaming/session_messager.h
+++ b/cast/streaming/session_messager.h
@@ -12,6 +12,7 @@
 
 #include "cast/common/public/message_port.h"
 #include "json/value.h"
+#include "util/flat_map.h"
 
 namespace openscreen {
 namespace cast {
@@ -64,8 +65,7 @@
  private:
   // Since the number of message callbacks is expected to be low,
   // we use a vector of key, value pairs instead of a map.
-  std::vector<std::pair<std::string, MessageCallback>> callbacks_;
-
+  FlatMap<std::string, MessageCallback> callbacks_;
   MessagePort* const message_port_;
   ErrorCallback error_callback_;
 };
diff --git a/util/BUILD.gn b/util/BUILD.gn
index 9886c65..2e395b1 100644
--- a/util/BUILD.gn
+++ b/util/BUILD.gn
@@ -41,6 +41,7 @@
     "crypto/sha2.cc",
     "crypto/sha2.h",
     "enum_name_table.h",
+    "flat_map.h",
     "hashing.h",
     "integer_division.h",
     "json/json_helpers.h",
@@ -93,6 +94,7 @@
     "crypto/secure_hash_unittest.cc",
     "crypto/sha2_unittest.cc",
     "enum_name_table_unittest.cc",
+    "flat_map_unittest.cc",
     "integer_division_unittest.cc",
     "json/json_helpers_unittest.cc",
     "json/json_serialization_unittest.cc",
diff --git a/util/flat_map.h b/util/flat_map.h
new file mode 100644
index 0000000..0e01b0f
--- /dev/null
+++ b/util/flat_map.h
@@ -0,0 +1,65 @@
+// Copyright 2020 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 UTIL_FLAT_MAP_H_
+#define UTIL_FLAT_MAP_H_
+
+#include <initializer_list>
+#include <map>
+#include <utility>
+#include <vector>
+
+#include "absl/types/optional.h"
+#include "util/osp_logging.h"
+
+namespace openscreen {
+
+// For small numbers of elements, a vector is much more efficient than a
+// map or unordered_map due to not needing hashing. FlatMap allows for
+// using map-like syntax but is backed by a std::vector, combining all the
+// performance of a vector with the convenience of a map.
+//
+// NOTE: this class allows usage of const char* as Key or Value types, but
+// it is generally recommended that you use std::string, or absl::string_view
+// for literals. string_view is similarly efficient to a raw char* pointer,
+// but gives sizing and equality operators, among other features.
+template <class Key, class Value>
+class FlatMap final : public std::vector<std::pair<Key, Value>> {
+ public:
+  FlatMap(std::initializer_list<std::pair<Key, Value>> init_list)
+      : std::vector<std::pair<Key, Value>>(init_list) {}
+  FlatMap() = default;
+  FlatMap(const FlatMap&) = default;
+  FlatMap(FlatMap&&) noexcept = default;
+  FlatMap& operator=(const FlatMap&) = default;
+  FlatMap& operator=(FlatMap&&) = default;
+  ~FlatMap() = default;
+
+  // Accessors that wrap std::find_if, and return an iterator to the key value
+  // pair.
+  decltype(auto) find(const Key& key) {
+    return std::find_if(
+        this->begin(), this->end(),
+        [key](const std::pair<Key, Value>& pair) { return key == pair.first; });
+  }
+
+  decltype(auto) find(const Key& key) const {
+    return const_cast<FlatMap<Key, Value>*>(this)->find(key);
+  }
+
+  // Remove an entry from the map. Returns an iterator pointing to the new
+  // location of the element that followed the last element erased by the
+  // function call. This is the container end if the operation erased the last
+  // element in the sequence.
+  decltype(auto) erase_key(const Key& key) {
+    auto it = find(key);
+    // This will otherwise segfault on platforms, as it is undefined behavior.
+    OSP_CHECK(it != this->end()) << "failed to erase: element not found";
+    return static_cast<std::vector<std::pair<Key, Value>>*>(this)->erase(it);
+  }
+};
+
+}  // namespace openscreen
+
+#endif  // UTIL_FLAT_MAP_H_
diff --git a/util/flat_map_unittest.cc b/util/flat_map_unittest.cc
new file mode 100644
index 0000000..308970d
--- /dev/null
+++ b/util/flat_map_unittest.cc
@@ -0,0 +1,111 @@
+// Copyright 2020 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.
+
+#include "util/flat_map.h"
+
+#include <chrono>
+
+#include "absl/strings/string_view.h"
+#include "gtest/gtest.h"
+
+namespace openscreen {
+
+namespace {
+
+const FlatMap<int, absl::string_view> kSimpleFlatMap{{-1, "bar"},
+                                                     {123, "foo"},
+                                                     {10000, "baz"},
+                                                     {0, ""}};
+
+}  // namespace
+
+TEST(FlatMapTest, Find) {
+  EXPECT_EQ(kSimpleFlatMap.begin(), kSimpleFlatMap.find(-1));
+  EXPECT_EQ("bar", kSimpleFlatMap.find(-1)->second);
+  EXPECT_EQ("foo", kSimpleFlatMap.find(123)->second);
+  EXPECT_EQ("baz", kSimpleFlatMap.find(10000)->second);
+  EXPECT_EQ("", kSimpleFlatMap.find(0)->second);
+  EXPECT_EQ(kSimpleFlatMap.end(), kSimpleFlatMap.find(2));
+}
+
+// Since it is backed by a vector, we don't expose an operator[] due
+// to potential confusion. If the type of Key is int or std::size_t, do
+// you want the std::pair<Key, Value> or just the Value?
+TEST(FlatMapTest, Access) {
+  EXPECT_EQ("bar", kSimpleFlatMap[0].second);
+  EXPECT_EQ("foo", kSimpleFlatMap[1].second);
+  EXPECT_EQ("baz", kSimpleFlatMap[2].second);
+  EXPECT_EQ("", kSimpleFlatMap[3].second);
+
+  // NOTE: vector doesn't do any range checking for operator[], only at().
+  EXPECT_EQ("bar", kSimpleFlatMap.at(0).second);
+  EXPECT_EQ("foo", kSimpleFlatMap.at(1).second);
+  EXPECT_EQ("baz", kSimpleFlatMap.at(2).second);
+  EXPECT_EQ("", kSimpleFlatMap.at(3).second);
+  EXPECT_DEATH(kSimpleFlatMap.at(31337), ".*std::out_of_range.*");
+}
+
+TEST(FlatMapTest, ErasureAndEmplacement) {
+  auto mutable_vector = kSimpleFlatMap;
+  EXPECT_NE(mutable_vector.find(-1), mutable_vector.end());
+  mutable_vector.erase_key(-1);
+  EXPECT_EQ(mutable_vector.find(-1), mutable_vector.end());
+
+  mutable_vector.emplace_back(-1, "bar");
+  EXPECT_NE(mutable_vector.find(-1), mutable_vector.end());
+
+  // We absolutely should fail to erase something that's not there.
+  EXPECT_DEATH(mutable_vector.erase_key(12345),
+               ".*failed to erase: element not found.*");
+}
+
+TEST(FlatMapTest, Mutation) {
+  FlatMap<int, int> mutable_vector{{1, 2}};
+  EXPECT_EQ(2, mutable_vector[0].second);
+
+  mutable_vector[0].second = 3;
+  EXPECT_EQ(3, mutable_vector[0].second);
+}
+
+TEST(FlatMapTest, GenerallyBehavesLikeAVector) {
+  EXPECT_EQ(kSimpleFlatMap, kSimpleFlatMap);
+  EXPECT_TRUE(kSimpleFlatMap == kSimpleFlatMap);
+
+  for (auto& entry : kSimpleFlatMap) {
+    if (entry.first != 0) {
+      EXPECT_LT(0u, entry.second.size());
+    }
+  }
+
+  FlatMap<int, int> simple;
+  simple.emplace_back(1, 10);
+  EXPECT_EQ(simple, (FlatMap<int, int>{{1, 10}}));
+
+  auto it = simple.find(1);
+  ASSERT_NE(it, simple.end());
+  simple.erase(it);
+  EXPECT_EQ(simple.find(1), simple.end());
+}
+
+TEST(FlatMapTest, CanUseNonDefaultConstructibleThings) {
+  class NonDefaultConstructible {
+   public:
+    NonDefaultConstructible(int x, int y) : x_(x), y_(y) {}
+
+    int x() { return x_; }
+
+    int y() { return y_; }
+
+   private:
+    int x_;
+    int y_;
+  };
+
+  FlatMap<int, NonDefaultConstructible> flat_map;
+  flat_map.emplace_back(3, NonDefaultConstructible(2, 3));
+  auto it = flat_map.find(3);
+  ASSERT_TRUE(it != flat_map.end());
+  EXPECT_GT(it->second.y(), it->second.x());
+}
+}  // namespace openscreen