/****************************************************************************
* bfs *
* Copyright (C) 2015-2017 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_dir: A directory that has been encountered during the
* traversal. They have reference-counted links to their parents in the
* directory tree.
*
* - struct bftw_cache: Holds bftw_dir'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_dir's left to explore. Implemented as
* a simple circular buffer.
*
* - struct bftw_state: Represents the current state of the traversal, allowing
* bftw() to be factored into various helper functions.
*/
#include "bftw.h"
#include "dstring.h"
#include "util.h"
#include <assert.h>
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
/**
* A directory.
*/
struct bftw_dir {
/** The parent directory, if any. */
struct bftw_dir *parent;
/** This directory's depth in the walk. */
size_t depth;
/** Reference count. */
size_t refcount;
/** Index in the bftw_cache priority queue. */
size_t heap_index;
/** An open file descriptor to this directory, or -1. */
int fd;
/** The device number, for cycle detection. */
dev_t dev;
/** The inode number, for cycle detection. */
ino_t ino;
/** The offset of this directory in the full path. */
size_t nameoff;
/** The length of the directory's name. */
size_t namelen;
/** The directory's name. */
char name[];
};
/**
* A cache of open directories.
*/
struct bftw_cache {
/** A min-heap of open directories. */
struct bftw_dir **heap;
/** Current heap size. */
size_t size;
/** Maximum heap size. */
size_t capacity;
};
/** Initialize a cache. */
static int bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
cache->heap = malloc(capacity*sizeof(*cache->heap));
if (!cache->heap) {
return -1;
}
cache->size = 0;
cache->capacity = capacity;
return 0;
}
/** Destroy a cache. */
static void bftw_cache_destroy(struct bftw_cache *cache) {
assert(cache->size == 0);
free(cache->heap);
}
/** Check if two heap entries are in heap order. */
static bool bftw_heap_check(const struct bftw_dir *parent, const struct bftw_dir *child) {
if (parent->depth > child->depth) {
return true;
} else if (parent->depth < child->depth) {
return false;
} else {
return parent->refcount <= child->refcount;
}
}
/** Move a bftw_dir to a particular place in the heap. */
static void bftw_heap_move(struct bftw_cache *cache, struct bftw_dir *dir, size_t i) {
cache->heap[i] = dir;
dir->heap_index = i;
}
/** Bubble an entry up the heap. */
static void bftw_heap_bubble_up(struct bftw_cache *cache, struct bftw_dir *dir) {
size_t i = dir->heap_index;
while (i > 0) {
size_t pi = (i - 1)/2;
struct bftw_dir *parent = cache->heap[pi];
if (bftw_heap_check(parent, dir)) {
break;
}
bftw_heap_move