1 /* 2 * Copyright 2020 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <ftl/initializer_list.h> 20 #include <ftl/small_vector.h> 21 22 #include <functional> 23 #include <optional> 24 #include <type_traits> 25 #include <utility> 26 27 namespace android::ftl { 28 29 // Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are 30 // stored in contiguous storage for cache efficiency. The map is allocated statically until its size 31 // exceeds N, at which point mappings are relocated to dynamic memory. 32 // 33 // SmallMap<K, V, 0> unconditionally allocates on the heap. 34 // 35 // Example usage: 36 // 37 // ftl::SmallMap<int, std::string, 3> map; 38 // assert(map.empty()); 39 // assert(!map.dynamic()); 40 // 41 // map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?'); 42 // assert(map.size() == 3u); 43 // assert(!map.dynamic()); 44 // 45 // assert(map.contains(123)); 46 // assert(map.find(42, [](const std::string& s) { return s.size(); }) == 3u); 47 // 48 // const auto opt = map.find(-1); 49 // assert(opt); 50 // 51 // std::string& ref = *opt; 52 // assert(ref.empty()); 53 // ref = "xyz"; 54 // 55 // assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc"))); 56 // 57 template <typename K, typename V, std::size_t N> 58 class SmallMap final { 59 using Map = SmallVector<std::pair<const K, V>, N>; 60 61 public: 62 using key_type = K; 63 using mapped_type = V; 64 65 using value_type = typename Map::value_type; 66 using size_type = typename Map::size_type; 67 using difference_type = typename Map::difference_type; 68 69 using reference = typename Map::reference; 70 using iterator = typename Map::iterator; 71 72 using const_reference = typename Map::const_reference; 73 using const_iterator = typename Map::const_iterator; 74 75 // Creates an empty map. 76 SmallMap() = default; 77 78 // Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments. 79 // The template arguments K, V, and N are inferred using the deduction guide defined below. 80 // The syntax for listing pairs is as follows: 81 // 82 // ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?'); 83 // 84 // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>); 85 // assert(map.size() == 3u); 86 // assert(map.contains(-1) && map.find(-1)->get().empty()); 87 // assert(map.contains(42) && map.find(42)->get() == "???"); 88 // assert(map.contains(123) && map.find(123)->get() == "abc"); 89 // 90 // The types of the key and value are deduced if the first pair contains exactly two arguments: 91 // 92 // ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c'); 93 // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>); 94 // 95 template <typename U, std::size_t... Sizes, typename... Types> SmallMap(InitializerList<U,std::index_sequence<Sizes...>,Types...> && list)96 SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list) 97 : map_(std::move(list)) { 98 // TODO: Enforce unique keys. 99 } 100 max_size()101 size_type max_size() const { return map_.max_size(); } size()102 size_type size() const { return map_.size(); } empty()103 bool empty() const { return map_.empty(); } 104 105 // Returns whether the map is backed by static or dynamic storage. dynamic()106 bool dynamic() const { return map_.dynamic(); } 107 begin()108 iterator begin() { return map_.begin(); } begin()109 const_iterator begin() const { return cbegin(); } cbegin()110 const_iterator cbegin() const { return map_.cbegin(); } 111 end()112 iterator end() { return map_.end(); } end()113 const_iterator end() const { return cend(); } cend()114 const_iterator cend() const { return map_.cend(); } 115 116 // Returns whether a mapping exists for the given key. contains(const key_type & key)117 bool contains(const key_type& key) const { 118 return find(key, [](const mapped_type&) {}); 119 } 120 121 // Returns a reference to the value for the given key, or std::nullopt if the key was not found. 122 // 123 // ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C'); 124 // 125 // const auto opt = map.find('c'); 126 // assert(opt == 'C'); 127 // 128 // char d = 'd'; 129 // const auto ref = map.find('d').value_or(std::ref(d)); 130 // ref.get() = 'D'; 131 // assert(d == 'D'); 132 // 133 auto find(const key_type& key) const -> std::optional<std::reference_wrapper<const mapped_type>> { 134 return find(key, [](const mapped_type& v) { return std::cref(v); }); 135 } 136 137 auto find(const key_type& key) -> std::optional<std::reference_wrapper<mapped_type>> { 138 return find(key, [](mapped_type& v) { return std::ref(v); }); 139 } 140 141 // Returns the result R of a unary operation F on (a constant or mutable reference to) the value 142 // for the given key, or std::nullopt if the key was not found. If F has a return type of void, 143 // then the Boolean result indicates whether the key was found. 144 // 145 // ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z'); 146 // 147 // assert(map.find('c', [](char c) { return std::toupper(c); }) == 'Z'); 148 // assert(map.find('c', [](char& c) { c = std::toupper(c); })); 149 // 150 template <typename F, typename R = std::invoke_result_t<F, const mapped_type&>> 151 auto find(const key_type& key, F f) const 152 -> std::conditional_t<std::is_void_v<R>, bool, std::optional<R>> { 153 for (auto& [k, v] : *this) { 154 if (k == key) { 155 if constexpr (std::is_void_v<R>) { 156 f(v); 157 return true; 158 } else { 159 return f(v); 160 } 161 } 162 } 163 164 return {}; 165 } 166 167 template <typename F> find(const key_type & key,F f)168 auto find(const key_type& key, F f) { 169 return std::as_const(*this).find( 170 key, [&f](const mapped_type& v) { return f(const_cast<mapped_type&>(v)); }); 171 } 172 173 private: 174 Map map_; 175 }; 176 177 // Deduction guide for in-place constructor. 178 template <typename K, typename V, std::size_t... Sizes, typename... Types> 179 SmallMap(InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...>&&) 180 -> SmallMap<K, V, sizeof...(Sizes)>; 181 182 // Returns whether the key-value pairs of two maps are equal. 183 template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M> 184 bool operator==(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) { 185 if (lhs.size() != rhs.size()) return false; 186 187 for (const auto& [k, v] : lhs) { 188 const auto& lv = v; 189 if (!rhs.find(k, [&lv](const auto& rv) { return lv == rv; }).value_or(false)) { 190 return false; 191 } 192 } 193 194 return true; 195 } 196 197 // TODO: Remove in C++20. 198 template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M> 199 inline bool operator!=(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) { 200 return !(lhs == rhs); 201 } 202 203 } // namespace android::ftl 204