From patchwork Mon Jul 13 08:37:02 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xi Ruoyao X-Patchwork-Id: 1327774 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=2620:52:3:1:0:246e:9693:128c; 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=AIY9xNSU; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (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 4B4xq045DQz9sRN for ; Mon, 13 Jul 2020 18:37:32 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8C28C3939C34; Mon, 13 Jul 2020 08:37:29 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8C28C3939C34 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1594629449; bh=8M22gybcri6euyCNl0CYd1y3FLlcKm5YjFawItJHUX8=; h=Subject:To:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=AIY9xNSUzSITi35W5kYf3zoCcwuIWs45FJJRgwP7RC75H5RvV4OuLw2tLO2TSBg/q pXjl6igBZS02V6PtEkTWW96Bwh0ONtaTEeing/5o80swI3Ke3j1tbK4Sv9jltytsF8 o00u+ufU9y2JzoXlE5L4jfWc2ek8u49nep57zras= 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 BBB8B3939C30; Mon, 13 Jul 2020 08:37:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org BBB8B3939C30 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 3FCCB65907; Mon, 13 Jul 2020 04:37:10 -0400 (EDT) Message-ID: <67798e6881dcc5612ef31ac6b98586dfa5d83695.camel@mengyan1223.wang> Subject: [PATCH 0/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:37:02 +0800 User-Agent: Evolution 3.36.3 MIME-Version: 1.0 X-Spam-Status: No, score=1.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, JMQ_SPF_NEUTRAL, RCVD_IN_ABUSEAT, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=no autolearn_force=no version=3.4.2 X-Spam-Level: * 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" This is a series of patches essentially adding order statistics directly into pb_ds binary search trees. The main purpose is to resolve PR 81806 (spliting a splay tree needs linear time). The first patch removes two redundant statements which are confusing. It should be applied anyway, disregarding other patches. The second and third patch together resolve PR 81806. 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 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. Tested with `make check-target-libstdc++` in a non-bootstrap GCC build. GCC does not use pb_ds so it should be unnecessary to run a bootstrap.