summaryrefslogtreecommitdiffstats
path: root/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* Implement exponential deepening searchTavian Barnes2020-06-161-12/+61
|
* bftw: Factor out some of the iterative deepening harnessTavian Barnes2020-06-121-39/+65
|
* bftw: Only do another level of deepening if there are unexplored directoriesTavian Barnes2020-06-121-3/+4
| | | | This makes -S ids about 20% faster on a checkout of the Linux kernel.
* bftw: Make iterative deepening actually do depth-first searchTavian Barnes2020-06-121-15/+21
| | | | | | | | | 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().
* Implement -s flag from FreeBSD find to sort resultsTavian Barnes2020-03-211-3/+80
|
* bftw: Use a two-star approach to the bftw_queue linked listTavian Barnes2020-03-201-58/+28
|
* bftw: Avoid shadowing a variableTavian Barnes2019-11-011-5/+2
|
* mtab: Rename maybe_mount to might_be_mountTavian Barnes2019-08-291-1/+1
|
* Make -mount and -xdev do different thingsTavian Barnes2019-07-041-14/+25
| | | | | | | | | 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
* bftw: Track the root bftw_file, not just the pathTavian Barnes2019-07-041-8/+7
|
* bftw: Use a flags enum rather than two bools for bftw_release_*()Tavian Barnes2019-07-031-24/+33
|
* bftw: Remove a dead assignmentTavian Barnes2019-06-271-1/+0
|
* bftw: Only rebuild the part of the path that changesTavian Barnes2019-06-251-24/+42
| | | | | | 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.
* bftw: Queue individual files in depth-first modeTavian Barnes2019-06-251-79/+150
| | | | This makes the order be truly depth-first.
* bftw: Don't store bftw_file in bftw_readerTavian Barnes2019-06-251-69/+72
|
* bftw: Remove BFTW_SKIP_SIBLINGSTavian Barnes2019-06-251-24/+11
| | | | | It's not used by bfs, and it's difficult to support in all search strategies.
* bftw: Rename bftw_dir to bftw_fileTavian Barnes2019-06-251-214/+213
|
* bftw: Don't store trailing slashes in bftw_dir namesTavian Barnes2019-06-251-27/+23
|
* util: Filter out . and .. in xreaddir()Tavian Barnes2019-06-251-3/+0
|
* Implement an iterative deepening mode (-ids)Tavian Barnes2019-05-291-0/+132
|
* Implement a depth-first mode (-dfs)Tavian Barnes2019-05-281-10/+113
|
* bftw: Visit multiple roots breadth-firstTavian Barnes2019-05-281-19/+25
| | | | This makes `bfs a b` treat `a` and `b` as siblings.
* bftw: Refactor the implementation a bitTavian Barnes2019-05-281-218/+180
|
* bftw: Take dir->{dev,ino} from the right stat bufferTavian Barnes2019-05-231-1/+1
| | | | I don't think this can cause any observable bugs, but it's still wrong.
* bftw: Pass a const struct BFTW * to the callbackTavian Barnes2019-05-051-30/+31
|
* bftw: Add a caching stat() API to struct BFTWTavian Barnes2019-05-041-20/+75
|
* stat: Unify the flags argumentsTavian Barnes2019-05-041-4/+4
|
* Release 1.41.4Tavian Barnes2019-04-151-1/+1
|
* bftw: Work around d_type being wrong for bind mounts on LinuxTavian Barnes2019-03-061-19/+52
| | | | | | 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
* bftw: Switch from taking separate parameters to a parameters structTavian Barnes2019-03-061-13/+13
|
* bftw: Move bftw_typeflag conversion out of utilTavian Barnes2018-12-171-2/+99
| | | | Turns out incomplete enum types are a GNU C extension.
* Update copyright datesTavian Barnes2018-09-241-1/+1
|
* bftw: Use bftw_action as the return type when applicableTavian Barnes2018-06-251-6/+8
|
* bftw: Introduce bftw_reader typeTavian Barnes2018-06-231-367/+336
|
* bftw: Replace the circular buffer queue with a linked listTavian Barnes2018-04-071-91/+39
| | | | The performance is within 1% with much simpler code.
* bftw: Open-code the "."/".." checksTavian Barnes2018-02-011-3/+4
| | | | | | GCC doesn't (yet) produce very fast code for strcmp() against constant strings (see https://gcc.gnu.org/PR78809), so hand-coding the comparison manually helps significantly.
* bftw: Fix the heap implementationTavian Barnes2018-02-011-1/+21
| | | | | | | | | | There were two problems: - bubble_down() would always bubble the entry all the way down the heap, instead of stopping at the appropriate place - remove() may need to bubble the replacement entry *up* the heap, if it came from a different subtree
* stat: New wrapper around the stat() familyTavian Barnes2018-01-081-14/+13
| | | | | This lets bfs transparently support the new statx() system call on Linux, giving it access to file birth times.
* bftw: Rename 'last' to 'previous'Tavian Barnes2018-01-061-11/+11
|
* Avoid multiple extra stat()s of broken symlinks for -xtypeTavian Barnes2017-08-221-1/+1
|
* Unify broken symlink handlingTavian Barnes2017-08-121-16/+6
| | | | | | | | | Rather than open-code the fallback logic for broken symlinks everywhere it's needed, introduce a new xfstatat() utility function that performs the fallback automatically. Using xfstatat() consistently fixes a few bugs, including cases where broken symlinks are given as arguments to predicates like -samefile.
* bftw: Assert that the queue is empty when freeing itTavian Barnes2017-08-101-0/+1
|
* util: Define O_DIRECTORY to 0 if it's not already definedTavian Barnes2017-07-291-5/+1
|
* Re-license under the BSD Zero Clause LicenseTavian Barnes2017-07-271-10/+15
|
* Handle ENOTDIR the same as ENOENTTavian Barnes2017-07-091-1/+1
| | | | | | For a/b/c, ENOTDIR is returned instead of ENOENT if a or b are not directories. Handle this uniformly when detecting broken symlinks, readdir races, etc.
* bftw: Rename and refactor the internalsTavian Barnes2017-07-091-235/+257
|
* bftw: Fix ENAMETOOLONG handling when the root is closedTavian Barnes2017-07-081-2/+7
| | | | | The root has depth == 0, but we still need to include it in the components array.
* bftw: Recover from ENAMETOOLONGTavian Barnes2017-07-081-23/+99
| | | | | | | | | | | | | | | | | | | | | | | | It is always possible to force a breadth-first traversal to encounter ENAMETOOLONG, regardless of the dircache eviction policy. As a concrete example, consider this directory structure: ./1/{NAME_MAX}/{NAME_MAX}/{NAME_MAX}/... (longer than {PATH_MAX}) ./2/{NAME_MAX}/{NAME_MAX}/{NAME_MAX}/... ./3/{NAME_MAX}/{NAME_MAX}/{NAME_MAX}/... ... (more than RLIMIT_NOFILE directories under .) Eventually, the next file to be processed will not have any parents in the cache, as the cache can only hold RLIMIT_NOFILE entries. Then the whole path must be traversed from ., which will exceed {PATH_MAX} bytes. Work around this by performing a component-by-component traversal manually when we see ENAMETOOLONG. This is required by POSIX: > The find utility shall be able to descend to arbitrary depths in a file > hierarchy and shall not fail due to path length limitations (unless a > path operand specified by the application exceeds {PATH_MAX} > requirements).
* Revert "bftw: Don't store the terminating '\0' in dircache_entry names."Tavian Barnes2017-07-081-1/+2
| | | | | | | This reverts commit 20860becb5a0e89ee2aaaddbb0ba1eb248552640. The terminating NUL will be useful for the upcoming per-component traversal to handle ENAMETOOLONG.
* bftw: Remove unused parameter to dircache_entry_base()Tavian Barnes2017-05-171-5/+3
|
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-06 11:07:26 +0000