/*********************************************************************
* bfs *
* Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com> *
* *
* This program is free software. It comes without any warranty, to *
* the extent permitted by applicable law. You can redistribute it *
* and/or modify it under the terms of the Do What The Fuck You Want *
* To Public License, Version 2, as published by Sam Hocevar. See *
* the COPYING file or http://www.wtfpl.net/ for more details. *
*********************************************************************/
/**
* 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(cache, parent, i);
i = pi