From patchwork Mon Jul 13 08:48:03 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327779 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=s9Lql5gN; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4B4y3c1pdfz9sDX for ; Mon, 13 Jul 2020 18:48:28 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BB235385DC2E; Mon, 13 Jul 2020 08:48:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BB235385DC2E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594630105; bh=Dxq5+x7oNUFNA2c5LNwWseZLy3xqNZvdI3hi8SqROII=; h=Subject:To:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=s9Lql5gNmCBarBZJL/jMApvj98sCxJQaYd8PXHOHX8vbab6ajfl9MnuVutHXo/XAJ 0P95S4gH1bg3xtjmIR+Gn2mPIcbKmDEcR3hvGcDKzNjB1pdce5PM6RycjgSc/rcurC nzo6pLfznmX7ejSph3YwNDRkYE38B4q5Xvs8fgqo= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mengyan1223.wang (mengyan1223.wang [89.208.246.23]) by sourceware.org (Postfix) with ESMTPS id 003AE3857031; Mon, 13 Jul 2020 08:48:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 003AE3857031 Received: from xry111-X57S1 (unknown [113.140.11.5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature ECDSA (P-384)) (Client did not present a certificate) (Authenticated sender: xry111@mengyan1223.wang) by mengyan1223.wang (Postfix) with ESMTPSA id 32B61661B7; Mon, 13 Jul 2020 04:48:09 -0400 (EDT) Message-ID: <5b30f1395039b7b179f095f5226fb1b841604bfa.camel@mengyan1223.wang> Subject: [PATCH 4/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) To: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Date: Mon, 13 Jul 2020 16:48:03 +0800 In-Reply-To: <67798e6881dcc5612ef31ac6b98586dfa5d83695.camel@mengyan1223.wang> References: <67798e6881dcc5612ef31ac6b98586dfa5d83695.camel@mengyan1223.wang> User-Agent: Evolution 3.36.3 MIME-Version: 1.0 X-Spam-Status: No, score=-6.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_ABUSEAT, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Xi Ruoyao via Gcc-patches From: Xi Ruoyao Reply-To: Xi Ruoyao Cc: Raihat Zaman Neloy , Oleksandr Kulkov , xry111@mengyan1223.wang Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" > The fourth patch converts the point_iterator of rb_tree and splay_tree based > maps to random access iterator. With the subtree size kept we can implement > the > operators required by random access iterator in logarithm time. The patch is attached. libstdc++-v3/ChangeLog: * include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp (bin_search_tree_const_it_::size_type): New typedef. (bin_search_tree_it_::difference_type): Likewise. (bin_search_tree_const_it_::inc): New overloads. (bin_search_tree_const_it_::dec): Likewise. (bin_search_tree_const_it_::order): New member function. (bin_search_tree_const_it_::operator+=): New operator. (bin_search_tree_const_it_::operator-=): Likewise. (bin_search_tree_const_it_::operator+): Likewise. (bin_search_tree_const_it_::operator-): Likewise. (bin_search_tree_const_it_::operator<): Likewise. (bin_search_tree_const_it_::operator<=): Likewise. (bin_search_tree_const_it_::operator>): Likewise. (bin_search_tree_const_it_::operator>=): Likewise. (bin_search_tree_const_it_::operator[]): Likewise. (bin_search_tree_it_::operator+=): Likewise. (bin_search_tree_it_::operator-=): Likewise. (bin_search_tree_it_::operator+): Likewise. (bin_search_tree_it_::operator-): Likewise. (bin_search_tree_it_::operator[]): Likewise. (bin_search_tree_const_it_::iterator_category): Change to std::random_access_iterator_tag. From 5149d3156b0b1ae5d8cf82c54d041bd47451c995 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= Date: Sat, 11 Jul 2020 23:32:36 +0800 Subject: [PATCH 4/5] libstdc++: make pb_ds binary search tree point iterator random accessible libstdc++-v3/ChangeLog: * include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp (bin_search_tree_const_it_::size_type): New typedef. (bin_search_tree_it_::difference_type): Likewise. (bin_search_tree_const_it_::inc): New overloads. (bin_search_tree_const_it_::dec): Likewise. (bin_search_tree_const_it_::order): New member function. (bin_search_tree_const_it_::operator+=): New operator. (bin_search_tree_const_it_::operator-=): Likewise. (bin_search_tree_const_it_::operator+): Likewise. (bin_search_tree_const_it_::operator-): Likewise. (bin_search_tree_const_it_::operator<): Likewise. (bin_search_tree_const_it_::operator<=): Likewise. (bin_search_tree_const_it_::operator>): Likewise. (bin_search_tree_const_it_::operator>=): Likewise. (bin_search_tree_const_it_::operator[]): Likewise. (bin_search_tree_it_::operator+=): Likewise. (bin_search_tree_it_::operator-=): Likewise. (bin_search_tree_it_::operator+): Likewise. (bin_search_tree_it_::operator-): Likewise. (bin_search_tree_it_::operator[]): Likewise. (bin_search_tree_const_it_::iterator_category): Change to std::random_access_iterator_tag. --- .../bin_search_tree_/point_iterators.hpp | 277 +++++++++++++++++- 1 file changed, 276 insertions(+), 1 deletion(-) diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp index eb2f4fdbfd2..f7efe79290a 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp @@ -105,8 +105,9 @@ namespace __gnu_pbds class bin_search_tree_const_it_ { public: - typedef std::bidirectional_iterator_tag iterator_category; + typedef std::random_access_iterator_tag iterator_category; typedef typename _Alloc::difference_type difference_type; + typedef typename _Alloc::size_type size_type; typedef Value_Type value_type; typedef Pointer pointer; typedef Const_Pointer const_pointer; @@ -185,6 +186,28 @@ namespace __gnu_pbds return ret_it; } + inline PB_DS_TREE_CONST_IT_C_DEC& + operator+=(difference_type dif) + { + inc(dif, integral_constant()); + return *this; + } + + inline PB_DS_TREE_CONST_IT_C_DEC + operator+(difference_type dif) const + { + PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); + ret_it += dif; + return ret_it; + } + + inline PB_DS_TREE_CONST_IT_C_DEC& + operator-=(difference_type dif) + { + dec(dif, integral_constant()); + return *this; + } + inline PB_DS_TREE_CONST_IT_C_DEC& operator--() { @@ -200,6 +223,54 @@ namespace __gnu_pbds return ret_it; } + inline PB_DS_TREE_CONST_IT_C_DEC + operator-(difference_type dif) const + { + PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); + ret_it -= dif; + return ret_it; + } + + inline const_reference + operator[](difference_type dif) const + { + return *operator+(dif); + } + + inline bool + operator<(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const + { + return order() < rhs.order(); + } + + inline bool + operator<=(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const + { + return order() <= rhs.order(); + } + + inline bool + operator>(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const + { + return order() >= rhs.order(); + } + + inline bool + operator>=(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const + { + return order() >= rhs.order(); + } + + inline difference_type + operator-(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const + { + size_type r = order(), l = rhs.order(); + if (r >= l) + return static_cast(r - l); + else + return -static_cast(l - r); + } + protected: inline void inc(false_type) @@ -266,6 +337,171 @@ namespace __gnu_pbds m_p_nd = p_y; } + Node_Pointer find_by_order_in_subtree(size_type order) + { + Node_Pointer p_nd = m_p_nd; + + while (p_nd != 0) + { + Node_Pointer p_left = p_nd->m_p_left; + const size_type o = (p_left == 0 ? 0 : p_left->m_subtree_size); + + if (order == o) + break; + else if (order < o) + p_nd = p_left; + else + { + order -= o + 1; + p_nd = p_nd->m_p_right; + } + } + + return p_nd; + } + + inline void + inc(difference_type dif, false_type) + { dec(dif, true_type()); } + + void + inc(difference_type dif, true_type) + { + if (dif < 0) + { + dec(-dif, true_type()); + return; + } + + size_type d = static_cast(dif); + + if (d != 0 && + m_p_nd->special() && + m_p_nd->m_p_parent->m_p_parent == m_p_nd) + { + --d; + m_p_nd = m_p_nd->m_p_left; + } + + while (d != 0) + { + Node_Pointer p_right = m_p_nd->m_p_right; + const size_type o = (p_right == 0 ? 0 : p_right->m_subtree_size); + + if (o >= d) + { + m_p_nd = m_p_nd->m_p_right; + m_p_nd = find_by_order_in_subtree(d - 1); + break; + } + + d -= o + 1; + + while (m_p_nd == m_p_nd->m_p_parent->m_p_right) + m_p_nd = m_p_nd->m_p_parent; + + m_p_nd = m_p_nd->m_p_parent; + } + } + + inline void + dec(difference_type dif, false_type) + { inc(dif, true_type()); } + + void + dec(difference_type dif, true_type) + { + if (dif < 0) + { + inc(-dif, true_type()); + return; + } + + size_type d = static_cast(dif); + + if (d != 0 && + m_p_nd->special() && + m_p_nd->m_p_parent->m_p_parent == m_p_nd) + { + --d; + m_p_nd = m_p_nd->m_p_right; + } + + while (d != 0) + { + Node_Pointer p_left = m_p_nd->m_p_left; + const size_type o = (p_left == 0 ? 0 : p_left->m_subtree_size); + + if (o >= d) + { + m_p_nd = m_p_nd->m_p_left; + m_p_nd = find_by_order_in_subtree(o - d); + break; + } + + d -= o + 1; + + while (m_p_nd == m_p_nd->m_p_parent->m_p_left) + m_p_nd = m_p_nd->m_p_parent; + + m_p_nd = m_p_nd->m_p_parent; + } + } + + inline size_type + order() const + { + return order(integral_constant()); + } + + size_type + order(true_type) const + { + if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) + return m_p_nd->m_p_parent->m_subtree_size; + + Node_Pointer p_left = m_p_nd->m_p_left; + size_type ret = (p_left == 0 ? 0 : p_left->m_subtree_size); + + for (Node_Pointer p_nd = m_p_nd; + p_nd->m_p_parent->m_p_parent != p_nd; + p_nd = p_nd->m_p_parent) + { + if (p_nd->m_p_parent->m_p_right == p_nd) + { + ret += 1; + if (p_nd->m_p_parent->m_p_left != 0) + ret += p_nd->m_p_parent->m_p_left->m_subtree_size; + } + } + + return ret; + } + + size_type + order(false_type) const + { + if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) + return m_p_nd->m_p_parent->m_subtree_size; + + Node_Pointer p_right = m_p_nd->m_p_right; + size_type ret = (p_right == 0 ? 0 : p_right->m_subtree_size); + + for (Node_Pointer p_nd = m_p_nd; + p_nd->m_p_parent->m_p_parent != p_nd; + p_nd = p_nd->m_p_parent) + { + if (p_nd->m_p_parent->m_p_left == p_nd) + { + ret += 1; + if (p_nd->m_p_parent->m_p_right != 0) + ret += p_nd->m_p_parent->m_p_right->m_subtree_size; + } + } + + return ret; + } + public: Node_Pointer m_p_nd; }; @@ -282,6 +518,8 @@ namespace __gnu_pbds class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC { public: + typedef typename _Alloc::difference_type difference_type; + inline bin_search_tree_it_(const Node_Pointer p_nd = 0) : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) @@ -337,6 +575,21 @@ namespace __gnu_pbds return ret_it; } + inline PB_DS_TREE_IT_C_DEC& + operator+=(difference_type dif) + { + PB_DS_TREE_CONST_IT_C_DEC:: operator+=(dif); + return *this; + } + + inline PB_DS_TREE_IT_C_DEC + operator+(difference_type dif) const + { + PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); + ret_it += dif; + return ret_it; + } + inline PB_DS_TREE_IT_C_DEC& operator--() { @@ -352,8 +605,30 @@ namespace __gnu_pbds return ret_it; } + inline PB_DS_TREE_IT_C_DEC& + operator-=(difference_type dif) + { + PB_DS_TREE_CONST_IT_C_DEC:: operator-=(dif); + return *this; + } + + inline PB_DS_TREE_IT_C_DEC + operator-(difference_type dif) const + { + PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); + ret_it -= dif; + return ret_it; + } + + inline typename PB_DS_TREE_CONST_IT_C_DEC::reference + operator[](difference_type dif) const + { + return *operator+(dif); + } + protected: typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; + }; #undef PB_DS_TREE_CONST_IT_C_DEC -- 2.27.0