From patchwork Mon Jul 13 08:40:40 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327776 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=ZtmsiXqn; 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 4B4xvB0QRjz9sDX for ; Mon, 13 Jul 2020 18:41:09 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 021EF385040B; Mon, 13 Jul 2020 08:41:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 021EF385040B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594629666; bh=bxAhIa2R4mh/4CuyisRTUYRup71HcFPeLB98Nx1Q14A=; 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=ZtmsiXqn7Ralljqhct6zvqQPKJ43JZpgu5t+mKIuqdhYUEZ4jCjrCM7xRZYro+syi MtUehgogEawr0KxhNhyp304UwiEdHl53aBxpRR9eufT+2Qi2VashEy9YAhtqJHRssd eiH4YUhTq4CpSR/qNy7tEMU98zM7KrUkYhzPwch0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mengyan1223.wang (unknown [89.208.246.23]) by sourceware.org (Postfix) with ESMTPS id 1F4E53857C5A; Mon, 13 Jul 2020 08:41:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 1F4E53857C5A 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) server-digest SHA384) (Client did not present a certificate) (Authenticated sender: xry111@mengyan1223.wang) by mengyan1223.wang (Postfix) with ESMTPSA id 4214B6590C; Mon, 13 Jul 2020 04:40:46 -0400 (EDT) Message-ID: <071987504076d5825c4d6aa148cfd463b79916f2.camel@mengyan1223.wang> Subject: [PATCH 1/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:40:40 +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=-5.3 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 first patch removes two redundant statements which are confusing. It > should > be applied anyway, disregarding other patches. The patch is attached, to prevent my mail client from destroying it :(. Please ignore a previous duplication of this mail with wrong title :(. libstdc++-v3/ChangeLog: * include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp (insert_leaf_new, insert_imp_empty): remove redundant statements. From 4eea45261ebf974ddf02f6154166c5cb6aa180da Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= Date: Fri, 10 Jul 2020 20:10:52 +0800 Subject: [PATCH 1/5] libstdc++: remove two redundant statements in pb_ds binary tree libstdc++-v3/ChangeLog: * include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp (insert_leaf_new, insert_imp_empty): remove redundant statements. --- .../ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp | 2 -- 1 file changed, 2 deletions(-) diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp index 3942da05600..bdc10379af6 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp @@ -122,7 +122,6 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd) } p_new_nd->m_p_parent = p_nd; - p_new_nd->m_p_left = p_new_nd->m_p_right = 0; PB_DS_ASSERT_NODE_CONSISTENT(p_nd) update_to_top(p_new_nd, (node_update* )this); @@ -142,7 +141,6 @@ insert_imp_empty(const_reference r_value) m_p_head->m_p_parent = p_new_node; p_new_node->m_p_parent = m_p_head; - p_new_node->m_p_left = p_new_node->m_p_right = 0; _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));) update_to_top(m_p_head->m_p_parent, (node_update*)this); -- 2.27.0 From patchwork Mon Jul 13 08:42:37 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327777 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=gTlCnXIB; 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 4B4xxM1zzGz9sRk for ; Mon, 13 Jul 2020 18:43:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3ED343850413; Mon, 13 Jul 2020 08:43:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3ED343850413 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594629780; bh=1jqoI5Lz0SuLY38fAOalX+4wD3nQyWLI5FDuy/cPgIc=; 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=gTlCnXIBgRo6EqbuTa32NCi3XxMR3t9zb5cdrtxObDmSVqlTPl6h6Axx+FTDdwH6u 7Zn35b96p/ZwYgctAZSI+3VktQ1faW9k2yOEDhwyHeVr8rLSUvkUs5v6ni9R3CCB3L XyA+vTozQhAUqZ7mKTtsj7rkO1KaWlK+CE3e6x5E= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mengyan1223.wang (unknown [89.208.246.23]) by sourceware.org (Postfix) with ESMTPS id 5929A3850411; Mon, 13 Jul 2020 08:42:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 5929A3850411 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 168BD6590C; Mon, 13 Jul 2020 04:42:40 -0400 (EDT) Message-ID: Subject: [PATCH 2/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:42:37 +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=-5.6 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 Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" > The second and third patch together resolve PR 81806. The attached patch keeps the subtree size in binary search tree nodes. libstdc++-v3/ChangeLog: * include/ext/pb_ds/detail/rb_tree_map_/node.hpp (rb_tree_node_::size_type): New typedef. (rb_tree_node_::m_subtree_size): New field. * include/ext/pb_ds/detail/splay_tree_map_/node.hpp (splay_tree_node_::size_type): New typedef. (splay_tree_node_::m_subtree_size): New field. * include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp (PB_DS_BIN_TREE_NAME::update_subtree_size): Declare new member function. * include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp (update_subtree_size): Define. (apply_update, update_to_top): Call update_subtree_size. From 248ab526b766070d348d676ebf9f9c7b16c3a93e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= Date: Fri, 10 Jul 2020 20:58:04 +0800 Subject: [PATCH 2/5] libstdc++: maintain subtree size in pb_ds binary search trees libstdc++-v3/ChangeLog: * include/ext/pb_ds/detail/rb_tree_map_/node.hpp (rb_tree_node_::size_type): New typedef. (rb_tree_node_::m_subtree_size): New field. * include/ext/pb_ds/detail/splay_tree_map_/node.hpp (splay_tree_node_::size_type): New typedef. (splay_tree_node_::m_subtree_size): New field. * include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp (PB_DS_BIN_TREE_NAME::update_subtree_size): Declare new member function. * include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp (update_subtree_size): Define. (apply_update, update_to_top): Call update_subtree_size. --- .../bin_search_tree_/bin_search_tree_.hpp | 3 ++ .../bin_search_tree_/rotate_fn_imps.hpp | 31 ++++++++++++++++--- .../ext/pb_ds/detail/rb_tree_map_/node.hpp | 8 +++++ .../ext/pb_ds/detail/splay_tree_/node.hpp | 8 +++++ 4 files changed, 46 insertions(+), 4 deletions(-) diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp index 32dcb6ee020..38a3bab0444 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp @@ -304,6 +304,9 @@ namespace __gnu_pbds inline void rotate_parent(node_pointer); + inline void + update_subtree_size(node_pointer); + inline void apply_update(node_pointer, null_node_update_pointer); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp index 1f18243a859..72ccfeb16a2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp @@ -122,8 +122,23 @@ rotate_parent(node_pointer p_nd) PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) -{ } +update_subtree_size(node_pointer p_nd) +{ + size_type size = 1; + if (p_nd->m_p_left) + size += p_nd->m_p_left->m_subtree_size; + if (p_nd->m_p_right) + size += p_nd->m_p_right->m_subtree_size; + p_nd->m_subtree_size = size; +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +apply_update(node_pointer p_nd, null_node_update_pointer /*p_update*/) +{ + update_subtree_size(p_nd); +} PB_DS_CLASS_T_DEC template @@ -131,6 +146,7 @@ inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer p_nd, Node_Update_* /*p_update*/) { + update_subtree_size(p_nd); node_update::operator()(node_iterator(p_nd), node_const_iterator(static_cast(0))); } @@ -152,7 +168,14 @@ update_to_top(node_pointer p_nd, Node_Update_* p_update) PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) -{ } +update_to_top(node_pointer p_nd, null_node_update_pointer /*p_update */) +{ + while (p_nd != m_p_head) + { + update_subtree_size(p_nd); + + p_nd = p_nd->m_p_parent; + } +} #endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp index de2d92a59b6..802562ad4f2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp @@ -58,6 +58,9 @@ namespace __gnu_pbds typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer node_pointer; + typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type + size_type; + typedef typename rebind_traits<_Alloc, metadata_type>::reference metadata_reference; @@ -88,6 +91,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; value_type m_value; bool m_red; metadata_type m_metadata; @@ -100,6 +104,9 @@ namespace __gnu_pbds typedef Value_Type value_type; typedef null_type metadata_type; + typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type + size_type; + typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer node_pointer; @@ -116,6 +123,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; value_type m_value; bool m_red; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp index 5c7b5d43c2b..d83b44deaae 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp @@ -56,6 +56,9 @@ namespace __gnu_pbds typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer node_pointer; + typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type + size_type; + typedef typename rebind_traits<_Alloc, metadata_type>::reference metadata_reference; @@ -85,6 +88,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; metadata_type m_metadata; }; @@ -98,6 +102,9 @@ namespace __gnu_pbds typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer node_pointer; + typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type + size_type; + inline bool special() const { return m_special; } @@ -111,6 +118,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; value_type m_value; bool m_special; }; -- 2.27.0 From patchwork Mon Jul 13 08:45:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327778 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=Iu89JWE2; 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 4B4y0z54yMz9sDX for ; Mon, 13 Jul 2020 18:46:11 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3BC3A385DC2E; Mon, 13 Jul 2020 08:46:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3BC3A385DC2E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594629969; bh=dlCAD8DkRJniPr/h85KyFBnbWLwfthb8wil3pF8p9Yc=; 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=Iu89JWE2fT2VtOnt7DvgDeVcmdnw48+zd5qidHjBly/PDIGza58LFQQevjtjMRUmy b6uhAAUAd+oxq4oKdqhxtCw7EJCEZCiGuLQ1jP6MZalA/Kf7zsapXoX+GJMO3zEmoy H1GuTIyrUjne35sOprUGyocD8Tmfx//2uhQfR4Sg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mengyan1223.wang (unknown [89.208.246.23]) by sourceware.org (Postfix) with ESMTPS id 7B7AF385DC2E; Mon, 13 Jul 2020 08:46:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 7B7AF385DC2E 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) server-digest SHA384) (Client did not present a certificate) (Authenticated sender: xry111@mengyan1223.wang) by mengyan1223.wang (Postfix) with ESMTPSA id 60BD166126; Mon, 13 Jul 2020 04:45:49 -0400 (EDT) Message-ID: Subject: [PATCH 3/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:45:46 +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=-5.8 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 second and third patch together resolve PR 81806. The attached patch modifies split_finish to use the subtree size we maintained in the previous patch, resolving libstdc++/81806. libstdc++-v3/ChangeLog: PR libstdc++/81806 * include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp (split_finish): Use maintained size, instead of calling std::distance. From 4434da1b2b45797204f4fd978dcc4fbba4b17c6e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= Date: Fri, 10 Jul 2020 21:38:09 +0800 Subject: [PATCH 3/5] libstdc++: use maintained size when split pb_ds binary search trees libstdc++-v3/ChangeLog: PR libstdc++/81806 * include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp (split_finish): Use maintained size, instead of calling std::distance. --- .../ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp index d08288f186d..fb924b4434b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp @@ -133,7 +133,9 @@ PB_DS_CLASS_C_DEC:: split_finish(PB_DS_CLASS_C_DEC& other) { other.initialize_min_max(); - other.m_size = std::distance(other.begin(), other.end()); + other.m_size = 0; + if (other.m_p_head->m_p_parent != 0) + other.m_size = other.m_p_head->m_p_parent->m_subtree_size; m_size -= other.m_size; initialize_min_max(); PB_DS_ASSERT_VALID((*this)) -- 2.27.0 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 From patchwork Mon Jul 13 08:51:09 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327780 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=H+wrggCk; 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 4B4y7158yFz9sDX for ; Mon, 13 Jul 2020 18:51:24 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 20863385041F; Mon, 13 Jul 2020 08:51:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 20863385041F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594630282; bh=X4KhYyDFKIUKvNtnlgwJL5bFnlJvFT2gaIZjp44u2cY=; 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=H+wrggCkxE21CWLBVc2qWqVTRmWo/EiXrr0E0xGCoD5cI5qrQZxSB033bpafzhukf bLLiyjYvtUqdiFLSPnUHNM2xKstTlbKvUJ5+ULTcC54KIe+TblUlMnQrrJ7nnALsbu 2kOOZPfkCWKV7sjLJnhTSvjly6/S9zZTUGmkLY+M= 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 CDC103857031; Mon, 13 Jul 2020 08:51:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org CDC103857031 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) server-digest SHA384) (Client did not present a certificate) (Authenticated sender: xry111@mengyan1223.wang) by mengyan1223.wang (Postfix) with ESMTPSA id 3BEB2661B7; Mon, 13 Jul 2020 04:51:15 -0400 (EDT) Message-ID: Subject: [PATCH 5/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:51:09 +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.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_SHORT, 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 fifth patch moves the functionality of tree_order_statistics_node_update > into the implementation of binary search trees (they are now order-statistics > trees), makes tree_order_statistics_node_update no-op, and deprecates it. The patch is attached. libstdc++-v3/ChangeLog: * include/Makefile.am: Add include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp and include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp, remove include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp. * include/Makefile.in: Regenerate. * include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp (PB_DS_BIN_TREE_NAME::find_by_order): Declare new member function. (PB_DS_BIN_TREE_NAME::order_of_key): Likewise. * include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp (PB_DS_OV_TREE_NAME::find_by_order): Likewise. (PB_DS_OV_TREE_NAME::order_of_key): Likewise. * include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp: New file. (PB_DS_CLASS_C_DEC::find_by_order): Implement. (PB_DS_CLASS_C_DEC::order_of_key): Likewise. * include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp: New file. (PB_DS_CLASS_C_DEC::find_by_order): Implement. (PB_DS_CLASS_C_DEC::order_of_key): Likewise. * include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp: Delete. * include/ext/pb_ds/tree_policy.hpp (tree_order_statistics_node_update): Make it noop, and deprecate. * testsuite/ext/pb_ds/example/tree_order_statistics.cc: Remove the usage of deprecated tree_order_statistics_node_update. * testsuite/ext/pb_ds/example/tree_order_statistics_join.cc: Likewise. From c0ee85f492872ba164ad3c1c9636aace1de02e96 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= Date: Sun, 12 Jul 2020 16:12:18 +0800 Subject: [PATCH 5/5] libstdc++: implement order statistics function in pb_ds tree maps libstdc++-v3/ChangeLog: * include/Makefile.am: Add include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp and include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp, remove include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp. * include/Makefile.in: Regenerate. * include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp (PB_DS_BIN_TREE_NAME::find_by_order): Declare new member function. (PB_DS_BIN_TREE_NAME::order_of_key): Likewise. * include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp (PB_DS_OV_TREE_NAME::find_by_order): Likewise. (PB_DS_OV_TREE_NAME::order_of_key): Likewise. * include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp: New file. (PB_DS_CLASS_C_DEC::find_by_order): Implement. (PB_DS_CLASS_C_DEC::order_of_key): Likewise. * include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp: New file. (PB_DS_CLASS_C_DEC::find_by_order): Implement. (PB_DS_CLASS_C_DEC::order_of_key): Likewise. * include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp: Delete. * include/ext/pb_ds/tree_policy.hpp (tree_order_statistics_node_update): Make it noop, and deprecate. * testsuite/ext/pb_ds/example/tree_order_statistics.cc: Remove the usage of deprecated tree_order_statistics_node_update. * testsuite/ext/pb_ds/example/tree_order_statistics_join.cc: Likewise. --- libstdc++-v3/include/Makefile.am | 3 +- libstdc++-v3/include/Makefile.in | 3 +- .../bin_search_tree_/bin_search_tree_.hpp | 10 +++ .../order_statistics_imps.hpp} | 50 ++++------- .../ov_tree_map_/order_statistics_imps.hpp | 77 ++++++++++++++++ .../detail/ov_tree_map_/ov_tree_map_.hpp | 10 +++ .../include/ext/pb_ds/tree_policy.hpp | 88 ++----------------- .../pb_ds/example/tree_order_statistics.cc | 9 +- .../example/tree_order_statistics_join.cc | 4 +- 9 files changed, 125 insertions(+), 129 deletions(-) rename libstdc++-v3/include/ext/pb_ds/detail/{tree_policy/order_statistics_imp.hpp => bin_search_tree_/order_statistics_imps.hpp} (71%) create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index e131ce04f8c..604821ecda2 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -365,6 +365,7 @@ pb_headers2 = \ ${pb_srcdir}/detail/bin_search_tree_/r_erase_fn_imps.hpp \ ${pb_srcdir}/detail/bin_search_tree_/rotate_fn_imps.hpp \ ${pb_srcdir}/detail/bin_search_tree_/split_join_fn_imps.hpp \ + ${pb_srcdir}/detail/bin_search_tree_/order_statistics_imps.hpp \ ${pb_srcdir}/detail/bin_search_tree_/traits.hpp \ ${pb_srcdir}/detail/cc_hash_table_map_/cc_ht_map_.hpp \ ${pb_srcdir}/detail/cc_hash_table_map_/cmp_fn_imps.hpp \ @@ -467,6 +468,7 @@ pb_headers4 = \ ${pb_srcdir}/detail/ov_tree_map_/info_fn_imps.hpp \ ${pb_srcdir}/detail/ov_tree_map_/insert_fn_imps.hpp \ ${pb_srcdir}/detail/ov_tree_map_/iterators_fn_imps.hpp \ + ${pb_srcdir}/detail/ov_tree_map_/order_statistics_imps.hpp \ ${pb_srcdir}/detail/ov_tree_map_/node_iterators.hpp \ ${pb_srcdir}/detail/ov_tree_map_/ov_tree_map_.hpp @@ -551,7 +553,6 @@ pb_headers7 = \ ${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \ ${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \ ${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \ - ${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \ ${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \ ${pb_srcdir}/detail/tree_trace_base.hpp \ ${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index c0b71e13a32..f7b2c136dbf 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -711,6 +711,7 @@ pb_headers2 = \ ${pb_srcdir}/detail/bin_search_tree_/r_erase_fn_imps.hpp \ ${pb_srcdir}/detail/bin_search_tree_/rotate_fn_imps.hpp \ ${pb_srcdir}/detail/bin_search_tree_/split_join_fn_imps.hpp \ + ${pb_srcdir}/detail/bin_search_tree_/order_statistics_imps.hpp \ ${pb_srcdir}/detail/bin_search_tree_/traits.hpp \ ${pb_srcdir}/detail/cc_hash_table_map_/cc_ht_map_.hpp \ ${pb_srcdir}/detail/cc_hash_table_map_/cmp_fn_imps.hpp \ @@ -813,6 +814,7 @@ pb_headers4 = \ ${pb_srcdir}/detail/ov_tree_map_/info_fn_imps.hpp \ ${pb_srcdir}/detail/ov_tree_map_/insert_fn_imps.hpp \ ${pb_srcdir}/detail/ov_tree_map_/iterators_fn_imps.hpp \ + ${pb_srcdir}/detail/ov_tree_map_/order_statistics_imps.hpp \ ${pb_srcdir}/detail/ov_tree_map_/node_iterators.hpp \ ${pb_srcdir}/detail/ov_tree_map_/ov_tree_map_.hpp @@ -897,7 +899,6 @@ pb_headers7 = \ ${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \ ${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \ ${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \ - ${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \ ${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \ ${pb_srcdir}/detail/tree_trace_base.hpp \ ${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \ diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp index 38a3bab0444..d76e822516b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp @@ -238,6 +238,15 @@ namespace __gnu_pbds inline const_reverse_iterator rend() const; + inline iterator + find_by_order(size_type order); + + inline const_iterator + find_by_order(size_type order) const; + + inline size_type + order_of_key(key_const_reference r_key) const; + /// Returns a const node_iterator corresponding to the node at the /// root of the tree. inline node_const_iterator @@ -411,6 +420,7 @@ namespace __gnu_pbds #include #include #include +#include #include #include #include diff --git a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp similarity index 71% rename from libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp rename to libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp index a31d5985d18..6358c79c3ba 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp @@ -34,8 +34,8 @@ // warranty. /** - * @file tree_policy/order_statistics_imp.hpp - * Contains forward declarations for order_statistics_key + * @file bin_search_tree_/order_statistics_imps.hpp + * Contains an implementation class for bin_search_tree_. */ #ifdef PB_DS_CLASS_C_DEC @@ -51,20 +51,20 @@ find_by_order(size_type order) while (it != end_it) { node_iterator l_it = it.get_l_child(); - const size_type o = (l_it == end_it)? 0 : l_it.get_metadata(); + const size_type o = (l_it == end_it)? 0 : l_it.m_p_nd->m_subtree_size; if (order == o) - return *it; + return *it; else if (order < o) - it = l_it; + it = l_it; else { - order -= o + 1; - it = it.get_r_child(); + order -= o + 1; + it = it.get_r_child(); } } - return base_type::end_iterator(); + return iterator(m_p_head); } PB_DS_CLASS_T_DEC @@ -87,38 +87,20 @@ order_of_key(key_const_reference r_key) const { node_const_iterator l_it = it.get_l_child(); - if (r_cmp_fn(r_key, this->extract_key(*(*it)))) - it = l_it; - else if (r_cmp_fn(this->extract_key(*(*it)), r_key)) + if (r_cmp_fn(r_key, PB_DS_V2F(*(*it)))) + it = l_it; + else if (r_cmp_fn(PB_DS_V2F(*(*it)), + r_key)) { - ord += (l_it == end_it)? 1 : 1 + l_it.get_metadata(); - it = it.get_r_child(); + ord += (l_it == end_it)? 1 : 1 + l_it.m_p_nd->m_subtree_size; + it = it.get_r_child(); } else { - ord += (l_it == end_it)? 0 : l_it.get_metadata(); - it = end_it; + ord += (l_it == end_it)? 0 : l_it.m_p_nd->m_subtree_size; + it = end_it; } } return ord; } - -PB_DS_CLASS_T_DEC -inline void -PB_DS_CLASS_C_DEC:: -operator()(node_iterator node_it, node_const_iterator end_nd_it) const -{ - node_iterator l_it = node_it.get_l_child(); - const size_type l_rank = (l_it == end_nd_it) ? 0 : l_it.get_metadata(); - - node_iterator r_it = node_it.get_r_child(); - const size_type r_rank = (r_it == end_nd_it) ? 0 : r_it.get_metadata(); - - const_cast(node_it.get_metadata())= 1 + l_rank + r_rank; -} - -PB_DS_CLASS_T_DEC -PB_DS_CLASS_C_DEC:: -~tree_order_statistics_node_update() -{ } #endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp new file mode 100644 index 00000000000..69c0d543b4c --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp @@ -0,0 +1,77 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file bin_search_tree_/order_statistics_imps.hpp + * Contains an implementation class for bin_search_tree_. + */ + +#ifdef PB_DS_CLASS_C_DEC + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +find_by_order(size_type order) +{ + if (order < m_size) + return iterator(&m_a_values[order]); + + return end(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +find_by_order(size_type order) const +{ return const_cast(this)->find_by_order(order); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +order_of_key(key_const_reference r_key) const +{ + pointer it = m_a_values; + pointer e_it = m_a_values + m_size; + while (it != e_it) + { + pointer mid_it = it + ((e_it - it) >> 1); + if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key)) + it = ++mid_it; + else + e_it = mid_it; + } + return (size_type)(it - m_a_values); +} +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp index 79ca5b30051..6dfc329eb7e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp @@ -382,6 +382,15 @@ namespace __gnu_pbds end() const { return m_end_it; } + inline iterator + find_by_order(size_type order); + + inline const_iterator + find_by_order(size_type order) const; + + inline size_type + order_of_key(key_const_reference r_key) const; + /// Returns a const node_iterator corresponding to the node at the /// root of the tree. inline node_const_iterator @@ -529,6 +538,7 @@ namespace __gnu_pbds #include #include #include +#include #include #undef PB_DS_CLASS_C_DEC diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp index e76b56a9454..1b769578fee 100644 --- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp @@ -55,99 +55,21 @@ namespace __gnu_pbds #define PB_DS_CLASS_C_DEC \ tree_order_statistics_node_update -#define PB_DS_BRANCH_POLICY_BASE \ - detail::branch_policy - - /// Functor updating ranks of entrees. template - class tree_order_statistics_node_update : private PB_DS_BRANCH_POLICY_BASE + class __attribute__((__deprecated__)) tree_order_statistics_node_update { - private: - typedef PB_DS_BRANCH_POLICY_BASE base_type; - public: - typedef Cmp_Fn cmp_fn; - typedef _Alloc allocator_type; - typedef typename allocator_type::size_type size_type; - typedef typename base_type::key_type key_type; - typedef typename base_type::key_const_reference key_const_reference; - - typedef size_type metadata_type; - typedef Node_CItr node_const_iterator; - typedef Node_Itr node_iterator; - typedef typename node_const_iterator::value_type const_iterator; - typedef typename node_iterator::value_type iterator; - - /// Finds an entry by __order. Returns a const_iterator to the - /// entry with the __order order, or a const_iterator to the - /// container object's end if order is at least the size of the - /// container object. - inline const_iterator - find_by_order(size_type) const; - - /// Finds an entry by __order. Returns an iterator to the entry - /// with the __order order, or an iterator to the container - /// object's end if order is at least the size of the container - /// object. - inline iterator - find_by_order(size_type); - - /// Returns the order of a key within a sequence. For exapmle, if - /// r_key is the smallest key, this method will return 0; if r_key - /// is a key between the smallest and next key, this method will - /// return 1; if r_key is a key larger than the largest key, this - /// method will return the size of r_c. - inline size_type - order_of_key(key_const_reference) const; - - private: - /// Const reference to the container's value-type. - typedef typename base_type::const_reference const_reference; - - /// Const pointer to the container's value-type. - typedef typename base_type::const_pointer const_pointer; - - /// Const metadata reference. - typedef typename detail::rebind_traits<_Alloc, metadata_type>::const_reference - metadata_const_reference; - - /// Metadata reference. - typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference - metadata_reference; - - /// Returns the node_const_iterator associated with the tree's root node. - virtual node_const_iterator - node_begin() const = 0; - - /// Returns the node_iterator associated with the tree's root node. - virtual node_iterator - node_begin() = 0; - - /// Returns the node_const_iterator associated with a just-after leaf node. - virtual node_const_iterator - node_end() const = 0; - - /// Returns the node_iterator associated with a just-after leaf node. - virtual node_iterator - node_end() = 0; - - /// Access to the cmp_fn object. - virtual cmp_fn& - get_cmp_fn() = 0; + typedef null_type metadata_type; - protected: - /// Updates the rank of a node through a node_iterator node_it; - /// end_nd_it is the end node iterator. inline void - operator()(node_iterator, node_const_iterator) const; + operator()(Node_CItr, Node_Itr) {} + protected: virtual - ~tree_order_statistics_node_update(); + ~tree_order_statistics_node_update() {} }; -#include - #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_BRANCH_POLICY_BASE diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc index cf4b357bff6..7a2f6f5a234 100644 --- a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc @@ -45,23 +45,18 @@ #include #include -#include using namespace std; using namespace __gnu_pbds; // A red-black tree table storing ints and their order -// statistics. Note that since the tree uses -// tree_order_statistics_node_update as its update policy, then it -// includes its methods by_order and order_of_key. +// statistics. typedef tree< int, null_type, less, - rb_tree_tag, - // This policy updates nodes' metadata for order statistics. - tree_order_statistics_node_update> + rb_tree_tag> set_t; int main() diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc index 2fc51ccdf6c..f8fc45a4344 100644 --- a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc @@ -42,7 +42,6 @@ #include #include -#include using namespace std; using namespace __gnu_pbds; @@ -51,8 +50,7 @@ using namespace __gnu_pbds; // statistics. typedef tree, - splay_tree_tag, - tree_order_statistics_node_update> + splay_tree_tag> tree_map_t; int main() -- 2.27.0