1 files changed, 137 insertions, 0 deletions
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 000000000..b4c2ab537
--- /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 kArraySize>
+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, kArraySize>;
+  using iterator = typename container_type::iterator;
+  using const_iterator = typename container_type::const_iterator;
+
+  constexpr FlatMap(const std::array<value_type, kArraySize>& items)
+      : items_(items) {
+    ConstexprSort(items_.data(), kArraySize);
+  }
+
+  FlatMap(FlatMap&) = delete;
+  FlatMap& operator=(FlatMap&) = delete;
+
+  // Capacity.
+  constexpr size_type size() const { return kArraySize; }
+  constexpr size_type empty() const { return size() == 0; }
+  constexpr size_type max_size() const { return kArraySize; }
+
+  // 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, kArraySize> items_;
+};
+
+}  // namespace pw::containers