summaryrefslogtreecommitdiffstats
path: root/bftw.c
AgeCommit message (Collapse)Author
2022-03-09bftw: Fix open FD accountingTavian Barnes
Due to the introduction of bfs_dir, we don't need to reserve an extra file descriptor for the currently open directory.
2022-03-09bftw: Keep root paths at the head of the LRU listTavian Barnes
With a low ulimit -n, this brings performance back in line with the old heap based implementation.
2022-03-09bftw: Bring back the LRU listTavian Barnes
2022-01-18bftw: Use a dynamic array for the cacheTavian Barnes
Since commit 69a5227 ("eval: Raise RLIMIT_NOFILE if possible"), bfs can pass a large nopenfd (e.g. 512K) to bftw() by default. This resulted in a large up-front allocation even for small trees. Change it to grow on demand, lowering the footprint for small searches.
2022-01-18util: New close() wrappers to check for EBADF and preserve errnoTavian Barnes
2021-03-10bftw: Fix bftw_type() for broken links and BFS_STAT_FOLLOWTavian Barnes
This fixes link target coloring for broken links with -L.
2021-02-05Update copyright datesTavian Barnes
2021-01-29bftw: Share the fd between the cache and open bfs_dirTavian Barnes
This avoids many dup()s. On Linux, we can completely avoid needing to dup() directory fds. On non-Linux, we only dup() when there are unexplored subdirectories.
2021-01-28dir: New DIR* facadeTavian Barnes
2021-01-28bftw: Get rid of bftw_readerTavian Barnes
2021-01-28bftw: Avoid allocating when handling ENAMETOOLONGTavian Barnes
2021-01-28bftw: Allow for NULL base when recovering from EMFILETavian Barnes
2020-11-12Include what I useTavian Barnes
Thanks to https://github.com/include-what-you-use/include-what-you-use
2020-11-04Enable -Wsign-compare to catch bugs like 726d7801Tavian Barnes
2020-10-13util: New BFS_FLEX_SIZEOF() macro for more precise flexible array allocationsTavian Barnes
See http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_282.htm for all the fun behind this.
2020-09-20bftw: Fix bftw_cached_stat() with BFS_STAT_TRYFOLLOWTavian Barnes
2020-09-18stat: Rename bfs_stat_flag to _flagsTavian Barnes
Flags enums should be plural.
2020-09-18Don't call stat() just to determine symbolic lengthsTavian Barnes
The new bftw_cached_stat() helper gets us stat info if we already have it, but doesn't call stat() if we don't. In that case we just take a guess for the initial length to readlinkat(). This lets us avoid stat() entirely in many cases for -lname and -printf %l.
2020-07-29bftw: Make some flag names more explicitTavian Barnes
2020-07-29bftw: Rename bftw_typeflag to bftw_type, and make it not a bitmaskTavian Barnes
2020-06-16Implement exponential deepening searchTavian Barnes
2020-06-12bftw: Factor out some of the iterative deepening harnessTavian Barnes
2020-06-12bftw: Only do another level of deepening if there are unexplored directoriesTavian Barnes
This makes -S ids about 20% faster on a checkout of the Linux kernel.
2020-06-12bftw: Make iterative deepening actually do depth-first searchTavian Barnes
bftw_stream() was always pushing to the end of the queue, resulting in breadth-first behaviour even when BFTW_DFS was set. This made iterative deepening a "worst of both worlds" with the same memory use as BFS, but much slower due to re-traversals. Fix it by re-using bftw_batch_{start,finish} from bftw_batch().
2020-03-21Implement -s flag from FreeBSD find to sort resultsTavian Barnes
2020-03-20bftw: Use a two-star approach to the bftw_queue linked listTavian Barnes
2019-11-01bftw: Avoid shadowing a variableTavian Barnes
2019-08-29mtab: Rename maybe_mount to might_be_mountTavian Barnes
2019-07-04Make -mount and -xdev do different thingsTavian Barnes
POSIX now says -mount should skip the whole mount point, while -xdev should only skip its descendents. C.f. http://austingroupbugs.net/view.php?id=1133 C.f. https://savannah.gnu.org/bugs/?42318 C.f. https://savannah.gnu.org/bugs/?54745
2019-07-04bftw: Track the root bftw_file, not just the pathTavian Barnes
2019-07-03bftw: Use a flags enum rather than two bools for bftw_release_*()Tavian Barnes
2019-06-27bftw: Remove a dead assignmentTavian Barnes
2019-06-25bftw: Only rebuild the part of the path that changesTavian Barnes
This is a re-introduction of 998ba6f, which was reverted by the introduction of bftw_reader in 68ae5d0. It's particularly relevant for depth-first searches now that we queue each file before visiting it.
2019-06-25bftw: Queue individual files in depth-first modeTavian Barnes
This makes the order be truly depth-first.
2019-06-25bftw: Don't store bftw_file in bftw_readerTavian Barnes
2019-06-25bftw: Remove BFTW_SKIP_SIBLINGSTavian Barnes
It's not used by bfs, and it's difficult to support in all search strategies.
2019-06-25bftw: Rename bftw_dir to bftw_fileTavian Barnes
2019-06-25bftw: Don't store trailing slashes in bftw_dir namesTavian Barnes
2019-06-25util: Filter out . and .. in xreaddir()Tavian Barnes
2019-05-29Implement an iterative deepening mode (-ids)Tavian Barnes
2019-05-28Implement a depth-first mode (-dfs)Tavian Barnes
2019-05-28bftw: Visit multiple roots breadth-firstTavian Barnes
This makes `bfs a b` treat `a` and `b` as siblings.
2019-05-28bftw: Refactor the implementation a bitTavian Barnes
2019-05-23bftw: Take dir->{dev,ino} from the right stat bufferTavian Barnes
I don't think this can cause any observable bugs, but it's still wrong.
2019-05-05bftw: Pass a const struct BFTW * to the callbackTavian Barnes
2019-05-04bftw: Add a caching stat() API to struct BFTWTavian Barnes
2019-05-04stat: Unify the flags argumentsTavian Barnes
2019-04-15Release 1.41.4Tavian Barnes
2019-03-06bftw: Work around d_type being wrong for bind mounts on LinuxTavian Barnes
C.f. https://savannah.gnu.org/bugs/?54913 C.f. https://lkml.org/lkml/2019/2/11/2027 Fixes https://github.com/tavianator/bfs/issues/37
2019-03-06bftw: Switch from taking separate parameters to a parameters structTavian Barnes
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-23 15:06:05 +0000