From patchwork Mon Mar 10 17:51:14 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthieu Longo X-Patchwork-Id: 107595 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 73A973858C2C for ; Mon, 10 Mar 2025 17:59:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 73A973858C2C Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=arm.com header.i=@arm.com header.a=rsa-sha256 header.s=selector1 header.b=Ah2cgTzY; dkim=pass (1024-bit key) header.d=arm.com header.i=@arm.com header.a=rsa-sha256 header.s=selector1 header.b=Ah2cgTzY X-Original-To: binutils@sourceware.org Delivered-To: binutils@sourceware.org Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05on2061f.outbound.protection.outlook.com [IPv6:2a01:111:f403:2614::61f]) by sourceware.org (Postfix) with ESMTPS id 29A313858D39 for ; Mon, 10 Mar 2025 17:52:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 29A313858D39 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 29A313858D39 Authentication-Results: server2.sourceware.org; arc=pass smtp.remote-ip=2a01:111:f403:2614::61f ARC-Seal: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1741629146; cv=pass; b=LqwzAQNufpKVFeHX5F3XSH3FJhoy/uYkKfpxONOtJlLrSiDHcWdNiVCYb8cFnSgU5nxEJcJBOxtupmLw3YmZkesGAY2ZL7TBQoH7ztoN6p5+i479IIzaPef/V6tl0YFcMSqM4aUdgpVaNJhRRfEUZtIPsyYz3//KkwWHss+yBqY= ARC-Message-Signature: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1741629146; c=relaxed/simple; bh=oyaY5+m3JYWM2CtHvwjkbLgANm2NAhmv/swFSa16B28=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=fcM3YjwJ6Um+7bgmVEa4y397Qi+3IzUp/zlGdNEaWRcKxVGiAE2lCrwAUir+BhrrEcrb+AA+fvM3Mr1XGkZ0bFcdcP5vbaFqOTZJkgpo0mJ2BCCed8CGrA17zbhdTBkpJ2c6PPxC7VUkocAFqKO0QTnQ0k0iE0JyWHHnIr9vYa0= ARC-Authentication-Results: i=3; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 29A313858D39 ARC-Seal: i=2; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=pass; b=yKLKw3sYwtNZUwRjNTSSQCrvhkrvPVOsNfXnEz9IdXn1f7ZgZ7+nw5ZrpPbC+hIwUQlMNs0PkvJADbGoxCz8rPjs+DBFX5a2l/KhWoOa494K/cL5CwPlva4L0uPUGYkIqDevovqfaAzMty+QrOLKTQgvvIz6QkmZ/XJ2uYwce12z4mgyrFB8BHw5/DaDAGEqKrAq2QHxyj0c3Kx12qY4mJjS+sgzLh6SX42QZP0vfQCu9CtLfodi5R2+8uAc7kH8MRKjimI/tgXl7axZS7tzx1w+uhM0IWv2jUD1v6d0wNY5Rovpgz4CjvIiRH7hQX4bvgauAMxRCV2vxyR6eduzWA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=TwGPWuDAbmsSNMn7p61Z1T9pUOXw5d8LyMFUpHvhYhk=; b=XhA/py+40AN/N5zLFatR9XzVnWEgM0HSbgj0I4n+71fN6eoUuwrjfhzdZhFRdifho1ZwSzmQg2xVv254Gs1kSKid2G2gPnWafzZTuvUcflHP7eQwfd43NdhPq++e/pz9PPpIy6cotbEeUkE54XvM/I6XtO/f2ofPfa//9pagR4fPz43vZDATVcIiesUW6EUvpJyQik/xBIPc/Q1HGTZBIq0z6y2whYOQEU7Ok5R9LuXMOMg3AJKCM+TqQjFYbR897xPKS1qbecbC8HRNbT47yG4WYbil++NwyVR6GmcUrj6OFDWcZ3+ClWtdTyCajsrIbv+PkKDMkLfkVw4vWwGvkg== ARC-Authentication-Results: i=2; mx.microsoft.com 1; spf=pass (sender ip is 63.35.35.123) smtp.rcpttodomain=sourceware.org smtp.mailfrom=arm.com; dmarc=pass (p=none sp=none pct=100) action=none header.from=arm.com; dkim=pass (signature was verified) header.d=arm.com; arc=pass (0 oda=0 ltdi=1) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=arm.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=TwGPWuDAbmsSNMn7p61Z1T9pUOXw5d8LyMFUpHvhYhk=; b=Ah2cgTzY/1Q3Lk4YsJaB2xohiQAC99V8PXgmH570TviGZzZffvrdUVddwN5L/dg4k9XDGqoKX34mvg5DHEZhBL+VJ1LfYKGdNIq6YQYzVdCa67mlt3dzC100T2loM3kml3bTeq5tOTfWVXiRV1r2oMG+yCmzwR5kwIDcTv6wCOI= Received: from DUZPR01CA0086.eurprd01.prod.exchangelabs.com (2603:10a6:10:46a::13) by DU0PR08MB7857.eurprd08.prod.outlook.com (2603:10a6:10:3b3::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8511.26; Mon, 10 Mar 2025 17:52:16 +0000 Received: from DU6PEPF00009526.eurprd02.prod.outlook.com (2603:10a6:10:46a:cafe::f3) by DUZPR01CA0086.outlook.office365.com (2603:10a6:10:46a::13) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.8511.26 via Frontend Transport; Mon, 10 Mar 2025 17:52:16 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=arm.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DU6PEPF00009526.mail.protection.outlook.com (10.167.8.7) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.8534.20 via Frontend Transport; Mon, 10 Mar 2025 17:52:16 +0000 Received: ("Tessian outbound 93a06e49d4fd:v585"); Mon, 10 Mar 2025 17:52:16 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 9c3d531540b5ad44 X-TessianGatewayMetadata: sU7Kv3FHePwfGSxHTShPkE0vF415vz+lN6E/TLfTkJhKwl2h2QkF15p7L1Qe5L0WcgCmqQr9/IqNa0aGcinEM8Rwgt/K7VLTvXlGV/r9axABtVazomXdOQ6vUn1xgCpkIjiSIoKdnccG6/MX4tkaUQoUImJYQrSPGXK+u6SZZME= X-CR-MTA-TID: 64aa7808 Received: from La16e72b78324.2 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 788B76E2-5407-4C3F-9D36-57F15135613C.1; Mon, 10 Mar 2025 17:52:09 +0000 Received: from OSPPR02CU001.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id La16e72b78324.2 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384); Mon, 10 Mar 2025 17:52:09 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=tLahPXjsaqAhVJJVkzvoxtHunJ2yptQ5nqh2PxLhOqNjdDYg75mlMopelCbr3myh1BIA+Kmx0zDoiV5XKAtuOxEl2qEJ6RlA9HCnQNqfMYJXRwMznWApoyj05ZjTKvs6b+07M9dC7STxvYD0z93jt5DF5SaCc46iPUDrqdZtdOGsuK4GBBL/uPFq0Tkx+DpB+ezO8QDemKVoJBlrOG/Rq+2kmNR043Xnhg5FEZN8nUhY0KvpgOzE4ZYFTPor7apGEMfTAMoFmdfAiycn+XmzxpbbKG89MNFjAJ4ReeHntvW7mizs7aIk/QiTiTaRk/xs8E2sKlos2iK8B9q8NwLiPA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=TwGPWuDAbmsSNMn7p61Z1T9pUOXw5d8LyMFUpHvhYhk=; b=uw6gBOxwHLoM5+1UHBkKPROQWOQZ5SVRm9qr6D8DshrIVqy5c40MwhAggJhZF45pZ7eFWvMgkQQZkzMbn41GmCdgnsMsxx3Y1LW5tOT0gltBAV10VX3y4KuIdrpY2LvKDGwTYM1pYfoypSWx/ION/inEf32lSvyM8KEtbYIHYiEVWuigInN4i+JrP3lZD+YO1X1XCmEu4xURhhHJEUIgGn21bLzcxGzIwPSlpjOdBfU1/Cr8LwPc7rsWsXIYSFmiu1kB7pzPRu4Coopaf+IN631fz+EPqu3J7ix433DpeqNHy02CCgshmt7GPKfiTKvjJSTgL1iWeMGSq380p+iqRA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=fail (sender ip is 172.205.89.229) smtp.rcpttodomain=sourceware.org smtp.mailfrom=arm.com; dmarc=fail (p=none sp=none pct=100) action=none header.from=arm.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=arm.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=TwGPWuDAbmsSNMn7p61Z1T9pUOXw5d8LyMFUpHvhYhk=; b=Ah2cgTzY/1Q3Lk4YsJaB2xohiQAC99V8PXgmH570TviGZzZffvrdUVddwN5L/dg4k9XDGqoKX34mvg5DHEZhBL+VJ1LfYKGdNIq6YQYzVdCa67mlt3dzC100T2loM3kml3bTeq5tOTfWVXiRV1r2oMG+yCmzwR5kwIDcTv6wCOI= Received: from AS4P195CA0022.EURP195.PROD.OUTLOOK.COM (2603:10a6:20b:5d6::10) by AM0PR08MB5475.eurprd08.prod.outlook.com (2603:10a6:208:188::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8511.27; Mon, 10 Mar 2025 17:52:01 +0000 Received: from AMS0EPF00000195.eurprd05.prod.outlook.com (2603:10a6:20b:5d6:cafe::b1) by AS4P195CA0022.outlook.office365.com (2603:10a6:20b:5d6::10) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.8511.26 via Frontend Transport; Mon, 10 Mar 2025 17:52:01 +0000 X-MS-Exchange-Authentication-Results: spf=fail (sender IP is 172.205.89.229) smtp.mailfrom=arm.com; dkim=none (message not signed) header.d=none;dmarc=fail action=none header.from=arm.com; Received-SPF: Fail (protection.outlook.com: domain of arm.com does not designate 172.205.89.229 as permitted sender) receiver=protection.outlook.com; client-ip=172.205.89.229; helo=nebula.arm.com; Received: from nebula.arm.com (172.205.89.229) by AMS0EPF00000195.mail.protection.outlook.com (10.167.16.215) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.20.8534.20 via Frontend Transport; Mon, 10 Mar 2025 17:52:01 +0000 Received: from AZ-NEU-EX06.Arm.com (10.240.25.134) by AZ-NEU-EX06.Arm.com (10.240.25.134) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.39; Mon, 10 Mar 2025 17:51:53 +0000 Received: from PW070M4K.arm.com (10.57.84.208) by mail.arm.com (10.240.25.134) with Microsoft SMTP Server id 15.1.2507.39 via Frontend Transport; Mon, 10 Mar 2025 17:51:52 +0000 From: Matthieu Longo To: CC: Alan Modra , Richard Earnshaw , Matthieu Longo Subject: [PATCH v0 01/15] libiberty: add implementations of common methods for type-sensitive doubly linked lists Date: Mon, 10 Mar 2025 17:51:14 +0000 Message-ID: <20250310175131.1217374-2-matthieu.longo@arm.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250310175131.1217374-1-matthieu.longo@arm.com> References: <20250310175131.1217374-1-matthieu.longo@arm.com> MIME-Version: 1.0 X-EOPAttributedMessage: 1 X-MS-TrafficTypeDiagnostic: AMS0EPF00000195:EE_|AM0PR08MB5475:EE_|DU6PEPF00009526:EE_|DU0PR08MB7857:EE_ X-MS-Office365-Filtering-Correlation-Id: 0a859d3b-f9f0-44fc-6e9d-08dd5ffc4ba4 x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; ARA:13230040|82310400026|376014|36860700013|1800799024; X-Microsoft-Antispam-Message-Info-Original: O1OKb9XOiG5LobMK29djfh/M+FPG7Wb0ytuOp5zBrK3qO9UCK4yxD4CxFP7yOo+sWuykHPTBj+/pRA/hg6EhXupvHYh5Efld4WI4xM5Sj3gs9u8rOSfS++b/oUBA5X/qjOpMVj499j39k/jbVwINg5hGvgyXHCRx6mYkuY4BIQvoKeHZsEvO9c3rXlWxqw4qnPEwyeLYwI6J10V8/eXst/mUCIsffPH0+pAsb/NAHzwYF75bAyicfGBSxd/SJq93vyql05cq98kXOOQDhXmIrb1JOg5Ack8ZrPB4uWH9CLv98+Mbt0XrsnNHSEu9PNE8rgxyHPhPNKH3EH5pk12zC21HFjnUwRSJm+pLURbqcdkpN8VgZk/JC3t7G937p2v1yNCyRlJin3ZE0RWSB/kXr/6ayN0aRU0Sbcu5F1ugS4mak2IY0V58mmr/6GxrHzRyeHMWrSRV45yVdNoYWeAsgYCyfTxUeNTIygZfdNm35iVF420snPBhRZjVz8IrbNrTsoynPEejfKJU5g8KAcw67h2NOoQRg9+PH+3Lv1srths+hwoea4VGRbiJBWABIhHMBrrk8BQuYQBfZpWrA/3muxyv3gniPbfIUmDXfUfhoHgB1P/NTtgiqN4nKI+B/RD+DzLESe4wL1nC1MGPUTeF6fTC3P8qxYwRS/HI59iCAp3hs18iWRmL5ZtJ60b3OJJVmAT2SQ78Rvc/r8Pzq1VrOi5/eAqJzpRLhtIZecXFUBfJdybtn3swrLCbLseak9/VaPIbEZ+ydJJ4fuvqtsze/zdUOj9l4b4D4Qd79HC6Y13VqHC3jSl37IESLCnpdSymkC1oPyXN9k4dkWwB0cK4uxTdHolxswr2TYR3TcXO6xZsu7JpyDhftvvZLj74oG1nnYT3PO9f1X50s48tqOpVZnFU2VrasKnfmENECm2OnlbX5uWtIkB38By4T5nSfXFkA6RyPGINMZ79p8fWnLErB2sTPlyinu9IAfy5RWaYDYvuLVo5lcO+r64ENJcHNjQ69qMe45F0BD8GR/6k3uaYkxyXTpXA7GUXOy9m3wbmY7/uFcQQx8TONZcWLcIbtfVAagHrYZvp8nTQdUSDjTv7nLZIYH+hW1mDYQhU09kWI3evgT/a15r58cAkqdUhu4mTkf77N0TZJNEx790mj9m8LIedND7EnmpsXl/YTISnK7yCbH0xHPTj04hAFbqk/ncc4SZ7thdHpZWDdftjtSHy/I48qTu2ZIIkrIjzx5bDhLTNR1zTA3hvwaS2JenOMficNnZcO5X85kTlsFmAkuoyuqrfAMhdg2oMwdDKgozIdRik78MY5Ukg8ALYA2TTgwrhpKbdu4dqxYH0O0mX3MOqWg5yhEDNAZC+W+7+AHYK6t5JFePPA7YnF967vLn7LyhItWq5oQSRduMlDluzsk+DO3Mm8YPXnycGDLZSvY0fjqs= X-Forefront-Antispam-Report-Untrusted: CIP:172.205.89.229; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:nebula.arm.com; PTR:InfoDomainNonexistent; CAT:NONE; SFS:(13230040)(82310400026)(376014)(36860700013)(1800799024); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM0PR08MB5475 X-MS-Exchange-SkipListedInternetSender: ip=[2603:10a6:20b:5d6::10]; domain=AS4P195CA0022.EURP195.PROD.OUTLOOK.COM X-MS-Exchange-Transport-CrossTenantHeadersStripped: DU6PEPF00009526.eurprd02.prod.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 75836800-8991-4edc-3c71-08dd5ffc42cd X-Microsoft-Antispam: BCL:0; ARA:13230040|14060799003|1800799024|35042699022|36860700013|82310400026|376014; X-Microsoft-Antispam-Message-Info: PDBiVLKky+mUuwnfuk6JwLivWg74gGVm/gzCZr6Vb60u3MD7gvLausYxXKclJWUQk4LVUIWqMkz3DkpF43HQEyNzF3xAW2zENEyiV5+exTrn48adSdTuIPpMZvzKM5Lr2y9gRwBiLbWuU9ZIBv0kNyiAUJ/RQwyXxELXtIbP6Af7Jm8H8iaFYdnquDl/T1560apytTC4fF2JWoQMBfdS7tNDVJJb33IrSsbs0i7HJAbtYj7uhjqvJaTidXmJRZI6evVJcfoiBFNsGlh29zSKUpLYq36ILw+F1TrCD/opX8Qz0+Fn8lph/w1xFHVB1F2Okc6RPU/0Od5K2k3SiCxy84HamfCsrkZVV+a6UwNHzEmSsHndCwOWxjqHaySigXKVM2VBNScXA16Oo31/K/3OaMfkWcfSW5Nizy7drtVGwAJPj96I+/JgIg/+GtsXTPIFDJ1le+9BGZ6de3HKzoLSmARmuarIGsox19EElsLqgVA+5oRw0Kg5PdZTJ2OciTrHGJZZGeZaTubqeyIIVz7rD4wvd2q/y5CpMWTprTLrUHvV1QKM4nVfiWmnQNTZuDjWPw0fnbWevMQkvexYlXq9taXLroJ/eCq891SDDqzCrsj8xz79wQnh4e8qzkZ+1hf37LC8Zw9YD2QDedXg9ki/7XLls3QUFgKuej4Sjh+ZSVxk7a03NO0GdGu0bpda0/gSU5vmhDbjA+FQ/7Gm2/v6ClngkVilKqAfpJ+yLPlTtaYEprnGK8mUcEp10GqsXmaJsDdUHMOpl35efwo4ZuK3xM/vSBxgl7ItNoZpzEXIw2NJ5cOQRvbgZIyWOBuMMRb1BXUmvwsY+9dIb2Wdpc9M/iOrIDWMeaEp6a1B1yWm1sBrF5h8FHjJtW+bmXSXWyXNGwsiIGJhnpiXy4+TuajYoLzf7NVMoSp7FIRaPJo3KxWsM79qEdGjW07HJJ82jkqpjuQ4A6jcKrX40f3EhAK0NnfEGTC7EJXYquyzsEFJWnnoxa6eu97RP0Ovx41E6KTmheDMF3UL9DKb+1AZea5mD0yKZiJdsBba012CeGBiZBtlH3bXgfZ1eRXSLVCSw7j6uutryyUZI9dnYGKgxCM7Efv/CXOMrC7dnwETNKyYQk4E5K3X17NakC33UC8xgN70qzzDKHQHYxeDW96ht+XJOpi+GgI6cILb8suSzC4DBsl2wEnXPf65QX/I956Ozqt8XrQicm4InCf2B7J8p8knH9WlGBA6BbrfuldKXoQhegv06+M8e2sqtCeb5W6KNLtgYVIPC6okvlpP88f03rcjS8PZwhcKcyVZcwFez4tBHyBBkI2vclt+pmdnrdmH+R9zraViBuv2fWAXOH/tcn/8Mqjw65QDL9TuqEmLlJBpnHIAUcWR2eHGbaMTMWOueXNsz2bvKP9CVHg9bbmPqI55yZzGxZ49sjZeIot4T45F//k= X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:64aa7808-outbound-1.mta.getcheckrecipient.com; CAT:NONE; SFS:(13230040)(14060799003)(1800799024)(35042699022)(36860700013)(82310400026)(376014); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 10 Mar 2025 17:52:16.1943 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 0a859d3b-f9f0-44fc-6e9d-08dd5ffc4ba4 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: DU6PEPF00009526.eurprd02.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU0PR08MB7857 X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FORGED_SPF_HELO, GIT_PATCH_0, KAM_SHORT, SPF_HELO_PASS, SPF_NONE, TXREP, UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: binutils@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Binutils mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: binutils-bounces~patchwork=sourceware.org@sourceware.org Those methods's implementation is relying on duck-typing at compile time. The structure corresponding to the node of a doubly linked list needs to define attributes 'prev' and 'next' which are pointers on the type of a node. The structure wrapping the nodes and others metadata (first, last, size) needs to define pointers 'first_', and 'last_' of the node's type, and an integer type for 'size'. Mutative methods are bundled together and are declarable once via a same macro. The merge sort is bundled separately. There are 3 types of macros: 1. for the declaration of protypes: to use in a header file for a public declaration, or as a forward declaration in the souce file for private declaration. 2. for the declaration of the implementation: always to use in a source file. 3. for the invokation of the functions. The methods are declarable public or private via the second argument of the declaration macros. List of currently implemented methods: - LINKED_LIST_: - APPEND: insert a node at the end of the list. - PREPEND: insert a node at the beginning of the list. - INSERT_BEFORE: insert a node before the given node. - POP_FRONT: remove the first node of the list. - POP_BACK: remove the last node of the list. - REMOVE: remove the given node from the list. - LINKED_LIST_MERGE_SORT: a merge sort implementation. --- include/double-linked-list.h | 313 +++++++++++++++++++++++++ libiberty/Makefile.in | 1 + libiberty/testsuite/Makefile.in | 12 +- libiberty/testsuite/test-linked-list.c | 244 +++++++++++++++++++ 4 files changed, 569 insertions(+), 1 deletion(-) create mode 100644 include/double-linked-list.h create mode 100644 libiberty/testsuite/test-linked-list.c diff --git a/include/double-linked-list.h b/include/double-linked-list.h new file mode 100644 index 00000000000..4bd41933d71 --- /dev/null +++ b/include/double-linked-list.h @@ -0,0 +1,313 @@ +/* Copyright (C) 2025 Free Software Foundation, Inc. + + This program 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 of the License, or + (at your option) any later version. + + This program 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. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + + +#pragma once + +#include + + +/*********************** + * Mutative operations * + ***********************/ + +#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_); \ + \ + EXPORT void \ + LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_); \ + \ + EXPORT void \ + LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \ + LTYPE *new_, \ + LTYPE *where); \ + \ + EXPORT LTYPE * \ + LTYPE##_pop_front (LWRAPPERTYPE *wrapper); \ + \ + EXPORT LTYPE * \ + LTYPE##_pop_back (LWRAPPERTYPE *wrapper); \ + \ + EXPORT LTYPE * \ + LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node) + + +#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append +#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend +#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before +#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front +#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back +#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove + + +#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \ +/* Note: all the mutative operations below also update the data in */ \ +/* the wrapper, i.e. first_, last_ and size. */ \ +\ +/* Append the given node new_ to the exising list. */ \ +EXPORT void \ +LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) \ +{ \ + if (wrapper->last_) \ + { \ + new_->prev = wrapper->last_; \ + wrapper->last_->next = new_; \ + } \ + else \ + { \ + new_->prev = NULL; \ + wrapper->first_ = new_; \ + } \ + wrapper->last_ = new_; \ + ++wrapper->size; \ +} \ +\ +/* Prepend the given node new_ to the exiting list. */ \ +EXPORT void \ +LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_) \ +{ \ + if (wrapper->first_ == NULL) \ + wrapper->last_ = new_; \ + else \ + { \ + new_->next = wrapper->first_; \ + wrapper->first_->prev = new_; \ + } \ + wrapper->first_ = new_; \ + ++wrapper->size; \ +} \ +\ +/* Insert the given node new_ after where in the existing list. */ \ +/* If where == NULL, the insertion is equivalent to an append. */ \ +/* If where == first_, the insertion is equivalent to a prepend. */ \ +EXPORT void \ +LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \ + LTYPE *new_, \ + LTYPE *where) \ +{ \ + if (where == wrapper->first_) \ + LTYPE##_prepend (wrapper, new_); \ + else if (where == NULL) \ + LTYPE##_append (wrapper, new_); \ + else \ + { \ + where->prev->next = new_; \ + new_->prev = where->prev; \ + where->prev = new_; \ + new_->next = where; \ + ++wrapper->size; \ + } \ +} \ +\ +/* Pop the first node of the list. */ \ +EXPORT LTYPE * \ +LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \ +{ \ + LTYPE *front_node = wrapper->first_; \ + if (front_node != NULL) \ + { \ + wrapper->first_ = front_node->next; \ + if (front_node->next != NULL) \ + { \ + front_node->next->prev = NULL; \ + front_node->next = NULL; \ + } \ + if (wrapper->last_ == front_node) \ + wrapper->last_ = NULL; \ + --wrapper->size; \ + } \ + return front_node; \ +} \ +\ +/* Pop the last node of the list. */ \ +EXPORT LTYPE * \ +LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \ +{ \ + LTYPE *back_node = wrapper->last_; \ + if (back_node != NULL) \ + { \ + wrapper->last_ = back_node->prev; \ + if (back_node->prev != NULL) \ + { \ + back_node->prev->next = NULL; \ + back_node->prev = NULL; \ + } \ + if (wrapper->first_ == back_node) \ + wrapper->first_ = NULL; \ + --wrapper->size; \ + } \ + return back_node; \ +} \ +\ +/* Remove the given node from the existing list, and return the */ \ +/* previous node. */ \ +EXPORT LTYPE * \ +LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node) \ +{ \ + LTYPE *previous = NULL; \ + \ + if (node->prev != NULL) \ + { \ + node->prev->next = node->next; \ + if (node->next == NULL) \ + wrapper->last_ = node->prev; \ + else \ + node->next->prev = node->prev; \ + previous = node->prev; \ + --wrapper->size; \ + } \ + else \ + LTYPE##_pop_front (wrapper); \ + \ + node->next = NULL; \ + node->prev = NULL; \ + \ + return previous; \ +} + + +/*********** + * Sorting * + ***********/ + +#define _LINKED_LIST_MERGE_SORT(LTYPE) _##LTYPE##_merge_sort + +#define LINKED_LIST_MERGE_SORT(LTYPE) LTYPE##_merge_sort + +#define _LINKED_LIST_MERGE_SORT_PROTOTYPE(LTYPE, EXPORT) \ + EXPORT LTYPE * \ + _##LTYPE##_merge_sort (LTYPE *node, int (*fn_cmp)(LTYPE *, LTYPE *)) + +#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, int (*fn_cmp)(LTYPE *, LTYPE *)) + +#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \ + \ +static LTYPE * \ +_##LTYPE##_merge_sort_compute_turtle (LTYPE *node) \ +{ \ + if (node == NULL) \ + return node; \ + \ + LTYPE *turtle = node, *hare = node->next; \ + while (hare != NULL && hare->next != NULL) \ + { \ + turtle = turtle->next; \ + hare = hare->next->next; \ + } \ + return turtle; \ +} \ + \ +static LTYPE * \ +_##LTYPE##_merge_sort_merge (LTYPE *l_left, LTYPE *l_right, \ + int (*fn_cmp) (LTYPE *, LTYPE *)) \ +{ \ + if (l_left == NULL) \ + return l_right; \ + else if (l_right == NULL) \ + return l_left; \ + \ + LTYPE *l_out, *current = NULL; \ + \ + LTYPE * _update (LTYPE *n) \ + { \ + if (current == NULL) \ + { \ + current = n; \ + l_out = current; \ + n->prev = NULL; \ + } \ + else \ + { \ + current->next = n; \ + n->prev = current; \ + current = n; \ + } \ + \ + return n->next; \ + } \ + \ + LTYPE *l_l = l_left, *l_r = l_right; \ + while (l_l != NULL && l_r != NULL) \ + { \ + int cmp = fn_cmp (l_l, l_r); \ + if (cmp <= 0) \ + l_l = _update (l_l); \ + else \ + l_r = _update (l_r); \ + } \ + \ + for (; l_l != NULL; l_l = l_l->next) \ + { \ + current->next = l_l; \ + l_l->prev = current; \ + current = current->next; \ + } \ + \ + for (; l_r != NULL; l_r = l_r->next) \ + { \ + current->next = l_r; \ + l_r->prev = current; \ + current = current->next; \ + } \ + \ + return l_out; \ +} \ + \ +/* Merge sort implementation taking the first node of the list to */ \ +/* sort, and the comparison function. Returns the first node of the */ \ +/* sorted list. */ \ +/* Note: use this if you don't care about updating the information */ \ +/* in the wrapper. */ \ +EXPORT LTYPE * \ +_##LTYPE##_merge_sort (LTYPE *node, int (*fn_cmp)(LTYPE *, LTYPE *)) \ +{ \ + assert (fn_cmp != NULL); \ + if (node == NULL) \ + return NULL; \ + else if (node->next == NULL) \ + return node; \ + \ + LTYPE *left_end = _##LTYPE##_merge_sort_compute_turtle (node); \ + LTYPE *left_begin = node; \ + LTYPE *right_begin = left_end->next; \ + /* break the list. */ \ + left_end->next = NULL; \ + right_begin->prev = NULL; \ + \ + left_begin = _##LTYPE##_merge_sort (left_begin, fn_cmp); \ + right_begin = _##LTYPE##_merge_sort (right_begin, fn_cmp); \ + return _##LTYPE##_merge_sort_merge (left_begin, right_begin, fn_cmp); \ +} \ + \ +/* Merge sort wrapper that the end-user should be using as it updates */ \ +/* the first_ and last_ metadata of the list in wrapper as well. */ \ +/* If the user does not want to pay the cost of the update of the */ \ +/* data, it can directly use _##LTYPE##_merge_sort_merge. */ \ +EXPORT void \ +LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, int (*fn_cmp)(LTYPE *, LTYPE *)) \ +{ \ + wrapper->first_ = _##LTYPE##_merge_sort (wrapper->first_, fn_cmp); \ + \ + if (wrapper->first_ == NULL || wrapper->first_->next == NULL) \ + wrapper->last_ = wrapper->first_; \ + else \ + for (LTYPE *node = wrapper->first_; \ + node != NULL; \ + node = node->next) \ + wrapper->last_ = node; \ +} diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in index b11df756b4b..a92491ca4cf 100644 --- a/libiberty/Makefile.in +++ b/libiberty/Makefile.in @@ -236,6 +236,7 @@ CONFIGURED_OFILES = ./asprintf.$(objext) ./atexit.$(objext) \ INSTALLED_HEADERS = \ $(INCDIR)/ansidecl.h \ $(INCDIR)/demangle.h \ + $(INCDIR)/double-linked-list.h \ $(INCDIR)/dyn-string.h \ $(INCDIR)/fibheap.h \ $(INCDIR)/floatformat.h \ diff --git a/libiberty/testsuite/Makefile.in b/libiberty/testsuite/Makefile.in index 2b0883c7630..f3aa5f7f236 100644 --- a/libiberty/testsuite/Makefile.in +++ b/libiberty/testsuite/Makefile.in @@ -45,7 +45,8 @@ all: check: @CHECK@ really-check: check-cplus-dem check-d-demangle check-rust-demangle \ - check-pexecute check-expandargv check-strtol + check-pexecute check-expandargv check-strtol \ + check-linked-list # Run some tests of the demangler. check-cplus-dem: test-demangle $(srcdir)/demangle-expected @@ -69,6 +70,10 @@ check-expandargv: test-expandargv check-strtol: test-strtol ./test-strtol +# Check the linked list functionality +check-linked-list: test-linked-list + ./test-linked-list + # Run the demangler fuzzer fuzz-demangler: demangler-fuzzer ./demangler-fuzzer @@ -90,6 +95,10 @@ test-strtol: $(srcdir)/test-strtol.c ../libiberty.a $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-strtol \ $(srcdir)/test-strtol.c ../libiberty.a +test-linked-list: $(srcdir)/test-linked-list.c + $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-linked-list \ + $(srcdir)/test-linked-list.c + demangler-fuzzer: $(srcdir)/demangler-fuzzer.c ../libiberty.a $(TEST_COMPILE) -o demangler-fuzzer \ $(srcdir)/demangler-fuzzer.c ../libiberty.a @@ -104,6 +113,7 @@ mostlyclean: rm -f test-pexecute rm -f test-expandargv rm -f test-strtol + rm -f test-linked-list rm -f demangler-fuzzer rm -f core clean: mostlyclean diff --git a/libiberty/testsuite/test-linked-list.c b/libiberty/testsuite/test-linked-list.c new file mode 100644 index 00000000000..0a249eca294 --- /dev/null +++ b/libiberty/testsuite/test-linked-list.c @@ -0,0 +1,244 @@ +#include +#include +#include + +#include "double-linked-list.h" + +#ifndef EXIT_SUCCESS +#define EXIT_SUCCESS 0 +#endif + +#ifndef EXIT_FAILURE +#define EXIT_FAILURE 1 +#endif + +/* Implementation */ + +typedef int T; + +typedef struct ListNodeType +{ + T value; + struct ListNodeType *next; + struct ListNodeType *prev; +} ListNodeType; + +ListNodeType * l_new_node (T value) +{ + ListNodeType *n = malloc (sizeof (ListNodeType)); + n->next = NULL; + n->prev = NULL; + n->value = value; + return n; +} + +typedef struct LinkedListWrapperType +{ + ListNodeType *first_; + ListNodeType *last_; + size_t size; +} LinkedListWrapperType; + +int compare_nodes (ListNodeType *n1, ListNodeType *n2) +{ + if (n1->value == n2->value) + return 0; + else if (n1->value < n2->value) + return -1; + else + return 1; +} + +LINKED_LIST_MUTATIVE_OPS_DECL (LinkedListWrapperType, ListNodeType, static) +LINKED_LIST_MERGE_SORT_DECL (LinkedListWrapperType, ListNodeType, static) + +ListNodeType * find_last_node (ListNodeType *head) +{ + if (head == NULL) + return NULL; + + ListNodeType *n = head; + while (n->next != NULL) + n = n->next; + + return n; +} + +void l_print (ListNodeType *node) +{ + for (ListNodeType *l = node; l != NULL; l = l->next) + printf ("%d ", l->value); + printf ("\n"); +} + +void l_reverse_print (ListNodeType *last_node) +{ + for (ListNodeType *l = last_node; l != NULL; l = l->prev) + printf ("%d ", l->value); + printf ("\n"); +} + +struct test_data_t +{ + T const *content; + size_t size; +}; + +bool run_test (const struct test_data_t *expect, + LinkedListWrapperType *current, + bool reversed) +{ + ListNodeType *node = (reversed) ? current->last_ : current->first_; + bool passed = true; + for (int i=0; isize && node != NULL; ++i) + { + if (reversed) + { + if (expect->content[expect->size - 1 - i] != node->value) + { + printf ("FAIL: mismatching expected (%d) VS current (%d).\n", + expect->content[expect->size - 1 - i], node->value); + passed = false; + } + if (node->prev == NULL && current->first_ != node) + { + printf ("FAIL: first_ is not matching the first node.\n"); + passed = false; + } + } + else + { + if (expect->content[i] != node->value) + { + printf ("FAIL: mismatching expected (%d) VS current (%d).\n", + expect->content[i], node->value); + passed = false; + } + if (node->next == NULL && current->last_ != node) + { + printf ("FAIL: last_ is not matching the last node.\n"); + passed = false; + } + } + + if (!passed) + return false; + + if (reversed) + node = node->prev; + else + node = node->next; + } + + if (node != NULL) + { + printf ("FAIL: the list is longer than expected.\n"); + passed = false; + } + if (expect->size != current->size) + { + printf ("FAIL: size (%d) is not matching the real size of the list (%d).\n", + current->size, expect->size); + passed = false; + } + + return passed; +} + +bool check(const char *op, + const struct test_data_t *expect, + LinkedListWrapperType *wrapper) +{ + bool success = true; + bool res; + + l_print (wrapper->first_); + res = run_test (expect, wrapper, false); + printf ("%s: test-linked-list::%s: check forward conformity\n", + res ? "PASS": "FAIL", op); + success &= res; + + l_reverse_print (wrapper->last_); + res = run_test (expect, wrapper, true); + printf ("%s: test-linked-list::%s: check backward conformity\n", + res ? "PASS": "FAIL", op); + success &= res; + + return success; +} + +const int EXPECT_0 [] = { 10, 4, 3, 1, 9, 2 }; +const int EXPECT_1 [] = { 1, 2, 3, 4, 9, 10 }; +const int EXPECT_2 [] = { 11, 1, 2, 3, 4, 9, 10 }; +const int EXPECT_3 [] = { 11, 1, 2, 3, 4, 9, 8, 10 }; +const int EXPECT_4 [] = { 11, 2, 3, 4, 9, 8, 10 }; +const int EXPECT_5 [] = { 2, 3, 4, 8, 9, 10, 11 }; +const int EXPECT_6 [] = { 3, 4, 8, 9, 10, 11 }; +const int EXPECT_7 [] = { 3, 4, 8, 9, 10 }; +const struct test_data_t test_data[] = { + { .content = EXPECT_0, .size = sizeof(EXPECT_0) / sizeof(EXPECT_0[0]) }, + { .content = EXPECT_1, .size = sizeof(EXPECT_1) / sizeof(EXPECT_1[0]) }, + { .content = EXPECT_2, .size = sizeof(EXPECT_2) / sizeof(EXPECT_2[0]) }, + { .content = EXPECT_3, .size = sizeof(EXPECT_3) / sizeof(EXPECT_3[0]) }, + { .content = EXPECT_4, .size = sizeof(EXPECT_4) / sizeof(EXPECT_4[0]) }, + { .content = EXPECT_5, .size = sizeof(EXPECT_5) / sizeof(EXPECT_5[0]) }, + { .content = EXPECT_6, .size = sizeof(EXPECT_6) / sizeof(EXPECT_6[0]) }, + { .content = EXPECT_7, .size = sizeof(EXPECT_7) / sizeof(EXPECT_7[0]) }, +}; + +int main (void) +{ + int failures = 0; + + LinkedListWrapperType wrapper = { + .first_ = NULL, + .last_ = NULL, + .size = 0, + }; + + /* Append nodes. */ + LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (10)); + LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (4)); + LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (3)); + LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (1)); + LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (9)); + LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (2)); + + failures += ! check ("append", &test_data[0], &wrapper); + + /* Sort nodes (without updating wrapper). */ + wrapper.first_ = + _LINKED_LIST_MERGE_SORT(ListNodeType) (wrapper.first_, compare_nodes); + wrapper.last_ = find_last_node (wrapper.first_); + + failures += ! check ("sort", &test_data[1], &wrapper); + + /* Save a reference to this node for later. */ + ListNodeType *n_to_remove = wrapper.first_; + + /* Prepend node. */ + LINKED_LIST_PREPEND(ListNodeType) (&wrapper, l_new_node (11)); + failures += ! check ("prepend", &test_data[2], &wrapper); + + /* Insert node. */ + LINKED_LIST_INSERT_BEFORE(ListNodeType) (&wrapper, l_new_node (8), wrapper.last_); + failures += ! check ("insert_before", &test_data[3], &wrapper); + + /* Remove a node. */ + LINKED_LIST_REMOVE(ListNodeType) (&wrapper, n_to_remove); + failures += ! check ("remove", &test_data[4], &wrapper); + + /* Sort nodes. */ + LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes); + failures += ! check ("sort", &test_data[5], &wrapper); + + /* Pop front. */ + LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper); + failures += ! check ("pop_front", &test_data[6], &wrapper); + + /* Pop back. */ + LINKED_LIST_POP_BACK(ListNodeType) (&wrapper); + failures += ! check ("pop_back", &test_data[7], &wrapper); + + exit (failures ? EXIT_FAILURE : EXIT_SUCCESS); +}