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 // A btree implementation of the STL set and map interfaces. A btree is smaller 16 // and generally also faster than STL set/map (refer to the benchmarks below). 17 // The red-black tree implementation of STL set/map has an overhead of 3 18 // pointers (left, right and parent) plus the node color information for each 19 // stored value. So a set<int32_t> consumes 40 bytes for each value stored in 20 // 64-bit mode. This btree implementation stores multiple values on fixed 21 // size nodes (usually 256 bytes) and doesn't store child pointers for leaf 22 // nodes. The result is that a btree_set<int32_t> may use much less memory per 23 // stored value. For the random insertion benchmark in btree_bench.cc, a 24 // btree_set<int32_t> with node-size of 256 uses 5.1 bytes per stored value. 25 // 26 // The packing of multiple values on to each node of a btree has another effect 27 // besides better space utilization: better cache locality due to fewer cache 28 // lines being accessed. Better cache locality translates into faster 29 // operations. 30 // 31 // CAVEATS 32 // 33 // Insertions and deletions on a btree can cause splitting, merging or 34 // rebalancing of btree nodes. And even without these operations, insertions 35 // and deletions on a btree will move values around within a node. In both 36 // cases, the result is that insertions and deletions can invalidate iterators 37 // pointing to values other than the one being inserted/deleted. Therefore, this 38 // container does not provide pointer stability. This is notably different from 39 // STL set/map which takes care to not invalidate iterators on insert/erase 40 // except, of course, for iterators pointing to the value being erased. A 41 // partial workaround when erasing is available: erase() returns an iterator 42 // pointing to the item just after the one that was erased (or end() if none 43 // exists). 44 45 #ifndef ABSL_CONTAINER_INTERNAL_BTREE_H_ 46 #define ABSL_CONTAINER_INTERNAL_BTREE_H_ 47 48 #include <algorithm> 49 #include <cassert> 50 #include <cstddef> 51 #include <cstdint> 52 #include <cstring> 53 #include <functional> 54 #include <iterator> 55 #include <limits> 56 #include <new> 57 #include <string> 58 #include <type_traits> 59 #include <utility> 60 61 #include "absl/base/macros.h" 62 #include "absl/container/internal/common.h" 63 #include "absl/container/internal/compressed_tuple.h" 64 #include "absl/container/internal/container_memory.h" 65 #include "absl/container/internal/layout.h" 66 #include "absl/memory/memory.h" 67 #include "absl/meta/type_traits.h" 68 #include "absl/strings/cord.h" 69 #include "absl/strings/string_view.h" 70 #include "absl/types/compare.h" 71 #include "absl/utility/utility.h" 72 73 namespace absl { 74 ABSL_NAMESPACE_BEGIN 75 namespace container_internal { 76 77 // A helper class that indicates if the Compare parameter is a key-compare-to 78 // comparator. 79 template <typename Compare, typename T> 80 using btree_is_key_compare_to = 81 std::is_convertible<absl::result_of_t<Compare(const T &, const T &)>, 82 absl::weak_ordering>; 83 84 struct StringBtreeDefaultLess { 85 using is_transparent = void; 86 87 StringBtreeDefaultLess() = default; 88 89 // Compatibility constructor. StringBtreeDefaultLessStringBtreeDefaultLess90 StringBtreeDefaultLess(std::less<std::string>) {} // NOLINT StringBtreeDefaultLessStringBtreeDefaultLess91 StringBtreeDefaultLess(std::less<string_view>) {} // NOLINT 92 operatorStringBtreeDefaultLess93 absl::weak_ordering operator()(absl::string_view lhs, 94 absl::string_view rhs) const { 95 return compare_internal::compare_result_as_ordering(lhs.compare(rhs)); 96 } StringBtreeDefaultLessStringBtreeDefaultLess97 StringBtreeDefaultLess(std::less<absl::Cord>) {} // NOLINT operatorStringBtreeDefaultLess98 absl::weak_ordering operator()(const absl::Cord &lhs, 99 const absl::Cord &rhs) const { 100 return compare_internal::compare_result_as_ordering(lhs.Compare(rhs)); 101 } operatorStringBtreeDefaultLess102 absl::weak_ordering operator()(const absl::Cord &lhs, 103 absl::string_view rhs) const { 104 return compare_internal::compare_result_as_ordering(lhs.Compare(rhs)); 105 } operatorStringBtreeDefaultLess106 absl::weak_ordering operator()(absl::string_view lhs, 107 const absl::Cord &rhs) const { 108 return compare_internal::compare_result_as_ordering(-rhs.Compare(lhs)); 109 } 110 }; 111 112 struct StringBtreeDefaultGreater { 113 using is_transparent = void; 114 115 StringBtreeDefaultGreater() = default; 116 StringBtreeDefaultGreaterStringBtreeDefaultGreater117 StringBtreeDefaultGreater(std::greater<std::string>) {} // NOLINT StringBtreeDefaultGreaterStringBtreeDefaultGreater118 StringBtreeDefaultGreater(std::greater<string_view>) {} // NOLINT 119 operatorStringBtreeDefaultGreater120 absl::weak_ordering operator()(absl::string_view lhs, 121 absl::string_view rhs) const { 122 return compare_internal::compare_result_as_ordering(rhs.compare(lhs)); 123 } StringBtreeDefaultGreaterStringBtreeDefaultGreater124 StringBtreeDefaultGreater(std::greater<absl::Cord>) {} // NOLINT operatorStringBtreeDefaultGreater125 absl::weak_ordering operator()(const absl::Cord &lhs, 126 const absl::Cord &rhs) const { 127 return compare_internal::compare_result_as_ordering(rhs.Compare(lhs)); 128 } operatorStringBtreeDefaultGreater129 absl::weak_ordering operator()(const absl::Cord &lhs, 130 absl::string_view rhs) const { 131 return compare_internal::compare_result_as_ordering(-lhs.Compare(rhs)); 132 } operatorStringBtreeDefaultGreater133 absl::weak_ordering operator()(absl::string_view lhs, 134 const absl::Cord &rhs) const { 135 return compare_internal::compare_result_as_ordering(rhs.Compare(lhs)); 136 } 137 }; 138 139 // A helper class to convert a boolean comparison into a three-way "compare-to" 140 // comparison that returns an `absl::weak_ordering`. This helper 141 // class is specialized for less<std::string>, greater<std::string>, 142 // less<string_view>, greater<string_view>, less<absl::Cord>, and 143 // greater<absl::Cord>. 144 // 145 // key_compare_to_adapter is provided so that btree users 146 // automatically get the more efficient compare-to code when using common 147 // Abseil string types with common comparison functors. 148 // These string-like specializations also turn on heterogeneous lookup by 149 // default. 150 template <typename Compare> 151 struct key_compare_to_adapter { 152 using type = Compare; 153 }; 154 155 template <> 156 struct key_compare_to_adapter<std::less<std::string>> { 157 using type = StringBtreeDefaultLess; 158 }; 159 160 template <> 161 struct key_compare_to_adapter<std::greater<std::string>> { 162 using type = StringBtreeDefaultGreater; 163 }; 164 165 template <> 166 struct key_compare_to_adapter<std::less<absl::string_view>> { 167 using type = StringBtreeDefaultLess; 168 }; 169 170 template <> 171 struct key_compare_to_adapter<std::greater<absl::string_view>> { 172 using type = StringBtreeDefaultGreater; 173 }; 174 175 template <> 176 struct key_compare_to_adapter<std::less<absl::Cord>> { 177 using type = StringBtreeDefaultLess; 178 }; 179 180 template <> 181 struct key_compare_to_adapter<std::greater<absl::Cord>> { 182 using type = StringBtreeDefaultGreater; 183 }; 184 185 // Detects an 'absl_btree_prefer_linear_node_search' member. This is 186 // a protocol used as an opt-in or opt-out of linear search. 187 // 188 // For example, this would be useful for key types that wrap an integer 189 // and define their own cheap operator<(). For example: 190 // 191 // class K { 192 // public: 193 // using absl_btree_prefer_linear_node_search = std::true_type; 194 // ... 195 // private: 196 // friend bool operator<(K a, K b) { return a.k_ < b.k_; } 197 // int k_; 198 // }; 199 // 200 // btree_map<K, V> m; // Uses linear search 201 // 202 // If T has the preference tag, then it has a preference. 203 // Btree will use the tag's truth value. 204 template <typename T, typename = void> 205 struct has_linear_node_search_preference : std::false_type {}; 206 template <typename T, typename = void> 207 struct prefers_linear_node_search : std::false_type {}; 208 template <typename T> 209 struct has_linear_node_search_preference< 210 T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>> 211 : std::true_type {}; 212 template <typename T> 213 struct prefers_linear_node_search< 214 T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>> 215 : T::absl_btree_prefer_linear_node_search {}; 216 217 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize, 218 bool Multi, typename SlotPolicy> 219 struct common_params { 220 // If Compare is a common comparator for a string-like type, then we adapt it 221 // to use heterogeneous lookup and to be a key-compare-to comparator. 222 using key_compare = typename key_compare_to_adapter<Compare>::type; 223 // True when key_compare has been adapted to StringBtreeDefault{Less,Greater}. 224 using is_key_compare_adapted = 225 absl::negation<std::is_same<key_compare, Compare>>; 226 // A type which indicates if we have a key-compare-to functor or a plain old 227 // key-compare functor. 228 using is_key_compare_to = btree_is_key_compare_to<key_compare, Key>; 229 230 using allocator_type = Alloc; 231 using key_type = Key; 232 using size_type = std::make_signed<size_t>::type; 233 using difference_type = ptrdiff_t; 234 235 // True if this is a multiset or multimap. 236 using is_multi_container = std::integral_constant<bool, Multi>; 237 238 using slot_policy = SlotPolicy; 239 using slot_type = typename slot_policy::slot_type; 240 using value_type = typename slot_policy::value_type; 241 using init_type = typename slot_policy::mutable_value_type; 242 using pointer = value_type *; 243 using const_pointer = const value_type *; 244 using reference = value_type &; 245 using const_reference = const value_type &; 246 247 enum { 248 kTargetNodeSize = TargetNodeSize, 249 250 // Upper bound for the available space for values. This is largest for leaf 251 // nodes, which have overhead of at least a pointer + 4 bytes (for storing 252 // 3 field_types and an enum). 253 kNodeValueSpace = 254 TargetNodeSize - /*minimum overhead=*/(sizeof(void *) + 4), 255 }; 256 257 // This is an integral type large enough to hold as many 258 // ValueSize-values as will fit a node of TargetNodeSize bytes. 259 using node_count_type = 260 absl::conditional_t<(kNodeValueSpace / sizeof(value_type) > 261 (std::numeric_limits<uint8_t>::max)()), 262 uint16_t, uint8_t>; // NOLINT 263 264 // The following methods are necessary for passing this struct as PolicyTraits 265 // for node_handle and/or are used within btree. 266 static value_type &element(slot_type *slot) { 267 return slot_policy::element(slot); 268 } 269 static const value_type &element(const slot_type *slot) { 270 return slot_policy::element(slot); 271 } 272 template <class... Args> 273 static void construct(Alloc *alloc, slot_type *slot, Args &&... args) { 274 slot_policy::construct(alloc, slot, std::forward<Args>(args)...); 275 } 276 static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { 277 slot_policy::construct(alloc, slot, other); 278 } 279 static void destroy(Alloc *alloc, slot_type *slot) { 280 slot_policy::destroy(alloc, slot); 281 } 282 static void transfer(Alloc *alloc, slot_type *new_slot, slot_type *old_slot) { 283 construct(alloc, new_slot, old_slot); 284 destroy(alloc, old_slot); 285 } 286 static void swap(Alloc *alloc, slot_type *a, slot_type *b) { 287 slot_policy::swap(alloc, a, b); 288 } 289 static void move(Alloc *alloc, slot_type *src, slot_type *dest) { 290 slot_policy::move(alloc, src, dest); 291 } 292 }; 293 294 // A parameters structure for holding the type parameters for a btree_map. 295 // Compare and Alloc should be nothrow copy-constructible. 296 template <typename Key, typename Data, typename Compare, typename Alloc, 297 int TargetNodeSize, bool Multi> 298 struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi, 299 map_slot_policy<Key, Data>> { 300 using super_type = typename map_params::common_params; 301 using mapped_type = Data; 302 // This type allows us to move keys when it is safe to do so. It is safe 303 // for maps in which value_type and mutable_value_type are layout compatible. 304 using slot_policy = typename super_type::slot_policy; 305 using slot_type = typename super_type::slot_type; 306 using value_type = typename super_type::value_type; 307 using init_type = typename super_type::init_type; 308 309 using key_compare = typename super_type::key_compare; 310 // Inherit from key_compare for empty base class optimization. 311 struct value_compare : private key_compare { 312 value_compare() = default; 313 explicit value_compare(const key_compare &cmp) : key_compare(cmp) {} 314 315 template <typename T, typename U> 316 auto operator()(const T &left, const U &right) const 317 -> decltype(std::declval<key_compare>()(left.first, right.first)) { 318 return key_compare::operator()(left.first, right.first); 319 } 320 }; 321 using is_map_container = std::true_type; 322 323 template <typename V> 324 static auto key(const V &value) -> decltype(value.first) { 325 return value.first; 326 } 327 static const Key &key(const slot_type *s) { return slot_policy::key(s); } 328 static const Key &key(slot_type *s) { return slot_policy::key(s); } 329 // For use in node handle. 330 static auto mutable_key(slot_type *s) 331 -> decltype(slot_policy::mutable_key(s)) { 332 return slot_policy::mutable_key(s); 333 } 334 static mapped_type &value(value_type *value) { return value->second; } 335 }; 336 337 // This type implements the necessary functions from the 338 // absl::container_internal::slot_type interface. 339 template <typename Key> 340 struct set_slot_policy { 341 using slot_type = Key; 342 using value_type = Key; 343 using mutable_value_type = Key; 344 345 static value_type &element(slot_type *slot) { return *slot; } 346 static const value_type &element(const slot_type *slot) { return *slot; } 347 348 template <typename Alloc, class... Args> 349 static void construct(Alloc *alloc, slot_type *slot, Args &&... args) { 350 absl::allocator_traits<Alloc>::construct(*alloc, slot, 351 std::forward<Args>(args)...); 352 } 353 354 template <typename Alloc> 355 static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { 356 absl::allocator_traits<Alloc>::construct(*alloc, slot, std::move(*other)); 357 } 358 359 template <typename Alloc> 360 static void destroy(Alloc *alloc, slot_type *slot) { 361 absl::allocator_traits<Alloc>::destroy(*alloc, slot); 362 } 363 364 template <typename Alloc> 365 static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) { 366 using std::swap; 367 swap(*a, *b); 368 } 369 370 template <typename Alloc> 371 static void move(Alloc * /*alloc*/, slot_type *src, slot_type *dest) { 372 *dest = std::move(*src); 373 } 374 }; 375 376 // A parameters structure for holding the type parameters for a btree_set. 377 // Compare and Alloc should be nothrow copy-constructible. 378 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize, 379 bool Multi> 380 struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi, 381 set_slot_policy<Key>> { 382 using value_type = Key; 383 using slot_type = typename set_params::common_params::slot_type; 384 using value_compare = typename set_params::common_params::key_compare; 385 using is_map_container = std::false_type; 386 387 template <typename V> 388 static const V &key(const V &value) { return value; } 389 static const Key &key(const slot_type *slot) { return *slot; } 390 static const Key &key(slot_type *slot) { return *slot; } 391 }; 392 393 // An adapter class that converts a lower-bound compare into an upper-bound 394 // compare. Note: there is no need to make a version of this adapter specialized 395 // for key-compare-to functors because the upper-bound (the first value greater 396 // than the input) is never an exact match. 397 template <typename Compare> 398 struct upper_bound_adapter { 399 explicit upper_bound_adapter(const Compare &c) : comp(c) {} 400 template <typename K1, typename K2> 401 bool operator()(const K1 &a, const K2 &b) const { 402 // Returns true when a is not greater than b. 403 return !compare_internal::compare_result_as_less_than(comp(b, a)); 404 } 405 406 private: 407 Compare comp; 408 }; 409 410 enum class MatchKind : uint8_t { kEq, kNe }; 411 412 template <typename V, bool IsCompareTo> 413 struct SearchResult { 414 V value; 415 MatchKind match; 416 417 static constexpr bool HasMatch() { return true; } 418 bool IsEq() const { return match == MatchKind::kEq; } 419 }; 420 421 // When we don't use CompareTo, `match` is not present. 422 // This ensures that callers can't use it accidentally when it provides no 423 // useful information. 424 template <typename V> 425 struct SearchResult<V, false> { 426 SearchResult() {} 427 explicit SearchResult(V value) : value(value) {} 428 SearchResult(V value, MatchKind /*match*/) : value(value) {} 429 430 V value; 431 432 static constexpr bool HasMatch() { return false; } 433 static constexpr bool IsEq() { return false; } 434 }; 435 436 // A node in the btree holding. The same node type is used for both internal 437 // and leaf nodes in the btree, though the nodes are allocated in such a way 438 // that the children array is only valid in internal nodes. 439 template <typename Params> 440 class btree_node { 441 using is_key_compare_to = typename Params::is_key_compare_to; 442 using is_multi_container = typename Params::is_multi_container; 443 using field_type = typename Params::node_count_type; 444 using allocator_type = typename Params::allocator_type; 445 using slot_type = typename Params::slot_type; 446 447 public: 448 using params_type = Params; 449 using key_type = typename Params::key_type; 450 using value_type = typename Params::value_type; 451 using pointer = typename Params::pointer; 452 using const_pointer = typename Params::const_pointer; 453 using reference = typename Params::reference; 454 using const_reference = typename Params::const_reference; 455 using key_compare = typename Params::key_compare; 456 using size_type = typename Params::size_type; 457 using difference_type = typename Params::difference_type; 458 459 // Btree decides whether to use linear node search as follows: 460 // - If the comparator expresses a preference, use that. 461 // - If the key expresses a preference, use that. 462 // - If the key is arithmetic and the comparator is std::less or 463 // std::greater, choose linear. 464 // - Otherwise, choose binary. 465 // TODO(ezb): Might make sense to add condition(s) based on node-size. 466 using use_linear_search = std::integral_constant< 467 bool, 468 has_linear_node_search_preference<key_compare>::value 469 ? prefers_linear_node_search<key_compare>::value 470 : has_linear_node_search_preference<key_type>::value 471 ? prefers_linear_node_search<key_type>::value 472 : std::is_arithmetic<key_type>::value && 473 (std::is_same<std::less<key_type>, key_compare>::value || 474 std::is_same<std::greater<key_type>, 475 key_compare>::value)>; 476 477 // This class is organized by gtl::Layout as if it had the following 478 // structure: 479 // // A pointer to the node's parent. 480 // btree_node *parent; 481 // 482 // // The position of the node in the node's parent. 483 // field_type position; 484 // // The index of the first populated value in `values`. 485 // // TODO(ezb): right now, `start` is always 0. Update insertion/merge 486 // // logic to allow for floating storage within nodes. 487 // field_type start; 488 // // The index after the last populated value in `values`. Currently, this 489 // // is the same as the count of values. 490 // field_type finish; 491 // // The maximum number of values the node can hold. This is an integer in 492 // // [1, kNodeValues] for root leaf nodes, kNodeValues for non-root leaf 493 // // nodes, and kInternalNodeMaxCount (as a sentinel value) for internal 494 // // nodes (even though there are still kNodeValues values in the node). 495 // // TODO(ezb): make max_count use only 4 bits and record log2(capacity) 496 // // to free extra bits for is_root, etc. 497 // field_type max_count; 498 // 499 // // The array of values. The capacity is `max_count` for leaf nodes and 500 // // kNodeValues for internal nodes. Only the values in 501 // // [start, finish) have been initialized and are valid. 502 // slot_type values[max_count]; 503 // 504 // // The array of child pointers. The keys in children[i] are all less 505 // // than key(i). The keys in children[i + 1] are all greater than key(i). 506 // // There are 0 children for leaf nodes and kNodeValues + 1 children for 507 // // internal nodes. 508 // btree_node *children[kNodeValues + 1]; 509 // 510 // This class is only constructed by EmptyNodeType. Normally, pointers to the 511 // layout above are allocated, cast to btree_node*, and de-allocated within 512 // the btree implementation. 513 ~btree_node() = default; 514 btree_node(btree_node const &) = delete; 515 btree_node &operator=(btree_node const &) = delete; 516 517 // Public for EmptyNodeType. 518 constexpr static size_type Alignment() { 519 static_assert(LeafLayout(1).Alignment() == InternalLayout().Alignment(), 520 "Alignment of all nodes must be equal."); 521 return InternalLayout().Alignment(); 522 } 523 524 protected: 525 btree_node() = default; 526 527 private: 528 using layout_type = absl::container_internal::Layout<btree_node *, field_type, 529 slot_type, btree_node *>; 530 constexpr static size_type SizeWithNValues(size_type n) { 531 return layout_type(/*parent*/ 1, 532 /*position, start, finish, max_count*/ 4, 533 /*values*/ n, 534 /*children*/ 0) 535 .AllocSize(); 536 } 537 // A lower bound for the overhead of fields other than values in a leaf node. 538 constexpr static size_type MinimumOverhead() { 539 return SizeWithNValues(1) - sizeof(value_type); 540 } 541 542 // Compute how many values we can fit onto a leaf node taking into account 543 // padding. 544 constexpr static size_type NodeTargetValues(const int begin, const int end) { 545 return begin == end ? begin 546 : SizeWithNValues((begin + end) / 2 + 1) > 547 params_type::kTargetNodeSize 548 ? NodeTargetValues(begin, (begin + end) / 2) 549 : NodeTargetValues((begin + end) / 2 + 1, end); 550 } 551 552 enum { 553 kTargetNodeSize = params_type::kTargetNodeSize, 554 kNodeTargetValues = NodeTargetValues(0, params_type::kTargetNodeSize), 555 556 // We need a minimum of 3 values per internal node in order to perform 557 // splitting (1 value for the two nodes involved in the split and 1 value 558 // propagated to the parent as the delimiter for the split). 559 kNodeValues = kNodeTargetValues >= 3 ? kNodeTargetValues : 3, 560 561 // The node is internal (i.e. is not a leaf node) if and only if `max_count` 562 // has this value. 563 kInternalNodeMaxCount = 0, 564 }; 565 566 // Leaves can have less than kNodeValues values. 567 constexpr static layout_type LeafLayout(const int max_values = kNodeValues) { 568 return layout_type(/*parent*/ 1, 569 /*position, start, finish, max_count*/ 4, 570 /*values*/ max_values, 571 /*children*/ 0); 572 } 573 constexpr static layout_type InternalLayout() { 574 return layout_type(/*parent*/ 1, 575 /*position, start, finish, max_count*/ 4, 576 /*values*/ kNodeValues, 577 /*children*/ kNodeValues + 1); 578 } 579 constexpr static size_type LeafSize(const int max_values = kNodeValues) { 580 return LeafLayout(max_values).AllocSize(); 581 } 582 constexpr static size_type InternalSize() { 583 return InternalLayout().AllocSize(); 584 } 585 586 // N is the index of the type in the Layout definition. 587 // ElementType<N> is the Nth type in the Layout definition. 588 template <size_type N> 589 inline typename layout_type::template ElementType<N> *GetField() { 590 // We assert that we don't read from values that aren't there. 591 assert(N < 3 || !leaf()); 592 return InternalLayout().template Pointer<N>(reinterpret_cast<char *>(this)); 593 } 594 template <size_type N> 595 inline const typename layout_type::template ElementType<N> *GetField() const { 596 assert(N < 3 || !leaf()); 597 return InternalLayout().template Pointer<N>( 598 reinterpret_cast<const char *>(this)); 599 } 600 void set_parent(btree_node *p) { *GetField<0>() = p; } 601 field_type &mutable_finish() { return GetField<1>()[2]; } 602 slot_type *slot(int i) { return &GetField<2>()[i]; } 603 slot_type *start_slot() { return slot(start()); } 604 slot_type *finish_slot() { return slot(finish()); } 605 const slot_type *slot(int i) const { return &GetField<2>()[i]; } 606 void set_position(field_type v) { GetField<1>()[0] = v; } 607 void set_start(field_type v) { GetField<1>()[1] = v; } 608 void set_finish(field_type v) { GetField<1>()[2] = v; } 609 // This method is only called by the node init methods. 610 void set_max_count(field_type v) { GetField<1>()[3] = v; } 611 612 public: 613 // Whether this is a leaf node or not. This value doesn't change after the 614 // node is created. 615 bool leaf() const { return GetField<1>()[3] != kInternalNodeMaxCount; } 616 617 // Getter for the position of this node in its parent. 618 field_type position() const { return GetField<1>()[0]; } 619 620 // Getter for the offset of the first value in the `values` array. 621 field_type start() const { 622 // TODO(ezb): when floating storage is implemented, return GetField<1>()[1]; 623 assert(GetField<1>()[1] == 0); 624 return 0; 625 } 626 627 // Getter for the offset after the last value in the `values` array. 628 field_type finish() const { return GetField<1>()[2]; } 629 630 // Getters for the number of values stored in this node. 631 field_type count() const { 632 assert(finish() >= start()); 633 return finish() - start(); 634 } 635 field_type max_count() const { 636 // Internal nodes have max_count==kInternalNodeMaxCount. 637 // Leaf nodes have max_count in [1, kNodeValues]. 638 const field_type max_count = GetField<1>()[3]; 639 return max_count == field_type{kInternalNodeMaxCount} 640 ? field_type{kNodeValues} 641 : max_count; 642 } 643 644 // Getter for the parent of this node. 645 btree_node *parent() const { return *GetField<0>(); } 646 // Getter for whether the node is the root of the tree. The parent of the 647 // root of the tree is the leftmost node in the tree which is guaranteed to 648 // be a leaf. 649 bool is_root() const { return parent()->leaf(); } 650 void make_root() { 651 assert(parent()->is_root()); 652 set_parent(parent()->parent()); 653 } 654 655 // Getters for the key/value at position i in the node. 656 const key_type &key(int i) const { return params_type::key(slot(i)); } 657 reference value(int i) { return params_type::element(slot(i)); } 658 const_reference value(int i) const { return params_type::element(slot(i)); } 659 660 // Getters/setter for the child at position i in the node. 661 btree_node *child(int i) const { return GetField<3>()[i]; } 662 btree_node *start_child() const { return child(start()); } 663 btree_node *&mutable_child(int i) { return GetField<3>()[i]; } 664 void clear_child(int i) { 665 absl::container_internal::SanitizerPoisonObject(&mutable_child(i)); 666 } 667 void set_child(int i, btree_node *c) { 668 absl::container_internal::SanitizerUnpoisonObject(&mutable_child(i)); 669 mutable_child(i) = c; 670 c->set_position(i); 671 } 672 void init_child(int i, btree_node *c) { 673 set_child(i, c); 674 c->set_parent(this); 675 } 676 677 // Returns the position of the first value whose key is not less than k. 678 template <typename K> 679 SearchResult<int, is_key_compare_to::value> lower_bound( 680 const K &k, const key_compare &comp) const { 681 return use_linear_search::value ? linear_search(k, comp) 682 : binary_search(k, comp); 683 } 684 // Returns the position of the first value whose key is greater than k. 685 template <typename K> 686 int upper_bound(const K &k, const key_compare &comp) const { 687 auto upper_compare = upper_bound_adapter<key_compare>(comp); 688 return use_linear_search::value ? linear_search(k, upper_compare).value 689 : binary_search(k, upper_compare).value; 690 } 691 692 template <typename K, typename Compare> 693 SearchResult<int, btree_is_key_compare_to<Compare, key_type>::value> 694 linear_search(const K &k, const Compare &comp) const { 695 return linear_search_impl(k, start(), finish(), comp, 696 btree_is_key_compare_to<Compare, key_type>()); 697 } 698 699 template <typename K, typename Compare> 700 SearchResult<int, btree_is_key_compare_to<Compare, key_type>::value> 701 binary_search(const K &k, const Compare &comp) const { 702 return binary_search_impl(k, start(), finish(), comp, 703 btree_is_key_compare_to<Compare, key_type>()); 704 } 705 706 // Returns the position of the first value whose key is not less than k using 707 // linear search performed using plain compare. 708 template <typename K, typename Compare> 709 SearchResult<int, false> linear_search_impl( 710 const K &k, int s, const int e, const Compare &comp, 711 std::false_type /* IsCompareTo */) const { 712 while (s < e) { 713 if (!comp(key(s), k)) { 714 break; 715 } 716 ++s; 717 } 718 return SearchResult<int, false>{s}; 719 } 720 721 // Returns the position of the first value whose key is not less than k using 722 // linear search performed using compare-to. 723 template <typename K, typename Compare> 724 SearchResult<int, true> linear_search_impl( 725 const K &k, int s, const int e, const Compare &comp, 726 std::true_type /* IsCompareTo */) const { 727 while (s < e) { 728 const absl::weak_ordering c = comp(key(s), k); 729 if (c == 0) { 730 return {s, MatchKind::kEq}; 731 } else if (c > 0) { 732 break; 733 } 734 ++s; 735 } 736 return {s, MatchKind::kNe}; 737 } 738 739 // Returns the position of the first value whose key is not less than k using 740 // binary search performed using plain compare. 741 template <typename K, typename Compare> 742 SearchResult<int, false> binary_search_impl( 743 const K &k, int s, int e, const Compare &comp, 744 std::false_type /* IsCompareTo */) const { 745 while (s != e) { 746 const int mid = (s + e) >> 1; 747 if (comp(key(mid), k)) { 748 s = mid + 1; 749 } else { 750 e = mid; 751 } 752 } 753 return SearchResult<int, false>{s}; 754 } 755 756 // Returns the position of the first value whose key is not less than k using 757 // binary search performed using compare-to. 758 template <typename K, typename CompareTo> 759 SearchResult<int, true> binary_search_impl( 760 const K &k, int s, int e, const CompareTo &comp, 761 std::true_type /* IsCompareTo */) const { 762 if (is_multi_container::value) { 763 MatchKind exact_match = MatchKind::kNe; 764 while (s != e) { 765 const int mid = (s + e) >> 1; 766 const absl::weak_ordering c = comp(key(mid), k); 767 if (c < 0) { 768 s = mid + 1; 769 } else { 770 e = mid; 771 if (c == 0) { 772 // Need to return the first value whose key is not less than k, 773 // which requires continuing the binary search if this is a 774 // multi-container. 775 exact_match = MatchKind::kEq; 776 } 777 } 778 } 779 return {s, exact_match}; 780 } else { // Not a multi-container. 781 while (s != e) { 782 const int mid = (s + e) >> 1; 783 const absl::weak_ordering c = comp(key(mid), k); 784 if (c < 0) { 785 s = mid + 1; 786 } else if (c > 0) { 787 e = mid; 788 } else { 789 return {mid, MatchKind::kEq}; 790 } 791 } 792 return {s, MatchKind::kNe}; 793 } 794 } 795 796 // Emplaces a value at position i, shifting all existing values and 797 // children at positions >= i to the right by 1. 798 template <typename... Args> 799 void emplace_value(size_type i, allocator_type *alloc, Args &&... args); 800 801 // Removes the values at positions [i, i + to_erase), shifting all existing 802 // values and children after that range to the left by to_erase. Clears all 803 // children between [i, i + to_erase). 804 void remove_values(field_type i, field_type to_erase, allocator_type *alloc); 805 806 // Rebalances a node with its right sibling. 807 void rebalance_right_to_left(int to_move, btree_node *right, 808 allocator_type *alloc); 809 void rebalance_left_to_right(int to_move, btree_node *right, 810 allocator_type *alloc); 811 812 // Splits a node, moving a portion of the node's values to its right sibling. 813 void split(int insert_position, btree_node *dest, allocator_type *alloc); 814 815 // Merges a node with its right sibling, moving all of the values and the 816 // delimiting key in the parent node onto itself, and deleting the src node. 817 void merge(btree_node *src, allocator_type *alloc); 818 819 // Node allocation/deletion routines. 820 void init_leaf(btree_node *parent, int max_count) { 821 set_parent(parent); 822 set_position(0); 823 set_start(0); 824 set_finish(0); 825 set_max_count(max_count); 826 absl::container_internal::SanitizerPoisonMemoryRegion( 827 start_slot(), max_count * sizeof(slot_type)); 828 } 829 void init_internal(btree_node *parent) { 830 init_leaf(parent, kNodeValues); 831 // Set `max_count` to a sentinel value to indicate that this node is 832 // internal. 833 set_max_count(kInternalNodeMaxCount); 834 absl::container_internal::SanitizerPoisonMemoryRegion( 835 &mutable_child(start()), (kNodeValues + 1) * sizeof(btree_node *)); 836 } 837 838 static void deallocate(const size_type size, btree_node *node, 839 allocator_type *alloc) { 840 absl::container_internal::Deallocate<Alignment()>(alloc, node, size); 841 } 842 843 // Deletes a node and all of its children. 844 static void clear_and_delete(btree_node *node, allocator_type *alloc); 845 846 private: 847 template <typename... Args> 848 void value_init(const field_type i, allocator_type *alloc, Args &&... args) { 849 absl::container_internal::SanitizerUnpoisonObject(slot(i)); 850 params_type::construct(alloc, slot(i), std::forward<Args>(args)...); 851 } 852 void value_destroy(const field_type i, allocator_type *alloc) { 853 params_type::destroy(alloc, slot(i)); 854 absl::container_internal::SanitizerPoisonObject(slot(i)); 855 } 856 void value_destroy_n(const field_type i, const field_type n, 857 allocator_type *alloc) { 858 for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) { 859 params_type::destroy(alloc, s); 860 absl::container_internal::SanitizerPoisonObject(s); 861 } 862 } 863 864 static void transfer(slot_type *dest, slot_type *src, allocator_type *alloc) { 865 absl::container_internal::SanitizerUnpoisonObject(dest); 866 params_type::transfer(alloc, dest, src); 867 absl::container_internal::SanitizerPoisonObject(src); 868 } 869 870 // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`. 871 void transfer(const size_type dest_i, const size_type src_i, 872 btree_node *src_node, allocator_type *alloc) { 873 transfer(slot(dest_i), src_node->slot(src_i), alloc); 874 } 875 876 // Transfers `n` values starting at value `src_i` in `src_node` into the 877 // values starting at value `dest_i` in `this`. 878 void transfer_n(const size_type n, const size_type dest_i, 879 const size_type src_i, btree_node *src_node, 880 allocator_type *alloc) { 881 for (slot_type *src = src_node->slot(src_i), *end = src + n, 882 *dest = slot(dest_i); 883 src != end; ++src, ++dest) { 884 transfer(dest, src, alloc); 885 } 886 } 887 888 // Same as above, except that we start at the end and work our way to the 889 // beginning. 890 void transfer_n_backward(const size_type n, const size_type dest_i, 891 const size_type src_i, btree_node *src_node, 892 allocator_type *alloc) { 893 for (slot_type *src = src_node->slot(src_i + n - 1), *end = src - n, 894 *dest = slot(dest_i + n - 1); 895 src != end; --src, --dest) { 896 transfer(dest, src, alloc); 897 } 898 } 899 900 template <typename P> 901 friend class btree; 902 template <typename N, typename R, typename P> 903 friend struct btree_iterator; 904 friend class BtreeNodePeer; 905 }; 906 907 template <typename Node, typename Reference, typename Pointer> 908 struct btree_iterator { 909 private: 910 using key_type = typename Node::key_type; 911 using size_type = typename Node::size_type; 912 using params_type = typename Node::params_type; 913 914 using node_type = Node; 915 using normal_node = typename std::remove_const<Node>::type; 916 using const_node = const Node; 917 using normal_pointer = typename params_type::pointer; 918 using normal_reference = typename params_type::reference; 919 using const_pointer = typename params_type::const_pointer; 920 using const_reference = typename params_type::const_reference; 921 using slot_type = typename params_type::slot_type; 922 923 using iterator = 924 btree_iterator<normal_node, normal_reference, normal_pointer>; 925 using const_iterator = 926 btree_iterator<const_node, const_reference, const_pointer>; 927 928 public: 929 // These aliases are public for std::iterator_traits. 930 using difference_type = typename Node::difference_type; 931 using value_type = typename params_type::value_type; 932 using pointer = Pointer; 933 using reference = Reference; 934 using iterator_category = std::bidirectional_iterator_tag; 935 936 btree_iterator() : node(nullptr), position(-1) {} 937 explicit btree_iterator(Node *n) : node(n), position(n->start()) {} 938 btree_iterator(Node *n, int p) : node(n), position(p) {} 939 940 // NOTE: this SFINAE allows for implicit conversions from iterator to 941 // const_iterator, but it specifically avoids defining copy constructors so 942 // that btree_iterator can be trivially copyable. This is for performance and 943 // binary size reasons. 944 template <typename N, typename R, typename P, 945 absl::enable_if_t< 946 std::is_same<btree_iterator<N, R, P>, iterator>::value && 947 std::is_same<btree_iterator, const_iterator>::value, 948 int> = 0> 949 btree_iterator(const btree_iterator<N, R, P> &other) // NOLINT 950 : node(other.node), position(other.position) {} 951 952 private: 953 // This SFINAE allows explicit conversions from const_iterator to 954 // iterator, but also avoids defining a copy constructor. 955 // NOTE: the const_cast is safe because this constructor is only called by 956 // non-const methods and the container owns the nodes. 957 template <typename N, typename R, typename P, 958 absl::enable_if_t< 959 std::is_same<btree_iterator<N, R, P>, const_iterator>::value && 960 std::is_same<btree_iterator, iterator>::value, 961 int> = 0> 962 explicit btree_iterator(const btree_iterator<N, R, P> &other) 963 : node(const_cast<node_type *>(other.node)), position(other.position) {} 964 965 // Increment/decrement the iterator. 966 void increment() { 967 if (node->leaf() && ++position < node->finish()) { 968 return; 969 } 970 increment_slow(); 971 } 972 void increment_slow(); 973 974 void decrement() { 975 if (node->leaf() && --position >= node->start()) { 976 return; 977 } 978 decrement_slow(); 979 } 980 void decrement_slow(); 981 982 public: 983 bool operator==(const iterator &other) const { 984 return node == other.node && position == other.position; 985 } 986 bool operator==(const const_iterator &other) const { 987 return node == other.node && position == other.position; 988 } 989 bool operator!=(const iterator &other) const { 990 return node != other.node || position != other.position; 991 } 992 bool operator!=(const const_iterator &other) const { 993 return node != other.node || position != other.position; 994 } 995 996 // Accessors for the key/value the iterator is pointing at. 997 reference operator*() const { 998 ABSL_HARDENING_ASSERT(node != nullptr); 999 ABSL_HARDENING_ASSERT(node->start() <= position); 1000 ABSL_HARDENING_ASSERT(node->finish() > position); 1001 return node->value(position); 1002 } 1003 pointer operator->() const { return &operator*(); } 1004 1005 btree_iterator &operator++() { 1006 increment(); 1007 return *this; 1008 } 1009 btree_iterator &operator--() { 1010 decrement(); 1011 return *this; 1012 } 1013 btree_iterator operator++(int) { 1014 btree_iterator tmp = *this; 1015 ++*this; 1016 return tmp; 1017 } 1018 btree_iterator operator--(int) { 1019 btree_iterator tmp = *this; 1020 --*this; 1021 return tmp; 1022 } 1023 1024 private: 1025 template <typename Params> 1026 friend class btree; 1027 template <typename Tree> 1028 friend class btree_container; 1029 template <typename Tree> 1030 friend class btree_set_container; 1031 template <typename Tree> 1032 friend class btree_map_container; 1033 template <typename Tree> 1034 friend class btree_multiset_container; 1035 template <typename N, typename R, typename P> 1036 friend struct btree_iterator; 1037 template <typename TreeType, typename CheckerType> 1038 friend class base_checker; 1039 1040 const key_type &key() const { return node->key(position); } 1041 slot_type *slot() { return node->slot(position); } 1042 1043 // The node in the tree the iterator is pointing at. 1044 Node *node; 1045 // The position within the node of the tree the iterator is pointing at. 1046 // NOTE: this is an int rather than a field_type because iterators can point 1047 // to invalid positions (such as -1) in certain circumstances. 1048 int position; 1049 }; 1050 1051 template <typename Params> 1052 class btree { 1053 using node_type = btree_node<Params>; 1054 using is_key_compare_to = typename Params::is_key_compare_to; 1055 using init_type = typename Params::init_type; 1056 using field_type = typename node_type::field_type; 1057 using is_multi_container = typename Params::is_multi_container; 1058 using is_key_compare_adapted = typename Params::is_key_compare_adapted; 1059 1060 // We use a static empty node for the root/leftmost/rightmost of empty btrees 1061 // in order to avoid branching in begin()/end(). 1062 struct alignas(node_type::Alignment()) EmptyNodeType : node_type { 1063 using field_type = typename node_type::field_type; 1064 node_type *parent; 1065 field_type position = 0; 1066 field_type start = 0; 1067 field_type finish = 0; 1068 // max_count must be != kInternalNodeMaxCount (so that this node is regarded 1069 // as a leaf node). max_count() is never called when the tree is empty. 1070 field_type max_count = node_type::kInternalNodeMaxCount + 1; 1071 1072 #ifdef _MSC_VER 1073 // MSVC has constexpr code generations bugs here. 1074 EmptyNodeType() : parent(this) {} 1075 #else 1076 constexpr EmptyNodeType(node_type *p) : parent(p) {} 1077 #endif 1078 }; 1079 1080 static node_type *EmptyNode() { 1081 #ifdef _MSC_VER 1082 static EmptyNodeType *empty_node = new EmptyNodeType; 1083 // This assert fails on some other construction methods. 1084 assert(empty_node->parent == empty_node); 1085 return empty_node; 1086 #else 1087 static constexpr EmptyNodeType empty_node( 1088 const_cast<EmptyNodeType *>(&empty_node)); 1089 return const_cast<EmptyNodeType *>(&empty_node); 1090 #endif 1091 } 1092 1093 enum : uint32_t { 1094 kNodeValues = node_type::kNodeValues, 1095 kMinNodeValues = kNodeValues / 2, 1096 }; 1097 1098 struct node_stats { 1099 using size_type = typename Params::size_type; 1100 1101 node_stats(size_type l, size_type i) : leaf_nodes(l), internal_nodes(i) {} 1102 1103 node_stats &operator+=(const node_stats &other) { 1104 leaf_nodes += other.leaf_nodes; 1105 internal_nodes += other.internal_nodes; 1106 return *this; 1107 } 1108 1109 size_type leaf_nodes; 1110 size_type internal_nodes; 1111 }; 1112 1113 public: 1114 using key_type = typename Params::key_type; 1115 using value_type = typename Params::value_type; 1116 using size_type = typename Params::size_type; 1117 using difference_type = typename Params::difference_type; 1118 using key_compare = typename Params::key_compare; 1119 using value_compare = typename Params::value_compare; 1120 using allocator_type = typename Params::allocator_type; 1121 using reference = typename Params::reference; 1122 using const_reference = typename Params::const_reference; 1123 using pointer = typename Params::pointer; 1124 using const_pointer = typename Params::const_pointer; 1125 using iterator = btree_iterator<node_type, reference, pointer>; 1126 using const_iterator = typename iterator::const_iterator; 1127 using reverse_iterator = std::reverse_iterator<iterator>; 1128 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 1129 using node_handle_type = node_handle<Params, Params, allocator_type>; 1130 1131 // Internal types made public for use by btree_container types. 1132 using params_type = Params; 1133 using slot_type = typename Params::slot_type; 1134 1135 private: 1136 // For use in copy_or_move_values_in_order. 1137 const value_type &maybe_move_from_iterator(const_iterator it) { return *it; } 1138 value_type &&maybe_move_from_iterator(iterator it) { return std::move(*it); } 1139 1140 // Copies or moves (depending on the template parameter) the values in 1141 // other into this btree in their order in other. This btree must be empty 1142 // before this method is called. This method is used in copy construction, 1143 // copy assignment, and move assignment. 1144 template <typename Btree> 1145 void copy_or_move_values_in_order(Btree &other); 1146 1147 // Validates that various assumptions/requirements are true at compile time. 1148 constexpr static bool static_assert_validation(); 1149 1150 public: 1151 btree(const key_compare &comp, const allocator_type &alloc) 1152 : root_(comp, alloc, EmptyNode()), rightmost_(EmptyNode()), size_(0) {} 1153 1154 btree(const btree &other) : btree(other, other.allocator()) {} 1155 btree(const btree &other, const allocator_type &alloc) 1156 : btree(other.key_comp(), alloc) { 1157 copy_or_move_values_in_order(other); 1158 } 1159 btree(btree &&other) noexcept 1160 : root_(std::move(other.root_)), 1161 rightmost_(absl::exchange(other.rightmost_, EmptyNode())), 1162 size_(absl::exchange(other.size_, 0)) { 1163 other.mutable_root() = EmptyNode(); 1164 } 1165 btree(btree &&other, const allocator_type &alloc) 1166 : btree(other.key_comp(), alloc) { 1167 if (alloc == other.allocator()) { 1168 swap(other); 1169 } else { 1170 // Move values from `other` one at a time when allocators are different. 1171 copy_or_move_values_in_order(other); 1172 } 1173 } 1174 1175 ~btree() { 1176 // Put static_asserts in destructor to avoid triggering them before the type 1177 // is complete. 1178 static_assert(static_assert_validation(), "This call must be elided."); 1179 clear(); 1180 } 1181 1182 // Assign the contents of other to *this. 1183 btree &operator=(const btree &other); 1184 btree &operator=(btree &&other) noexcept; 1185 1186 iterator begin() { return iterator(leftmost()); } 1187 const_iterator begin() const { return const_iterator(leftmost()); } 1188 iterator end() { return iterator(rightmost_, rightmost_->finish()); } 1189 const_iterator end() const { 1190 return const_iterator(rightmost_, rightmost_->finish()); 1191 } 1192 reverse_iterator rbegin() { return reverse_iterator(end()); } 1193 const_reverse_iterator rbegin() const { 1194 return const_reverse_iterator(end()); 1195 } 1196 reverse_iterator rend() { return reverse_iterator(begin()); } 1197 const_reverse_iterator rend() const { 1198 return const_reverse_iterator(begin()); 1199 } 1200 1201 // Finds the first element whose key is not less than key. 1202 template <typename K> 1203 iterator lower_bound(const K &key) { 1204 return internal_end(internal_lower_bound(key).value); 1205 } 1206 template <typename K> 1207 const_iterator lower_bound(const K &key) const { 1208 return internal_end(internal_lower_bound(key).value); 1209 } 1210 1211 // Finds the first element whose key is greater than key. 1212 template <typename K> 1213 iterator upper_bound(const K &key) { 1214 return internal_end(internal_upper_bound(key)); 1215 } 1216 template <typename K> 1217 const_iterator upper_bound(const K &key) const { 1218 return internal_end(internal_upper_bound(key)); 1219 } 1220 1221 // Finds the range of values which compare equal to key. The first member of 1222 // the returned pair is equal to lower_bound(key). The second member of the 1223 // pair is equal to upper_bound(key). 1224 template <typename K> 1225 std::pair<iterator, iterator> equal_range(const K &key); 1226 template <typename K> 1227 std::pair<const_iterator, const_iterator> equal_range(const K &key) const { 1228 return const_cast<btree *>(this)->equal_range(key); 1229 } 1230 1231 // Inserts a value into the btree only if it does not already exist. The 1232 // boolean return value indicates whether insertion succeeded or failed. 1233 // Requirement: if `key` already exists in the btree, does not consume `args`. 1234 // Requirement: `key` is never referenced after consuming `args`. 1235 template <typename K, typename... Args> 1236 std::pair<iterator, bool> insert_unique(const K &key, Args &&... args); 1237 1238 // Inserts with hint. Checks to see if the value should be placed immediately 1239 // before `position` in the tree. If so, then the insertion will take 1240 // amortized constant time. If not, the insertion will take amortized 1241 // logarithmic time as if a call to insert_unique() were made. 1242 // Requirement: if `key` already exists in the btree, does not consume `args`. 1243 // Requirement: `key` is never referenced after consuming `args`. 1244 template <typename K, typename... Args> 1245 std::pair<iterator, bool> insert_hint_unique(iterator position, 1246 const K &key, 1247 Args &&... args); 1248 1249 // Insert a range of values into the btree. 1250 // Note: the first overload avoids constructing a value_type if the key 1251 // already exists in the btree. 1252 template <typename InputIterator, 1253 typename = decltype(std::declval<const key_compare &>()( 1254 params_type::key(*std::declval<InputIterator>()), 1255 std::declval<const key_type &>()))> 1256 void insert_iterator_unique(InputIterator b, InputIterator e, int); 1257 // We need the second overload for cases in which we need to construct a 1258 // value_type in order to compare it with the keys already in the btree. 1259 template <typename InputIterator> 1260 void insert_iterator_unique(InputIterator b, InputIterator e, char); 1261 1262 // Inserts a value into the btree. 1263 template <typename ValueType> 1264 iterator insert_multi(const key_type &key, ValueType &&v); 1265 1266 // Inserts a value into the btree. 1267 template <typename ValueType> 1268 iterator insert_multi(ValueType &&v) { 1269 return insert_multi(params_type::key(v), std::forward<ValueType>(v)); 1270 } 1271 1272 // Insert with hint. Check to see if the value should be placed immediately 1273 // before position in the tree. If it does, then the insertion will take 1274 // amortized constant time. If not, the insertion will take amortized 1275 // logarithmic time as if a call to insert_multi(v) were made. 1276 template <typename ValueType> 1277 iterator insert_hint_multi(iterator position, ValueType &&v); 1278 1279 // Insert a range of values into the btree. 1280 template <typename InputIterator> 1281 void insert_iterator_multi(InputIterator b, InputIterator e); 1282 1283 // Erase the specified iterator from the btree. The iterator must be valid 1284 // (i.e. not equal to end()). Return an iterator pointing to the node after 1285 // the one that was erased (or end() if none exists). 1286 // Requirement: does not read the value at `*iter`. 1287 iterator erase(iterator iter); 1288 1289 // Erases range. Returns the number of keys erased and an iterator pointing 1290 // to the element after the last erased element. 1291 std::pair<size_type, iterator> erase_range(iterator begin, iterator end); 1292 1293 // Finds the iterator corresponding to a key or returns end() if the key is 1294 // not present. 1295 template <typename K> 1296 iterator find(const K &key) { 1297 return internal_end(internal_find(key)); 1298 } 1299 template <typename K> 1300 const_iterator find(const K &key) const { 1301 return internal_end(internal_find(key)); 1302 } 1303 1304 // Clear the btree, deleting all of the values it contains. 1305 void clear(); 1306 1307 // Swaps the contents of `this` and `other`. 1308 void swap(btree &other); 1309 1310 const key_compare &key_comp() const noexcept { 1311 return root_.template get<0>(); 1312 } 1313 template <typename K1, typename K2> 1314 bool compare_keys(const K1 &a, const K2 &b) const { 1315 return compare_internal::compare_result_as_less_than(key_comp()(a, b)); 1316 } 1317 1318 value_compare value_comp() const { return value_compare(key_comp()); } 1319 1320 // Verifies the structure of the btree. 1321 void verify() const; 1322 1323 // Size routines. 1324 size_type size() const { return size_; } 1325 size_type max_size() const { return (std::numeric_limits<size_type>::max)(); } 1326 bool empty() const { return size_ == 0; } 1327 1328 // The height of the btree. An empty tree will have height 0. 1329 size_type height() const { 1330 size_type h = 0; 1331 if (!empty()) { 1332 // Count the length of the chain from the leftmost node up to the 1333 // root. We actually count from the root back around to the level below 1334 // the root, but the calculation is the same because of the circularity 1335 // of that traversal. 1336 const node_type *n = root(); 1337 do { 1338 ++h; 1339 n = n->parent(); 1340 } while (n != root()); 1341 } 1342 return h; 1343 } 1344 1345 // The number of internal, leaf and total nodes used by the btree. 1346 size_type leaf_nodes() const { return internal_stats(root()).leaf_nodes; } 1347 size_type internal_nodes() const { 1348 return internal_stats(root()).internal_nodes; 1349 } 1350 size_type nodes() const { 1351 node_stats stats = internal_stats(root()); 1352 return stats.leaf_nodes + stats.internal_nodes; 1353 } 1354 1355 // The total number of bytes used by the btree. 1356 size_type bytes_used() const { 1357 node_stats stats = internal_stats(root()); 1358 if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) { 1359 return sizeof(*this) + node_type::LeafSize(root()->max_count()); 1360 } else { 1361 return sizeof(*this) + stats.leaf_nodes * node_type::LeafSize() + 1362 stats.internal_nodes * node_type::InternalSize(); 1363 } 1364 } 1365 1366 // The average number of bytes used per value stored in the btree. 1367 static double average_bytes_per_value() { 1368 // Returns the number of bytes per value on a leaf node that is 75% 1369 // full. Experimentally, this matches up nicely with the computed number of 1370 // bytes per value in trees that had their values inserted in random order. 1371 return node_type::LeafSize() / (kNodeValues * 0.75); 1372 } 1373 1374 // The fullness of the btree. Computed as the number of elements in the btree 1375 // divided by the maximum number of elements a tree with the current number 1376 // of nodes could hold. A value of 1 indicates perfect space 1377 // utilization. Smaller values indicate space wastage. 1378 // Returns 0 for empty trees. 1379 double fullness() const { 1380 if (empty()) return 0.0; 1381 return static_cast<double>(size()) / (nodes() * kNodeValues); 1382 } 1383 // The overhead of the btree structure in bytes per node. Computed as the 1384 // total number of bytes used by the btree minus the number of bytes used for 1385 // storing elements divided by the number of elements. 1386 // Returns 0 for empty trees. 1387 double overhead() const { 1388 if (empty()) return 0.0; 1389 return (bytes_used() - size() * sizeof(value_type)) / 1390 static_cast<double>(size()); 1391 } 1392 1393 // The allocator used by the btree. 1394 allocator_type get_allocator() const { return allocator(); } 1395 1396 private: 1397 // Internal accessor routines. 1398 node_type *root() { return root_.template get<2>(); } 1399 const node_type *root() const { return root_.template get<2>(); } 1400 node_type *&mutable_root() noexcept { return root_.template get<2>(); } 1401 key_compare *mutable_key_comp() noexcept { return &root_.template get<0>(); } 1402 1403 // The leftmost node is stored as the parent of the root node. 1404 node_type *leftmost() { return root()->parent(); } 1405 const node_type *leftmost() const { return root()->parent(); } 1406 1407 // Allocator routines. 1408 allocator_type *mutable_allocator() noexcept { 1409 return &root_.template get<1>(); 1410 } 1411 const allocator_type &allocator() const noexcept { 1412 return root_.template get<1>(); 1413 } 1414 1415 // Allocates a correctly aligned node of at least size bytes using the 1416 // allocator. 1417 node_type *allocate(const size_type size) { 1418 return reinterpret_cast<node_type *>( 1419 absl::container_internal::Allocate<node_type::Alignment()>( 1420 mutable_allocator(), size)); 1421 } 1422 1423 // Node creation/deletion routines. 1424 node_type *new_internal_node(node_type *parent) { 1425 node_type *n = allocate(node_type::InternalSize()); 1426 n->init_internal(parent); 1427 return n; 1428 } 1429 node_type *new_leaf_node(node_type *parent) { 1430 node_type *n = allocate(node_type::LeafSize()); 1431 n->init_leaf(parent, kNodeValues); 1432 return n; 1433 } 1434 node_type *new_leaf_root_node(const int max_count) { 1435 node_type *n = allocate(node_type::LeafSize(max_count)); 1436 n->init_leaf(/*parent=*/n, max_count); 1437 return n; 1438 } 1439 1440 // Deletion helper routines. 1441 iterator rebalance_after_delete(iterator iter); 1442 1443 // Rebalances or splits the node iter points to. 1444 void rebalance_or_split(iterator *iter); 1445 1446 // Merges the values of left, right and the delimiting key on their parent 1447 // onto left, removing the delimiting key and deleting right. 1448 void merge_nodes(node_type *left, node_type *right); 1449 1450 // Tries to merge node with its left or right sibling, and failing that, 1451 // rebalance with its left or right sibling. Returns true if a merge 1452 // occurred, at which point it is no longer valid to access node. Returns 1453 // false if no merging took place. 1454 bool try_merge_or_rebalance(iterator *iter); 1455 1456 // Tries to shrink the height of the tree by 1. 1457 void try_shrink(); 1458 1459 iterator internal_end(iterator iter) { 1460 return iter.node != nullptr ? iter : end(); 1461 } 1462 const_iterator internal_end(const_iterator iter) const { 1463 return iter.node != nullptr ? iter : end(); 1464 } 1465 1466 // Emplaces a value into the btree immediately before iter. Requires that 1467 // key(v) <= iter.key() and (--iter).key() <= key(v). 1468 template <typename... Args> 1469 iterator internal_emplace(iterator iter, Args &&... args); 1470 1471 // Returns an iterator pointing to the first value >= the value "iter" is 1472 // pointing at. Note that "iter" might be pointing to an invalid location such 1473 // as iter.position == iter.node->finish(). This routine simply moves iter up 1474 // in the tree to a valid location. 1475 // Requires: iter.node is non-null. 1476 template <typename IterType> 1477 static IterType internal_last(IterType iter); 1478 1479 // Returns an iterator pointing to the leaf position at which key would 1480 // reside in the tree, unless there is an exact match - in which case, the 1481 // result may not be on a leaf. When there's a three-way comparator, we can 1482 // return whether there was an exact match. This allows the caller to avoid a 1483 // subsequent comparison to determine if an exact match was made, which is 1484 // important for keys with expensive comparison, such as strings. 1485 template <typename K> 1486 SearchResult<iterator, is_key_compare_to::value> internal_locate( 1487 const K &key) const; 1488 1489 // Internal routine which implements lower_bound(). 1490 template <typename K> 1491 SearchResult<iterator, is_key_compare_to::value> internal_lower_bound( 1492 const K &key) const; 1493 1494 // Internal routine which implements upper_bound(). 1495 template <typename K> 1496 iterator internal_upper_bound(const K &key) const; 1497 1498 // Internal routine which implements find(). 1499 template <typename K> 1500 iterator internal_find(const K &key) const; 1501 1502 // Verifies the tree structure of node. 1503 int internal_verify(const node_type *node, const key_type *lo, 1504 const key_type *hi) const; 1505 1506 node_stats internal_stats(const node_type *node) const { 1507 // The root can be a static empty node. 1508 if (node == nullptr || (node == root() && empty())) { 1509 return node_stats(0, 0); 1510 } 1511 if (node->leaf()) { 1512 return node_stats(1, 0); 1513 } 1514 node_stats res(0, 1); 1515 for (int i = node->start(); i <= node->finish(); ++i) { 1516 res += internal_stats(node->child(i)); 1517 } 1518 return res; 1519 } 1520 1521 // We use compressed tuple in order to save space because key_compare and 1522 // allocator_type are usually empty. 1523 absl::container_internal::CompressedTuple<key_compare, allocator_type, 1524 node_type *> 1525 root_; 1526 1527 // A pointer to the rightmost node. Note that the leftmost node is stored as 1528 // the root's parent. 1529 node_type *rightmost_; 1530 1531 // Number of values. 1532 size_type size_; 1533 }; 1534 1535 //// 1536 // btree_node methods 1537 template <typename P> 1538 template <typename... Args> 1539 inline void btree_node<P>::emplace_value(const size_type i, 1540 allocator_type *alloc, 1541 Args &&... args) { 1542 assert(i >= start()); 1543 assert(i <= finish()); 1544 // Shift old values to create space for new value and then construct it in 1545 // place. 1546 if (i < finish()) { 1547 transfer_n_backward(finish() - i, /*dest_i=*/i + 1, /*src_i=*/i, this, 1548 alloc); 1549 } 1550 value_init(i, alloc, std::forward<Args>(args)...); 1551 set_finish(finish() + 1); 1552 1553 if (!leaf() && finish() > i + 1) { 1554 for (int j = finish(); j > i + 1; --j) { 1555 set_child(j, child(j - 1)); 1556 } 1557 clear_child(i + 1); 1558 } 1559 } 1560 1561 template <typename P> 1562 inline void btree_node<P>::remove_values(const field_type i, 1563 const field_type to_erase, 1564 allocator_type *alloc) { 1565 // Transfer values after the removed range into their new places. 1566 value_destroy_n(i, to_erase, alloc); 1567 const field_type orig_finish = finish(); 1568 const field_type src_i = i + to_erase; 1569 transfer_n(orig_finish - src_i, i, src_i, this, alloc); 1570 1571 if (!leaf()) { 1572 // Delete all children between begin and end. 1573 for (int j = 0; j < to_erase; ++j) { 1574 clear_and_delete(child(i + j + 1), alloc); 1575 } 1576 // Rotate children after end into new positions. 1577 for (int j = i + to_erase + 1; j <= orig_finish; ++j) { 1578 set_child(j - to_erase, child(j)); 1579 clear_child(j); 1580 } 1581 } 1582 set_finish(orig_finish - to_erase); 1583 } 1584 1585 template <typename P> 1586 void btree_node<P>::rebalance_right_to_left(const int to_move, 1587 btree_node *right, 1588 allocator_type *alloc) { 1589 assert(parent() == right->parent()); 1590 assert(position() + 1 == right->position()); 1591 assert(right->count() >= count()); 1592 assert(to_move >= 1); 1593 assert(to_move <= right->count()); 1594 1595 // 1) Move the delimiting value in the parent to the left node. 1596 transfer(finish(), position(), parent(), alloc); 1597 1598 // 2) Move the (to_move - 1) values from the right node to the left node. 1599 transfer_n(to_move - 1, finish() + 1, right->start(), right, alloc); 1600 1601 // 3) Move the new delimiting value to the parent from the right node. 1602 parent()->transfer(position(), right->start() + to_move - 1, right, alloc); 1603 1604 // 4) Shift the values in the right node to their correct positions. 1605 right->transfer_n(right->count() - to_move, right->start(), 1606 right->start() + to_move, right, alloc); 1607 1608 if (!leaf()) { 1609 // Move the child pointers from the right to the left node. 1610 for (int i = 0; i < to_move; ++i) { 1611 init_child(finish() + i + 1, right->child(i)); 1612 } 1613 for (int i = right->start(); i <= right->finish() - to_move; ++i) { 1614 assert(i + to_move <= right->max_count()); 1615 right->init_child(i, right->child(i + to_move)); 1616 right->clear_child(i + to_move); 1617 } 1618 } 1619 1620 // Fixup `finish` on the left and right nodes. 1621 set_finish(finish() + to_move); 1622 right->set_finish(right->finish() - to_move); 1623 } 1624 1625 template <typename P> 1626 void btree_node<P>::rebalance_left_to_right(const int to_move, 1627 btree_node *right, 1628 allocator_type *alloc) { 1629 assert(parent() == right->parent()); 1630 assert(position() + 1 == right->position()); 1631 assert(count() >= right->count()); 1632 assert(to_move >= 1); 1633 assert(to_move <= count()); 1634 1635 // Values in the right node are shifted to the right to make room for the 1636 // new to_move values. Then, the delimiting value in the parent and the 1637 // other (to_move - 1) values in the left node are moved into the right node. 1638 // Lastly, a new delimiting value is moved from the left node into the 1639 // parent, and the remaining empty left node entries are destroyed. 1640 1641 // 1) Shift existing values in the right node to their correct positions. 1642 right->transfer_n_backward(right->count(), right->start() + to_move, 1643 right->start(), right, alloc); 1644 1645 // 2) Move the delimiting value in the parent to the right node. 1646 right->transfer(right->start() + to_move - 1, position(), parent(), alloc); 1647 1648 // 3) Move the (to_move - 1) values from the left node to the right node. 1649 right->transfer_n(to_move - 1, right->start(), finish() - (to_move - 1), this, 1650 alloc); 1651 1652 // 4) Move the new delimiting value to the parent from the left node. 1653 parent()->transfer(position(), finish() - to_move, this, alloc); 1654 1655 if (!leaf()) { 1656 // Move the child pointers from the left to the right node. 1657 for (int i = right->finish(); i >= right->start(); --i) { 1658 right->init_child(i + to_move, right->child(i)); 1659 right->clear_child(i); 1660 } 1661 for (int i = 1; i <= to_move; ++i) { 1662 right->init_child(i - 1, child(finish() - to_move + i)); 1663 clear_child(finish() - to_move + i); 1664 } 1665 } 1666 1667 // Fixup the counts on the left and right nodes. 1668 set_finish(finish() - to_move); 1669 right->set_finish(right->finish() + to_move); 1670 } 1671 1672 template <typename P> 1673 void btree_node<P>::split(const int insert_position, btree_node *dest, 1674 allocator_type *alloc) { 1675 assert(dest->count() == 0); 1676 assert(max_count() == kNodeValues); 1677 1678 // We bias the split based on the position being inserted. If we're 1679 // inserting at the beginning of the left node then bias the split to put 1680 // more values on the right node. If we're inserting at the end of the 1681 // right node then bias the split to put more values on the left node. 1682 if (insert_position == start()) { 1683 dest->set_finish(dest->start() + finish() - 1); 1684 } else if (insert_position == kNodeValues) { 1685 dest->set_finish(dest->start()); 1686 } else { 1687 dest->set_finish(dest->start() + count() / 2); 1688 } 1689 set_finish(finish() - dest->count()); 1690 assert(count() >= 1); 1691 1692 // Move values from the left sibling to the right sibling. 1693 dest->transfer_n(dest->count(), dest->start(), finish(), this, alloc); 1694 1695 // The split key is the largest value in the left sibling. 1696 --mutable_finish(); 1697 parent()->emplace_value(position(), alloc, finish_slot()); 1698 value_destroy(finish(), alloc); 1699 parent()->init_child(position() + 1, dest); 1700 1701 if (!leaf()) { 1702 for (int i = dest->start(), j = finish() + 1; i <= dest->finish(); 1703 ++i, ++j) { 1704 assert(child(j) != nullptr); 1705 dest->init_child(i, child(j)); 1706 clear_child(j); 1707 } 1708 } 1709 } 1710 1711 template <typename P> 1712 void btree_node<P>::merge(btree_node *src, allocator_type *alloc) { 1713 assert(parent() == src->parent()); 1714 assert(position() + 1 == src->position()); 1715 1716 // Move the delimiting value to the left node. 1717 value_init(finish(), alloc, parent()->slot(position())); 1718 1719 // Move the values from the right to the left node. 1720 transfer_n(src->count(), finish() + 1, src->start(), src, alloc); 1721 1722 if (!leaf()) { 1723 // Move the child pointers from the right to the left node. 1724 for (int i = src->start(), j = finish() + 1; i <= src->finish(); ++i, ++j) { 1725 init_child(j, src->child(i)); 1726 src->clear_child(i); 1727 } 1728 } 1729 1730 // Fixup `finish` on the src and dest nodes. 1731 set_finish(start() + 1 + count() + src->count()); 1732 src->set_finish(src->start()); 1733 1734 // Remove the value on the parent node and delete the src node. 1735 parent()->remove_values(position(), /*to_erase=*/1, alloc); 1736 } 1737 1738 template <typename P> 1739 void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) { 1740 if (node->leaf()) { 1741 node->value_destroy_n(node->start(), node->count(), alloc); 1742 deallocate(LeafSize(node->max_count()), node, alloc); 1743 return; 1744 } 1745 if (node->count() == 0) { 1746 deallocate(InternalSize(), node, alloc); 1747 return; 1748 } 1749 1750 // The parent of the root of the subtree we are deleting. 1751 btree_node *delete_root_parent = node->parent(); 1752 1753 // Navigate to the leftmost leaf under node, and then delete upwards. 1754 while (!node->leaf()) node = node->start_child(); 1755 // Use `int` because `pos` needs to be able to hold `kNodeValues+1`, which 1756 // isn't guaranteed to be a valid `field_type`. 1757 int pos = node->position(); 1758 btree_node *parent = node->parent(); 1759 for (;;) { 1760 // In each iteration of the next loop, we delete one leaf node and go right. 1761 assert(pos <= parent->finish()); 1762 do { 1763 node = parent->child(pos); 1764 if (!node->leaf()) { 1765 // Navigate to the leftmost leaf under node. 1766 while (!node->leaf()) node = node->start_child(); 1767 pos = node->position(); 1768 parent = node->parent(); 1769 } 1770 node->value_destroy_n(node->start(), node->count(), alloc); 1771 deallocate(LeafSize(node->max_count()), node, alloc); 1772 ++pos; 1773 } while (pos <= parent->finish()); 1774 1775 // Once we've deleted all children of parent, delete parent and go up/right. 1776 assert(pos > parent->finish()); 1777 do { 1778 node = parent; 1779 pos = node->position(); 1780 parent = node->parent(); 1781 node->value_destroy_n(node->start(), node->count(), alloc); 1782 deallocate(InternalSize(), node, alloc); 1783 if (parent == delete_root_parent) return; 1784 ++pos; 1785 } while (pos > parent->finish()); 1786 } 1787 } 1788 1789 //// 1790 // btree_iterator methods 1791 template <typename N, typename R, typename P> 1792 void btree_iterator<N, R, P>::increment_slow() { 1793 if (node->leaf()) { 1794 assert(position >= node->finish()); 1795 btree_iterator save(*this); 1796 while (position == node->finish() && !node->is_root()) { 1797 assert(node->parent()->child(node->position()) == node); 1798 position = node->position(); 1799 node = node->parent(); 1800 } 1801 // TODO(ezb): assert we aren't incrementing end() instead of handling. 1802 if (position == node->finish()) { 1803 *this = save; 1804 } 1805 } else { 1806 assert(position < node->finish()); 1807 node = node->child(position + 1); 1808 while (!node->leaf()) { 1809 node = node->start_child(); 1810 } 1811 position = node->start(); 1812 } 1813 } 1814 1815 template <typename N, typename R, typename P> 1816 void btree_iterator<N, R, P>::decrement_slow() { 1817 if (node->leaf()) { 1818 assert(position <= -1); 1819 btree_iterator save(*this); 1820 while (position < node->start() && !node->is_root()) { 1821 assert(node->parent()->child(node->position()) == node); 1822 position = node->position() - 1; 1823 node = node->parent(); 1824 } 1825 // TODO(ezb): assert we aren't decrementing begin() instead of handling. 1826 if (position < node->start()) { 1827 *this = save; 1828 } 1829 } else { 1830 assert(position >= node->start()); 1831 node = node->child(position); 1832 while (!node->leaf()) { 1833 node = node->child(node->finish()); 1834 } 1835 position = node->finish() - 1; 1836 } 1837 } 1838 1839 //// 1840 // btree methods 1841 template <typename P> 1842 template <typename Btree> 1843 void btree<P>::copy_or_move_values_in_order(Btree &other) { 1844 static_assert(std::is_same<btree, Btree>::value || 1845 std::is_same<const btree, Btree>::value, 1846 "Btree type must be same or const."); 1847 assert(empty()); 1848 1849 // We can avoid key comparisons because we know the order of the 1850 // values is the same order we'll store them in. 1851 auto iter = other.begin(); 1852 if (iter == other.end()) return; 1853 insert_multi(maybe_move_from_iterator(iter)); 1854 ++iter; 1855 for (; iter != other.end(); ++iter) { 1856 // If the btree is not empty, we can just insert the new value at the end 1857 // of the tree. 1858 internal_emplace(end(), maybe_move_from_iterator(iter)); 1859 } 1860 } 1861 1862 template <typename P> 1863 constexpr bool btree<P>::static_assert_validation() { 1864 static_assert(std::is_nothrow_copy_constructible<key_compare>::value, 1865 "Key comparison must be nothrow copy constructible"); 1866 static_assert(std::is_nothrow_copy_constructible<allocator_type>::value, 1867 "Allocator must be nothrow copy constructible"); 1868 static_assert(type_traits_internal::is_trivially_copyable<iterator>::value, 1869 "iterator not trivially copyable."); 1870 1871 // Note: We assert that kTargetValues, which is computed from 1872 // Params::kTargetNodeSize, must fit the node_type::field_type. 1873 static_assert( 1874 kNodeValues < (1 << (8 * sizeof(typename node_type::field_type))), 1875 "target node size too large"); 1876 1877 // Verify that key_compare returns an absl::{weak,strong}_ordering or bool. 1878 using compare_result_type = 1879 absl::result_of_t<key_compare(key_type, key_type)>; 1880 static_assert( 1881 std::is_same<compare_result_type, bool>::value || 1882 std::is_convertible<compare_result_type, absl::weak_ordering>::value, 1883 "key comparison function must return absl::{weak,strong}_ordering or " 1884 "bool."); 1885 1886 // Test the assumption made in setting kNodeValueSpace. 1887 static_assert(node_type::MinimumOverhead() >= sizeof(void *) + 4, 1888 "node space assumption incorrect"); 1889 1890 return true; 1891 } 1892 1893 template <typename P> 1894 template <typename K> 1895 auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> { 1896 const SearchResult<iterator, is_key_compare_to::value> res = 1897 internal_lower_bound(key); 1898 const iterator lower = internal_end(res.value); 1899 if (res.HasMatch() ? !res.IsEq() 1900 : lower == end() || compare_keys(key, lower.key())) { 1901 return {lower, lower}; 1902 } 1903 1904 const iterator next = std::next(lower); 1905 // When the comparator is heterogeneous, we can't assume that comparison with 1906 // non-`key_type` will be equivalent to `key_type` comparisons so there 1907 // could be multiple equivalent keys even in a unique-container. But for 1908 // heterogeneous comparisons from the default string adapted comparators, we 1909 // don't need to worry about this. 1910 if (!is_multi_container::value && 1911 (std::is_same<K, key_type>::value || is_key_compare_adapted::value)) { 1912 // The next iterator after lower must point to a key greater than `key`. 1913 // Note: if this assert fails, then it may indicate that the comparator does 1914 // not meet the equivalence requirements for Compare 1915 // (see https://en.cppreference.com/w/cpp/named_req/Compare). 1916 assert(next == end() || compare_keys(key, next.key())); 1917 return {lower, next}; 1918 } 1919 // Try once more to avoid the call to upper_bound() if there's only one 1920 // equivalent key. This should prevent all calls to upper_bound() in cases of 1921 // unique-containers with heterogeneous comparators in which all comparison 1922 // operators have the same equivalence classes. 1923 if (next == end() || compare_keys(key, next.key())) return {lower, next}; 1924 1925 // In this case, we need to call upper_bound() to avoid worst case O(N) 1926 // behavior if we were to iterate over equal keys. 1927 return {lower, upper_bound(key)}; 1928 } 1929 1930 template <typename P> 1931 template <typename K, typename... Args> 1932 auto btree<P>::insert_unique(const K &key, Args &&... args) 1933 -> std::pair<iterator, bool> { 1934 if (empty()) { 1935 mutable_root() = rightmost_ = new_leaf_root_node(1); 1936 } 1937 1938 SearchResult<iterator, is_key_compare_to::value> res = internal_locate(key); 1939 iterator iter = res.value; 1940 1941 if (res.HasMatch()) { 1942 if (res.IsEq()) { 1943 // The key already exists in the tree, do nothing. 1944 return {iter, false}; 1945 } 1946 } else { 1947 iterator last = internal_last(iter); 1948 if (last.node && !compare_keys(key, last.key())) { 1949 // The key already exists in the tree, do nothing. 1950 return {last, false}; 1951 } 1952 } 1953 return {internal_emplace(iter, std::forward<Args>(args)...), true}; 1954 } 1955 1956 template <typename P> 1957 template <typename K, typename... Args> 1958 inline auto btree<P>::insert_hint_unique(iterator position, const K &key, 1959 Args &&... args) 1960 -> std::pair<iterator, bool> { 1961 if (!empty()) { 1962 if (position == end() || compare_keys(key, position.key())) { 1963 if (position == begin() || compare_keys(std::prev(position).key(), key)) { 1964 // prev.key() < key < position.key() 1965 return {internal_emplace(position, std::forward<Args>(args)...), true}; 1966 } 1967 } else if (compare_keys(position.key(), key)) { 1968 ++position; 1969 if (position == end() || compare_keys(key, position.key())) { 1970 // {original `position`}.key() < key < {current `position`}.key() 1971 return {internal_emplace(position, std::forward<Args>(args)...), true}; 1972 } 1973 } else { 1974 // position.key() == key 1975 return {position, false}; 1976 } 1977 } 1978 return insert_unique(key, std::forward<Args>(args)...); 1979 } 1980 1981 template <typename P> 1982 template <typename InputIterator, typename> 1983 void btree<P>::insert_iterator_unique(InputIterator b, InputIterator e, int) { 1984 for (; b != e; ++b) { 1985 insert_hint_unique(end(), params_type::key(*b), *b); 1986 } 1987 } 1988 1989 template <typename P> 1990 template <typename InputIterator> 1991 void btree<P>::insert_iterator_unique(InputIterator b, InputIterator e, char) { 1992 for (; b != e; ++b) { 1993 init_type value(*b); 1994 insert_hint_unique(end(), params_type::key(value), std::move(value)); 1995 } 1996 } 1997 1998 template <typename P> 1999 template <typename ValueType> 2000 auto btree<P>::insert_multi(const key_type &key, ValueType &&v) -> iterator { 2001 if (empty()) { 2002 mutable_root() = rightmost_ = new_leaf_root_node(1); 2003 } 2004 2005 iterator iter = internal_upper_bound(key); 2006 if (iter.node == nullptr) { 2007 iter = end(); 2008 } 2009 return internal_emplace(iter, std::forward<ValueType>(v)); 2010 } 2011 2012 template <typename P> 2013 template <typename ValueType> 2014 auto btree<P>::insert_hint_multi(iterator position, ValueType &&v) -> iterator { 2015 if (!empty()) { 2016 const key_type &key = params_type::key(v); 2017 if (position == end() || !compare_keys(position.key(), key)) { 2018 if (position == begin() || 2019 !compare_keys(key, std::prev(position).key())) { 2020 // prev.key() <= key <= position.key() 2021 return internal_emplace(position, std::forward<ValueType>(v)); 2022 } 2023 } else { 2024 ++position; 2025 if (position == end() || !compare_keys(position.key(), key)) { 2026 // {original `position`}.key() < key < {current `position`}.key() 2027 return internal_emplace(position, std::forward<ValueType>(v)); 2028 } 2029 } 2030 } 2031 return insert_multi(std::forward<ValueType>(v)); 2032 } 2033 2034 template <typename P> 2035 template <typename InputIterator> 2036 void btree<P>::insert_iterator_multi(InputIterator b, InputIterator e) { 2037 for (; b != e; ++b) { 2038 insert_hint_multi(end(), *b); 2039 } 2040 } 2041 2042 template <typename P> 2043 auto btree<P>::operator=(const btree &other) -> btree & { 2044 if (this != &other) { 2045 clear(); 2046 2047 *mutable_key_comp() = other.key_comp(); 2048 if (absl::allocator_traits< 2049 allocator_type>::propagate_on_container_copy_assignment::value) { 2050 *mutable_allocator() = other.allocator(); 2051 } 2052 2053 copy_or_move_values_in_order(other); 2054 } 2055 return *this; 2056 } 2057 2058 template <typename P> 2059 auto btree<P>::operator=(btree &&other) noexcept -> btree & { 2060 if (this != &other) { 2061 clear(); 2062 2063 using std::swap; 2064 if (absl::allocator_traits< 2065 allocator_type>::propagate_on_container_copy_assignment::value) { 2066 // Note: `root_` also contains the allocator and the key comparator. 2067 swap(root_, other.root_); 2068 swap(rightmost_, other.rightmost_); 2069 swap(size_, other.size_); 2070 } else { 2071 if (allocator() == other.allocator()) { 2072 swap(mutable_root(), other.mutable_root()); 2073 swap(*mutable_key_comp(), *other.mutable_key_comp()); 2074 swap(rightmost_, other.rightmost_); 2075 swap(size_, other.size_); 2076 } else { 2077 // We aren't allowed to propagate the allocator and the allocator is 2078 // different so we can't take over its memory. We must move each element 2079 // individually. We need both `other` and `this` to have `other`s key 2080 // comparator while moving the values so we can't swap the key 2081 // comparators. 2082 *mutable_key_comp() = other.key_comp(); 2083 copy_or_move_values_in_order(other); 2084 } 2085 } 2086 } 2087 return *this; 2088 } 2089 2090 template <typename P> 2091 auto btree<P>::erase(iterator iter) -> iterator { 2092 bool internal_delete = false; 2093 if (!iter.node->leaf()) { 2094 // Deletion of a value on an internal node. First, move the largest value 2095 // from our left child here, then delete that position (in remove_values() 2096 // below). We can get to the largest value from our left child by 2097 // decrementing iter. 2098 iterator internal_iter(iter); 2099 --iter; 2100 assert(iter.node->leaf()); 2101 params_type::move(mutable_allocator(), iter.node->slot(iter.position), 2102 internal_iter.node->slot(internal_iter.position)); 2103 internal_delete = true; 2104 } 2105 2106 // Delete the key from the leaf. 2107 iter.node->remove_values(iter.position, /*to_erase=*/1, mutable_allocator()); 2108 --size_; 2109 2110 // We want to return the next value after the one we just erased. If we 2111 // erased from an internal node (internal_delete == true), then the next 2112 // value is ++(++iter). If we erased from a leaf node (internal_delete == 2113 // false) then the next value is ++iter. Note that ++iter may point to an 2114 // internal node and the value in the internal node may move to a leaf node 2115 // (iter.node) when rebalancing is performed at the leaf level. 2116 2117 iterator res = rebalance_after_delete(iter); 2118 2119 // If we erased from an internal node, advance the iterator. 2120 if (internal_delete) { 2121 ++res; 2122 } 2123 return res; 2124 } 2125 2126 template <typename P> 2127 auto btree<P>::rebalance_after_delete(iterator iter) -> iterator { 2128 // Merge/rebalance as we walk back up the tree. 2129 iterator res(iter); 2130 bool first_iteration = true; 2131 for (;;) { 2132 if (iter.node == root()) { 2133 try_shrink(); 2134 if (empty()) { 2135 return end(); 2136 } 2137 break; 2138 } 2139 if (iter.node->count() >= kMinNodeValues) { 2140 break; 2141 } 2142 bool merged = try_merge_or_rebalance(&iter); 2143 // On the first iteration, we should update `res` with `iter` because `res` 2144 // may have been invalidated. 2145 if (first_iteration) { 2146 res = iter; 2147 first_iteration = false; 2148 } 2149 if (!merged) { 2150 break; 2151 } 2152 iter.position = iter.node->position(); 2153 iter.node = iter.node->parent(); 2154 } 2155 2156 // Adjust our return value. If we're pointing at the end of a node, advance 2157 // the iterator. 2158 if (res.position == res.node->finish()) { 2159 res.position = res.node->finish() - 1; 2160 ++res; 2161 } 2162 2163 return res; 2164 } 2165 2166 template <typename P> 2167 auto btree<P>::erase_range(iterator begin, iterator end) 2168 -> std::pair<size_type, iterator> { 2169 difference_type count = std::distance(begin, end); 2170 assert(count >= 0); 2171 2172 if (count == 0) { 2173 return {0, begin}; 2174 } 2175 2176 if (count == size_) { 2177 clear(); 2178 return {count, this->end()}; 2179 } 2180 2181 if (begin.node == end.node) { 2182 assert(end.position > begin.position); 2183 begin.node->remove_values(begin.position, end.position - begin.position, 2184 mutable_allocator()); 2185 size_ -= count; 2186 return {count, rebalance_after_delete(begin)}; 2187 } 2188 2189 const size_type target_size = size_ - count; 2190 while (size_ > target_size) { 2191 if (begin.node->leaf()) { 2192 const size_type remaining_to_erase = size_ - target_size; 2193 const size_type remaining_in_node = begin.node->finish() - begin.position; 2194 const size_type to_erase = 2195 (std::min)(remaining_to_erase, remaining_in_node); 2196 begin.node->remove_values(begin.position, to_erase, mutable_allocator()); 2197 size_ -= to_erase; 2198 begin = rebalance_after_delete(begin); 2199 } else { 2200 begin = erase(begin); 2201 } 2202 } 2203 return {count, begin}; 2204 } 2205 2206 template <typename P> 2207 void btree<P>::clear() { 2208 if (!empty()) { 2209 node_type::clear_and_delete(root(), mutable_allocator()); 2210 } 2211 mutable_root() = EmptyNode(); 2212 rightmost_ = EmptyNode(); 2213 size_ = 0; 2214 } 2215 2216 template <typename P> 2217 void btree<P>::swap(btree &other) { 2218 using std::swap; 2219 if (absl::allocator_traits< 2220 allocator_type>::propagate_on_container_swap::value) { 2221 // Note: `root_` also contains the allocator and the key comparator. 2222 swap(root_, other.root_); 2223 } else { 2224 // It's undefined behavior if the allocators are unequal here. 2225 assert(allocator() == other.allocator()); 2226 swap(mutable_root(), other.mutable_root()); 2227 swap(*mutable_key_comp(), *other.mutable_key_comp()); 2228 } 2229 swap(rightmost_, other.rightmost_); 2230 swap(size_, other.size_); 2231 } 2232 2233 template <typename P> 2234 void btree<P>::verify() const { 2235 assert(root() != nullptr); 2236 assert(leftmost() != nullptr); 2237 assert(rightmost_ != nullptr); 2238 assert(empty() || size() == internal_verify(root(), nullptr, nullptr)); 2239 assert(leftmost() == (++const_iterator(root(), -1)).node); 2240 assert(rightmost_ == (--const_iterator(root(), root()->finish())).node); 2241 assert(leftmost()->leaf()); 2242 assert(rightmost_->leaf()); 2243 } 2244 2245 template <typename P> 2246 void btree<P>::rebalance_or_split(iterator *iter) { 2247 node_type *&node = iter->node; 2248 int &insert_position = iter->position; 2249 assert(node->count() == node->max_count()); 2250 assert(kNodeValues == node->max_count()); 2251 2252 // First try to make room on the node by rebalancing. 2253 node_type *parent = node->parent(); 2254 if (node != root()) { 2255 if (node->position() > parent->start()) { 2256 // Try rebalancing with our left sibling. 2257 node_type *left = parent->child(node->position() - 1); 2258 assert(left->max_count() == kNodeValues); 2259 if (left->count() < kNodeValues) { 2260 // We bias rebalancing based on the position being inserted. If we're 2261 // inserting at the end of the right node then we bias rebalancing to 2262 // fill up the left node. 2263 int to_move = (kNodeValues - left->count()) / 2264 (1 + (insert_position < static_cast<int>(kNodeValues))); 2265 to_move = (std::max)(1, to_move); 2266 2267 if (insert_position - to_move >= node->start() || 2268 left->count() + to_move < static_cast<int>(kNodeValues)) { 2269 left->rebalance_right_to_left(to_move, node, mutable_allocator()); 2270 2271 assert(node->max_count() - node->count() == to_move); 2272 insert_position = insert_position - to_move; 2273 if (insert_position < node->start()) { 2274 insert_position = insert_position + left->count() + 1; 2275 node = left; 2276 } 2277 2278 assert(node->count() < node->max_count()); 2279 return; 2280 } 2281 } 2282 } 2283 2284 if (node->position() < parent->finish()) { 2285 // Try rebalancing with our right sibling. 2286 node_type *right = parent->child(node->position() + 1); 2287 assert(right->max_count() == kNodeValues); 2288 if (right->count() < kNodeValues) { 2289 // We bias rebalancing based on the position being inserted. If we're 2290 // inserting at the beginning of the left node then we bias rebalancing 2291 // to fill up the right node. 2292 int to_move = (static_cast<int>(kNodeValues) - right->count()) / 2293 (1 + (insert_position > node->start())); 2294 to_move = (std::max)(1, to_move); 2295 2296 if (insert_position <= node->finish() - to_move || 2297 right->count() + to_move < static_cast<int>(kNodeValues)) { 2298 node->rebalance_left_to_right(to_move, right, mutable_allocator()); 2299 2300 if (insert_position > node->finish()) { 2301 insert_position = insert_position - node->count() - 1; 2302 node = right; 2303 } 2304 2305 assert(node->count() < node->max_count()); 2306 return; 2307 } 2308 } 2309 } 2310 2311 // Rebalancing failed, make sure there is room on the parent node for a new 2312 // value. 2313 assert(parent->max_count() == kNodeValues); 2314 if (parent->count() == kNodeValues) { 2315 iterator parent_iter(node->parent(), node->position()); 2316 rebalance_or_split(&parent_iter); 2317 } 2318 } else { 2319 // Rebalancing not possible because this is the root node. 2320 // Create a new root node and set the current root node as the child of the 2321 // new root. 2322 parent = new_internal_node(parent); 2323 parent->init_child(parent->start(), root()); 2324 mutable_root() = parent; 2325 // If the former root was a leaf node, then it's now the rightmost node. 2326 assert(!parent->start_child()->leaf() || 2327 parent->start_child() == rightmost_); 2328 } 2329 2330 // Split the node. 2331 node_type *split_node; 2332 if (node->leaf()) { 2333 split_node = new_leaf_node(parent); 2334 node->split(insert_position, split_node, mutable_allocator()); 2335 if (rightmost_ == node) rightmost_ = split_node; 2336 } else { 2337 split_node = new_internal_node(parent); 2338 node->split(insert_position, split_node, mutable_allocator()); 2339 } 2340 2341 if (insert_position > node->finish()) { 2342 insert_position = insert_position - node->count() - 1; 2343 node = split_node; 2344 } 2345 } 2346 2347 template <typename P> 2348 void btree<P>::merge_nodes(node_type *left, node_type *right) { 2349 left->merge(right, mutable_allocator()); 2350 if (rightmost_ == right) rightmost_ = left; 2351 } 2352 2353 template <typename P> 2354 bool btree<P>::try_merge_or_rebalance(iterator *iter) { 2355 node_type *parent = iter->node->parent(); 2356 if (iter->node->position() > parent->start()) { 2357 // Try merging with our left sibling. 2358 node_type *left = parent->child(iter->node->position() - 1); 2359 assert(left->max_count() == kNodeValues); 2360 if (1U + left->count() + iter->node->count() <= kNodeValues) { 2361 iter->position += 1 + left->count(); 2362 merge_nodes(left, iter->node); 2363 iter->node = left; 2364 return true; 2365 } 2366 } 2367 if (iter->node->position() < parent->finish()) { 2368 // Try merging with our right sibling. 2369 node_type *right = parent->child(iter->node->position() + 1); 2370 assert(right->max_count() == kNodeValues); 2371 if (1U + iter->node->count() + right->count() <= kNodeValues) { 2372 merge_nodes(iter->node, right); 2373 return true; 2374 } 2375 // Try rebalancing with our right sibling. We don't perform rebalancing if 2376 // we deleted the first element from iter->node and the node is not 2377 // empty. This is a small optimization for the common pattern of deleting 2378 // from the front of the tree. 2379 if (right->count() > kMinNodeValues && 2380 (iter->node->count() == 0 || iter->position > iter->node->start())) { 2381 int to_move = (right->count() - iter->node->count()) / 2; 2382 to_move = (std::min)(to_move, right->count() - 1); 2383 iter->node->rebalance_right_to_left(to_move, right, mutable_allocator()); 2384 return false; 2385 } 2386 } 2387 if (iter->node->position() > parent->start()) { 2388 // Try rebalancing with our left sibling. We don't perform rebalancing if 2389 // we deleted the last element from iter->node and the node is not 2390 // empty. This is a small optimization for the common pattern of deleting 2391 // from the back of the tree. 2392 node_type *left = parent->child(iter->node->position() - 1); 2393 if (left->count() > kMinNodeValues && 2394 (iter->node->count() == 0 || iter->position < iter->node->finish())) { 2395 int to_move = (left->count() - iter->node->count()) / 2; 2396 to_move = (std::min)(to_move, left->count() - 1); 2397 left->rebalance_left_to_right(to_move, iter->node, mutable_allocator()); 2398 iter->position += to_move; 2399 return false; 2400 } 2401 } 2402 return false; 2403 } 2404 2405 template <typename P> 2406 void btree<P>::try_shrink() { 2407 node_type *orig_root = root(); 2408 if (orig_root->count() > 0) { 2409 return; 2410 } 2411 // Deleted the last item on the root node, shrink the height of the tree. 2412 if (orig_root->leaf()) { 2413 assert(size() == 0); 2414 mutable_root() = rightmost_ = EmptyNode(); 2415 } else { 2416 node_type *child = orig_root->start_child(); 2417 child->make_root(); 2418 mutable_root() = child; 2419 } 2420 node_type::clear_and_delete(orig_root, mutable_allocator()); 2421 } 2422 2423 template <typename P> 2424 template <typename IterType> 2425 inline IterType btree<P>::internal_last(IterType iter) { 2426 assert(iter.node != nullptr); 2427 while (iter.position == iter.node->finish()) { 2428 iter.position = iter.node->position(); 2429 iter.node = iter.node->parent(); 2430 if (iter.node->leaf()) { 2431 iter.node = nullptr; 2432 break; 2433 } 2434 } 2435 return iter; 2436 } 2437 2438 template <typename P> 2439 template <typename... Args> 2440 inline auto btree<P>::internal_emplace(iterator iter, Args &&... args) 2441 -> iterator { 2442 if (!iter.node->leaf()) { 2443 // We can't insert on an internal node. Instead, we'll insert after the 2444 // previous value which is guaranteed to be on a leaf node. 2445 --iter; 2446 ++iter.position; 2447 } 2448 const field_type max_count = iter.node->max_count(); 2449 allocator_type *alloc = mutable_allocator(); 2450 if (iter.node->count() == max_count) { 2451 // Make room in the leaf for the new item. 2452 if (max_count < kNodeValues) { 2453 // Insertion into the root where the root is smaller than the full node 2454 // size. Simply grow the size of the root node. 2455 assert(iter.node == root()); 2456 iter.node = 2457 new_leaf_root_node((std::min<int>)(kNodeValues, 2 * max_count)); 2458 // Transfer the values from the old root to the new root. 2459 node_type *old_root = root(); 2460 node_type *new_root = iter.node; 2461 new_root->transfer_n(old_root->count(), new_root->start(), 2462 old_root->start(), old_root, alloc); 2463 new_root->set_finish(old_root->finish()); 2464 old_root->set_finish(old_root->start()); 2465 node_type::clear_and_delete(old_root, alloc); 2466 mutable_root() = rightmost_ = new_root; 2467 } else { 2468 rebalance_or_split(&iter); 2469 } 2470 } 2471 iter.node->emplace_value(iter.position, alloc, std::forward<Args>(args)...); 2472 ++size_; 2473 return iter; 2474 } 2475 2476 template <typename P> 2477 template <typename K> 2478 inline auto btree<P>::internal_locate(const K &key) const 2479 -> SearchResult<iterator, is_key_compare_to::value> { 2480 iterator iter(const_cast<node_type *>(root())); 2481 for (;;) { 2482 SearchResult<int, is_key_compare_to::value> res = 2483 iter.node->lower_bound(key, key_comp()); 2484 iter.position = res.value; 2485 if (res.IsEq()) { 2486 return {iter, MatchKind::kEq}; 2487 } 2488 // Note: in the non-key-compare-to case, we don't need to walk all the way 2489 // down the tree if the keys are equal, but determining equality would 2490 // require doing an extra comparison on each node on the way down, and we 2491 // will need to go all the way to the leaf node in the expected case. 2492 if (iter.node->leaf()) { 2493 break; 2494 } 2495 iter.node = iter.node->child(iter.position); 2496 } 2497 // Note: in the non-key-compare-to case, the key may actually be equivalent 2498 // here (and the MatchKind::kNe is ignored). 2499 return {iter, MatchKind::kNe}; 2500 } 2501 2502 template <typename P> 2503 template <typename K> 2504 auto btree<P>::internal_lower_bound(const K &key) const 2505 -> SearchResult<iterator, is_key_compare_to::value> { 2506 iterator iter(const_cast<node_type *>(root())); 2507 SearchResult<int, is_key_compare_to::value> res; 2508 bool seen_eq = false; 2509 for (;;) { 2510 res = iter.node->lower_bound(key, key_comp()); 2511 iter.position = res.value; 2512 // TODO(ezb): we should be able to terminate early on IsEq() if there can't 2513 // be multiple equivalent keys in container for this lookup type. 2514 if (iter.node->leaf()) { 2515 break; 2516 } 2517 seen_eq = seen_eq || res.IsEq(); 2518 iter.node = iter.node->child(iter.position); 2519 } 2520 if (res.IsEq()) return {iter, MatchKind::kEq}; 2521 return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe}; 2522 } 2523 2524 template <typename P> 2525 template <typename K> 2526 auto btree<P>::internal_upper_bound(const K &key) const -> iterator { 2527 iterator iter(const_cast<node_type *>(root())); 2528 for (;;) { 2529 iter.position = iter.node->upper_bound(key, key_comp()); 2530 if (iter.node->leaf()) { 2531 break; 2532 } 2533 iter.node = iter.node->child(iter.position); 2534 } 2535 return internal_last(iter); 2536 } 2537 2538 template <typename P> 2539 template <typename K> 2540 auto btree<P>::internal_find(const K &key) const -> iterator { 2541 SearchResult<iterator, is_key_compare_to::value> res = internal_locate(key); 2542 if (res.HasMatch()) { 2543 if (res.IsEq()) { 2544 return res.value; 2545 } 2546 } else { 2547 const iterator iter = internal_last(res.value); 2548 if (iter.node != nullptr && !compare_keys(key, iter.key())) { 2549 return iter; 2550 } 2551 } 2552 return {nullptr, 0}; 2553 } 2554 2555 template <typename P> 2556 int btree<P>::internal_verify(const node_type *node, const key_type *lo, 2557 const key_type *hi) const { 2558 assert(node->count() > 0); 2559 assert(node->count() <= node->max_count()); 2560 if (lo) { 2561 assert(!compare_keys(node->key(node->start()), *lo)); 2562 } 2563 if (hi) { 2564 assert(!compare_keys(*hi, node->key(node->finish() - 1))); 2565 } 2566 for (int i = node->start() + 1; i < node->finish(); ++i) { 2567 assert(!compare_keys(node->key(i), node->key(i - 1))); 2568 } 2569 int count = node->count(); 2570 if (!node->leaf()) { 2571 for (int i = node->start(); i <= node->finish(); ++i) { 2572 assert(node->child(i) != nullptr); 2573 assert(node->child(i)->parent() == node); 2574 assert(node->child(i)->position() == i); 2575 count += internal_verify(node->child(i), 2576 i == node->start() ? lo : &node->key(i - 1), 2577 i == node->finish() ? hi : &node->key(i)); 2578 } 2579 } 2580 return count; 2581 } 2582 2583 } // namespace container_internal 2584 ABSL_NAMESPACE_END 2585 } // namespace absl 2586 2587 #endif // ABSL_CONTAINER_INTERNAL_BTREE_H_ 2588