diff options
author | 2020-01-31 10:09:12 -0800 | |
---|---|---|
committer | 2020-01-31 17:10:19 -0500 | |
commit | 0f86336b6939ea673cc1cbe29189286cae67d63a (patch) | |
tree | af3e02fa702f5ef5a82c2fc22f4ce52707c5c047 /absl/container/internal/btree.h | |
parent | c512f118dde6ffd51cb7d8ac8804bbaf4d266c3a (diff) |
Export of internal Abseil changes
--
0b924fe4e9871200792617329d32beb8356daa9b by Derek Mauro <dmauro@google.com>:
Use less threads in the GetTID() test to avoid test timeouts
PiperOrigin-RevId: 292566826
--
0b519c4fd48d61b7c4ea94ed6a6be6e981b9c51a by Abseil Team <absl-team@google.com>:
Internal change.
PiperOrigin-RevId: 292563778
--
3204f6e07bcc2b5e9098d45f1a20998f25ab808e by Abseil Team <absl-team@google.com>:
Internal change.
PiperOrigin-RevId: 292550551
--
09fbbe73833478d3f26f3e33c8291b991fd3be51 by Derek Mauro <dmauro@google.com>:
Add a debug bounds-check to absl::string_view::operator[]
string_view accesses that are out-of-bounds are undefined behavior:
https://en.cppreference.com/w/cpp/string/basic_string_view/operator_at
This change causes code to abort in debug mode, indicating a bug and
possibly a security issue like a buffer overflow. Code broken by this
change should be investigated.
PiperOrigin-RevId: 292544735
--
bf2c19cb45682628f963d4067c0cd6deed7e656d by Derek Mauro <dmauro@google.com>:
Add debug assertions to absl::string_view::front and absl::string_view::back
Calling front() or back() on an empty string_view is undefined behavior. This
assertion is to help catch broken code.
https://en.cppreference.com/w/cpp/string/basic_string_view/front
https://en.cppreference.com/w/cpp/string/basic_string_view/back
PiperOrigin-RevId: 292453255
--
47f573679b322f8c0fd2cb037cc87e7bc822ac6b by Xiaoyi Zhang <zhangxy@google.com>:
Release functional/CMakeList.txt.
PiperOrigin-RevId: 292417025
GitOrigin-RevId: 0b924fe4e9871200792617329d32beb8356daa9b
Change-Id: Ie6980fb1ac351d72a2ce4468f25bd31db396f88a
Diffstat (limited to 'absl/container/internal/btree.h')
-rw-r--r-- | absl/container/internal/btree.h | 79 |
1 files changed, 28 insertions, 51 deletions
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index aef861dc..707e9f0e 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; |