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>

3 files changed, 178 insertions, 0 deletions

diff --git a/util/BUILD.gn b/util/BUILD.gn
index 9886c657..2e395b1e 100644
--- a/util/BUILD.gn
+++ b/util/BUILD.gn
@@ -41,6 +41,7 @@ source_set("util") {
     "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 @@ source_set("unittests") {
     "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 00000000..0e01b0fd
--- /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 00000000..308970de
--- /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