Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2218228/?format=api
{ "id": 2218228, "url": "http://patchwork.ozlabs.org/api/patches/2218228/?format=api", "web_url": "http://patchwork.ozlabs.org/project/glibc/patch/20260331175439.932978-2-adhemerval.zanella@linaro.org/", "project": { "id": 41, "url": "http://patchwork.ozlabs.org/api/projects/41/?format=api", "name": "GNU C Library", "link_name": "glibc", "list_id": "libc-alpha.sourceware.org", "list_email": "libc-alpha@sourceware.org", "web_url": "", "scm_url": "", "webscm_url": "", "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<20260331175439.932978-2-adhemerval.zanella@linaro.org>", "list_archive_url": null, "date": "2026-03-31T17:53:32", "name": "[v4,2/2] io: Use gnulib fts implementation (BZ 22944, BZ 20331)", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "b6cfaa463679c8a0d79d6aa14e5ec6abe3df2d30", "submitter": { "id": 66065, "url": "http://patchwork.ozlabs.org/api/people/66065/?format=api", "name": "Adhemerval Zanella Netto", "email": "adhemerval.zanella@linaro.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/glibc/patch/20260331175439.932978-2-adhemerval.zanella@linaro.org/mbox/", "series": [ { "id": 498235, "url": "http://patchwork.ozlabs.org/api/series/498235/?format=api", "web_url": "http://patchwork.ozlabs.org/project/glibc/list/?series=498235", "date": "2026-03-31T17:53:31", "name": "[v4,1/2] stdlib: Add internal stdc_rotate_right implementation", "version": 4, "mbox": "http://patchwork.ozlabs.org/series/498235/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2218228/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2218228/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<libc-alpha-bounces~incoming=patchwork.ozlabs.org@sourceware.org>", "X-Original-To": [ "incoming@patchwork.ozlabs.org", "libc-alpha@sourceware.org" ], "Delivered-To": [ "patchwork-incoming@legolas.ozlabs.org", "libc-alpha@sourceware.org" ], "Authentication-Results": [ "legolas.ozlabs.org;\n\tdkim=pass (2048-bit key;\n unprotected) header.d=linaro.org header.i=@linaro.org header.a=rsa-sha256\n header.s=google header.b=FNWVsSvl;\n\tdkim-atps=neutral", "legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=libc-alpha-bounces~incoming=patchwork.ozlabs.org@sourceware.org;\n receiver=patchwork.ozlabs.org)", "sourceware.org;\n\tdkim=pass (2048-bit key,\n unprotected) header.d=linaro.org header.i=@linaro.org header.a=rsa-sha256\n header.s=google header.b=FNWVsSvl", "sourceware.org;\n dmarc=pass (p=none dis=none) header.from=linaro.org", "sourceware.org; spf=pass smtp.mailfrom=linaro.org", "server2.sourceware.org;\n arc=none smtp.remote-ip=2607:f8b0:4864:20::931" ], "Received": [ "from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4flbPt2DqRz1yCp\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 01 Apr 2026 04:55:46 +1100 (AEDT)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 10BE64B92097\n\tfor <incoming@patchwork.ozlabs.org>; Tue, 31 Mar 2026 17:55:44 +0000 (GMT)", "from mail-ua1-x931.google.com (mail-ua1-x931.google.com\n [IPv6:2607:f8b0:4864:20::931])\n by sourceware.org (Postfix) with ESMTPS id E126C4BB58EC\n for <libc-alpha@sourceware.org>; Tue, 31 Mar 2026 17:54:51 +0000 (GMT)", "by mail-ua1-x931.google.com with SMTP id\n a1e0cc1a2514c-953a2a4761cso1989753241.1\n for <libc-alpha@sourceware.org>; Tue, 31 Mar 2026 10:54:51 -0700 (PDT)", "from mandiga.. ([2804:1b3:a7c2:40e0:331:b678:2d1:1e6e])\n by smtp.gmail.com with ESMTPSA id\n ada2fe7eead31-60512a1dc2asm12984911137.4.2026.03.31.10.54.45\n (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);\n Tue, 31 Mar 2026 10:54:46 -0700 (PDT)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org 10BE64B92097", "OpenDKIM Filter v2.11.0 sourceware.org E126C4BB58EC" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org E126C4BB58EC", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org E126C4BB58EC", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1774979692; cv=none;\n b=iZnmEyvTCUbw/lNy4bokaBDGsV2SE3GeH+lfrmoxSM7jJc1oq5OBJXtt6kzGPa13OsOADrx821OinXtjq2pJNBZuc7HzR9xRlxvhdEig8l7f3W7SqGk6lys59s5LP8chVIIYqXsUgbkmlBOlvuhp3SyfdA5Z92Jz9tzb4NElQ+s=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1774979692; c=relaxed/simple;\n bh=6iio/UdlbPzkNoQcS7VORCXWPGvX1YIHwwqn9kfRSEE=;\n h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version;\n b=ZwTZK63Y6aP8oHJN2Kt9sDXZ4mrhcEe7g77Ggxnbb08pEQ2mfVQm8TymMse2qU+IduRhIxt6iKdwN1LXXaMROwDIzPLVE8oJnMCJiMFOOIvX7V2RJpyYfzhFHU6XMWA1UAz2J1OXOAAAg2ItToihQMNeC+fBHmI5HaR9Y92UIhE=", "ARC-Authentication-Results": "i=1; server2.sourceware.org", "DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=linaro.org; s=google; t=1774979691; x=1775584491; darn=sourceware.org;\n h=content-transfer-encoding:mime-version:references:in-reply-to\n :message-id:date:subject:cc:to:from:from:to:cc:subject:date\n :message-id:reply-to;\n bh=xuDeqbVoHBn5xxUkjzIOXSuJBwO6CmzV5HEUasW3HDw=;\n b=FNWVsSvlX0gbyyr2NDfJZehi2IBO8UibOPlZlz3zNoDkmkYUYtsHqPpFT9B4pwsQ+r\n TAWl5LPngBzS0JHMqIF5+A2rzNkheTSv8MWOqEQiqksqQGgoC51zY68Cywtahv1RE/pq\n xkKjMZiVOMmk7RR9lCxsPhBKfP47GGKWHF/9H6ERWyxwcVsRiixd0SM0irwC8LqH2OZ1\n K6IGD/s5MBidW+ZRK8pIHrL3ageOkt2Hsa3O6ZjYy2f9utMSeGZEeFLk3dy3okkSoXhX\n rdXt5hzRnoDbCzI6f0Qteaf1+sglNEB/oMrQy6T/y/8pQIR5/jV+34IeGLbPXH1wuSS2\n OMOQ==", "X-Google-DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed;\n d=1e100.net; s=20251104; t=1774979691; x=1775584491;\n h=content-transfer-encoding:mime-version:references:in-reply-to\n :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from\n :to:cc:subject:date:message-id:reply-to;\n bh=xuDeqbVoHBn5xxUkjzIOXSuJBwO6CmzV5HEUasW3HDw=;\n b=OUDB5m2XaihMEejvC2KcfizD8lAOE7jH4asucvtPp8gkENLz+1u9yPITasLkeysNzA\n SdHIZNXs7k6yzTYCAYVgr/d34KEoew3c3ML+MHaYPEBDg1JF/U7o82CbSf1K+ErDDgNL\n evWqouy8W6XAhUijRm6JR/GJKez+0kaezkAOxvogInxM8TpQJdtJRHCysZCWaODuCjzI\n HzlpWC1liV9QPVZdl1IRSl5+tcO2zNSs7+Y9Qzy3G/MHockqe7mlGQSiJ3CSaOwCK9Gv\n MGfxkQ7N0Opq5XmxvGyHLcIxQZyzoRcMRlqx3Zx1YbiC/Sr/lC6MIvTZ06Yv+YjaeaO+\n 7/lA==", "X-Gm-Message-State": "AOJu0Yy481mA5BLD8K1HGJscYxXAdM4knjZumMIDiPki8n4aoVYWAAFD\n rjfyNC6rGYNCXJspYH2NnDcR0TamS3496THkCZ08M4NAzfb+2tbgK1TYq1+ii4sy8vbO5g/h+az\n Pe/Fn", "X-Gm-Gg": "ATEYQzzJvAP1uEtf73KfybZ2/17VKNcQUFXot+w60bwBuLFI03uhJSlsvx90JItracA\n qn98wkvnTIx7uForYbfmR25JXy4rlhGnKt6PEPX5d0ePD+CBznz4jdevPi3Hm1TeYm+sw1XGXg3\n 1TFZ3UhodxvfU5lL7vA+mmRCFtAt3n5a2swRynymwVq7fBcFPk691GgdgK79p6TLyrASgg3dSdL\n dNn3aVF0wm2B8CRhfIhcOh6pyq3UGZJiwlmqK3jY/E8VVKU5lciI0twnLkc/6SluT9p5+6kKytw\n 5ykjYCLpbN/nODVXHKNn9Zs/SdOsqjYKRDhAjx3f0V47yGmMMxgbev2FrMDTFho93pGhXTyZzzC\n QGsgHejBaOclmMeFcD114oxapCGrDD6e+NClAQ0IfTFWJy5qjuRqAFVKN6tRR4tyoEzh46o0Ylp\n QxsBOGuh96dprTSp+EQR8+X+Tz0KP7k6g0", "X-Received": "by 2002:a05:6102:3594:b0:5fe:12c9:6e5a with SMTP id\n ada2fe7eead31-60567e8d2fbmr99811137.12.1774979688375;\n Tue, 31 Mar 2026 10:54:48 -0700 (PDT)", "From": "Adhemerval Zanella <adhemerval.zanella@linaro.org>", "To": "libc-alpha@sourceware.org", "Cc": "Collin Funk <collin.funk1@gmail.com>", "Subject": "[PATCH v4 2/2] io: Use gnulib fts implementation (BZ 22944, BZ 20331)", "Date": "Tue, 31 Mar 2026 14:53:32 -0300", "Message-ID": "<20260331175439.932978-2-adhemerval.zanella@linaro.org>", "X-Mailer": "git-send-email 2.43.0", "In-Reply-To": "<20260331175439.932978-1-adhemerval.zanella@linaro.org>", "References": "<20260331175439.932978-1-adhemerval.zanella@linaro.org>", "MIME-Version": "1.0", "Content-Transfer-Encoding": "8bit", "X-BeenThere": "libc-alpha@sourceware.org", "X-Mailman-Version": "2.1.30", "Precedence": "list", "List-Id": "Libc-alpha mailing list <libc-alpha.sourceware.org>", "List-Unsubscribe": "<https://sourceware.org/mailman/options/libc-alpha>,\n <mailto:libc-alpha-request@sourceware.org?subject=unsubscribe>", "List-Archive": "<https://sourceware.org/pipermail/libc-alpha/>", "List-Post": "<mailto:libc-alpha@sourceware.org>", "List-Help": "<mailto:libc-alpha-request@sourceware.org?subject=help>", "List-Subscribe": "<https://sourceware.org/mailman/listinfo/libc-alpha>,\n <mailto:libc-alpha-request@sourceware.org?subject=subscribe>", "Errors-To": "libc-alpha-bounces~incoming=patchwork.ozlabs.org@sourceware.org" }, "content": "This patch synchronizes the glibc fts implementation with the latest\nversion from gnulib (as of 2026-02-16).\n\nThe primary motivation is to address limitations in the legacy glibc\nimplementation, most notably BZ 22944, where fts fails with an\nENAMETOOLONG error when traversing very long paths or deeply nested\ndirectory trees. The gnulib implementation dynamically reallocates\npath buffers and uses openat/fchdir optimizations, effectively\nlifting the MAXPATHLEN limitation.\n\nThe gnulib implementation also added extra features, which are\nused by different GNU projects (coreutils, diffutils):\n\n * FTS_TIGHT_CYCLE_CHECK: used to enable a strict, immediate\n cycle-detection algorithm during a file system traversal. This is\n done internally using a hash table: every time the traversal enters\n a directory, it records the directory's device and inode (dev/ino)\n pair in the hash table, and before entering any directory, fts\n checks the hash table.\n\n * FTS_CWDFD: instead of actually changing the process's current\n working directory, it maintains a virtual current working directory\n using file descriptors. The file descriptor is store at the\n fts_cwd_fd field and all subsequent file operations are performed\n relative to this file descriptor using *at functions.\n\n * FTS_DEFER_STAT: performance-oriented flag that instructs the file\n tree traversal engine to delay fetching file metadata. When the\n flag is used, fts skips the immediate stat call. Instead, it marks\n the entry with a special internal state (FTS_NSOK and\n FTS_STAT_REQUIRED). The actual stat call is pushed down the line\n and executed by fts_read right before the application actually\n accesses the entry.\n\n * FTS_VERBATIM: fts_open aaccept and use the path strings exactly as\n they were provided in the arguments array without slash trimming.\n\n * FTS_MOUNT: it restrict the file tree walk to a single file system.\n\nHopefully,it would allow some GNU projects to use the glibc\nimplementation instead of pulling the gnulib one.\n\nIt requires some changes to keep compatibility, compared to gnulib:\n\n * The new required fields are added at the end of FTS structure, and\n the new FTS flags are adjusted to avoid change FTS_NAMEONLY/FTS_STOP\n (even though they are marked as private).\n\n * The FTSENT uses a flexible array (fts_name), so two adjustments are\n required: the two new members (fts_fts and fts_dirp) are place\n *before* the struct and the fts_statp is now always allocated and\n accounted (the gnulib implementation uses a awalys allocated member).\n\nChecked on x86_64-linux-gnu and i686-linux-gnu.\n--\nChanges from v3:\n* Move stdc_rotate_right to a different patch, along with tests from\n gnulib.\nChanges from v2:\n* Remove bitrotate.h and replace with internal stdc_rotate_right\n implementation.\nChanges from v1:\n* Move next-prime.c, hash.c to io subfolder, and hash.h and next-prive.h\n to include/.\n---\n SHARED-FILES | 16 +\n dirent/scandirat.c | 3 +-\n dirent/scandirat64.c | 3 +-\n include/assure.h | 57 +\n include/dirent.h | 3 +-\n include/flexmember.h | 77 +\n include/fts.h | 7 +\n include/hash.h | 331 ++++\n include/next-prime.h | 47 +\n include/xalloc-oversized.h | 65 +\n io/Makefile | 2 +\n io/cycle-check.c | 85 +\n io/cycle-check.h | 70 +\n io/dev-ino.h | 44 +\n io/fts-cycle.c | 162 ++\n io/fts.c | 2902 ++++++++++++++++++++---------\n io/fts.h | 126 +-\n io/fts64-time64.c | 25 +-\n io/fts64.c | 5 +-\n io/i-ring.c | 69 +\n io/same-inode.h | 106 ++\n io/tst-fts-bz22944.c | 100 +\n io/tst-fts-newflags.c | 234 +++\n io/tst-fts.c | 2 +\n misc/Makefile | 2 +\n misc/hash.c | 1045 +++++++++++\n misc/next-prime.c | 64 +\n sysdeps/mach/hurd/opendir.c | 7 +-\n sysdeps/unix/sysv/linux/opendir.c | 16 +-\n 29 files changed, 4737 insertions(+), 938 deletions(-)\n create mode 100644 include/assure.h\n create mode 100644 include/flexmember.h\n create mode 100644 include/hash.h\n create mode 100644 include/next-prime.h\n create mode 100644 include/xalloc-oversized.h\n create mode 100644 io/cycle-check.c\n create mode 100644 io/cycle-check.h\n create mode 100644 io/dev-ino.h\n create mode 100644 io/fts-cycle.c\n create mode 100644 io/i-ring.c\n create mode 100644 io/same-inode.h\n create mode 100644 io/tst-fts-bz22944.c\n create mode 100644 io/tst-fts-newflags.c\n create mode 100644 misc/hash.c\n create mode 100644 misc/next-prime.c", "diff": "diff --git a/SHARED-FILES b/SHARED-FILES\nindex 5a676e1a48..e39a7670f5 100644\n--- a/SHARED-FILES\n+++ b/SHARED-FILES\n@@ -36,8 +36,22 @@ gnulib:\n # Merged from gnulib 2025-10-29 (gnulib commit 1790ef25d8)\n include/intprops.h\n include/intprops-internal.h\n+ # Merged from gnulib 2026-02-16\n+ include/assure.h\n+ include/flexmember.h\n+ include/hash.h\n+ include/next-prime.h\n+ include/xalloc-oversized.h\n # Merged from gnulib 2021-09-21\n include/regex.h\n+ # Merged from gnulib 2026-02-16\n+ io/cycle-check.c\n+ io/cycle-check.h\n+ io/dev-ino.h\n+ io/fts-cycle.c\n+ io/fts.c\n+ io/i-ring.c\n+ io/same-inode.h\n locale/programs/3level.h\n # Merged from gnulib 2014-6-23\n malloc/obstack.c\n@@ -47,7 +61,9 @@ gnulib:\n misc/error.c\n misc/error.h\n misc/getpass.c\n+ misc/hash.c\n misc/mkdtemp.c\n+ misc/next-prime.c\n # Merged from gnulib 2021-09-21\n misc/sys/cdefs.h\n posix/fnmatch_loop.c\ndiff --git a/dirent/scandirat.c b/dirent/scandirat.c\nindex 31ec9662b0..d40c0828f1 100644\n--- a/dirent/scandirat.c\n+++ b/dirent/scandirat.c\n@@ -23,7 +23,8 @@ __scandirat (int dfd, const char *dir, struct dirent ***namelist,\n \t int (*select) (const struct dirent *),\n \t int (*cmp) (const struct dirent **, const struct dirent **))\n {\n- return __scandir_tail (__opendirat (dfd, dir), namelist, select, cmp);\n+ return __scandir_tail (__opendirat (dfd, dir, 0, NULL), namelist, select,\n+\t\t\t cmp);\n }\n weak_alias (__scandirat, scandirat)\n #endif\ndiff --git a/dirent/scandirat64.c b/dirent/scandirat64.c\nindex fb010fac28..cb1821174e 100644\n--- a/dirent/scandirat64.c\n+++ b/dirent/scandirat64.c\n@@ -24,7 +24,8 @@ scandirat64 (int dfd, const char *dir, struct dirent64 ***namelist,\n \t int (*select) (const struct dirent64 *),\n \t int (*cmp) (const struct dirent64 **, const struct dirent64 **))\n {\n- return __scandir64_tail (__opendirat (dfd, dir), namelist, select, cmp);\n+ return __scandir64_tail (__opendirat (dfd, dir, 0, NULL), namelist, select,\n+\t\t\t cmp);\n }\n \n #if _DIRENT_MATCHES_DIRENT64\ndiff --git a/include/assure.h b/include/assure.h\nnew file mode 100644\nindex 0000000000..edc72591d1\n--- /dev/null\n+++ b/include/assure.h\n@@ -0,0 +1,57 @@\n+/* Run-time assert-like macros.\n+\n+ Copyright (C) 2014-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* Written by Paul Eggert. */\n+\n+#ifndef _GL_ASSURE_H\n+#define _GL_ASSURE_H\n+\n+#include <assert.h>\n+#include \"verify.h\"\n+\n+/* Evaluate an assertion E that is guaranteed to be true.\n+ If NDEBUG is not defined, abort the program if E is false.\n+ If NDEBUG is defined, the compiler can assume E and behavior is\n+ undefined if E is false, fails to evaluate, or has side effects.\n+\n+ Unlike standard 'assert', this macro evaluates E even when NDEBUG\n+ is defined, so as to catch typos, avoid some GCC warnings, and\n+ improve performance when E is simple enough.\n+\n+ Also see the documentation for 'assume' in verify.h. */\n+\n+#ifdef NDEBUG\n+# define affirm(E) assume (E)\n+#else\n+# define affirm(E) assert (E)\n+#endif\n+\n+/* Check E's value at runtime, and report an error and abort if not.\n+ However, do nothing if NDEBUG is defined.\n+\n+ Unlike standard 'assert', this macro compiles E even when NDEBUG\n+ is defined, so as to catch typos and avoid some GCC warnings.\n+ Unlike 'affirm', it is OK for E to use hard-to-optimize features,\n+ since E is not executed if NDEBUG is defined. */\n+\n+#ifdef NDEBUG\n+# define assure(E) ((void) (0 && (E)))\n+#else\n+# define assure(E) assert (E)\n+#endif\n+\n+#endif\ndiff --git a/include/dirent.h b/include/dirent.h\nindex d7567f5e86..9a4bd5a1e3 100644\n--- a/include/dirent.h\n+++ b/include/dirent.h\n@@ -16,7 +16,8 @@ struct scandir_cancel_struct\n \n /* Now define the internal interfaces. */\n extern DIR *__opendir (const char *__name) attribute_hidden;\n-extern DIR *__opendirat (int dfd, const char *__name) attribute_hidden;\n+extern DIR *__opendirat (int dfd, const char *__nam, int extra_flags,\n+\t\t\t int *pnew_fd) attribute_hidden;\n extern DIR *__fdopendir (int __fd) attribute_hidden;\n extern int __closedir (DIR *__dirp) attribute_hidden;\n extern struct dirent *__readdir (DIR *__dirp) attribute_hidden;\ndiff --git a/include/flexmember.h b/include/flexmember.h\nnew file mode 100644\nindex 0000000000..c6bb2842ec\n--- /dev/null\n+++ b/include/flexmember.h\n@@ -0,0 +1,77 @@\n+/* Sizes of structs with flexible array members.\n+\n+ Copyright 2016-2026 Free Software Foundation, Inc.\n+\n+ This file is part of the GNU C Library.\n+\n+ The GNU C Library is free software; you can redistribute it and/or\n+ modify it under the terms of the GNU Lesser General Public\n+ License as published by the Free Software Foundation; either\n+ version 2.1 of the License, or (at your option) any later version.\n+\n+ The GNU C Library is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public\n+ License along with the GNU C Library; if not, see\n+ <https://www.gnu.org/licenses/>.\n+\n+ Written by Paul Eggert. */\n+\n+/* This file uses _Alignof. */\n+#if !_LIBC && !_GL_CONFIG_H_INCLUDED\n+ #error \"Please include config.h first.\"\n+#endif\n+\n+#include <stddef.h>\n+\n+/* Nonzero multiple of alignment of TYPE, suitable for FLEXSIZEOF below.\n+ If _Alignof might not exist or might not work correctly on\n+ structs with flexible array members, use a pessimistic bound that is\n+ safe in practice even if FLEXIBLE_ARRAY_MEMBER is 1.\n+ Otherwise, use _Alignof to get a tighter bound. */\n+\n+#if !defined __STDC_VERSION__ || __STDC_VERSION__ < 201112 || defined _Alignof\n+# define FLEXALIGNOF(type) (sizeof (type) & ~ (sizeof (type) - 1))\n+#else\n+# define FLEXALIGNOF(type) _Alignof (type)\n+#endif\n+\n+/* Yield a properly aligned upper bound on the size of a struct of\n+ type TYPE with a flexible array member named MEMBER that is\n+ followed by N bytes of other data. The result is suitable as an\n+ argument to malloc. For example:\n+\n+ struct s { int a; char d[FLEXIBLE_ARRAY_MEMBER]; };\n+ struct s *p = malloc (FLEXSIZEOF (struct s, d, n * sizeof (char)));\n+\n+ FLEXSIZEOF (TYPE, MEMBER, N) is not simply (sizeof (TYPE) + N),\n+ since FLEXIBLE_ARRAY_MEMBER may be 1 on pre-C11 platforms. Nor is\n+ it simply (offsetof (TYPE, MEMBER) + N), as that might yield a size\n+ that causes malloc to yield a pointer that is not properly aligned\n+ for TYPE; for example, if sizeof (int) == alignof (int) == 4,\n+ malloc (offsetof (struct s, d) + 3 * sizeof (char)) is equivalent\n+ to malloc (7) and might yield a pointer that is not a multiple of 4\n+ (which means the pointer is not properly aligned for struct s),\n+ whereas malloc (FLEXSIZEOF (struct s, d, 3 * sizeof (char))) is\n+ equivalent to malloc (8) and must yield a pointer that is a\n+ multiple of 4.\n+\n+ Yield a value less than N if and only if arithmetic overflow occurs. */\n+\n+#define FLEXSIZEOF(type, member, n) \\\n+ ((offsetof (type, member) + FLEXALIGNOF (type) - 1 + (n)) \\\n+ & ~ (FLEXALIGNOF (type) - 1))\n+\n+/* Yield a properly aligned upper bound on the size of a struct of\n+ type TYPE with a flexible array member named MEMBER that has N\n+ elements. The result is suitable as an argument to malloc.\n+ For example:\n+\n+ struct s { int a; double d[FLEXIBLE_ARRAY_MEMBER]; };\n+ struct s *p = malloc (FLEXNSIZEOF (struct s, d, n));\n+ */\n+#define FLEXNSIZEOF(type, member, n) \\\n+ FLEXSIZEOF (type, member, (n) * sizeof (((type *) 0)->member[0]))\ndiff --git a/include/fts.h b/include/fts.h\nindex ea36a9b9be..706cb4ab61 100644\n--- a/include/fts.h\n+++ b/include/fts.h\n@@ -17,6 +17,13 @@ typedef struct\n int fts_nitems;\n int (*fts_compar) (const void *, const void *);\n int fts_options;\n+ int fts_cwd_fd;\n+ struct hash_table *fts_leaf_optimization_works_ht;\n+ union {\n+\t struct hash_table *ht;\n+\t struct cycle_check_state *state;\n+ } fts_cycle;\n+ I_ring fts_fd_ring;\n } FTS64_TIME64;\n \n typedef struct _ftsent64_time64\ndiff --git a/include/hash.h b/include/hash.h\nnew file mode 100644\nindex 0000000000..d3c80aeedf\n--- /dev/null\n+++ b/include/hash.h\n@@ -0,0 +1,331 @@\n+/* hash - hashing table processing.\n+ Copyright (C) 1998-1999, 2001, 2003, 2009-2026 Free Software Foundation,\n+ Inc.\n+ Written by Jim Meyering <meyering@ascend.com>, 1998.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* A generic hash table package. */\n+\n+/* Make sure USE_OBSTACK is defined to 1 if you want the allocator to use\n+ obstacks instead of malloc, and recompile 'hash.c' with same setting. */\n+\n+#ifndef HASH_H_\n+# define HASH_H_\n+\n+/* This file uses _GL_ATTRIBUTE_DEALLOC, _GL_ATTRIBUTE_DEPRECATED,\n+ _GL_ATTRIBUTE_MALLOC, _GL_ATTRIBUTE_NODISCARD, _GL_ATTRIBUTE_PURE,\n+ _GL_ATTRIBUTE_RETURNS_NONNULL. */\n+#if !_LIBC && !_GL_CONFIG_H_INCLUDED\n+ #error \"Please include config.h first.\"\n+#endif\n+\n+# include <stdbool.h>\n+# include <stdio.h>\n+\n+# ifdef _LIBC\n+# define _GL_ATTRIBUTE_NODISCARD __attribute_warn_unused_result__\n+# define _GL_ATTRIBUTE_MALLOC __attribute_malloc__\n+# define _GL_ATTRIBUTE_DEALLOC(__a, __b) __attr_dealloc (__a, __b)\n+# define _GL_ATTRIBUTE_RETURNS_NONNULL __returns_nonnull\n+# define GNULIB_HASHCODE_STRING1 0\n+# define hash_get_n_buckets __hash_get_n_buckets\n+# define hash_get_n_buckets_used __hash_get_n_buckets_used\n+# define hash_get_n_entries __hash_get_n_entries\n+# define hash_get_max_bucket_length __hash_get_max_bucket_length\n+# define hash_table_ok __hash_table_ok\n+# define hash_print_statistics __hash_print_statistics\n+# define hash_lookup __hash_lookup\n+# define hash_get_first __hash_get_first\n+# define hash_get_next __hash_get_next\n+# define hash_get_entries __hash_get_entries\n+# define hash_do_for_each __hash_do_for_each\n+# define hash_reset_tuning __hash_reset_tuning\n+# define hash_free __hash_free\n+# define hash_initialize __hash_initialize\n+# define hash_xinitialize __hash_xinitialize\n+# define hash_clear __hash_clear\n+# define hash_rehash __hash_rehash\n+# define hash_insert __hash_insert\n+# define hash_xinsert __hash_xinsert\n+# define hash_insert_if_absent __hash_insert_if_absent\n+# define hash_remove __hash_remove\n+# else\n+# define attribute_hidden\n+# endif\n+\n+# ifdef __cplusplus\n+extern \"C\" {\n+# endif\n+\n+struct hash_tuning\n+ {\n+ /* This structure is mainly used for 'hash_initialize', see the block\n+ documentation of 'hash_reset_tuning' for more complete comments. */\n+\n+ float shrink_threshold; /* ratio of used buckets to trigger a shrink */\n+ float shrink_factor; /* ratio of new smaller size to original size */\n+ float growth_threshold; /* ratio of used buckets to trigger a growth */\n+ float growth_factor; /* ratio of new bigger size to original size */\n+ bool is_n_buckets; /* if CANDIDATE really means table size */\n+ };\n+\n+typedef struct hash_tuning Hash_tuning;\n+\n+struct hash_table;\n+\n+typedef struct hash_table Hash_table;\n+\n+/*\n+ * Information and lookup.\n+ */\n+\n+/* The following few functions provide information about the overall hash\n+ table organization: the number of entries, number of buckets and maximum\n+ length of buckets. */\n+\n+/* Return the number of buckets in the hash table. The table size, the total\n+ number of buckets (used plus unused), or the maximum number of slots, are\n+ the same quantity. */\n+extern size_t hash_get_n_buckets (const Hash_table *table)\n+ _GL_ATTRIBUTE_PURE attribute_hidden;\n+\n+/* Return the number of slots in use (non-empty buckets). */\n+extern size_t hash_get_n_buckets_used (const Hash_table *table)\n+ _GL_ATTRIBUTE_PURE attribute_hidden;\n+\n+/* Return the number of active entries. */\n+extern size_t hash_get_n_entries (const Hash_table *table)\n+ _GL_ATTRIBUTE_PURE attribute_hidden;\n+\n+/* Return the length of the longest chain (bucket). */\n+extern size_t hash_get_max_bucket_length (const Hash_table *table)\n+ _GL_ATTRIBUTE_PURE attribute_hidden;\n+\n+/* Do a mild validation of a hash table, by traversing it and checking two\n+ statistics. */\n+extern bool hash_table_ok (const Hash_table *table)\n+ _GL_ATTRIBUTE_PURE attribute_hidden;\n+\n+extern void hash_print_statistics (const Hash_table *table, FILE *stream)\n+ attribute_hidden;\n+\n+/* If ENTRY matches an entry already in the hash table, return the\n+ entry from the table. Otherwise, return NULL. */\n+extern void *hash_lookup (const Hash_table *table, const void *entry)\n+ attribute_hidden;\n+\n+/*\n+ * Walking.\n+ */\n+\n+/* The functions in this page traverse the hash table and process the\n+ contained entries. For the traversal to work properly, the hash table\n+ should not be resized nor modified while any particular entry is being\n+ processed. In particular, entries should not be added, and an entry\n+ may be removed only if there is no shrink threshold and the entry being\n+ removed has already been passed to hash_get_next. */\n+\n+/* Return the first data in the table, or NULL if the table is empty. */\n+extern void *hash_get_first (const Hash_table *table)\n+ _GL_ATTRIBUTE_PURE attribute_hidden;\n+\n+/* Return the user data for the entry following ENTRY, where ENTRY has been\n+ returned by a previous call to either 'hash_get_first' or 'hash_get_next'.\n+ Return NULL if there are no more entries. */\n+extern void *hash_get_next (const Hash_table *table, const void *entry)\n+ attribute_hidden;\n+\n+/* Fill BUFFER with pointers to active user entries in the hash table, then\n+ return the number of pointers copied. Do not copy more than BUFFER_SIZE\n+ pointers. */\n+extern size_t hash_get_entries (const Hash_table *table, void **buffer,\n+ size_t buffer_size)\n+ attribute_hidden;\n+\n+typedef bool (*Hash_processor) (void *entry, void *processor_data);\n+\n+/* Call a PROCESSOR function for each entry of a hash table, and return the\n+ number of entries for which the processor function returned success. A\n+ pointer to some PROCESSOR_DATA which will be made available to each call to\n+ the processor function. The PROCESSOR accepts two arguments: the first is\n+ the user entry being walked into, the second is the value of PROCESSOR_DATA\n+ as received. The walking continue for as long as the PROCESSOR function\n+ returns nonzero. When it returns zero, the walking is interrupted. */\n+extern size_t hash_do_for_each (const Hash_table *table,\n+ Hash_processor processor, void *processor_data)\n+ attribute_hidden;\n+\n+/* Return a hash code of ENTRY, in the range 0..TABLE_SIZE-1.\n+ This hash code function must have the property that if the comparator of\n+ ENTRY1 and ENTRY2 returns true, the hasher returns the same value for ENTRY1\n+ and for ENTRY2.\n+ The hash code function typically computes an unsigned integer and at the end\n+ performs a % TABLE_SIZE modulo operation. This modulo operation is performed\n+ as part of this hash code function, not by the caller, because in some cases\n+ the unsigned integer will be a 'size_t', in other cases an 'uintmax_t' or\n+ even larger. */\n+typedef size_t (*Hash_hasher) (const void *entry, size_t table_size);\n+\n+/* Compare two entries, ENTRY1 (being looked up or being inserted) and\n+ ENTRY2 (already in the table) for equality. Return true for equal,\n+ false otherwise. */\n+typedef bool (*Hash_comparator) (const void *entry1, const void *entry2);\n+\n+/* This function is invoked when an ENTRY is removed from the hash table. */\n+typedef void (*Hash_data_freer) (void *entry);\n+\n+/*\n+ * Allocation and clean-up.\n+ */\n+\n+extern void hash_reset_tuning (Hash_tuning *tuning)\n+ attribute_hidden;\n+\n+/* Reclaim all storage associated with a hash table. If a data_freer\n+ function has been supplied by the user when the hash table was created,\n+ this function applies it to the data of each entry before freeing that\n+ entry. This function preserves errno, like 'free'. */\n+extern void hash_free (Hash_table *table)\n+ attribute_hidden;\n+\n+/* Allocate and return a new hash table, or NULL upon failure. The initial\n+ number of buckets is automatically selected so as to _guarantee_ that you\n+ may insert at least CANDIDATE different user entries before any growth of\n+ the hash table size occurs. So, if have a reasonably tight a-priori upper\n+ bound on the number of entries you intend to insert in the hash table, you\n+ may save some table memory and insertion time, by specifying it here. If\n+ the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE\n+ argument has its meaning changed to the wanted number of buckets.\n+\n+ TUNING points to a structure of user-supplied values, in case some fine\n+ tuning is wanted over the default behavior of the hasher. If TUNING is\n+ NULL, the default tuning parameters are used instead. If TUNING is\n+ provided but the values requested are out of bounds or might cause\n+ rounding errors, return NULL.\n+\n+ The user-supplied HASHER function, when not NULL, accepts two\n+ arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a\n+ slot number for that entry which should be in the range 0..TABLE_SIZE-1.\n+ This slot number is then returned.\n+\n+ The user-supplied COMPARATOR function, when not NULL, accepts two\n+ arguments pointing to user data, it then returns true for a pair of entries\n+ that compare equal, or false otherwise. This function is internally called\n+ on entries which are already known to hash to the same bucket index,\n+ but which are distinct pointers.\n+\n+ The user-supplied DATA_FREER function, when not NULL, may be later called\n+ with the user data as an argument, just before the entry containing the\n+ data gets freed. This happens from within 'hash_free' or 'hash_clear'.\n+ You should specify this function only if you want these functions to free\n+ all of your 'data' data. This is typically the case when your data is\n+ simply an auxiliary struct that you have malloc'd to aggregate several\n+ values.\n+\n+ Set errno on failure; otherwise errno is unspecified. */\n+_GL_ATTRIBUTE_NODISCARD\n+extern Hash_table *hash_initialize (size_t candidate,\n+ const Hash_tuning *tuning,\n+ Hash_hasher hasher,\n+ Hash_comparator comparator,\n+ Hash_data_freer data_freer)\n+ _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC (hash_free, 1)\n+ attribute_hidden;\n+\n+/* Like hash_initialize, but invokes xalloc_die instead of returning NULL. */\n+/* This function is defined by module 'xhash'. */\n+_GL_ATTRIBUTE_NODISCARD\n+extern Hash_table *hash_xinitialize (size_t candidate,\n+ const Hash_tuning *tuning,\n+ Hash_hasher hasher,\n+ Hash_comparator comparator,\n+ Hash_data_freer data_freer)\n+ _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC (hash_free, 1)\n+ _GL_ATTRIBUTE_RETURNS_NONNULL\n+ attribute_hidden;\n+\n+/* Make all buckets empty, placing any chained entries on the free list.\n+ Apply the user-specified function data_freer (if any) to the data of any\n+ affected entries. */\n+extern void hash_clear (Hash_table *table)\n+ attribute_hidden;;\n+\n+/*\n+ * Insertion and deletion.\n+ */\n+\n+/* For an already existing hash table, change the number of buckets through\n+ specifying CANDIDATE. The contents of the hash table are preserved. The\n+ new number of buckets is automatically selected so as to _guarantee_ that\n+ the table may receive at least CANDIDATE different user entries, including\n+ those already in the table, before any other growth of the hash table size\n+ occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the\n+ exact number of buckets desired. Return true iff the rehash succeeded,\n+ false (setting errno) otherwise. */\n+_GL_ATTRIBUTE_NODISCARD\n+extern bool hash_rehash (Hash_table *table, size_t candidate)\n+ attribute_hidden;\n+\n+/* If ENTRY matches an entry already in the hash table, return the pointer\n+ to the entry from the table. Otherwise, insert ENTRY and return ENTRY.\n+ Return NULL (setting errno) if the storage required for insertion\n+ cannot be allocated. This implementation does not support\n+ duplicate entries or insertion of NULL. */\n+_GL_ATTRIBUTE_NODISCARD\n+extern void *hash_insert (Hash_table *table, const void *entry)\n+ attribute_hidden;\n+\n+/* Same as hash_insert, but invokes xalloc_die instead of returning NULL. */\n+/* This function is defined by module 'xhash'. */\n+extern void *hash_xinsert (Hash_table *table, const void *entry)\n+ attribute_hidden;\n+\n+/* Insert ENTRY into hash TABLE if there is not already a matching entry.\n+\n+ Return -1 (setting errno) upon memory allocation failure.\n+ Return 1 if insertion succeeded.\n+ Return 0 if there is already a matching entry in the table,\n+ and in that case, if MATCHED_ENT is non-NULL, set *MATCHED_ENT\n+ to that entry.\n+\n+ This interface is easier to use than hash_insert when you must\n+ distinguish between the latter two cases. More importantly,\n+ hash_insert is unusable for some types of ENTRY values. When using\n+ hash_insert, the only way to distinguish those cases is to compare\n+ the return value and ENTRY. That works only when you can have two\n+ different ENTRY values that point to data that compares \"equal\". Thus,\n+ when the ENTRY value is a simple scalar, you must use\n+ hash_insert_if_absent. ENTRY must not be NULL. */\n+extern int hash_insert_if_absent (Hash_table *table, const void *entry,\n+ const void **matched_ent)\n+ attribute_hidden;\n+\n+/* If ENTRY is already in the table, remove it and return the just-deleted\n+ data (the user may want to deallocate its storage). If ENTRY is not in the\n+ table, don't modify the table and return NULL. */\n+extern void *hash_remove (Hash_table *table, const void *entry)\n+ attribute_hidden;\n+\n+\n+# if GNULIB_HASHCODE_STRING1\n+/* Include declarations of module 'hashcode-string1'. */\n+# include \"hashcode-string1.h\"\n+# endif\n+\n+# ifdef __cplusplus\n+}\n+# endif\n+\n+#endif\ndiff --git a/include/next-prime.h b/include/next-prime.h\nnew file mode 100644\nindex 0000000000..2ee965982b\n--- /dev/null\n+++ b/include/next-prime.h\n@@ -0,0 +1,47 @@\n+/* Finding the next prime >= a given small integer.\n+ Copyright (C) 1995-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+#ifndef _GL_NEXT_PRIME_H\n+#define _GL_NEXT_PRIME_H\n+\n+/* This file uses _GL_ATTRIBUTE_CONST. */\n+#if !_LIBC && !_GL_CONFIG_H_INCLUDED\n+ #error \"Please include config.h first.\"\n+#endif\n+\n+#include <stddef.h>\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\n+#ifdef _LIBC\n+# define next_prime __next_prime\n+#else\n+# define attribute_hidden\n+#endif\n+\n+/* Round a given CANDIDATE number up to the nearest prime, and return that\n+ prime. Primes lower than 10 are merely skipped. */\n+extern size_t _GL_ATTRIBUTE_CONST next_prime (size_t candidate)\n+ attribute_hidden;;\n+\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+\n+#endif /* _GL_NEXT_PRIME_H */\ndiff --git a/include/xalloc-oversized.h b/include/xalloc-oversized.h\nnew file mode 100644\nindex 0000000000..cecdaec51e\n--- /dev/null\n+++ b/include/xalloc-oversized.h\n@@ -0,0 +1,65 @@\n+/* xalloc-oversized.h -- memory allocation size checking\n+\n+ Copyright (C) 1990-2000, 2003-2004, 2006-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+#ifndef XALLOC_OVERSIZED_H_\n+#define XALLOC_OVERSIZED_H_\n+\n+#include <stddef.h>\n+#include <stdint.h>\n+\n+/* True if N * S does not fit into both ptrdiff_t and size_t.\n+ N and S should be nonnegative and free of side effects.\n+ This expands to a constant expression if N and S are both constants.\n+ By gnulib convention, SIZE_MAX represents overflow in size_t\n+ calculations, so the conservative size_t-based dividend to use here\n+ is SIZE_MAX - 1. */\n+#define __xalloc_oversized(n, s) \\\n+ ((s) != 0 \\\n+ && (PTRDIFF_MAX < SIZE_MAX ? PTRDIFF_MAX : SIZE_MAX - 1) / (s) < (n))\n+\n+/* Return 1 if and only if an array of N objects, each of size S,\n+ cannot exist reliably because its total size in bytes would exceed\n+ MIN (PTRDIFF_MAX, SIZE_MAX - 1).\n+\n+ N and S should be nonnegative and free of side effects.\n+\n+ Warning: (xalloc_oversized (N, S) ? NULL : malloc (N * S)) can\n+ misbehave if N and S are both narrower than ptrdiff_t and size_t,\n+ and can be rewritten as (xalloc_oversized (N, S) ? NULL\n+ : malloc (N * (size_t) S)).\n+\n+ This is a macro, not a function, so that it works even if an\n+ argument exceeds MAX (PTRDIFF_MAX, SIZE_MAX). */\n+#if 7 <= __GNUC__ && !defined __clang__ && PTRDIFF_MAX < SIZE_MAX\n+# define xalloc_oversized(n, s) \\\n+ __builtin_mul_overflow_p (n, s, (ptrdiff_t) 1)\n+#elif 5 <= __GNUC__ && !defined __clang__ && !defined __ICC \\\n+ && PTRDIFF_MAX < SIZE_MAX\n+# define xalloc_oversized(n, s) \\\n+ (__builtin_constant_p (n) && __builtin_constant_p (s) \\\n+ ? __xalloc_oversized (n, s) \\\n+ : __extension__ \\\n+ ({ ptrdiff_t __xalloc_count; \\\n+ __builtin_mul_overflow (n, s, &__xalloc_count); }))\n+\n+/* Other compilers use integer division; this may be slower but is\n+ more portable. */\n+#else\n+# define xalloc_oversized(n, s) __xalloc_oversized (n, s)\n+#endif\n+\n+#endif /* !XALLOC_OVERSIZED_H_ */\ndiff --git a/io/Makefile b/io/Makefile\nindex 80e50578b2..2a5b4dcb65 100644\n--- a/io/Makefile\n+++ b/io/Makefile\n@@ -197,7 +197,9 @@ tests := \\\n tst-fcntl-lock-lfs \\\n tst-fstatat \\\n tst-fts \\\n+ tst-fts-bz22944 \\\n tst-fts-lfs \\\n+ tst-fts-newflags \\\n tst-ftw-bz26353 \\\n tst-ftw-bz28126 \\\n tst-ftw-lnk \\\ndiff --git a/io/cycle-check.c b/io/cycle-check.c\nnew file mode 100644\nindex 0000000000..3a20d28aec\n--- /dev/null\n+++ b/io/cycle-check.c\n@@ -0,0 +1,85 @@\n+\n+/* help detect directory cycles efficiently\n+\n+ Copyright (C) 2003-2006, 2009-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* Written by Jim Meyering */\n+\n+#include <config.h>\n+\n+#include \"cycle-check.h\"\n+\n+#include <sys/types.h>\n+#include <sys/stat.h>\n+#include <stdio.h>\n+#include <stdlib.h>\n+\n+#include \"assure.h\"\n+\n+#define CC_MAGIC 9827862\n+\n+/* Return true if I is a power of 2, or is zero. */\n+\n+static bool\n+is_zero_or_power_of_two (uintmax_t i)\n+{\n+ return (i & (i - 1)) == 0;\n+}\n+\n+INTERNAL_DEF void\n+cycle_check_init (struct cycle_check_state *state)\n+{\n+ state->chdir_counter = 0;\n+ state->magic = CC_MAGIC;\n+}\n+\n+/* In traversing a directory hierarchy, call this function once for each\n+ descending chdir call, with SB corresponding to the chdir operand.\n+ If SB corresponds to a directory that has already been seen,\n+ return true to indicate that there is a directory cycle.\n+ Note that this is done \"lazily\", which means that some of\n+ the directories in the cycle may be processed twice before\n+ the cycle is detected. */\n+\n+INTERNAL_DEF bool\n+cycle_check (struct cycle_check_state *state, struct STRUCT_STAT const *sb)\n+{\n+ assure (state->magic == CC_MAGIC);\n+\n+ /* If the current directory ever happens to be the same\n+ as the one we last recorded for the cycle detection,\n+ then it's obviously part of a cycle. */\n+ if (state->chdir_counter && SAME_INODE (*sb, state->dev_ino))\n+ return true;\n+\n+ /* If the number of \"descending\" chdir calls is a power of two,\n+ record the dev/ino of the current directory. */\n+ if (is_zero_or_power_of_two (++(state->chdir_counter)))\n+ {\n+ /* On all architectures that we know about, if the counter\n+ overflows then there is a directory cycle here somewhere,\n+ even if we haven't detected it yet. Typically this happens\n+ only after the counter is incremented 2**64 times, so it's a\n+ fairly theoretical point. */\n+ if (state->chdir_counter == 0)\n+ return true;\n+\n+ state->dev_ino.st_dev = sb->st_dev;\n+ state->dev_ino.st_ino = sb->st_ino;\n+ }\n+\n+ return false;\n+}\ndiff --git a/io/cycle-check.h b/io/cycle-check.h\nnew file mode 100644\nindex 0000000000..0152992ced\n--- /dev/null\n+++ b/io/cycle-check.h\n@@ -0,0 +1,70 @@\n+\n+/* help detect directory cycles efficiently\n+\n+ Copyright (C) 2003-2004, 2006, 2009-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* Written by Jim Meyering */\n+\n+#ifndef CYCLE_CHECK_H\n+#define CYCLE_CHECK_H 1\n+\n+#include <stdint.h>\n+#include \"dev-ino.h\"\n+#include \"same-inode.h\"\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\n+#if _LIBC\n+# define cycle_check_init __cycle_check_init\n+# define cycle_check __cycle_check\n+# define INTERNAL_DEF static\n+#else\n+# define INTERNAL_DEF\n+#endif\n+\n+struct cycle_check_state\n+{\n+ struct dev_ino dev_ino;\n+ uintmax_t chdir_counter;\n+ int magic;\n+};\n+\n+INTERNAL_DEF void cycle_check_init (struct cycle_check_state *state);\n+INTERNAL_DEF bool cycle_check (struct cycle_check_state *state,\n+\t\t\t struct STRUCT_STAT const *sb);\n+\n+#define CYCLE_CHECK_REFLECT_CHDIR_UP(State, SB_dir, SB_subdir) \\\n+ do \\\n+ { \\\n+ /* You must call cycle_check at least once before using this macro. */ \\\n+ if ((State)->chdir_counter == 0) \\\n+ abort (); \\\n+ if (SAME_INODE ((State)->dev_ino, SB_subdir)) \\\n+ { \\\n+ (State)->dev_ino.st_dev = (SB_dir).st_dev; \\\n+ (State)->dev_ino.st_ino = (SB_dir).st_ino; \\\n+ } \\\n+ } \\\n+ while (0)\n+\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+\n+#endif\ndiff --git a/io/dev-ino.h b/io/dev-ino.h\nnew file mode 100644\nindex 0000000000..9b1878c79f\n--- /dev/null\n+++ b/io/dev-ino.h\n@@ -0,0 +1,44 @@\n+/* A simple (device, inode) struct.\n+ Copyright (C) 2003-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* Written by Jim Meyering, 2003. */\n+\n+#ifndef DEV_INO_H\n+#define DEV_INO_H 1\n+\n+#include <sys/types.h>\n+#include <sys/stat.h>\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\n+#ifndef INO_T\n+#define INO_T ino_t\n+#endif\n+\n+struct dev_ino\n+{\n+ INO_T st_ino;\n+ dev_t st_dev;\n+};\n+\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+\n+#endif\ndiff --git a/io/fts-cycle.c b/io/fts-cycle.c\nnew file mode 100644\nindex 0000000000..6bbc9f9446\n--- /dev/null\n+++ b/io/fts-cycle.c\n@@ -0,0 +1,162 @@\n+/* Detect cycles in file tree walks.\n+\n+ Copyright (C) 2003-2006, 2009-2026 Free Software Foundation, Inc.\n+\n+ Written by Jim Meyering.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+#include \"cycle-check.h\"\n+#include \"hash.h\"\n+\n+#ifndef FTS_OPEN\n+# define FTSOBJ FTS\n+# define FTSENTRY FTSENT\n+#endif\n+\n+/* Use each of these to map a device/inode pair to an FTSENT. */\n+struct Active_dir\n+{\n+ dev_t dev;\n+ INO_T ino;\n+ FTSENTRY *fts_ent;\n+};\n+\n+static bool\n+AD_compare (void const *x, void const *y)\n+{\n+ struct Active_dir const *ax = x;\n+ struct Active_dir const *ay = y;\n+ return ax->ino == ay->ino\n+ && ax->dev == ay->dev;\n+}\n+\n+static size_t\n+AD_hash (void const *x, size_t table_size)\n+{\n+ struct Active_dir const *ax = x;\n+ return (uintmax_t) ax->ino % table_size;\n+}\n+\n+/* Set up the cycle-detection machinery. */\n+\n+static bool\n+setup_dir (FTSOBJ *fts)\n+{\n+ if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))\n+ {\n+ enum { HT_INITIAL_SIZE = 31 };\n+ fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash,\n+ AD_compare, free);\n+ if (! fts->fts_cycle.ht)\n+ return false;\n+ }\n+ else\n+ {\n+ fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state);\n+ if (! fts->fts_cycle.state)\n+ return false;\n+ cycle_check_init (fts->fts_cycle.state);\n+ }\n+\n+ return true;\n+}\n+\n+/* Enter a directory during a file tree walk. */\n+\n+static bool\n+enter_dir (FTSOBJ *fts, FTSENTRY *ent)\n+{\n+ if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))\n+ {\n+ struct Active_dir *ad = malloc (sizeof *ad);\n+ if (!ad)\n+ return false;\n+\n+ struct STRUCT_STAT const *st = ent->fts_statp;\n+ ad->dev = st->st_dev;\n+ ad->ino = st->st_ino;\n+ ad->fts_ent = ent;\n+\n+ /* See if we've already encountered this directory.\n+ This can happen when following symlinks as well as\n+ with a corrupted directory hierarchy. */\n+ struct Active_dir *ad_from_table = hash_insert (fts->fts_cycle.ht, ad);\n+\n+ if (ad_from_table != ad)\n+ {\n+ free (ad);\n+ if (!ad_from_table)\n+ return false;\n+\n+ /* There was an entry with matching dev/inode already in the table.\n+ Record the fact that we've found a cycle. */\n+ ent->fts_cycle = ad_from_table->fts_ent;\n+ ent->fts_info = FTS_DC;\n+ }\n+ }\n+ else\n+ {\n+ if (cycle_check (fts->fts_cycle.state, ent->fts_statp))\n+ {\n+ /* FIXME: setting fts_cycle like this isn't proper.\n+ To do what the documentation requires, we'd have to\n+ go around the cycle again and find the right entry.\n+ But no callers in coreutils use the fts_cycle member. */\n+ ent->fts_cycle = ent;\n+ ent->fts_info = FTS_DC;\n+ }\n+ }\n+\n+ return true;\n+}\n+\n+/* Leave a directory during a file tree walk. */\n+\n+static void\n+leave_dir (FTSOBJ *fts, FTSENTRY *ent)\n+{\n+ struct STRUCT_STAT const *st = ent->fts_statp;\n+ if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))\n+ {\n+ struct Active_dir obj;\n+ obj.dev = st->st_dev;\n+ obj.ino = st->st_ino;\n+ void *found = hash_remove (fts->fts_cycle.ht, &obj);\n+ if (!found)\n+ abort ();\n+ free (found);\n+ }\n+ else\n+ {\n+ FTSENTRY *parent = ent->fts_parent;\n+ if (parent != NULL && 0 <= parent->fts_level)\n+ CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state,\n+ *(parent->fts_statp), *st);\n+ }\n+}\n+\n+/* Free any memory used for cycle detection. */\n+\n+static void\n+free_dir (FTSOBJ *sp)\n+{\n+ if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))\n+ {\n+ if (sp->fts_cycle.ht)\n+ hash_free (sp->fts_cycle.ht);\n+ }\n+ else\n+ free (sp->fts_cycle.state);\n+}\ndiff --git a/io/fts.c b/io/fts.c\nindex 27a15b1104..3825f0aeb4 100644\n--- a/io/fts.c\n+++ b/io/fts.c\n@@ -1,24 +1,23 @@\n-/* File tree traversal functions.\n- Copyright (C) 1994-2026 Free Software Foundation, Inc.\n- This file is part of the GNU C Library.\n+/* Traverse a file hierarchy.\n \n- The GNU C Library is free software; you can redistribute it and/or\n- modify it under the terms of the GNU Lesser General Public\n- License as published by the Free Software Foundation; either\n- version 2.1 of the License, or (at your option) any later version.\n+ Copyright (C) 2004-2026 Free Software Foundation, Inc.\n \n- The GNU C Library is distributed in the hope that it will be useful,\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n but WITHOUT ANY WARRANTY; without even the implied warranty of\n- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n- Lesser General Public License for more details.\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n \n- You should have received a copy of the GNU Lesser General Public\n- License along with the GNU C Library; if not, see\n- <https://www.gnu.org/licenses/>. */\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n \n /*-\n * Copyright (c) 1990, 1993, 1994\n- *\tThe Regents of the University of California. All rights reserved.\n+ * The Regents of the University of California. All rights reserved.\n *\n * Redistribution and use in source and binary forms, with or without\n * modification, are permitted provided that the following conditions\n@@ -32,7 +31,7 @@\n * may be used to endorse or promote products derived from this software\n * without specific prior written permission.\n *\n- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND\n+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS \"AS IS\" AND\n * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\n * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE\n@@ -45,457 +44,1122 @@\n * SUCH DAMAGE.\n */\n \n-#if defined(LIBC_SCCS) && !defined(lint)\n-static char sccsid[] = \"@(#)fts.c\t8.6 (Berkeley) 8/14/94\";\n-#endif /* LIBC_SCCS and not lint */\n+#include <config.h>\n \n-#include <sys/param.h>\n-#include <include/sys/stat.h>\n+#if defined LIBC_SCCS && !defined GCC_LINT && !defined lint\n+static char sccsid[] = \"@(#)fts.c 8.6 (Berkeley) 8/14/94\";\n+#endif\n+\n+#if _LIBC\n+# include <fts.h>\n+#else\n+# include \"fts_.h\"\n+#endif\n+#if _LIBC || HAVE_SYS_PARAM_H\n+# include <sys/param.h>\n+#endif\n+#include <sys/stat.h>\n #include <fcntl.h>\n-#include <dirent.h>\n #include <errno.h>\n-#include <fts.h>\n+#include <stddef.h>\n #include <stdint.h>\n #include <stdlib.h>\n #include <string.h>\n #include <unistd.h>\n \n-\n-/* Largest alignment size needed, minus one.\n- Usually long double is the worst case. */\n-#ifndef ALIGNBYTES\n-#define ALIGNBYTES\t(__alignof__ (long double) - 1)\n-#endif\n-/* Align P to that size. */\n-#ifndef ALIGN\n-#define\tALIGN(p)\t(((uintptr_t) (p) + ALIGNBYTES) & ~ALIGNBYTES)\n-#endif\n-\n-\n /* Support for the LFS API version. */\n #ifndef FTS_OPEN\n-#define FTS_OPEN fts_open\n-#define FTS_CLOSE fts_close\n-#define FTS_READ fts_read\n-#define FTS_SET fts_set\n-#define FTS_CHILDREN fts_children\n+# define FTS_OPEN fts_open\n+# define FTS_CLOSE fts_close\n+# define FTS_READ fts_read\n+# define FTS_SET fts_set\n+# define FTS_CHILDREN fts_children\n # define FTSOBJ FTS\n # define FTSENTRY FTSENT\n # define INO_T ino_t\n # define STRUCT_STAT stat\n-# define STAT __stat\n-# define LSTAT __lstat\n # define FSTAT __fstat\n+# define FSTATAT __fstatat\n+# define STRUCT_STATFS statfs\n+# define FSTATFS __fstatfs\n #endif\n \n-static FTSENTRY\t*fts_alloc (FTSOBJ *, const char *, size_t);\n-static FTSENTRY\t*fts_build (FTSOBJ *, int);\n-static void\t fts_lfree (FTSENTRY *);\n-static void\t fts_load (FTSOBJ *, FTSENTRY *);\n-static size_t\t fts_maxarglen (char * const *);\n-static void\t fts_padjust (FTSOBJ *, FTSENTRY *);\n-static int\t fts_palloc (FTSOBJ *, size_t);\n-static FTSENTRY\t*fts_sort (FTSOBJ *, FTSENTRY *, int);\n-static u_short\t fts_stat (FTSOBJ *, FTSENTRY *, int);\n+#if ! _LIBC\n+# include \"attribute.h\"\n+# include \"fcntl--.h\"\n+# include \"openat.h\"\n+# include \"opendirat.h\"\n+# include \"same-inode.h\"\n+# define OPENDIRAT opendirat\n+# define FTSENT_WRAPPER(__p) __p\n+# define FTS_COMPAR_CAST(__fn) __fn\n+#else\n+# include <stdbool.h>\n+\n+# define internal_function\n+# define FALLTHROUGH ; [[fallthrough]]\n+# define HAVE_STRUCT_DIRENT_D_TYPE 1\n+# define GNULIB_FTS_DEBUG 0\n+# ifdef O_PATH\n+# define O_SEARCH O_PATH\n+# else\n+# define O_SEARCH O_RDONLY\n+# endif\n+# define HAVE_SYS_VFS_H 1\n+# define HAVE_FSTATFS 1\n+# define HAVE_STRUCT_STATFS_F_TYPE 1\n+# define HAVE_OPENAT 1\n+# define HAVE_WORKING_O_NOFOLLOW 1\n+# define _GL_CMP(a, b) ((a) < (b) ? -1 : (a) > (b))\n+# define OPENDIRAT __opendirat\n+\n+static inline bool openat_needs_fchdir (void)\n+{\n+ return false;\n+}\n+\n+static inline bool streq (const char *s1, const char *s2)\n+{\n+ return strcmp (s1, s2) == 0;\n+}\n+# define reallocarray __libc_reallocarray\n+# define fchdir __fchdir\n+# define close __close\n+# define closedir __closedir\n+# define fcntl __fcntl\n+# define readdir __readdir\n+# ifndef dirfd\n+# define dirfd __dirfd\n+# endif\n+# define open __open\n+# define openat __openat\n+\n+# include \"cycle-check.c\"\n+# include \"i-ring.c\"\n+\n+struct FTSENT_wrapper\n+{\n+ FTSOBJ *fts_fts; /* the file hierarchy itself */\n+ DIR *fts_dirp; /* Dir pointer for any directory containing\n+\t\t\t\t more entries than we read at one time. */\n+ struct STRUCT_STAT fts_stat;\n+\n+ FTSENTRY ent;\n+};\n+\n+/* glibc historicaly defines the FTS::fts_compar as having 'void *', while the\n+ fts_open has a function point using 'FTSENT **' as argument. */\n+# define FTS_COMPAR_CAST(__fn) ((int (*) (void const *, void const *))__fn)\n+\n+# define FTSENT_WRAPPER(p) \\\n+ ((struct FTSENT_wrapper *) ((char *)(p) - offsetof(struct FTSENT_wrapper, ent)))\n+#endif\n+#define FTSENT_FTS(p) (FTSENT_WRAPPER(p)->fts_fts)\n+#define FTSENT_DIRP(p) (FTSENT_WRAPPER(p)->fts_dirp)\n+\n+#include \"flexmember.h\"\n+\n+#include <dirent.h>\n+#ifndef _D_EXACT_NAMLEN\n+# define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)\n+#endif\n+\n+#if HAVE_STRUCT_DIRENT_D_TYPE\n+/* True if the type of the directory entry D is known. */\n+# define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)\n+/* True if the type of the directory entry D must be T. */\n+# define DT_MUST_BE(d, t) ((d)->d_type == (t))\n+# define D_TYPE(d) ((d)->d_type)\n+#else\n+# define DT_IS_KNOWN(d) false\n+# define DT_MUST_BE(d, t) false\n+# define D_TYPE(d) DT_UNKNOWN\n+\n+# undef DT_UNKNOWN\n+# define DT_UNKNOWN 0\n+\n+/* Any nonzero values will do here, so long as they're distinct.\n+ Undef any existing macros out of the way. */\n+# undef DT_BLK\n+# undef DT_CHR\n+# undef DT_DIR\n+# undef DT_FIFO\n+# undef DT_LNK\n+# undef DT_REG\n+# undef DT_SOCK\n+# define DT_BLK 1\n+# define DT_CHR 2\n+# define DT_DIR 3\n+# define DT_FIFO 4\n+# define DT_LNK 5\n+# define DT_REG 6\n+# define DT_SOCK 7\n+#endif\n+\n+#ifndef S_IFBLK\n+# define S_IFBLK 0\n+#endif\n+#ifndef S_IFLNK\n+# define S_IFLNK 0\n+#endif\n+#ifndef S_IFSOCK\n+# define S_IFSOCK 0\n+#endif\n+\n+enum\n+{\n+ NOT_AN_INODE_NUMBER = 0\n+};\n+\n+#ifdef D_INO_IN_DIRENT\n+# define D_INO(dp) (dp)->d_ino\n+#else\n+/* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */\n+# define D_INO(dp) NOT_AN_INODE_NUMBER\n+#endif\n+\n+/* If possible (see max_entries, below), read no more than this many directory\n+ entries at a time. Without this limit (i.e., when using non-NULL\n+ fts_compar), processing a directory with 4,000,000 entries requires ~1GiB\n+ of memory, and handling 64M entries would require 16GiB of memory. */\n+#ifndef FTS_MAX_READDIR_ENTRIES\n+# define FTS_MAX_READDIR_ENTRIES 100000\n+#endif\n+\n+/* If there are more than this many entries in a directory,\n+ and the conditions mentioned below are satisfied, then sort\n+ the entries on inode number before any further processing. */\n+#ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD\n+# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000\n+#endif\n+\n+enum\n+{\n+ _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD\n+};\n+\n+enum Fts_stat\n+{\n+ FTS_NO_STAT_REQUIRED = 1,\n+ FTS_STAT_REQUIRED = 2\n+};\n+\n+#ifndef __set_errno\n+# define __set_errno(Val) errno = (Val)\n+#endif\n+\n+/* If this host provides the openat function, then we can avoid\n+ attempting to open \".\" in some initialization code below. */\n+#ifdef HAVE_OPENAT\n+# define HAVE_OPENAT_SUPPORT 1\n+#else\n+# define HAVE_OPENAT_SUPPORT 0\n+#endif\n+\n+#ifdef NDEBUG\n+# define fts_assert(expr) ((void) (0 && (expr)))\n+#else\n+# define fts_assert(expr) \\\n+ do \\\n+ { \\\n+ if (!(expr)) \\\n+ abort (); \\\n+ } \\\n+ while (false)\n+#endif\n+\n+static FTSENTRY *fts_alloc (FTSOBJ *, const char *, size_t);\n+static FTSENTRY *fts_build (FTSOBJ *, int);\n+static void fts_lfree (FTSENTRY *);\n+static void fts_load (FTSOBJ *, FTSENTRY *);\n+static size_t fts_maxarglen (char * const *);\n+static void fts_padjust (FTSOBJ *, FTSENTRY *);\n+static bool fts_palloc (FTSOBJ *, size_t);\n+static FTSENTRY *fts_sort (FTSOBJ *, FTSENTRY *, size_t);\n+static unsigned short int fts_stat (FTSOBJ *, FTSENTRY *, bool);\n static int fts_safe_changedir (FTSOBJ *, FTSENTRY *, int, const char *);\n \n+#include \"fts-cycle.c\"\n+\n #ifndef MAX\n-#define MAX(a, b)\t({ __typeof__ (a) _a = (a); \\\n-\t\t\t __typeof__ (b) _b = (b); \\\n-\t\t\t _a > _b ? _a : _b; })\n+# define MAX(a,b) ((a) > (b) ? (a) : (b))\n #endif\n \n-#define\tISDOT(a)\t(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))\n+#ifndef SIZE_MAX\n+# define SIZE_MAX ((size_t) -1)\n+#endif\n \n-#define CLR(opt)\t(sp->fts_options &= ~(opt))\n-#define\tISSET(opt)\t(sp->fts_options & (opt))\n-#define\tSET(opt)\t(sp->fts_options |= (opt))\n+#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))\n+\n+#define CLR(opt) (sp->fts_options &= ~(opt))\n+#define ISSET(opt) ((sp->fts_options & (opt)) != 0)\n+#define SET(opt) (sp->fts_options |= (opt))\n+\n+/* FIXME: FTS_NOCHDIR is now misnamed.\n+ Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */\n+#define FCHDIR(sp, fd) \\\n+ (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \\\n+ ? (cwd_advance_fd ((sp), (fd), true), 0) \\\n+ : fchdir (fd)))\n \n-#define\tFCHDIR(sp, fd)\t(!ISSET(FTS_NOCHDIR) && __fchdir(fd))\n \n /* fts_build flags */\n-#define\tBCHILD\t\t1\t\t/* fts_children */\n-#define\tBNAMES\t\t2\t\t/* fts_children, names only */\n-#define\tBREAD\t\t3\t\t/* fts_read */\n+/* FIXME: make this an enum */\n+#define BCHILD 1 /* fts_children */\n+#define BNAMES 2 /* fts_children, names only */\n+#define BREAD 3 /* fts_read */\n+\n+#if GNULIB_FTS_DEBUG\n+# include <inttypes.h>\n+# include <stdio.h>\n+bool fts_debug = false;\n+# define Dprintf(x) do { if (fts_debug) printf x; } while (false)\n+static void fd_ring_check (FTSOBJ const *);\n+static void fd_ring_print (FTSOBJ const *, FILE *, char const *);\n+#else\n+# define Dprintf(x)\n+# define fd_ring_check(x)\n+# define fd_ring_print(a, b, c)\n+#endif\n+\n+#define LEAVE_DIR(Fts, Ent, Tag) \\\n+ do \\\n+ { \\\n+ Dprintf ((\" %s-leaving: %s\\n\", Tag, (Ent)->fts_path)); \\\n+ leave_dir (Fts, Ent); \\\n+ fd_ring_check (Fts); \\\n+ } \\\n+ while (false)\n+\n+static void\n+fd_ring_clear (I_ring *fd_ring)\n+{\n+ while ( ! i_ring_empty (fd_ring))\n+ {\n+ int fd = i_ring_pop (fd_ring);\n+ if (0 <= fd)\n+ close (fd);\n+ }\n+}\n+\n+/* Overload the fts_statp->st_size member (otherwise unused, when\n+ fts_info is FTS_NSOK) to indicate whether fts_read should stat\n+ this entry or not. */\n+static void\n+fts_set_stat_required (FTSENTRY *p, bool required)\n+{\n+ fts_assert (p->fts_info == FTS_NSOK);\n+ p->fts_statp->st_size = (required\n+ ? FTS_STAT_REQUIRED\n+ : FTS_NO_STAT_REQUIRED);\n+}\n+\n+/* Virtual fchdir. Advance SP's working directory file descriptor,\n+ SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.\n+ CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory\n+ open on sp->fts_cwd_fd; i.e., to move the working directory one level\n+ down. */\n+static void\n+internal_function\n+cwd_advance_fd (FTSOBJ *sp, int fd, bool chdir_down_one)\n+{\n+ int old = sp->fts_cwd_fd;\n+ fts_assert (old != fd || old == AT_FDCWD);\n+\n+ if (chdir_down_one)\n+ {\n+ /* Push \"old\" onto the ring.\n+ If the displaced file descriptor is non-negative, close it. */\n+ int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);\n+ fd_ring_print (sp, stderr, \"post-push\");\n+ if (0 <= prev_fd_in_slot)\n+ close (prev_fd_in_slot); /* ignore any close failure */\n+ }\n+ else if ( ! ISSET (FTS_NOCHDIR))\n+ {\n+ if (0 <= old)\n+ close (old); /* ignore any close failure */\n+ }\n+\n+ sp->fts_cwd_fd = fd;\n+}\n+\n+/* Restore the initial, pre-traversal, \"working directory\".\n+ In FTS_CWDFD mode, we merely call cwd_advance_fd, otherwise,\n+ we may actually change the working directory.\n+ Return 0 upon success. Upon failure, set errno and return nonzero. */\n+static int\n+restore_initial_cwd (FTSOBJ *sp)\n+{\n+ int fail = FCHDIR (sp, ISSET (FTS_CWDFD) ? AT_FDCWD : sp->fts_rfd);\n+ fd_ring_clear (&(sp->fts_fd_ring));\n+ return fail;\n+}\n+\n+/* Open the directory DIR if possible, and return a file\n+ descriptor. Return -1 and set errno on failure. It doesn't matter\n+ whether the file descriptor has read or write access. */\n+\n+static int\n+internal_function\n+diropen (FTSOBJ const *sp, char const *dir)\n+{\n+ int open_flags = (O_SEARCH | O_CLOEXEC | O_DIRECTORY | O_NOCTTY | O_NONBLOCK\n+ | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));\n+\n+ int fd = (ISSET (FTS_CWDFD)\n+ ? openat (sp->fts_cwd_fd, dir, open_flags)\n+ : open (dir, open_flags));\n+ return fd;\n+}\n \n FTSOBJ *\n-FTS_OPEN (char * const *argv, int options,\n-\t int (*compar) (const FTSENTRY **, const FTSENTRY **))\n+FTS_OPEN (char * const *argv,\n+ register int options,\n+ int (*compar) (const FTSENTRY **, const FTSENTRY **))\n {\n-\tFTSOBJ *sp;\n-\tFTSENTRY *p, *root;\n-\tint nitems;\n-\tFTSENTRY *parent = NULL;\n-\tFTSENTRY *tmp;\n-\n-\t/* Options check. */\n-\tif (options & ~FTS_OPTIONMASK) {\n-\t\t__set_errno (EINVAL);\n-\t\treturn (NULL);\n-\t}\n-\n-\t/* Allocate/initialize the stream */\n-\tif ((sp = malloc((u_int)sizeof(FTSOBJ))) == NULL)\n-\t\treturn (NULL);\n-\tmemset(sp, 0, sizeof(FTSOBJ));\n-\tsp->fts_compar = (int (*) (const void *, const void *)) compar;\n-\tsp->fts_options = options;\n-\n-\t/* Logical walks turn on NOCHDIR; symbolic links are too hard. */\n-\tif (ISSET(FTS_LOGICAL))\n-\t\tSET(FTS_NOCHDIR);\n-\n-\t/*\n-\t * Start out with 1K of path space, and enough, in any case,\n-\t * to hold the user's paths.\n-\t */\n-#ifndef MAXPATHLEN\n-#define MAXPATHLEN 1024\n+ /* Options check: glibc added other flags after FTS_NAMEONLY and\n+\t FTS_STOP, and they are assumed to be private. */\n+ if (options & ~FTS_OPTIONMASK\n+#if _LIBC\n+\t || options & (FTS_NAMEONLY | FTS_STOP)\n+#endif\n+\t ) {\n+ __set_errno (EINVAL);\n+ return (NULL);\n+ }\n+ if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {\n+ __set_errno (EINVAL);\n+ return (NULL);\n+ }\n+#if !_LIBC\n+ if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {\n+ __set_errno (EINVAL);\n+ return (NULL);\n+ }\n+#else\n+\t/* glibc historically falls to FTS_PHYSICAL if no FTS_PHYSICAL or\n+\t FTS_LOGICAL is specified. */\n+ if (! (options & (FTS_PHYSICAL | FTS_LOGICAL)))\n+\t options |= FTS_PHYSICAL;\n #endif\n-\tsize_t maxarglen = fts_maxarglen(argv);\n-\tif (fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))\n-\t\tgoto mem1;\n \n-\t/* Allocate/initialize root's parent. */\n-\tif (*argv != NULL) {\n-\t\tif ((parent = fts_alloc(sp, \"\", 0)) == NULL)\n-\t\t\tgoto mem2;\n-\t\tparent->fts_level = FTS_ROOTPARENTLEVEL;\n-\t }\n+ /* Allocate/initialize the stream */\n+ register FTSOBJ *sp = calloc (1, sizeof *sp);\n+ if (sp == NULL)\n+ return (NULL);\n+ sp->fts_compar = FTS_COMPAR_CAST(compar);\n+ sp->fts_options = options;\n \n-\t/* Allocate/initialize root(s). */\n-\tfor (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {\n-\t\t/* Don't allow zero-length paths. */\n-\t\tsize_t len = strlen(*argv);\n-\t\tif (len == 0) {\n-\t\t\t__set_errno (ENOENT);\n-\t\t\tgoto mem3;\n-\t\t}\n+ /* Logical walks turn on NOCHDIR; symbolic links are too hard. */\n+ if (ISSET(FTS_LOGICAL)) {\n+ SET(FTS_NOCHDIR);\n+ CLR(FTS_CWDFD);\n+ }\n \n-\t\tp = fts_alloc(sp, *argv, len);\n-\t\tp->fts_level = FTS_ROOTLEVEL;\n-\t\tp->fts_parent = parent;\n-\t\tp->fts_accpath = p->fts_name;\n-\t\tp->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));\n+ /* Initialize fts_cwd_fd. */\n+ sp->fts_cwd_fd = AT_FDCWD;\n+ if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)\n+ {\n+ /* While it isn't technically necessary to open \".\" this\n+ early, doing it here saves us the trouble of ensuring\n+ later (where it'd be messier) that \".\" can in fact\n+ be opened. If not, revert to FTS_NOCHDIR mode. */\n+ int fd = open (\".\", O_SEARCH | O_CLOEXEC);\n+ if (fd < 0)\n+ {\n+ /* Even if \".\" is unreadable, don't revert to FTS_NOCHDIR mode\n+ on systems like Linux+PROC_FS, where our openat emulation\n+ is good enough. Note: on a system that emulates\n+ openat via /proc, this technique can still fail, but\n+ only in extreme conditions, e.g., when the working\n+ directory cannot be saved (i.e. save_cwd fails) --\n+ and that happens on Linux only when \".\" is unreadable\n+ and the CWD would be longer than PATH_MAX.\n+ FIXME: once Linux kernel openat support is well established,\n+ replace the above open call and this entire if/else block\n+ with the body of the if-block below. */\n+ if ( openat_needs_fchdir ())\n+ {\n+ SET(FTS_NOCHDIR);\n+ CLR(FTS_CWDFD);\n+ }\n+ }\n+ else\n+ {\n+ close (fd);\n+ }\n+ }\n \n-\t\t/* Command-line \".\" and \"..\" are real directories. */\n-\t\tif (p->fts_info == FTS_DOT)\n-\t\t\tp->fts_info = FTS_D;\n+ /*\n+ * Start out with 1K of file name space, and enough, in any case,\n+ * to hold the user's file names.\n+ */\n+#ifndef MAXPATHLEN\n+# define MAXPATHLEN 1024\n+#endif\n+ {\n+ size_t maxarglen = fts_maxarglen(argv);\n+ if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))\n+ goto mem1;\n+ }\n \n-\t\t/*\n-\t\t * If comparison routine supplied, traverse in sorted\n-\t\t * order; otherwise traverse in the order specified.\n-\t\t */\n-\t\tif (compar) {\n-\t\t\tp->fts_link = root;\n-\t\t\troot = p;\n-\t\t} else {\n-\t\t\tp->fts_link = NULL;\n-\t\t\tif (root == NULL)\n-\t\t\t\ttmp = root = p;\n-\t\t\telse {\n-\t\t\t\ttmp->fts_link = p;\n-\t\t\t\ttmp = p;\n-\t\t\t}\n-\t\t}\n-\t}\n-\tif (compar && nitems > 1)\n-\t\troot = fts_sort(sp, root, nitems);\n+ /* Allocate/initialize root's parent. */\n+ FTSENTRY *parent = NULL;\n+ if (*argv != NULL) {\n+ if ((parent = fts_alloc(sp, \"\", 0)) == NULL)\n+ goto mem2;\n+ parent->fts_level = FTS_ROOTPARENTLEVEL;\n+ }\n \n-\t/*\n-\t * Allocate a dummy pointer and make fts_read think that we've just\n-\t * finished the node before the root(s); set p->fts_info to FTS_INIT\n-\t * so that everything about the \"current\" node is ignored.\n-\t */\n-\tif ((sp->fts_cur = fts_alloc(sp, \"\", 0)) == NULL)\n-\t\tgoto mem3;\n-\tsp->fts_cur->fts_link = root;\n-\tsp->fts_cur->fts_info = FTS_INIT;\n+ /* The classic fts implementation would call fts_stat with\n+ a new entry for each iteration of the loop below.\n+ If the comparison function is not specified or if the\n+ FTS_DEFER_STAT option is in effect, don't stat any entry\n+ in this loop. This is an attempt to minimize the interval\n+ between the initial stat/lstat/fstatat and the point at which\n+ a directory argument is first opened. This matters for any\n+ directory command line argument that resides on a file system\n+ without genuine i-nodes. If you specify FTS_DEFER_STAT along\n+ with a comparison function, that function must not access any\n+ data via the fts_statp pointer. */\n+ bool defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));\n \n-\t/*\n-\t * If using chdir(2), grab a file descriptor pointing to dot to ensure\n-\t * that we can get back here; this could be avoided for some paths,\n-\t * but almost certainly not worth the effort. Slashes, symbolic links,\n-\t * and \"..\" are all fairly nasty problems. Note, if we can't get the\n-\t * descriptor we run anyway, just more slowly.\n-\t */\n-\tif (!ISSET(FTS_NOCHDIR)\n-\t && (sp->fts_rfd = __open(\".\", O_RDONLY, 0)) < 0)\n-\t\tSET(FTS_NOCHDIR);\n+ /* Allocate/initialize root(s). */\n+ register FTSENTRY *root;\n+ register size_t nitems;\n+ FTSENTRY *tmp = NULL; /* pacify gcc */\n+ for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {\n+ /* *Do* allow zero-length file names. */\n+ size_t len = strlen(*argv);\n \n-\treturn (sp);\n+ if ( ! (options & FTS_VERBATIM))\n+ {\n+ /* If there are two or more trailing slashes, trim all but one,\n+ but don't change \"//\" to \"/\", and do map \"///\" to \"/\". */\n+ char const *v = *argv;\n+ if (2 < len && v[len - 1] == '/')\n+ while (1 < len && v[len - 2] == '/')\n+ --len;\n+ }\n \n-mem3:\tfts_lfree(root);\n-\tfree(parent);\n-mem2:\tfree(sp->fts_path);\n-mem1:\tfree(sp);\n-\treturn (NULL);\n+ register FTSENTRY *p = fts_alloc(sp, *argv, len);\n+ if (p == NULL)\n+ goto mem3;\n+ p->fts_level = FTS_ROOTLEVEL;\n+ p->fts_parent = parent;\n+ p->fts_accpath = p->fts_name;\n+ /* Even when defer_stat is true, be sure to stat the first\n+ command line argument, since fts_read (at least with\n+ FTS_XDEV) requires that. */\n+ if (defer_stat && root != NULL) {\n+ p->fts_info = FTS_NSOK;\n+ fts_set_stat_required(p, true);\n+ } else {\n+ p->fts_info = fts_stat(sp, p, false);\n+ }\n+\n+ /*\n+ * If comparison routine supplied, traverse in sorted\n+ * order; otherwise traverse in the order specified.\n+ */\n+ if (compar) {\n+ p->fts_link = root;\n+ root = p;\n+ } else {\n+ p->fts_link = NULL;\n+ if (root == NULL)\n+ tmp = root = p;\n+ else {\n+ tmp->fts_link = p;\n+ tmp = p;\n+ }\n+ }\n+ }\n+ if (compar && nitems > 1)\n+ root = fts_sort(sp, root, nitems);\n+\n+ /*\n+ * Allocate a dummy pointer and make fts_read think that we've just\n+ * finished the node before the root(s); set p->fts_info to FTS_INIT\n+ * so that everything about the \"current\" node is ignored.\n+ */\n+ if ((sp->fts_cur = fts_alloc(sp, \"\", 0)) == NULL)\n+ goto mem3;\n+ sp->fts_cur->fts_link = root;\n+ sp->fts_cur->fts_info = FTS_INIT;\n+ sp->fts_cur->fts_level = 1;\n+ if (! setup_dir (sp))\n+ goto mem3;\n+\n+ /*\n+ * If using chdir(2), grab a file descriptor pointing to dot to ensure\n+ * that we can get back here; this could be avoided for some file names,\n+ * but almost certainly not worth the effort. Slashes, symbolic links,\n+ * and \"..\" are all fairly nasty problems. Note, if we can't get the\n+ * descriptor we run anyway, just more slowly.\n+ */\n+ if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)\n+ && (sp->fts_rfd = diropen (sp, \".\")) < 0)\n+ SET(FTS_NOCHDIR);\n+\n+ i_ring_init (&sp->fts_fd_ring, -1);\n+ return (sp);\n+\n+mem3: fts_lfree(root);\n+ free(FTSENT_WRAPPER(parent));\n+mem2: free(sp->fts_path);\n+mem1: free(sp);\n+ return (NULL);\n }\n \n static void\n-fts_load (FTSOBJ *sp, FTSENTRY *p)\n+internal_function\n+fts_load (FTSOBJ *sp, register FTSENTRY *p)\n {\n-\tint len;\n-\tchar *cp;\n-\n-\t/*\n-\t * Load the stream structure for the next traversal. Since we don't\n-\t * actually enter the directory until after the preorder visit, set\n-\t * the fts_accpath field specially so the chdir gets done to the right\n-\t * place and the user can access the first node. From fts_open it's\n-\t * known that the path will fit.\n-\t */\n-\tlen = p->fts_pathlen = p->fts_namelen;\n-\tmemmove(sp->fts_path, p->fts_name, len + 1);\n-\tif ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {\n-\t\tlen = strlen(++cp);\n-\t\tmemmove(p->fts_name, cp, len + 1);\n-\t\tp->fts_namelen = len;\n-\t}\n-\tp->fts_accpath = p->fts_path = sp->fts_path;\n-\tsp->fts_dev = p->fts_dev;\n+ /*\n+ * Load the stream structure for the next traversal. Since we don't\n+ * actually enter the directory until after the preorder visit, set\n+ * the fts_accpath field specially so the chdir gets done to the right\n+ * place and the user can access the first node. From fts_open it's\n+ * known that the file name will fit.\n+ */\n+ register size_t len = p->fts_pathlen = p->fts_namelen;\n+ memmove(sp->fts_path, p->fts_name, len + 1);\n+ register char *cp = strrchr(p->fts_name, '/');\n+ if (cp && (cp != p->fts_name || cp[1])) {\n+ len = strlen(++cp);\n+ memmove(p->fts_name, cp, len + 1);\n+ p->fts_namelen = len;\n+ }\n+ p->fts_accpath = p->fts_path = sp->fts_path;\n }\n \n int\n FTS_CLOSE (FTSOBJ *sp)\n {\n-\tFTSENTRY *freep, *p;\n-\tint saved_errno;\n+ /*\n+ * This still works if we haven't read anything -- the dummy structure\n+ * points to the root list, so we step through to the end of the root\n+ * list which has a valid parent pointer.\n+ */\n+ if (sp->fts_cur) {\n+ register FTSENTRY *p;\n+ for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {\n+ register FTSENTRY *freep = p;\n+ p = p->fts_link != NULL ? p->fts_link : p->fts_parent;\n+ free(FTSENT_WRAPPER(freep));\n+ }\n+ free(FTSENT_WRAPPER(p));\n+ }\n \n-\t/*\n-\t * This still works if we haven't read anything -- the dummy structure\n-\t * points to the root list, so we step through to the end of the root\n-\t * list which has a valid parent pointer.\n-\t */\n-\tif (sp->fts_cur) {\n-\t\tfor (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {\n-\t\t\tfreep = p;\n-\t\t\tp = p->fts_link != NULL ? p->fts_link : p->fts_parent;\n-\t\t\tfree(freep);\n-\t\t}\n-\t\tfree(p);\n-\t}\n+ /* Free up child linked list, sort array, file name buffer. */\n+ if (sp->fts_child)\n+ fts_lfree(sp->fts_child);\n+ free(sp->fts_array);\n+ free(sp->fts_path);\n \n-\t/* Free up child linked list, sort array, path buffer. */\n-\tif (sp->fts_child)\n-\t\tfts_lfree(sp->fts_child);\n-\tfree(sp->fts_array);\n-\tfree(sp->fts_path);\n+ int saved_errno = 0;\n+ if (ISSET(FTS_CWDFD))\n+ {\n+ if (0 <= sp->fts_cwd_fd)\n+ if (close (sp->fts_cwd_fd))\n+ saved_errno = errno;\n+ }\n+ else if (!ISSET(FTS_NOCHDIR))\n+ {\n+ /* Return to original directory, save errno if necessary. */\n+ if (fchdir(sp->fts_rfd))\n+ saved_errno = errno;\n \n-\t/* Return to original directory, save errno if necessary. */\n-\tif (!ISSET(FTS_NOCHDIR)) {\n-\t\tsaved_errno = __fchdir(sp->fts_rfd) ? errno : 0;\n-\t\t(void)__close(sp->fts_rfd);\n+ /* If close fails, record errno only if saved_errno is zero,\n+ so that we report the probably-more-meaningful fchdir errno. */\n+ if (close (sp->fts_rfd))\n+ if (saved_errno == 0)\n+ saved_errno = errno;\n+ }\n \n-\t\t/* Set errno and return. */\n-\t\tif (saved_errno != 0) {\n-\t\t\t/* Free up the stream pointer. */\n-\t\t\tfree(sp);\n-\t\t\t__set_errno (saved_errno);\n-\t\t\treturn (-1);\n-\t\t}\n-\t}\n+ fd_ring_clear (&sp->fts_fd_ring);\n \n-\t/* Free up the stream pointer. */\n-\tfree(sp);\n-\treturn (0);\n+ if (sp->fts_leaf_optimization_works_ht)\n+ hash_free (sp->fts_leaf_optimization_works_ht);\n+\n+ free_dir (sp);\n+\n+ /* Free up the stream pointer. */\n+ free(sp);\n+\n+ /* Set errno and return. */\n+ if (saved_errno) {\n+ __set_errno (saved_errno);\n+ return (-1);\n+ }\n+\n+ return (0);\n }\n \n+/* Minimum link count of a traditional Unix directory. When leaf\n+ optimization is OK and a directory's st_nlink == MIN_DIR_NLINK,\n+ then the directory has no subdirectories. */\n+enum { MIN_DIR_NLINK = 2 };\n+\n+/* Whether leaf optimization is OK for a directory. */\n+enum leaf_optimization\n+ {\n+ /* st_nlink is not reliable for this directory's subdirectories. */\n+ NO_LEAF_OPTIMIZATION,\n+\n+ /* st_nlink == 2 means the directory lacks subdirectories. */\n+ OK_LEAF_OPTIMIZATION\n+ };\n+\n+#if (defined __linux__ || defined __ANDROID__) \\\n+ && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE\n+\n+# include <sys/vfs.h>\n+\n+/* Linux-specific constants from coreutils' src/fs.h */\n+# define S_MAGIC_AFS 0x5346414F\n+# define S_MAGIC_CIFS 0xFF534D42\n+# define S_MAGIC_LUSTRE 0x0BD00BD0\n+# define S_MAGIC_NFS 0x6969\n+# define S_MAGIC_PROC 0x9FA0\n+# define S_MAGIC_TMPFS 0x1021994\n+\n+# ifdef HAVE___FSWORD_T\n+typedef __fsword_t fsword;\n+# else\n+typedef long int fsword;\n+# endif\n+\n+/* Map a stat.st_dev number to a file system type number f_ftype. */\n+struct dev_type\n+{\n+ dev_t st_dev;\n+ fsword f_type;\n+};\n+\n+/* Use a tiny initial size. If a traversal encounters more than\n+ a few devices, the cost of growing/rehashing this table will be\n+ rendered negligible by the number of inodes processed. */\n+enum { DEV_TYPE_HT_INITIAL_SIZE = 13 };\n+\n+static size_t\n+dev_type_hash (void const *x, size_t table_size)\n+{\n+ struct dev_type const *ax = x;\n+ uintmax_t dev = ax->st_dev;\n+ return dev % table_size;\n+}\n+\n+static bool\n+dev_type_compare (void const *x, void const *y)\n+{\n+ struct dev_type const *ax = x;\n+ struct dev_type const *ay = y;\n+ return ax->st_dev == ay->st_dev;\n+}\n+\n+/* Return the file system type of P with file descriptor FD, or 0 if not known.\n+ If FD is negative, P's file descriptor is unavailable.\n+ Try to cache known values. */\n+\n+static fsword\n+filesystem_type (FTSENTRY const *p, int fd)\n+{\n+ FTSOBJ *sp = FTSENT_FTS(p);\n+\n+ /* If we're not in CWDFD mode, don't bother with this optimization,\n+ since the caller is not serious about performance. */\n+ if (!ISSET (FTS_CWDFD))\n+ return 0;\n+\n+ Hash_table *h = sp->fts_leaf_optimization_works_ht;\n+ if (! h)\n+ h = sp->fts_leaf_optimization_works_ht\n+ = hash_initialize (DEV_TYPE_HT_INITIAL_SIZE, NULL, dev_type_hash,\n+ dev_type_compare, free);\n+\n+ if (h)\n+ {\n+ struct dev_type tmp;\n+ tmp.st_dev = p->fts_statp->st_dev;\n+ struct dev_type *ent = hash_lookup (h, &tmp);\n+ if (ent)\n+ return ent->f_type;\n+ }\n+\n+ /* Look-up failed. Query directly and cache the result. */\n+ struct STRUCT_STATFS fs_buf;\n+ if (fd < 0 || FSTATFS (fd, &fs_buf) != 0)\n+ return 0;\n+\n+ if (h)\n+ {\n+ struct dev_type *t2 = malloc (sizeof *t2);\n+ if (t2)\n+ {\n+ t2->st_dev = p->fts_statp->st_dev;\n+ t2->f_type = fs_buf.f_type;\n+\n+ struct dev_type *ent = hash_insert (h, t2);\n+ if (ent)\n+ fts_assert (ent == t2);\n+ else\n+ free (t2);\n+ }\n+ }\n+\n+ return fs_buf.f_type;\n+}\n+\n+/* Return true if sorting dirents on inode numbers is known to improve\n+ traversal performance for the directory P with descriptor DIR_FD.\n+ Return false otherwise. When in doubt, return true.\n+ DIR_FD is negative if unavailable. */\n+static bool\n+dirent_inode_sort_may_be_useful (FTSENTRY const *p, int dir_fd)\n+{\n+ /* Skip the sort only if we can determine efficiently\n+ that skipping it is the right thing to do.\n+ The cost of performing an unnecessary sort is negligible,\n+ while the cost of *not* performing it can be O(N^2) with\n+ a very large constant. */\n+\n+ switch (filesystem_type (p, dir_fd))\n+ {\n+ case S_MAGIC_LUSTRE:\n+ /* On Lustre, sorting directory entries interferes with its ability to\n+ prefetch file metadata (via statahead). This would make a command\n+ like 'du' around 9 times slower. See\n+ <https://bugs.gnu.org/80106>. */\n+ case S_MAGIC_CIFS:\n+ case S_MAGIC_NFS:\n+ case S_MAGIC_TMPFS:\n+ /* On a file system of any of these types, sorting\n+ is unnecessary, and hence wasteful. */\n+ return false;\n+\n+ default:\n+ return true;\n+ }\n+}\n+\n+/* Given an FTS entry P for a directory with descriptor DIR_FD,\n+ return whether it is valid to apply leaf optimization.\n+ The optimization is valid if a directory's st_nlink value equal\n+ to MIN_DIR_NLINK means the directory has no subdirectories.\n+ DIR_FD is negative if unavailable. */\n+static enum leaf_optimization\n+leaf_optimization (FTSENTRY const *p, int dir_fd)\n+{\n+ switch (filesystem_type (p, dir_fd))\n+ {\n+ case 0:\n+ /* Leaf optimization is unsafe if the file system type is unknown. */\n+ FALLTHROUGH;\n+ case S_MAGIC_AFS:\n+ /* Although AFS mount points are not counted in st_nlink, they\n+ act like directories. See <https://bugs.debian.org/143111>. */\n+ FALLTHROUGH;\n+ case S_MAGIC_CIFS:\n+ /* Leaf optimization causes 'find' to abort. See\n+ <https://lists.gnu.org/r/bug-gnulib/2018-04/msg00015.html>. */\n+ FALLTHROUGH;\n+ case S_MAGIC_NFS:\n+ /* NFS provides usable dirent.d_type but not necessarily for all entries\n+ of large directories, so as per <https://bugzilla.redhat.com/1252549>\n+ NFS should return true. However st_nlink values are not accurate on\n+ all implementations as per <https://bugzilla.redhat.com/1299169>. */\n+ FALLTHROUGH;\n+ case S_MAGIC_PROC:\n+ /* Per <https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=143111> /proc\n+ may have bogus stat.st_nlink values. */\n+ return NO_LEAF_OPTIMIZATION;\n+\n+ default:\n+ return OK_LEAF_OPTIMIZATION;\n+ }\n+}\n+\n+#else\n+static bool\n+dirent_inode_sort_may_be_useful (_GL_UNUSED FTSENTRY const *p,\n+ _GL_UNUSED int dir_fd)\n+{\n+ return true;\n+}\n+static enum leaf_optimization\n+leaf_optimization (_GL_UNUSED FTSENTRY const *p, _GL_UNUSED int dir_fd)\n+{\n+ return NO_LEAF_OPTIMIZATION;\n+}\n+#endif\n+\n /*\n- * Special case of \"/\" at the end of the path so that slashes aren't\n- * appended which would cause paths to be written as \"....//foo\".\n+ * Special case of \"/\" at the end of the file name so that slashes aren't\n+ * appended which would cause file names to be written as \"....//foo\".\n */\n-#define\tNAPPEND(p)\t\t\t\t\t\t\t\\\n-\t(p->fts_path[p->fts_pathlen - 1] == '/'\t\t\t\t\\\n-\t ? p->fts_pathlen - 1 : p->fts_pathlen)\n+#define NAPPEND(p) \\\n+ (p->fts_path[p->fts_pathlen - 1] == '/' \\\n+ ? p->fts_pathlen - 1 : p->fts_pathlen)\n \n FTSENTRY *\n FTS_READ (FTSOBJ *sp)\n {\n-\tFTSENTRY *p, *tmp;\n-\tint instr;\n-\tchar *t;\n-\tint saved_errno;\n+ /* If finished or unrecoverable error, return NULL. */\n+ if (sp->fts_cur == NULL || ISSET(FTS_STOP))\n+ return (NULL);\n \n-\t/* If finished or unrecoverable error, return NULL. */\n-\tif (sp->fts_cur == NULL || ISSET(FTS_STOP))\n-\t\treturn (NULL);\n+ /* Set current node pointer. */\n+ register FTSENTRY *p = sp->fts_cur;\n \n-\t/* Set current node pointer. */\n-\tp = sp->fts_cur;\n+ /* Save and zero out user instructions. */\n+ register unsigned short int instr = p->fts_instr;\n+ p->fts_instr = FTS_NOINSTR;\n \n-\t/* Save and zero out user instructions. */\n-\tinstr = p->fts_instr;\n-\tp->fts_instr = FTS_NOINSTR;\n+ /* Any type of file may be re-visited; re-stat and re-turn. */\n+ if (instr == FTS_AGAIN) {\n+ p->fts_info = fts_stat(sp, p, false);\n+ return (p);\n+ }\n+ Dprintf ((\"fts_read: p=%s\\n\",\n+ p->fts_info == FTS_INIT ? \"\" : p->fts_path));\n \n-\t/* Any type of file may be re-visited; re-stat and re-turn. */\n-\tif (instr == FTS_AGAIN) {\n-\t\tp->fts_info = fts_stat(sp, p, 0);\n-\t\treturn (p);\n-\t}\n+ /*\n+ * Following a symlink -- SLNONE test allows application to see\n+ * SLNONE and recover. If indirecting through a symlink, have\n+ * keep a pointer to current location. If unable to get that\n+ * pointer, follow fails.\n+ */\n+ if (instr == FTS_FOLLOW &&\n+ (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {\n+ p->fts_info = fts_stat(sp, p, true);\n+ if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {\n+ if ((p->fts_symfd = diropen (sp, \".\")) < 0) {\n+ p->fts_errno = errno;\n+ p->fts_info = FTS_ERR;\n+ } else\n+ p->fts_flags |= FTS_SYMFOLLOW;\n+ }\n+ goto check_for_dir;\n+ }\n \n-\t/*\n-\t * Following a symlink -- SLNONE test allows application to see\n-\t * SLNONE and recover. If indirecting through a symlink, have\n-\t * keep a pointer to current location. If unable to get that\n-\t * pointer, follow fails.\n-\t */\n-\tif (instr == FTS_FOLLOW &&\n-\t (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {\n-\t\tp->fts_info = fts_stat(sp, p, 1);\n-\t\tif (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {\n-\t\t\tif ((p->fts_symfd = __open(\".\", O_RDONLY, 0)) < 0) {\n-\t\t\t\tp->fts_errno = errno;\n-\t\t\t\tp->fts_info = FTS_ERR;\n-\t\t\t} else\n-\t\t\t\tp->fts_flags |= FTS_SYMFOLLOW;\n-\t\t}\n-\t\treturn (p);\n-\t}\n+ /* Directory in pre-order. */\n+ if (p->fts_info == FTS_D) {\n+ /* If skipped or crossed mount point, do post-order visit. */\n+ if (instr == FTS_SKIP ||\n+ (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {\n+ if (p->fts_flags & FTS_SYMFOLLOW)\n+ (void)close(p->fts_symfd);\n+ if (sp->fts_child) {\n+ fts_lfree(sp->fts_child);\n+ sp->fts_child = NULL;\n+ }\n+ p->fts_info = FTS_DP;\n+ LEAVE_DIR (sp, p, \"1\");\n+ return (p);\n+ }\n \n-\t/* Directory in pre-order. */\n-\tif (p->fts_info == FTS_D) {\n-\t\t/* If skipped or crossed mount point, do post-order visit. */\n-\t\tif (instr == FTS_SKIP ||\n-\t\t (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {\n-\t\t\tif (p->fts_flags & FTS_SYMFOLLOW)\n-\t\t\t\t(void)__close(p->fts_symfd);\n-\t\t\tif (sp->fts_child) {\n-\t\t\t\tfts_lfree(sp->fts_child);\n-\t\t\t\tsp->fts_child = NULL;\n-\t\t\t}\n-\t\t\tp->fts_info = FTS_DP;\n-\t\t\treturn (p);\n-\t\t}\n+ /* Rebuild if only read the names and now traversing. */\n+ if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {\n+ CLR(FTS_NAMEONLY);\n+ fts_lfree(sp->fts_child);\n+ sp->fts_child = NULL;\n+ }\n \n-\t\t/* Rebuild if only read the names and now traversing. */\n-\t\tif (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {\n-\t\t\tCLR(FTS_NAMEONLY);\n-\t\t\tfts_lfree(sp->fts_child);\n-\t\t\tsp->fts_child = NULL;\n-\t\t}\n+ /*\n+ * Cd to the subdirectory.\n+ *\n+ * If have already read and now fail to chdir, whack the list\n+ * to make the names come out right, and set the parent errno\n+ * so the application will eventually get an error condition.\n+ * Set the FTS_DONTCHDIR flag so that when we logically change\n+ * directories back to the parent we don't do a chdir.\n+ *\n+ * If haven't read do so. If the read fails, fts_build sets\n+ * FTS_STOP or the fts_info field of the node.\n+ */\n+ if (sp->fts_child != NULL) {\n+ if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {\n+ p->fts_errno = errno;\n+ p->fts_flags |= FTS_DONTCHDIR;\n+ for (p = sp->fts_child; p != NULL;\n+ p = p->fts_link)\n+ p->fts_accpath =\n+ p->fts_parent->fts_accpath;\n+ }\n+ } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {\n+ if (ISSET(FTS_STOP))\n+ return (NULL);\n+ /* If fts_build's call to fts_safe_changedir failed\n+ because it was not able to fchdir into a\n+ subdirectory, tell the caller. */\n+ if (p->fts_errno && p->fts_info != FTS_DNR)\n+ p->fts_info = FTS_ERR;\n+ LEAVE_DIR (sp, p, \"2\");\n+ return (p);\n+ }\n+ p = sp->fts_child;\n+ sp->fts_child = NULL;\n+ goto name;\n+ }\n \n-\t\t/*\n-\t\t * Cd to the subdirectory.\n-\t\t *\n-\t\t * If have already read and now fail to chdir, whack the list\n-\t\t * to make the names come out right, and set the parent errno\n-\t\t * so the application will eventually get an error condition.\n-\t\t * Set the FTS_DONTCHDIR flag so that when we logically change\n-\t\t * directories back to the parent we don't do a chdir.\n-\t\t *\n-\t\t * If haven't read do so. If the read fails, fts_build sets\n-\t\t * FTS_STOP or the fts_info field of the node.\n-\t\t */\n-\t\tif (sp->fts_child != NULL) {\n-\t\t\tif (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {\n-\t\t\t\tp->fts_errno = errno;\n-\t\t\t\tp->fts_flags |= FTS_DONTCHDIR;\n-\t\t\t\tfor (p = sp->fts_child; p != NULL;\n-\t\t\t\t p = p->fts_link)\n-\t\t\t\t\tp->fts_accpath =\n-\t\t\t\t\t p->fts_parent->fts_accpath;\n-\t\t\t}\n-\t\t} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {\n-\t\t\tif (ISSET(FTS_STOP))\n-\t\t\t\treturn (NULL);\n-\t\t\treturn (p);\n-\t\t}\n-\t\tp = sp->fts_child;\n-\t\tsp->fts_child = NULL;\n-\t\tsp->fts_cur = p;\n-\t\tgoto name;\n-\t}\n+ /* Move to the next node on this level. */\n+next: ;\n+ register FTSENTRY *tmp = p;\n \n-\t/* Move to the next node on this level. */\n-next:\ttmp = p;\n-\tif ((p = p->fts_link) != NULL) {\n-\t\tsp->fts_cur = p;\n-\t\tfree(tmp);\n+ /* If we have so many directory entries that we're reading them\n+ in batches, and we've reached the end of the current batch,\n+ read in a new batch. */\n+ if (p->fts_link == NULL && FTSENT_DIRP(p->fts_parent))\n+ {\n+ p = tmp->fts_parent;\n+ sp->fts_cur = p;\n+ sp->fts_path[p->fts_pathlen] = '\\0';\n \n-\t\t/*\n-\t\t * If reached the top, return to the original directory (or\n-\t\t * the root of the tree), and load the paths for the next root.\n-\t\t */\n-\t\tif (p->fts_level == FTS_ROOTLEVEL) {\n-\t\t\tif (FCHDIR(sp, sp->fts_rfd)) {\n-\t\t\t\tSET(FTS_STOP);\n-\t\t\t\treturn (NULL);\n-\t\t\t}\n-\t\t\tfts_load(sp, p);\n-\t\t\treturn p;\n-\t\t}\n+ if ((p = fts_build (sp, BREAD)) == NULL)\n+ {\n+ if (ISSET(FTS_STOP))\n+ return NULL;\n+ goto cd_dot_dot;\n+ }\n \n-\t\t/*\n-\t\t * User may have called fts_set on the node. If skipped,\n-\t\t * ignore. If followed, get a file descriptor so we can\n-\t\t * get back if necessary.\n-\t\t */\n-\t\tif (p->fts_instr == FTS_SKIP)\n-\t\t\tgoto next;\n-\t\tif (p->fts_instr == FTS_FOLLOW) {\n-\t\t\tp->fts_info = fts_stat(sp, p, 1);\n-\t\t\tif (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {\n-\t\t\t\tif ((p->fts_symfd =\n-\t\t\t\t __open(\".\", O_RDONLY, 0)) < 0) {\n-\t\t\t\t\tp->fts_errno = errno;\n-\t\t\t\t\tp->fts_info = FTS_ERR;\n-\t\t\t\t} else\n-\t\t\t\t\tp->fts_flags |= FTS_SYMFOLLOW;\n-\t\t\t}\n-\t\t\tp->fts_instr = FTS_NOINSTR;\n-\t\t}\n+ free(FTSENT_WRAPPER(tmp));\n+ goto name;\n+ }\n \n-name:\t\tt = sp->fts_path + NAPPEND(p->fts_parent);\n-\t\t*t++ = '/';\n-\t\tmemmove(t, p->fts_name, p->fts_namelen + 1);\n-\t\treturn p;\n-\t}\n+ if ((p = p->fts_link) != NULL) {\n+ sp->fts_cur = p;\n+ free(FTSENT_WRAPPER(tmp));\n \n-\t/* Move up to the parent node. */\n-\tp = tmp->fts_parent;\n-\tsp->fts_cur = p;\n-\tfree(tmp);\n+ /*\n+ * If reached the top, return to the original directory (or\n+ * the root of the tree), and load the file names for the next\n+ * root.\n+ */\n+ if (p->fts_level == FTS_ROOTLEVEL) {\n+ if (restore_initial_cwd(sp)) {\n+ SET(FTS_STOP);\n+ return (NULL);\n+ }\n+ free_dir(sp);\n+ fts_load(sp, p);\n+ if (! setup_dir(sp)) {\n+ free_dir(sp);\n+ return (NULL);\n+ }\n+ goto check_for_dir;\n+ }\n \n-\tif (p->fts_level == FTS_ROOTPARENTLEVEL) {\n-\t\t/*\n-\t\t * Done; free everything up and set errno to 0 so the user\n-\t\t * can distinguish between error and EOF.\n-\t\t */\n-\t\tfree(p);\n-\t\t__set_errno (0);\n-\t\treturn (sp->fts_cur = NULL);\n-\t}\n+ /*\n+ * User may have called fts_set on the node. If skipped,\n+ * ignore. If followed, get a file descriptor so we can\n+ * get back if necessary.\n+ */\n+ if (p->fts_instr == FTS_SKIP)\n+ goto next;\n+ if (p->fts_instr == FTS_FOLLOW) {\n+ p->fts_info = fts_stat(sp, p, true);\n+ if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {\n+ if ((p->fts_symfd = diropen (sp, \".\")) < 0) {\n+ p->fts_errno = errno;\n+ p->fts_info = FTS_ERR;\n+ } else\n+ p->fts_flags |= FTS_SYMFOLLOW;\n+ }\n+ p->fts_instr = FTS_NOINSTR;\n+ }\n \n-\t/* NUL terminate the pathname. */\n-\tsp->fts_path[p->fts_pathlen] = '\\0';\n+name: {\n+ register char *t = sp->fts_path + NAPPEND(p->fts_parent);\n+ *t++ = '/';\n+ memmove(t, p->fts_name, p->fts_namelen + 1);\n+ }\n+check_for_dir:\n+ sp->fts_cur = p;\n+ if (p->fts_info == FTS_NSOK)\n+ {\n+ if (p->fts_statp->st_size == FTS_STAT_REQUIRED)\n+ p->fts_info = fts_stat(sp, p, false);\n+ else\n+ fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);\n+ }\n \n-\t/*\n-\t * Return to the parent directory. If at a root node or came through\n-\t * a symlink, go back through the file descriptor. Otherwise, cd up\n-\t * one directory.\n-\t */\n-\tif (p->fts_level == FTS_ROOTLEVEL) {\n-\t\tif (FCHDIR(sp, sp->fts_rfd)) {\n-\t\t\tSET(FTS_STOP);\n-\t\t\treturn (NULL);\n-\t\t}\n-\t} else if (p->fts_flags & FTS_SYMFOLLOW) {\n-\t\tif (FCHDIR(sp, p->fts_symfd)) {\n-\t\t\tsaved_errno = errno;\n-\t\t\t(void)__close(p->fts_symfd);\n-\t\t\t__set_errno (saved_errno);\n-\t\t\tSET(FTS_STOP);\n-\t\t\treturn (NULL);\n-\t\t}\n-\t\t(void)__close(p->fts_symfd);\n-\t} else if (!(p->fts_flags & FTS_DONTCHDIR) &&\n-\t\t fts_safe_changedir(sp, p->fts_parent, -1, \"..\")) {\n-\t\tSET(FTS_STOP);\n-\t\treturn (NULL);\n-\t}\n-\tp->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;\n-\treturn p;\n+ /* Skip files with different device numbers when FTS_MOUNT\n+ is set. */\n+ if (ISSET (FTS_MOUNT) && p->fts_info != FTS_NS &&\n+ p->fts_level != FTS_ROOTLEVEL &&\n+ p->fts_statp->st_dev != sp->fts_dev)\n+ goto next;\n+\n+ if (p->fts_info == FTS_D)\n+ {\n+ /* Now that P->fts_statp is guaranteed to be valid, if\n+ this is a command-line directory, record its device\n+ number, to be used for FTS_MOUNT and FTS_XDEV. */\n+ if (p->fts_level == FTS_ROOTLEVEL)\n+ sp->fts_dev = p->fts_statp->st_dev;\n+ Dprintf ((\" entering: %s\\n\", p->fts_path));\n+ if (! enter_dir (sp, p))\n+ return NULL;\n+ }\n+ return p;\n+ }\n+cd_dot_dot:\n+\n+ /* Move up to the parent node. */\n+ p = tmp->fts_parent;\n+ sp->fts_cur = p;\n+ free(FTSENT_WRAPPER(tmp));\n+\n+ if (p->fts_level == FTS_ROOTPARENTLEVEL) {\n+ /*\n+ * Done; free everything up and set errno to 0 so the user\n+ * can distinguish between error and EOF.\n+ */\n+ free(FTSENT_WRAPPER(p));\n+ __set_errno (0);\n+ return (sp->fts_cur = NULL);\n+ }\n+\n+ fts_assert (p->fts_info != FTS_NSOK);\n+\n+ /* NUL terminate the file name. */\n+ sp->fts_path[p->fts_pathlen] = '\\0';\n+\n+ /*\n+ * Return to the parent directory. If at a root node, restore\n+ * the initial working directory. If we came through a symlink,\n+ * go back through the file descriptor. Otherwise, move up\n+ * one level, via \"..\".\n+ */\n+ if (p->fts_level == FTS_ROOTLEVEL) {\n+ if (restore_initial_cwd(sp)) {\n+ p->fts_errno = errno;\n+ SET(FTS_STOP);\n+ }\n+ } else if (p->fts_flags & FTS_SYMFOLLOW) {\n+ if (FCHDIR(sp, p->fts_symfd)) {\n+ p->fts_errno = errno;\n+ SET(FTS_STOP);\n+ }\n+ (void)close(p->fts_symfd);\n+ } else if (!(p->fts_flags & FTS_DONTCHDIR) &&\n+ fts_safe_changedir(sp, p->fts_parent, -1, \"..\")) {\n+ p->fts_errno = errno;\n+ SET(FTS_STOP);\n+ }\n+\n+ /* If the directory causes a cycle, preserve the FTS_DC flag and keep\n+ the corresponding dev/ino pair in the hash table. It is going to be\n+ removed when leaving the original directory. */\n+ if (p->fts_info != FTS_DC) {\n+ p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;\n+ if (p->fts_errno == 0)\n+ LEAVE_DIR (sp, p, \"3\");\n+ }\n+ return ISSET(FTS_STOP) ? NULL : p;\n }\n \n /*\n@@ -506,93 +1170,157 @@ name:\t\tt = sp->fts_path + NAPPEND(p->fts_parent);\n */\n /* ARGSUSED */\n int\n-FTS_SET (FTSOBJ *sp, FTSENTRY *p, int instr)\n+FTS_SET (_GL_UNUSED FTSOBJ *sp, FTSENTRY *p, int instr)\n {\n-\tif (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&\n-\t instr != FTS_NOINSTR && instr != FTS_SKIP) {\n-\t\t__set_errno (EINVAL);\n-\t\treturn (1);\n-\t}\n-\tp->fts_instr = instr;\n-\treturn (0);\n+ if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&\n+ instr != FTS_NOINSTR && instr != FTS_SKIP) {\n+ __set_errno (EINVAL);\n+ return (1);\n+ }\n+ p->fts_instr = instr;\n+ return (0);\n }\n \n FTSENTRY *\n-FTS_CHILDREN(FTSOBJ *sp, int instr)\n+FTS_CHILDREN (FTSOBJ *sp, int instr)\n {\n-\tFTSENTRY *p;\n-\tint fd;\n+ if (instr != 0 && instr != FTS_NAMEONLY) {\n+ __set_errno (EINVAL);\n+ return (NULL);\n+ }\n \n-\tif (instr != 0 && instr != FTS_NAMEONLY) {\n-\t\t__set_errno (EINVAL);\n-\t\treturn (NULL);\n-\t}\n+ /* Set current node pointer. */\n+ register FTSENTRY *p = sp->fts_cur;\n \n-\t/* Set current node pointer. */\n-\tp = sp->fts_cur;\n+ /*\n+ * Errno set to 0 so user can distinguish empty directory from\n+ * an error.\n+ */\n+ __set_errno (0);\n \n-\t/*\n-\t * Errno set to 0 so user can distinguish empty directory from\n-\t * an error.\n-\t */\n-\t__set_errno (0);\n+ /* Fatal errors stop here. */\n+ if (ISSET(FTS_STOP))\n+ return (NULL);\n \n-\t/* Fatal errors stop here. */\n-\tif (ISSET(FTS_STOP))\n-\t\treturn (NULL);\n+ /* Return logical hierarchy of user's arguments. */\n+ if (p->fts_info == FTS_INIT)\n+ return (p->fts_link);\n \n-\t/* Return logical hierarchy of user's arguments. */\n-\tif (p->fts_info == FTS_INIT)\n-\t\treturn (p->fts_link);\n+ /*\n+ * If not a directory being visited in pre-order, stop here. Could\n+ * allow FTS_DNR, assuming the user has fixed the problem, but the\n+ * same effect is available with FTS_AGAIN.\n+ */\n+ if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)\n+ return (NULL);\n \n-\t/*\n-\t * If not a directory being visited in pre-order, stop here. Could\n-\t * allow FTS_DNR, assuming the user has fixed the problem, but the\n-\t * same effect is available with FTS_AGAIN.\n-\t */\n-\tif (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)\n-\t\treturn (NULL);\n+ /* Free up any previous child list. */\n+ if (sp->fts_child != NULL)\n+ fts_lfree(sp->fts_child);\n \n-\t/* Free up any previous child list. */\n-\tif (sp->fts_child != NULL)\n-\t\tfts_lfree(sp->fts_child);\n+ if (instr == FTS_NAMEONLY) {\n+ SET(FTS_NAMEONLY);\n+ instr = BNAMES;\n+ } else\n+ instr = BCHILD;\n \n-\tif (instr == FTS_NAMEONLY) {\n-\t\tSET(FTS_NAMEONLY);\n-\t\tinstr = BNAMES;\n-\t} else\n-\t\tinstr = BCHILD;\n+ /*\n+ * If using chdir on a relative file name and called BEFORE fts_read\n+ * does its chdir to the root of a traversal, we can lose -- we need to\n+ * chdir into the subdirectory, and we don't know where the current\n+ * directory is, so we can't get back so that the upcoming chdir by\n+ * fts_read will work.\n+ */\n+ if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||\n+ ISSET(FTS_NOCHDIR))\n+ return (sp->fts_child = fts_build(sp, instr));\n \n-\t/*\n-\t * If using chdir on a relative path and called BEFORE fts_read does\n-\t * its chdir to the root of a traversal, we can lose -- we need to\n-\t * chdir into the subdirectory, and we don't know where the current\n-\t * directory is, so we can't get back so that the upcoming chdir by\n-\t * fts_read will work.\n-\t */\n-\tif (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||\n-\t ISSET(FTS_NOCHDIR))\n-\t\treturn (sp->fts_child = fts_build(sp, instr));\n-\n-\tif ((fd = __open(\".\", O_RDONLY, 0)) < 0)\n-\t\treturn (NULL);\n-\tsp->fts_child = fts_build(sp, instr);\n-\tif (__fchdir(fd))\n-\t\treturn (NULL);\n-\t(void)__close(fd);\n-\treturn (sp->fts_child);\n+ int fd = diropen (sp, \".\");\n+ if (fd < 0)\n+ return (sp->fts_child = NULL);\n+ sp->fts_child = fts_build(sp, instr);\n+ if (ISSET(FTS_CWDFD))\n+ {\n+ cwd_advance_fd (sp, fd, true);\n+ }\n+ else\n+ {\n+ if (fchdir(fd))\n+ {\n+ int saved_errno = errno;\n+ close (fd);\n+ __set_errno (saved_errno);\n+ return NULL;\n+ }\n+ close (fd);\n+ }\n+ return (sp->fts_child);\n }\n \n-static inline int\n-dirent_not_directory(const struct dirent *dp)\n+/* A comparison function to sort on increasing inode number.\n+ For some file system types, sorting either way makes a huge\n+ performance difference for a directory with very many entries,\n+ but sorting on increasing values is slightly better than sorting\n+ on decreasing values. The difference is in the 5% range. */\n+static int\n+fts_compare_ino (FTSENTRY const **a, FTSENTRY const **b)\n {\n-#if defined DT_DIR && defined _DIRENT_HAVE_D_TYPE\n- return dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN;\n-#else\n- return 0;\n-#endif\n+ return _GL_CMP (a[0]->fts_statp->st_ino, b[0]->fts_statp->st_ino);\n }\n \n+/* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode\n+ S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */\n+static void\n+set_stat_type (struct STRUCT_STAT *st, unsigned int dtype)\n+{\n+ mode_t type;\n+ switch (dtype)\n+ {\n+ case DT_BLK:\n+ type = S_IFBLK;\n+ break;\n+ case DT_CHR:\n+ type = S_IFCHR;\n+ break;\n+ case DT_DIR:\n+ type = S_IFDIR;\n+ break;\n+ case DT_FIFO:\n+ type = S_IFIFO;\n+ break;\n+ case DT_LNK:\n+ type = S_IFLNK;\n+ break;\n+ case DT_REG:\n+ type = S_IFREG;\n+ break;\n+ case DT_SOCK:\n+ type = S_IFSOCK;\n+ break;\n+ default:\n+ type = 0;\n+ }\n+ st->st_mode = type;\n+}\n+\n+#define closedir_and_clear(dirp) \\\n+ do \\\n+ { \\\n+ closedir (dirp); \\\n+ dirp = NULL; \\\n+ } \\\n+ while (0)\n+\n+#define fts_opendir(file, Pdir_fd) \\\n+ OPENDIRAT((! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \\\n+ ? sp->fts_cwd_fd : AT_FDCWD), \\\n+ file, \\\n+ (((ISSET(FTS_PHYSICAL) \\\n+ && ! (ISSET(FTS_COMFOLLOW) \\\n+ && cur->fts_level == FTS_ROOTLEVEL)) \\\n+ ? O_NOFOLLOW : 0)), \\\n+ Pdir_fd)\n+\n /*\n * This is the tricky part -- do not casually change *anything* in here. The\n * idea is to build the linked list of entries that are used by fts_children\n@@ -608,531 +1336,873 @@ dirent_not_directory(const struct dirent *dp)\n * been found, cutting the stat calls by about 2/3.\n */\n static FTSENTRY *\n-fts_build (FTSOBJ *sp, int type)\n+internal_function\n+fts_build (register FTSOBJ *sp, int type)\n {\n-\tstruct dirent *dp;\n-\tFTSENTRY *p, *head;\n-\tint nitems;\n-\tFTSENTRY *cur, *tail;\n-\tDIR *dirp;\n-\tvoid *oldaddr;\n-\tint cderrno, descend, len, level, nlinks, saved_errno,\n-\t nostat, doadjust;\n-\tsize_t maxlen;\n-\tchar *cp;\n+ FTSENTRY *cur = sp->fts_cur;\n+ bool continue_readdir = !!FTSENT_DIRP(cur);\n \n-\t/* Set current node pointer. */\n-\tcur = sp->fts_cur;\n+ /* When cur->fts_dirp is non-NULL, that means we should\n+ continue calling readdir on that existing DIR* pointer\n+ rather than opening a new one. */\n+ int dir_fd;\n+ if (continue_readdir)\n+ {\n+ DIR *dp = FTSENT_DIRP(cur);\n+ dir_fd = dirfd (dp);\n+ if (dir_fd < 0)\n+ {\n+ int dirfd_errno = errno;\n+ closedir_and_clear (FTSENT_DIRP(cur));\n+ if (type == BREAD)\n+ {\n+ cur->fts_info = FTS_DNR;\n+ cur->fts_errno = dirfd_errno;\n+ }\n+ return NULL;\n+ }\n+ }\n+ else\n+ {\n+ /* Open the directory for reading. If this fails, we're done.\n+ If being called from fts_read, set the fts_info field. */\n+ if ((FTSENT_DIRP (cur) = fts_opendir(cur->fts_accpath, &dir_fd)) == NULL)\n+ {\n+ if (type == BREAD)\n+ {\n+ cur->fts_info = FTS_DNR;\n+ cur->fts_errno = errno;\n+ }\n+ return NULL;\n+ }\n+ /* Rather than calling fts_stat for each and every entry encountered\n+ in the readdir loop (below), stat each directory only right after\n+ opening it. */\n+ bool stat_optimization = cur->fts_info == FTS_NSOK;\n \n-\t/*\n-\t * Open the directory for reading. If this fails, we're done.\n-\t * If being called from fts_read, set the fts_info field.\n-\t */\n-#if defined FTS_WHITEOUT && 0\n-\tif (ISSET(FTS_WHITEOUT))\n-\t\toflag = DTF_NODUP|DTF_REWIND;\n-\telse\n-\t\toflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;\n-#else\n-# define __opendir2(path, flag) __opendir(path)\n+ if (stat_optimization\n+ /* Also read the stat info again after opening a directory to\n+ reveal eventual changes caused by a submount triggered by\n+ the traversal. But do it only for utilities which use\n+ FTS_TIGHT_CYCLE_CHECK. Therefore, only find and du\n+ benefit/suffer from this feature for now. */\n+ || ISSET (FTS_TIGHT_CYCLE_CHECK))\n+ {\n+ if (!stat_optimization)\n+ LEAVE_DIR (sp, cur, \"4\");\n+ if (FSTAT (dir_fd, cur->fts_statp) != 0)\n+ {\n+ int fstat_errno = errno;\n+ closedir_and_clear (FTSENT_DIRP(cur));\n+ if (type == BREAD)\n+ {\n+ cur->fts_errno = fstat_errno;\n+ cur->fts_info = FTS_NS;\n+ }\n+ __set_errno (fstat_errno);\n+ return NULL;\n+ }\n+ if (stat_optimization)\n+ cur->fts_info = FTS_D;\n+ else if (! enter_dir (sp, cur))\n+ {\n+ int saved_errno = errno;\n+ closedir_and_clear (FTSENT_DIRP(cur));\n+ __set_errno (saved_errno);\n+ return NULL;\n+ }\n+ }\n+ }\n+\n+ /* Maximum number of readdir entries to read at one time. This\n+ limitation is to avoid reading millions of entries into memory\n+ at once. When an fts_compar function is specified, we have no\n+ choice: we must read all entries into memory before calling that\n+ function. But when no such function is specified, we can read\n+ entries in batches that are large enough to help us with inode-\n+ sorting, yet not so large that we risk exhausting memory. */\n+ size_t max_entries = sp->fts_compar ? SIZE_MAX : FTS_MAX_READDIR_ENTRIES;\n+\n+ /*\n+ * If we're going to need to stat anything or we want to descend\n+ * and stay in the directory, chdir. If this fails we keep going,\n+ * but set a flag so we don't chdir after the post-order visit.\n+ * We won't be able to stat anything, but we can still return the\n+ * names themselves. Note, that since fts_read won't be able to\n+ * chdir into the directory, it will have to return different file\n+ * names than before, i.e. \"a/b\" instead of \"b\". Since the node\n+ * has already been visited in pre-order, have to wait until the\n+ * post-order visit to return the error. There is a special case\n+ * here, if there was nothing to stat then it's not an error to\n+ * not be able to stat. This is all fairly nasty. If a program\n+ * needed sorted entries or stat information, they had better be\n+ * checking FTS_NS on the returned nodes.\n+ */\n+ bool descend;\n+ if (continue_readdir)\n+ {\n+ /* When resuming a short readdir run, we already have\n+ the required dirp and dir_fd. */\n+ descend = true;\n+ }\n+ else\n+ {\n+ /* Try to descend unless it is a names-only fts_children,\n+ or the directory is known to lack subdirectories. */\n+ descend = (type != BNAMES\n+ && ! (ISSET (FTS_NOSTAT) && ISSET (FTS_PHYSICAL)\n+ && ! ISSET (FTS_SEEDOT)\n+ && cur->fts_statp->st_nlink == MIN_DIR_NLINK\n+ && (leaf_optimization (cur, dir_fd)\n+ != NO_LEAF_OPTIMIZATION)));\n+ if (descend || type == BREAD)\n+ {\n+ if (ISSET(FTS_CWDFD))\n+ dir_fd = fcntl (dir_fd, F_DUPFD_CLOEXEC, STDERR_FILENO + 1);\n+ if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {\n+ if (descend && type == BREAD)\n+ cur->fts_errno = errno;\n+ cur->fts_flags |= FTS_DONTCHDIR;\n+ descend = false;\n+ closedir_and_clear(FTSENT_DIRP(cur));\n+ if (ISSET(FTS_CWDFD) && 0 <= dir_fd)\n+ close (dir_fd);\n+ FTSENT_DIRP(cur) = NULL;\n+ } else\n+ descend = true;\n+ }\n+ }\n+\n+ /*\n+ * Figure out the max file name length that can be stored in the\n+ * current buffer -- the inner loop allocates more space as necessary.\n+ * We really wouldn't have to do the maxlen calculations here, we\n+ * could do them in fts_read before returning the name, but it's a\n+ * lot easier here since the length is part of the dirent structure.\n+ *\n+ * If not changing directories set a pointer so that can just append\n+ * each new component into the file name.\n+ */\n+ size_t len = NAPPEND(cur);\n+ char *cp;\n+ if (ISSET(FTS_NOCHDIR)) {\n+ cp = sp->fts_path + len;\n+ *cp++ = '/';\n+ } else {\n+ /* GCC, you're too verbose. */\n+ cp = NULL;\n+ }\n+ len++;\n+ size_t maxlen = sp->fts_pathlen - len;\n+\n+ ptrdiff_t level = cur->fts_level + 1;\n+\n+ /* Read the directory, attaching each entry to the \"link\" pointer. */\n+ bool doadjust = false;\n+ register FTSENTRY *head = NULL;\n+ FTSENTRY *tail = NULL;\n+ register size_t nitems = 0;\n+ bool sort_by_inode = false;\n+ while (FTSENT_DIRP(cur)) {\n+ __set_errno (0);\n+ struct dirent *dp = readdir(FTSENT_DIRP(cur));\n+ if (dp == NULL) {\n+ /* Some readdir()s do not absorb ENOENT (dir\n+ deleted but open). This bug was fixed in\n+ glibc 2.3 (2002). */\n+#if ! (2 < __GLIBC__ + (3 <= __GLIBC_MINOR__))\n+ if (errno == ENOENT)\n+ errno = 0;\n #endif\n- if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {\n-\t\tif (type == BREAD) {\n-\t\t\tcur->fts_info = FTS_DNR;\n-\t\t\tcur->fts_errno = errno;\n-\t\t}\n-\t\treturn (NULL);\n-\t}\n+ if (errno) {\n+ cur->fts_errno = errno;\n+ /* If we've not read any items yet, treat\n+ the error as if we can't access the dir. */\n+ cur->fts_info = (continue_readdir || nitems)\n+ ? FTS_ERR : FTS_DNR;\n+ }\n+ closedir_and_clear(FTSENT_DIRP(cur));\n+ break;\n+ }\n+ if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))\n+ continue;\n \n-\t/*\n-\t * Nlinks is the number of possible entries of type directory in the\n-\t * directory if we're cheating on stat calls, 0 if we're not doing\n-\t * any stat calls at all, -1 if we're doing stats on everything.\n-\t */\n-\tif (type == BNAMES) {\n-\t\tnlinks = 0;\n-\t\t/* Be quiet about nostat, GCC. */\n-\t\tnostat = 0;\n-\t} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {\n-\t\tnlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);\n-\t\tnostat = 1;\n-\t} else {\n-\t\tnlinks = -1;\n-\t\tnostat = 0;\n-\t}\n+ size_t d_namelen = _D_EXACT_NAMLEN (dp);\n+ register FTSENTRY *p = fts_alloc (sp, dp->d_name, d_namelen);\n+ if (!p)\n+ goto mem1;\n+ if (d_namelen >= maxlen) {\n+ /* include space for NUL */\n+ uintptr_t oldaddr = (uintptr_t) sp->fts_path;\n+ if (! fts_palloc(sp, d_namelen + len + 1)) {\n+ /*\n+ * No more memory. Save\n+ * errno, free up the current structure and the\n+ * structures already allocated.\n+ */\n+mem1: ;\n+ int saved_errno = errno;\n+ free(FTSENT_WRAPPER(p));\n+ fts_lfree(head);\n+ closedir_and_clear(FTSENT_DIRP(cur));\n+ cur->fts_info = FTS_ERR;\n+ SET(FTS_STOP);\n+ __set_errno (saved_errno);\n+ return (NULL);\n+ }\n+ /* Did realloc() change the pointer? */\n+ if (oldaddr != (uintptr_t) sp->fts_path) {\n+ doadjust = true;\n+ if (ISSET(FTS_NOCHDIR))\n+ cp = sp->fts_path + len;\n+ }\n+ maxlen = sp->fts_pathlen - len;\n+ }\n \n-#ifdef notdef\n-\t(void)printf(\"nlinks == %d (cur: %d)\\n\", nlinks, cur->fts_nlink);\n-\t(void)printf(\"NOSTAT %d PHYSICAL %d SEEDOT %d\\n\",\n-\t ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));\n-#endif\n-\t/*\n-\t * If we're going to need to stat anything or we want to descend\n-\t * and stay in the directory, chdir. If this fails we keep going,\n-\t * but set a flag so we don't chdir after the post-order visit.\n-\t * We won't be able to stat anything, but we can still return the\n-\t * names themselves. Note, that since fts_read won't be able to\n-\t * chdir into the directory, it will have to return different path\n-\t * names than before, i.e. \"a/b\" instead of \"b\". Since the node\n-\t * has already been visited in pre-order, have to wait until the\n-\t * post-order visit to return the error. There is a special case\n-\t * here, if there was nothing to stat then it's not an error to\n-\t * not be able to stat. This is all fairly nasty. If a program\n-\t * needed sorted entries or stat information, they had better be\n-\t * checking FTS_NS on the returned nodes.\n-\t */\n-\tcderrno = 0;\n-\tif (nlinks || type == BREAD) {\n-\t\tif (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {\n-\t\t\tif (nlinks && type == BREAD)\n-\t\t\t\tcur->fts_errno = errno;\n-\t\t\tcur->fts_flags |= FTS_DONTCHDIR;\n-\t\t\tdescend = 0;\n-\t\t\tcderrno = errno;\n-\t\t\t(void)__closedir(dirp);\n-\t\t\tdirp = NULL;\n-\t\t} else\n-\t\t\tdescend = 1;\n-\t} else\n-\t\tdescend = 0;\n+ size_t new_len = len + d_namelen;\n+ if (new_len < len) {\n+ /*\n+ * In the unlikely event that we would end up\n+ * with a file name longer than SIZE_MAX, free up\n+ * the current structure and the structures already\n+ * allocated, then error out with ENAMETOOLONG.\n+ */\n+ free(FTSENT_WRAPPER(p));\n+ fts_lfree(head);\n+ closedir_and_clear(FTSENT_DIRP(cur));\n+ cur->fts_info = FTS_ERR;\n+ SET(FTS_STOP);\n+ __set_errno (ENAMETOOLONG);\n+ return (NULL);\n+ }\n+ p->fts_level = level;\n+ p->fts_parent = sp->fts_cur;\n+ p->fts_pathlen = new_len;\n \n-\t/*\n-\t * Figure out the max file name length that can be stored in the\n-\t * current path -- the inner loop allocates more path as necessary.\n-\t * We really wouldn't have to do the maxlen calculations here, we\n-\t * could do them in fts_read before returning the path, but it's a\n-\t * lot easier here since the length is part of the dirent structure.\n-\t *\n-\t * If not changing directories set a pointer so that can just append\n-\t * each new name into the path.\n-\t */\n-\tlen = NAPPEND(cur);\n-\tif (ISSET(FTS_NOCHDIR)) {\n-\t\tcp = sp->fts_path + len;\n-\t\t*cp++ = '/';\n-\t} else {\n-\t\t/* GCC, you're too verbose. */\n-\t\tcp = NULL;\n-\t}\n-\tlen++;\n-\tmaxlen = sp->fts_pathlen - len;\n+ /* Store dirent.d_ino, in case we need to sort\n+ entries before processing them. */\n+ p->fts_statp->st_ino = D_INO (dp);\n \n-\tlevel = cur->fts_level + 1;\n+ /* Build a file name for fts_stat to stat. */\n+ if (ISSET(FTS_NOCHDIR)) {\n+ p->fts_accpath = p->fts_path;\n+ memmove(cp, p->fts_name, p->fts_namelen + 1);\n+ } else\n+ p->fts_accpath = p->fts_name;\n \n-\t/* Read the directory, attaching each entry to the `link' pointer. */\n-\tdoadjust = 0;\n-\tfor (head = tail = NULL, nitems = 0; dirp && (dp = __readdir(dirp));) {\n-\t\tif (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))\n-\t\t\tcontinue;\n+ if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {\n+ /* Record what fts_read will have to do with this\n+ entry. In many cases, it will simply fts_stat it,\n+ but we can take advantage of any d_type information\n+ to optimize away the unnecessary stat calls. I.e.,\n+ if FTS_NOSTAT is in effect, we don't need device\n+ numbers unconditionally (FTS_MOUNT) and we're not\n+ following symlinks (FTS_PHYSICAL) and d_type\n+ indicates this is *not* a directory, then we won't\n+ have to stat it at all. If it *is* a directory,\n+ then (currently) we stat it regardless, in order to\n+ get device and inode numbers. Some day we might\n+ optimize that away, too, for directories where\n+ d_ino is known to be valid. */\n+ bool skip_stat = (ISSET(FTS_NOSTAT)\n+ && DT_IS_KNOWN(dp)\n+ && ! DT_MUST_BE(dp, DT_DIR)\n+ && (ISSET(FTS_PHYSICAL)\n+ || ! DT_MUST_BE(dp, DT_LNK))\n+ && ! ISSET(FTS_MOUNT));\n+ p->fts_info = FTS_NSOK;\n+ /* Propagate dirent.d_type information back\n+ to caller, when possible. */\n+ set_stat_type (p->fts_statp, D_TYPE (dp));\n+ fts_set_stat_required(p, !skip_stat);\n+ } else {\n+ p->fts_info = fts_stat(sp, p, false);\n+ }\n \n-\t\tif ((p = fts_alloc(sp, dp->d_name, _D_EXACT_NAMLEN (dp))) == NULL)\n-\t\t\tgoto mem1;\n-\t\tif (_D_EXACT_NAMLEN (dp) >= maxlen) {/* include space for NUL */\n-\t\t\toldaddr = sp->fts_path;\n-\t\t\tif (fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {\n-\t\t\t\t/*\n-\t\t\t\t * No more memory for path or structures. Save\n-\t\t\t\t * errno, free up the current structure and the\n-\t\t\t\t * structures already allocated.\n-\t\t\t\t */\n-mem1:\t\t\t\tsaved_errno = errno;\n-\t\t\t\tfree(p);\n-\t\t\t\tfts_lfree(head);\n-\t\t\t\t(void)__closedir(dirp);\n-\t\t\t\tcur->fts_info = FTS_ERR;\n-\t\t\t\tSET(FTS_STOP);\n-\t\t\t\t__set_errno (saved_errno);\n-\t\t\t\treturn (NULL);\n-\t\t\t}\n-\t\t\t/* Did realloc() change the pointer? */\n-\t\t\tif (oldaddr != sp->fts_path) {\n-\t\t\t\tdoadjust = 1;\n-\t\t\t\tif (ISSET(FTS_NOCHDIR))\n-\t\t\t\t\tcp = sp->fts_path + len;\n-\t\t\t}\n-\t\t\tmaxlen = sp->fts_pathlen - len;\n-\t\t}\n+ /* We walk in directory order so \"ls -f\" doesn't get upset. */\n+ p->fts_link = NULL;\n+ if (head == NULL)\n+ head = tail = p;\n+ else {\n+ tail->fts_link = p;\n+ tail = p;\n+ }\n \n-\t\tif (len + _D_EXACT_NAMLEN (dp) >= USHRT_MAX) {\n-\t\t\t/*\n-\t\t\t * In an FTSENT, fts_pathlen is a u_short so it is\n-\t\t\t * possible to wraparound here. If we do, free up\n-\t\t\t * the current structure and the structures already\n-\t\t\t * allocated, then error out with ENAMETOOLONG.\n-\t\t\t */\n-\t\t\tfree(p);\n-\t\t\tfts_lfree(head);\n-\t\t\t(void)__closedir(dirp);\n-\t\t\tcur->fts_info = FTS_ERR;\n-\t\t\tSET(FTS_STOP);\n-\t\t\t__set_errno (ENAMETOOLONG);\n-\t\t\treturn (NULL);\n-\t\t}\n-\t\tp->fts_level = level;\n-\t\tp->fts_parent = sp->fts_cur;\n-\t\tp->fts_pathlen = len + _D_EXACT_NAMLEN (dp);\n+ /* If there are many entries, no sorting function has been\n+ specified, and this file system is of a type that may be\n+ slow with a large number of entries, arrange to sort the\n+ directory entries on increasing inode numbers.\n \n-#if defined FTS_WHITEOUT && 0\n-\t\tif (dp->d_type == DT_WHT)\n-\t\t\tp->fts_flags |= FTS_ISW;\n-#endif\n+ The NITEMS comparison uses ==, not >, because the test\n+ needs to be tried at most once once, and NITEMS will exceed\n+ the threshold after it is incremented below. */\n+ if (nitems == _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD\n+ && !sp->fts_compar)\n+ sort_by_inode = dirent_inode_sort_may_be_useful (cur, dir_fd);\n \n-\t\t/* Unreachable code. cderrno is only ever set to a nonnull\n-\t\t value if dirp is closed at the same time. But then we\n-\t\t cannot enter this loop. */\n-\t\tif (0 && cderrno) {\n-\t\t\tif (nlinks) {\n-\t\t\t\tp->fts_info = FTS_NS;\n-\t\t\t\tp->fts_errno = cderrno;\n-\t\t\t} else\n-\t\t\t\tp->fts_info = FTS_NSOK;\n-\t\t\tp->fts_accpath = cur->fts_accpath;\n-\t\t} else if (nlinks == 0\n- || (nostat && dirent_not_directory(dp))) {\n-\t\t\tp->fts_accpath =\n-\t\t\t ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;\n-\t\t\tp->fts_info = FTS_NSOK;\n-\t\t} else {\n-\t\t\t/* Build a file name for fts_stat to stat. */\n-\t\t\tif (ISSET(FTS_NOCHDIR)) {\n-\t\t\t\tp->fts_accpath = p->fts_path;\n-\t\t\t\tmemmove(cp, p->fts_name, p->fts_namelen + 1);\n-\t\t\t} else\n-\t\t\t\tp->fts_accpath = p->fts_name;\n-\t\t\t/* Stat it. */\n-\t\t\tp->fts_info = fts_stat(sp, p, 0);\n+ ++nitems;\n+ if (max_entries <= nitems) {\n+ /* When there are too many dir entries, leave\n+ fts_dirp open, so that a subsequent fts_read\n+ can take up where we leave off. */\n+ break;\n+ }\n+ }\n \n-\t\t\t/* Decrement link count if applicable. */\n-\t\t\tif (nlinks > 0 && (p->fts_info == FTS_D ||\n-\t\t\t p->fts_info == FTS_DC || p->fts_info == FTS_DOT))\n-\t\t\t\t--nlinks;\n-\t\t}\n+ /*\n+ * If realloc() changed the address of the file name, adjust the\n+ * addresses for the rest of the tree and the dir list.\n+ */\n+ if (doadjust)\n+ fts_padjust(sp, head);\n \n-\t\t/* We walk in directory order so \"ls -f\" doesn't get upset. */\n-\t\tp->fts_link = NULL;\n-\t\tif (head == NULL)\n-\t\t\thead = tail = p;\n-\t\telse {\n-\t\t\ttail->fts_link = p;\n-\t\t\ttail = p;\n-\t\t}\n-\t\t++nitems;\n-\t}\n-\tif (dirp)\n-\t\t(void)__closedir(dirp);\n+ /*\n+ * If not changing directories, reset the file name back to original\n+ * state.\n+ */\n+ if (ISSET(FTS_NOCHDIR)) {\n+ if (len == sp->fts_pathlen || nitems == 0)\n+ --cp;\n+ *cp = '\\0';\n+ }\n \n-\t/*\n-\t * If realloc() changed the address of the path, adjust the\n-\t * addresses for the rest of the tree and the dir list.\n-\t */\n-\tif (doadjust)\n-\t\tfts_padjust(sp, head);\n+ /*\n+ * If descended after called from fts_children or after called from\n+ * fts_read and nothing found, get back. At the root level we use\n+ * the saved fd; if one of fts_open()'s arguments is a relative name\n+ * to an empty directory, we wind up here with no other way back. If\n+ * can't get back, we're done.\n+ */\n+ if (!continue_readdir && descend && (type == BCHILD || !nitems) &&\n+ (cur->fts_level == FTS_ROOTLEVEL\n+ ? restore_initial_cwd(sp)\n+ : fts_safe_changedir(sp, cur->fts_parent, -1, \"..\"))) {\n+ cur->fts_info = FTS_ERR;\n+ SET(FTS_STOP);\n+ fts_lfree(head);\n+ return (NULL);\n+ }\n \n-\t/*\n-\t * If not changing directories, reset the path back to original\n-\t * state.\n-\t */\n-\tif (ISSET(FTS_NOCHDIR)) {\n-\t\tif (len == sp->fts_pathlen || nitems == 0)\n-\t\t\t--cp;\n-\t\t*cp = '\\0';\n-\t}\n+ /* If didn't find anything, return NULL. */\n+ if (!nitems) {\n+ if (type == BREAD\n+ && cur->fts_info != FTS_DNR && cur->fts_info != FTS_ERR)\n+ cur->fts_info = FTS_DP;\n+ fts_lfree(head);\n+ return (NULL);\n+ }\n \n-\t/*\n-\t * If descended after called from fts_children or after called from\n-\t * fts_read and nothing found, get back. At the root level we use\n-\t * the saved fd; if one of fts_open()'s arguments is a relative path\n-\t * to an empty directory, we wind up here with no other way back. If\n-\t * can't get back, we're done.\n-\t */\n-\tif (descend && (type == BCHILD || !nitems) &&\n-\t (cur->fts_level == FTS_ROOTLEVEL ?\n-\t FCHDIR(sp, sp->fts_rfd) :\n-\t fts_safe_changedir(sp, cur->fts_parent, -1, \"..\"))) {\n-\t\tcur->fts_info = FTS_ERR;\n-\t\tSET(FTS_STOP);\n-\t\tfts_lfree(head);\n-\t\treturn (NULL);\n-\t}\n+ if (sort_by_inode) {\n+ sp->fts_compar = FTS_COMPAR_CAST (fts_compare_ino);\n+ head = fts_sort (sp, head, nitems);\n+ sp->fts_compar = NULL;\n+ }\n \n-\t/* If didn't find anything, return NULL. */\n-\tif (!nitems) {\n-\t\tif (type == BREAD)\n-\t\t\tcur->fts_info = FTS_DP;\n-\t\tfts_lfree(head);\n-\t\treturn (NULL);\n-\t}\n-\n-\t/* Sort the entries. */\n-\tif (sp->fts_compar && nitems > 1)\n-\t\thead = fts_sort(sp, head, nitems);\n-\treturn (head);\n+ /* Sort the entries. */\n+ if (sp->fts_compar && nitems > 1)\n+ head = fts_sort(sp, head, nitems);\n+ return (head);\n }\n \n-static u_short\n-fts_stat (FTSOBJ *sp, FTSENTRY *p, int follow)\n+#if GNULIB_FTS_DEBUG\n+\n+struct devino {\n+ intmax_t dev, ino;\n+};\n+#define PRINT_DEVINO \"(%jd,%jd)\"\n+\n+static struct devino\n+getdevino (int fd)\n {\n-\tFTSENTRY *t;\n-\tdev_t dev;\n-\tINO_T ino;\n-\tstruct STRUCT_STAT *sbp, sb;\n-\tint saved_errno;\n-\n-\t/* If user needs stat info, stat buffer already allocated. */\n-\tsbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;\n-\n-#if defined FTS_WHITEOUT && 0\n-\t/* check for whiteout */\n-\tif (p->fts_flags & FTS_ISW) {\n-\t\tif (sbp != &sb) {\n-\t\t\tmemset(sbp, '\\0', sizeof (*sbp));\n-\t\t\tsbp->st_mode = S_IFWHT;\n-\t\t}\n-\t\treturn (FTS_W);\n- }\n-#endif\n-\n-\t/*\n-\t * If doing a logical walk, or application requested FTS_FOLLOW, do\n-\t * a stat(2). If that fails, check for a non-existent symlink. If\n-\t * fail, set the errno from the stat call.\n-\t */\n-\tif (ISSET(FTS_LOGICAL) || follow) {\n-\t\tif (STAT(p->fts_accpath, sbp)) {\n-\t\t\tsaved_errno = errno;\n-\t\t\tif (!LSTAT(p->fts_accpath, sbp)) {\n-\t\t\t\t__set_errno (0);\n-\t\t\t\treturn (FTS_SLNONE);\n-\t\t\t}\n-\t\t\tp->fts_errno = saved_errno;\n-\t\t\tgoto err;\n-\t\t}\n-\t} else if (LSTAT(p->fts_accpath, sbp)) {\n-\t\tp->fts_errno = errno;\n-err:\t\tmemset(sbp, 0, sizeof(struct STRUCT_STAT));\n-\t\treturn (FTS_NS);\n-\t}\n-\n-\tif (S_ISDIR(sbp->st_mode)) {\n-\t\t/*\n-\t\t * Set the device/inode. Used to find cycles and check for\n-\t\t * crossing mount points. Also remember the link count, used\n-\t\t * in fts_build to limit the number of stat calls. It is\n-\t\t * understood that these fields are only referenced if fts_info\n-\t\t * is set to FTS_D.\n-\t\t */\n-\t\tdev = p->fts_dev = sbp->st_dev;\n-\t\tino = p->fts_ino = sbp->st_ino;\n-\t\tp->fts_nlink = sbp->st_nlink;\n-\n-\t\tif (ISDOT(p->fts_name))\n-\t\t\treturn (FTS_DOT);\n-\n-\t\t/*\n-\t\t * Cycle detection is done by brute force when the directory\n-\t\t * is first encountered. If the tree gets deep enough or the\n-\t\t * number of symbolic links to directories is high enough,\n-\t\t * something faster might be worthwhile.\n-\t\t */\n-\t\tfor (t = p->fts_parent;\n-\t\t t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)\n-\t\t\tif (ino == t->fts_ino && dev == t->fts_dev) {\n-\t\t\t\tp->fts_cycle = t;\n-\t\t\t\treturn (FTS_DC);\n-\t\t\t}\n-\t\treturn (FTS_D);\n-\t}\n-\tif (S_ISLNK(sbp->st_mode))\n-\t\treturn (FTS_SL);\n-\tif (S_ISREG(sbp->st_mode))\n-\t\treturn (FTS_F);\n-\treturn (FTS_DEFAULT);\n+ struct STRUCT_STAT st;\n+ return (fd == AT_FDCWD\n+ ? (struct devino) { -1, 0 }\n+ : FSTAT (fd, &st) == 0\n+ ? (struct devino) { st.st_dev, st.st_ino }\n+ : (struct devino) { -1, errno });\n }\n \n-static FTSENTRY *\n-fts_sort (FTSOBJ *sp, FTSENTRY *head, int nitems)\n+/* Walk ->fts_parent links starting at E_CURR, until the root of the\n+ current hierarchy. There should be a directory with dev/inode\n+ matching those of AD. If not, print a lot of diagnostics. */\n+static void\n+find_matching_ancestor (FTSENTRY const *e_curr, struct Active_dir const *ad)\n {\n-\tFTSENTRY **ap, *p;\n-\n-\t/*\n-\t * Construct an array of pointers to the structures and call qsort(3).\n-\t * Reassemble the array in the order returned by qsort. If unable to\n-\t * sort for memory reasons, return the directory entries in their\n-\t * current order. Allocate enough space for the current needs plus\n-\t * 40 so don't realloc one entry at a time.\n-\t */\n-\tif (nitems > sp->fts_nitems) {\n-\t\tFTSENTRY **a;\n-\n-\t\tsp->fts_nitems = nitems + 40;\n-\t\tif ((a = realloc(sp->fts_array,\n-\t\t (size_t)(sp->fts_nitems * sizeof(FTSENTRY *)))) == NULL) {\n-\t\t\tfree(sp->fts_array);\n-\t\t\tsp->fts_array = NULL;\n-\t\t\tsp->fts_nitems = 0;\n-\t\t\treturn (head);\n-\t\t}\n-\t\tsp->fts_array = a;\n-\t}\n-\tfor (ap = sp->fts_array, p = head; p; p = p->fts_link)\n-\t\t*ap++ = p;\n-\tqsort((void *)sp->fts_array, nitems, sizeof(FTSENTRY *), sp->fts_compar);\n-\tfor (head = *(ap = sp->fts_array); --nitems; ++ap)\n-\t\tap[0]->fts_link = ap[1];\n-\tap[0]->fts_link = NULL;\n-\treturn (head);\n+ for (FTSENTRY const *ent = e_curr;\n+ ent->fts_level >= FTS_ROOTLEVEL;\n+ ent = ent->fts_parent)\n+ {\n+ if (ad->ino == ent->fts_statp->st_ino\n+ && ad->dev == ent->fts_statp->st_dev)\n+ return;\n+ }\n+ printf (\"ERROR: tree dir, %s, not active\\n\", ad->fts_ent->fts_accpath);\n+ printf (\"active dirs:\\n\");\n+ for (FTSENTRY const *ent = e_curr;\n+ ent->fts_level >= FTS_ROOTLEVEL;\n+ ent = ent->fts_parent)\n+ printf (\" %s(%\"PRIuMAX\"/%\"PRIuMAX\") to %s(%\"PRIuMAX\"/%\"PRIuMAX\")...\\n\",\n+ ad->fts_ent->fts_accpath,\n+ (uintmax_t) ad->dev,\n+ (uintmax_t) ad->ino,\n+ ent->fts_accpath,\n+ (uintmax_t) ent->fts_statp->st_dev,\n+ (uintmax_t) ent->fts_statp->st_ino);\n }\n \n-static FTSENTRY *\n-fts_alloc (FTSOBJ *sp, const char *name, size_t namelen)\n+void\n+fts_cross_check (FTSOBJ const *sp)\n {\n-\tFTSENTRY *p;\n-\tsize_t len;\n+ if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))\n+ return;\n \n-\t/*\n-\t * The file name is a variable length array and no stat structure is\n-\t * necessary if the user has set the nostat bit. Allocate the FTSENT\n-\t * structure, the file name and the stat structure in one chunk, but\n-\t * be careful that the stat structure is reasonably aligned. Since the\n-\t * fts_name field is declared to be of size 1, the fts_name pointer is\n-\t * namelen + 2 before the first possible address of the stat structure.\n-\t */\n-\tlen = sizeof(FTSENTRY) + namelen;\n-\tif (!ISSET(FTS_NOSTAT))\n-\t\tlen += sizeof(struct STRUCT_STAT) + ALIGNBYTES;\n-\tif ((p = malloc(len)) == NULL)\n-\t\treturn (NULL);\n+ FTSENTRY const *ent = sp->fts_cur;\n \n-\t/* Copy the name and guarantee NUL termination. */\n-\tmemmove(p->fts_name, name, namelen);\n-\tp->fts_name[namelen] = '\\0';\n+ Dprintf ((\"fts-cross-check cur=%s\\n\", ent->fts_path));\n+ /* Make sure every parent dir is in the tree. */\n+ for (FTSENTRY const *t = ent->fts_parent;\n+ t->fts_level >= FTS_ROOTLEVEL;\n+ t = t->fts_parent)\n+ {\n+ struct Active_dir ad;\n+ ad.ino = t->fts_statp->st_ino;\n+ ad.dev = t->fts_statp->st_dev;\n+ if ( ! hash_lookup (sp->fts_cycle.ht, &ad))\n+ printf (\"ERROR: active dir, %s, not in tree\\n\", t->fts_path);\n+ }\n \n-\tif (!ISSET(FTS_NOSTAT))\n-\t\tp->fts_statp = (struct STRUCT_STAT *)ALIGN(p->fts_name + namelen + 2);\n-\tp->fts_namelen = namelen;\n-\tp->fts_path = sp->fts_path;\n-\tp->fts_errno = 0;\n-\tp->fts_flags = 0;\n-\tp->fts_instr = FTS_NOINSTR;\n-\tp->fts_number = 0;\n-\tp->fts_pointer = NULL;\n-\treturn (p);\n+ /* Make sure every dir in the tree is an active dir.\n+ But ENT is not necessarily a directory. If so, just skip this part. */\n+ if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL\n+ && (ent->fts_info == FTS_DP\n+ || ent->fts_info == FTS_D))\n+ for (struct Active_dir *ad = hash_get_first (sp->fts_cycle.ht);\n+ ad != NULL;\n+ ad = hash_get_next (sp->fts_cycle.ht, ad))\n+ {\n+ find_matching_ancestor (ent, ad);\n+ }\n+}\n+\n+static bool\n+same_fd (int fd1, int fd2)\n+{\n+ struct STRUCT_STAT sb1, sb2;\n+ return (FSTAT (fd1, &sb1) == 0\n+ && FSTAT (fd2, &sb2) == 0\n+ && psame_inode (&sb1, &sb2));\n }\n \n static void\n-fts_lfree (FTSENTRY *head)\n+fd_ring_print (FTSOBJ const *sp, FILE *stream, char const *msg)\n {\n-\tFTSENTRY *p;\n+ if (!fts_debug)\n+ return;\n+ I_ring const *fd_ring = &sp->fts_fd_ring;\n+ struct devino cwd = getdevino (sp->fts_cwd_fd);\n+ fprintf (stream, \"=== %s ========== \"PRINT_DEVINO\"\\n\", msg, cwd.dev, cwd.ino);\n+ if (i_ring_empty (fd_ring))\n+ return;\n \n-\t/* Free a linked list of structures. */\n-\twhile ((p = head)) {\n-\t\thead = head->fts_link;\n-\t\tfree(p);\n-\t}\n+ unsigned int i = fd_ring->ir_front;\n+ while (true)\n+ {\n+ int fd = fd_ring->ir_data[i];\n+ if (fd < 0)\n+ fprintf (stream, \"%u: %d:\\n\", i, fd);\n+ else\n+ {\n+ struct devino wd = getdevino (fd);\n+ fprintf (stream, \"%u: %d: \"PRINT_DEVINO\"\\n\", i, fd, wd.dev, wd.ino);\n+ }\n+ if (i == fd_ring->ir_back)\n+ break;\n+ i = (i + I_RING_SIZE - 1) % I_RING_SIZE;\n+ }\n+}\n+\n+/* Ensure that each file descriptor on the fd_ring matches a\n+ parent, grandparent, etc. of the current working directory. */\n+static void\n+fd_ring_check (FTSOBJ const *sp)\n+{\n+ if (!fts_debug)\n+ return;\n+\n+ /* Make a writable copy. */\n+ I_ring fd_w = sp->fts_fd_ring;\n+\n+ int cwd_fd = sp->fts_cwd_fd;\n+ cwd_fd = fcntl (cwd_fd, F_DUPFD_CLOEXEC, STDERR_FILENO + 1);\n+ struct devino dot = getdevino (cwd_fd);\n+ fprintf (stderr, \"===== check ===== cwd: \"PRINT_DEVINO\"\\n\",\n+ dot.dev, dot.ino);\n+ while ( ! i_ring_empty (&fd_w))\n+ {\n+ int fd = i_ring_pop (&fd_w);\n+ if (0 <= fd)\n+ {\n+ int open_flags = O_SEARCH | O_CLOEXEC;\n+ int parent_fd = openat (cwd_fd, \"..\", open_flags);\n+ if (parent_fd < 0)\n+ {\n+ // Warn?\n+ break;\n+ }\n+ if (!same_fd (fd, parent_fd))\n+ {\n+ struct devino cwd = getdevino (fd);\n+ fprintf (stderr, \"ring : \"PRINT_DEVINO\"\\n\", cwd.dev, cwd.ino);\n+ struct devino c2 = getdevino (parent_fd);\n+ fprintf (stderr, \"parent: \"PRINT_DEVINO\"\\n\", c2.dev, c2.ino);\n+ fts_assert (0);\n+ }\n+ close (cwd_fd);\n+ cwd_fd = parent_fd;\n+ }\n+ }\n+ close (cwd_fd);\n+}\n+#endif\n+\n+static unsigned short int\n+internal_function\n+fts_stat(FTSOBJ *sp, register FTSENTRY *p, bool follow)\n+{\n+ if (ISSET (FTS_LOGICAL)\n+ || (ISSET (FTS_COMFOLLOW) && p->fts_level == FTS_ROOTLEVEL))\n+ follow = true;\n+\n+ struct STRUCT_STAT *sbp = p->fts_statp;\n+\n+ /*\n+ * If doing a logical walk, or application requested FTS_FOLLOW, do\n+ * a stat(2). If that fails, check for a nonexistent symlink. If\n+ * fail, set the errno from the stat call.\n+ */\n+ int flags = follow ? 0 : AT_SYMLINK_NOFOLLOW;\n+ if (FSTATAT (sp->fts_cwd_fd, p->fts_accpath, sbp, flags) < 0)\n+ {\n+ if (follow && errno == ENOENT\n+ && 0 <= FSTATAT (sp->fts_cwd_fd, p->fts_accpath, sbp,\n+ AT_SYMLINK_NOFOLLOW))\n+ {\n+ __set_errno (0);\n+ return FTS_SLNONE;\n+ }\n+\n+ p->fts_errno = errno;\n+ memset (sbp, 0, sizeof *sbp);\n+ return FTS_NS;\n+ }\n+\n+ if (S_ISDIR(sbp->st_mode)) {\n+ if (ISDOT(p->fts_name)) {\n+ /* Command-line \".\" and \"..\" are real directories. */\n+ return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);\n+ }\n+\n+ return (FTS_D);\n+ }\n+ if (S_ISLNK(sbp->st_mode))\n+ return (FTS_SL);\n+ if (S_ISREG(sbp->st_mode))\n+ return (FTS_F);\n+ return (FTS_DEFAULT);\n+}\n+\n+static int\n+fts_compar (void const *a, void const *b)\n+{\n+ /* Convert A and B to the correct types, to pacify the compiler, and\n+ for portability to bizarre hosts where \"void const *\" and \"FTSENT\n+ const **\" differ in runtime representation. The comparison\n+ function cannot modify *a and *b, but there is no compile-time\n+ check for this. */\n+ FTSENTRY const **pa = (FTSENTRY const **) a;\n+ FTSENTRY const **pb = (FTSENTRY const **) b;\n+ return FTSENT_FTS(pa[0])->fts_compar (pa, pb);\n+}\n+\n+static FTSENTRY *\n+internal_function\n+fts_sort (FTSOBJ *sp, FTSENTRY *head, register size_t nitems)\n+{\n+ register FTSENTRY **ap, *p;\n+\n+ /* On most modern hosts, void * and FTSENT ** have the same\n+ run-time representation, and one can convert sp->fts_compar to\n+ the type qsort expects without problem. Use the heuristic that\n+ this is OK if the two pointer types are the same size, and if\n+ converting FTSENT ** to uintptr_t is the same as converting\n+ FTSENT ** to void * and then to uintptr_t. This heuristic isn't\n+ valid in general but we don't know of any counterexamples. */\n+ FTSENTRY *dummy;\n+ int (*compare) (void const *, void const *) =\n+ ((sizeof &dummy == sizeof (void *)\n+ && (uintptr_t) &dummy == (uintptr_t) (void *) &dummy)\n+ ? (int (*) (void const *, void const *)) sp->fts_compar\n+ : fts_compar);\n+\n+ /*\n+ * Construct an array of pointers to the structures and call qsort(3).\n+ * Reassemble the array in the order returned by qsort. If unable to\n+ * sort for memory reasons, return the directory entries in their\n+ * current order. Allocate enough space for the current needs plus\n+ * 40 so don't realloc one entry at a time.\n+ */\n+ if (nitems > sp->fts_nitems) {\n+ sp->fts_nitems = nitems + 40;\n+ FTSENTRY **a;\n+ if (! (a = reallocarray (sp->fts_array,\n+ sp->fts_nitems, sizeof *a))) {\n+ free(sp->fts_array);\n+ sp->fts_array = NULL;\n+ sp->fts_nitems = 0;\n+ return (head);\n+ }\n+ sp->fts_array = a;\n+ }\n+ for (ap = sp->fts_array, p = head; p; p = p->fts_link)\n+ *ap++ = p;\n+ qsort((void *)sp->fts_array, nitems, sizeof(FTSENTRY *), compare);\n+ for (head = *(ap = sp->fts_array); --nitems; ++ap)\n+ ap[0]->fts_link = ap[1];\n+ ap[0]->fts_link = NULL;\n+ return (head);\n+}\n+\n+static FTSENTRY *\n+internal_function\n+fts_alloc (FTSOBJ *sp, const char *name, register size_t namelen)\n+{\n+ /*\n+ * The file name is a variable length array. Allocate the FTSENT\n+ * structure and the file name in one chunk.\n+ */\n+ size_t len = FLEXSIZEOF(FTSENT, fts_name, namelen + 1);\n+\tregister FTSENTRY *p;\n+#if !_LIBC\n+ p = malloc(len);\n+ if (p == NULL)\n+ return (NULL);\n+#else\n+\t/*\n+\t * For glibc, we use a wrapper struct to provide the extra required\n+\t * fields without changing the FSENT layout.\n+\t */\n+\tlen += sizeof (struct FTSENT_wrapper);\n+\tstruct FTSENT_wrapper *wrapper = malloc(len);\n+\tif (wrapper == NULL)\n+\t\treturn (NULL);\n+\tp = &wrapper->ent;\n+ p->fts_statp = &wrapper->fts_stat;\n+#endif\n+\n+ /* Copy the name and guarantee NUL termination. */\n+ memcpy(p->fts_name, name, namelen);\n+ p->fts_name[namelen] = '\\0';\n+\n+ p->fts_namelen = namelen;\n+ FTSENT_FTS(p)= sp;\n+ p->fts_path = sp->fts_path;\n+ p->fts_errno = 0;\n+ FTSENT_DIRP(p) = NULL;\n+ p->fts_flags = 0;\n+ p->fts_instr = FTS_NOINSTR;\n+ p->fts_number = 0;\n+ p->fts_pointer = NULL;\n+ return (p);\n+}\n+\n+static void\n+internal_function\n+fts_lfree (register FTSENTRY *head)\n+{\n+ int saved_errno = errno;\n+\n+ /* Free a linked list of structures. */\n+ register FTSENTRY *p;\n+ while ((p = head)) {\n+ head = head->fts_link;\n+ if (FTSENT_DIRP(p))\n+ closedir (FTSENT_DIRP(p));\n+ free(FTSENT_WRAPPER(p));\n+ }\n+\n+ __set_errno (saved_errno);\n }\n \n /*\n- * Allow essentially unlimited paths; find, rm, ls should all work on any tree.\n- * Most systems will allow creation of paths much longer than MAXPATHLEN, even\n- * though the kernel won't resolve them. Add the size (not just what's needed)\n- * plus 256 bytes so don't realloc the path 2 bytes at a time.\n+ * Allow essentially unlimited file name lengths; find, rm, ls should\n+ * all work on any tree. Most systems will allow creation of file\n+ * names much longer than MAXPATHLEN, even though the kernel won't\n+ * resolve them. Add the size (not just what's needed) plus 256 bytes\n+ * so don't realloc the file name 2 bytes at a time.\n */\n-static int\n+static bool\n+internal_function\n fts_palloc (FTSOBJ *sp, size_t more)\n {\n-\tchar *p;\n+ size_t new_len = sp->fts_pathlen + more + 256;\n \n-\tsp->fts_pathlen += more + 256;\n-\t/*\n-\t * Check for possible wraparound. In an FTS, fts_pathlen is\n-\t * a signed int but in an FTSENT it is an unsigned short.\n-\t * We limit fts_pathlen to USHRT_MAX to be safe in both cases.\n-\t */\n-\tif (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {\n-\t\tfree(sp->fts_path);\n-\t\tsp->fts_path = NULL;\n-\t\t__set_errno (ENAMETOOLONG);\n-\t\treturn (1);\n-\t}\n-\tp = realloc(sp->fts_path, sp->fts_pathlen);\n-\tif (p == NULL) {\n-\t\tfree(sp->fts_path);\n-\t\tsp->fts_path = NULL;\n-\t\treturn 1;\n-\t}\n-\tsp->fts_path = p;\n-\treturn 0;\n+ /*\n+ * See if fts_pathlen would overflow.\n+ */\n+ if (new_len < sp->fts_pathlen) {\n+ free(sp->fts_path);\n+ sp->fts_path = NULL;\n+ __set_errno (ENAMETOOLONG);\n+ return false;\n+ }\n+ sp->fts_pathlen = new_len;\n+ char *p = realloc(sp->fts_path, sp->fts_pathlen);\n+ if (p == NULL) {\n+ free(sp->fts_path);\n+ sp->fts_path = NULL;\n+ return false;\n+ }\n+ sp->fts_path = p;\n+ return true;\n }\n \n /*\n- * When the path is realloc'd, have to fix all of the pointers in structures\n- * already returned.\n+ * When the file name is realloc'd, have to fix all of the pointers in\n+ * structures already returned.\n */\n static void\n+internal_function\n fts_padjust (FTSOBJ *sp, FTSENTRY *head)\n {\n-\tFTSENTRY *p;\n-\tchar *addr = sp->fts_path;\n+ char *addr = sp->fts_path;\n \n-#define\tADJUST(p) do {\t\t\t\t\t\t\t\\\n-\tif ((p)->fts_accpath != (p)->fts_name) {\t\t\t\\\n-\t\t(p)->fts_accpath =\t\t\t\t\t\\\n-\t\t (char *)addr + ((p)->fts_accpath - (p)->fts_path);\t\\\n-\t}\t\t\t\t\t\t\t\t\\\n-\t(p)->fts_path = addr;\t\t\t\t\t\t\\\n+ /* This code looks at bit-patterns of freed pointers to\n+ relocate them, so it relies on undefined behavior. If this\n+ trick does not work on your platform, please report a bug. */\n+\n+#define ADJUST(p) do { \\\n+ uintptr_t old_accpath = (uintptr_t) (p)->fts_accpath; \\\n+ if (old_accpath != (uintptr_t) (p)->fts_name) { \\\n+ (p)->fts_accpath = \\\n+ addr + (old_accpath - (uintptr_t) (p)->fts_path); \\\n+ } \\\n+ (p)->fts_path = addr; \\\n } while (0)\n-\t/* Adjust the current set of children. */\n-\tfor (p = sp->fts_child; p; p = p->fts_link)\n-\t\tADJUST(p);\n+ /* Adjust the current set of children. */\n+ for (FTSENTRY *p = sp->fts_child; p; p = p->fts_link)\n+ ADJUST(p);\n \n-\t/* Adjust the rest of the tree, including the current level. */\n-\tfor (p = head; p->fts_level >= FTS_ROOTLEVEL;) {\n-\t\tADJUST(p);\n-\t\tp = p->fts_link ? p->fts_link : p->fts_parent;\n-\t}\n+ /* Adjust the rest of the tree, including the current level. */\n+ for (FTSENTRY *p = head; p->fts_level >= FTS_ROOTLEVEL;) {\n+ ADJUST(p);\n+ p = p->fts_link ? p->fts_link : p->fts_parent;\n+ }\n }\n \n static size_t\n+internal_function _GL_ATTRIBUTE_PURE\n fts_maxarglen (char * const *argv)\n {\n-\tsize_t len, max;\n+ size_t max;\n \n-\tfor (max = 0; *argv; ++argv)\n-\t\tif ((len = strlen(*argv)) > max)\n-\t\t\tmax = len;\n-\treturn (max + 1);\n+ for (max = 0; *argv; ++argv) {\n+ size_t len = strlen(*argv);\n+ if (len > max)\n+ max = len;\n+ }\n+ return (max + 1);\n }\n \n /*\n- * Change to dir specified by fd or p->fts_accpath without getting\n+ * Change to dir specified by fd or file name without getting\n * tricked by someone changing the world out from underneath us.\n- * Assumes p->fts_dev and p->fts_ino are filled in.\n+ * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.\n+ * If FD is non-negative, expect it to be used after this function returns,\n+ * and to be closed eventually. So don't pass e.g., 'dirfd(dirp)' and then\n+ * do closedir(dirp), because that would invalidate the saved FD.\n+ * Upon failure, close FD immediately and return nonzero.\n */\n static int\n-fts_safe_changedir (FTSOBJ *sp, FTSENTRY *p, int fd, const char *path)\n+internal_function\n+fts_safe_changedir (FTSOBJ *sp, FTSENTRY *p, int fd, char const *dir)\n {\n-\tint ret, oerrno, newfd;\n-\tstruct STRUCT_STAT sb;\n+ fts_assert (0 <= fd || dir != NULL);\n+ bool is_dotdot = dir && streq (dir, \"..\");\n \n-\tnewfd = fd;\n-\tif (ISSET(FTS_NOCHDIR))\n-\t\treturn (0);\n-\tif (fd < 0 && (newfd = __open(path, O_RDONLY, 0)) < 0)\n-\t\treturn (-1);\n-\tif (FSTAT (newfd, &sb)) {\n-\t\tret = -1;\n-\t\tgoto bail;\n-\t}\n-\tif (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {\n-\t\t__set_errno (ENOENT);\t\t/* disinformation */\n-\t\tret = -1;\n-\t\tgoto bail;\n-\t}\n-\tret = __fchdir(newfd);\n+ /* This clause handles the unusual case in which FTS_NOCHDIR\n+ is specified, along with FTS_CWDFD. In that case, there is\n+ no need to change even the virtual cwd file descriptor.\n+ However, if FD is non-negative, we do close it here. */\n+ if (ISSET (FTS_NOCHDIR))\n+ {\n+ if (ISSET (FTS_CWDFD) && 0 <= fd)\n+ close (fd);\n+ return 0;\n+ }\n+\n+ if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))\n+ {\n+ /* When possible, skip the diropen and subsequent fstat+dev/ino\n+ comparison. I.e., when changing to parent directory\n+ (chdir (\"..\")), use a file descriptor from the ring and\n+ save the overhead of diropen+fstat, as well as avoiding\n+ failure when we lack \"x\" access to the virtual cwd. */\n+ if ( ! i_ring_empty (&sp->fts_fd_ring))\n+ {\n+ int parent_fd;\n+ fd_ring_print (sp, stderr, \"pre-pop\");\n+ parent_fd = i_ring_pop (&sp->fts_fd_ring);\n+ if (0 <= parent_fd)\n+ {\n+ fd = parent_fd;\n+ dir = NULL;\n+ }\n+ }\n+ }\n+\n+ int newfd = fd;\n+ if (fd < 0 && (newfd = diropen (sp, dir)) < 0)\n+ return -1;\n+\n+ /* The following dev/inode check is necessary if we're doing a\n+ \"logical\" traversal (through symlinks, a la chown -L), if the\n+ system lacks O_NOFOLLOW support, or if we're changing to \"..\"\n+ (but not via a popped file descriptor). When changing to the\n+ name \"..\", O_NOFOLLOW can't help. In general, when the target is\n+ not \"..\", diropen's use of O_NOFOLLOW ensures we don't mistakenly\n+ follow a symlink, so we can avoid the expense of this fstat. */\n+ int ret;\n+ if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW\n+ || (dir && streq (dir, \"..\")))\n+ {\n+ struct STRUCT_STAT sb;\n+ if (FSTAT (newfd, &sb))\n+ {\n+ ret = -1;\n+ goto bail;\n+ }\n+ if (p->fts_statp->st_dev != sb.st_dev\n+ || p->fts_statp->st_ino != sb.st_ino)\n+ {\n+ __set_errno (ENOENT); /* disinformation */\n+ ret = -1;\n+ goto bail;\n+ }\n+ }\n+\n+ if (ISSET(FTS_CWDFD))\n+ {\n+ cwd_advance_fd (sp, newfd, ! is_dotdot);\n+ return 0;\n+ }\n+\n+ ret = fchdir(newfd);\n bail:\n-\toerrno = errno;\n-\tif (fd < 0)\n-\t\t(void)__close(newfd);\n-\t__set_errno (oerrno);\n-\treturn (ret);\n+ if (fd < 0)\n+ {\n+ int oerrno = errno;\n+ (void)close(newfd);\n+ __set_errno (oerrno);\n+ }\n+ return ret;\n }\ndiff --git a/io/fts.h b/io/fts.h\nindex b496e75cee..cc30d282d3 100644\n--- a/io/fts.h\n+++ b/io/fts.h\n@@ -52,7 +52,29 @@\n \n #include <features.h>\n #include <sys/types.h>\n+#include <sys/stat.h>\n+#include <dirent.h>\n+#include <stdbool.h>\n \n+enum { I_RING_SIZE = 4 };\n+\n+/* When ir_empty is true, the ring is empty.\n+ Otherwise, ir_data[B..F] are defined, where B..F is the contiguous\n+ range of indices, modulo I_RING_SIZE, from back to front, inclusive.\n+ Undefined elements of ir_data are always set to ir_default_val.\n+ Popping from an empty ring aborts.\n+ Pushing onto a full ring returns the displaced value.\n+ An empty ring has F==B and ir_empty == true.\n+ A ring with one entry still has F==B, but now ir_empty == false. */\n+struct I_ring\n+{\n+ int ir_data[I_RING_SIZE];\n+ int ir_default_val;\n+ unsigned int ir_front;\n+ unsigned int ir_back;\n+ bool ir_empty;\n+};\n+typedef struct I_ring I_ring;\n \n typedef struct {\n \tstruct _ftsent *fts_cur;\t/* current node */\n@@ -73,11 +95,106 @@ typedef struct {\n #define\tFTS_SEEDOT\t0x0020\t\t/* return dot and dot-dot */\n #define\tFTS_XDEV\t0x0040\t\t/* don't cross devices */\n #define FTS_WHITEOUT\t0x0080\t\t/* return whiteout information */\n-#define\tFTS_OPTIONMASK\t0x00ff\t\t/* valid user option mask */\n+\n+ /* There are two ways to detect cycles.\n+ The lazy way (which works only with FTS_PHYSICAL),\n+ with which one may process a directory that is a\n+ part of the cycle several times before detecting the cycle.\n+ The \"tight\" way, whereby fts uses more memory (proportional\n+ to number of \"active\" directories, aka distance from root\n+ of current tree to current directory -- see active_dir_ht)\n+ to detect any cycle right away. For example, du must use\n+ this option to avoid counting disk space in a cycle multiple\n+ times, but chown -R need not.\n+ The default is to use the constant-memory lazy way, when possible\n+ (see below).\n+\n+ However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)\n+ using lazy cycle detection is inadequate. For example, traversing\n+ a directory containing a symbolic link to a peer directory, it is\n+ possible to encounter the same directory twice even though there\n+ is no cycle:\n+ dir\n+ ...\n+ slink -> dir\n+ So, when FTS_LOGICAL is selected, we have to use a different\n+ mode of cycle detection: FTS_TIGHT_CYCLE_CHECK. */\n+#define FTS_TIGHT_CYCLE_CHECK\t0x0400\n+\n+ /* Use this flag to enable semantics with which the parent\n+ application may be made both more efficient and more robust.\n+ Whereas the default is to visit each directory in a recursive\n+ traversal (via chdir), using this flag makes it so the initial\n+ working directory is never changed. Instead, these functions\n+ perform the traversal via a virtual working directory, maintained\n+ through the file descriptor member, fts_cwd_fd. */\n+# define FTS_CWDFD 0x0800\n+\n+ /* Historically, for each directory that fts initially encounters, it would\n+ open it, read all entries, and stat each entry, storing the results, and\n+ then it would process the first entry. But that behavior is bad for\n+ locality of reference, and also causes trouble with inode-simulating\n+ file systems like FAT, CIFS, FUSE-based ones, etc., when entries from\n+ their name/inode cache are flushed too early.\n+ Use this flag to make fts_open and fts_read defer the stat/lstat/fststat\n+ of each entry until it is actually processed. However, note that if you\n+ use this option and also specify a comparison function, that function may\n+ not examine any data via fts_statp. However, when fts_statp->st_mode is\n+ nonzero, the S_IFMT type bits are valid, with mapped dirent.d_type data.\n+ Of course, that happens only on file systems that provide useful\n+ dirent.d_type data. */\n+#define FTS_DEFER_STAT\t0x1000\n+\n+ /* Use this flag to disable stripping of trailing slashes\n+ from input path names during fts_open initialization. */\n+#define FTS_VERBATIM\t0x2000\n+\n+#define FTS_MOUNT 0x4000 /* skip other devices */\n+#define FTS_OPTIONMASK 0x7fff /* valid user option mask */\n \n #define\tFTS_NAMEONLY\t0x0100\t\t/* (private) child names only */\n #define\tFTS_STOP\t0x0200\t\t/* (private) unrecoverable error */\n+\n \tint fts_options;\t\t/* fts_open options, global flags */\n+\n+\tint fts_cwd_fd; /* the file descriptor on which the\n+\t virtual cwd is open, or AT_FDCWD */\n+\n+\t/* Map a directory's device number to a boolean. The boolean is\n+\t true if for that file system (type determined by a single fstatfs\n+\t call per FS) st_nlink can be used to calculate the number of\n+\t sub-directory entries in a directory.\n+\t Using this table is an optimization that permits us to look up\n+\t file system type on a per-inode basis at the minimal cost of\n+\t calling fstatfs only once per traversed device. */\n+\tstruct hash_table *fts_leaf_optimization_works_ht;\n+\n+\tunion {\n+\t /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is\n+\t specified. It records the directories between a starting\n+\t point and the current directory. I.e., a directory is\n+\t recorded here IFF we have visited it once, but we have not\n+\t yet completed processing of all its entries. Every time we\n+\t visit a new directory, we add that directory to this set.\n+\t When we finish with a directory (usually by visiting it a\n+\t second time), we remove it from this set. Each entry in\n+\t this data structure is a device/inode pair. This data\n+\t structure is used to detect directory cycles efficiently and\n+\t promptly even when the depth of a hierarchy is in the tens\n+\t of thousands. */\n+\t struct hash_table *ht;\n+\n+\t /* FIXME: rename these two members to have the fts_ prefix */\n+\t /* This data structure uses a lazy cycle-detection algorithm,\n+\t as done by rm via cycle-check.c. It's the default,\n+\t but it's not appropriate for programs like du. */\n+\t struct cycle_check_state *state;\n+\t} fts_cycle;\n+\n+\t/* A stack of the file descriptors corresponding to the\n+\t most-recently traversed parent directories.\n+\t Currently used only in FTS_CWDFD mode. */\n+\tI_ring fts_fd_ring;\n } FTS;\n \n #ifdef __USE_LARGEFILE64\n@@ -92,6 +209,13 @@ typedef struct {\n \tint fts_nitems;\t\t\t/* elements in the sort array */\n \tint (*fts_compar) (const void *, const void *); /* compare fn */\n \tint fts_options;\t\t/* fts_open options, global flags */\n+\tint fts_cwd_fd;\n+\tstruct hash_table *fts_leaf_optimization_works_ht;\n+\tunion {\n+\t struct hash_table *ht;\n+\t struct cycle_check_state *state;\n+\t} fts_cycle;\n+\tI_ring fts_fd_ring;\n } FTS64;\n #endif\n \ndiff --git a/io/fts64-time64.c b/io/fts64-time64.c\nindex f9bad60572..6a1053194e 100644\n--- a/io/fts64-time64.c\n+++ b/io/fts64-time64.c\n@@ -19,18 +19,19 @@\n #include <time.h>\n \n #if __TIMESIZE != 64\n-# define FTS_OPEN __fts64_open_time64\n-# define FTS_CLOSE __fts64_close_time64\n-# define FTS_READ __fts64_read_time64\n-# define FTS_SET __fts64_set_time64\n-# define FTS_CHILDREN __fts64_children_time64\n-# define FTSOBJ FTS64_TIME64\n-# define FTSENTRY FSTENT64_TIME64\n-# define INO_T ino64_t\n-# define STRUCT_STAT __stat64_t64\n-# define STAT __stat64_time64\n-# define LSTAT __lstat64_time64\n-# define FSTAT __fstat64_time64\n+# define FTS_OPEN __fts64_open_time64\n+# define FTS_CLOSE __fts64_close_time64\n+# define FTS_READ __fts64_read_time64\n+# define FTS_SET __fts64_set_time64\n+# define FTS_CHILDREN __fts64_children_time64\n+# define FTSOBJ FTS64_TIME64\n+# define FTSENTRY FSTENT64_TIME64\n+# define INO_T ino64_t\n+# define STRUCT_STAT __stat64_t64\n+# define FSTAT __fstat64_time64\n+# define FSTATAT __fstatat64_time64\n+# define STRUCT_STATFS statfs64\n+# define FSTATFS __fstatfs64\n \n # include \"fts.c\"\n #endif\ndiff --git a/io/fts64.c b/io/fts64.c\nindex 152910018e..a6f607a873 100644\n--- a/io/fts64.c\n+++ b/io/fts64.c\n@@ -25,8 +25,9 @@\n #define FTSENTRY FTSENT64\n #define INO_T ino64_t\n #define STRUCT_STAT stat64\n-#define STAT __stat64\n-#define LSTAT __lstat64\n #define FSTAT __fstat64\n+#define FSTATAT __fstatat64\n+#define STRUCT_STATFS statfs64\n+#define FSTATFS __fstatfs64\n \n #include \"fts.c\"\ndiff --git a/io/i-ring.c b/io/i-ring.c\nnew file mode 100644\nindex 0000000000..28047b7dc4\n--- /dev/null\n+++ b/io/i-ring.c\n@@ -0,0 +1,69 @@\n+/* a simple ring buffer\n+ Copyright (C) 2006, 2009-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* written by Jim Meyering */\n+\n+#include <config.h>\n+#if !_LIBC\n+# include \"i-ring.h\"\n+# define INTERNAL_DEF\n+#endif\n+\n+#include <stdlib.h>\n+\n+INTERNAL_DEF void\n+i_ring_init (I_ring *ir, int default_val)\n+{\n+ ir->ir_empty = true;\n+ ir->ir_front = 0;\n+ ir->ir_back = 0;\n+ for (int i = 0; i < I_RING_SIZE; i++)\n+ ir->ir_data[i] = default_val;\n+ ir->ir_default_val = default_val;\n+}\n+\n+INTERNAL_DEF bool\n+i_ring_empty (I_ring const *ir)\n+{\n+ return ir->ir_empty;\n+}\n+\n+INTERNAL_DEF int\n+i_ring_push (I_ring *ir, int val)\n+{\n+ unsigned int dest_idx = (ir->ir_front + !ir->ir_empty) % I_RING_SIZE;\n+ int old_val = ir->ir_data[dest_idx];\n+ ir->ir_data[dest_idx] = val;\n+ ir->ir_front = dest_idx;\n+ if (dest_idx == ir->ir_back)\n+ ir->ir_back = (ir->ir_back + !ir->ir_empty) % I_RING_SIZE;\n+ ir->ir_empty = false;\n+ return old_val;\n+}\n+\n+INTERNAL_DEF int\n+i_ring_pop (I_ring *ir)\n+{\n+ if (i_ring_empty (ir))\n+ abort ();\n+ int top_val = ir->ir_data[ir->ir_front];\n+ ir->ir_data[ir->ir_front] = ir->ir_default_val;\n+ if (ir->ir_front == ir->ir_back)\n+ ir->ir_empty = true;\n+ else\n+ ir->ir_front = ((ir->ir_front + I_RING_SIZE - 1) % I_RING_SIZE);\n+ return top_val;\n+}\ndiff --git a/io/same-inode.h b/io/same-inode.h\nnew file mode 100644\nindex 0000000000..44b6f3ed84\n--- /dev/null\n+++ b/io/same-inode.h\n@@ -0,0 +1,106 @@\n+/* Determine whether two stat buffers are known to refer to the same file.\n+\n+ Copyright (C) 2006, 2009-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+#ifndef SAME_INODE_H\n+#define SAME_INODE_H 1\n+\n+/* This file uses _GL_INLINE_HEADER_BEGIN, _GL_INLINE. */\n+#if !_LIBC && !_GL_CONFIG_H_INCLUDED\n+ #error \"Please include config.h first.\"\n+#endif\n+\n+#include <sys/stat.h>\n+#if _LIBC\n+# define _GL_INLINE_HEADER_BEGIN\n+# define _GL_INLINE_HEADER_END\n+# define SAME_INODE_INLINE static inline\n+# define S_TYPEISTMO(p) 0\n+#endif\n+\n+_GL_INLINE_HEADER_BEGIN\n+#ifndef SAME_INODE_INLINE\n+# define SAME_INODE_INLINE _GL_INLINE\n+#endif\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\n+\n+/* True if A and B point to structs with st_dev and st_ino members\n+ that are known to represent the same file.\n+\n+ Use | and ^ to shorten generated code, and to lessen the\n+ probability of screwups if st_ino is an array. */\n+\n+#if defined __VMS && __CRTL_VER < 80200000\n+# define PSAME_INODE(a, b) (! (((a)->st_dev ^ (b)->st_dev) \\\n+ | ((a)->st_ino[0] ^ (b)->st_ino[0]) \\\n+ | ((a)->st_ino[1] ^ (b)->st_ino[1]) \\\n+ | ((a)->st_ino[2] ^ (b)->st_ino[2])))\n+#elif defined _WIN32 && ! defined __CYGWIN__\n+ /* Native Windows. */\n+# if _GL_WINDOWS_STAT_INODES\n+ /* stat() and fstat() set st_dev and st_ino to 0 if information about\n+ the inode is not available. */\n+# if _GL_WINDOWS_STAT_INODES == 2\n+# define PSAME_INODE(a, b) \\\n+ (! (! ((a)->st_dev | (a)->st_ino._gl_ino[0] | (a)->st_ino._gl_ino[1]) \\\n+ | ((a)->st_dev ^ (b)->st_dev) \\\n+ | ((a)->st_ino._gl_ino[0] ^ (b)->st_ino._gl_ino[0]) \\\n+ | ((a)->st_ino._gl_ino[1] ^ (b)->st_ino._gl_ino[1])))\n+# else\n+# define PSAME_INODE(a, b) (! (! ((a)->st_dev | (a)->st_ino) \\\n+ | ((a)->st_dev ^ (b)->st_dev) \\\n+ | ((a)->st_ino ^ (b)->st_ino)))\n+# endif\n+# else\n+ /* stat() and fstat() set st_ino to 0 always. */\n+# define PSAME_INODE(a, b) 0\n+# endif\n+#else\n+ /* POSIX. */\n+# define PSAME_INODE(a, b) (! (((a)->st_dev ^ (b)->st_dev) \\\n+ | ((a)->st_ino ^ (b)->st_ino)))\n+#endif\n+\n+/* True if struct objects A and B are known to represent the same file. */\n+\n+#define SAME_INODE(a, b) PSAME_INODE (&(a), &(b))\n+\n+/* True if *A and *B represent the same file. Unlike PSAME_INODE,\n+ args are evaluated once and must point to struct stat,\n+ and this function works even on POSIX platforms where fstat etc. do\n+ not return useful st_dev and st_ino values for shared memory\n+ objects and typed memory objects. */\n+\n+SAME_INODE_INLINE bool\n+psame_inode (struct stat const *a, struct stat const *b)\n+{\n+ return (! (S_TYPEISSHM (a) | S_TYPEISTMO (a)\n+ | S_TYPEISSHM (b) | S_TYPEISTMO (b))\n+ && PSAME_INODE (a, b));\n+}\n+\n+\n+#ifdef __cplusplus\n+}\n+#endif\n+\n+_GL_INLINE_HEADER_END\n+\n+#endif\ndiff --git a/io/tst-fts-bz22944.c b/io/tst-fts-bz22944.c\nnew file mode 100644\nindex 0000000000..41bcd5f597\n--- /dev/null\n+++ b/io/tst-fts-bz22944.c\n@@ -0,0 +1,100 @@\n+/* Check if fts does not fail with very long paths.\n+ Copyright (C) 2026 Free Software Foundation, Inc.\n+ This file is part of the GNU C Library.\n+\n+ The GNU C Library is free software; you can redistribute it and/or\n+ modify it under the terms of the GNU Lesser General Public\n+ License as published by the Free Software Foundation; either\n+ version 2.1 of the License, or (at your option) any later version.\n+\n+ The GNU C Library is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public\n+ License along with the GNU C Library; if not, see\n+ <https://www.gnu.org/licenses/>. */\n+\n+#include <fts.h>\n+#include <errno.h>\n+#include <stdio.h>\n+#include <support/check.h>\n+#include <support/temp_file.h>\n+#include <support/xunistd.h>\n+\n+#define BASENAME \"tst-fts-bz22944.\"\n+\n+enum { nested_depth = 150 };\n+static const char dir_name[] = { [0 ... 254] = 'A', '\\0' };\n+\n+static void\n+do_cleanup (void)\n+{\n+ xchdir (\"..\");\n+ for (int i = 0; i < nested_depth; i++)\n+ {\n+ remove (dir_name);\n+ xchdir (\"..\");\n+ }\n+ remove (dir_name);\n+}\n+#define CLEANUP_HANDLER do_cleanup\n+\n+static void\n+check_mkdir (const char *path)\n+{\n+ int r = mkdir (path, 0700);\n+ /* Some filesystem such as overlayfs does not support larger path required\n+ to trigger the internal buffer reallocation. */\n+ if (r != 0)\n+ {\n+ if (errno == ENAMETOOLONG)\n+\tFAIL_UNSUPPORTED (\"the filesystem does not support the required\"\n+\t\t\t \"large path\");\n+ else\n+\tFAIL_EXIT1 (\"mkdir (\\\"%s\\\", 0%o): %m\", path, 0700);\n+ }\n+}\n+\n+int\n+do_test (void)\n+{\n+ char *tempdir = support_create_temp_directory (BASENAME);\n+ xchdir (tempdir);\n+ for (int i = 0; i < nested_depth; i++)\n+ {\n+ check_mkdir (dir_name);\n+ xchdir (dir_name);\n+ }\n+\n+ char *paths[] = { tempdir , 0 };\n+ FTS *ftsp = fts_open (paths, FTS_XDEV | FTS_COMFOLLOW | FTS_PHYSICAL, 0);\n+ TEST_VERIFY_EXIT (ftsp != NULL);\n+\n+ int num_dirs = 0;\n+\n+ FTSENT *ent;\n+ while ((ent = fts_read(ftsp)) != 0)\n+ {\n+ switch (ent->fts_info)\n+\t{\n+\tcase FTS_D:\n+\t num_dirs++;\n+\t break;\n+\tdefault:\n+\t break;\n+\t}\n+ }\n+\n+ TEST_COMPARE (num_dirs, nested_depth + 1);\n+ TEST_COMPARE (errno, 0);\n+\n+ fts_close (ftsp);\n+\n+ do_cleanup ();\n+\n+ return 0;\n+}\n+\n+#include <support/test-driver.c>\ndiff --git a/io/tst-fts-newflags.c b/io/tst-fts-newflags.c\nnew file mode 100644\nindex 0000000000..49cd630f3a\n--- /dev/null\n+++ b/io/tst-fts-newflags.c\n@@ -0,0 +1,234 @@\n+/* Simple tests for some gnulib imported fts features.\n+ Copyright (C) 2026 Free Software Foundation, Inc.\n+ This file is part of the GNU C Library.\n+\n+ The GNU C Library is free software; you can redistribute it and/or\n+ modify it under the terms of the GNU Lesser General Public\n+ License as published by the Free Software Foundation; either\n+ version 2.1 of the License, or (at your option) any later version.\n+\n+ The GNU C Library is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public\n+ License along with the GNU C Library; if not, see\n+ <https://www.gnu.org/licenses/>. */\n+\n+#include <errno.h>\n+#include <fts.h>\n+#include <stdbool.h>\n+#include <stdio.h>\n+#include <stdlib.h>\n+#include <fcntl.h>\n+#include <string.h>\n+#include <support/check.h>\n+#include <support/support.h>\n+#include <support/temp_file.h>\n+#include <support/xunistd.h>\n+\n+static char *tempdir;\n+\n+static void\n+do_prepare (int argc, char **argv)\n+{\n+ tempdir = support_create_temp_directory (\"tst-fts-newflags\");\n+\n+ /* Create directory tree:\n+ tempdir/dir\n+ tempdir/dir/file\n+ tempdir/dir/symlink -> tempdir (cycle) */\n+ char *path;\n+\n+ path = xasprintf (\"%s/dir\", tempdir);\n+ xmkdir (path, 0777);\n+ add_temp_file (path);\n+ free (path);\n+\n+ path = xasprintf (\"%s/dir/file\", tempdir);\n+ int fd = xopen (path, O_CREAT | O_RDWR, 0666);\n+ xclose (fd);\n+ add_temp_file (path);\n+ free (path);\n+\n+ path = xasprintf (\"%s/dir/symlink\", tempdir);\n+ xsymlink (tempdir, path);\n+ add_temp_file (path);\n+ free (path);\n+}\n+#define PREPARE do_prepare\n+\n+/* FTS_TIGHT_CYCLE_CHECK: we use FTS_LOGICAL to follow the symlink we\n+ created, causing a loop. The tight cycle checker should catch this\n+ immediately and emit FTS_DC. */\n+static void\n+test_tight_cycle (void)\n+{\n+ char *paths[] = { tempdir, NULL };\n+ FTS *fts = fts_open (paths, FTS_LOGICAL | FTS_TIGHT_CYCLE_CHECK, NULL);\n+ TEST_VERIFY_EXIT (fts != NULL);\n+\n+ FTSENT *ent;\n+ bool found_cycle = false;\n+ while ((ent = fts_read (fts)) != NULL)\n+ {\n+ if (ent->fts_info == FTS_DC)\n+ {\n+ found_cycle = true;\n+ break;\n+ }\n+ }\n+ TEST_VERIFY (found_cycle);\n+ fts_close (fts);\n+}\n+\n+/* FTS_CWDFD: ensures that fts uses virtual file descriptors and does not\n+ actually change the process's global working directory. */\n+static void\n+test_cwdfd (void)\n+{\n+ char *paths[] = { tempdir, NULL };\n+ FTS *fts = fts_open (paths, FTS_PHYSICAL | FTS_CWDFD, NULL);\n+ TEST_VERIFY_EXIT (fts != NULL);\n+\n+ char *cwd_before = getcwd (NULL, 0);\n+ TEST_VERIFY_EXIT (cwd_before != NULL);\n+\n+ FTSENT *ent;\n+ while ((ent = fts_read (fts)) != NULL)\n+ {\n+ }\n+\n+ char *cwd_after = getcwd (NULL, 0);\n+ TEST_VERIFY_EXIT (cwd_after != NULL);\n+\n+ /* If FTS_CWDFD works, the global CWD remains untouched. */\n+ TEST_COMPARE_STRING (cwd_before, cwd_after);\n+\n+ free (cwd_before);\n+ free (cwd_after);\n+ fts_close (fts);\n+}\n+\n+/* FTS_DEFER_STAT: verifies that deferring the stat calls does not break\n+ standard physical tree traversals. */\n+static void\n+test_defer_stat (void)\n+{\n+ char *paths[] = { tempdir, NULL };\n+ FTS *fts = fts_open (paths, FTS_PHYSICAL | FTS_DEFER_STAT, NULL);\n+ TEST_VERIFY_EXIT (fts != NULL);\n+\n+ FTSENT *ent;\n+ int count = 0;\n+ while ((ent = fts_read (fts)) != NULL)\n+ {\n+ count++;\n+ }\n+\n+ /* Expects:\n+\n+ 1: $tmpdir\n+ 2: $tmpdir/dir\n+ 3: $tmpdir/dir/file\n+ 4: $tmpdir/dir/symlink\n+ 5: $tmpdir/dir/\n+ 6: $tmpdir/ */\n+ TEST_COMPARE (count, 6);\n+ fts_close (fts);\n+}\n+\n+/* FTS_MOUNT: validates that the traversal refuses to cross into a different\n+ file system when the flag is set. Assumes /proc is on a different mount. */\n+static void\n+test_mount (void)\n+{\n+ /* Create a symlink to /proc, which resides on a different mount point. */\n+ char *link_path = xasprintf (\"%s/mnt_link\", tempdir);\n+ xsymlink (\"/proc\", link_path);\n+\n+ /* Traverse with FTS_LOGICAL so fts resolves the symlink and sees the\n+ /proc device ID, but add FTS_MOUNT to enforce the boundary. */\n+ char *paths[] = { tempdir, NULL };\n+ FTS *fts = fts_open (paths, FTS_LOGICAL | FTS_MOUNT, NULL);\n+ TEST_VERIFY_EXIT (fts != NULL);\n+\n+ FTSENT *ent;\n+ bool found_mnt_link = false;\n+ while ((ent = fts_read (fts)) != NULL)\n+ {\n+ if (strcmp (ent->fts_name, \"mnt_link\") == 0)\n+ found_mnt_link = true;\n+ }\n+\n+ /* Because the device ID of /proc differs from the root traversal\n+ device ID, FTS_MOUNT forces fts to skip the entry entirely. */\n+ TEST_VERIFY (!found_mnt_link);\n+\n+ fts_close (fts);\n+ unlink (link_path);\n+ free (link_path);\n+}\n+\n+/* FTS_VERBATIM: eEnsures paths are passed through without having trailing\n+ slashes stripped. */\n+static void\n+test_verbatim (void)\n+{\n+ char *path_with_slashes = xasprintf (\"%s///\", tempdir);\n+ char *paths[] = { path_with_slashes, NULL };\n+\n+ FTS *fts = fts_open (paths, FTS_PHYSICAL | FTS_VERBATIM, NULL);\n+ TEST_VERIFY_EXIT (fts != NULL);\n+\n+ FTSENT *ent = fts_read (fts);\n+ TEST_VERIFY_EXIT (ent != NULL);\n+\n+ /* The returned root path should retain the exact slashes passed to it. */\n+ TEST_COMPARE_STRING (ent->fts_path, path_with_slashes);\n+\n+ fts_close (fts);\n+ free (path_with_slashes);\n+}\n+\n+/* Main test driver */\n+static int\n+do_test (void)\n+{\n+ support_need_proc (\"FTS_MOUNT test requires /proc\");\n+\n+ {\n+ /* Check if fts_open does not fail if neither FTS_LOGICAL nor FTS_PHYSICAL\n+ are specified. */\n+ char *paths[] = { tempdir, NULL };\n+ FTS *fts = fts_open (paths, 0, NULL);\n+ TEST_VERIFY_EXIT (fts != NULL);\n+ fts_close (fts);\n+ }\n+\n+ {\n+ FTS *fts;\n+ char *paths[] = { tempdir, NULL };\n+\n+ /* There are internal only flags. */\n+ fts = fts_open (paths, FTS_NAMEONLY, NULL);\n+ TEST_VERIFY_EXIT (fts == NULL);\n+ TEST_COMPARE (errno, EINVAL);\n+\n+ fts = fts_open (paths, FTS_STOP, NULL);\n+ TEST_VERIFY_EXIT (fts == NULL);\n+ TEST_COMPARE (errno, EINVAL);\n+ }\n+\n+ test_tight_cycle ();\n+ test_cwdfd ();\n+ test_defer_stat ();\n+ test_mount ();\n+ test_verbatim ();\n+\n+ return 0;\n+}\n+\n+/* Includes the glibc test framework driver */\n+#include <support/test-driver.c>\ndiff --git a/io/tst-fts.c b/io/tst-fts.c\nindex 494eb29c9a..ca82377d20 100644\n--- a/io/tst-fts.c\n+++ b/io/tst-fts.c\n@@ -192,6 +192,8 @@ do_test (void)\n don't use FTS_LOGICAL. */\n #ifndef TST_FTS_Y2038\n flags |= FTS_LOGICAL;\n+#else\n+ flags |= FTS_PHYSICAL;\n #endif\n fts = fts_open (paths, flags, &compare_ents);\n if (fts == NULL)\ndiff --git a/misc/Makefile b/misc/Makefile\nindex fc44de9934..4395366d74 100644\n--- a/misc/Makefile\n+++ b/misc/Makefile\n@@ -121,6 +121,7 @@ routines := \\\n getusershell \\\n getxattr \\\n gtty \\\n+ hash \\\n hsearch \\\n hsearch_r \\\n ifunc-impl-list \\\n@@ -157,6 +158,7 @@ routines := \\\n munlock \\\n munlockall \\\n munmap \\\n+ next-prime \\\n preadv \\\n preadv2 \\\n preadv64 \\\ndiff --git a/misc/hash.c b/misc/hash.c\nnew file mode 100644\nindex 0000000000..f722713a8f\n--- /dev/null\n+++ b/misc/hash.c\n@@ -0,0 +1,1045 @@\n+/* hash - hashing table processing.\n+\n+ Copyright (C) 1998-2004, 2006-2007, 2009-2026 Free Software Foundation, Inc.\n+\n+ Written by Jim Meyering, 1992.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+/* A generic hash table package. */\n+\n+/* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead\n+ of malloc. If you change USE_OBSTACK, you have to recompile! */\n+\n+#include <config.h>\n+#ifdef _LIBC\n+# define USE_OBSTACK 0\n+# define TESTING 0\n+# include <stdbit.h>\n+# define rotr_sz(__x, __n) stdc_rotate_right(__x, __n)\n+#else\n+# include \"bitrotate.h\"\n+#endif\n+\n+#include \"hash.h\"\n+\n+#include \"next-prime.h\"\n+#include \"xalloc-oversized.h\"\n+\n+#include <errno.h>\n+#include <stdint.h>\n+#include <stdio.h>\n+#include <stdlib.h>\n+\n+#if USE_OBSTACK\n+# include \"obstack.h\"\n+# ifndef obstack_chunk_alloc\n+# define obstack_chunk_alloc malloc\n+# endif\n+# ifndef obstack_chunk_free\n+# define obstack_chunk_free free\n+# endif\n+#endif\n+\n+struct hash_entry\n+ {\n+ void *data;\n+ struct hash_entry *next;\n+ /* Invariant: If DATA is NULL, this entry is an unused bucket head,\n+ and therefore NEXT is NULL as well. */\n+ };\n+\n+struct hash_table\n+ {\n+ /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,\n+ for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets\n+ are not empty, there are N_ENTRIES active entries in the table. */\n+ struct hash_entry *bucket;\n+ struct hash_entry const *bucket_limit;\n+ size_t n_buckets;\n+ size_t n_buckets_used;\n+ size_t n_entries;\n+\n+ /* Tuning arguments, kept in a physically separate structure. */\n+ const Hash_tuning *tuning;\n+\n+ /* Three functions are given to 'hash_initialize', see the documentation\n+ block for this function. In a word, HASHER randomizes a user entry\n+ into a number up from 0 up to some maximum minus 1; COMPARATOR returns\n+ true if two user entries compare equally; and DATA_FREER is the cleanup\n+ function for a user entry. */\n+ Hash_hasher hasher;\n+ Hash_comparator comparator;\n+ Hash_data_freer data_freer;\n+\n+ /* A linked list of freed struct hash_entry structs. */\n+ struct hash_entry *free_entry_list;\n+\n+#if USE_OBSTACK\n+ /* Whenever obstacks are used, it is possible to allocate all overflowed\n+ entries into a single stack, so they all can be freed in a single\n+ operation. It is not clear if the speedup is worth the trouble. */\n+ struct obstack entry_stack;\n+#endif\n+ };\n+\n+/* A hash table contains many internal entries, each holding a pointer to\n+ some user-provided data (also called a user entry). An entry indistinctly\n+ refers to both the internal entry and its associated user entry. A user\n+ entry contents may be hashed by a randomization function (the hashing\n+ function, or just \"hasher\" for short) into a number (or \"slot\") between 0\n+ and the current table size. At each slot position in the hash table,\n+ starts a linked chain of entries for which the user data all hash to this\n+ slot. A bucket is the collection of all entries hashing to the same slot.\n+\n+ A good \"hasher\" function will distribute entries rather evenly in buckets.\n+ In the ideal case, the length of each bucket is roughly the number of\n+ entries divided by the table size. Finding the slot for a data is usually\n+ done in constant time by the \"hasher\", and the later finding of a precise\n+ entry is linear in time with the size of the bucket. Consequently, a\n+ larger hash table size (that is, a larger number of buckets) is prone to\n+ yielding shorter chains, *given* the \"hasher\" function behaves properly.\n+\n+ Long buckets slow down the lookup algorithm. One might use big hash table\n+ sizes in hope to reduce the average length of buckets, but this might\n+ become inordinate, as unused slots in the hash table take some space. The\n+ best bet is to make sure you are using a good \"hasher\" function (beware\n+ that those are not that easy to write! :-), and to use a table size\n+ larger than the actual number of entries. */\n+\n+/* If an insertion makes the ratio of nonempty buckets to table size larger\n+ than the growth threshold (a number between 0.0 and 1.0), then increase\n+ the table size by multiplying by the growth factor (a number greater than\n+ 1.0). The growth threshold defaults to 0.8, and the growth factor\n+ defaults to 1.414, meaning that the table will have doubled its size\n+ every second time 80% of the buckets get used. */\n+#define DEFAULT_GROWTH_THRESHOLD 0.8f\n+#define DEFAULT_GROWTH_FACTOR 1.414f\n+\n+/* If a deletion empties a bucket and causes the ratio of used buckets to\n+ table size to become smaller than the shrink threshold (a number between\n+ 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a\n+ number greater than the shrink threshold but smaller than 1.0). The shrink\n+ threshold and factor default to 0.0 and 1.0, meaning that the table never\n+ shrinks. */\n+#define DEFAULT_SHRINK_THRESHOLD 0.0f\n+#define DEFAULT_SHRINK_FACTOR 1.0f\n+\n+/* Use this to initialize or reset a TUNING structure to\n+ some sensible values. */\n+static const Hash_tuning default_tuning =\n+ {\n+ DEFAULT_SHRINK_THRESHOLD,\n+ DEFAULT_SHRINK_FACTOR,\n+ DEFAULT_GROWTH_THRESHOLD,\n+ DEFAULT_GROWTH_FACTOR,\n+ false\n+ };\n+\n+/* Information and lookup. */\n+\n+#if !_LIBC\n+size_t\n+hash_get_n_buckets (const Hash_table *table)\n+{\n+ return table->n_buckets;\n+}\n+\n+size_t\n+hash_get_n_buckets_used (const Hash_table *table)\n+{\n+ return table->n_buckets_used;\n+}\n+\n+size_t\n+hash_get_n_entries (const Hash_table *table)\n+{\n+ return table->n_entries;\n+}\n+\n+size_t\n+hash_get_max_bucket_length (const Hash_table *table)\n+{\n+ size_t max_bucket_length = 0;\n+\n+ for (struct hash_entry const *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket->data)\n+ {\n+ struct hash_entry const *cursor = bucket;\n+ size_t bucket_length = 1;\n+\n+ while (cursor = cursor->next, cursor)\n+ bucket_length++;\n+\n+ if (bucket_length > max_bucket_length)\n+ max_bucket_length = bucket_length;\n+ }\n+ }\n+\n+ return max_bucket_length;\n+}\n+\n+bool\n+hash_table_ok (const Hash_table *table)\n+{\n+ size_t n_buckets_used = 0;\n+ size_t n_entries = 0;\n+\n+ for (struct hash_entry const *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket->data)\n+ {\n+ struct hash_entry const *cursor = bucket;\n+\n+ /* Count bucket head. */\n+ n_buckets_used++;\n+ n_entries++;\n+\n+ /* Count bucket overflow. */\n+ while (cursor = cursor->next, cursor)\n+ n_entries++;\n+ }\n+ }\n+\n+ if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)\n+ return true;\n+\n+ return false;\n+}\n+\n+void\n+hash_print_statistics (const Hash_table *table, FILE *stream)\n+{\n+ size_t n_entries = hash_get_n_entries (table);\n+ size_t n_buckets = hash_get_n_buckets (table);\n+ size_t n_buckets_used = hash_get_n_buckets_used (table);\n+ size_t max_bucket_length = hash_get_max_bucket_length (table);\n+\n+ fprintf (stream, \"# entries: %lu\\n\", (unsigned long int) n_entries);\n+ fprintf (stream, \"# buckets: %lu\\n\", (unsigned long int) n_buckets);\n+ fprintf (stream, \"# buckets used: %lu (%.2f%%)\\n\",\n+ (unsigned long int) n_buckets_used,\n+ (100.0 * n_buckets_used) / n_buckets);\n+ fprintf (stream, \"max bucket length: %lu\\n\",\n+ (unsigned long int) max_bucket_length);\n+}\n+#endif\n+\n+/* Hash KEY and return a pointer to the selected bucket.\n+ If TABLE->hasher misbehaves, abort. */\n+static struct hash_entry *\n+safe_hasher (const Hash_table *table, const void *key)\n+{\n+ size_t n = table->hasher (key, table->n_buckets);\n+ if (! (n < table->n_buckets))\n+ abort ();\n+ return table->bucket + n;\n+}\n+\n+void *\n+hash_lookup (const Hash_table *table, const void *entry)\n+{\n+ struct hash_entry const *bucket = safe_hasher (table, entry);\n+\n+ if (bucket->data == NULL)\n+ return NULL;\n+\n+ for (struct hash_entry const *cursor = bucket; cursor; cursor = cursor->next)\n+ if (entry == cursor->data || table->comparator (entry, cursor->data))\n+ return cursor->data;\n+\n+ return NULL;\n+}\n+\n+#if !_LIBC\n+/* Walking. */\n+\n+void *\n+hash_get_first (const Hash_table *table)\n+{\n+ if (table->n_entries == 0)\n+ return NULL;\n+\n+ for (struct hash_entry const *bucket = table->bucket; ; bucket++)\n+ if (! (bucket < table->bucket_limit))\n+ abort ();\n+ else if (bucket->data)\n+ return bucket->data;\n+}\n+\n+void *\n+hash_get_next (const Hash_table *table, const void *entry)\n+{\n+ struct hash_entry const *bucket = safe_hasher (table, entry);\n+\n+ /* Find next entry in the same bucket. */\n+ {\n+ struct hash_entry const *cursor = bucket;\n+ do\n+ {\n+ if (cursor->data == entry && cursor->next)\n+ return cursor->next->data;\n+ cursor = cursor->next;\n+ }\n+ while (cursor != NULL);\n+ }\n+\n+ /* Find first entry in any subsequent bucket. */\n+ while (++bucket < table->bucket_limit)\n+ if (bucket->data)\n+ return bucket->data;\n+\n+ /* None found. */\n+ return NULL;\n+}\n+\n+size_t\n+hash_get_entries (const Hash_table *table, void **buffer,\n+ size_t buffer_size)\n+{\n+ size_t counter = 0;\n+\n+ for (struct hash_entry const *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket->data)\n+ {\n+ for (struct hash_entry const *cursor = bucket; cursor; cursor = cursor->next)\n+ {\n+ if (counter >= buffer_size)\n+ return counter;\n+ buffer[counter++] = cursor->data;\n+ }\n+ }\n+ }\n+\n+ return counter;\n+}\n+\n+size_t\n+hash_do_for_each (const Hash_table *table, Hash_processor processor,\n+ void *processor_data)\n+{\n+ size_t counter = 0;\n+\n+ for (struct hash_entry const *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket->data)\n+ {\n+ for (struct hash_entry const *cursor = bucket; cursor; cursor = cursor->next)\n+ {\n+ if (! processor (cursor->data, processor_data))\n+ return counter;\n+ counter++;\n+ }\n+ }\n+ }\n+\n+ return counter;\n+}\n+#endif\n+\n+\n+/* If the user passes a NULL hasher, we hash the raw pointer. */\n+static size_t\n+raw_hasher (const void *data, size_t n)\n+{\n+ /* When hashing unique pointers, it is often the case that they were\n+ generated by malloc and thus have the property that the low-order\n+ bits are 0. As this tends to give poorer performance with small\n+ tables, we rotate the pointer value before performing division,\n+ in an attempt to improve hash quality. */\n+ size_t val = rotr_sz ((size_t) data, 3);\n+ return val % n;\n+}\n+\n+/* If the user passes a NULL comparator, we use pointer comparison. */\n+static bool\n+raw_comparator (const void *a, const void *b)\n+{\n+ return a == b;\n+}\n+\n+\n+#if !_LIBC\n+/* Allocation and clean-up. */\n+\n+void\n+hash_reset_tuning (Hash_tuning *tuning)\n+{\n+ *tuning = default_tuning;\n+}\n+#endif\n+\n+/* For the given hash TABLE, check the user supplied tuning structure for\n+ reasonable values, and return true if there is no gross error with it.\n+ Otherwise, definitively reset the TUNING field to some acceptable default\n+ in the hash table (that is, the user loses the right of further modifying\n+ tuning arguments), and return false. */\n+\n+static bool\n+check_tuning (Hash_table *table)\n+{\n+ const Hash_tuning *tuning = table->tuning;\n+ if (tuning == &default_tuning)\n+ return true;\n+\n+ /* Be a bit stricter than mathematics would require, so that\n+ rounding errors in size calculations do not cause allocations to\n+ fail to grow or shrink as they should. The smallest allocation\n+ is 11 (due to next_prime's algorithm), so an epsilon of 0.1\n+ should be good enough. */\n+ float epsilon = 0.1f;\n+\n+ if (epsilon < tuning->growth_threshold\n+ && tuning->growth_threshold < 1 - epsilon\n+ && 1 + epsilon < tuning->growth_factor\n+ && 0 <= tuning->shrink_threshold\n+ && tuning->shrink_threshold + epsilon < tuning->shrink_factor\n+ && tuning->shrink_factor <= 1\n+ && tuning->shrink_threshold + epsilon < tuning->growth_threshold)\n+ return true;\n+\n+ table->tuning = &default_tuning;\n+ return false;\n+}\n+\n+/* Compute the size of the bucket array for the given CANDIDATE and\n+ TUNING, or return 0 if there is no possible way to allocate that\n+ many entries. */\n+\n+static size_t _GL_ATTRIBUTE_PURE\n+compute_bucket_size (size_t candidate, const Hash_tuning *tuning)\n+{\n+ if (!tuning->is_n_buckets)\n+ {\n+ float new_candidate = candidate / tuning->growth_threshold;\n+ if ((float) SIZE_MAX <= new_candidate)\n+ goto nomem;\n+ candidate = new_candidate;\n+ }\n+ candidate = next_prime (candidate);\n+ if (xalloc_oversized (candidate, sizeof (struct hash_entry *)))\n+ goto nomem;\n+ return candidate;\n+\n+ nomem:\n+ errno = ENOMEM;\n+ return 0;\n+}\n+\n+Hash_table *\n+hash_initialize (size_t candidate, const Hash_tuning *tuning,\n+ Hash_hasher hasher, Hash_comparator comparator,\n+ Hash_data_freer data_freer)\n+{\n+ if (hasher == NULL)\n+ hasher = raw_hasher;\n+ if (comparator == NULL)\n+ comparator = raw_comparator;\n+\n+ Hash_table *table = malloc (sizeof *table);\n+ if (table == NULL)\n+ return NULL;\n+\n+ if (!tuning)\n+ tuning = &default_tuning;\n+ table->tuning = tuning;\n+ if (!check_tuning (table))\n+ {\n+ /* Fail if the tuning options are invalid. This is the only occasion\n+ when the user gets some feedback about it. Once the table is created,\n+ if the user provides invalid tuning options, we silently revert to\n+ using the defaults, and ignore further request to change the tuning\n+ options. */\n+ errno = EINVAL;\n+ goto fail;\n+ }\n+\n+ table->n_buckets = compute_bucket_size (candidate, tuning);\n+ if (!table->n_buckets)\n+ goto fail;\n+\n+ table->bucket = calloc (table->n_buckets, sizeof *table->bucket);\n+ if (table->bucket == NULL)\n+ goto fail;\n+ table->bucket_limit = table->bucket + table->n_buckets;\n+ table->n_buckets_used = 0;\n+ table->n_entries = 0;\n+\n+ table->hasher = hasher;\n+ table->comparator = comparator;\n+ table->data_freer = data_freer;\n+\n+ table->free_entry_list = NULL;\n+#if USE_OBSTACK\n+ obstack_init (&table->entry_stack);\n+#endif\n+ return table;\n+\n+ fail:\n+ free (table);\n+ return NULL;\n+}\n+\n+#if !_LIBC\n+void\n+hash_clear (Hash_table *table)\n+{\n+ for (struct hash_entry *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket->data)\n+ {\n+ /* Free the bucket overflow. */\n+ for (struct hash_entry *cursor = bucket->next; cursor; )\n+ {\n+ if (table->data_freer)\n+ table->data_freer (cursor->data);\n+ cursor->data = NULL;\n+\n+ struct hash_entry *next = cursor->next;\n+ /* Relinking is done one entry at a time, as it is to be expected\n+ that overflows are either rare or short. */\n+ cursor->next = table->free_entry_list;\n+ table->free_entry_list = cursor;\n+\n+ cursor = next;\n+ }\n+\n+ /* Free the bucket head. */\n+ if (table->data_freer)\n+ table->data_freer (bucket->data);\n+ bucket->data = NULL;\n+ bucket->next = NULL;\n+ }\n+ }\n+\n+ table->n_buckets_used = 0;\n+ table->n_entries = 0;\n+}\n+#endif\n+\n+void\n+hash_free (Hash_table *table)\n+{\n+ int saved_errno = errno;\n+\n+ /* Call the user data_freer function. */\n+ if (table->data_freer && table->n_entries)\n+ {\n+ for (struct hash_entry *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket->data)\n+ {\n+ for (struct hash_entry *cursor = bucket; cursor; cursor = cursor->next)\n+ table->data_freer (cursor->data);\n+ }\n+ }\n+ }\n+\n+#if USE_OBSTACK\n+\n+ obstack_free (&table->entry_stack, NULL);\n+\n+#else\n+\n+ /* Free all bucket overflowed entries. */\n+ for (struct hash_entry *bucket = table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ for (struct hash_entry *cursor = bucket->next; cursor; )\n+ {\n+ struct hash_entry *next = cursor->next;\n+ free (cursor);\n+ cursor = next;\n+ }\n+ }\n+\n+ /* Also reclaim the internal list of previously freed entries. */\n+ for (struct hash_entry *cursor = table->free_entry_list; cursor; )\n+ {\n+ struct hash_entry *next = cursor->next;\n+ free (cursor);\n+ cursor = next;\n+ }\n+\n+#endif\n+\n+ /* Free the remainder of the hash table structure. */\n+ free (table->bucket);\n+ free (table);\n+\n+ errno = saved_errno;\n+}\n+\n+/* Insertion and deletion. */\n+\n+/* Get a new hash entry for a bucket overflow, possibly by recycling a\n+ previously freed one. If this is not possible, allocate a new one. */\n+\n+static struct hash_entry *\n+allocate_entry (Hash_table *table)\n+{\n+ struct hash_entry *new;\n+\n+ if (table->free_entry_list)\n+ {\n+ new = table->free_entry_list;\n+ table->free_entry_list = new->next;\n+ }\n+ else\n+ {\n+#if USE_OBSTACK\n+ new = obstack_alloc (&table->entry_stack, sizeof *new);\n+#else\n+ new = malloc (sizeof *new);\n+#endif\n+ }\n+\n+ return new;\n+}\n+\n+/* Free a hash entry which was part of some bucket overflow,\n+ saving it for later recycling. */\n+\n+static void\n+free_entry (Hash_table *table, struct hash_entry *entry)\n+{\n+ entry->data = NULL;\n+ entry->next = table->free_entry_list;\n+ table->free_entry_list = entry;\n+}\n+\n+/* This private function is used to help with insertion and deletion. When\n+ ENTRY matches an entry in the table, return a pointer to the corresponding\n+ user data and set *BUCKET_HEAD to the head of the selected bucket.\n+ Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in\n+ the table, unlink the matching entry. */\n+\n+static void *\n+find_entry (Hash_table *table, const void *entry,\n+ struct hash_entry **bucket_head, bool delete)\n+{\n+ struct hash_entry *bucket = safe_hasher (table, entry);\n+\n+ *bucket_head = bucket;\n+\n+ /* Test for empty bucket. */\n+ if (bucket->data == NULL)\n+ return NULL;\n+\n+ /* See if the entry is the first in the bucket. */\n+ if (entry == bucket->data || table->comparator (entry, bucket->data))\n+ {\n+ void *data = bucket->data;\n+\n+ if (delete)\n+ {\n+ if (bucket->next)\n+ {\n+ struct hash_entry *next = bucket->next;\n+\n+ /* Bump the first overflow entry into the bucket head, then save\n+ the previous first overflow entry for later recycling. */\n+ *bucket = *next;\n+ free_entry (table, next);\n+ }\n+ else\n+ {\n+ bucket->data = NULL;\n+ }\n+ }\n+\n+ return data;\n+ }\n+\n+ /* Scan the bucket overflow. */\n+ for (struct hash_entry *cursor = bucket; cursor->next; cursor = cursor->next)\n+ {\n+ if (entry == cursor->next->data\n+ || table->comparator (entry, cursor->next->data))\n+ {\n+ void *data = cursor->next->data;\n+\n+ if (delete)\n+ {\n+ struct hash_entry *next = cursor->next;\n+\n+ /* Unlink the entry to delete, then save the freed entry for later\n+ recycling. */\n+ cursor->next = next->next;\n+ free_entry (table, next);\n+ }\n+\n+ return data;\n+ }\n+ }\n+\n+ /* No entry found. */\n+ return NULL;\n+}\n+\n+/* Internal helper, to move entries from SRC to DST. Both tables must\n+ share the same free entry list. If SAFE, only move overflow\n+ entries, saving bucket heads for later, so that no allocations will\n+ occur. Return false (setting errno) if the free entry list is\n+ exhausted and an allocation fails. */\n+\n+static bool\n+transfer_entries (Hash_table *dst, Hash_table *src, bool safe)\n+{\n+ for (struct hash_entry *bucket = src->bucket; bucket < src->bucket_limit; bucket++)\n+ if (bucket->data)\n+ {\n+ void *data;\n+ struct hash_entry *new_bucket;\n+\n+ /* Within each bucket, transfer overflow entries first and\n+ then the bucket head, to minimize memory pressure. After\n+ all, the only time we might allocate is when moving the\n+ bucket head, but moving overflow entries first may create\n+ free entries that can be recycled by the time we finally\n+ get to the bucket head. */\n+ for (struct hash_entry *cursor = bucket->next; cursor; )\n+ {\n+ data = cursor->data;\n+ new_bucket = safe_hasher (dst, data);\n+\n+ struct hash_entry *next = cursor->next;\n+\n+ if (new_bucket->data)\n+ {\n+ /* Merely relink an existing entry, when moving from a\n+ bucket overflow into a bucket overflow. */\n+ cursor->next = new_bucket->next;\n+ new_bucket->next = cursor;\n+ }\n+ else\n+ {\n+ /* Free an existing entry, when moving from a bucket\n+ overflow into a bucket header. */\n+ new_bucket->data = data;\n+ dst->n_buckets_used++;\n+ free_entry (dst, cursor);\n+ }\n+\n+ cursor = next;\n+ }\n+ /* Now move the bucket head. Be sure that if we fail due to\n+ allocation failure that the src table is in a consistent\n+ state. */\n+ data = bucket->data;\n+ bucket->next = NULL;\n+ if (!safe)\n+ {\n+ new_bucket = safe_hasher (dst, data);\n+\n+ if (new_bucket->data)\n+ {\n+ /* Allocate or recycle an entry, when moving from a bucket\n+ header into a bucket overflow. */\n+ struct hash_entry *new_entry = allocate_entry (dst);\n+\n+ if (new_entry == NULL)\n+ return false;\n+\n+ new_entry->data = data;\n+ new_entry->next = new_bucket->next;\n+ new_bucket->next = new_entry;\n+ }\n+ else\n+ {\n+ /* Move from one bucket header to another. */\n+ new_bucket->data = data;\n+ dst->n_buckets_used++;\n+ }\n+ bucket->data = NULL;\n+ src->n_buckets_used--;\n+ }\n+ }\n+ return true;\n+}\n+\n+bool\n+hash_rehash (Hash_table *table, size_t candidate)\n+{\n+ size_t new_size = compute_bucket_size (candidate, table->tuning);\n+\n+ if (!new_size)\n+ return false;\n+ if (new_size == table->n_buckets)\n+ return true;\n+\n+ Hash_table storage;\n+ Hash_table *new_table = &storage;\n+ new_table->bucket = calloc (new_size, sizeof *new_table->bucket);\n+ if (new_table->bucket == NULL)\n+ return false;\n+ new_table->n_buckets = new_size;\n+ new_table->bucket_limit = new_table->bucket + new_size;\n+ new_table->n_buckets_used = 0;\n+ new_table->n_entries = 0;\n+ new_table->tuning = table->tuning;\n+ new_table->hasher = table->hasher;\n+ new_table->comparator = table->comparator;\n+ new_table->data_freer = table->data_freer;\n+\n+ /* In order for the transfer to successfully complete, we need\n+ additional overflow entries when distinct buckets in the old\n+ table collide into a common bucket in the new table. The worst\n+ case possible is a hasher that gives a good spread with the old\n+ size, but returns a constant with the new size; if we were to\n+ guarantee table->n_buckets_used-1 free entries in advance, then\n+ the transfer would be guaranteed to not allocate memory.\n+ However, for large tables, a guarantee of no further allocation\n+ introduces a lot of extra memory pressure, all for an unlikely\n+ corner case (most rehashes reduce, rather than increase, the\n+ number of overflow entries needed). So, we instead ensure that\n+ the transfer process can be reversed if we hit a memory\n+ allocation failure mid-transfer. */\n+\n+ /* Merely reuse the extra old space into the new table. */\n+#if USE_OBSTACK\n+ new_table->entry_stack = table->entry_stack;\n+#endif\n+ new_table->free_entry_list = table->free_entry_list;\n+\n+ if (transfer_entries (new_table, table, false))\n+ {\n+ /* Entries transferred successfully; tie up the loose ends. */\n+ free (table->bucket);\n+ table->bucket = new_table->bucket;\n+ table->bucket_limit = new_table->bucket_limit;\n+ table->n_buckets = new_table->n_buckets;\n+ table->n_buckets_used = new_table->n_buckets_used;\n+ table->free_entry_list = new_table->free_entry_list;\n+ /* table->n_entries and table->entry_stack already hold their value. */\n+ return true;\n+ }\n+\n+ /* We've allocated new_table->bucket (and possibly some entries),\n+ exhausted the free list, and moved some but not all entries into\n+ new_table. We must undo the partial move before returning\n+ failure. The only way to get into this situation is if new_table\n+ uses fewer buckets than the old table, so we will reclaim some\n+ free entries as overflows in the new table are put back into\n+ distinct buckets in the old table.\n+\n+ There are some pathological cases where a single pass through the\n+ table requires more intermediate overflow entries than using two\n+ passes. Two passes give worse cache performance and takes\n+ longer, but at this point, we're already out of memory, so slow\n+ and safe is better than failure. */\n+ int saved_errno = errno;\n+ table->free_entry_list = new_table->free_entry_list;\n+ if (! (transfer_entries (table, new_table, true)\n+ && transfer_entries (table, new_table, false)))\n+ abort ();\n+ /* table->n_entries already holds its value. */\n+ free (new_table->bucket);\n+ errno = saved_errno;\n+ return false;\n+}\n+\n+int\n+hash_insert_if_absent (Hash_table *table, void const *entry,\n+ void const **matched_ent)\n+{\n+\n+ /* The caller cannot insert a NULL entry, since hash_lookup returns NULL\n+ to indicate \"not found\", and find_entry uses \"bucket->data == NULL\"\n+ to indicate an empty bucket. */\n+ if (! entry)\n+ abort ();\n+\n+ /* If there's a matching entry already in the table, return that. */\n+ struct hash_entry *bucket;\n+ void *data = find_entry (table, entry, &bucket, false);\n+ if (data != NULL)\n+ {\n+ if (matched_ent)\n+ *matched_ent = data;\n+ return 0;\n+ }\n+\n+ /* If the growth threshold of the buckets in use has been reached, increase\n+ the table size and rehash. There's no point in checking the number of\n+ entries: if the hashing function is ill-conditioned, rehashing is not\n+ likely to improve it. */\n+\n+ if (table->n_buckets_used\n+ > table->tuning->growth_threshold * table->n_buckets)\n+ {\n+ /* Check more fully, before starting real work. If tuning arguments\n+ became invalid, the second check will rely on proper defaults. */\n+ check_tuning (table);\n+ if (table->n_buckets_used\n+ > table->tuning->growth_threshold * table->n_buckets)\n+ {\n+ const Hash_tuning *tuning = table->tuning;\n+ float candidate =\n+ (tuning->is_n_buckets\n+ ? (table->n_buckets * tuning->growth_factor)\n+ : (table->n_buckets * tuning->growth_factor\n+ * tuning->growth_threshold));\n+\n+ if ((float) SIZE_MAX <= candidate)\n+ {\n+ errno = ENOMEM;\n+ return -1;\n+ }\n+\n+ /* If the rehash fails, arrange to return NULL. */\n+ if (!hash_rehash (table, candidate))\n+ return -1;\n+\n+ /* Update the bucket we are interested in. */\n+ if (find_entry (table, entry, &bucket, false) != NULL)\n+ abort ();\n+ }\n+ }\n+\n+ /* ENTRY is not matched, it should be inserted. */\n+\n+ if (bucket->data)\n+ {\n+ struct hash_entry *new_entry = allocate_entry (table);\n+\n+ if (new_entry == NULL)\n+ return -1;\n+\n+ /* Add ENTRY in the overflow of the bucket. */\n+\n+ new_entry->data = (void *) entry;\n+ new_entry->next = bucket->next;\n+ bucket->next = new_entry;\n+ table->n_entries++;\n+ return 1;\n+ }\n+\n+ /* Add ENTRY right in the bucket head. */\n+\n+ bucket->data = (void *) entry;\n+ table->n_entries++;\n+ table->n_buckets_used++;\n+\n+ return 1;\n+}\n+\n+void *\n+hash_insert (Hash_table *table, void const *entry)\n+{\n+ void const *matched_ent;\n+ int err = hash_insert_if_absent (table, entry, &matched_ent);\n+ return (err == -1\n+ ? NULL\n+ : (void *) (err == 0 ? matched_ent : entry));\n+}\n+\n+void *\n+hash_remove (Hash_table *table, const void *entry)\n+{\n+ struct hash_entry *bucket;\n+ void *data = find_entry (table, entry, &bucket, true);\n+ if (!data)\n+ return NULL;\n+\n+ table->n_entries--;\n+ if (!bucket->data)\n+ {\n+ table->n_buckets_used--;\n+\n+ /* If the shrink threshold of the buckets in use has been reached,\n+ rehash into a smaller table. */\n+\n+ if (table->n_buckets_used\n+ < table->tuning->shrink_threshold * table->n_buckets)\n+ {\n+ /* Check more fully, before starting real work. If tuning arguments\n+ became invalid, the second check will rely on proper defaults. */\n+ check_tuning (table);\n+ if (table->n_buckets_used\n+ < table->tuning->shrink_threshold * table->n_buckets)\n+ {\n+ const Hash_tuning *tuning = table->tuning;\n+ size_t candidate =\n+ (tuning->is_n_buckets\n+ ? table->n_buckets * tuning->shrink_factor\n+ : (table->n_buckets * tuning->shrink_factor\n+ * tuning->growth_threshold));\n+\n+ if (!hash_rehash (table, candidate))\n+ {\n+ /* Failure to allocate memory in an attempt to\n+ shrink the table is not fatal. But since memory\n+ is low, we can at least be kind and free any\n+ spare entries, rather than keeping them tied up\n+ in the free entry list. */\n+#if ! USE_OBSTACK\n+ struct hash_entry *cursor = table->free_entry_list;\n+ struct hash_entry *next;\n+ while (cursor)\n+ {\n+ next = cursor->next;\n+ free (cursor);\n+ cursor = next;\n+ }\n+ table->free_entry_list = NULL;\n+#endif\n+ }\n+ }\n+ }\n+ }\n+\n+ return data;\n+}\n+\n+/* Testing. */\n+\n+#if TESTING\n+\n+void\n+hash_print (const Hash_table *table)\n+{\n+ for (struct hash_entry *bucket = (struct hash_entry *) table->bucket;\n+ bucket < table->bucket_limit;\n+ bucket++)\n+ {\n+ if (bucket)\n+ printf (\"%lu:\\n\", (unsigned long int) (bucket - table->bucket));\n+\n+ for (struct hash_entry *cursor = bucket; cursor; cursor = cursor->next)\n+ {\n+ char const *s = cursor->data;\n+ /* FIXME */\n+ if (s)\n+ printf (\" %s\\n\", s);\n+ }\n+ }\n+}\n+\n+#endif /* TESTING */\ndiff --git a/misc/next-prime.c b/misc/next-prime.c\nnew file mode 100644\nindex 0000000000..62fbf94a47\n--- /dev/null\n+++ b/misc/next-prime.c\n@@ -0,0 +1,64 @@\n+/* Finding the next prime >= a given small integer.\n+ Copyright (C) 1995-2026 Free Software Foundation, Inc.\n+\n+ This file is free software: you can redistribute it and/or modify\n+ it under the terms of the GNU Lesser General Public License as\n+ published by the Free Software Foundation; either version 2.1 of the\n+ License, or (at your option) any later version.\n+\n+ This file is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see <https://www.gnu.org/licenses/>. */\n+\n+#include <config.h>\n+#ifdef _LIBC\n+# include <stdbool.h>\n+#endif\n+\n+/* Specification. */\n+#include \"next-prime.h\"\n+\n+#include <stdint.h> /* for SIZE_MAX */\n+\n+/* Return true if CANDIDATE is a prime number or 1.\n+ CANDIDATE should be an odd number >= 1. */\n+static bool _GL_ATTRIBUTE_CONST\n+is_prime (size_t candidate)\n+{\n+ size_t divisor = 3;\n+ size_t square = divisor * divisor;\n+\n+ for (;;)\n+ {\n+ if (square > candidate)\n+ return true;\n+ if ((candidate % divisor) == 0)\n+ return false;\n+ /* Increment divisor by 2. */\n+ divisor++;\n+ square += 4 * divisor;\n+ divisor++;\n+ }\n+}\n+\n+size_t _GL_ATTRIBUTE_CONST\n+next_prime (size_t candidate)\n+{\n+#if !defined IN_LIBGETTEXTLIB\n+ /* Skip small primes. */\n+ if (candidate < 10)\n+ candidate = 10;\n+#endif\n+\n+ /* Make it definitely odd. */\n+ candidate |= 1;\n+\n+ while (SIZE_MAX != candidate && !is_prime (candidate))\n+ candidate += 2;\n+\n+ return candidate;\n+}\ndiff --git a/sysdeps/mach/hurd/opendir.c b/sysdeps/mach/hurd/opendir.c\nindex ee005cc371..e610236a58 100644\n--- a/sysdeps/mach/hurd/opendir.c\n+++ b/sysdeps/mach/hurd/opendir.c\n@@ -66,14 +66,15 @@ _hurd_fd_opendir (struct hurd_fd *d)\n \n \n DIR *\n-__opendirat (int dfd, const char *name)\n+__opendirat (int dfd, const char *name, int extra_flags, int *pnew_fd)\n {\n if (name[0] == '\\0')\n /* POSIX.1-1990 says an empty name gets ENOENT;\n but `open' might like it fine. */\n return __hurd_fail (ENOENT), NULL;\n \n- int flags = O_RDONLY | O_NONBLOCK | O_DIRECTORY | O_CLOEXEC;\n+ int flags = O_RDONLY | O_NONBLOCK | O_DIRECTORY | O_CLOEXEC\n+ | extra_flags;\n int fd;\n #if IS_IN (rtld)\n assert (dfd == AT_FDCWD);\n@@ -88,6 +89,8 @@ __opendirat (int dfd, const char *name)\n DIR *dirp = _hurd_fd_opendir (_hurd_fd_get (fd));\n if (dirp == NULL)\n __close (fd);\n+ else if (pnew_fd != NULL)\n+ *pnew_fd = fd;\n \n return dirp;\n }\ndiff --git a/sysdeps/unix/sysv/linux/opendir.c b/sysdeps/unix/sysv/linux/opendir.c\nindex ceaaefe2bb..9c41a8ff3e 100644\n--- a/sysdeps/unix/sysv/linux/opendir.c\n+++ b/sysdeps/unix/sysv/linux/opendir.c\n@@ -66,12 +66,24 @@ opendir_tail (int fd)\n \n #if IS_IN (libc)\n DIR *\n-__opendirat (int dfd, const char *name)\n+__opendirat (int dfd, const char *name, int extra_flags, int *pnew_fd)\n {\n if (__glibc_unlikely (invalid_name (name)))\n return NULL;\n \n- return opendir_tail (__openat_nocancel (dfd, name, opendir_oflags));\n+ int open_oflags = opendir_oflags | extra_flags;\n+ int new_fd = __openat_nocancel (dfd, name, open_oflags);\n+ if (new_fd < 0)\n+ return NULL;\n+ DIR *dirp = opendir_tail (new_fd);\n+ if (dirp == NULL)\n+ {\n+ __close_nocancel_nostatus (new_fd);\n+ return NULL;\n+ }\n+ else if (pnew_fd != NULL)\n+ *pnew_fd = new_fd;\n+ return dirp;\n }\n #endif\n \n", "prefixes": [ "v4", "2/2" ] }