Do any POSIX functions or glibc extensions implement a breadth-first file tree walk?

Question

I am writing a daemon that utilizes inotify to monitor file access and it is critical that I don't miss anything on a recursive search. I found this interesting idea and have begun to implement it.

ftw() and ftw64() do not use a breadth-first algorithm, its more "pre-order". nftw() gives me the option of depth-first, but I'm worried about races in upper leaves.

I'm hoping that I'm missing something, perhaps a GNU extension? Or am I just looking at implementing my own with type safe call backs (something I'd really rather not do) ?

Or, is my understanding of the advantages of breadth-first over depth-first erroneous for this type of application?

Answer 1

Looking at the spec for 'nftw()', the FTW_DEPTH flag does a post-order (depth first) traversal, visiting the sub-directories before visiting the directory node.

I don't think any of the standard algorithms do a breadth-first search.

Presumably, you should write a bfftw() based on the nftw() interface. Note that you have to queue the items to be visited recursively (directories) while doing the scan.