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