summaryrefslogtreecommitdiffstats
path: root/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* 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.
* Implement -regex, -iregex, and -regextype/-ETavian Barnes2016-12-181-1/+4
|
* bftw: Clean up the dirqueue implementation a bitTavian Barnes2016-12-171-38/+34
|
* Move portability code into util.hTavian Barnes2016-12-041-2/+2
|
* bftw: Infer the flags in ftwbuf_stat()Tavian Barnes2016-11-231-5/+5
|
* bftw: Make a defensive copy of the ftwbufTavian Barnes2016-11-211-1/+4
| | | | | The callback may modify the ftwbuf, but we check it after the callback (for typeflag and statbuf). Have them mutate a copy instead.
* bftw: Always initialize dircache_entry::{dev,ino}Tavian Barnes2016-11-211-6/+7
| | | | | If stat() fails, they won't get filled in otherwise. Then cycle detection would have read uninitialized values.
* bftw: Make bftw_flags more similar to fts() options.Tavian Barnes2016-11-211-5/+9
|
* Check for readdir() errors everywhere.Tavian Barnes2016-11-141-14/+2
|
* bftw: Keep trailing slashes on the root in BFTW_DEPTH mode.Tavian Barnes2016-11-131-6/+16
|
* bftw: Don't fail just because we couldn't open/read a directory.Tavian Barnes2016-11-031-3/+3
| | | | | | | With BFTW_RECOVER set, we're not supposed to fail just because a single measly directory couldn't be handled. But using state.error as scratch space made us fail in this case. The end result is that #7 resurfaced, so fix it again.
* Implement -ignore_readdir_race.Tavian Barnes2016-10-241-1/+4
|
* bftw: Add support for some exotic file types, where available.Tavian Barnes2016-10-021-1/+59
|
* bftw: Handle errors from readdir().Tavian Barnes2016-10-021-25/+66
|
* bftw: Fix do/to typo in a comment.Tavian Barnes2016-09-101-1/+1
|
* bftw: Initialize typeflag to BFTW_UNKNOWN.Tavian Barnes2016-08-241-2/+1
| | | | It was totally broken on filesystems that spit out DT_UNKNOWN.
* dstring: Clean up the API a bit.Tavian Barnes2016-05-221-1/+4
|
* bftw: Use realloc() to grow the dirqueue.Tavian Barnes2016-05-171-13/+11
|
* bftw: Remove some debugging counters that were left in accidentally.Tavian Barnes2016-05-171-10/+0
|
* dstring: Split out the dynamic string logic.Tavian Barnes2016-04-131-68/+25
|
* bftw: Update at_flags when not following a broken symbolic link.Tavian Barnes2016-02-231-1/+2
|
* bftw: Plug a leak when the root is not a directory.Tavian Barnes2016-02-231-1/+6
|
* bftw: Use the currently open directory as at_fd in BFTW_CHILD mode.Tavian Barnes2016-02-221-2/+5
|
* bftw: Use O_CLOEXEC.Tavian Barnes2016-02-211-3/+3
|
* bftw: Don't store the terminating '\0' in dircache_entry names.Tavian Barnes2016-02-211-2/+1
|
* bftw: Use a better cache eviction policy.Tavian Barnes2016-02-211-113/+186
| | | | | | Instead of simple LRU, we now evict the open entry with the lowest refcount. This reduces the average number of components passed to openat() by a significant margin, and speeds bfs up by about ~5%.
* bftw: Shrink the LRU before finding the parent.Tavian Barnes2016-02-201-10/+6
| | | | Otherwise we might close the found parent.
* bftw: Clean up dirqueue implementation a bit.Tavian Barnes2016-02-191-20/+28
|
* bftw: Don't keep DIR*'s around.Tavian Barnes2016-02-191-40/+75
| | | | | | | | | | | | | | | DIR*'s were being kept around so dirfd(dir) could be passed to future openat() calls. But DIR*'s are big, holding a cache of filenames etc. read by readdir(). Instead, store the raw fd and dup() it to open a DIR* with fdopendir(). This way we can call dirclose() as soon as possible, while still keeping an open fd. Ideally there would be a way to closedir() without invoking close() on the underlying fd, but this is a good approximation. Reduces memory footprint by around 64% in a large directory tree.
* bftw: Use a circular buffer to implement the dirqueue.Tavian Barnes2016-02-171-46/+37
|
* Implement -mount/-xdev.Tavian Barnes2016-02-141-2/+11
|
* Fix -name handling when the root has trailing slashes.Tavian Barnes2016-02-131-2/+18
|
* Follow links if appropriate in predicates.Tavian Barnes2016-02-131-5/+3
|
* Implement -L/-follow.Tavian Barnes2016-02-091-22/+66
|
* bftw: Don't give up when following a broken symlink.Tavian Barnes2016-02-061-1/+9
|
* Implement -P and -H.Tavian Barnes2016-02-041-4/+14
|
* Don't use typedefs to avoid struct/enum tags.Tavian Barnes2016-02-041-66/+62
|
* bftw: Add missing #include.Tavian Barnes2016-01-301-0/+1
|
* bftw: Fix fd leak if fdopendir() fails.Tavian Barnes2016-01-301-1/+5
|
* Optimize -maxdepth in -depth mode.Tavian Barnes2015-09-261-14/+1
|
* bftw() interface improvements:Tavian Barnes2015-09-261-52/+38
| | | | | | - Use enums instead of ints where it makes sense - Move the file path inside struct BFTW - Expose a fd and relative path for *at() calls
* Add -depth support.Tavian Barnes2015-09-081-41/+186
| | | | | | | The resulting order is fairly weird, as files are still returned in breadth-first order, but directories are returned in a backwards order based on when their reference counts drop to zero. But it's good enough for -delete support.