From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca by simark.ca with LMTP id 18mAIMDAb2hDoTAAWB0awg (envelope-from ) for ; Thu, 10 Jul 2025 09:31:44 -0400 Authentication-Results: simark.ca; dkim=pass (1024-bit key; unprotected) header.d=arm.com header.i=@arm.com header.a=rsa-sha256 header.s=selector1 header.b=GP+Qi5fr; dkim=pass (1024-bit key) header.d=arm.com header.i=@arm.com header.a=rsa-sha256 header.s=selector1 header.b=GP+Qi5fr; dkim-atps=neutral Received: by simark.ca (Postfix, from userid 112) id 6C0EF1E11C; Thu, 10 Jul 2025 09:31:44 -0400 (EDT) X-Spam-Checker-Version: SpamAssassin 4.0.1 (2024-03-25) on simark.ca X-Spam-Level: X-Spam-Status: No, score=-9.1 required=5.0 tests=ARC_SIGNED,ARC_VALID,BAYES_00, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_VALIDITY_CERTIFIED,RCVD_IN_VALIDITY_RPBL, RCVD_IN_VALIDITY_SAFE autolearn=ham autolearn_force=no version=4.0.1 Received: from server2.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 ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPS id A67661E089 for ; Thu, 10 Jul 2025 09:31:41 -0400 (EDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 02178385AC0A for ; Thu, 10 Jul 2025 13:31:41 +0000 (GMT) Received: from MRWPR03CU001.outbound.protection.outlook.com (mail-francesouthazlp170110003.outbound.protection.outlook.com [IPv6:2a01:111:f403:c207::3]) by sourceware.org (Postfix) with ESMTPS id 77D3D3857354 for ; Thu, 10 Jul 2025 13:31:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 77D3D3857354 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 77D3D3857354 Authentication-Results: server2.sourceware.org; arc=pass smtp.remote-ip=2a01:111:f403:c207::3 ARC-Seal: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1752154272; cv=pass; b=hp8g7fYbo16xAhGVD5mp8sWjMgs/azG4fDmDIEBjdUTQREQHx/XVhftZDY82f7QIXwb1gOw4BMPFukpqmBrVNWE213ilQuuuQHEXJMuJZ3Q1IBkKnPngy0AHaQQ/yWWBA+2+IlJXlauJ6HKAmoBn+qjbFm/Qi6uOmsjbfLogLPo= ARC-Message-Signature: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1752154272; c=relaxed/simple; bh=kZWmnOD2CmeGYXb+tG6lJ8a9bi1AlPZAFaybtoKAUIA=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=m8IP3MesX1qW064bWysxr3saD3PDf41mtLnTHeDug/ZFQA5/7sxjgIpUPZ3qSAxIc5/QxvKDrwAc+Yz+pgV3K1q/ZUmioS0XsEDCQY78vPAA4FV68gDNCEXixwVsj8sFisPl1m91/KTbNwEtdOrRzU/aKDQNdmqpZiGdQjZo0kM= ARC-Authentication-Results: i=3; server2.sourceware.org ARC-Seal: i=2; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=pass; b=npO+iQcxHeiHUmKinSZYF39HsNhOn00XoijIxF0szoxCa/eGn4I/HKjbigbBnMLlVGRZ9ysJc8FTfpCYgUTib3hWvlgC+xbQWjbcLfulD1XbFIJhSlBmWDPiD1vc2W3GcbDnArmuBVJ7F0cSj88x3JEkPcJxtHnjcX4+shB7tcECr55RIwQknJQV3hlqN0YDRPaQLgOqdMVPy8BUIh+y1l0nyrC4g0ZZE0Q8aldzPOMhGtMes7qWveaUb0UN6m2HTwmENvs585lQF9HSP2QRhMERKO9gPF4e1iVEmqbJpikrioNXKmpxKHE+9Z3KP8WXjCMVP8wbhlwLgQrxQm5Kbg== 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=jsndZ9ETxWUEQmk6JB9EPm1XJifJC1TDhJh9oGYdv00=; b=XAdPwEQP30fdMoL30eUeZW2Covds0bkR1ShE0qxgWZVTVDAS76Zt2ZV4z49AUOmNckh+/fs1HDPo+Bab6m87iBUxGoeVIxrsekqGVInYrsrl0JE1dWdFoGuPFfMdrZHTbUY064kzmZtb6qO379SvrPQ8AuLq3pseFy4vnMtDntX1R5Y5r4eyjnQJ8/RIiGsj5+2avPmSczBFBgSQxSyZ3LhNldn6yAnAaUH7OBpnTYyo9N+r8do/X4HpHh87zVAIppJjOmcphunz8rl6Q7efVUerebjS543UESK8mEGlAxSkw7ntyE9xO5nD4EzyjnPzfFAS2+xn8RIXXZ18+ZrQUQ== ARC-Authentication-Results: i=2; mx.microsoft.com 1; spf=pass (sender ip is 4.158.2.129) 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=1 ltdi=1 spf=[1,1,smtp.mailfrom=arm.com] dmarc=[1,1,header.from=arm.com]) 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=jsndZ9ETxWUEQmk6JB9EPm1XJifJC1TDhJh9oGYdv00=; b=GP+Qi5frrgT/mnm0sRkD07U7xptzTCDB4qvWdgNoWMVzk7LtO+H1Goq6PpKhuiluBfU7b8Rywvy5NjHfDmaoFqV9dSjOVZfSQo01lbzg4CWhIv83LCrAPSB6MatYRUOsDmEUsAhQ+nq/YR1RLC9ykOgKjNtYidbgTYNPC+pI4jw= Received: from AM0PR08CA0021.eurprd08.prod.outlook.com (2603:10a6:208:d2::34) by AM8PR08MB5764.eurprd08.prod.outlook.com (2603:10a6:20b:1d2::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8901.27; Thu, 10 Jul 2025 13:31:09 +0000 Received: from AMS1EPF0000004E.eurprd04.prod.outlook.com (2603:10a6:208:d2:cafe::3b) by AM0PR08CA0021.outlook.office365.com (2603:10a6:208:d2::34) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.8922.22 via Frontend Transport; Thu, 10 Jul 2025 13:31:09 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 4.158.2.129) 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 4.158.2.129 as permitted sender) receiver=protection.outlook.com; client-ip=4.158.2.129; helo=outbound-uk1.az.dlp.m.darktrace.com; pr=C Received: from outbound-uk1.az.dlp.m.darktrace.com (4.158.2.129) by AMS1EPF0000004E.mail.protection.outlook.com (10.167.16.139) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.8922.22 via Frontend Transport; Thu, 10 Jul 2025 13:31:07 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=CP8eqNz9wpXHl953HQw1krRiPkJ28UNLG0MsYVv7gEG8+1Vc2DBC9cesyY9tZ+Yf7sh3fEfjekwAlCEPAYwqW+9uLF3J3r1FIiJsIpcenQdqprmCLoDfluZKANpxjLfeA6kDXhcZxvOrccF2+hM9s31HWPAZMmELD/CHvOqkX1OOk2P6vKggVYEyCZOIXJAsfH3vf+m7xwZgMYs8MS/vcA4tXPeLW5GS2c6T9pGDv1f0lQ5jKMb12myqfB0W2rsdkSqK3AVJlbzGnwfIecBF71S649csQMZ2dacMPKpZp9kOg8ypklVgTF0aGMoKPYJgyhuUNmVpA4xZT3ejco4Q3Q== 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=jsndZ9ETxWUEQmk6JB9EPm1XJifJC1TDhJh9oGYdv00=; b=nWmZVW7Rs+ATNA0EZmIlg+JmUn1e+LD/khoEshJxn3q1Ob4lg+2S0tSNFa16GivBQsbYJx5Xp459Osmb6gGSjO9zIPB2G2QAOe4RKCavex426fdv9AdZBB6wHZOwOIHdW7fCI5/ZubcMaIfCvD3fiR6f5Comaem2UCx9LxcUNh4pD0DV+YrkJyuup1HfNWfw6vf1O8IN0zkec9y0zpdw1WSi/EljRCRxsUUIDxd4173p/Z4CVtVWBZV+2QKa8W7K5wYskbgO68lDfR0vJ6IvfPqvhEiAunI5hbkbnoAcQYsZMni5525D2rp2E9yx926vnXeuCFfzwdPQo2T0JmdUzg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 172.205.89.229) smtp.rcpttodomain=sourceware.org smtp.mailfrom=arm.com; dmarc=pass (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=jsndZ9ETxWUEQmk6JB9EPm1XJifJC1TDhJh9oGYdv00=; b=GP+Qi5frrgT/mnm0sRkD07U7xptzTCDB4qvWdgNoWMVzk7LtO+H1Goq6PpKhuiluBfU7b8Rywvy5NjHfDmaoFqV9dSjOVZfSQo01lbzg4CWhIv83LCrAPSB6MatYRUOsDmEUsAhQ+nq/YR1RLC9ykOgKjNtYidbgTYNPC+pI4jw= Received: from AS4PR09CA0028.eurprd09.prod.outlook.com (2603:10a6:20b:5d4::16) by DU0PR08MB8907.eurprd08.prod.outlook.com (2603:10a6:10:47f::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8901.22; Thu, 10 Jul 2025 13:30:35 +0000 Received: from AMS0EPF00000196.eurprd05.prod.outlook.com (2603:10a6:20b:5d4:cafe::56) by AS4PR09CA0028.outlook.office365.com (2603:10a6:20b:5d4::16) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.8922.23 via Frontend Transport; Thu, 10 Jul 2025 13:30:35 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 172.205.89.229) smtp.mailfrom=arm.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 172.205.89.229 as permitted sender) receiver=protection.outlook.com; client-ip=172.205.89.229; helo=nebula.arm.com; pr=C Received: from nebula.arm.com (172.205.89.229) by AMS0EPF00000196.mail.protection.outlook.com (10.167.16.217) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.20.8922.22 via Frontend Transport; Thu, 10 Jul 2025 13:30:35 +0000 Received: from AZ-NEU-EX06.Arm.com (10.240.25.134) by AZ-NEU-EX05.Arm.com (10.240.25.133) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.39; Thu, 10 Jul 2025 13:30:34 +0000 Received: from PW070M4K.arm.com (10.57.67.98) by mail.arm.com (10.240.25.134) with Microsoft SMTP Server id 15.1.2507.39 via Frontend Transport; Thu, 10 Jul 2025 13:30:33 +0000 From: Matthieu Longo To: CC: Matthieu Longo Subject: [PATCH] libiberty: sync with gcc Date: Thu, 10 Jul 2025 14:30:30 +0100 Message-ID: <20250710133030.1612694-1-matthieu.longo@arm.com> X-Mailer: git-send-email 2.50.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-EOPAttributedMessage: 1 X-MS-TrafficTypeDiagnostic: AMS0EPF00000196:EE_|DU0PR08MB8907:EE_|AMS1EPF0000004E:EE_|AM8PR08MB5764:EE_ X-MS-Office365-Filtering-Correlation-Id: 135cda34-e122-4e29-8bdd-08ddbfb606da x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; ARA:13230040|36860700013|82310400026|1800799024|376014; X-Microsoft-Antispam-Message-Info-Original: =?us-ascii?Q?4t8j1QkBNGOwdLyCwU8P1YhAR3KwWI1D1Q22pNqFq2V/KAYNv8yUi3b6cO1g?= =?us-ascii?Q?8yaLon99GNWSjN3g7s5O/M5eW44CEhI8hbRemqlMGeEeWASWlwgpzVZiWooD?= =?us-ascii?Q?HDxZgKdC6ikXeUQ8HiymbXFTWqALZ1Yr9yX6E4WoszKubLrCrkFxje/VrLQN?= =?us-ascii?Q?dJCNvxQi9fqGIiH/ND0q93tsyqyXNDNTxAPYLnHJiJE9sIrFVwIJ2H5Akjar?= =?us-ascii?Q?dce1YGORUWIXmRvXbXiHMkV8M+DcPSq4ZWY4thVkx2iGoDz8lVJeByBbn/yW?= =?us-ascii?Q?lpktUbFUmvfRzvl17JCLI1+KXnMxJBKYXu1kM0FNZhW0GzMKugqxFKum9wYH?= =?us-ascii?Q?DQ27HdarbyXVlwYBoUZXOzt793Un6F7PtCzgqueLArCdaH1Io0qxqEy8unE3?= =?us-ascii?Q?WNazqUK1uaZRlTonRpRnnL0Hso2ac7lmr3LxPOCydIjpVhh6C0NM8XTI/BIu?= =?us-ascii?Q?cvK97OuBJZKMm/Q8s4/PD4Pd3YtrqQkDVLoVVYpaoqydePR8h6W2wJWEm2KW?= =?us-ascii?Q?xlL88pAbZjfXHQlIVRR+/qperNkc3JlUGvyTuGhsrNSy7hlnOwA/RIJ6KH9R?= =?us-ascii?Q?8CTSvE1KO0MhPFSYMLHJVGdh2353c6HPouqIsKHEKvizcSrEriXBw+v/7QBL?= =?us-ascii?Q?pm3bStRX6enkemeVnM7ZVpBikCy9aM5nwwuWlnIsEHL5A55dqY4GNUd3nS29?= =?us-ascii?Q?s8H5lqgoeczT9pRR1sgB3uuR7qbUUmv4wjbzUW8E8OYle+dhWz8crwC19YAK?= =?us-ascii?Q?h54CfEfVSAOaLzpgzhfZzQbsBi98kUjrAwOQpDEvijNhhRJaQzzMZ6735FQ1?= =?us-ascii?Q?P+5VtI7t1sfBBYjKnNjmBA4RXMGTeQ659sZdmHeQ/eX/7iEnVvE9QEf+O3YA?= =?us-ascii?Q?BzDCKewa1xyjhaq3RYJ09sKuAqTEFsxC2bFECbtOXtkzCHYO/y5MHMv9A5zo?= =?us-ascii?Q?6GrTOg4ObwPjDzXH+5gW3jY1wVhOYfGQGVn6CUGY+9ARrSP1FhCg5oZE2Pm9?= =?us-ascii?Q?ksb+8IoktQIT/XFeF7TeipQJXX6zKEAMXKKLfOCpRVrn8rMNr9ToH5FFMN0D?= =?us-ascii?Q?wwSVmz3kxQ8utcAYHiLAg0IkP7ZvUWCWI+wu6dM6IxO2DoBtPxDX9EwkLMkw?= =?us-ascii?Q?wKAqWy2lJYnKVXQchqMy4byz2wnwdw/rfo4ihgOKUxKOZnbklahT3pzFpbCM?= =?us-ascii?Q?Zaz7Ykf2VbgfLN/MmxqhiVFAtbEGaT+GHY+SpGB0A/0V98NiCVzpIEItTeNZ?= =?us-ascii?Q?7YAfol6BIKA6J0LOeCD8YMOx5DgNG6K41aVAhkiOCyEeEZcvIpgYqBqyPYyP?= =?us-ascii?Q?jpgLuAeqjDpu2uLOS7BKZmX1Zoepcunvuf+p7FJ6FUMPHDY+iq0vyATq+kQ5?= =?us-ascii?Q?8qzzt9vScVvkNg3GdjYAai9T8VDNCo1TcWcM0LYVOo1CKOLJogqZgMK9gbXR?= =?us-ascii?Q?khAFixbtcwRGeS9/+YvUIHgGTBuaT5DKrpF5T6ki8tDVEZiH9mCeYhg0lbII?= =?us-ascii?Q?a2Bhe/F8Z/CVxTWWD0V/MO0NMiBBTXYJyHOu8IQ6Qadu+rgZHe55GK+Czw?= =?us-ascii?Q?=3D=3D?= 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)(36860700013)(82310400026)(1800799024)(376014); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU0PR08MB8907 X-MS-Exchange-Transport-CrossTenantHeadersStripped: AMS1EPF0000004E.eurprd04.prod.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 8b521ee0-abb2-4755-656d-08ddbfb5f388 X-Microsoft-Antispam: BCL:0; ARA:13230040|35042699022|1800799024|82310400026|376014|36860700013|14060799003; X-Microsoft-Antispam-Message-Info: =?us-ascii?Q?MFMrkKZR5oDQ/Qta+UKy82RDb2J8GhgQhrC7kTmZVKHCb2mo3KnJ9+R3zalq?= =?us-ascii?Q?i+2ZqZSL+AHA0MhWOU9lPeMaZvWqMfjjE4i2blgBlzbofqBgNcJzEImzf9KN?= =?us-ascii?Q?81h8SqUT+NqHnDyTHKGEEcPiCicXSi5sFoF6YNjnhLnM/W+V4AkdgAJ7Hfft?= =?us-ascii?Q?kwSgyoGMag74J9p/rLnzkF8iLcGEYzAkZEcDGbOaNoVRimVQpcKiAxfF2Afj?= =?us-ascii?Q?/41e4YJL9ebk60NNwN9z4Tkb4LM0YpP0PUtBedFVMUgJ4rpVdA/Lp0oomAmZ?= =?us-ascii?Q?ZVx5W7LGSbFmALEyTc6eFYncZ0MbIsnM/0mkbNuPaCtM2s30IENF4qmqR29H?= =?us-ascii?Q?bH2WJNvBsiCClwDoVuAU3bF9PhzLxN7eerlZargm9MLmMVodP2UCIuBsg6sk?= =?us-ascii?Q?suGWnnyN4qojyOPGUW+1dKKzdkddtS5AZZy0fhkuJg9oSAH5pHQ0+JSVftVs?= =?us-ascii?Q?x17AfkM9sKOr3GzLJ2kP6+sJc6DNaXdcH6ZbJwdJNc45RtlOxvax3Sff3Eml?= =?us-ascii?Q?gEPzyLU7xg2qXrgPUj9OSWFwMj9GOJHVr+FP26ZfurOEtn6eij+WLoFIKOpt?= =?us-ascii?Q?9wFzyT4mPtO5QaUBNqUcMTs/EQfZxIM2MxOY3ct7AgUVco/LTtgWWvRadxxT?= =?us-ascii?Q?2V7jDFk/bv2JzBvZ6ryZqPN7KdNazahhKHiXc0NIP/QQmzVzgUkUYc1zsDsp?= =?us-ascii?Q?31qZx6us6hSAm2vc7NbrYXES0+II5nfVt2HOIBZ9+0k6KGuTvCz1Pok8PFZ9?= =?us-ascii?Q?Xfl5dohXtSQNiuwPHde5dS/OQMPQWsVZk4MBOU2BQyR21Bhz2U295fQpbEM3?= =?us-ascii?Q?Ti6UujHnKF844DrhPrSb5xgTNqX+H4gAcf3qulYxP28wWtWrrHN2jLI+bAMA?= =?us-ascii?Q?ekwdL2FIr8J/v7fehwnf9Su0mnSn0SUq07IsiAKENkzsrr1KWcjRmEDjGn6D?= =?us-ascii?Q?zr2p7yMXJxbEaMS5SAU6dfhVp/6V18A9cHPNaVEYFX02Lqfy97I3/JvrSKPk?= =?us-ascii?Q?lfmsYv8fkn29KUczx8rsRz3vLMtrEUMvctDMqgy85QORCKWyNnPbBmbhKKKl?= =?us-ascii?Q?z0Es774eNgFWjWxRrvQJ8TNHCUkQ1w6yV00NJ5eDJtozRdT9TteAbiR9Zlw2?= =?us-ascii?Q?kHhB3aRiejD0ik6Qi1m5MTQKMBYDVaaSbSi+wdRQMu2iBJBZ5xoFdfV8Ap6K?= =?us-ascii?Q?H+zq42g9L1LNpM/bYH+0awGTxRsFq5aDaqFu6VVghVPbdbIbFVqO68Jc3mRV?= =?us-ascii?Q?9VTtofkzOIg8ftQ2rApMie+JtVxidLXej8g8EBnprauoKw0DHryg1yVeFYsq?= =?us-ascii?Q?0hLdAyDJzrchzQ1mHNNjrReY/2xUjF2HR4nDHs2FQA5WGY01ra4J09Av0DPQ?= =?us-ascii?Q?Sw2tbYngCczMr0+AcU1AgFLGwj2qeKBb1/hVSPNbPrLBNHsDmHKzXhD/Fb9B?= =?us-ascii?Q?N2PgSw+YCPlHRpw7jZZshwJoNbrgNDAlqsXgfsO3ONZLQ2hQJJuq3fJ7TIDo?= =?us-ascii?Q?xDED57U9pL/q58Q9e8V+jhO09fIga/+fg8etQ0VNNijaLciGyfwG2BgWiA?= =?us-ascii?Q?=3D=3D?= X-Forefront-Antispam-Report: CIP:4.158.2.129; CTRY:GB; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:outbound-uk1.az.dlp.m.darktrace.com; PTR:InfoDomainNonexistent; CAT:NONE; SFS:(13230040)(35042699022)(1800799024)(82310400026)(376014)(36860700013)(14060799003); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 10 Jul 2025 13:31:07.5989 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 135cda34-e122-4e29-8bdd-08ddbfb606da X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[4.158.2.129]; Helo=[outbound-uk1.az.dlp.m.darktrace.com] X-MS-Exchange-CrossTenant-AuthSource: AMS1EPF0000004E.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM8PR08MB5764 X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gdb-patches-bounces~public-inbox=simark.ca@sourceware.org Import the following commits from GCC as of r16-2170-g2f2e9bcfb0fd9c: 0fd98b6f9f2 libiberty: add routines to handle type-sensitive doubly linked lists --- include/doubly-linked-list.h | 447 ++++++++++++++++++ libiberty/Makefile.in | 1 + libiberty/testsuite/Makefile.in | 12 +- libiberty/testsuite/test-doubly-linked-list.c | 269 +++++++++++ 4 files changed, 728 insertions(+), 1 deletion(-) create mode 100644 include/doubly-linked-list.h create mode 100644 libiberty/testsuite/test-doubly-linked-list.c diff --git a/include/doubly-linked-list.h b/include/doubly-linked-list.h new file mode 100644 index 00000000000..3f5ea2808f9 --- /dev/null +++ b/include/doubly-linked-list.h @@ -0,0 +1,447 @@ +/* Manipulate doubly linked lists. + 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 . */ + + +#ifndef _DOUBLY_LINKED_LIST_H +#define _DOUBLY_LINKED_LIST_H + +/* Doubly linked list implementation enforcing typing. + + This implementation of doubly linked list tries to achieve the enforcement of + typing similarly to C++ templates, but without encapsulation. + + All the functions are prefixed with the type of the value: "AType_xxx". + Some functions are prefixed with "_AType_xxx" and are not part of the public + API, so should not be used, except for _##LTYPE##_merge_sort with a caveat + (see note above its definition). + + Each function (### is a placeholder for method name) has a macro for: + (1) its invocation LINKED_LIST_###(LTYPE). + (2) its prototype LINKED_LIST_DECL_###(A, A2, scope). To add in a header + file, or a source file for forward declaration. 'scope' should be set + respectively to 'extern', or 'static'. + (3) its definition LINKED_LIST_DEFN_###(A, A2, scope). To add in a source + file with the 'scope' set respectively to nothing, or 'static' depending + on (2). + + Data structures requirements: + - LTYPE corresponds to the node of a doubly linked list. It needs to define + attributes 'prev' and 'next' which are pointers on the type of a node. + For instance: + struct my_list_node + { + T value; + struct my_list_node *prev; + struct my_list_node *next; + }; + - LWRAPPERTYPE is a structure wrapping the nodes and others metadata (first, + last, size). + */ + + +/* Mutative operations: + - append + - prepend + - insert_before + - pop_front + - pop_back + - remove + - swap + The header and body of each of those operation can be declared individually, + or as a whole via LINKED_LIST_MUTATIVE_OPS_PROTOTYPE for the prototypes, and + LINKED_LIST_MUTATIVE_OPS_DECL for the implementations. */ + +/* Append the given node new_ to the exising list. + Precondition: prev and next of new_ must be NULL. */ +#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append + +#define LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) + +#define LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \ +EXPORT void \ +LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) \ +{ \ + if (wrapper->last == NULL) \ + wrapper->first = new_; \ + else \ + { \ + new_->prev = wrapper->last; \ + wrapper->last->next = new_; \ + } \ + wrapper->last = new_; \ + ++wrapper->size; \ +} + +/* Prepend the given node new_ to the existing list. + Precondition: prev and next of new_ must be NULL. */ +#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend + +#define LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_) + +#define LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \ +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_ before '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. */ +#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before + +#define LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \ + LTYPE *new_, \ + LTYPE *where) + +#define LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \ +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. */ +#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front + +#define LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT LTYPE * \ + LTYPE##_pop_front (LWRAPPERTYPE *wrapper) + +#define LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \ +EXPORT LTYPE * \ +LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \ +{ \ + LTYPE *front_node = wrapper->first; \ + if (front_node != NULL) \ + { \ + wrapper->first = front_node->next; \ + if (wrapper->last == front_node) \ + wrapper->last = NULL; \ + else \ + { \ + front_node->next->prev = NULL; \ + front_node->next = NULL; \ + } \ + front_node->next = NULL; \ + --wrapper->size; \ + } \ + return front_node; \ +} + +/* Pop the last node of the list. */ +#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back + +#define LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT LTYPE * \ + LTYPE##_pop_back (LWRAPPERTYPE *wrapper) + +#define LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \ +EXPORT LTYPE * \ +LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \ +{ \ + LTYPE *back_node = wrapper->last; \ + if (back_node != NULL) \ + { \ + wrapper->last = back_node->prev; \ + if (wrapper->first == back_node) \ + wrapper->first = NULL; \ + else \ + { \ + back_node->prev->next = NULL; \ + back_node->prev = NULL; \ + } \ + back_node->prev = NULL; \ + --wrapper->size; \ + } \ + return back_node; \ +} + +/* Remove the given node from the existing list, and return the previous + node. */ +#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove + +#define LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT LTYPE * \ + LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node) + +#define LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \ +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; \ + node->next = NULL; \ + node->prev = NULL; \ + --wrapper->size; \ + } \ + else \ + LTYPE##_pop_front (wrapper); \ + \ + return previous; \ +} + +/* Generic swap. */ +#define LINKED_LIST_SWAP(LTYPE) LTYPE##_swap + +#define LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2) + +/* Swap two nodes in a list. */ +#define LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \ +EXPORT void \ +LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2) \ +{ \ + LTYPE *prev1 = node1->prev; \ + LTYPE *next1 = node1->next; \ + LTYPE *prev2 = node2->prev; \ + LTYPE *next2 = node2->next; \ + \ + if (prev1 != NULL) \ + prev1->next = node2; \ + else \ + wrapper->first = node2; \ + if (prev2 != NULL) \ + prev2->next = node1; \ + else \ + wrapper->first = node1; \ + \ + if (next1 != NULL) \ + next1->prev = node2; \ + else \ + wrapper->last = node2; \ + if (next2 != NULL) \ + next2->prev = node1; \ + else \ + wrapper->last = node1; \ + \ + { \ + LTYPE *temp = node1->next; \ + node1->next = node2->next; \ + node2->next = temp; \ + } \ + { \ + LTYPE *temp = node1->prev; \ + node1->prev = node2->prev; \ + node2->prev = temp; \ + } \ +} + +/* Note: all the mutative operations below also update the data in the wrapper, + i.e. first, last and size. */ +#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT); \ + LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT); \ + LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT); \ + LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT); \ + LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT); \ + LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT); \ + LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) + +#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \ + LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) + + +/* 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) (const LTYPE *, const LTYPE *)) + +#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \ + EXPORT void \ + LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, \ + int (*fn_cmp) (const LTYPE *, const LTYPE *)) + +/* Note: all the functions and macros below starting with "_" should be + considered private. */ + +/* Compute the middle element of the list based on the turtle and hare + approach, i.e. the hare runs twice faster than the turtle. */ +#define _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE) \ +static inline 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; \ +} + +/* Append n at the end of l_out, and return the next node after n. + l_out and l_last should be ideally encapsulated into a list structure + but this is overkill for what we need here. */ +#define _MERGE_SORT_IMPL_OUT_APPEND(LTYPE) \ +static inline LTYPE * \ +LTYPE##_merge_sort_out_append_ (LTYPE **l_out, LTYPE **l_last, \ + LTYPE *n) \ +{ \ + if (*l_last == NULL) \ + { \ + *l_last = n; \ + *l_out = n; \ + n->prev = NULL; \ + } \ + else \ + { \ + (*l_last)->next = n; \ + n->prev = *l_last; \ + *l_last = n; \ + } \ + \ + return n->next; \ +} + +/* Merge two sorted lists together. + The returned value corresponds to the first element of the list. + Note: both input lists are invalidated after the call. */ +#define _MERGE_SORT_IMPL_MERGE(LTYPE) \ +static inline LTYPE * \ +LTYPE##_merge_sort_merge_ (LTYPE *l_left, LTYPE *l_right, \ + int (*fn_cmp) (const LTYPE *, const LTYPE *))\ +{ \ + if (l_left == NULL) \ + return l_right; \ + else if (l_right == NULL) \ + return l_left; \ + \ + LTYPE *l_out = NULL, *l_last = NULL; \ + \ + 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 = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_l); \ + else \ + l_r = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_r); \ + } \ + \ + LTYPE *l_remaining = (l_l != NULL) ? l_l : l_r; \ + while (l_remaining != NULL) \ + l_remaining = \ + LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_remaining); \ + \ + 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. */ +#define _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT) \ +EXPORT LTYPE * \ +LTYPE##_merge_sort_ (LTYPE *node, \ + int (*fn_cmp)(const LTYPE *, const LTYPE *)) \ +{ \ + 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. */ +#define _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT) \ +EXPORT void \ +LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, \ + int (*fn_cmp) (const LTYPE *, const 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; \ +} + +#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \ + _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE) \ + _MERGE_SORT_IMPL_OUT_APPEND(LTYPE) \ + _MERGE_SORT_IMPL_MERGE(LTYPE) \ + _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT) \ + _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT) + +#endif /* _DOUBLY_LINKED_LIST_H */ diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in index 387975daf58..d507f27a9ef 100644 --- a/libiberty/Makefile.in +++ b/libiberty/Makefile.in @@ -237,6 +237,7 @@ CONFIGURED_OFILES = ./asprintf.$(objext) ./atexit.$(objext) \ INSTALLED_HEADERS = \ $(INCDIR)/ansidecl.h \ $(INCDIR)/demangle.h \ + $(INCDIR)/doubly-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..ef549ca910a 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-doubly-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-doubly-linked-list: test-doubly-linked-list + ./test-doubly-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-doubly-linked-list: $(srcdir)/test-doubly-linked-list.c + $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-doubly-linked-list \ + $(srcdir)/test-doubly-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-doubly-linked-list rm -f demangler-fuzzer rm -f core clean: mostlyclean diff --git a/libiberty/testsuite/test-doubly-linked-list.c b/libiberty/testsuite/test-doubly-linked-list.c new file mode 100644 index 00000000000..1e1fc637653 --- /dev/null +++ b/libiberty/testsuite/test-doubly-linked-list.c @@ -0,0 +1,269 @@ +#include +#include +#include + +#include "doubly-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 (const ListNodeType *n1, const ListNodeType *n2) +{ + if (n1->value == n2->value) + return 0; + else if (n1->value < n2->value) + return -1; + else + return 1; +} + +LINKED_LIST_MUTATIVE_OPS_PROTOTYPE (LinkedListWrapperType, ListNodeType, static); +LINKED_LIST_MERGE_SORT_PROTOTYPE (LinkedListWrapperType, ListNodeType, static); + +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 (%ld) is not matching the real size of the list (%ld).\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; + + printf("\n"); + + 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 [] = { 10, 2, 3, 4, 9, 8, 11 }; +const int EXPECT_6 [] = { 10, 3, 2, 4, 9, 8, 11 }; +const int EXPECT_7 [] = { 10, 9, 2, 4, 3, 8, 11 }; +const int EXPECT_8 [] = { 2, 3, 4, 8, 9, 10, 11 }; +const int EXPECT_9 [] = { 3, 4, 8, 9, 10, 11 }; +const int EXPECT_10 [] = { 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]) }, + { .content = EXPECT_8, .size = sizeof(EXPECT_8) / sizeof(EXPECT_8[0]) }, + { .content = EXPECT_9, .size = sizeof(EXPECT_9) / sizeof(EXPECT_9[0]) }, + { .content = EXPECT_10, .size = sizeof(EXPECT_10) / sizeof(EXPECT_10[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); + + /* Swap first and last. */ + LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first, wrapper.last); + failures += ! check ("swap first and last", &test_data[5], &wrapper); + + /* Swap adjacent nodes. */ + LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first->next, + wrapper.first->next->next); + failures += ! check ("swap adjacent nodes", &test_data[6], &wrapper); + + /* Swap non-adjacent nodes, but neither first nor last. */ + LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first->next, + wrapper.first->next->next->next->next); + failures += ! check ("swap non-adjacent nodes", &test_data[7], &wrapper); + + /* Sort nodes. */ + LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes); + failures += ! check ("sort", &test_data[8], &wrapper); + + /* Pop front. */ + LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper); + failures += ! check ("pop_front", &test_data[9], &wrapper); + + /* Pop back. */ + LINKED_LIST_POP_BACK(ListNodeType) (&wrapper); + failures += ! check ("pop_back", &test_data[10], &wrapper); + + exit (failures ? EXIT_FAILURE : EXIT_SUCCESS); +} -- 2.50.1