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