/****************************************************************************
* bfs *
* Copyright (C) 2015-2022 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: An LRU list of bftw_file's with open file descriptors,
* used for openat() to minimize the amount of path re-traversals.
*
* - struct bftw_queue: The queue of bftw_file's left to explore. Implemented
* as a simple circular buffer.
*
* - struct bftw_state: Represents the current state of the traversal, allowing
* various helper functions to take fewer parameters.
*/
#include "bftw.h"
#include "dir.h"
#include "darray.h"
#include "dstring.h"
#include "mtab.h"
#include "stat.h"
#include "trie.h"
#include "util.h"
#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
/**
* A file.
*/
struct bftw_file {
/** The parent directory, if any. */
struct bftw_file *parent;
/** The root under which this file was found. */
struct bftw_file *