/****************************************************************************
* bfs *
* Copyright (C) 2015-2019 Tavian Barnes <tavianator@tavianator.com> *
* *
* Permission to use, copy, modify, and/or distribute this software for any *
* purpose with or without fee is hereby granted. *
* *
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
****************************************************************************/
/**
* The bftw() implementation consists of the following components:
*
* - struct bftw_file: A file that has been encountered during the traversal.
* They have reference-counted links to their parents in the directory tree.
*
* - struct bftw_cache: Holds bftw_file's with open file descriptors, used for
* openat() to minimize the amount of path re-traversals that need to happen.
* Currently implemented as a priority queue based on depth and reference
* count.
*
* - struct bftw_queue: The queue of bftw_file's left to explore. Implemented
* as a simple circular buffer.
*
* - struct bftw_reader: A reader object that simplifies reading directories and
* reporting errors.
*
* - struct bftw_state: Represents the current state of the traversal, allowing
* various helper functions to take fewer parameters.