1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <algorithm> 17 #include <array> 18 #include <cstddef> 19 #include <cstdint> 20 #include <type_traits> 21 22 namespace pw::containers { 23 24 // A simple, fixed-size associative array with lookup by key or value. 25 // 26 // FlatMaps are initialized with a std::array of FlatMap::Pair objects: 27 // FlatMap<int, int> map({{{1, 2}, {3, 4}}}); 28 // 29 // The keys do not need to be sorted as the constructor will sort the items 30 // if need be. 31 template <typename Key, typename Value, size_t kArraySize> 32 class FlatMap { 33 public: 34 // Define and use a custom Pair object. This is because std::pair does not 35 // support constexpr assignment until C++20. The assignment is needed since 36 // the array of pairs will be sorted in the constructor (if not already). 37 template <typename First, typename Second> 38 struct Pair { 39 First first; 40 Second second; 41 }; 42 43 using key_type = Key; 44 using mapped_type = Value; 45 using value_type = Pair<key_type, mapped_type>; 46 using size_type = size_t; 47 using difference_type = ptrdiff_t; 48 using container_type = typename std::array<value_type, kArraySize>; 49 using iterator = typename container_type::iterator; 50 using const_iterator = typename container_type::const_iterator; 51 FlatMap(const std::array<value_type,kArraySize> & items)52 constexpr FlatMap(const std::array<value_type, kArraySize>& items) 53 : items_(items) { 54 ConstexprSort(items_.data(), kArraySize); 55 } 56 57 FlatMap(FlatMap&) = delete; 58 FlatMap& operator=(FlatMap&) = delete; 59 60 // Capacity. size()61 constexpr size_type size() const { return kArraySize; } empty()62 constexpr size_type empty() const { return size() == 0; } max_size()63 constexpr size_type max_size() const { return kArraySize; } 64 65 // Lookup. contains(const key_type & key)66 constexpr bool contains(const key_type& key) const { 67 return find(key) != end(); 68 } 69 find(const key_type & key)70 constexpr const_iterator find(const key_type& key) const { 71 if (end() == begin()) { 72 return end(); 73 } 74 75 const_iterator it = lower_bound(key); 76 return key == it->first ? it : end(); 77 } 78 lower_bound(const key_type & key)79 constexpr const_iterator lower_bound(const key_type& key) const { 80 return std::lower_bound( 81 begin(), end(), key, [](const value_type& item, key_type lkey) { 82 return item.first < lkey; 83 }); 84 } 85 upper_bound(const key_type & key)86 constexpr const_iterator upper_bound(const key_type& key) const { 87 return std::upper_bound( 88 begin(), end(), key, [](key_type lkey, const value_type& item) { 89 return item.first > lkey; 90 }); 91 } 92 equal_range(const key_type & key)93 constexpr std::pair<const_iterator, const_iterator> equal_range( 94 const key_type& key) const { 95 if (end() == begin()) { 96 return std::make_pair(end(), end()); 97 } 98 99 return std::make_pair(lower_bound(key), upper_bound(key)); 100 } 101 102 // Iterators. begin()103 constexpr const_iterator begin() const { return cbegin(); } cbegin()104 constexpr const_iterator cbegin() const { return items_.cbegin(); } end()105 constexpr const_iterator end() const { return cend(); } cend()106 constexpr const_iterator cend() const { return items_.cend(); } 107 108 private: 109 // Simple stable insertion sort function for constexpr support. 110 // std::stable_sort is not constexpr. Should not be a problem with performance 111 // in regards to the sizes that are typically dealt with. ConstexprSort(iterator data,size_type size)112 static constexpr void ConstexprSort(iterator data, size_type size) { 113 if (size < 2) { 114 return; 115 } 116 117 for (iterator it = data + 1, end = data + size; it < end; ++it) { 118 if (it->first < it[-1].first) { 119 // Rotate the value into place. 120 value_type temp = std::move(*it); 121 iterator it2 = it - 1; 122 while (true) { 123 *(it2 + 1) = std::move(*it2); 124 if (it2 == data || !(temp.first < it2[-1].first)) { 125 break; 126 } 127 --it2; 128 } 129 *it2 = std::move(temp); 130 } 131 } 132 } 133 134 std::array<value_type, kArraySize> items_; 135 }; 136 137 } // namespace pw::containers 138