diff options
| -rw-r--r-- | CMakeLists.txt | 16 | ||||
| -rw-r--r-- | absl/container/internal/btree.h | 85 |
2 files changed, 38 insertions, 63 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 54ce4994..bc195e04 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -22,16 +22,24 @@ cmake_minimum_required(VERSION 3.5) # Compiler id for Apple Clang is now AppleClang. -cmake_policy(SET CMP0025 NEW) +if (POLICY CMP0025) + cmake_policy(SET CMP0025 NEW) +endif (POLICY CMP0025) # if command can use IN_LIST -cmake_policy(SET CMP0057 NEW) +if (POLICY CMP0057) + cmake_policy(SET CMP0057 NEW) +endif (POLICY CMP0057) # Project version variables are the empty string if version is unspecified -cmake_policy(SET CMP0048 NEW) +if (POLICY CMP0048) + cmake_policy(SET CMP0048 NEW) +endif (POLICY CMP0048) # option() honor variables -cmake_policy(SET CMP0077 NEW) +if (POLICY CMP0077) + cmake_policy(SET CMP0077 NEW) +endif (POLICY CMP0077) project(absl CXX) diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 188631d1..047055a2 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -785,13 +785,28 @@ class btree_node { &mutable_child(start()), (kNodeValues + 1) * sizeof(btree_node *)); } - static void deallocate(const size_type size, btree_node *node, - allocator_type *alloc) { - absl::container_internal::Deallocate<Alignment()>(alloc, node, size); - } - // Deletes a node and all of its children. - static void clear_and_delete(btree_node *node, allocator_type *alloc); + // TODO(ezb): don't use recursion here to avoid potential stack overflows. + static void clear_and_delete(btree_node *node, allocator_type *alloc) { + const field_type start = node->start(); + const field_type finish = node->finish(); + for (field_type i = start; i < finish; ++i) { + node->value_destroy(i, alloc); + } + if (node->leaf()) { + absl::container_internal::Deallocate<Alignment()>( + alloc, node, LeafSize(node->max_count())); + } else { + // If the node is empty, then there are no children so don't try clearing. + if (start < finish) { + for (field_type i = start; i <= finish; ++i) { + clear_and_delete(node->child(i), alloc); + } + } + absl::container_internal::Deallocate<Alignment()>(alloc, node, + InternalSize()); + } + } public: // Exposed only for tests. @@ -801,21 +816,14 @@ class btree_node { private: template <typename... Args> - void value_init(const field_type i, allocator_type *alloc, Args &&... args) { + void value_init(const size_type i, allocator_type *alloc, Args &&... args) { absl::container_internal::SanitizerUnpoisonObject(slot(i)); params_type::construct(alloc, slot(i), std::forward<Args>(args)...); } - void value_destroy(const field_type i, allocator_type *alloc) { + void value_destroy(const size_type i, allocator_type *alloc) { params_type::destroy(alloc, slot(i)); absl::container_internal::SanitizerPoisonObject(slot(i)); } - void value_destroy_n(const field_type i, const field_type n, - allocator_type *alloc) { - for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) { - params_type::destroy(alloc, s); - absl::container_internal::SanitizerPoisonObject(s); - } - } // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`. void transfer(const size_type dest_i, const size_type src_i, @@ -1559,9 +1567,11 @@ inline void btree_node<P>::remove_values(const field_type i, const field_type to_erase, allocator_type *alloc) { // Transfer values after the removed range into their new places. - value_destroy_n(i, to_erase, alloc); const field_type orig_finish = finish(); const field_type src_i = i + to_erase; + for (field_type j = i; j < src_i; ++j) { + value_destroy(j, alloc); + } transfer_n(orig_finish - src_i, i, src_i, this, alloc); if (!leaf()) { @@ -1731,49 +1741,6 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) { parent()->remove_values(position(), /*to_erase=*/1, alloc); } -template <typename P> -void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) { - if (node->leaf()) { - node->value_destroy_n(node->start(), node->count(), alloc); - deallocate(LeafSize(node->max_count()), node, alloc); - return; - } - if (node->count() == 0) { - deallocate(InternalSize(), node, alloc); - return; - } - - // The parent of the root of the subtree we are deleting. - btree_node *delete_root_parent = node->parent(); - - // Navigate to the leftmost leaf under node, and then delete upwards. - while (!node->leaf()) node = node->start_child(); - field_type pos = node->position(); - btree_node *parent = node->parent(); - do { - // In each iteration of this loop, we delete one leaf node and go right. - for (; pos <= parent->finish(); ++pos) { - node = parent->child(pos); - if (!node->leaf()) { - // Navigate to the leftmost leaf under node. - while (!node->leaf()) node = node->start_child(); - pos = node->position(); - parent = node->parent(); - } - node->value_destroy_n(node->start(), node->count(), alloc); - deallocate(LeafSize(node->max_count()), node, alloc); - } - // If we've deleted all children of parent, then delete parent and go up. - for (; parent != delete_root_parent && pos > parent->finish(); ++pos) { - node = parent; - pos = node->position(); - parent = node->parent(); - node->value_destroy_n(node->start(), node->count(), alloc); - deallocate(InternalSize(), node, alloc); - } - } while (parent != delete_root_parent); -} - //// // btree_iterator methods template <typename N, typename R, typename P> |