summaryrefslogtreecommitdiffstats
path: root/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* 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
|
* Release 1.01.0Tavian Barnes2017-04-241-1/+1
|
* Move bftw_typeflag converters to util.cTavian Barnes2017-04-081-108/+2
|
* bftw: Only rebuild the part of the path that changesTavian Barnes2017-03-221-37/+50
| | | | | | | | | | | | | | Quadratic complexity is still possible for directory structures like root -- a -- a -- a -- a ... | +- b -- b -- b -- b ... But for most realistic directory structures, bfs should now spend less time building paths. (Of course if you print every path, overall complexity is quadratic anyway.)
* bftw: Fix quadratic reference counting complexityTavian Barnes2017-03-201-8/+15
| | | | | | | | | | | | | dircache_entry refcounts used to count every single descendant, resulting in n refcount updates to create/delete an entry at depth n, and thus O(n^2) complexity overall for deep directory structures. Fix it by only counting direct children instead. The cache eviction policy is changed to prefer shallower entries in all cases, attempting to save at least some of the benefit of the previous accounting scheme. Unfortunately, the average number of traversed components for openat() calls still went up by ~20%, but the performance in practice is roughly unchanged in my tests.
* Color link targets for -lsTavian Barnes2017-03-161-19/+1
| | | | Fixes #18.
* bftw: Make the nameoff of "///" point to "/"Tavian Barnes2017-02-091-0/+3
| | | | This simplifies a few things such as -name handling for ///.
* bftw: Add the DIR* to bftw_stateTavian Barnes2017-02-091-15/+39
| | | | Can't forget to close it that way.
* Add support for -x?type with multiple typesTavian Barnes2017-02-081-30/+26
| | | | This functionality is already part of GNU findutils git.
* bftw: Add mising closedir() to error pathTavian Barnes2017-02-071-0/+1
|
* bftw: Plug a leak if dirqueue_push() failsTavian Barnes2017-02-061-16/+28
| | | | | | | | | | If bftw_add() succeeds but dirqueue_push() fails, we need to clean up the just-added dircache_entry. Otherwise it will leak, and we'll also fail the cache->size == 0 assertion. Fix it by extracting the dircache-related parts of bftw_pop() into a new helper function bftw_gc(), and call it from bftw_pop() as well as the bftw_push() failure path.
* bftw: Compute nameoff correctly for the root in BFTW_DEPTH modeTavian Barnes2017-02-051-1/+5
|
* Implement -printf/-fprintfTavian Barnes2017-02-051-0/+1
| | | | | Based on a patch by Fangrui Song <i@maskray.me>. Closes #16.
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 12:57:18 +0000