btree_container.h (36972B)
1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of 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, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_ 16 #define ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_ 17 18 #include <algorithm> 19 #include <initializer_list> 20 #include <iterator> 21 #include <type_traits> 22 #include <utility> 23 24 #include "absl/base/attributes.h" 25 #include "absl/base/internal/throw_delegate.h" 26 #include "absl/container/internal/btree.h" // IWYU pragma: export 27 #include "absl/container/internal/common.h" 28 #include "absl/memory/memory.h" 29 #include "absl/meta/type_traits.h" 30 31 namespace absl { 32 ABSL_NAMESPACE_BEGIN 33 namespace container_internal { 34 35 // A common base class for btree_set, btree_map, btree_multiset, and 36 // btree_multimap. 37 template <typename Tree> 38 class btree_container { 39 using params_type = typename Tree::params_type; 40 41 protected: 42 // Alias used for heterogeneous lookup functions. 43 // `key_arg<K>` evaluates to `K` when the functors are transparent and to 44 // `key_type` otherwise. It permits template argument deduction on `K` for the 45 // transparent case. 46 template <class K> 47 using key_arg = 48 typename KeyArg<params_type::kIsKeyCompareTransparent>::template type< 49 K, typename Tree::key_type>; 50 51 public: 52 using key_type = typename Tree::key_type; 53 using value_type = typename Tree::value_type; 54 using size_type = typename Tree::size_type; 55 using difference_type = typename Tree::difference_type; 56 using key_compare = typename Tree::original_key_compare; 57 using value_compare = typename Tree::value_compare; 58 using allocator_type = typename Tree::allocator_type; 59 using reference = typename Tree::reference; 60 using const_reference = typename Tree::const_reference; 61 using pointer = typename Tree::pointer; 62 using const_pointer = typename Tree::const_pointer; 63 using iterator = typename Tree::iterator; 64 using const_iterator = typename Tree::const_iterator; 65 using reverse_iterator = typename Tree::reverse_iterator; 66 using const_reverse_iterator = typename Tree::const_reverse_iterator; 67 using node_type = typename Tree::node_handle_type; 68 69 struct extract_and_get_next_return_type { 70 node_type node; 71 iterator next; 72 }; 73 74 // Constructors/assignments. 75 btree_container() : tree_(key_compare(), allocator_type()) {} 76 explicit btree_container(const key_compare &comp, 77 const allocator_type &alloc = allocator_type()) 78 : tree_(comp, alloc) {} 79 explicit btree_container(const allocator_type &alloc) 80 : tree_(key_compare(), alloc) {} 81 82 btree_container(const btree_container &other) 83 : btree_container(other, absl::allocator_traits<allocator_type>:: 84 select_on_container_copy_construction( 85 other.get_allocator())) {} 86 btree_container(const btree_container &other, const allocator_type &alloc) 87 : tree_(other.tree_, alloc) {} 88 89 btree_container(btree_container &&other) noexcept( 90 std::is_nothrow_move_constructible<Tree>::value) = default; 91 btree_container(btree_container &&other, const allocator_type &alloc) 92 : tree_(std::move(other.tree_), alloc) {} 93 94 btree_container &operator=(const btree_container &other) = default; 95 btree_container &operator=(btree_container &&other) noexcept( 96 std::is_nothrow_move_assignable<Tree>::value) = default; 97 98 // Iterator routines. 99 iterator begin() ABSL_ATTRIBUTE_LIFETIME_BOUND { return tree_.begin(); } 100 const_iterator begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 101 return tree_.begin(); 102 } 103 const_iterator cbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 104 return tree_.begin(); 105 } 106 iterator end() ABSL_ATTRIBUTE_LIFETIME_BOUND { return tree_.end(); } 107 const_iterator end() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 108 return tree_.end(); 109 } 110 const_iterator cend() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 111 return tree_.end(); 112 } 113 reverse_iterator rbegin() ABSL_ATTRIBUTE_LIFETIME_BOUND { 114 return tree_.rbegin(); 115 } 116 const_reverse_iterator rbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 117 return tree_.rbegin(); 118 } 119 const_reverse_iterator crbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 120 return tree_.rbegin(); 121 } 122 reverse_iterator rend() ABSL_ATTRIBUTE_LIFETIME_BOUND { return tree_.rend(); } 123 const_reverse_iterator rend() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 124 return tree_.rend(); 125 } 126 const_reverse_iterator crend() const ABSL_ATTRIBUTE_LIFETIME_BOUND { 127 return tree_.rend(); 128 } 129 130 // Lookup routines. 131 template <typename K = key_type> 132 size_type count(const key_arg<K> &key) const { 133 auto equal_range = this->equal_range(key); 134 return equal_range.second - equal_range.first; 135 } 136 template <typename K = key_type> 137 iterator find(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 138 return tree_.find(key); 139 } 140 template <typename K = key_type> 141 const_iterator find(const key_arg<K> &key) const 142 ABSL_ATTRIBUTE_LIFETIME_BOUND { 143 return tree_.find(key); 144 } 145 template <typename K = key_type> 146 bool contains(const key_arg<K> &key) const { 147 return find(key) != end(); 148 } 149 template <typename K = key_type> 150 iterator lower_bound(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 151 return tree_.lower_bound(key); 152 } 153 template <typename K = key_type> 154 const_iterator lower_bound(const key_arg<K> &key) const 155 ABSL_ATTRIBUTE_LIFETIME_BOUND { 156 return tree_.lower_bound(key); 157 } 158 template <typename K = key_type> 159 iterator upper_bound(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 160 return tree_.upper_bound(key); 161 } 162 template <typename K = key_type> 163 const_iterator upper_bound(const key_arg<K> &key) const 164 ABSL_ATTRIBUTE_LIFETIME_BOUND { 165 return tree_.upper_bound(key); 166 } 167 template <typename K = key_type> 168 std::pair<iterator, iterator> equal_range(const key_arg<K> &key) 169 ABSL_ATTRIBUTE_LIFETIME_BOUND { 170 return tree_.equal_range(key); 171 } 172 template <typename K = key_type> 173 std::pair<const_iterator, const_iterator> equal_range( 174 const key_arg<K> &key) const ABSL_ATTRIBUTE_LIFETIME_BOUND { 175 return tree_.equal_range(key); 176 } 177 178 // Deletion routines. Note that there is also a deletion routine that is 179 // specific to btree_set_container/btree_multiset_container. 180 181 // Erase the specified iterator from the btree. The iterator must be valid 182 // (i.e. not equal to end()). Return an iterator pointing to the node after 183 // the one that was erased (or end() if none exists). 184 iterator erase(const_iterator iter) ABSL_ATTRIBUTE_LIFETIME_BOUND { 185 return tree_.erase(iterator(iter)); 186 } 187 iterator erase(iterator iter) ABSL_ATTRIBUTE_LIFETIME_BOUND { 188 return tree_.erase(iter); 189 } 190 iterator erase(const_iterator first, 191 const_iterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND { 192 return tree_.erase_range(iterator(first), iterator(last)).second; 193 } 194 template <typename K = key_type> 195 size_type erase(const key_arg<K> &key) { 196 auto equal_range = this->equal_range(key); 197 return tree_.erase_range(equal_range.first, equal_range.second).first; 198 } 199 200 // Extract routines. 201 extract_and_get_next_return_type extract_and_get_next(const_iterator position) 202 ABSL_ATTRIBUTE_LIFETIME_BOUND { 203 // Use Construct instead of Transfer because the rebalancing code will 204 // destroy the slot later. 205 // Note: we rely on erase() taking place after Construct(). 206 return {CommonAccess::Construct<node_type>(get_allocator(), 207 iterator(position).slot()), 208 erase(position)}; 209 } 210 node_type extract(iterator position) { 211 // Use Construct instead of Transfer because the rebalancing code will 212 // destroy the slot later. 213 auto node = 214 CommonAccess::Construct<node_type>(get_allocator(), position.slot()); 215 erase(position); 216 return node; 217 } 218 node_type extract(const_iterator position) { 219 return extract(iterator(position)); 220 } 221 222 // Utility routines. 223 ABSL_ATTRIBUTE_REINITIALIZES void clear() { tree_.clear(); } 224 void swap(btree_container &other) { tree_.swap(other.tree_); } 225 void verify() const { tree_.verify(); } 226 227 // Size routines. 228 size_type size() const { return tree_.size(); } 229 size_type max_size() const { return tree_.max_size(); } 230 bool empty() const { return tree_.empty(); } 231 232 friend bool operator==(const btree_container &x, const btree_container &y) { 233 if (x.size() != y.size()) return false; 234 return std::equal(x.begin(), x.end(), y.begin()); 235 } 236 237 friend bool operator!=(const btree_container &x, const btree_container &y) { 238 return !(x == y); 239 } 240 241 friend bool operator<(const btree_container &x, const btree_container &y) { 242 return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); 243 } 244 245 friend bool operator>(const btree_container &x, const btree_container &y) { 246 return y < x; 247 } 248 249 friend bool operator<=(const btree_container &x, const btree_container &y) { 250 return !(y < x); 251 } 252 253 friend bool operator>=(const btree_container &x, const btree_container &y) { 254 return !(x < y); 255 } 256 257 // The allocator used by the btree. 258 allocator_type get_allocator() const { return tree_.get_allocator(); } 259 260 // The key comparator used by the btree. 261 key_compare key_comp() const { return key_compare(tree_.key_comp()); } 262 value_compare value_comp() const { return tree_.value_comp(); } 263 264 // Support absl::Hash. 265 template <typename State> 266 friend State AbslHashValue(State h, const btree_container &b) { 267 for (const auto &v : b) { 268 h = State::combine(std::move(h), v); 269 } 270 return State::combine(std::move(h), b.size()); 271 } 272 273 protected: 274 friend struct btree_access; 275 Tree tree_; 276 }; 277 278 // A common base class for btree_set and btree_map. 279 template <typename Tree> 280 class btree_set_container : public btree_container<Tree> { 281 using super_type = btree_container<Tree>; 282 using params_type = typename Tree::params_type; 283 using init_type = typename params_type::init_type; 284 using is_key_compare_to = typename params_type::is_key_compare_to; 285 friend class BtreeNodePeer; 286 287 protected: 288 template <class K> 289 using key_arg = typename super_type::template key_arg<K>; 290 291 public: 292 using key_type = typename Tree::key_type; 293 using value_type = typename Tree::value_type; 294 using size_type = typename Tree::size_type; 295 using key_compare = typename Tree::original_key_compare; 296 using allocator_type = typename Tree::allocator_type; 297 using iterator = typename Tree::iterator; 298 using const_iterator = typename Tree::const_iterator; 299 using node_type = typename super_type::node_type; 300 using insert_return_type = InsertReturnType<iterator, node_type>; 301 302 // Inherit constructors. 303 using super_type::super_type; 304 btree_set_container() {} 305 306 // Range constructors. 307 template <class InputIterator> 308 btree_set_container(InputIterator b, InputIterator e, 309 const key_compare &comp = key_compare(), 310 const allocator_type &alloc = allocator_type()) 311 : super_type(comp, alloc) { 312 insert(b, e); 313 } 314 template <class InputIterator> 315 btree_set_container(InputIterator b, InputIterator e, 316 const allocator_type &alloc) 317 : btree_set_container(b, e, key_compare(), alloc) {} 318 319 // Initializer list constructors. 320 btree_set_container(std::initializer_list<init_type> init, 321 const key_compare &comp = key_compare(), 322 const allocator_type &alloc = allocator_type()) 323 : btree_set_container(init.begin(), init.end(), comp, alloc) {} 324 btree_set_container(std::initializer_list<init_type> init, 325 const allocator_type &alloc) 326 : btree_set_container(init.begin(), init.end(), alloc) {} 327 328 // Insertion routines. 329 std::pair<iterator, bool> insert(const value_type &v) 330 ABSL_ATTRIBUTE_LIFETIME_BOUND { 331 return this->tree_.insert_unique(params_type::key(v), v); 332 } 333 std::pair<iterator, bool> insert(value_type &&v) 334 ABSL_ATTRIBUTE_LIFETIME_BOUND { 335 return this->tree_.insert_unique(params_type::key(v), std::move(v)); 336 } 337 template <typename... Args> 338 std::pair<iterator, bool> emplace(Args &&...args) 339 ABSL_ATTRIBUTE_LIFETIME_BOUND { 340 // Use a node handle to manage a temp slot. 341 auto node = CommonAccess::Construct<node_type>(this->get_allocator(), 342 std::forward<Args>(args)...); 343 auto *slot = CommonAccess::GetSlot(node); 344 return this->tree_.insert_unique(params_type::key(slot), slot); 345 } 346 iterator insert(const_iterator hint, 347 const value_type &v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 348 return this->tree_ 349 .insert_hint_unique(iterator(hint), params_type::key(v), v) 350 .first; 351 } 352 iterator insert(const_iterator hint, 353 value_type &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 354 return this->tree_ 355 .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v)) 356 .first; 357 } 358 template <typename... Args> 359 iterator emplace_hint(const_iterator hint, 360 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 361 // Use a node handle to manage a temp slot. 362 auto node = CommonAccess::Construct<node_type>(this->get_allocator(), 363 std::forward<Args>(args)...); 364 auto *slot = CommonAccess::GetSlot(node); 365 return this->tree_ 366 .insert_hint_unique(iterator(hint), params_type::key(slot), slot) 367 .first; 368 } 369 template <typename InputIterator> 370 void insert(InputIterator b, InputIterator e) { 371 this->tree_.insert_iterator_unique(b, e, 0); 372 } 373 void insert(std::initializer_list<init_type> init) { 374 this->tree_.insert_iterator_unique(init.begin(), init.end(), 0); 375 } 376 insert_return_type insert(node_type &&node) ABSL_ATTRIBUTE_LIFETIME_BOUND { 377 if (!node) return {this->end(), false, node_type()}; 378 std::pair<iterator, bool> res = 379 this->tree_.insert_unique(params_type::key(CommonAccess::GetSlot(node)), 380 CommonAccess::GetSlot(node)); 381 if (res.second) { 382 CommonAccess::Destroy(&node); 383 return {res.first, true, node_type()}; 384 } else { 385 return {res.first, false, std::move(node)}; 386 } 387 } 388 iterator insert(const_iterator hint, 389 node_type &&node) ABSL_ATTRIBUTE_LIFETIME_BOUND { 390 if (!node) return this->end(); 391 std::pair<iterator, bool> res = this->tree_.insert_hint_unique( 392 iterator(hint), params_type::key(CommonAccess::GetSlot(node)), 393 CommonAccess::GetSlot(node)); 394 if (res.second) CommonAccess::Destroy(&node); 395 return res.first; 396 } 397 398 // Node extraction routines. 399 template <typename K = key_type> 400 node_type extract(const key_arg<K> &key) { 401 const std::pair<iterator, bool> lower_and_equal = 402 this->tree_.lower_bound_equal(key); 403 return lower_and_equal.second ? extract(lower_and_equal.first) 404 : node_type(); 405 } 406 using super_type::extract; 407 408 // Merge routines. 409 // Moves elements from `src` into `this`. If the element already exists in 410 // `this`, it is left unmodified in `src`. 411 template < 412 typename T, 413 typename absl::enable_if_t< 414 absl::conjunction< 415 std::is_same<value_type, typename T::value_type>, 416 std::is_same<allocator_type, typename T::allocator_type>, 417 std::is_same<typename params_type::is_map_container, 418 typename T::params_type::is_map_container>>::value, 419 int> = 0> 420 void merge(btree_container<T> &src) { // NOLINT 421 for (auto src_it = src.begin(); src_it != src.end();) { 422 if (insert(std::move(params_type::element(src_it.slot()))).second) { 423 src_it = src.erase(src_it); 424 } else { 425 ++src_it; 426 } 427 } 428 } 429 430 template < 431 typename T, 432 typename absl::enable_if_t< 433 absl::conjunction< 434 std::is_same<value_type, typename T::value_type>, 435 std::is_same<allocator_type, typename T::allocator_type>, 436 std::is_same<typename params_type::is_map_container, 437 typename T::params_type::is_map_container>>::value, 438 int> = 0> 439 void merge(btree_container<T> &&src) { 440 merge(src); 441 } 442 }; 443 444 // Base class for btree_map. 445 template <typename Tree> 446 class btree_map_container : public btree_set_container<Tree> { 447 using super_type = btree_set_container<Tree>; 448 using params_type = typename Tree::params_type; 449 friend class BtreeNodePeer; 450 451 private: 452 template <class K> 453 using key_arg = typename super_type::template key_arg<K>; 454 455 // NOTE: The mess here is to shorten the code for the (very repetitive) 456 // function overloads, and to allow the lifetime-bound overloads to dispatch 457 // to the non-lifetime-bound overloads, to ensure there is a single source of 458 // truth for each overload set. 459 // 460 // Enabled if an assignment from the given type would require the 461 // source object to remain alive for the life of the element. 462 // 463 // TODO(b/402804213): Remove these traits and simplify the overloads whenever 464 // we have a better mechanism available to handle lifetime analysis. 465 template <class K, bool Value, typename = void> 466 using LifetimeBoundK = 467 HasValue<Value, type_traits_internal::IsLifetimeBoundAssignment< 468 typename Tree::key_type, K>>; 469 template <class M, bool Value, typename = void> 470 using LifetimeBoundV = 471 HasValue<Value, type_traits_internal::IsLifetimeBoundAssignment< 472 typename Tree::params_type::mapped_type, M>>; 473 template <class K, bool KValue, class M, bool MValue, typename... Dummy> 474 using LifetimeBoundKV = 475 absl::conjunction<LifetimeBoundK<K, KValue, absl::void_t<Dummy...>>, 476 LifetimeBoundV<M, MValue>>; 477 478 public: 479 using key_type = typename Tree::key_type; 480 using mapped_type = typename params_type::mapped_type; 481 using value_type = typename Tree::value_type; 482 using key_compare = typename Tree::original_key_compare; 483 using allocator_type = typename Tree::allocator_type; 484 using iterator = typename Tree::iterator; 485 using const_iterator = typename Tree::const_iterator; 486 487 // Inherit constructors. 488 using super_type::super_type; 489 btree_map_container() {} 490 491 // TODO(b/402804213): Remove these macros whenever we have a better mechanism 492 // available to handle lifetime analysis. 493 #define ABSL_INTERNAL_X(Func, Callee, KQual, MQual, KValue, MValue, ...) \ 494 template < \ 495 typename K = key_type, class M, \ 496 ABSL_INTERNAL_IF_##KValue##_NOR_##MValue( \ 497 int = (EnableIf<LifetimeBoundKV<K, KValue, M, MValue, \ 498 IfRRef<int KQual>::AddPtr<K>, \ 499 IfRRef<int MQual>::AddPtr<M>>>()), \ 500 ABSL_INTERNAL_SINGLE_ARG( \ 501 int &..., \ 502 decltype(EnableIf<LifetimeBoundKV<K, KValue, M, MValue>>()) = \ 503 0))> \ 504 decltype(auto) Func( \ 505 __VA_ARGS__ key_arg<K> KQual k ABSL_INTERNAL_IF_##KValue( \ 506 ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)), \ 507 M MQual obj ABSL_INTERNAL_IF_##MValue( \ 508 ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this))) \ 509 ABSL_ATTRIBUTE_LIFETIME_BOUND { \ 510 return ABSL_INTERNAL_IF_##KValue##_OR_##MValue( \ 511 (this->template Func<K, M, 0>), Callee)( \ 512 __VA_ARGS__ std::forward<decltype(k)>(k), \ 513 std::forward<decltype(obj)>(obj)); \ 514 } \ 515 friend struct std::enable_if<false> /* just to force a semicolon */ 516 // Insertion routines. 517 // Note: the nullptr template arguments and extra `const M&` overloads allow 518 // for supporting bitfield arguments. 519 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 520 false, false); 521 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 522 false, true); 523 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 524 true, false); 525 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 526 true, true); 527 528 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, false, 529 false); 530 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, false, 531 true); 532 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, true, 533 false); 534 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, true, 535 true); 536 537 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, false, 538 false); 539 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, false, 540 true); 541 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, true, 542 false); 543 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, true, 544 true); 545 546 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, 547 false); 548 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, true); 549 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, false); 550 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, true); 551 552 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, 553 const &, false, false, 554 const_iterator(hint) ABSL_INTERNAL_COMMA); 555 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, 556 const &, false, true, 557 const_iterator(hint) ABSL_INTERNAL_COMMA); 558 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, 559 const &, true, false, 560 const_iterator(hint) ABSL_INTERNAL_COMMA); 561 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, 562 const &, true, true, 563 const_iterator(hint) ABSL_INTERNAL_COMMA); 564 565 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, &&, 566 false, false, const_iterator(hint) ABSL_INTERNAL_COMMA); 567 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, &&, 568 false, true, const_iterator(hint) ABSL_INTERNAL_COMMA); 569 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, &&, 570 true, false, const_iterator(hint) ABSL_INTERNAL_COMMA); 571 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, const &, &&, 572 true, true, const_iterator(hint) ABSL_INTERNAL_COMMA); 573 574 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, const &, 575 false, false, const_iterator(hint) ABSL_INTERNAL_COMMA); 576 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, const &, 577 false, true, const_iterator(hint) ABSL_INTERNAL_COMMA); 578 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, const &, 579 true, false, const_iterator(hint) ABSL_INTERNAL_COMMA); 580 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, const &, 581 true, true, const_iterator(hint) ABSL_INTERNAL_COMMA); 582 583 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, &&, false, 584 false, const_iterator(hint) ABSL_INTERNAL_COMMA); 585 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, &&, false, 586 true, const_iterator(hint) ABSL_INTERNAL_COMMA); 587 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, &&, true, 588 false, const_iterator(hint) ABSL_INTERNAL_COMMA); 589 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_hint_impl, &&, &&, true, 590 true, const_iterator(hint) ABSL_INTERNAL_COMMA); 591 #undef ABSL_INTERNAL_X 592 593 #define ABSL_INTERNAL_X(Func, Callee, KQual, KValue, ...) \ 594 template < \ 595 class K = key_type, \ 596 ABSL_INTERNAL_IF_##KValue( \ 597 class... Args, \ 598 int = (EnableIf< \ 599 LifetimeBoundK<K, KValue, IfRRef<int KQual>::AddPtr<K>>>())), \ 600 ABSL_INTERNAL_IF_##KValue( \ 601 decltype(EnableIf<LifetimeBoundK< \ 602 K, KValue, IfRRef<int KQual>::AddPtr<K>>>()) = 0, \ 603 class... Args), \ 604 std::enable_if_t<!std::is_convertible<K, const_iterator>::value, int> = \ 605 0> \ 606 decltype(auto) Func( \ 607 __VA_ARGS__ key_arg<K> KQual k ABSL_INTERNAL_IF_##KValue( \ 608 ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)), \ 609 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { \ 610 return ABSL_INTERNAL_IF_##KValue((this->template Func<K, 0>), Callee)( \ 611 __VA_ARGS__ std::forward<decltype(k)>(k), \ 612 std::forward<decltype(args)>(args)...); \ 613 } \ 614 friend struct std::enable_if<false> /* just to force a semicolon */ 615 ABSL_INTERNAL_X(try_emplace, try_emplace_impl, const &, false); 616 ABSL_INTERNAL_X(try_emplace, try_emplace_impl, const &, true); 617 ABSL_INTERNAL_X(try_emplace, try_emplace_impl, &&, false); 618 ABSL_INTERNAL_X(try_emplace, try_emplace_impl, &&, true); 619 ABSL_INTERNAL_X(try_emplace, try_emplace_hint_impl, const &, false, 620 const_iterator(hint) ABSL_INTERNAL_COMMA); 621 ABSL_INTERNAL_X(try_emplace, try_emplace_hint_impl, const &, true, 622 const_iterator(hint) ABSL_INTERNAL_COMMA); 623 ABSL_INTERNAL_X(try_emplace, try_emplace_hint_impl, &&, false, 624 const_iterator(hint) ABSL_INTERNAL_COMMA); 625 ABSL_INTERNAL_X(try_emplace, try_emplace_hint_impl, &&, true, 626 const_iterator(hint) ABSL_INTERNAL_COMMA); 627 #undef ABSL_INTERNAL_X 628 629 template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false>>()> 630 mapped_type &operator[](const key_arg<K> &k) ABSL_ATTRIBUTE_LIFETIME_BOUND { 631 return try_emplace(k).first->second; 632 } 633 template <class K = key_type, int &..., EnableIf<LifetimeBoundK<K, true>> = 0> 634 mapped_type &operator[]( 635 const key_arg<K> &k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)) 636 ABSL_ATTRIBUTE_LIFETIME_BOUND { 637 return this->template operator[]<K, 0>(k); 638 } 639 template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false>>()> 640 mapped_type &operator[](key_arg<K> &&k) ABSL_ATTRIBUTE_LIFETIME_BOUND { 641 return try_emplace(std::forward<K>(k)).first->second; 642 } 643 template <class K = key_type, int &..., EnableIf<LifetimeBoundK<K, true>> = 0> 644 mapped_type &operator[](key_arg<K> &&k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY( 645 this)) ABSL_ATTRIBUTE_LIFETIME_BOUND { 646 return this->template operator[]<K, 0>(std::forward<K>(k)); 647 } 648 649 template <typename K = key_type> 650 mapped_type &at(const key_arg<K> &key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 651 auto it = this->find(key); 652 if (it == this->end()) 653 base_internal::ThrowStdOutOfRange("absl::btree_map::at"); 654 return it->second; 655 } 656 template <typename K = key_type> 657 const mapped_type &at(const key_arg<K> &key) const 658 ABSL_ATTRIBUTE_LIFETIME_BOUND { 659 auto it = this->find(key); 660 if (it == this->end()) 661 base_internal::ThrowStdOutOfRange("absl::btree_map::at"); 662 return it->second; 663 } 664 665 private: 666 // Note: when we call `std::forward<M>(obj)` twice, it's safe because 667 // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when 668 // `ret.second` is false. 669 template <class K, class M> 670 std::pair<iterator, bool> insert_or_assign_impl(K &&k, M &&obj) { 671 const std::pair<iterator, bool> ret = 672 this->tree_.insert_unique(k, std::forward<K>(k), std::forward<M>(obj)); 673 if (!ret.second) ret.first->second = std::forward<M>(obj); 674 return ret; 675 } 676 template <class K, class M> 677 iterator insert_or_assign_hint_impl(const_iterator hint, K &&k, M &&obj) { 678 const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique( 679 iterator(hint), k, std::forward<K>(k), std::forward<M>(obj)); 680 if (!ret.second) ret.first->second = std::forward<M>(obj); 681 return ret.first; 682 } 683 684 template <class K, class... Args> 685 std::pair<iterator, bool> try_emplace_impl(K &&k, Args &&... args) { 686 return this->tree_.insert_unique( 687 k, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(k)), 688 std::forward_as_tuple(std::forward<Args>(args)...)); 689 } 690 template <class K, class... Args> 691 iterator try_emplace_hint_impl(const_iterator hint, K &&k, Args &&... args) { 692 return this->tree_ 693 .insert_hint_unique(iterator(hint), k, std::piecewise_construct, 694 std::forward_as_tuple(std::forward<K>(k)), 695 std::forward_as_tuple(std::forward<Args>(args)...)) 696 .first; 697 } 698 }; 699 700 // A common base class for btree_multiset and btree_multimap. 701 template <typename Tree> 702 class btree_multiset_container : public btree_container<Tree> { 703 using super_type = btree_container<Tree>; 704 using params_type = typename Tree::params_type; 705 using init_type = typename params_type::init_type; 706 using is_key_compare_to = typename params_type::is_key_compare_to; 707 friend class BtreeNodePeer; 708 709 template <class K> 710 using key_arg = typename super_type::template key_arg<K>; 711 712 public: 713 using key_type = typename Tree::key_type; 714 using value_type = typename Tree::value_type; 715 using size_type = typename Tree::size_type; 716 using key_compare = typename Tree::original_key_compare; 717 using allocator_type = typename Tree::allocator_type; 718 using iterator = typename Tree::iterator; 719 using const_iterator = typename Tree::const_iterator; 720 using node_type = typename super_type::node_type; 721 722 // Inherit constructors. 723 using super_type::super_type; 724 btree_multiset_container() {} 725 726 // Range constructors. 727 template <class InputIterator> 728 btree_multiset_container(InputIterator b, InputIterator e, 729 const key_compare &comp = key_compare(), 730 const allocator_type &alloc = allocator_type()) 731 : super_type(comp, alloc) { 732 insert(b, e); 733 } 734 template <class InputIterator> 735 btree_multiset_container(InputIterator b, InputIterator e, 736 const allocator_type &alloc) 737 : btree_multiset_container(b, e, key_compare(), alloc) {} 738 739 // Initializer list constructors. 740 btree_multiset_container(std::initializer_list<init_type> init, 741 const key_compare &comp = key_compare(), 742 const allocator_type &alloc = allocator_type()) 743 : btree_multiset_container(init.begin(), init.end(), comp, alloc) {} 744 btree_multiset_container(std::initializer_list<init_type> init, 745 const allocator_type &alloc) 746 : btree_multiset_container(init.begin(), init.end(), alloc) {} 747 748 // Insertion routines. 749 iterator insert(const value_type &v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 750 return this->tree_.insert_multi(v); 751 } 752 iterator insert(value_type &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 753 return this->tree_.insert_multi(std::move(v)); 754 } 755 iterator insert(const_iterator hint, 756 const value_type &v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 757 return this->tree_.insert_hint_multi(iterator(hint), v); 758 } 759 iterator insert(const_iterator hint, 760 value_type &&v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 761 return this->tree_.insert_hint_multi(iterator(hint), std::move(v)); 762 } 763 template <typename InputIterator> 764 void insert(InputIterator b, InputIterator e) { 765 this->tree_.insert_iterator_multi(b, e); 766 } 767 void insert(std::initializer_list<init_type> init) { 768 this->tree_.insert_iterator_multi(init.begin(), init.end()); 769 } 770 template <typename... Args> 771 iterator emplace(Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 772 // Use a node handle to manage a temp slot. 773 auto node = CommonAccess::Construct<node_type>(this->get_allocator(), 774 std::forward<Args>(args)...); 775 return this->tree_.insert_multi(CommonAccess::GetSlot(node)); 776 } 777 template <typename... Args> 778 iterator emplace_hint(const_iterator hint, 779 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 780 // Use a node handle to manage a temp slot. 781 auto node = CommonAccess::Construct<node_type>(this->get_allocator(), 782 std::forward<Args>(args)...); 783 return this->tree_.insert_hint_multi(iterator(hint), 784 CommonAccess::GetSlot(node)); 785 } 786 iterator insert(node_type &&node) ABSL_ATTRIBUTE_LIFETIME_BOUND { 787 if (!node) return this->end(); 788 iterator res = 789 this->tree_.insert_multi(params_type::key(CommonAccess::GetSlot(node)), 790 CommonAccess::GetSlot(node)); 791 CommonAccess::Destroy(&node); 792 return res; 793 } 794 iterator insert(const_iterator hint, 795 node_type &&node) ABSL_ATTRIBUTE_LIFETIME_BOUND { 796 if (!node) return this->end(); 797 iterator res = this->tree_.insert_hint_multi( 798 iterator(hint), 799 std::move(params_type::element(CommonAccess::GetSlot(node)))); 800 CommonAccess::Destroy(&node); 801 return res; 802 } 803 804 // Node extraction routines. 805 template <typename K = key_type> 806 node_type extract(const key_arg<K> &key) { 807 const std::pair<iterator, bool> lower_and_equal = 808 this->tree_.lower_bound_equal(key); 809 return lower_and_equal.second ? extract(lower_and_equal.first) 810 : node_type(); 811 } 812 using super_type::extract; 813 814 // Merge routines. 815 // Moves all elements from `src` into `this`. 816 template < 817 typename T, 818 typename absl::enable_if_t< 819 absl::conjunction< 820 std::is_same<value_type, typename T::value_type>, 821 std::is_same<allocator_type, typename T::allocator_type>, 822 std::is_same<typename params_type::is_map_container, 823 typename T::params_type::is_map_container>>::value, 824 int> = 0> 825 void merge(btree_container<T> &src) { // NOLINT 826 for (auto src_it = src.begin(), end = src.end(); src_it != end; ++src_it) { 827 insert(std::move(params_type::element(src_it.slot()))); 828 } 829 src.clear(); 830 } 831 832 template < 833 typename T, 834 typename absl::enable_if_t< 835 absl::conjunction< 836 std::is_same<value_type, typename T::value_type>, 837 std::is_same<allocator_type, typename T::allocator_type>, 838 std::is_same<typename params_type::is_map_container, 839 typename T::params_type::is_map_container>>::value, 840 int> = 0> 841 void merge(btree_container<T> &&src) { 842 merge(src); 843 } 844 }; 845 846 // A base class for btree_multimap. 847 template <typename Tree> 848 class btree_multimap_container : public btree_multiset_container<Tree> { 849 using super_type = btree_multiset_container<Tree>; 850 using params_type = typename Tree::params_type; 851 friend class BtreeNodePeer; 852 853 public: 854 using mapped_type = typename params_type::mapped_type; 855 856 // Inherit constructors. 857 using super_type::super_type; 858 btree_multimap_container() {} 859 }; 860 861 } // namespace container_internal 862 ABSL_NAMESPACE_END 863 } // namespace absl 864 865 #endif // ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_