1 // Copyright 2024 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 "pw_containers/internal/aa_tree.h" 17 #include "pw_containers/internal/aa_tree_item.h" 18 19 namespace pw { 20 21 /// A `std::multimap<Key, T, Compare>`-like class that uses intrusive items. 22 /// 23 /// Since the map structure is stored in the items themselves, each item must 24 /// outlive any map it is a part of and must be part of at most one map. 25 /// 26 /// This map requires unique keys. Attempting to add an item with same key as an 27 /// item already in the map will fail. 28 /// 29 /// - Since items are not allocated by this class, the following methods have 30 /// no analogue: 31 /// - std::multimap<T>::operator= 32 /// - std::multimap<T>::get_allocator 33 /// - std::multimap<T>::emplace 34 /// - std::multimap<T>::emplace_hint 35 /// 36 /// - Methods corresponding to the following take initializer lists of pointer 37 /// to items rather than the items themselves: 38 /// - std::multimap<T>::(constructor) 39 /// - std::multimap<T>::insert 40 /// 41 /// - There are no overloads corresponding to the following methods that take 42 /// r-value references.: 43 /// - std::multimap<T>::insert 44 /// - std::multimap<T>::merge 45 /// 46 /// - Since modifying the map modifies the items themselves, methods 47 /// corresponding to those below only take `iterator`s and not 48 /// `const_iterator`s: 49 /// - std::multimap<T>::insert 50 /// - std::multimap<T>::erase 51 /// 52 /// - An additional overload of `erase` is provided that takes a direct 53 /// reference to an item. 54 /// 55 /// - C++23 methods are not (yet) supported. 56 /// 57 /// @tparam Key Type to sort items on 58 /// @tparam T Type of values stored in the map. 59 template <typename Key, typename T> 60 class IntrusiveMultiMap { 61 private: 62 using GenericIterator = containers::internal::GenericAATree::iterator; 63 using Tree = containers::internal::AATree<Key, T>; 64 using Compare = typename Tree::Compare; 65 using GetKey = typename Tree::GetKey; 66 67 public: 68 /// IntrusiveMultiMap items must derive from either `Item` or `Pair`. 69 /// Use `Pair` to automatically provide storage for a `Key`. 70 /// Use `Item` when the derived type has a `key()` accessor method or when the 71 /// map provides a custom `GetKey` function object. 72 using Item = typename Tree::Item; 73 using Pair = typename Tree::Pair; 74 75 using key_type = Key; 76 using mapped_type = std::remove_cv_t<T>; 77 using value_type = Item; 78 using size_type = std::size_t; 79 using difference_type = std::ptrdiff_t; 80 using key_compare = Compare; 81 using reference = value_type&; 82 using const_reference = const value_type&; 83 using pointer = value_type*; 84 using const_pointer = const value_type*; 85 86 class iterator : public containers::internal::AATreeIterator<T> { 87 public: 88 constexpr iterator() = default; 89 90 private: 91 using Base = containers::internal::AATreeIterator<T>; 92 friend IntrusiveMultiMap; iterator(GenericIterator iter)93 constexpr explicit iterator(GenericIterator iter) : Base(iter) {} 94 }; 95 96 class const_iterator 97 : public containers::internal::AATreeIterator<std::add_const_t<T>> { 98 public: 99 constexpr const_iterator() = default; 100 101 private: 102 using Base = containers::internal::AATreeIterator<std::add_const_t<T>>; 103 friend IntrusiveMultiMap; const_iterator(GenericIterator iter)104 constexpr explicit const_iterator(GenericIterator iter) : Base(iter) {} 105 }; 106 107 using reverse_iterator = std::reverse_iterator<iterator>; 108 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 109 110 /// Constructs an empty map of items. IntrusiveMultiMap()111 constexpr explicit IntrusiveMultiMap() 112 : IntrusiveMultiMap(std::less<Key>()) {} 113 114 /// Constructs an empty map of items. 115 /// 116 /// SFINAE is used to disambiguate between this constructor and the one that 117 /// takes an initializer list. 118 /// 119 /// @param compare Function with the signature `bool(Key, Key)` that is 120 /// used to order items. 121 /// @param get_key Function with signature `Key(const T&)` that returns the 122 /// value that items are sorted on. 123 template <typename Comparator> IntrusiveMultiMap(Comparator && compare)124 constexpr explicit IntrusiveMultiMap(Comparator&& compare) 125 : IntrusiveMultiMap(std::forward<Comparator>(compare), 126 [](const T& t) { return t.key(); }) {} 127 128 /// Constructs an empty map of items. 129 /// 130 /// @param compare Function with the signature `bool(Key, Key)` that is 131 /// used to order items. 132 /// @param get_key Function with signature `Key(const T&)` that returns the 133 /// value that items are sorted on. 134 template <typename Comparator, typename KeyRetriever> IntrusiveMultiMap(Comparator && compare,KeyRetriever && get_key)135 constexpr IntrusiveMultiMap(Comparator&& compare, KeyRetriever&& get_key) 136 : tree_(false, 137 std::forward<Comparator>(compare), 138 std::forward<KeyRetriever>(get_key)) { 139 CheckItemType(); 140 } 141 142 /// Constructs an IntrusiveMultiMap from an iterator over Items. 143 /// 144 /// The iterator may dereference as either Item& (e.g. from std::array<Item>) 145 /// or Item* (e.g. from std::initializer_list<Item*>). 146 template <typename Iterator, typename... Functors> IntrusiveMultiMap(Iterator first,Iterator last,Functors &&...functors)147 IntrusiveMultiMap(Iterator first, Iterator last, Functors&&... functors) 148 : IntrusiveMultiMap(std::forward<Functors>(functors)...) { 149 tree_.insert(first, last); 150 } 151 152 /// Constructs an IntrusiveMultiMap from a std::initializer_list of pointers 153 /// to items. 154 template <typename... Functors> IntrusiveMultiMap(std::initializer_list<T * > items,Functors &&...functors)155 IntrusiveMultiMap(std::initializer_list<T*> items, Functors&&... functors) 156 : IntrusiveMultiMap( 157 items.begin(), items.end(), std::forward<Functors>(functors)...) {} 158 159 // Iterators 160 begin()161 iterator begin() noexcept { return iterator(tree_.begin()); } begin()162 const_iterator begin() const noexcept { 163 return const_iterator(tree_.begin()); 164 } cbegin()165 const_iterator cbegin() const noexcept { return begin(); } 166 end()167 iterator end() noexcept { return iterator(tree_.end()); } end()168 const_iterator end() const noexcept { return const_iterator(tree_.end()); } cend()169 const_iterator cend() const noexcept { return end(); } 170 rbegin()171 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } rbegin()172 const_reverse_iterator rbegin() const noexcept { 173 return const_reverse_iterator(end()); 174 } crbegin()175 const_reverse_iterator crbegin() const noexcept { return rbegin(); } 176 rend()177 reverse_iterator rend() noexcept { return reverse_iterator(begin()); } rend()178 const_reverse_iterator rend() const noexcept { 179 return const_reverse_iterator(begin()); 180 } crend()181 const_reverse_iterator crend() const noexcept { return rend(); } 182 183 // Capacity 184 185 /// Returns whether the multimap has zero items or not. empty()186 [[nodiscard]] bool empty() const noexcept { return tree_.empty(); } 187 188 /// Returns the number of items in the multimap. size()189 size_t size() const { return tree_.size(); } 190 191 /// Returns how many items can be added. 192 /// 193 /// As an intrusive container, this is effectively unbounded. max_size()194 constexpr size_t max_size() const noexcept { return tree_.max_size(); } 195 196 // Modifiers 197 198 /// Removes all items from the multimap and leaves it empty. 199 /// 200 /// The items themselves are not destructed. clear()201 void clear() { tree_.clear(); } 202 203 /// Adds the given item to the multimap. insert(T & item)204 iterator insert(T& item) { return iterator(tree_.insert(item).first); } 205 insert(iterator,T & item)206 iterator insert(iterator, T& item) { 207 // Disregard the hint. 208 return iterator(insert(item)); 209 } 210 211 template <class Iterator> insert(Iterator first,Iterator last)212 void insert(Iterator first, Iterator last) { 213 tree_.insert(first, last); 214 } 215 insert(std::initializer_list<T * > ilist)216 void insert(std::initializer_list<T*> ilist) { 217 tree_.insert(ilist.begin(), ilist.end()); 218 } 219 220 /// Removes an item from the multimap and returns an iterator to the item 221 /// after the removed item. 222 /// 223 /// The items themselves are not destructed. erase(T & item)224 iterator erase(T& item) { return iterator(tree_.erase_one(item)); } 225 erase(iterator pos)226 iterator erase(iterator pos) { return iterator(tree_.erase_one(*pos)); } 227 erase(iterator first,iterator last)228 iterator erase(iterator first, iterator last) { 229 return iterator(tree_.erase_range(*first, *last)); 230 } 231 erase(const Key & key)232 size_t erase(const Key& key) { return tree_.erase_all(key); } 233 234 /// Exchanges this multimap's items with the `other` multimap's items. swap(IntrusiveMultiMap<Key,T> & other)235 void swap(IntrusiveMultiMap<Key, T>& other) { tree_.swap(other.tree_); } 236 237 /// Splices items from the `other` map into this one. 238 template <typename MapType> merge(MapType & other)239 void merge(MapType& other) { 240 tree_.merge(other.tree_); 241 } 242 243 /// Returns the number of items in the multimap with the given key. count(const Key & key)244 size_t count(const Key& key) const { return tree_.count(key); } 245 246 /// Returns a pointer to an item with the given key, or null if the multimap 247 /// does not contain such an item. find(const Key & key)248 iterator find(const Key& key) { return iterator(tree_.find(key)); } 249 find(const Key & key)250 const_iterator find(const Key& key) const { 251 return const_iterator(tree_.find(key)); 252 } 253 254 /// Returns a pair of iterators where the first points to the item with the 255 /// smallest key that is not less than the given key, and the second points to 256 /// the item with the smallest key that is greater than the given key. equal_range(const Key & key)257 std::pair<iterator, iterator> equal_range(const Key& key) { 258 auto result = tree_.equal_range(key); 259 return std::make_pair(iterator(result.first), iterator(result.second)); 260 } equal_range(const Key & key)261 std::pair<const_iterator, const_iterator> equal_range(const Key& key) const { 262 auto result = tree_.equal_range(key); 263 return std::make_pair(const_iterator(result.first), 264 const_iterator(result.second)); 265 } 266 267 /// Returns an iterator to the item in the multimap with the smallest key that 268 /// is greater than or equal to the given key, or `end()` if the multimap is 269 /// empty. lower_bound(const Key & key)270 iterator lower_bound(const Key& key) { 271 return iterator(tree_.lower_bound(key)); 272 } lower_bound(const Key & key)273 const_iterator lower_bound(const Key& key) const { 274 return const_iterator(tree_.lower_bound(key)); 275 } 276 277 /// Returns an iterator to the item in the multimap with the smallest key that 278 /// is strictly greater than the given key, or `end()` if the multimap is 279 /// empty. upper_bound(const Key & key)280 iterator upper_bound(const Key& key) { 281 return iterator(tree_.upper_bound(key)); 282 } upper_bound(const Key & key)283 const_iterator upper_bound(const Key& key) const { 284 return const_iterator(tree_.upper_bound(key)); 285 } 286 287 private: 288 // Check that T is an Item in a function, since the class T will not be fully 289 // defined when the IntrusiveList<T> class is instantiated. CheckItemType()290 static constexpr void CheckItemType() { 291 using ItemBase = containers::internal::AATreeItem; 292 using IntrusiveItemType = 293 typename containers::internal::IntrusiveItem<ItemBase, T>::Type; 294 static_assert( 295 std::is_base_of<IntrusiveItemType, T>(), 296 "IntrusiveMultiMap items must be derived from " 297 "IntrusiveMultiMap<Key, T>::Item, where T is the item or one of its " 298 "bases."); 299 } 300 301 // Allow maps to access the tree for `merge`. 302 template <typename, typename> 303 friend class IntrusiveMap; 304 305 // The AA tree that stores the map. 306 // 307 // This field is mutable so that it doesn't need const overloads. 308 mutable Tree tree_; 309 }; 310 311 } // namespace pw 312