From b92f23a08ac620694b1db3c006b3445d5662b154 Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Tue, 13 Sep 2022 10:36:22 -0700 Subject: Apply clang-format to btree.h. PiperOrigin-RevId: 474060540 Change-Id: Ie0f24dfa6ec724eaa9eca82de5f73bbd8d622e38 --- absl/container/internal/btree.h | 133 +++++++++++++++++----------------------- 1 file changed, 55 insertions(+), 78 deletions(-) diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 116c62f8..bdf2446e 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -100,7 +100,7 @@ struct StringBtreeDefaultLess { StringBtreeDefaultLess() = default; // Compatibility constructor. - StringBtreeDefaultLess(std::less) {} // NOLINT + StringBtreeDefaultLess(std::less) {} // NOLINT StringBtreeDefaultLess(std::less) {} // NOLINT // Allow converting to std::less for use in key_comp()/value_comp(). @@ -132,7 +132,7 @@ struct StringBtreeDefaultGreater { StringBtreeDefaultGreater() = default; - StringBtreeDefaultGreater(std::greater) {} // NOLINT + StringBtreeDefaultGreater(std::greater) {} // NOLINT StringBtreeDefaultGreater(std::greater) {} // NOLINT // Allow converting to std::greater for use in key_comp()/value_comp(). @@ -376,8 +376,7 @@ struct common_params { std::is_same::value || std::is_same::value; static constexpr bool kIsKeyCompareTransparent = - IsTransparent::value || - kIsKeyCompareStringAdapted; + IsTransparent::value || kIsKeyCompareStringAdapted; static constexpr bool kEnableGenerations = #ifdef ABSL_BTREE_ENABLE_GENERATIONS true; @@ -430,8 +429,7 @@ struct common_params { // Upper bound for the available space for slots. This is largest for leaf // nodes, which have overhead of at least a pointer + 4 bytes (for storing // 3 field_types and an enum). - kNodeSlotSpace = - TargetNodeSize - /*minimum overhead=*/(sizeof(void *) + 4), + kNodeSlotSpace = TargetNodeSize - /*minimum overhead=*/(sizeof(void *) + 4), }; // This is an integral type large enough to hold as many slots as will fit a @@ -450,7 +448,7 @@ struct common_params { return slot_policy::element(slot); } template - static void construct(Alloc *alloc, slot_type *slot, Args &&... args) { + static void construct(Alloc *alloc, slot_type *slot, Args &&...args) { slot_policy::construct(alloc, slot, std::forward(args)...); } static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { @@ -628,10 +626,10 @@ class btree_node { constexpr static size_type NodeTargetSlots(const size_type begin, const size_type end) { return begin == end ? begin - : SizeWithNSlots((begin + end) / 2 + 1) > - params_type::kTargetNodeSize - ? NodeTargetSlots(begin, (begin + end) / 2) - : NodeTargetSlots((begin + end) / 2 + 1, end); + : SizeWithNSlots((begin + end) / 2 + 1) > + params_type::kTargetNodeSize + ? NodeTargetSlots(begin, (begin + end) / 2) + : NodeTargetSlots((begin + end) / 2 + 1, end); } constexpr static size_type kTargetNodeSize = params_type::kTargetNodeSize; @@ -693,10 +691,10 @@ class btree_node { } void set_parent(btree_node *p) { *GetField<0>() = p; } field_type &mutable_finish() { return GetField<2>()[2]; } - slot_type* slot(size_type i) { return &GetField<3>()[i]; } + slot_type *slot(size_type i) { return &GetField<3>()[i]; } slot_type *start_slot() { return slot(start()); } slot_type *finish_slot() { return slot(finish()); } - const slot_type* slot(size_type i) const { return &GetField<3>()[i]; } + const slot_type *slot(size_type i) const { return &GetField<3>()[i]; } void set_position(field_type v) { GetField<2>()[0] = v; } void set_start(field_type v) { GetField<2>()[1] = v; } void set_finish(field_type v) { GetField<2>()[2] = v; } @@ -773,25 +771,25 @@ class btree_node { } // Getters for the key/value at position i in the node. - const key_type& key(size_type i) const { return params_type::key(slot(i)); } + const key_type &key(size_type i) const { return params_type::key(slot(i)); } reference value(size_type i) { return params_type::element(slot(i)); } const_reference value(size_type i) const { return params_type::element(slot(i)); } // Getters/setter for the child at position i in the node. - btree_node* child(field_type i) const { return GetField<4>()[i]; } + btree_node *child(field_type i) const { return GetField<4>()[i]; } btree_node *start_child() const { return child(start()); } - btree_node*& mutable_child(field_type i) { return GetField<4>()[i]; } + btree_node *&mutable_child(field_type i) { return GetField<4>()[i]; } void clear_child(field_type i) { absl::container_internal::SanitizerPoisonObject(&mutable_child(i)); } - void set_child(field_type i, btree_node* c) { + void set_child(field_type i, btree_node *c) { absl::container_internal::SanitizerUnpoisonObject(&mutable_child(i)); mutable_child(i) = c; c->set_position(i); } - void init_child(field_type i, btree_node* c) { + void init_child(field_type i, btree_node *c) { set_child(i, c); c->set_parent(this); } @@ -799,14 +797,13 @@ class btree_node { // Returns the position of the first value whose key is not less than k. template SearchResult lower_bound( - const K& k, - const key_compare& comp) const { + const K &k, const key_compare &comp) const { return use_linear_search::value ? linear_search(k, comp) : binary_search(k, comp); } // Returns the position of the first value whose key is greater than k. template - size_type upper_bound(const K& k, const key_compare& comp) const { + size_type upper_bound(const K &k, const key_compare &comp) const { auto upper_compare = upper_bound_adapter(comp); return use_linear_search::value ? linear_search(k, upper_compare).value : binary_search(k, upper_compare).value; @@ -814,14 +811,14 @@ class btree_node { template SearchResult::value> - linear_search(const K& k, const Compare& comp) const { + linear_search(const K &k, const Compare &comp) const { return linear_search_impl(k, start(), finish(), comp, btree_is_key_compare_to()); } template SearchResult::value> - binary_search(const K& k, const Compare& comp) const { + binary_search(const K &k, const Compare &comp) const { return binary_search_impl(k, start(), finish(), comp, btree_is_key_compare_to()); } @@ -830,10 +827,7 @@ class btree_node { // linear search performed using plain compare. template SearchResult linear_search_impl( - const K& k, - size_type s, - const size_type e, - const Compare& comp, + const K &k, size_type s, const size_type e, const Compare &comp, std::false_type /* IsCompareTo */) const { while (s < e) { if (!comp(key(s), k)) { @@ -848,10 +842,7 @@ class btree_node { // linear search performed using compare-to. template SearchResult linear_search_impl( - const K& k, - size_type s, - const size_type e, - const Compare& comp, + const K &k, size_type s, const size_type e, const Compare &comp, std::true_type /* IsCompareTo */) const { while (s < e) { const absl::weak_ordering c = comp(key(s), k); @@ -869,10 +860,7 @@ class btree_node { // binary search performed using plain compare. template SearchResult binary_search_impl( - const K& k, - size_type s, - size_type e, - const Compare& comp, + const K &k, size_type s, size_type e, const Compare &comp, std::false_type /* IsCompareTo */) const { while (s != e) { const size_type mid = (s + e) >> 1; @@ -889,10 +877,7 @@ class btree_node { // binary search performed using compare-to. template SearchResult binary_search_impl( - const K& k, - size_type s, - size_type e, - const CompareTo& comp, + const K &k, size_type s, size_type e, const CompareTo &comp, std::true_type /* IsCompareTo */) const { if (params_type::template can_have_multiple_equivalent_keys()) { MatchKind exact_match = MatchKind::kNe; @@ -931,7 +916,7 @@ class btree_node { // Emplaces a value at position i, shifting all existing values and // children at positions >= i to the right by 1. template - void emplace_value(field_type i, allocator_type* alloc, Args&&... args); + void emplace_value(field_type i, allocator_type *alloc, Args &&...args); // Removes the values at positions [i, i + to_erase), shifting all existing // values and children after that range to the left by to_erase. Clears all @@ -939,12 +924,10 @@ class btree_node { void remove_values(field_type i, field_type to_erase, allocator_type *alloc); // Rebalances a node with its right sibling. - void rebalance_right_to_left(field_type to_move, - btree_node* right, - allocator_type* alloc); - void rebalance_left_to_right(field_type to_move, - btree_node* right, - allocator_type* alloc); + void rebalance_right_to_left(field_type to_move, btree_node *right, + allocator_type *alloc); + void rebalance_left_to_right(field_type to_move, btree_node *right, + allocator_type *alloc); // Splits a node, moving a portion of the node's values to its right sibling. void split(int insert_position, btree_node *dest, allocator_type *alloc); @@ -954,7 +937,7 @@ class btree_node { void merge(btree_node *src, allocator_type *alloc); // Node allocation/deletion routines. - void init_leaf(field_type max_count, btree_node* parent) { + void init_leaf(field_type max_count, btree_node *parent) { set_generation(0); set_parent(parent); set_position(0); @@ -983,7 +966,7 @@ class btree_node { private: template - void value_init(const field_type i, allocator_type *alloc, Args &&... args) { + void value_init(const field_type i, allocator_type *alloc, Args &&...args) { next_generation(); absl::container_internal::SanitizerUnpoisonObject(slot(i)); params_type::construct(alloc, slot(i), std::forward(args)...); @@ -1212,7 +1195,7 @@ class btree_iterator { #endif } - const key_type& key() const { + const key_type &key() const { return node_->key(static_cast(position_)); } decltype(std::declval()->slot(0)) slot() { @@ -1430,7 +1413,7 @@ class btree { // Requirement: if `key` already exists in the btree, does not consume `args`. // Requirement: `key` is never referenced after consuming `args`. template - std::pair insert_unique(const K &key, Args &&... args); + std::pair insert_unique(const K &key, Args &&...args); // Inserts with hint. Checks to see if the value should be placed immediately // before `position` in the tree. If so, then the insertion will take @@ -1439,9 +1422,8 @@ class btree { // Requirement: if `key` already exists in the btree, does not consume `args`. // Requirement: `key` is never referenced after consuming `args`. template - std::pair insert_hint_unique(iterator position, - const K &key, - Args &&... args); + std::pair insert_hint_unique(iterator position, const K &key, + Args &&...args); // Insert a range of values into the btree. // Note: the first overload avoids constructing a value_type if the key @@ -1568,8 +1550,7 @@ class btree { static double average_bytes_per_value() { // The expected number of values per node with random insertion order is the // average of the maximum and minimum numbers of values per node. - const double expected_values_per_node = - (kNodeSlots + kMinNodeValues) / 2.0; + const double expected_values_per_node = (kNodeSlots + kMinNodeValues) / 2.0; return node_type::LeafSize() / expected_values_per_node; } @@ -1625,7 +1606,7 @@ class btree { // Allocates a correctly aligned node of at least size bytes using the // allocator. - node_type* allocate(size_type size) { + node_type *allocate(size_type size) { return reinterpret_cast( absl::container_internal::Allocate( mutable_allocator(), size)); @@ -1642,7 +1623,7 @@ class btree { n->init_leaf(kNodeSlots, parent); return n; } - node_type* new_leaf_root_node(field_type max_count) { + node_type *new_leaf_root_node(field_type max_count) { node_type *n = allocate(node_type::LeafSize(max_count)); n->init_leaf(max_count, /*parent=*/n); return n; @@ -1677,7 +1658,7 @@ class btree { // Emplaces a value into the btree immediately before iter. Requires that // key(v) <= iter.key() and (--iter).key() <= key(v). template - iterator internal_emplace(iterator iter, Args &&... args); + iterator internal_emplace(iterator iter, Args &&...args); // Returns an iterator pointing to the first value >= the value "iter" is // pointing at. Note that "iter" might be pointing to an invalid location such @@ -1710,9 +1691,8 @@ class btree { iterator internal_find(const K &key) const; // Verifies the tree structure of node. - size_type internal_verify(const node_type* node, - const key_type* lo, - const key_type* hi) const; + size_type internal_verify(const node_type *node, const key_type *lo, + const key_type *hi) const; node_stats internal_stats(const node_type *node) const { // The root can be a static empty node. @@ -1747,8 +1727,8 @@ class btree { template template inline void btree_node

::emplace_value(const field_type i, - allocator_type* alloc, - Args&&... args) { + allocator_type *alloc, + Args &&...args) { assert(i >= start()); assert(i <= finish()); // Shift old values to create space for new value and then construct it in @@ -1794,8 +1774,8 @@ inline void btree_node

::remove_values(const field_type i, template void btree_node

::rebalance_right_to_left(field_type to_move, - btree_node* right, - allocator_type* alloc) { + btree_node *right, + allocator_type *alloc) { assert(parent() == right->parent()); assert(position() + 1 == right->position()); assert(right->count() >= count()); @@ -1834,8 +1814,8 @@ void btree_node

::rebalance_right_to_left(field_type to_move, template void btree_node

::rebalance_left_to_right(field_type to_move, - btree_node* right, - allocator_type* alloc) { + btree_node *right, + allocator_type *alloc) { assert(parent() == right->parent()); assert(position() + 1 == right->position()); assert(count() >= right->count()); @@ -2157,7 +2137,7 @@ auto btree

::equal_range(const K &key) -> std::pair { template template -auto btree

::insert_unique(const K &key, Args &&... args) +auto btree

::insert_unique(const K &key, Args &&...args) -> std::pair { if (empty()) { mutable_root() = mutable_rightmost() = new_leaf_root_node(1); @@ -2184,7 +2164,7 @@ auto btree

::insert_unique(const K &key, Args &&... args) template template inline auto btree

::insert_hint_unique(iterator position, const K &key, - Args &&... args) + Args &&...args) -> std::pair { if (!empty()) { if (position == end() || compare_keys(key, position.key())) { @@ -2686,7 +2666,7 @@ inline IterType btree

::internal_last(IterType iter) { template template -inline auto btree

::internal_emplace(iterator iter, Args &&... args) +inline auto btree

::internal_emplace(iterator iter, Args &&...args) -> iterator { if (iter.node_->is_internal()) { // We can't insert on an internal node. Instead, we'll insert after the @@ -2702,9 +2682,8 @@ inline auto btree

::internal_emplace(iterator iter, Args &&... args) // Insertion into the root where the root is smaller than the full node // size. Simply grow the size of the root node. assert(iter.node_ == root()); - iter.node_ = new_leaf_root_node( - static_cast((std::min)(static_cast(kNodeSlots), - 2 * max_count))); + iter.node_ = new_leaf_root_node(static_cast( + (std::min)(static_cast(kNodeSlots), 2 * max_count))); // Transfer the values from the old root to the new root. node_type *old_root = root(); node_type *new_root = iter.node_; @@ -2810,9 +2789,7 @@ auto btree

::internal_find(const K &key) const -> iterator { template typename btree

::size_type btree

::internal_verify( - const node_type* node, - const key_type* lo, - const key_type* hi) const { + const node_type *node, const key_type *lo, const key_type *hi) const { assert(node->count() > 0); assert(node->count() <= node->max_count()); if (lo) { @@ -2840,8 +2817,8 @@ typename btree

::size_type btree

::internal_verify( struct btree_access { template - static auto erase_if(BtreeContainer &container, Pred pred) - -> typename BtreeContainer::size_type { + static auto erase_if(BtreeContainer &container, Pred pred) -> + typename BtreeContainer::size_type { const auto initial_size = container.size(); auto &tree = container.tree_; auto *alloc = tree.mutable_allocator(); -- cgit v1.2.3