[libc++] Disable tree invariant check in asserts mode

[hans]

Summary

This is a follow-up to D153672 which removed the old debug mode and moved many of those checks to the regular asserts mode.

The tree invariant check is too expensive for the regular asserts mode, making element removal O(n) instead of O(log n), so disable it until there is a new debug assert category it can be put in.

[alexfh]

Thanks for the temporary fix, Hans! We're also affected by this.

LGTM

[alexfh]

Given the comment in https://reviews.llvm.org/D153672#4468348, I think, this should be fine to submit.

[hans]

In D154417#4471141, @alexfh wrote:

Given the comment in https://reviews.llvm.org/D153672#4468348, I think, this should be fine to submit.

Sounds good to me. Happy to follow up if libc++ maintainers have more input.

[ldionne]

LGTM, but as a matter of process, please try to wait for someone from the libc++ review group before submitting. Thanks for the fix!

libcxx/include/__tree

379–381

CC @var-const in case you want to annotate your TODOs for the debug mode in some special way to find them later.

libcxx/include/__tree

 //                nor any of its children refer to __z.  end_node->__left_
 //                may be different than the value passed in as __root.
 template <class _NodePtr>
 _LIBCPP_HIDE_FROM_ABI void
 __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
 {
     _LIBCPP_ASSERT_UNCATEGORIZED(__root != nullptr, "Root node should not be null");
     _LIBCPP_ASSERT_UNCATEGORIZED(__z != nullptr, "The node to remove should not be null");
-    _LIBCPP_ASSERT_UNCATEGORIZED(std::__tree_invariant(__root), "The tree invariants should hold");
+    // TODO: Use in the new debug mode:
+    // _LIBCPP_DEBUG_ASSERT(std::__tree_invariant(__root), "The tree invariants should hold");
     // __z will be removed from the tree.  Client still needs to destruct/deallocate it
     // __y is either __z, or if __z has two children, __tree_next(__z).
     // __y will have at most one child.
     // __y will be the initial hole in the tree (make the hole at a leaf)
     _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ?
                     __z : _VSTD::__tree_next(__z);
     // __x is __y's possibly null single child
     _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
     // __w is __x's possibly null uncle (will become __x's sibling)