about summary refs log tree commit diff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/btree_test.cc32
-rw-r--r--absl/container/internal/btree.h79
-rw-r--r--absl/container/internal/btree_container.h6
3 files changed, 44 insertions, 73 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index af8ee00b3524..9edf38f9d0ac 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -180,9 +180,7 @@ class base_checker {
   const_iterator find(const key_type &key) const {
     return iter_check(tree_.find(key), checker_.find(key));
   }
-  bool contains(const key_type &key) const {
-    return find(key) != end();
-  }
+  bool contains(const key_type &key) const { return find(key) != end(); }
   size_type count(const key_type &key) const {
     size_type res = checker_.count(key);
     EXPECT_EQ(res, tree_.count(key));
@@ -240,8 +238,10 @@ class base_checker {
         ++checker_end;
       }
     }
-    checker_.erase(checker_begin, checker_end);
-    tree_.erase(begin, end);
+    const auto checker_ret = checker_.erase(checker_begin, checker_end);
+    const auto tree_ret = tree_.erase(begin, end);
+    EXPECT_EQ(std::distance(checker_.begin(), checker_ret),
+              std::distance(tree_.begin(), tree_ret));
     EXPECT_EQ(tree_.size(), checker_.size());
     EXPECT_EQ(tree_.size(), size - count);
   }
@@ -326,7 +326,7 @@ class unique_checker : public base_checker<TreeType, CheckerType> {
   unique_checker(const unique_checker &x) : super_type(x) {}
   template <class InputIterator>
   unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
-  unique_checker& operator=(const unique_checker&) = default;
+  unique_checker &operator=(const unique_checker &) = default;
 
   // Insertion routines.
   std::pair<iterator, bool> insert(const value_type &x) {
@@ -374,7 +374,7 @@ class multi_checker : public base_checker<TreeType, CheckerType> {
   multi_checker(const multi_checker &x) : super_type(x) {}
   template <class InputIterator>
   multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
-  multi_checker& operator=(const multi_checker&) = default;
+  multi_checker &operator=(const multi_checker &) = default;
 
   // Insertion routines.
   iterator insert(const value_type &x) {
@@ -868,7 +868,7 @@ struct CompareIntToString {
 
 struct NonTransparentCompare {
   template <typename T, typename U>
-  bool operator()(const T& t, const U& u) const {
+  bool operator()(const T &t, const U &u) const {
     // Treating all comparators as transparent can cause inefficiencies (see
     // N3657 C++ proposal). Test that for comparators without 'is_transparent'
     // alias (like this one), we do not attempt heterogeneous lookup.
@@ -1005,21 +1005,15 @@ class StringLike {
  public:
   StringLike() = default;
 
-  StringLike(const char* s) : s_(s) {  // NOLINT
+  StringLike(const char *s) : s_(s) {  // NOLINT
     ++constructor_calls_;
   }
 
-  bool operator<(const StringLike& a) const {
-    return s_ < a.s_;
-  }
+  bool operator<(const StringLike &a) const { return s_ < a.s_; }
 
-  static void clear_constructor_call_count() {
-    constructor_calls_ = 0;
-  }
+  static void clear_constructor_call_count() { constructor_calls_ = 0; }
 
-  static int constructor_calls() {
-    return constructor_calls_;
-  }
+  static int constructor_calls() { return constructor_calls_; }
 
  private:
   static int constructor_calls_;
@@ -1476,7 +1470,7 @@ struct NoDefaultCtor {
   int num;
   explicit NoDefaultCtor(int i) : num(i) {}
 
-  friend bool operator<(const NoDefaultCtor& a, const NoDefaultCtor& b) {
+  friend bool operator<(const NoDefaultCtor &a, const NoDefaultCtor &b) {
     return a.num < b.num;
   }
 };
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index aef861dc6dc6..707e9f0e48bf 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -882,18 +882,14 @@ struct btree_iterator {
   }
 
   // Accessors for the key/value the iterator is pointing at.
-  reference operator*() const {
-    return node->value(position);
-  }
-  pointer operator->() const {
-    return &node->value(position);
-  }
+  reference operator*() const { return node->value(position); }
+  pointer operator->() const { return &node->value(position); }
 
-  btree_iterator& operator++() {
+  btree_iterator &operator++() {
     increment();
     return *this;
   }
-  btree_iterator& operator--() {
+  btree_iterator &operator--() {
     decrement();
     return *this;
   }
@@ -961,7 +957,7 @@ class btree {
 
   static node_type *EmptyNode() {
 #ifdef _MSC_VER
-    static EmptyNodeType* empty_node = new EmptyNodeType;
+    static EmptyNodeType *empty_node = new EmptyNodeType;
     // This assert fails on some other construction methods.
     assert(empty_node->parent == empty_node);
     return empty_node;
@@ -980,12 +976,9 @@ class btree {
   struct node_stats {
     using size_type = typename Params::size_type;
 
-    node_stats(size_type l, size_type i)
-        : leaf_nodes(l),
-          internal_nodes(i) {
-    }
+    node_stats(size_type l, size_type i) : leaf_nodes(l), internal_nodes(i) {}
 
-    node_stats& operator+=(const node_stats &x) {
+    node_stats &operator+=(const node_stats &x) {
       leaf_nodes += x.leaf_nodes;
       internal_nodes += x.internal_nodes;
       return *this;
@@ -1054,25 +1047,17 @@ class btree {
   btree &operator=(const btree &x);
   btree &operator=(btree &&x) noexcept;
 
-  iterator begin() {
-    return iterator(leftmost(), 0);
-  }
-  const_iterator begin() const {
-    return const_iterator(leftmost(), 0);
-  }
+  iterator begin() { return iterator(leftmost(), 0); }
+  const_iterator begin() const { return const_iterator(leftmost(), 0); }
   iterator end() { return iterator(rightmost_, rightmost_->count()); }
   const_iterator end() const {
     return const_iterator(rightmost_, rightmost_->count());
   }
-  reverse_iterator rbegin() {
-    return reverse_iterator(end());
-  }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
   const_reverse_iterator rbegin() const {
     return const_reverse_iterator(end());
   }
-  reverse_iterator rend() {
-    return reverse_iterator(begin());
-  }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
   const_reverse_iterator rend() const {
     return const_reverse_iterator(begin());
   }
@@ -1160,7 +1145,7 @@ class btree {
 
   // Erases range. Returns the number of keys erased and an iterator pointing
   // to the element after the last erased element.
-  std::pair<size_type, iterator> erase(iterator begin, iterator end);
+  std::pair<size_type, iterator> erase_range(iterator begin, iterator end);
 
   // Erases the specified key from the btree. Returns 1 if an element was
   // erased and 0 otherwise.
@@ -1242,9 +1227,7 @@ class btree {
   }
 
   // The number of internal, leaf and total nodes used by the btree.
-  size_type leaf_nodes() const {
-    return internal_stats(root()).leaf_nodes;
-  }
+  size_type leaf_nodes() const { return internal_stats(root()).leaf_nodes; }
   size_type internal_nodes() const {
     return internal_stats(root()).internal_nodes;
   }
@@ -1257,11 +1240,9 @@ class btree {
   size_type bytes_used() const {
     node_stats stats = internal_stats(root());
     if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) {
-      return sizeof(*this) +
-             node_type::LeafSize(root()->max_count());
+      return sizeof(*this) + node_type::LeafSize(root()->max_count());
     } else {
-      return sizeof(*this) +
-             stats.leaf_nodes * node_type::LeafSize() +
+      return sizeof(*this) + stats.leaf_nodes * node_type::LeafSize() +
              stats.internal_nodes * node_type::InternalSize();
     }
   }
@@ -1294,9 +1275,7 @@ class btree {
   }
 
   // The allocator used by the btree.
-  allocator_type get_allocator() const {
-    return allocator();
-  }
+  allocator_type get_allocator() const { return allocator(); }
 
  private:
   // Internal accessor routines.
@@ -1326,11 +1305,11 @@ class btree {
   }
 
   // Node creation/deletion routines.
-  node_type* new_internal_node(node_type *parent) {
+  node_type *new_internal_node(node_type *parent) {
     node_type *p = allocate(node_type::InternalSize());
     return node_type::init_internal(p, parent);
   }
-  node_type* new_leaf_node(node_type *parent) {
+  node_type *new_leaf_node(node_type *parent) {
     node_type *p = allocate(node_type::LeafSize());
     return node_type::init_leaf(p, parent, kNodeValues);
   }
@@ -1431,8 +1410,8 @@ class btree {
   void internal_clear(node_type *node);
 
   // Verifies the tree structure of node.
-  int internal_verify(const node_type *node,
-                      const key_type *lo, const key_type *hi) const;
+  int 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.
@@ -2098,7 +2077,7 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
 }
 
 template <typename P>
-auto btree<P>::erase(iterator begin, iterator end)
+auto btree<P>::erase_range(iterator begin, iterator end)
     -> std::pair<size_type, iterator> {
   difference_type count = std::distance(begin, end);
   assert(count >= 0);
@@ -2198,7 +2177,7 @@ auto btree<P>::erase_multi(const K &key) -> size_type {
   }
   // Delete all of the keys between begin and upper_bound(key).
   const iterator end = internal_end(internal_upper_bound(key));
-  return erase(begin, end).first;
+  return erase_range(begin, end).first;
 }
 
 template <typename P>
@@ -2379,8 +2358,7 @@ bool btree<P>::try_merge_or_rebalance(iterator *iter) {
     // empty. This is a small optimization for the common pattern of deleting
     // from the front of the tree.
     if ((right->count() > kMinNodeValues) &&
-        ((iter->node->count() == 0) ||
-         (iter->position > 0))) {
+        ((iter->node->count() == 0) || (iter->position > 0))) {
       int to_move = (right->count() - iter->node->count()) / 2;
       to_move = (std::min)(to_move, right->count() - 1);
       iter->node->rebalance_right_to_left(to_move, right, mutable_allocator());
@@ -2578,8 +2556,8 @@ void btree<P>::internal_clear(node_type *node) {
 }
 
 template <typename P>
-int btree<P>::internal_verify(
-    const node_type *node, const key_type *lo, const key_type *hi) const {
+int btree<P>::internal_verify(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) {
@@ -2597,10 +2575,9 @@ int btree<P>::internal_verify(
       assert(node->child(i) != nullptr);
       assert(node->child(i)->parent() == node);
       assert(node->child(i)->position() == i);
-      count += internal_verify(
-          node->child(i),
-          (i == 0) ? lo : &node->key(i - 1),
-          (i == node->count()) ? hi : &node->key(i));
+      count +=
+          internal_verify(node->child(i), (i == 0) ? lo : &node->key(i - 1),
+                          (i == node->count()) ? hi : &node->key(i));
     }
   }
   return count;
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index 3e6ff4b892f1..f2e4c3a5358b 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -136,7 +136,7 @@ class btree_container {
   iterator erase(const_iterator iter) { return tree_.erase(iterator(iter)); }
   iterator erase(iterator iter) { return tree_.erase(iter); }
   iterator erase(const_iterator first, const_iterator last) {
-    return tree_.erase(iterator(first), iterator(last)).second;
+    return tree_.erase_range(iterator(first), iterator(last)).second;
   }
 
   // Extract routines.
@@ -465,7 +465,7 @@ class btree_map_container : public btree_set_container<Tree> {
     // and then using `k` unsequenced. This is safe because the move is into a
     // forwarding reference and insert_unique guarantees that `key` is never
     // referenced after consuming `args`.
-    const key_type& key_ref = k;
+    const key_type &key_ref = k;
     return this->tree_.insert_unique(
         key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)),
         std::forward_as_tuple(std::forward<Args>(args)...));
@@ -485,7 +485,7 @@ class btree_map_container : public btree_set_container<Tree> {
     // and then using `k` unsequenced. This is safe because the move is into a
     // forwarding reference and insert_hint_unique guarantees that `key` is
     // never referenced after consuming `args`.
-    const key_type& key_ref = k;
+    const key_type &key_ref = k;
     return this->tree_
         .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct,
                             std::forward_as_tuple(std::move(k)),