Fast tree walk

walk.c

/* Traverse a folder recursively, save all regular files to a slice and print
the final slice.

The slice structure is heavily inspired from Go. The main differences are: 1) its
memory needs to be freed, 2) the len() and cap() functions retun a size_t, not
an int.

The walk is optimized by using the `d_type` field from the `dirent` structure.
It works on *BSD and Linux but might not work on other systems.
*/

/* For PATH_MAX. Adapt this for non-Linux hosts. */
#include <linux/limits.h>

/* For DT_* constants. */
#define _DEFAULT_SOURCE 1

#include <dirent.h>
#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>


typedef struct {
	char (*array)[PATH_MAX];
	size_t cap;
} _slice;

#define SLICE_ELEMSZ PATH_MAX * sizeof (char)

typedef struct {
	_slice *sub;
	size_t begin;
	size_t end;
} slice;

size_t cap(slice s) {
	return s.sub->cap - s.begin;
}

size_t len(slice s) {
	return s.end - s.begin;
}

char *val(slice s, size_t i) {
	if (i >= len(s)) {
		errx(1, "Index %zu > slice length %zu\n", i, cap(s));
	}
	return s.sub->array[s.begin + i];
}

slice reslice(slice s, size_t begin, size_t end) {
	if (begin > end || begin >= cap(s) || end >= cap(s)) {
		errx(1, "Slice bound out of range");
		return s;
	}
	s.begin = begin;
	s.end = end;
	return s;
}

slice make(size_t len, size_t cap) {
	slice s;
	s.sub = malloc(sizeof (_slice));
	if (s.sub == NULL) {
		errx(1, "Allocation error");
	}
	if (cap < len) {
		errx(1, "len larger than cap in make\n.");
	}
	if (cap == 0) {
		s.sub->array = NULL;
	} else {
		s.sub->array = calloc(cap, SLICE_ELEMSZ);
		if (s.sub->array == NULL) {
			errx(1, "Allocation error");
		}
	}
	s.begin = 0;
	s.end = len;
	s.sub->cap = cap;
	return s;
}

/* Type-specific element copy. WARNING: Caller should check if `pos` is within
bounds. */
void _valcopy(slice s, size_t pos, char elem[PATH_MAX]) {
	strncpy(s.sub->array[pos], elem, PATH_MAX);
	s.sub->array[pos][PATH_MAX - 1] = '\0';
}

slice append(slice s, char elem[PATH_MAX]) {
	if (cap(s) == 0) {
		s.sub->cap = 1;
		s.sub->array = calloc(1, SLICE_ELEMSZ);
		if (s.sub->array == NULL) {
			errx(1, "Allocation error");
		}
	} else if (len(s) == cap(s)) {
		s.sub->cap *= 2;
		s.sub->array = realloc(s.sub->array, s.sub->cap * SLICE_ELEMSZ);
		if (s.sub->array == NULL) {
			errx(1, "Allocation error");
		}
	}
	_valcopy(s, len(s), elem);

	s.end++;
	return s;
}

/* The source and destination may overlap. */
size_t copy(slice dst, slice src) {
	size_t minlen = len(dst);
	if (len(src) < minlen) {
		minlen = len(src);
	}

	/* We need to handle overlapping memory differently if src is after dst in
	memory. */
	if (dst.sub == src.sub && dst.begin > src.begin) {
		size_t i;
		for (i = 0; i < minlen; i++) {
			_valcopy(dst, dst.begin + minlen - 1 - i, src.sub->array[src.begin + minlen - 1 - i]);
		}
	} else if (dst.sub != src.sub || dst.begin < src.begin) {
		size_t i;
		for (i = 0; i < minlen; i++) {
			_valcopy(dst, dst.begin + i, src.sub->array[src.begin + i]);
		}
	}

	return minlen;
}

/* WARNING: Only destroy slices that were created with `make`. */
void destroy(slice s) {
	if (s.sub->array != NULL) {
		free(s.sub->array);
		s.sub->array = NULL;
	}
	free(s.sub);
}

slice fast_walk(char *root, slice names) {
	struct dirent *dent;
	DIR *dir;
	size_t rootlen = strlen(root);
	if (rootlen >= PATH_MAX - 1) {
		warn("Path too long: %s", root);
		return names;
	}

	if (!(dir = opendir(root))) {
		warn("Cannot open %s", root);
		return names;
	}

	char fn[PATH_MAX];
	strcpy(fn, root);
	fn[rootlen++] = '/';

	errno = 0;
	while ((dent = readdir(dir))) {
		if (!strcmp(dent->d_name, ".") || !strcmp(dent->d_name, "..")) {
			continue;
		}

		if (dent->d_type == DT_DIR) {
			strncpy(fn + rootlen, dent->d_name, PATH_MAX - rootlen);
			names = fast_walk(fn, names);
		} else if (dent->d_type == DT_REG) {
			strncpy(fn + rootlen, dent->d_name, PATH_MAX - rootlen);
			names = append(names, fn);
		}
	}

	if (dir) {
		closedir(dir);
	}

	return names;
}

int main(int argc, char **argv) {
	if (argc < 2) {
		puts("I need a folder parameter.");
		return 0;
	}

	slice names = make(0, 1024);
	names = fast_walk(argv[1], names);

	size_t i;
	for (i = 0; i < len(names); i++) {
		printf("%s\n", val(names, i));
	}

	destroy(names);
	return 0;
}