// Copyright © Tavian Barnes <tavianator@tavianator.com>
// SPDX-License-Identifier: 0BSD
/**
* 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: A linked list of bftw_file's left to explore.
*
* - struct bftw_state: Represents the current state of the traversal, allowing
* various helper functions to take fewer parameters.
*/
#include "bftw.h"
#include "bfstd.h"
#include "config.h"
#include "dir.h"
#include "dstring.h"
#include "mtab.h"
#include "stat.h"
#include "trie.h"
#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.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 *root;
/** The next file in the queue, if any. */
struct bftw_file *next;
/** The previous file in the LRU list. */
struct bftw_file *lru_prev;
/** The next file in the LRU list. */
struct bftw_file *lru_next;
/** This file's depth in the walk. */
size_t depth;
/** Reference count. */
size_t refcount;
/** An open descriptor to this file, or -1. */
int fd;
/** This file's type, if known. */
enum bfs_type type;
/** The device number, for cycle detection. */
dev_t dev;
/** The inode number, for cycle detection. */
ino_t ino;
/** The offset of this file in the full path. */
size_t nameoff;
/** The length of the file's name. */
size_t namelen;
/** The file's name. */
char name[];
};
/**
* A cache of open directories.
*/
struct bftw_cache {
/** The head o