pw_containers: FlatMap class
pw::containers::FlatMap implements the std::map interface, but only
the accessors. pw::containers::FlatMap does not contain any methods
for modifying the data in the map. The FlatMap data during construction
does not have to be sorted and will automatically sort during
construction.
Testing:
Host test -- OK
Change-Id: I01740d0765ea18d81d9db7947a7f61e1ca563058
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/29320
Commit-Queue: Kevin Zeng <zengk@google.com>
Reviewed-by: Wyatt Hepler <hepler@google.com>
diff --git a/pw_containers/BUILD b/pw_containers/BUILD
index 0e2af8c..99926f4 100644
--- a/pw_containers/BUILD
+++ b/pw_containers/BUILD
@@ -25,6 +25,7 @@
pw_cc_library(
name = "pw_containers",
deps = [
+ ":flat_map",
":vector",
":intrusive_list",
],
@@ -51,6 +52,25 @@
includes = ["public"],
)
+pw_cc_library(
+ name = "flat_map",
+ hdrs = [
+ "public/pw_containers/flat_map.h",
+ ],
+ includes = ["public"],
+)
+
+pw_cc_test(
+ name = "flat_map_test",
+ srcs = [
+ "flat_map_test.cc",
+ ],
+ deps = [
+ ":pw_containers",
+ "//pw_unit_test",
+ ],
+)
+
pw_cc_test(
name = "vector_test",
srcs = [
diff --git a/pw_containers/BUILD.gn b/pw_containers/BUILD.gn
index a7d79b7..bf839ea 100644
--- a/pw_containers/BUILD.gn
+++ b/pw_containers/BUILD.gn
@@ -24,11 +24,17 @@
group("pw_containers") {
public_deps = [
+ ":flat_map",
":intrusive_list",
":vector",
]
}
+pw_source_set("flat_map") {
+ public_configs = [ ":default_config" ]
+ public = [ "public/pw_containers/flat_map.h" ]
+}
+
pw_source_set("vector") {
public_configs = [ ":default_config" ]
public = [ "public/pw_containers/vector.h" ]
@@ -40,28 +46,34 @@
"public/pw_containers/internal/intrusive_list_impl.h",
"public/pw_containers/intrusive_list.h",
]
- deps = [ dir_pw_assert ]
sources = [ "intrusive_list.cc" ]
+ deps = [ dir_pw_assert ]
}
pw_test_group("tests") {
tests = [
- ":vector_test",
+ ":flat_map_test",
":intrusive_list_test",
+ ":vector_test",
]
}
+pw_test("flat_map_test") {
+ sources = [ "flat_map_test.cc" ]
+ deps = [ ":flat_map" ]
+}
+
pw_test("vector_test") {
- deps = [ ":vector" ]
sources = [ "vector_test.cc" ]
+ deps = [ ":vector" ]
}
pw_test("intrusive_list_test") {
+ sources = [ "intrusive_list_test.cc" ]
deps = [
":intrusive_list",
"$dir_pw_preprocessor",
]
- sources = [ "intrusive_list_test.cc" ]
}
pw_doc_group("docs") {
diff --git a/pw_containers/docs.rst b/pw_containers/docs.rst
index dd36fc5..a4ffafa 100644
--- a/pw_containers/docs.rst
+++ b/pw_containers/docs.rst
@@ -34,6 +34,16 @@
list.
+pw::containers::FlatMap
+=======================
+FlatMap provides a simple, fixed-size associative array with lookup by key or
+value. ``pw::containers::FlatMap`` contains the same methods and features for
+looking up data as std::map. However, there are no methods that modify the
+underlying data. The underlying array in ``pw::containers::FlatMap`` does not
+need to be sorted. During construction, ``pw::containers::FlatMap`` will
+perform a constexpr insertion sort.
+
+
Usage
-----
While the API of `pw::IntrusiveList` is relatively similar to a
diff --git a/pw_containers/flat_map_test.cc b/pw_containers/flat_map_test.cc
new file mode 100644
index 0000000..51cf005
--- /dev/null
+++ b/pw_containers/flat_map_test.cc
@@ -0,0 +1,181 @@
+// Copyright 2020 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+#include "pw_containers/flat_map.h"
+
+#include <limits>
+
+#include "gtest/gtest.h"
+
+namespace pw::containers {
+namespace {
+constexpr FlatMap<int, char, 5> kOddMap({{
+ {-3, 'a'},
+ {0, 'b'},
+ {1, 'c'},
+ {50, 'd'},
+ {100, 'e'},
+}});
+} // namespace
+
+TEST(FlatMap, Size) { EXPECT_EQ(kOddMap.size(), static_cast<uint32_t>(5)); }
+
+TEST(FlatMap, EmptyFlatMapSize) {
+ constexpr FlatMap<int, char, 0> kEmpty({{}});
+ EXPECT_EQ(kEmpty.size(), static_cast<uint32_t>(0));
+}
+
+TEST(FlatMap, Empty) {
+ constexpr FlatMap<int, char, 0> kEmpty({{}});
+ EXPECT_TRUE(kEmpty.empty());
+}
+
+TEST(FlatMap, NotEmpty) {
+ constexpr FlatMap<int, char, 1> kNotEmpty({{}});
+ EXPECT_FALSE(kNotEmpty.empty());
+}
+
+TEST(FlatMap, EmptyFlatMapFind) {
+ constexpr FlatMap<int, char, 0> kEmpty({{}});
+ EXPECT_EQ(kEmpty.find(0), kEmpty.end());
+}
+
+TEST(FlatMap, EmptyFlatMapLowerBound) {
+ constexpr FlatMap<int, char, 0> kEmpty({{}});
+ EXPECT_EQ(kEmpty.lower_bound(0), kEmpty.end());
+}
+
+TEST(FlatMap, EmptyFlatMapUpperBound) {
+ constexpr FlatMap<int, char, 0> kEmpty({{}});
+ EXPECT_EQ(kEmpty.upper_bound(0), kEmpty.end());
+}
+
+TEST(FlatMap, EmptyEqualRange) {
+ constexpr FlatMap<int, char, 0> kEmpty({{}});
+ EXPECT_EQ(kEmpty.equal_range(0).first, kEmpty.end());
+ EXPECT_EQ(kEmpty.equal_range(0).second, kEmpty.end());
+}
+
+TEST(FlatMap, Contains) {
+ EXPECT_TRUE(kOddMap.contains(0));
+ EXPECT_FALSE(kOddMap.contains(10));
+}
+
+TEST(FlatMap, Iterate) {
+ char value = 'a';
+ for (const auto& item : kOddMap) {
+ EXPECT_EQ(value, item.second);
+ EXPECT_EQ(&item, kOddMap.find(item.first));
+ value += 1;
+ }
+}
+
+TEST(FlatMap, EqualRange) {
+ auto pair = kOddMap.equal_range(1);
+ EXPECT_EQ(1, pair.first->first);
+ EXPECT_EQ(50, pair.second->first);
+
+ pair = kOddMap.equal_range(75);
+ EXPECT_EQ(100, pair.first->first);
+ EXPECT_EQ(100, pair.second->first);
+}
+
+TEST(FlatMap, Find) {
+ auto it = kOddMap.find(50);
+ EXPECT_EQ(50, it->first);
+ EXPECT_EQ('d', it->second);
+
+ auto not_found = kOddMap.find(-1);
+ EXPECT_EQ(kOddMap.cend(), not_found);
+}
+
+TEST(FlatMap, UpperBoundLessThanSmallestKey) {
+ EXPECT_EQ(-3, kOddMap.upper_bound(std::numeric_limits<int>::min())->first);
+ EXPECT_EQ(-3, kOddMap.upper_bound(-123)->first);
+ EXPECT_EQ(-3, kOddMap.upper_bound(-4)->first);
+}
+
+TEST(FlatMap, UpperBoundBetweenTheTwoSmallestKeys) {
+ EXPECT_EQ(0, kOddMap.upper_bound(-3)->first);
+ EXPECT_EQ(0, kOddMap.upper_bound(-2)->first);
+ EXPECT_EQ(0, kOddMap.upper_bound(-1)->first);
+}
+
+TEST(FlatMap, UpperBoundIntermediateKeys) {
+ EXPECT_EQ(1, kOddMap.upper_bound(0)->first);
+ EXPECT_EQ('c', kOddMap.upper_bound(0)->second);
+ EXPECT_EQ(50, kOddMap.upper_bound(1)->first);
+ EXPECT_EQ('d', kOddMap.upper_bound(1)->second);
+ EXPECT_EQ(50, kOddMap.upper_bound(2)->first);
+ EXPECT_EQ(50, kOddMap.upper_bound(49)->first);
+ EXPECT_EQ(100, kOddMap.upper_bound(51)->first);
+}
+
+TEST(FlatMap, UpperBoundGreaterThanLargestKey) {
+ EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(100));
+ EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(2384924));
+ EXPECT_EQ(kOddMap.end(),
+ kOddMap.upper_bound(std::numeric_limits<int>::max()));
+}
+
+TEST(FlatMap, LowerBoundLessThanSmallestKey) {
+ EXPECT_EQ(-3, kOddMap.lower_bound(std::numeric_limits<int>::min())->first);
+ EXPECT_EQ(-3, kOddMap.lower_bound(-123)->first);
+ EXPECT_EQ(-3, kOddMap.lower_bound(-4)->first);
+}
+
+TEST(FlatMap, LowerBoundBetweenTwoSmallestKeys) {
+ EXPECT_EQ(-3, kOddMap.lower_bound(-3)->first);
+ EXPECT_EQ(0, kOddMap.lower_bound(-2)->first);
+ EXPECT_EQ(0, kOddMap.lower_bound(-1)->first);
+}
+
+TEST(FlatMap, LowerBoundIntermediateKeys) {
+ EXPECT_EQ(0, kOddMap.lower_bound(0)->first);
+ EXPECT_EQ('b', kOddMap.lower_bound(0)->second);
+ EXPECT_EQ(1, kOddMap.lower_bound(1)->first);
+ EXPECT_EQ('c', kOddMap.lower_bound(1)->second);
+ EXPECT_EQ(50, kOddMap.lower_bound(2)->first);
+ EXPECT_EQ(50, kOddMap.lower_bound(49)->first);
+ EXPECT_EQ(100, kOddMap.lower_bound(51)->first);
+}
+
+TEST(FlatMap, LowerBoundGreaterThanLargestKey) {
+ EXPECT_EQ(100, kOddMap.lower_bound(100)->first);
+ EXPECT_EQ(kOddMap.end(), kOddMap.lower_bound(2384924));
+ EXPECT_EQ(kOddMap.end(),
+ kOddMap.lower_bound(std::numeric_limits<int>::max()));
+}
+
+TEST(FlatMap, ForEachIteration) {
+ for (const auto& item : kOddMap) {
+ EXPECT_NE(item.first, 2);
+ }
+}
+
+TEST(FlatMap, MapsWithUnsortedKeys) {
+ constexpr FlatMap<int, const char*, 2> bad_array({{
+ {2, "hello"},
+ {1, "goodbye"},
+ }});
+
+ EXPECT_EQ(bad_array.begin()->first, 1);
+
+ constexpr FlatMap<int, const char*, 2> too_short({{
+ {1, "goodbye"},
+ }});
+ EXPECT_EQ(too_short.begin()->first, 0);
+}
+
+} // namespace pw::containers
diff --git a/pw_containers/public/pw_containers/flat_map.h b/pw_containers/public/pw_containers/flat_map.h
new file mode 100644
index 0000000..29daab0
--- /dev/null
+++ b/pw_containers/public/pw_containers/flat_map.h
@@ -0,0 +1,137 @@
+// Copyright 2020 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <type_traits>
+
+namespace pw::containers {
+
+// A simple, fixed-size associative array with lookup by key or value.
+//
+// FlatMaps are initialized with a std::array of FlatMap::Pair objects:
+// FlatMap<int, int> map({{{1, 2}, {3, 4}}});
+//
+// The keys do not need to be sorted as the constructor will sort the items
+// if need be.
+template <typename Key, typename Value, size_t array_size>
+class FlatMap {
+ public:
+ // Define and use a custom Pair object. This is because std::pair does not
+ // support constexpr assignment until C++20. The assignment is needed since
+ // the array of pairs will be sorted in the constructor (if not already).
+ template <typename First, typename Second>
+ struct Pair {
+ First first;
+ Second second;
+ };
+
+ using key_type = Key;
+ using mapped_type = Value;
+ using value_type = Pair<key_type, mapped_type>;
+ using size_type = size_t;
+ using difference_type = ptrdiff_t;
+ using container_type = typename std::array<value_type, array_size>;
+ using iterator = typename container_type::iterator;
+ using const_iterator = typename container_type::const_iterator;
+
+ constexpr FlatMap(const std::array<value_type, array_size>& items)
+ : items_(items) {
+ ConstexprSort(items_.data(), array_size);
+ }
+
+ FlatMap(FlatMap&) = delete;
+ FlatMap& operator=(FlatMap&) = delete;
+
+ // Capacity.
+ constexpr size_type size() const { return array_size; }
+ constexpr size_type empty() const { return size() == 0; }
+ constexpr size_type max_size() const { return array_size; }
+
+ // Lookup.
+ constexpr bool contains(const key_type& key) const {
+ return find(key) != end();
+ }
+
+ constexpr const_iterator find(const key_type& key) const {
+ if (end() == begin()) {
+ return end();
+ }
+
+ const_iterator it = lower_bound(key);
+ return key == it->first ? it : end();
+ }
+
+ constexpr const_iterator lower_bound(const key_type& key) const {
+ return std::lower_bound(
+ begin(), end(), key, [](const value_type& item, key_type lkey) {
+ return item.first < lkey;
+ });
+ }
+
+ constexpr const_iterator upper_bound(const key_type& key) const {
+ return std::upper_bound(
+ begin(), end(), key, [](key_type lkey, const value_type& item) {
+ return item.first > lkey;
+ });
+ }
+
+ constexpr std::pair<const_iterator, const_iterator> equal_range(
+ const key_type& key) const {
+ if (end() == begin()) {
+ return std::make_pair(end(), end());
+ }
+
+ return std::make_pair(lower_bound(key), upper_bound(key));
+ }
+
+ // Iterators.
+ constexpr const_iterator begin() const { return cbegin(); }
+ constexpr const_iterator cbegin() const { return items_.cbegin(); }
+ constexpr const_iterator end() const { return cend(); }
+ constexpr const_iterator cend() const { return items_.cend(); }
+
+ private:
+ // Simple stable insertion sort function for constexpr support.
+ // std::stable_sort is not constexpr. Should not be a problem with performance
+ // in regards to the sizes that are typically dealt with.
+ static constexpr void ConstexprSort(iterator data, size_type size) {
+ if (size < 2) {
+ return;
+ }
+
+ for (iterator it = data + 1, end = data + size; it < end; ++it) {
+ if (it->first < it[-1].first) {
+ // Rotate the value into place.
+ value_type temp = std::move(*it);
+ iterator it2 = it - 1;
+ while (true) {
+ *(it2 + 1) = std::move(*it2);
+ if (it2 == data || !(temp.first < it2[-1].first)) {
+ break;
+ }
+ --it2;
+ }
+ *it2 = std::move(temp);
+ }
+ }
+ }
+
+ std::array<value_type, array_size> items_;
+};
+
+} // namespace pw::containers