xref: /dports/ports-mgmt/parfetch-overlay/parfetch-0.1.0/libias/mkbuild.c

#if !__MKBUILD_CONFIG_H__
#if MKBUILD
/*-
 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
 *
 * Copyright (c) 2021 Tobias Kortkamp <tobik@FreeBSD.org>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#if defined(__CYGWIN__) || defined(__linux__) || defined(__MINT__)
# define _GNU_SOURCE
# define _DEFAULT_SOURCE
#endif

#define MKBUILD_WHICH 1
#include <sys/param.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/utsname.h>
#include <sys/wait.h>
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <libgen.h>
#include <spawn.h>
#include <stdarg.h>
#include <stdbool.h>
#define _WITH_GETLINE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#ifndef nitems
#define	nitems(x) (sizeof((x)) / sizeof((x)[0]))
#endif

#ifdef PATH_MAX
#define MKBUILD_BUFSZ PATH_MAX
#else
#define MKBUILD_BUFSZ 4096
#endif

#define MKBUILD_ARRAY_MAX 128
#define MKBUILD_FIELD_MAX 32

extern char **environ;

enum LTOType {
	LTO_DISABLED,
	LTO_FULL,
	LTO_THIN,
};

enum SpecMode {
	SPEC_NONE,
	SPEC_BIN,
	SPEC_BUNDLE,
	SPEC_DEFAULT_FEATURES,
	SPEC_GEN,
	SPEC_IF,
	SPEC_INSTALL_DATA,
	SPEC_INSTALL_MAN,
	SPEC_NINJA,
	SPEC_PKG_CONFIG,
	SPEC_TESTS,
	SPEC_TOOL,
};

struct Array {
	void *buf[MKBUILD_ARRAY_MAX];
	size_t len;
};

struct SpecFile {
	char *name;
	char *obj;
	char *src;
};

struct SpecVar {
	char *name;
	struct Array *words;
};

struct Spec {
	struct Array *defaults;
	struct Array *install;
	struct Array *testbins;
	struct Array *files;
	struct Array *vars;
	enum SpecMode mode;
	const char *name;
	const char *generator;
};

struct Toolchain {
	enum LTOType lto;
	struct Array *ar;
	struct Array *cc;
};

struct Mkbuild {
	struct Toolchain toolchain;
	const char *arg0;
	struct Array *args;
	struct Array *features;
	struct Array *pkg_config_modules;
	struct Array *system_features;
	bool auto_lto;
	bool try_lto;
	const char *ninja;
	const char *pkg_config;
	const char *mkbuild_src;
	const char *srcdir;
	const char *builddir;
	FILE *config_h;
	FILE *build_ninja;
	FILE *build_ninja_spec;
	FILE *info;
	FILE *log;
};

static const char *default_gcc_cflags[] = {
	"-O2",
	"-g",
	"-W",
	"-Wall",
	"-Wextra",
	"-Wmissing-prototypes",
	"-Wstrict-prototypes",
	"-Wwrite-strings",
	"-Wno-unused-parameter",
};

static const char *default_gcc_ldflags[] = {};

static const char *tests[] = {
	"__progname",
	"arc4random",
	"b64_ntop",
	"b64_ntop_ldadd",
	"bsd_qsort_r",
	"capsicum",
	"crypt",
	"crypt_ldadd",
	"endian_h",
	"err",
	"execinfo",
	"execinfo_ldadd",
	"explicit_bzero",
	"fts",
	"getexecname",
	"getprogname",
	"gnu_qsort_r",
	"INFTIM",
	"lib_socket",
	"lib_socket_ldadd",
	"memmem",
	"memrchr",
	"memset_s",
	"mkfifoat",
	"mknodat",
	"osbyteorder_h",
	"PATH_MAX",
	"pledge",
	"program_invocation_short_name",
	"readpassphrase",
	"reallocarray",
	"recallocarray",
	"seccomp_filter",
	"setresgid",
	"setresuid",
	"SOCK_NONBLOCK",
	"strlcat",
	"strlcpy",
	"strndup",
	"strnlen",
	"strnstr",
	"strsep",
	"strtonum",
	"sys_byteorder_h",
	"sys_endian_h",
	"sys_mkdev_h",
	"sys_queue",
	"sys_sysmacros_h",
	"sys_tree",
	"unveil",
	"WAIT_ANY",
};

static struct {
	const char *name;
	const char *prefix;
	const char *ldadd[2];
} tests_flags[] = {
	{ "b64_ntop_ldadd", "b64_ntop", { "-lresolv" } },
	{ "crypt_ldadd", "crypt", { "-lcrypt" } },
	{ "execinfo_ldadd", "execinfo", { "-lexecinfo", "-lelf" } },
	{ "lib_socket_ldadd",  "lib_socket", { "-lsocket", "-lnsl" } },
};

static const char *mkbuild_configure_rules = ""
"rule mkbuild-check\n"
"  command = if $CC -DTEST_$var=1 -o $out.bin $in $ldadd >$out.log 2>&1 && $out.bin >>$out.log 2>&1; then echo '#define HAVE_$var 1' >$out; else echo '#define HAVE_$var 0' >$out; fi; rm -f $out.bin\n"
"  description = $name\n"
"rule mkbuild-config\n"
"  command = cat $in >$out\n"
"  description = done.\n"
"";

static const char *mkbuild_pkgconf_rules = ""
"rule mkbuild-pkgconf-cflags\n"
"  command = (printf 'CFLAGS_$name = '; if $PKG_CONFIG $name; then $PKG_CONFIG --cflags $name; else PKG_CONFIG_PATH=\"$builddir\" $PKG_CONFIG --cflags $name; fi) > $out\n"
"  description = $name cflags\n"
"rule mkbuild-pkgconf-ldadd\n"
"  command = (printf 'LDADD_$name = '; if $PKG_CONFIG $name; then $PKG_CONFIG --libs $name; else PKG_CONFIG_PATH=\"$builddir\" $PKG_CONFIG --libs $name; fi) > $out\n"
"  description = $name ldadd\n"
"rule mkbuild-pkgconf-ldadd-static\n"
"  command = (printf 'LDADD_static_$name = '; if $PKG_CONFIG $name; then $PKG_CONFIG --static --libs $name; else PKG_CONFIG_PATH=\"$builddir\" $PKG_CONFIG --static --libs $name; fi) > $out\n"
"  description = $name ldadd static\n"
"rule mkbuild-pkgconf-config\n"
"  command = cat $in >$out\n"
"  description = done.\n"
"";

#ifdef __FreeBSD__
// Provide pkg-config files for base libraries as a fallback

static const char *libcrypto_pc = ""
"prefix=/usr\n"
"libdir=${prefix}/lib\n"
"includedir=${prefix}/include\n"
"Description: libcrypto\n"
"Version: 1.1.1k\n"
"Name: libcrypto\n"
"Libs: -L${libdir} -lcrypto\n"
"Cflags: -I${includedir}\n"
"";

static const char *libssl_pc = ""
"prefix=/usr\n"
"libdir=${prefix}/lib\n"
"includedir=${prefix}/include\n"
"Description: libssl\n"
"Version: 1.1.1k\n"
"Name: libssl\n"
"Requires.private: libcrypto\n"
"Libs: -L${libdir} -lssl\n"
"Cflags: -I${includedir}\n"
"";

static const char *openssl_pc= ""
"prefix=/usr\n"
"libdir=${prefix}/lib\n"
"includedir=${prefix}/include\n"
"Description: OpenSSL\n"
"Version: 1.1.1k\n"
"Name: openssl\n"
"Requires: libcrypto libssl\n"
"";
#endif

static const char *mkbuild_rules = ""
#ifdef __APPLE__
"LD_START_GROUP = \n"
"LD_END_GROUP = \n"
#else
"LD_START_GROUP = -Wl,--start-group\n"
"LD_END_GROUP = -Wl,--end-group\n"
#endif
"rule configure\n"
"  generator = true\n"
"  command = cd $srcdir && ./configure $configure_args\n"
"  description = reconfiguring...\n"
"rule cc\n"
"  depfile = $out.d\n"
"  deps = gcc\n"
"  command = $CC -std=$CSTD $CFLAGS $CPPFLAGS -MD -MF $out.d -I$builddir -I$subdir -c -o $out $in\n"
"  description = CC $name\n"
"rule bundle\n"
"  command = rm -f $out && $AR rcs $out $in\n"
"  description = BUNDLE $name\n"
"rule gen\n"
"  command = $generator $in >$out\n"
"  description = GEN $name\n"
"  generator = false\n"
"rule bin\n"
"  command = $CC $LDFLAGS -o $out $LD_START_GROUP $in $LDADD $LD_END_GROUP\n"
"  description = BIN $name\n"
"rule install-program\n"
"  command = $INSTALL_PROGRAM $in $out\n"
"  description = INSTALL-PROGRAM $name\n"
"rule install-data\n"
"  command = $INSTALL_DATA $in $out\n"
"  description = INSTALL-DATA $name\n"
"rule install-man\n"
"  command = $INSTALL_MAN $in $out\n"
"  description = INSTALL-MAN $name\n"
"rule mkbuild-test\n"
"  command = cd $srcdir && $in && touch $in.stamp \n"
"  description = TEST $name\n"
"";

static struct {
	const char *key;
	const char *value;
} mkbuild_settings[] = {
	{ "AR", "ar" },
	{ "AWK", "awk" },
	{ "BUILDDIR", NULL },
	{ "SRCDIR", NULL },
	{ "CC", "cc" },
	{ "CSTD", "c99" },
	{ "CFLAGS", "" },
	{ "CPPFLAGS", "" },
	{ "LDADD", "" },
	{ "LDADD_B64_NTOP", "" },
	{ "LDADD_CRYPT", "" },
	{ "LDADD_EXECINFO", "" },
	{ "LDADD_LIB_SOCKET", "" },
	{ "LDFLAGS", "" },
	{ "FEATURES", "" },
	{ "LTO", "1" },
	{ "NINJA", NULL },
	{ "DESTDIR", "" },
	{ "PREFIX", "/usr/local" },
	{ "BINDIR", "$PREFIX/bin" },
	{ "SHAREDIR", "$PREFIX/share" },
	{ "SBINDIR", "$PREFIX/sbin" },
	{ "INCLUDEDIR", "$PREFIX/include" },
	{ "LIBDIR", "$PREFIX/lib" },
	{ "MANDIR", "$PREFIX/share/man" },
	{ "INSTALL", "install" },
	{ "INSTALL_PROGRAM", "$INSTALL -m 0555" },
	{ "INSTALL_LIB", "$INSTALL -m 0444" },
	{ "INSTALL_MAN", "$INSTALL -m 0444" },
	{ "INSTALL_DATA", "$INSTALL -m 0444" },
};

struct Mkbuild this;

/* Prototypes */
static struct Array *array_new(void);
static struct Array *array_append(struct Array *, const void *);
struct Array *array_join(struct Array *, struct Array *);
static struct Array *array_joinv(struct Array *, void **, const size_t);
static void *array_get(struct Array *, size_t);
static size_t array_len(struct Array *);
static void array_truncate(struct Array *);
static char *str_printf(const char *, ...);
static bool str_endswith(const char *, const char *);
static bool str_startswith(const char *, const char *);
static char *str_toupper(const char *);
static char *escape_arg(const char *, bool);
static bool has_feature(const char *);
static bool has_system_feature(const char *);
static void configure(void);
static void system_features(void);
static void pkg_config(void);
static void define(const char *, const char *, const char *);
static void info(const char *, ...);
static void debug(const char *, ...);
static bool ltotoolchain(void);
static enum LTOType test_ltotoolchain(struct Array *, struct Array *);
static bool test_ltotoolchain_helper(enum LTOType, struct Array *, struct Array *);
static void spec_write(void);
static void spec_build(struct Spec *, const char *, struct Array *, struct Array *);
static void spec_cc(struct Spec *);
static void spec_var(struct SpecVar *, bool);
static void spec_flush(struct Spec *);
static bool which(const char *);
static int run(struct Array *);

struct Array *
array_new(void)
{
	return calloc(1, sizeof(struct Array));
}

struct Array *
array_append(struct Array *array, const void *val)
{
	assert(array->len < MKBUILD_ARRAY_MAX);
	array->buf[array->len++] = (void *)val;
	return array;
}

struct Array *
array_join(struct Array *array, struct Array *other)
{
	return array_joinv(array, other->buf, other->len);
}

struct Array *
array_joinv(struct Array *array, void **vals, const size_t n)
{
	for (size_t i = 0; i < n; i++) {
		assert(array->len < MKBUILD_ARRAY_MAX);
		array->buf[array->len++] = (void *)vals[i];
	}
	return array;
}

void *
array_get(struct Array *array, size_t i)
{
	assert(i < array->len);
	return array->buf[i];
}

size_t
array_len(struct Array *array)
{
	return array->len;
}

void
array_truncate(struct Array *array)
{
	array->len = 0;
}

char *
str_printf(const char *format, ...)
{
	va_list ap;
	va_start(ap, format);
	char *buf = malloc(MKBUILD_BUFSZ);
	vsnprintf(buf, MKBUILD_BUFSZ, format, ap);
	va_end(ap);
	return buf;
}

bool
str_endswith(const char *s, const char *end)
{
	size_t len = strlen(end);
	if (strlen(s) < len) {
		return false;
	}
	return strncmp(s + strlen(s) - len, end, len) == 0;
}

bool
str_startswith(const char *s, const char *start)
{
	size_t len = strlen(start);
	if (strlen(s) < len) {
		return false;
	}
	return strncmp(s, start, len) == 0;
}

struct Array *
str_split(const char *s, const char *sep)
{
	struct Array *array = array_new();
	size_t seplen = strlen(sep);
	const char *buf = strdup(s);
	if (seplen > 0) {
		char *ptr;
		while (*buf && (ptr = strstr(buf, sep))) {
			*ptr = 0;
			array_append(array, buf);
			buf = ptr + seplen;
		}
	}
	array_append(array, buf);
	return array;
}

char *
str_toupper(const char *s)
{
	char *buf = strdup(s);
	size_t len = strlen(buf);
	for (size_t i = 0; i < len; i++) {
		buf[i] = toupper((unsigned char)buf[i]);
	}
	return buf;
}

char *
escape_arg(const char *s, bool sh)
{
	char *buf = NULL;
	size_t len = 0;

	FILE *f = open_memstream(&buf, &len);
	if (f == NULL) {
		perror("open_memstream");
		exit(1);
	}

	if (sh) {
		fputc('\'', f);
	}
	size_t slen = strlen(s);
	for (size_t i = 0; i < slen; i++) {
		switch (s[i]) {
		case '$':
		case ':':
		case ' ':
		case '\n':
			fputc('$', f);
			break;
		case '\\':
		case '\'':
			if (sh) {
				fputc('\\', f);
			}
			break;
		default:
			break;
		}
		fputc(s[i], f);
	}
	if (sh) {
		fputc('\'', f);
	}

	fclose(f);

	return buf;
}

bool
has_feature(const char *feature)
{
	const char *notfeature;
	if (str_startswith(feature, "!")) {
		notfeature = feature + 1;
	} else {
		notfeature = str_printf("!%s", feature);
	}
	bool has_feature = false;
	for (size_t i = 0; i < array_len(this.features); i++) {
		const char *value = array_get(this.features, i);
		if (strcmp(value, feature) == 0) {
			has_feature = true;
		} else if (strcmp(value, notfeature) == 0) {
			has_feature = false;
		}
	}
	return has_feature;
}

bool
has_system_feature(const char *feature)
{
	debug("==> checking system feature %s", feature);
	const char *path = str_printf("%s/.mkbuild/test-%s", this.builddir, feature);
	FILE *f = fopen(path, "r");
	if (f == NULL) {
		debug("unable to read %s", path);
		return false;
	}
	if (fseek(f, -2, SEEK_END) == -1) {
		fclose(f);
		debug("unable to seek %s: %s", path, strerror(errno));
		return false;
	}

	int c = fgetc(f);
	if (c == EOF) {
		debug("EOF for %s: %s", path, strerror(errno));
		fclose(f);
		return false;
	}
	fclose(f);

	bool available = c == (unsigned char)'1';
	if (available) {
		debug("%s available", feature);
		return true;
	} else {
		debug("%s not available", feature);
		return false;
	}
}

void
define(const char *prefix, const char *name, const char *value)
{
	fputs("#define ", this.config_h);
	fputs(prefix, this.config_h);
	fputs(name, this.config_h);
	fputs(" ", this.config_h);
	fputs(value, this.config_h);
	fputs("\n", this.config_h);
}

void
info(const char *format, ...)
{
	va_list ap;
	va_start(ap, format);
	vfprintf(this.info, format, ap);
	va_end(ap);
	fputs("\n", this.info);
	fflush(this.info);
	if (this.log) {
		fputs("=> ", this.log);
		va_start(ap, format);
		vfprintf(this.log, format, ap);
		va_end(ap);
		fputs("\n", this.log);
		fflush(this.log);
	}
}

void
debug(const char *format, ...)
{
	if (this.log) {
		va_list ap;
		va_start(ap, format);
		vfprintf(this.log, format, ap);
		va_end(ap);
		fputs("\n", this.log);
		fflush(this.log);
	}
}

int
run(struct Array *argv)
{
	if (this.log) {
		fputs("==> Executing '", this.log);
		for (size_t i = 0; i < array_len(argv); i++) {
			fputs(array_get(argv, i), this.log);
			if (i == array_len(argv) - 1) {
				fputs("'\n", this.log);
			} else {
				fputc(' ', this.log);
			}
		}
	}
	struct Array *args = array_join(array_new(), argv);
	array_append(args, NULL);

	posix_spawn_file_actions_t actions;
	posix_spawn_file_actions_init(&actions);
	posix_spawn_file_actions_addclose(&actions, STDIN_FILENO);
	if (this.log) {
		posix_spawn_file_actions_adddup2(&actions, fileno(this.log), STDERR_FILENO);
		posix_spawn_file_actions_adddup2(&actions, fileno(this.log), STDOUT_FILENO);
	} else {
		posix_spawn_file_actions_addclose(&actions, STDERR_FILENO);
		posix_spawn_file_actions_addclose(&actions, STDOUT_FILENO);
	}

	pid_t pid;
	if (posix_spawnp(&pid, array_get(args, 0), &actions, NULL, (char **)args->buf, environ) != 0) {
		debug("[FAILED: %s]", strerror(errno));
		return 1;
	}

	int status = 1;
	if (waitpid(pid, &status, 0) < 0) {
		debug("[FAILED: %s]", strerror(errno));
		return 1;
	} else if (WIFEXITED(status)) {
		debug("[status: %d]", WEXITSTATUS(status));
		return WEXITSTATUS(status);
	} else {
		debug("[FAILED]");
		return 1;
	}
}

enum LTOType
test_ltotoolchain(struct Array *cc, struct Array *ar)
{
	if (test_ltotoolchain_helper(LTO_THIN, cc, ar)) {
		return LTO_THIN;
	}

	if (test_ltotoolchain_helper(LTO_FULL, cc, ar)) {
		return LTO_FULL;
	}

	return LTO_DISABLED;
}

static struct Array *
ar_candidate(const char *path, const char *tool, struct Array *candidate)
{
	if (!strchr(path, '/')) {
		if (str_startswith(path, tool)) {
			char *buf = str_printf("%s%s", array_get(candidate, 0), path + strlen(tool));
			if (which(buf)) {
				return array_append(array_new(), buf);
			}
		}
		return NULL;
	} else {
		char *tmp = strdup(path);
		char *base = basename(tmp);
		char *dir = dirname(tmp);
		if (str_startswith(base, tool)) {
			char *buf = str_printf("%s/%s%s", dir, array_get(candidate, 0), base + strlen(tool));
			if (which(buf)) {
				free(tmp);
				return array_append(array_new(), buf);
			}
		}
		free(tmp);
		return NULL;
	}
}

bool
ltotoolchain()
{
	debug("=> LTO toolchain test");

	struct Array *cc = this.toolchain.cc;
	struct Array *ar = this.toolchain.ar;
	enum LTOType type;

	if (LTO_DISABLED != (type = test_ltotoolchain(cc, ar))) {
		goto found;
	}

	if (!this.auto_lto) {
		return false;
	}

	if ((ar = ar_candidate(array_get(cc, 0), "cc", array_append(array_new(), "llvm-ar"))) &&
	    (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
		goto found;
	}

	if ((ar = ar_candidate(array_get(cc, 0), "cc", array_append(array_new(), "gcc-ar"))) &&
	    (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
		goto found;
	}

	if ((ar = ar_candidate(array_get(cc, 0), "clang", array_append(array_new(), "llvm-ar"))) &&
	    (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
		goto found;
	}

	if ((ar = ar_candidate(array_get(cc, 0), "gcc", array_append(array_new(), "gcc-ar"))) &&
	    (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
		goto found;
	}

	return false;

found:
	this.toolchain.lto = type;
	this.toolchain.ar = ar;
	this.toolchain.cc = cc;

	return true;
}

void
system_features()
{
	info("checking system features...");

	FILE *config_ninja = fopen("config.ninja", "w");
	if (config_ninja == NULL) {
		fprintf(stderr, "%s: cannot open %s/config.ninja: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
		exit(1);
	}

	fprintf(config_ninja, "mkbuild = %s\n", this.mkbuild_src);
	fprintf(config_ninja, "builddir = %s/.mkbuild\n", this.builddir);
	fputs(mkbuild_configure_rules, config_ninja);
	fprintf(config_ninja, "CC = %s\n", (const char *)array_get(this.toolchain.cc, 0));
	for (size_t i = 0; i < nitems(tests); i++) {
		fprintf(config_ninja, "build $builddir/test-$name: mkbuild-check $mkbuild\n  name = %s\n  var = %s\n",
			tests[i], str_toupper(tests[i]));
		fputs("  ldadd = ", config_ninja);
		for (size_t j = 0; j < nitems(tests_flags); j++) {
			if (strcmp(tests[i], tests_flags[j].name) == 0) {
				for (size_t k = 0; k < nitems(tests_flags[j].ldadd) && tests_flags[j].ldadd[k]; k++) {
					fputs(tests_flags[j].ldadd[k], config_ninja);
					fputs(" ", config_ninja);
				}
				break;
			}
		}
		fputs("\n", config_ninja);
	}

	fputs("build $builddir/system_features.h: mkbuild-config", config_ninja);
	for (size_t i = 0; i < nitems(tests); i++) {
		fputs(" $builddir/test-", config_ninja);
		fputs(tests[i], config_ninja);
	}
	fputs("\n", config_ninja);
	fclose(config_ninja);

	configure();
}

void
configure()
{
	setenv("NINJA_STATUS", "", true);
	setenv("SAMUFLAGS", "", true);

	posix_spawn_file_actions_t actions;
	posix_spawn_file_actions_init(&actions);
	posix_spawn_file_actions_addclose(&actions, STDIN_FILENO);

	const char *args[] = { "ninja", "-f", "config.ninja", NULL };
	if (this.ninja) {
		args[0] = this.ninja;
	}
	pid_t pid;
	debug("==> Executing '%s -f config.ninja'", args[0]);
	if (posix_spawnp(&pid, args[0], &actions, NULL, (char **)args, environ) != 0) {
		if (!this.ninja && (errno == EACCES || errno == ENOENT || errno == EEXIST)) {
			debug("==> ninja failed to run: %s", strerror(errno));
			args[0] = "samu";
			debug("==> Executing '%s -f config.ninja'", args[0]);
			if (posix_spawnp(&pid, args[0], &actions, NULL, (char **)args, environ) != 0) {
				goto error;
			}
		} else {
			goto error;
		}
	}

	int status = 1;
	if (waitpid(pid, &status, 0) >= 0 && WIFEXITED(status)) {
		debug("[status: %d]", WEXITSTATUS(status));
		if (WEXITSTATUS(status) == 0) {
			return;
		} else {
			fprintf(stderr, "config.ninja failed: status %d\n", WEXITSTATUS(status));
			exit(1);
		}
	}

error:
	fprintf(stderr, "'%s -f config.ninja' failed: %s\n", args[0], strerror(errno));
	exit(1);
}

void
pkg_config()
{
	if (array_len(this.pkg_config_modules) == 0) {
		FILE *f = fopen("pkgconf.ninja", "w");
		if (f == NULL) {
			fprintf(stderr, "cannot open %s/.mkbuild/pkgconf.ninja: %s\n", this.builddir, strerror(errno));
			exit(1);
		}
		fclose(f);
		return;
	}

	info("checking for modules...");

	FILE *config_ninja = fopen("config.ninja", "w");
	if (config_ninja == NULL) {
		fprintf(stderr, "%s: cannot open %s/config.ninja: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
		exit(1);
	}

#ifdef __FreeBSD__
	FILE *libcrypto = fopen("libcrypto.pc", "w");
	if (libcrypto == NULL) {
		fprintf(stderr, "%s: cannot open %s/libcrypto.pc: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
		exit(1);
	}
	fputs(libcrypto_pc, libcrypto);
	fclose(libcrypto);

	FILE *libssl = fopen("libssl.pc", "w");
	if (libssl == NULL) {
		fprintf(stderr, "%s: cannot open %s/libssl.pc: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
		exit(1);
	}
	fputs(libssl_pc, libssl);
	fclose(libssl);

	FILE *openssl = fopen("openssl.pc", "w");
	if (openssl == NULL) {
		fprintf(stderr, "%s: cannot open %s/openssl.pc: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
		exit(1);
	}
	fputs(openssl_pc, openssl);
	fclose(openssl);
#endif

	fprintf(config_ninja, "builddir = %s/.mkbuild\n", this.builddir);
	fprintf(config_ninja, "PKG_CONFIG = %s\n", this.pkg_config);
	fputs(mkbuild_pkgconf_rules, config_ninja);
	for (size_t i = 0; i < array_len(this.pkg_config_modules); i++) {
		const char *module = array_get(this.pkg_config_modules, i);
		fprintf(config_ninja, "build $builddir/pkgconf-cflags-$name: mkbuild-pkgconf-cflags\n");
		fprintf(config_ninja, "  name = %s\n", module);
		fprintf(config_ninja, "build $builddir/pkgconf-ldadd-$name: mkbuild-pkgconf-ldadd\n");
		fprintf(config_ninja, "  name = %s\n", module);
		fprintf(config_ninja, "build $builddir/pkgconf-ldadd-static-$name: mkbuild-pkgconf-ldadd-static\n");
		fprintf(config_ninja, "  name = %s\n", module);
	}
	fputs("build $builddir/pkgconf.ninja: mkbuild-pkgconf-config", config_ninja);
	for (size_t i = 0; i < array_len(this.pkg_config_modules); i++) {
		const char *module = array_get(this.pkg_config_modules, i);
		fprintf(config_ninja, " $builddir/pkgconf-cflags-%s $builddir/pkgconf-ldadd-%s $builddir/pkgconf-ldadd-static-%s",
			module, module, module);
	}
	fputs("\n", config_ninja);
	fclose(config_ninja);

	configure();
}

bool
test_ltotoolchain_helper(enum LTOType lto, struct Array *cc, struct Array *ar)
{
	bool ok = false;
	const char *cppflag = "-DTEST_SANITY=1";
	const char *ltoarg = NULL;
	switch (lto) {
	case LTO_DISABLED:
		break;
	case LTO_FULL:
		ltoarg = "-flto";
		break;
	case LTO_THIN:
		ltoarg = "-flto=thin";
		break;
	}

	struct Array *test0_args = array_join(array_new(), cc);
	array_joinv(test0_args, (void **)default_gcc_cflags, nitems(default_gcc_cflags));
	if (ltoarg) {
		array_append(test0_args, ltoarg);
	}
	const char *src_file = this.mkbuild_src;
	const char *object_file = "test-lto.o";
	array_append(test0_args, "-c");
	array_append(test0_args, "-o");
	array_append(test0_args, object_file);
	array_append(test0_args, cppflag);
	array_append(test0_args, src_file);

	struct Array *test1_args = NULL;
	const char *archive = "libtest-lto.a";
	test1_args = array_join(array_new(), ar);
	array_append(test1_args, "rcs");
	array_append(test1_args, archive);
	array_append(test1_args, object_file);

	struct Array *test2_args = array_join(array_new(), cc);
	array_joinv(test2_args, (void **)default_gcc_ldflags, nitems(default_gcc_ldflags));
	if (ltoarg) {
		array_append(test2_args, ltoarg);
	}
	array_append(test2_args, "-o");
	array_append(test2_args, "test-lto");
	array_append(test2_args, archive);

	if (run(test0_args) != 0) {
		goto fail;
	}
	if (run(test1_args) != 0) {
		goto fail;
	}
	if (run(test2_args) != 0) {
		goto fail;
	}

	if (run(array_append(array_new(), "./test-lto")) == 0) {
		ok = true;
	}

fail:
	unlink(object_file);
	unlink(archive);
	unlink("test-lto");

	return ok;
}

void
spec_build(struct Spec *spec, const char *rule, struct Array *outputs, struct Array *inputs)
{
	fputs("build", this.build_ninja);
	if (outputs) {
		for (size_t i = 0; i < array_len(outputs); i++) {
			fputs(" ", this.build_ninja);
			fputs(array_get(outputs, i), this.build_ninja);
		}
	}
	fprintf(this.build_ninja, ": %s", rule);
	if (inputs) {
		for (size_t i = 0; i < array_len(inputs); i++) {
			fputs(" ", this.build_ninja);
			fputs(array_get(inputs, i), this.build_ninja);
		}
	}
	fputs("\n", this.build_ninja);

	if (strcmp(rule, "phony") != 0) {
		for (size_t i = 0; i < array_len(spec->vars); i++) {
			spec_var(array_get(spec->vars, i), false);
		}
	}
}

void
spec_cc(struct Spec *spec)
{
	for (size_t i = 0; i < array_len(spec->files); i++) {
		struct SpecFile *f = array_get(spec->files, i);
		if (str_endswith(f->src, ".c")) {
			spec_build(spec, "cc", array_append(array_new(), f->obj), array_append(array_new(), f->src));
			spec_var(&(struct SpecVar){"name", array_append(array_new(), f->name)}, false);
		}
	}
}

void
spec_var(struct SpecVar *var, bool global)
{
	if (!global) {
		fputs("  ", this.build_ninja);
	}
	fprintf(this.build_ninja, "%s =", var->name);
	for (size_t i = 0; i < array_len(var->words); i++) {
		fputs(" ", this.build_ninja);
		fputs(array_get(var->words, i), this.build_ninja);
	}
	fputs("\n", this.build_ninja);
}

void
spec_flush(struct Spec *spec)
{
	switch (spec->mode) {
	case SPEC_NONE:
	case SPEC_NINJA:
		break;
	case SPEC_BIN:
	case SPEC_TOOL: {
		struct Array *inputs = array_new();
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			array_append(inputs, f->obj);
		}
		const char *subdir = ".bin";
		if (spec->mode == SPEC_TOOL) {
			subdir = ".tool";
		}
		struct Array *outputs = array_append(array_new(), str_printf("$builddir/%s/%s", subdir, spec->name));
		spec_build(spec, "bin", outputs, inputs);
		spec_var(&(struct SpecVar){"name", array_append(array_new(), spec->name)}, false);
		spec_build(spec, "phony", array_append(array_new(), spec->name), outputs);
		spec_cc(spec);
		if (spec->mode == SPEC_BIN) {
			array_append(spec->defaults, strdup(spec->name));
			const char *target = str_printf("$DESTDIR$BINDIR/%s", spec->name);
			array_append(spec->install, target);
			spec_build(spec, "install-program", array_append(array_new(), target), outputs);
			spec_var(&(struct SpecVar){"name", array_append(array_new(), str_printf("%s $DESTDIR$BINDIR", spec->name))}, false);
		}
		break;
	} case SPEC_BUNDLE: {
		struct Array *outputs = array_append(array_new(), str_printf("$builddir/%s", spec->name));
		struct Array *inputs = array_new();
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			array_append(inputs, f->obj);
		}
		spec_build(spec, "bundle", outputs, inputs);
		spec_var(&(struct SpecVar){"name", array_append(array_new(), spec->name)}, false);
		spec_build(spec, "phony", array_append(array_new(), spec->name), outputs);
		array_append(spec->defaults, strdup(spec->name));
		spec_cc(spec);
		break;
	} case SPEC_DEFAULT_FEATURES:
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			struct Array *features = array_new();
			array_append(features, f->name);
			array_join(features, this.features);
			this.features = features;
		}
		break;
	case SPEC_IF:
		if (has_feature(spec->name)) {
			for (size_t i = 0; i < array_len(spec->vars); i++) {
				spec_var(array_get(spec->vars, i), true);
			}
		}
		break;
	case SPEC_GEN: {
		struct Array *inputs = array_new();
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			array_append(inputs, f->src);
		}
		array_append(inputs, "|");
		array_append(inputs, spec->generator);
		spec_build(spec, "gen", array_append(array_new(), spec->name), inputs);
		spec_var(&(struct SpecVar){"name", array_append(array_new(), spec->name)}, false);
		if (str_endswith(spec->generator, ".awk")) {
			spec_var(&(struct SpecVar){"generator", array_append(array_append(array_append(array_new(), "$AWK"), "-f"), spec->generator)}, false);
		} else {
			spec_var(&(struct SpecVar){"generator", array_append(array_new(), spec->generator)}, false);
		}
		break;
	} case SPEC_INSTALL_DATA:
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			const char *dest = str_printf("$DESTDIR$SHAREDIR/%s/%s", spec->name, f->name);
			spec_build(spec, "install-data", array_append(array_new(), dest), array_append(array_new(), f->src));
			spec_var(&(struct SpecVar){"name", array_append(array_new(), str_printf("%s %s", f->name, dest))}, false);
			array_append(spec->install, dest);
		}
		break;
	case SPEC_INSTALL_MAN:
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			if (strlen(f->src) > 2 &&
			    f->src[strlen(f->src) - 2] == '.' &&
			    isdigit((unsigned char)f->src[strlen(f->src) - 1])) {
				const char category = f->src[strlen(f->src) - 1];
				char *base = basename(strdup(f->src));
				const char *dest = str_printf("$DESTDIR$MANDIR/man%c/%s", category, base);
				spec_build(spec, "install-man", array_append(array_new(), dest), array_append(array_new(), f->src));
				spec_var(&(struct SpecVar){"name", array_append(array_new(), str_printf("%s %s", f->name, dest))}, false);
				array_append(spec->install, dest);
			}
		}
		break;
	case SPEC_PKG_CONFIG:
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			array_append(this.pkg_config_modules, f->name);
		}
		break;
	case SPEC_TESTS:
		for (size_t i = 0; i < array_len(spec->files); i++) {
			struct SpecFile *f = array_get(spec->files, i);
			if (strlen(f->obj) > 2) {
				const char *testbin = strndup(f->obj, strlen(f->obj) - 2);
				if (strlen(testbin) > strlen("$builddir/")) {
					spec_build(spec, "bin", array_append(array_new(), testbin), array_append(array_append(array_new(), f->obj), spec->name));
					const char *testbinrel = testbin + strlen("$builddir/");
					spec_var(&(struct SpecVar){"name", array_append(array_new(), testbinrel)}, false);
					const char *stamp = str_printf("%s.stamp", testbin);
					spec_build(spec, "mkbuild-test", array_append(array_new(), stamp), array_append(array_new(), testbin));
					spec_var(&(struct SpecVar){"name", array_append(array_new(), testbinrel)}, false);
					spec_build(spec, "phony", array_append(array_new(), testbinrel), array_append(array_new(), stamp));
					array_append(spec->testbins, stamp);
				}
			}
		}
		spec_cc(spec);
		break;
	}

	spec->mode = SPEC_NONE;
	spec->name = "";
	spec->generator = "";

	array_truncate(spec->files);
	array_truncate(spec->vars);
}

void
spec_write()
{
	fprintf(this.build_ninja, "builddir = %s\nsrcdir = %s\nsubdir = $srcdir\nmkbuild_src = %s\n%s", this.builddir, this.srcdir, this.mkbuild_src, mkbuild_rules);

	struct Spec spec = {
		.defaults = array_new(),
		.install = array_new(),
		.testbins = array_new(),

		.files = array_new(),
		.vars = array_new(),
		.mode = SPEC_NONE,
		.name = "",
		.generator = "",
	};

	char *line = NULL;
	size_t linecap = 0;
	ssize_t linelen;
	size_t linecnt = 0;
	while ((linelen = getline(&line, &linecap, this.build_ninja_spec)) > 0) {
		linecnt++;
		if (linelen > 0 && line[linelen - 1] == '\n') {
			line[linelen - 1] = 0;
			linelen--;
		}

		// Tokenize into fields similar to awk
		char *$[MKBUILD_FIELD_MAX];
		for (size_t i = 0; i < MKBUILD_FIELD_MAX; i++) {
			$[i] = "";
		}
		size_t NF = 1;
		$[0] = strdup(line);
		char *token;
		char *_tok = line;
		while (NF < MKBUILD_FIELD_MAX && (token = strtok(_tok, " \t")) != NULL) {
			_tok = NULL;
			if (strcmp(token, "") != 0) {
				$[NF++] = token;
			}
		}

		if (str_startswith($[1], "#")) {
			continue;
		} else if (strcmp($[0], "") == 0) {
			continue;
		} else if (str_startswith($[0], "\t")) {
			if (spec.mode == SPEC_NINJA) {
				fprintf(this.build_ninja, "%s\n", $[0] + 1);
			} else if (strcmp($[2], "=") == 0 || strcmp($[2], "+=") == 0) {
				struct SpecVar *v = malloc(sizeof(struct SpecVar));
				v->name = strdup($[1]);
				v->words = array_new();
				if (strcmp($[2], "+=") == 0) {
					array_append(v->words, str_printf("$%s", v->name));
				}
				for (size_t i = 3; i < NF; i++) {
					array_append(v->words, strdup($[i]));
				}
				array_append(spec.vars, v);
			} else {
				struct SpecFile *f = malloc(sizeof(struct SpecFile));
				f->name = strdup($[1]);
				if (str_startswith($[1], "$builddir/") || str_startswith($[1], "$srcdir/")) {
					f->src = strdup($[1]);
					f->obj = strdup($[1]);
				} else {
					f->src = str_printf("$srcdir/%s", $[1]);
					f->obj = str_printf("$builddir/%s", $[1]);
				}
				if (str_endswith(f->obj, ".c")) {
					f->obj[strlen(f->obj) - 1] = 'o';
				}
				array_append(spec.files, f);
			}
		} else if (strcmp($[1], "default") == 0) {
			fprintf(this.build_ninja, "%s\n", $[0]);
			for (size_t i = 2; i < NF; i++) {
				array_append(spec.defaults, strdup($[i]));
			}
		} else if (strcmp($[1], "default-install") == 0) {
			for (size_t i = 2; i < NF; i++) {
				array_append(spec.install, strdup($[i]));
			}
		} else if (strcmp($[1], "include") == 0 || strcmp($[1], "subninja") == 0 || strcmp($[2], "=") == 0) {
			fprintf(this.build_ninja, "%s\n", $[0]);
		} else if (strcmp($[2], "+=") == 0) {
			fputs($[1], this.build_ninja);
			fputs(" = $", this.build_ninja);
			fputs($[1], this.build_ninja);
			for (size_t i = 3; i < NF; i++) {
				fputs(" ", this.build_ninja);
				fputs($[i], this.build_ninja);
			}
			fputs("\n", this.build_ninja);
		} else {
			spec_flush(&spec);
			if (strcmp($[1], "ninja") == 0) {
				spec.mode = SPEC_NINJA;
			} else if (strcmp($[1], "bin") == 0) {
				spec.mode = SPEC_BIN;
			} else if (strcmp($[1], "bundle") == 0) {
				spec.mode = SPEC_BUNDLE;
			} else if (strcmp($[1], "default-features") == 0) {
				spec.mode = SPEC_DEFAULT_FEATURES;
			} else if (strcmp($[1], "if") == 0) {
				spec.mode = SPEC_IF;
			} else if (strcmp($[1], "gen") == 0) {
				spec.mode = SPEC_GEN;
			} else if (strcmp($[1], "install-data") == 0) {
				spec.mode = SPEC_INSTALL_DATA;
			} else if (strcmp($[1], "install-man") == 0) {
				spec.mode = SPEC_INSTALL_MAN;
			} else if (strcmp($[1], "pkg-config") == 0) {
				spec.mode = SPEC_PKG_CONFIG;
			} else if (strcmp($[1], "tests") == 0) {
				spec.mode = SPEC_TESTS;
			} else if (strcmp($[1], "tool") == 0) {
				spec.mode = SPEC_TOOL;
			} else {
				fprintf(stderr, "unknown mode on line %zu\n", linecnt);
				exit(1);
			}

			spec.name = strdup($[2]);
			if (spec.mode == SPEC_GEN) {
				if (strcmp($[3], "") == 0) {
					fprintf(stderr, "missing generator on line %zu\n", linecnt);
					exit(1);
				} else {
					spec.generator = strdup($[3]);
				}
			}
		}
	}

	spec_flush(&spec);
	if (array_len(spec.defaults) > 0) {
		spec_build(&spec, "phony", array_append(array_new(), "all"), spec.defaults);
		fputs("default", this.build_ninja);
		for (size_t i = 0; i < array_len(spec.defaults); i++) {
			fputs(" ", this.build_ninja);
			fputs(array_get(spec.defaults, i), this.build_ninja);
		}
		fputs("\n", this.build_ninja);
	}
	if (array_len(spec.install) > 0) {
		spec_build(&spec, "phony", array_append(array_new(), "install"), spec.install);
	}
	if (array_len(spec.testbins) > 0) {
		spec_build(&spec, "phony", array_append(array_new(), "test"), spec.testbins);
	}
}

int
main(int argc, char *argv[])
{
	this.arg0 = argv[0];
	this.args = array_new();

	for (int i = 1; i < argc; i++) {
		bool valid = false;
		char *key = strdup(argv[i]);
		char *value = strstr(key, "=");
		if (value) {
			value[0] = 0;
			value++;
			bool append = false;
			if (str_endswith(key, "+")) {
				append = true;
				key[strlen(key) - 1] = 0;
			}
			for (size_t j = 0; j < nitems(mkbuild_settings); j++) {
				if (strcmp(key, mkbuild_settings[j].key) == 0) {
					valid = true;
					if (append && mkbuild_settings[j].value) {
						value = str_printf("%s %s", mkbuild_settings[j].value, escape_arg(value, false));
					} else {
						value = escape_arg(value, false);
					}
					mkbuild_settings[j].value = value;
					break;
				}
			}
		}
		if (!valid) {
			fprintf(stderr, "%s: invalid key-value: %s\n", this.arg0, argv[i]);
			return 1;
		}
	}

	this.features = array_new();
	this.pkg_config = "pkg-config";
	this.pkg_config_modules = array_new();
	this.system_features = array_new();
	this.info = stderr;
	this.log = NULL;

	this.toolchain.lto = LTO_DISABLED;
	this.auto_lto = true;
	this.try_lto = true;
	for (size_t i = 0; i < nitems(mkbuild_settings); i++) {
		const char *key = mkbuild_settings[i].key;
		const char *value = mkbuild_settings[i].value;
		if (value == NULL) {
			continue;
		} else if (strcmp(key, "AR") == 0) {
			this.toolchain.ar = str_split(value, " ");
		} else if (strcmp(key, "BUILDDIR") == 0) {
			this.builddir = strdup(value);
		} else if (strcmp(key, "FEATURES") == 0) {
			this.features = str_split(value, " ");
		} else if (strcmp(key, "LTO") == 0) {
			this.auto_lto = strcmp(value, "noauto") != 0;
			this.try_lto = strcmp(value, "0") != 0;
		} else if (strcmp(key, "NINJA") == 0) {
			this.ninja = strdup(value);
		} else if (strcmp(key, "PKG_CONFIG") == 0) {
			this.pkg_config = strdup(value);
		} else if (strcmp(key, "SRCDIR") == 0) {
			this.srcdir = strdup(value);
		} else if (strcmp(key, "CC") == 0) {
			this.toolchain.cc = str_split(value, " ");
		}
	}

	this.mkbuild_src = str_printf("%s/mkbuild.c", getcwd(NULL, 0));
	if (this.builddir == NULL) {
		this.builddir = "_build";
	}
	if (this.srcdir == NULL) {
		this.srcdir = getcwd(NULL, 0);
	} else if (chdir(this.srcdir) == -1) {
		perror("chdir");
		exit(1);
	}

	if ((this.build_ninja_spec = fopen("build.ninja.spec", "r")) == NULL) {
		fprintf(stderr, "cannot open %s/build.ninja.spec: %s\n", this.srcdir, strerror(errno));
		return 1;
	}

	// The builddir was created by the configure script that
	// compiled mkbuild. We cd into it to get a normalized
	// path via getcwd.
	if (chdir(this.builddir) == -1) {
		perror("chdir");
		exit(1);
	}
	this.builddir = getcwd(NULL, 0);
	info("builddir: %s", this.builddir);

	if ((this.config_h = fopen("config.h", "w")) == NULL) {
		fprintf(stderr, "cannot open %s/config.h: %s\n", this.builddir, strerror(errno));
		exit(1);
	}

	if ((this.build_ninja = fopen("build.ninja", "w")) == NULL) {
		fprintf(stderr, "cannot open %s/build.ninja: %s\n", this.builddir, strerror(errno));
		return 1;
	}

	// Go into $builddir/.mkbuild where we will stash
	// our temporary files.
	if (mkdir(".mkbuild", 0755) == -1 && errno != EEXIST) {
		perror("mkdir");
		exit(1);
	}
	if (chdir(".mkbuild") == -1) {
		perror("chdir");
		exit(1);
	}

	if ((this.log = fopen("config.log", "a")) == NULL) {
		fprintf(stderr, "cannot open %s/.mkbuild/config.log: %s\n", this.builddir, strerror(errno));
		return 1;
	}

	if (this.try_lto) {
		ltotoolchain();
	}
	switch (this.toolchain.lto) {
	case LTO_DISABLED:
		info("lto: disabled");
		break;
	case LTO_FULL:
		info("lto: full");
		break;
	case LTO_THIN:
		info("lto: thin");
		break;
	}
	info("ar: %s", array_get(this.toolchain.ar, 0));
	info("cc: %s", array_get(this.toolchain.cc, 0));

	system_features();
	fprintf(this.config_h, "#pragma once\n#include \"%s/.mkbuild/system_features.h\"\n", this.builddir);
	fprintf(this.config_h, "#define __MKBUILD_CONFIG_H__ 1\n#include \"%s\"\n#undef __MKBUILD_CONFIG_H__\n", this.mkbuild_src);

	if (has_system_feature("seccomp_filter")) {
		struct utsname name;
		if (uname(&name) == 0) {
			if (strcmp(name.machine, "x86_64") == 0) {
				define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_X86_64");
			} else if (strlen(name.machine) == 4 && name.machine[0] == 'i' && name.machine[2] == '8' && name.machine[3] == '6') {
				define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_I386");
			} else if (str_startswith(name.machine, "arm")) {
				define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_ARM");
			} else if (strcmp(name.machine, "aarch64") == 0) {
				define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_AARCH64");
			}
		}
	}

	for(size_t i = 0; i < nitems(mkbuild_settings); i++) {
		const char *value = mkbuild_settings[i].value;
		if (!value) {
			value = "";
		}
		fprintf(this.build_ninja, "%s = %s\n", mkbuild_settings[i].key, value);
	}
	fputs("CFLAGS =", this.build_ninja);
	for (size_t i = 0; i < nitems(default_gcc_cflags); i++) {
		fputs(" ", this.build_ninja);
		fputs(default_gcc_cflags[i], this.build_ninja);
	}
	switch (this.toolchain.lto) {
	case LTO_DISABLED:
		break;
	case LTO_FULL:
		fputs(" -flto", this.build_ninja);
		break;
	case LTO_THIN:
		fputs(" -flto=thin", this.build_ninja);
		break;
	}
	fputs(" $CFLAGS\n", this.build_ninja);
	fputs("LDFLAGS =", this.build_ninja);
	for (size_t i = 0; i < nitems(default_gcc_ldflags); i++) {
		fputs(" ", this.build_ninja);
		fputs(default_gcc_ldflags[i], this.build_ninja);
	}
	switch (this.toolchain.lto) {
	case LTO_DISABLED:
		break;
	case LTO_FULL:
		fputs(" -flto", this.build_ninja);
		break;
	case LTO_THIN:
		fputs(" -flto=thin", this.build_ninja);
		break;
	}
	fputs(" $LDFLAGS\n", this.build_ninja);
	fputs("AR =", this.build_ninja);
	for (size_t i = 0; i < array_len(this.toolchain.ar); i++) {
		fputs(" ", this.build_ninja);
		fputs(array_get(this.toolchain.ar, i), this.build_ninja);
	}
	fputs("\nCC =", this.build_ninja);
	for (size_t i = 0; i < array_len(this.toolchain.cc); i++) {
		fputs(" ", this.build_ninja);
		fputs(array_get(this.toolchain.cc, i), this.build_ninja);
	}
	fputs("\n", this.build_ninja);

	for (size_t i = 0; i < nitems(tests_flags); i++) {
		if (has_system_feature(tests_flags[i].prefix)) {
			continue;
		} else if (has_system_feature(tests_flags[i].name)) {
			fprintf(this.build_ninja, "LDADD_%s", str_toupper(tests_flags[i].prefix));
			fputs(" = ", this.build_ninja);
			for (size_t j = 0; j < nitems(tests_flags[i].ldadd) && tests_flags[i].ldadd[j]; j++) {
				fputs(tests_flags[i].ldadd[j], this.build_ninja);
				fputs(" ", this.build_ninja);
			}
			fputs("\n", this.build_ninja);
		}
	}

	fprintf(this.build_ninja, "include %s/.mkbuild/pkgconf.ninja\n", this.builddir);

	spec_write();

	fputs("build $builddir/config.h: configure $srcdir/configure $srcdir/build.ninja.spec $mkbuild_src\n", this.build_ninja);
	fputs("  configure_args =", this.build_ninja);
	for (int i = 1; i < argc; i++) {
		fputs(" ", this.build_ninja);
		fputs(escape_arg(argv[i], true), this.build_ninja);
	}
	fputs("\n", this.build_ninja);

	pkg_config();

	info("ready.");

	fclose(this.config_h);
	fclose(this.build_ninja);
	fclose(this.build_ninja_spec);
	fclose(this.info);
	fclose(this.log);

	return 0;
}
#endif /* MKBUILD */
#if MKBUILD_WHICH
// Based on: http://git.suckless.org/sbase/commit/7315b8686f3fcbf213113247bea980b0548ec66a.html
//
// MIT/X Consortium License
//
// © 2011 Connor Lane Smith <cls@lubutu.com>
// © 2011-2016 Dimitris Papastamos <sin@2f30.org>
// © 2014-2016 Laslo Hunhold <dev@frign.de>
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.
//
// Authors/contributors include:
//
// © 2011 Kamil Cholewiński <harry666t@gmail.com>
// © 2011 Rob Pilling <robpilling@gmail.com>
// © 2011 Hiltjo Posthuma <hiltjo@codemadness.org>
// © 2011 pancake <pancake@youterm.com>
// © 2011 Random832 <random832@fastmail.us>
// © 2012 William Haddon <william@haddonthethird.net>
// © 2012 Kurt H. Maier <khm@sciops.net>
// © 2012 Christoph Lohmann <20h@r-36.net>
// © 2012 David Galos <galosd83@students.rowan.edu>
// © 2012 Robert Ransom <rransom.8774@gmail.com>
// © 2013 Jakob Kramer <jakob.kramer@gmx.de>
// © 2013 Anselm R Garbe <anselm@garbe.us>
// © 2013 Truls Becken <truls.becken@gmail.com>
// © 2013 dsp <dsp@2f30.org>
// © 2013 Markus Teich <markus.teich@stusta.mhn.de>
// © 2013 Jesse Ogle <jesse.p.ogle@gmail.com>
// © 2013 Lorenzo Cogotti <miciamail@hotmail.it>
// © 2013 Federico G. Benavento <benavento@gmail.com>
// © 2013 Roberto E. Vargas Caballero <k0ga@shike2.com>
// © 2013 Christian Hesse <mail@eworm.de>
// © 2013 Markus Wichmann <nullplan@gmx.net>
// © 2014 Silvan Jegen <s.jegen@gmail.com>
// © 2014 Daniel Bainton <dpb@driftaway.org>
// © 2014 Tuukka Kataja <stuge@xor.fi>
// © 2014 Jeffrey Picard <jeff@jeffreypicard.com>
// © 2014 Evan Gates <evan.gates@gmail.com>
// © 2014 Michael Forney <mforney@mforney.org>
// © 2014 Ari Malinen <ari.malinen@gmail.com>
// © 2014 Brandon Mulcahy <brandon@jangler.info>
// © 2014 Adria Garriga <rhaps0dy@installgentoo.com>
// © 2014-2015 Greg Reagle <greg.reagle@umbc.edu>
// © 2015 Tai Chi Minh Ralph Eastwood <tcmreastwood@gmail.com>
// © 2015 Quentin Rameau <quinq@quinq.eu.org>
// © 2015 Dionysis Grigoropoulos <info@erethon.com>
// © 2015 Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
// © 2016 Mattias Andrée <maandree@kth.se>
// © 2016 Eivind Uggedal <eivind@uggedal.com>

static bool canexec(int, const char *);

bool
canexec(int fd, const char *name)
{
	struct stat st;

	if (fstatat(fd, name, &st, 0) < 0 || !S_ISREG(st.st_mode))
		return false;
	return faccessat(fd, name, X_OK, AT_EACCESS) == 0;
}

bool
which(const char *name)
{
	char *ptr, *p;
	size_t i, len;
	int dirfd;
	bool found = false;

	if (strchr(name, '/')) {
		return canexec(AT_FDCWD, name);
	}

	const char *path = getenv("PATH");
	if (!path)
		return false;

	ptr = p = strdup(path);
	len = strlen(p);
	for (i = 0; i < len + 1; i++) {
		if (ptr[i] != ':' && ptr[i] != '\0')
			continue;
		ptr[i] = '\0';
		if ((dirfd = open(p, O_RDONLY)) >= 0) {
			if (canexec(dirfd, name)) {
				found = true;
			}
			close(dirfd);
			if (found)
				break;
		}
		p = ptr + i + 1;
	}
	free(ptr);

	return found;
}
#endif /* MKBUILD_WHICH */
#if TEST_SANITY
int
main(int argc, char *argv[])
{
	return 0;
}
#endif /* TEST_SANITY */
#if TEST___PROGNAME
int
main(void)
{
	extern char *__progname;

	return !__progname;
}
#endif /* TEST___PROGNAME */
#if TEST_ARC4RANDOM
#include <stdlib.h>

int
main(void)
{
	return (arc4random() + 1) ? 0 : 1;
}
#endif /* TEST_ARC4RANDOM */
#if TEST_B64_NTOP || TEST_B64_NTOP_LDADD
#include <netinet/in.h>
#include <resolv.h>

int
main(void)
{
	const char *src = "hello world";
	char output[1024];

	return b64_ntop((const unsigned char *)src, 11, output, sizeof(output)) > 0 ? 0 : 1;
}
#endif // TEST_B64_NTOP || TEST_B64_NTOP_LDADD
#if TEST_CAPSICUM
#include <sys/capsicum.h>

int
main(void)
{
	cap_enter();
	return(0);
}
#endif /* TEST_CAPSICUM */
#if TEST_CRYPT || TEST_CRYPT_LDADD
#if defined(__linux__)
# define _GNU_SOURCE /* old glibc */
# define _DEFAULT_SOURCE /* new glibc */
#endif
#if defined(__sun)
# ifndef _XOPEN_SOURCE /* SunOS already defines */
#  define _XOPEN_SOURCE /* XPGx */
# endif
# define _XOPEN_SOURCE_EXTENDED 1 /* XPG4v2 */
# ifndef __EXTENSIONS__ /* SunOS already defines */
#  define __EXTENSIONS__ /* reallocarray, etc. */
# endif
#endif
#include <unistd.h>

int main(void)
{
	char	*v;

	v = crypt("this_is_a_key", "123455");
	return v == NULL;
}
#endif // TEST_CRYPT || TEST_CRYPT_LDADD
#if TEST_ENDIAN_H
#ifdef __linux__
# define _DEFAULT_SOURCE
#endif
#include <endian.h>

int
main(void)
{
	return !htole32(23);
}
#endif /* TEST_ENDIAN_H */
#if TEST_ERR
/*
 * Copyright (c) 2015 Ingo Schwarze <schwarze@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * 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.
 */

#include <err.h>
#include <errno.h>

int
main(void)
{
	warnx("%d. warnx", 1);
	warnc(ENOENT, "%d. warn", ENOENT);
	warn("%d. warn", 2);
	err(0, "%d. err", 3);
	errx(0, "%d. err", 3);
	errc(0, ENOENT, "%d. err", 3);
	/* NOTREACHED */
	return 1;
}
#endif /* TEST_ERR */
#if TEST_EXECINFO || TEST_EXECINFO_LDADD
#include <execinfo.h>
#include <unistd.h>

int
main(void)
{
	void *addrlist[10];
	size_t len = backtrace(addrlist, 10);
	return (backtrace_symbols_fd(addrlist, len, STDERR_FILENO) == -1);
}
#endif // TEST_EXECINFO || TEST_EXECINFO_LDADD
#if TEST_EXPLICIT_BZERO
#include <string.h>

int
main(void)
{
	char foo[10];

	explicit_bzero(foo, sizeof(foo));
	return(0);
}
#endif /* TEST_EXPLICIT_BZERO */
#if TEST_FTS
#include <stddef.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fts.h>

int
main(void)
{
	const char	*argv[2];
	FTS		*ftsp;
	FTSENT		*entry;

	argv[0] = ".";
	argv[1] = (char *)NULL;

	ftsp = fts_open((char * const *)argv,
	    FTS_PHYSICAL | FTS_NOCHDIR, NULL);

	if (ftsp == NULL)
		return 1;

	entry = fts_read(ftsp);

	if (entry == NULL)
		return 1;

	if (fts_set(ftsp, entry, FTS_SKIP) != 0)
		return 1;

	if (fts_close(ftsp) != 0)
		return 1;

	return 0;
}
#endif /* TEST_FTS */
#if TEST_GETEXECNAME
#include <stdlib.h>

int
main(void)
{
	const char * progname;

	progname = getexecname();
	return progname == NULL;
}
#endif /* TEST_GETEXECNAME */
#if TEST_GETPROGNAME
#include <stdlib.h>

int
main(void)
{
	const char * progname;

	progname = getprogname();
	return progname == NULL;
}
#endif /* TEST_GETPROGNAME */
#if TEST_INFTIM
/*
 * Linux doesn't (always?) have this.
 */

#include <poll.h>
#include <stdio.h>

int
main(void)
{
	printf("INFTIM is defined to be %ld\n", (long)INFTIM);
	return 0;
}
#endif /* TEST_INFTIM */
#if TEST_LIB_SOCKET || TEST_LIB_SOCKET_LDADD
#include <sys/socket.h>

int
main(void)
{
	int fds[2], c;

	c = socketpair(AF_UNIX, SOCK_STREAM, 0, fds);
	return c == -1;
}
#endif // TEST_LIB_SOCKET || TEST_LIB_SOCKET_LDADD
#if TEST_MEMMEM
#define _GNU_SOURCE
#include <string.h>

int
main(void)
{
	char *a = memmem("hello, world", strlen("hello, world"), "world", strlen("world"));
	return(NULL == a);
}
#endif /* TEST_MEMMEM */
#if TEST_MEMRCHR
#if defined(__linux__) || defined(__MINT__)
#define _GNU_SOURCE	/* See test-*.c what needs this. */
#endif
#include <string.h>

int
main(void)
{
	const char *buf = "abcdef";
	void *res;

	res = memrchr(buf, 'a', strlen(buf));
	return(NULL == res ? 1 : 0);
}
#endif /* TEST_MEMRCHR */
#if TEST_MEMSET_S
#include <string.h>

int main(void)
{
	char buf[10];
	memset_s(buf, 0, 'c', sizeof(buf));
	return 0;
}
#endif /* TEST_MEMSET_S */
#if TEST_MKFIFOAT
#include <sys/stat.h>
#include <fcntl.h>

int main(void) {
	mkfifoat(AT_FDCWD, "this/path/should/not/exist", 0600);
	return 0;
}
#endif /* TEST_MKFIFOAT */
#if TEST_MKNODAT
#include <sys/stat.h>
#include <fcntl.h>

int main(void) {
	mknodat(AT_FDCWD, "this/path/should/not/exist", S_IFIFO | 0600, 0);
	return 0;
}
#endif /* TEST_MKNODAT */
#if TEST_OSBYTEORDER_H
#include <libkern/OSByteOrder.h>

int
main(void)
{
	return !OSSwapHostToLittleInt32(23);
}
#endif /* TEST_OSBYTEORDER_H */
#if TEST_PATH_MAX
/*
 * POSIX allows PATH_MAX to not be defined, see
 * http://pubs.opengroup.org/onlinepubs/9699919799/functions/sysconf.html;
 * the GNU Hurd is an example of a system not having it.
 *
 * Arguably, it would be better to test sysconf(_SC_PATH_MAX),
 * but since the individual *.c files include "config.h" before
 * <limits.h>, overriding an excessive value of PATH_MAX from
 * "config.h" is impossible anyway, so for now, the simplest
 * fix is to provide a value only on systems not having any.
 * So far, we encountered no system defining PATH_MAX to an
 * impractically large value, even though POSIX explicitly
 * allows that.
 *
 * The real fix would be to replace all static buffers of size
 * PATH_MAX by dynamically allocated buffers.  But that is
 * somewhat intrusive because it touches several files and
 * because it requires changing struct mlink in mandocdb.c.
 * So i'm postponing that for now.
 */

#include <limits.h>
#include <stdio.h>

int
main(void)
{
	printf("PATH_MAX is defined to be %ld\n", (long)PATH_MAX);
	return 0;
}
#endif /* TEST_PATH_MAX */
#if TEST_PLEDGE
#include <unistd.h>

int
main(void)
{
	return !!pledge("stdio", NULL);
}
#endif /* TEST_PLEDGE */
#if TEST_PROGRAM_INVOCATION_SHORT_NAME
#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <errno.h>

int
main(void)
{

	return !program_invocation_short_name;
}
#endif /* TEST_PROGRAM_INVOCATION_SHORT_NAME */
#if TEST_BSD_QSORT_R
#define _GNU_SOURCE
#include <stdlib.h>
void (qsort_r)(void *base, size_t nmemb, size_t size, void *arg, int (*compar)(void *, const void *, const void *));

static int
int_cmp(void *arg, const void *p1, const void *p2)
{
	int left = *(const int *)p1;
	int right = *(const int *)p2;
	int *flag = arg;
	*flag = 42;
	return ((left > right) - (left < right));
}

int
main(void)
{
	int xs[] = { 3, 2, 1 };
	int flag = -1;
	qsort_r(&xs, 3, sizeof(xs[0]), &flag, int_cmp);
	return !(xs[0] == 1 && xs[1] == 2 && xs[2] == 3 && flag == 42);
}
#endif /* TEST_BSD_QSORT_R */
#if TEST_GNU_QSORT_R
#define _GNU_SOURCE
#include <stdlib.h>
void (qsort_r)(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *arg);

static int
int_cmp(const void *p1, const void *p2, void *arg)
{
	int left = *(const int *)p1;
	int right = *(const int *)p2;
	int *flag = arg;
	*flag = 42;
	return ((left > right) - (left < right));
}

int
main(void)
{
	int xs[] = { 3, 2, 1 };
	int flag = -1;
	qsort_r(&xs, 3, sizeof(xs[0]), int_cmp, &flag);
	return !(xs[0] == 1 && xs[1] == 2 && xs[2] == 3 && flag == 42);
}
#endif /* TEST_GNU_QSORT_R */
#if TEST_READPASSPHRASE
#include <stddef.h>
#include <readpassphrase.h>

int
main(void)
{
	return !!readpassphrase("prompt: ", NULL, 0, 0);
}
#endif /* TEST_READPASSPHRASE */
#if TEST_REALLOCARRAY
#ifdef __NetBSD__
# define _OPENBSD_SOURCE
#endif
#include <stdlib.h>

int
main(void)
{
	return !reallocarray(NULL, 2, 2);
}
#endif /* TEST_REALLOCARRAY */
#if TEST_RECALLOCARRAY
#include <stdlib.h>

int
main(void)
{
	return !recallocarray(NULL, 0, 2, 2);
}
#endif /* TEST_RECALLOCARRAY */
#if TEST_SANDBOX_INIT
#include <sandbox.h>

int
main(void)
{
	char	*ep;
	int	 rc;

	rc = sandbox_init(kSBXProfileNoInternet, SANDBOX_NAMED, &ep);
	if (-1 == rc)
		sandbox_free_error(ep);
	return(-1 == rc);
}
#endif /* TEST_SANDBOX_INIT */
#if TEST_SECCOMP_FILTER
#include <sys/prctl.h>
#include <linux/seccomp.h>
#include <errno.h>

int
main(void)
{

	prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, 0);
	return(EFAULT == errno ? 0 : 1);
}
#endif /* TEST_SECCOMP_FILTER */
#if TEST_SETRESGID
#define _GNU_SOURCE /* linux */
#include <sys/types.h>
#include <unistd.h>

int
main(void)
{
	return setresgid(-1, -1, -1) == -1;
}
#endif /* TEST_SETRESGID */
#if TEST_SETRESUID
#define _GNU_SOURCE /* linux */
#include <sys/types.h>
#include <unistd.h>

int
main(void)
{
	return setresuid(-1, -1, -1) == -1;
}
#endif /* TEST_SETRESUID */
#if TEST_SOCK_NONBLOCK
/*
 * Linux doesn't (always?) have this.
 */

#include <sys/socket.h>

int
main(void)
{
	int fd[2];
	socketpair(AF_UNIX, SOCK_STREAM|SOCK_NONBLOCK, 0, fd);
	return 0;
}
#endif /* TEST_SOCK_NONBLOCK */
#if TEST_STATIC
int
main(void)
{
	return 0; /* not meant to do anything */
}
#endif /* TEST_STATIC */
#if TEST_STRLCAT
#include <string.h>

int
main(void)
{
	char buf[3] = "a";
	return ! (strlcat(buf, "b", sizeof(buf)) == 2 &&
	    buf[0] == 'a' && buf[1] == 'b' && buf[2] == '\0');
}
#endif /* TEST_STRLCAT */
#if TEST_STRLCPY
#include <string.h>

int
main(void)
{
	char buf[2] = "";
	return ! (strlcpy(buf, "a", sizeof(buf)) == 1 &&
	    buf[0] == 'a' && buf[1] == '\0');
}
#endif /* TEST_STRLCPY */
#if TEST_STRNDUP
#include <string.h>

int
main(void)
{
	const char *foo = "bar";
	char *baz;

	baz = strndup(foo, 1);
	return(0 != strcmp(baz, "b"));
}
#endif /* TEST_STRNDUP */
#if TEST_STRNLEN
#include <string.h>

int
main(void)
{
	const char *foo = "bar";
	size_t sz;

	sz = strnlen(foo, 1);
	return(1 != sz);
}
#endif /* TEST_STRNLEN */
#if TEST_STRNSTR
#include <string.h>

int
main(void)
{
	const char *foo = "bar";
	return(NULL == strnstr(foo, "a", 2));
}
#endif /* TEST_STRNSTR */
#if TEST_STRSEP
#include <string.h>

int
main(void)
{
	char *foo = strdup("foo bar");
	char *token = strsep(&foo, " ");
	return !(token && strcmp(token, "foo") == 0);
}
#endif // TEST_STRSEP
#if TEST_STRTONUM
/*
 * Copyright (c) 2015 Ingo Schwarze <schwarze@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * 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.
 */
#ifdef __NetBSD__
# define _OPENBSD_SOURCE
#endif
#include <stdlib.h>

int
main(void)
{
	const char *errstr;

	if (strtonum("1", 0, 2, &errstr) != 1)
		return 1;
	if (errstr != NULL)
		return 2;
	if (strtonum("1x", 0, 2, &errstr) != 0)
		return 3;
	if (errstr == NULL)
		return 4;
	if (strtonum("2", 0, 1, &errstr) != 0)
		return 5;
	if (errstr == NULL)
		return 6;
	if (strtonum("0", 1, 2, &errstr) != 0)
		return 7;
	if (errstr == NULL)
		return 8;
	return 0;
}
#endif /* TEST_STRTONUM */
#if TEST_SYS_BYTEORDER_H
#include <sys/byteorder.h>

int
main(void)
{
	return !LE_32(23);
}
#endif /* TEST_SYS_BYTEORDER_H */
#if TEST_SYS_ENDIAN_H
#include <sys/endian.h>

int
main(void)
{
	return !htole32(23);
}
#endif /* TEST_SYS_ENDIAN_H */
#if TEST_SYS_MKDEV_H
#include <sys/types.h>
#include <sys/mkdev.h>

int
main(void)
{
	return !minor(0);
}
#endif /* TEST_SYS_MKDEV_H */
#if TEST_SYS_QUEUE
#include <sys/queue.h>
#include <stddef.h>

struct foo {
	int bar;
	TAILQ_ENTRY(foo) entries;
};

TAILQ_HEAD(fooq, foo);

int
main(void)
{
	struct fooq foo_q, bar_q;
	struct foo *p, *tmp;
	int i = 0;

	TAILQ_INIT(&foo_q);
	TAILQ_INIT(&bar_q);

	/*
	 * Use TAILQ_FOREACH_SAFE because some systems (e.g., Linux)
	 * have TAILQ_FOREACH but not the safe variant.
	 */

	TAILQ_FOREACH_SAFE(p, &foo_q, entries, tmp)
		p->bar = i++;

	/* Test for newer macros as well. */

	TAILQ_CONCAT(&foo_q, &bar_q, entries);
	return 0;
}
#endif /* TEST_SYS_QUEUE */
#if TEST_SYS_SYSMACROS_H
#include <sys/sysmacros.h>

int
main(void)
{
	return !minor(0);
}
#endif /* TEST_SYS_SYSMACROS_H */
#if TEST_SYS_TREE
#include <sys/tree.h>
#include <stdlib.h>

struct node {
	RB_ENTRY(node) entry;
	int i;
};

static int
intcmp(struct node *e1, struct node *e2)
{
	return (e1->i < e2->i ? -1 : e1->i > e2->i);
}

RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
RB_PROTOTYPE(inttree, node, entry, intcmp)
RB_GENERATE(inttree, node, entry, intcmp)

int testdata[] = {
	20, 16, 17, 13, 3, 6, 1, 8, 2, 4
};

int
main(void)
{
	size_t i;
	struct node *n;

	for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
		if ((n = malloc(sizeof(struct node))) == NULL)
			return 1;
		n->i = testdata[i];
		RB_INSERT(inttree, &head, n);
	}

	return 0;
}

#endif /* TEST_SYS_TREE */
#if TEST_UNVEIL
#include <unistd.h>

int
main(void)
{
	return -1 != unveil(NULL, NULL);
}
#endif /* TEST_UNVEIL */
#if TEST_WAIT_ANY
#include <sys/wait.h>

int
main(void)
{
	int st;

	return waitpid(WAIT_ANY, &st, WNOHANG) != -1;
}
#endif /* TEST_WAIT_ANY */

#else /* __MKBUILD_CONFIG_H__ */

#if HAVE_BSD_QSORT_R || HAVE_GNU_QSORT_R
# define HAVE_QSORT_R 1
#else
# define HAVE_QSORT_R 0
#endif

#if HAVE_B64_NTOP_LDADD
#undef HAVE_B64_NTOP
#define HAVE_B64_NTOP 1
#endif

#if HAVE_CRYPT_LDADD
#undef HAVE_CRYPT
#define HAVE_CRYPT 1
#endif

#if HAVE_EXECINFO_LDADD
#undef HAVE_EXECINFO
#define HAVE_EXECINFO 1
#endif

#if HAVE_LIB_SOCKET_LDADD
#undef HAVE_LIB_SOCKET
#define HAVE_LIB_SOCKET 1
#endif

#ifdef __cplusplus
# error "Do not use C++: this is a C application."
#endif
#if !defined(__GNUC__) || (__GNUC__ < 4)
# define __attribute__(x)
#endif
#if defined(__CYGWIN__) || defined(__linux__) || defined(__MINT__)
# define _GNU_SOURCE /* memmem, memrchr, setresuid... */
# define _DEFAULT_SOURCE /* le32toh, crypt, ... */
#endif
#if defined(__NetBSD__)
# define _OPENBSD_SOURCE /* reallocarray, etc. */
#endif
#if defined(__sun)
# ifndef _XOPEN_SOURCE /* SunOS already defines */
#  define _XOPEN_SOURCE /* XPGx */
# endif
# define _XOPEN_SOURCE_EXTENDED 1 /* XPG4v2 */
# ifndef __EXTENSIONS__ /* SunOS already defines */
#  define __EXTENSIONS__ /* reallocarray, etc. */
# endif
#endif
#if !defined(__BEGIN_DECLS)
# define __BEGIN_DECLS
#endif
#if !defined(__END_DECLS)
# define __END_DECLS
#endif

#if !HAVE_FTS || !HAVE_MEMMEM || !HAVE_MEMRCHR || !HAVE_MKFIFOAT || \
	!HAVE_MKNODAT || !HAVE_QSORT_R || !HAVE_READPASSPHRASE || !HAVE_REALLOCARRAY || \
	!HAVE_RECALLOCARRAY || !HAVE_SETRESGID || !HAVE_SETRESUID || \
	!HAVE_STRLCAT || !HAVE_STRLCPY || !HAVE_STRNDUP || !HAVE_STRNLEN || !HAVE_STRNSTR
#include <sys/types.h> /* size_t, mode_t, dev_t */
#endif

#if !HAVE_ERR
#include <stdarg.h> /* err(3) */
#endif

#if !HAVE_PATH_MAX
#define PATH_MAX 4096
#endif

#if !HAVE_WAIT_ANY
#define WAIT_ANY (-1) /* sys/wait.h */
#define WAIT_MYPGRP 0
#endif

#if !HAVE_INFTIM
#define INFTIM (-1) /* poll.h */
#endif

#if HAVE_OSBYTEORDER_H && !HAVE_ENDIAN_H && !HAVE_SYS_BYTEORDER_H && !HAVE_SYS_ENDIAN_H
/*
 * endian.h compatibility with libkern/OSByteOrder.h.
 */
#define htobe16(x) OSSwapHostToBigInt16(x)
#define htole16(x) OSSwapHostToLittleInt16(x)
#define be16toh(x) OSSwapBigToHostInt16(x)
#define le16toh(x) OSSwapLittleToHostInt16(x)
#define htobe32(x) OSSwapHostToBigInt32(x)
#define htole32(x) OSSwapHostToLittleInt32(x)
#define be32toh(x) OSSwapBigToHostInt32(x)
#define le32toh(x) OSSwapLittleToHostInt32(x)
#define htobe64(x) OSSwapHostToBigInt64(x)
#define htole64(x) OSSwapHostToLittleInt64(x)
#define be64toh(x) OSSwapBigToHostInt64(x)
#define le64toh(x) OSSwapLittleToHostInt64(x)
#endif

#if HAVE_SYS_BYTEORDER_H && !HAVE_ENDIAN_H && !HAVE_OSBYTEORDER_H && !HAVE_SYS_ENDIAN_H
/*
 * endian.h compatibility with sys/byteorder.h.
 */
#define htobe16(x) BE_16(x)
#define htole16(x) LE_16(x)
#define be16toh(x) BE_16(x)
#define le16toh(x) LE_16(x)
#define htobe32(x) BE_32(x)
#define htole32(x) LE_32(x)
#define be32toh(x) BE_32(x)
#define le32toh(x) LE_32(x)
#define htobe64(x) BE_64(x)
#define htole64(x) LE_64(x)
#define be64toh(x) BE_64(x)
#define le64toh(x) LE_64(x)
#endif

/*
 * Handle the various major()/minor() header files.
 * Use sys/mkdev.h before sys/sysmacros.h because SunOS
 * has both, where only the former works properly.
 */
#if HAVE_SYS_MKDEV_H
# define COMPAT_MAJOR_MINOR_H <sys/mkdev.h>
#elif HAVE_SYS_SYSMACROS_H
# define COMPAT_MAJOR_MINOR_H <sys/sysmacros.h>
#else
# define COMPAT_MAJOR_MINOR_H <sys/types.h>
#endif

/*
 * Make it easier to include endian.h forms.
 */
#if HAVE_ENDIAN_H
# define COMPAT_ENDIAN_H <endian.h>
#elif HAVE_SYS_ENDIAN_H
# define COMPAT_ENDIAN_H <sys/endian.h>
#elif HAVE_OSBYTEORDER_H
# define COMPAT_ENDIAN_H <libkern/OSByteOrder.h>
#elif HAVE_SYS_BYTEORDER_H
# define COMPAT_ENDIAN_H <sys/byteorder.h>
#else
# warning No suitable endian.h could be found.
# warning Please e-mail the maintainers with your OS.
# define COMPAT_ENDIAN_H <endian.h>
#endif

#if !HAVE_ERR
/*
 * Compatibility functions for err(3).
 */
extern void err(int, const char *, ...) __attribute__((noreturn));
extern void errc(int, int, const char *, ...) __attribute__((noreturn));
extern void errx(int, const char *, ...) __attribute__((noreturn));
extern void verr(int, const char *, va_list) __attribute__((noreturn));
extern void verrc(int, int, const char *, va_list) __attribute__((noreturn));
extern void verrx(int, const char *, va_list) __attribute__((noreturn));
extern void warn(const char *, ...);
extern void warnx(const char *, ...);
extern void warnc(int, const char *, ...);
extern void vwarn(const char *, va_list);
extern void vwarnc(int, const char *, va_list);
extern void vwarnx(const char *, va_list);
#endif

#if !HAVE_B64_NTOP
/*
 * Compatibility for b64_ntop(3).
 */
extern int b64_ntop(unsigned char const *, size_t, char *, size_t);
extern int b64_pton(char const *, unsigned char *, size_t);
#endif

#if !HAVE_EXPLICIT_BZERO
/*
 * Compatibility for explicit_bzero(3).
 */
extern void explicit_bzero(void *, size_t);
#endif

#if !HAVE_MEMMEM
/*
 * Compatibility for memmem(3).
 */
void *memmem(const void *, size_t, const void *, size_t);
#endif

#if !HAVE_MEMRCHR
/*
 * Compatibility for memrchr(3).
 */
void *memrchr(const void *b, int, size_t);
#endif

#if !HAVE_GETPROGNAME
/*
 * Compatibility for getprogname(3).
 */
extern const char *getprogname(void);
#endif

#if !HAVE_QSORT_R
/*
 * Compatibility for qsort_r(3).
 */
extern void qsort_r(void *, size_t, size_t, void *, int (*compar)(void *, const void *, const void *));
#endif

#if !HAVE_READPASSPHRASE
/*
 * Macros and function required for readpassphrase(3).
 */
#define RPP_ECHO_OFF 0x00
#define RPP_ECHO_ON 0x01
#define RPP_REQUIRE_TTY 0x02
#define RPP_FORCELOWER 0x04
#define RPP_FORCEUPPER 0x08
#define RPP_SEVENBIT 0x10
#define RPP_STDIN 0x20
char *readpassphrase(const char *, char *, size_t, int);
#endif

#if !HAVE_REALLOCARRAY
/*
 * Compatibility for reallocarray(3).
 */
extern void *reallocarray(void *, size_t, size_t);
#endif

#if !HAVE_RECALLOCARRAY
/*
 * Compatibility for recallocarray(3).
 */
extern void *recallocarray(void *, size_t, size_t, size_t);
#endif

#if !HAVE_STRLCAT
/*
 * Compatibility for strlcat(3).
 */
extern size_t strlcat(char *, const char *, size_t);
#endif

#if !HAVE_STRLCPY
/*
 * Compatibility for strlcpy(3).
 */
extern size_t strlcpy(char *, const char *, size_t);
#endif

#if !HAVE_STRNDUP
/*
 * Compatibility for strndup(3).
 */
extern char *strndup(const char *, size_t);
#endif

#if !HAVE_STRNLEN
/*
 * Compatibility for strnlen(3).
 */
extern size_t strnlen(const char *, size_t);
#endif

#if !HAVE_STRNSTR
/*
 * Compatibility for strnstr(3).
 */
extern char *strnstr(const char *, const char *, size_t);
#endif

#if !HAVE_STRSEP
// Compatibility for strsep(3)
extern char *strsep(char **, const char *);
#endif

#if !HAVE_STRTONUM
/*
 * Compatibility for strotnum(3).
 */
extern long long strtonum(const char *, long long, long long, const char **);
#endif

#if !HAVE_MKFIFOAT
/*
 * Compatibility for mkfifoat(2).
 */
int mkfifoat(int, const char *, mode_t);
#endif

#if !HAVE_MKNODAT
/*
 * Compatibility for mknodat(2).
 */
int mknodat(int, const char *, mode_t, dev_t);
#endif

#if !HAVE_SETRESGID
/*
 * Compatibility for setresgid(2).
 */
int setresgid(gid_t rgid, gid_t egid, gid_t sgid);
#endif

#if !HAVE_SETRESUID
/*
 * Compatibility for setresuid(2).
 */
int setresuid(uid_t ruid, uid_t euid, uid_t suid);
#endif

#if !HAVE_SYS_QUEUE
/*
 * Copyright (c) 1991, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)queue.h	8.5 (Berkeley) 8/20/94
 */

/* OPENBSD ORIGINAL: sys/sys/queue.h */

/*
 * Require for OS/X and other platforms that have old/broken/incomplete
 * <sys/queue.h>.
 */

#undef LIST_EMPTY
#undef LIST_END
#undef LIST_ENTRY
#undef LIST_FIRST
#undef LIST_FOREACH
#undef LIST_FOREACH_SAFE
#undef LIST_HEAD
#undef LIST_HEAD_INITIALIZER
#undef LIST_INIT
#undef LIST_INSERT_AFTER
#undef LIST_INSERT_BEFORE
#undef LIST_INSERT_HEAD
#undef LIST_NEXT
#undef LIST_REMOVE
#undef LIST_REPLACE
#undef SIMPLEQ_CONCAT
#undef SIMPLEQ_EMPTY
#undef SIMPLEQ_END
#undef SIMPLEQ_ENTRY
#undef SIMPLEQ_FIRST
#undef SIMPLEQ_FOREACH
#undef SIMPLEQ_FOREACH_SAFE
#undef SIMPLEQ_HEAD
#undef SIMPLEQ_HEAD_INITIALIZER
#undef SIMPLEQ_INIT
#undef SIMPLEQ_INSERT_AFTER
#undef SIMPLEQ_INSERT_HEAD
#undef SIMPLEQ_INSERT_TAIL
#undef SIMPLEQ_NEXT
#undef SIMPLEQ_REMOVE_AFTER
#undef SIMPLEQ_REMOVE_HEAD
#undef SLIST_EMPTY
#undef SLIST_END
#undef SLIST_ENTRY
#undef SLIST_FIRST
#undef SLIST_FOREACH
#undef SLIST_FOREACH_SAFE
#undef SLIST_HEAD
#undef SLIST_HEAD_INITIALIZER
#undef SLIST_INIT
#undef SLIST_INSERT_AFTER
#undef SLIST_INSERT_HEAD
#undef SLIST_NEXT
#undef SLIST_REMOVE
#undef SLIST_REMOVE_AFTER
#undef SLIST_REMOVE_HEAD
#undef TAILQ_CONCAT
#undef TAILQ_EMPTY
#undef TAILQ_END
#undef TAILQ_ENTRY
#undef TAILQ_FIRST
#undef TAILQ_FOREACH
#undef TAILQ_FOREACH_REVERSE
#undef TAILQ_FOREACH_REVERSE_SAFE
#undef TAILQ_FOREACH_SAFE
#undef TAILQ_HEAD
#undef TAILQ_HEAD_INITIALIZER
#undef TAILQ_INIT
#undef TAILQ_INSERT_AFTER
#undef TAILQ_INSERT_BEFORE
#undef TAILQ_INSERT_HEAD
#undef TAILQ_INSERT_TAIL
#undef TAILQ_LAST
#undef TAILQ_NEXT
#undef TAILQ_PREV
#undef TAILQ_REMOVE
#undef TAILQ_REPLACE
#undef XSIMPLEQ_EMPTY
#undef XSIMPLEQ_END
#undef XSIMPLEQ_ENTRY
#undef XSIMPLEQ_FIRST
#undef XSIMPLEQ_FOREACH
#undef XSIMPLEQ_FOREACH_SAFE
#undef XSIMPLEQ_HEAD
#undef XSIMPLEQ_INIT
#undef XSIMPLEQ_INSERT_AFTER
#undef XSIMPLEQ_INSERT_HEAD
#undef XSIMPLEQ_INSERT_TAIL
#undef XSIMPLEQ_NEXT
#undef XSIMPLEQ_REMOVE_AFTER
#undef XSIMPLEQ_REMOVE_HEAD
#undef XSIMPLEQ_XOR

/*
 * This file defines five types of data structures: singly-linked lists,
 * lists, simple queues, tail queues and XOR simple queues.
 *
 *
 * A singly-linked list is headed by a single forward pointer. The elements
 * are singly linked for minimum space and pointer manipulation overhead at
 * the expense of O(n) removal for arbitrary elements. New elements can be
 * added to the list after an existing element or at the head of the list.
 * Elements being removed from the head of the list should use the explicit
 * macro for this purpose for optimum efficiency. A singly-linked list may
 * only be traversed in the forward direction.  Singly-linked lists are ideal
 * for applications with large datasets and few or no removals or for
 * implementing a LIFO queue.
 *
 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.
 *
 * A simple queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are singly
 * linked to save space, so elements can only be removed from the
 * head of the list. New elements can be added to the list before or after
 * an existing element, at the head of the list, or at the end of the
 * list. A simple queue may only be traversed in the forward direction.
 *
 * A tail queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or
 * after an existing element, at the head of the list, or at the end of
 * the list. A tail queue may be traversed in either direction.
 *
 * An XOR simple queue is used in the same way as a regular simple queue.
 * The difference is that the head structure also includes a "cookie" that
 * is XOR'd with the queue pointer (first, last or next) to generate the
 * real pointer value.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 */

#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
#define _Q_INVALID ((void *)-1)
#define _Q_INVALIDATE(a) (a) = _Q_INVALID
#else
#define _Q_INVALIDATE(a)
#endif

/*
 * Singly-linked List definitions.
 */
#define SLIST_HEAD(name, type)						\
struct name {								\
	struct type *slh_first;	/* first element */			\
}

#define	SLIST_HEAD_INITIALIZER(head)					\
	{ NULL }

#define SLIST_ENTRY(type)						\
struct {								\
	struct type *sle_next;	/* next element */			\
}

/*
 * Singly-linked List access methods.
 */
#define	SLIST_FIRST(head)	((head)->slh_first)
#define	SLIST_END(head)		NULL
#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)

#define	SLIST_FOREACH(var, head, field)					\
	for((var) = SLIST_FIRST(head);					\
	    (var) != SLIST_END(head);					\
	    (var) = SLIST_NEXT(var, field))

#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = SLIST_FIRST(head);				\
	    (var) && ((tvar) = SLIST_NEXT(var, field), 1);		\
	    (var) = (tvar))

/*
 * Singly-linked List functions.
 */
#define	SLIST_INIT(head) {						\
	SLIST_FIRST(head) = SLIST_END(head);				\
}

#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
	(slistelm)->field.sle_next = (elm);				\
} while (0)

#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.sle_next = (head)->slh_first;			\
	(head)->slh_first = (elm);					\
} while (0)

#define	SLIST_REMOVE_AFTER(elm, field) do {				\
	(elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;	\
} while (0)

#define	SLIST_REMOVE_HEAD(head, field) do {				\
	(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)

#define SLIST_REMOVE(head, elm, type, field) do {			\
	if ((head)->slh_first == (elm)) {				\
		SLIST_REMOVE_HEAD((head), field);			\
	} else {							\
		struct type *curelm = (head)->slh_first;		\
									\
		while (curelm->field.sle_next != (elm))			\
			curelm = curelm->field.sle_next;		\
		curelm->field.sle_next =				\
		    curelm->field.sle_next->field.sle_next;		\
	}								\
	_Q_INVALIDATE((elm)->field.sle_next);				\
} while (0)

/*
 * List definitions.
 */
#define LIST_HEAD(name, type)						\
struct name {								\
	struct type *lh_first;	/* first element */			\
}

#define LIST_HEAD_INITIALIZER(head)					\
	{ NULL }

#define LIST_ENTRY(type)						\
struct {								\
	struct type *le_next;	/* next element */			\
	struct type **le_prev;	/* address of previous next element */	\
}

/*
 * List access methods.
 */
#define	LIST_FIRST(head)		((head)->lh_first)
#define	LIST_END(head)			NULL
#define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
#define	LIST_NEXT(elm, field)		((elm)->field.le_next)

#define LIST_FOREACH(var, head, field)					\
	for((var) = LIST_FIRST(head);					\
	    (var)!= LIST_END(head);					\
	    (var) = LIST_NEXT(var, field))

#define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = LIST_FIRST(head);				\
	    (var) && ((tvar) = LIST_NEXT(var, field), 1);		\
	    (var) = (tvar))

/*
 * List functions.
 */
#define	LIST_INIT(head) do {						\
	LIST_FIRST(head) = LIST_END(head);				\
} while (0)

#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
		(listelm)->field.le_next->field.le_prev =		\
		    &(elm)->field.le_next;				\
	(listelm)->field.le_next = (elm);				\
	(elm)->field.le_prev = &(listelm)->field.le_next;		\
} while (0)

#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.le_prev = (listelm)->field.le_prev;		\
	(elm)->field.le_next = (listelm);				\
	*(listelm)->field.le_prev = (elm);				\
	(listelm)->field.le_prev = &(elm)->field.le_next;		\
} while (0)

#define LIST_INSERT_HEAD(head, elm, field) do {				\
	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
	(head)->lh_first = (elm);					\
	(elm)->field.le_prev = &(head)->lh_first;			\
} while (0)

#define LIST_REMOVE(elm, field) do {					\
	if ((elm)->field.le_next != NULL)				\
		(elm)->field.le_next->field.le_prev =			\
		    (elm)->field.le_prev;				\
	*(elm)->field.le_prev = (elm)->field.le_next;			\
	_Q_INVALIDATE((elm)->field.le_prev);				\
	_Q_INVALIDATE((elm)->field.le_next);				\
} while (0)

#define LIST_REPLACE(elm, elm2, field) do {				\
	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
		(elm2)->field.le_next->field.le_prev =			\
		    &(elm2)->field.le_next;				\
	(elm2)->field.le_prev = (elm)->field.le_prev;			\
	*(elm2)->field.le_prev = (elm2);				\
	_Q_INVALIDATE((elm)->field.le_prev);				\
	_Q_INVALIDATE((elm)->field.le_next);				\
} while (0)

/*
 * Simple queue definitions.
 */
#define SIMPLEQ_HEAD(name, type)					\
struct name {								\
	struct type *sqh_first;	/* first element */			\
	struct type **sqh_last;	/* addr of last next element */		\
}

#define SIMPLEQ_HEAD_INITIALIZER(head)					\
	{ NULL, &(head).sqh_first }

#define SIMPLEQ_ENTRY(type)						\
struct {								\
	struct type *sqe_next;	/* next element */			\
}

/*
 * Simple queue access methods.
 */
#define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
#define	SIMPLEQ_END(head)	    NULL
#define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
#define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)

#define SIMPLEQ_FOREACH(var, head, field)				\
	for((var) = SIMPLEQ_FIRST(head);				\
	    (var) != SIMPLEQ_END(head);					\
	    (var) = SIMPLEQ_NEXT(var, field))

#define	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = SIMPLEQ_FIRST(head);				\
	    (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1);		\
	    (var) = (tvar))

/*
 * Simple queue functions.
 */
#define	SIMPLEQ_INIT(head) do {						\
	(head)->sqh_first = NULL;					\
	(head)->sqh_last = &(head)->sqh_first;				\
} while (0)

#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
		(head)->sqh_last = &(elm)->field.sqe_next;		\
	(head)->sqh_first = (elm);					\
} while (0)

#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.sqe_next = NULL;					\
	*(head)->sqh_last = (elm);					\
	(head)->sqh_last = &(elm)->field.sqe_next;			\
} while (0)

#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
		(head)->sqh_last = &(elm)->field.sqe_next;		\
	(listelm)->field.sqe_next = (elm);				\
} while (0)

#define SIMPLEQ_REMOVE_HEAD(head, field) do {			\
	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
		(head)->sqh_last = &(head)->sqh_first;			\
} while (0)

#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
	if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
	    == NULL)							\
		(head)->sqh_last = &(elm)->field.sqe_next;		\
} while (0)

#define SIMPLEQ_CONCAT(head1, head2) do {				\
	if (!SIMPLEQ_EMPTY((head2))) {					\
		*(head1)->sqh_last = (head2)->sqh_first;		\
		(head1)->sqh_last = (head2)->sqh_last;			\
		SIMPLEQ_INIT((head2));					\
	}								\
} while (0)

/*
 * XOR Simple queue definitions.
 */
#define XSIMPLEQ_HEAD(name, type)					\
struct name {								\
	struct type *sqx_first;	/* first element */			\
	struct type **sqx_last;	/* addr of last next element */		\
	unsigned long sqx_cookie;					\
}

#define XSIMPLEQ_ENTRY(type)						\
struct {								\
	struct type *sqx_next;	/* next element */			\
}

/*
 * XOR Simple queue access methods.
 */
#define XSIMPLEQ_XOR(head, ptr)	    ((__typeof(ptr))((head)->sqx_cookie ^ \
					(unsigned long)(ptr)))
#define	XSIMPLEQ_FIRST(head)	    XSIMPLEQ_XOR(head, ((head)->sqx_first))
#define	XSIMPLEQ_END(head)	    NULL
#define	XSIMPLEQ_EMPTY(head)	    (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
#define	XSIMPLEQ_NEXT(head, elm, field)    XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))


#define XSIMPLEQ_FOREACH(var, head, field)				\
	for ((var) = XSIMPLEQ_FIRST(head);				\
	    (var) != XSIMPLEQ_END(head);				\
	    (var) = XSIMPLEQ_NEXT(head, var, field))

#define	XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = XSIMPLEQ_FIRST(head);				\
	    (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1);	\
	    (var) = (tvar))

/*
 * XOR Simple queue functions.
 */
#define	XSIMPLEQ_INIT(head) do {					\
	arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
	(head)->sqx_first = XSIMPLEQ_XOR(head, NULL);			\
	(head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);	\
} while (0)

#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.sqx_next = (head)->sqx_first) ==		\
	    XSIMPLEQ_XOR(head, NULL))					\
		(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
	(head)->sqx_first = XSIMPLEQ_XOR(head, (elm));			\
} while (0)

#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL);		\
	*(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
	(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);	\
} while (0)

#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	if (((elm)->field.sqx_next = (listelm)->field.sqx_next) ==	\
	    XSIMPLEQ_XOR(head, NULL))					\
		(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
	(listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm));		\
} while (0)

#define XSIMPLEQ_REMOVE_HEAD(head, field) do {				\
	if (((head)->sqx_first = XSIMPLEQ_XOR(head,			\
	    (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
		(head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
} while (0)

#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
	if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head,			\
	    (elm)->field.sqx_next)->field.sqx_next)			\
	    == XSIMPLEQ_XOR(head, NULL))				\
		(head)->sqx_last = 					\
		    XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);		\
} while (0)


/*
 * Tail queue definitions.
 */
#define TAILQ_HEAD(name, type)						\
struct name {								\
	struct type *tqh_first;	/* first element */			\
	struct type **tqh_last;	/* addr of last next element */		\
}

#define TAILQ_HEAD_INITIALIZER(head)					\
	{ NULL, &(head).tqh_first }

#define TAILQ_ENTRY(type)						\
struct {								\
	struct type *tqe_next;	/* next element */			\
	struct type **tqe_prev;	/* address of previous next element */	\
}

/*
 * Tail queue access methods.
 */
#define	TAILQ_FIRST(head)		((head)->tqh_first)
#define	TAILQ_END(head)			NULL
#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname)					\
	(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field)				\
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#define	TAILQ_EMPTY(head)						\
	(TAILQ_FIRST(head) == TAILQ_END(head))

#define TAILQ_FOREACH(var, head, field)					\
	for((var) = TAILQ_FIRST(head);					\
	    (var) != TAILQ_END(head);					\
	    (var) = TAILQ_NEXT(var, field))

#define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = TAILQ_FIRST(head);					\
	    (var) != TAILQ_END(head) &&					\
	    ((tvar) = TAILQ_NEXT(var, field), 1);			\
	    (var) = (tvar))


#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
	for((var) = TAILQ_LAST(head, headname);				\
	    (var) != TAILQ_END(head);					\
	    (var) = TAILQ_PREV(var, headname, field))

#define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
	for ((var) = TAILQ_LAST(head, headname);			\
	    (var) != TAILQ_END(head) &&					\
	    ((tvar) = TAILQ_PREV(var, headname, field), 1);		\
	    (var) = (tvar))

/*
 * Tail queue functions.
 */
#define	TAILQ_INIT(head) do {						\
	(head)->tqh_first = NULL;					\
	(head)->tqh_last = &(head)->tqh_first;				\
} while (0)

#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
		(head)->tqh_first->field.tqe_prev =			\
		    &(elm)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm)->field.tqe_next;		\
	(head)->tqh_first = (elm);					\
	(elm)->field.tqe_prev = &(head)->tqh_first;			\
} while (0)

#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.tqe_next = NULL;					\
	(elm)->field.tqe_prev = (head)->tqh_last;			\
	*(head)->tqh_last = (elm);					\
	(head)->tqh_last = &(elm)->field.tqe_next;			\
} while (0)

#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
		(elm)->field.tqe_next->field.tqe_prev =			\
		    &(elm)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm)->field.tqe_next;		\
	(listelm)->field.tqe_next = (elm);				\
	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
} while (0)

#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
	(elm)->field.tqe_next = (listelm);				\
	*(listelm)->field.tqe_prev = (elm);				\
	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
} while (0)

#define TAILQ_REMOVE(head, elm, field) do {				\
	if (((elm)->field.tqe_next) != NULL)				\
		(elm)->field.tqe_next->field.tqe_prev =			\
		    (elm)->field.tqe_prev;				\
	else								\
		(head)->tqh_last = (elm)->field.tqe_prev;		\
	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
	_Q_INVALIDATE((elm)->field.tqe_prev);				\
	_Q_INVALIDATE((elm)->field.tqe_next);				\
} while (0)

#define TAILQ_REPLACE(head, elm, elm2, field) do {			\
	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
		(elm2)->field.tqe_next->field.tqe_prev =		\
		    &(elm2)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm2)->field.tqe_next;		\
	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
	*(elm2)->field.tqe_prev = (elm2);				\
	_Q_INVALIDATE((elm)->field.tqe_prev);				\
	_Q_INVALIDATE((elm)->field.tqe_next);				\
} while (0)

#define TAILQ_CONCAT(head1, head2, field) do {				\
	if (!TAILQ_EMPTY(head2)) {					\
		*(head1)->tqh_last = (head2)->tqh_first;		\
		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
		(head1)->tqh_last = (head2)->tqh_last;			\
		TAILQ_INIT((head2));					\
	}								\
} while (0)
#endif /* !HAVE_SYS_QUEUE */

#if !HAVE_SYS_TREE
/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/* OPENBSD ORIGINAL: sys/sys/tree.h */

/*
 * This file defines data structures for different types of trees:
 * splay trees and red-black trees.
 *
 * A splay tree is a self-organizing data structure.  Every operation
 * on the tree causes a splay to happen.  The splay moves the requested
 * node to the root of the tree and partly rebalances it.
 *
 * This has the benefit that request locality causes faster lookups as
 * the requested nodes move to the top of the tree.  On the other hand,
 * every lookup causes memory writes.
 *
 * The Balance Theorem bounds the total access time for m operations
 * and n inserts on an initially empty tree as O((m + n)lg n).  The
 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
 *
 * A red-black tree is a binary search tree with the node color as an
 * extra attribute.  It fulfills a set of conditions:
 *	- every search path from the root to a leaf consists of the
 *	  same number of black nodes,
 *	- each red node (except for the root) has a black parent,
 *	- each leaf node is black.
 *
 * Every operation on a red-black tree is bounded as O(lg n).
 * The maximum height of a red-black tree is 2lg (n+1).
 */

#define SPLAY_HEAD(name, type)						\
struct name {								\
	struct type *sph_root; /* root of the tree */			\
}

#define SPLAY_INITIALIZER(root)						\
	{ NULL }

#define SPLAY_INIT(root) do {						\
	(root)->sph_root = NULL;					\
} while (0)

#define SPLAY_ENTRY(type)						\
struct {								\
	struct type *spe_left; /* left element */			\
	struct type *spe_right; /* right element */			\
}

#define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
#define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
#define SPLAY_ROOT(head)		(head)->sph_root
#define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)

/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
	(head)->sph_root = tmp;						\
} while (0)

#define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
	(head)->sph_root = tmp;						\
} while (0)

#define SPLAY_LINKLEFT(head, tmp, field) do {				\
	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
	tmp = (head)->sph_root;						\
	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
} while (0)

#define SPLAY_LINKRIGHT(head, tmp, field) do {				\
	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
	tmp = (head)->sph_root;						\
	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
} while (0)

#define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
} while (0)

/* Generates prototypes and inline functions */

#define SPLAY_PROTOTYPE(name, type, field, cmp)				\
void name##_SPLAY(struct name *, struct type *);			\
void name##_SPLAY_MINMAX(struct name *, int);				\
struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
									\
/* Finds the node with the same key as elm */				\
static __inline struct type *						\
name##_SPLAY_FIND(struct name *head, struct type *elm)			\
{									\
	if (SPLAY_EMPTY(head))						\
		return(NULL);						\
	name##_SPLAY(head, elm);					\
	if ((cmp)(elm, (head)->sph_root) == 0)				\
		return (head->sph_root);				\
	return (NULL);							\
}									\
									\
static __inline struct type *						\
name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
{									\
	name##_SPLAY(head, elm);					\
	if (SPLAY_RIGHT(elm, field) != NULL) {				\
		elm = SPLAY_RIGHT(elm, field);				\
		while (SPLAY_LEFT(elm, field) != NULL) {		\
			elm = SPLAY_LEFT(elm, field);			\
		}							\
	} else								\
		elm = NULL;						\
	return (elm);							\
}									\
									\
static __inline struct type *						\
name##_SPLAY_MIN_MAX(struct name *head, int val)			\
{									\
	name##_SPLAY_MINMAX(head, val);					\
        return (SPLAY_ROOT(head));					\
}

/* Main splay operation.
 * Moves node close to the key of elm to top
 */
#define SPLAY_GENERATE(name, type, field, cmp)				\
struct type *								\
name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
{									\
    if (SPLAY_EMPTY(head)) {						\
	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
    } else {								\
	    int __comp;							\
	    name##_SPLAY(head, elm);					\
	    __comp = (cmp)(elm, (head)->sph_root);			\
	    if(__comp < 0) {						\
		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
	    } else if (__comp > 0) {					\
		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
	    } else							\
		    return ((head)->sph_root);				\
    }									\
    (head)->sph_root = (elm);						\
    return (NULL);							\
}									\
									\
struct type *								\
name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
{									\
	struct type *__tmp;						\
	if (SPLAY_EMPTY(head))						\
		return (NULL);						\
	name##_SPLAY(head, elm);					\
	if ((cmp)(elm, (head)->sph_root) == 0) {			\
		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
		} else {						\
			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
			name##_SPLAY(head, elm);			\
			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
		}							\
		return (elm);						\
	}								\
	return (NULL);							\
}									\
									\
void									\
name##_SPLAY(struct name *head, struct type *elm)			\
{									\
	struct type __node, *__left, *__right, *__tmp;			\
	int __comp;							\
\
	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
	__left = __right = &__node;					\
\
	while ((__comp = (cmp)(elm, (head)->sph_root))) {		\
		if (__comp < 0) {					\
			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if ((cmp)(elm, __tmp) < 0){			\
				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKLEFT(head, __right, field);		\
		} else if (__comp > 0) {				\
			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if ((cmp)(elm, __tmp) > 0){			\
				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKRIGHT(head, __left, field);		\
		}							\
	}								\
	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
}									\
									\
/* Splay with either the minimum or the maximum element			\
 * Used to find minimum or maximum element in tree.			\
 */									\
void name##_SPLAY_MINMAX(struct name *head, int __comp) \
{									\
	struct type __node, *__left, *__right, *__tmp;			\
\
	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
	__left = __right = &__node;					\
\
	while (1) {							\
		if (__comp < 0) {					\
			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if (__comp < 0){				\
				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKLEFT(head, __right, field);		\
		} else if (__comp > 0) {				\
			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if (__comp > 0) {				\
				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKRIGHT(head, __left, field);		\
		}							\
	}								\
	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
}

#define SPLAY_NEGINF	-1
#define SPLAY_INF	1

#define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
#define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
#define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
#define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
#define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\
					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
#define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\
					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))

#define SPLAY_FOREACH(x, name, head)					\
	for ((x) = SPLAY_MIN(name, head);				\
	     (x) != NULL;						\
	     (x) = SPLAY_NEXT(name, head, x))

/* Macros that define a red-black tree */
#define RB_HEAD(name, type)						\
struct name {								\
	struct type *rbh_root; /* root of the tree */			\
}

#define RB_INITIALIZER(root)						\
	{ NULL }

#define RB_INIT(root) do {						\
	(root)->rbh_root = NULL;					\
} while (0)

#define RB_BLACK	0
#define RB_RED		1
#define RB_ENTRY(type)							\
struct {								\
	struct type *rbe_left;		/* left element */		\
	struct type *rbe_right;		/* right element */		\
	struct type *rbe_parent;	/* parent element */		\
	int rbe_color;			/* node color */		\
}

#define RB_LEFT(elm, field)		(elm)->field.rbe_left
#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
#define RB_PARENT(elm, field)		(elm)->field.rbe_parent
#define RB_COLOR(elm, field)		(elm)->field.rbe_color
#define RB_ROOT(head)			(head)->rbh_root
#define RB_EMPTY(head)			(RB_ROOT(head) == NULL)

#define RB_SET(elm, parent, field) do {					\
	RB_PARENT(elm, field) = parent;					\
	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
	RB_COLOR(elm, field) = RB_RED;					\
} while (0)

#define RB_SET_BLACKRED(black, red, field) do {				\
	RB_COLOR(black, field) = RB_BLACK;				\
	RB_COLOR(red, field) = RB_RED;					\
} while (0)

#ifndef RB_AUGMENT
#define RB_AUGMENT(x)	do {} while (0)
#endif

#define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
	(tmp) = RB_RIGHT(elm, field);					\
	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {		\
		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
	}								\
	RB_AUGMENT(elm);						\
	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
		else							\
			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
	} else								\
		(head)->rbh_root = (tmp);				\
	RB_LEFT(tmp, field) = (elm);					\
	RB_PARENT(elm, field) = (tmp);					\
	RB_AUGMENT(tmp);						\
	if ((RB_PARENT(tmp, field)))					\
		RB_AUGMENT(RB_PARENT(tmp, field));			\
} while (0)

#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
	(tmp) = RB_LEFT(elm, field);					\
	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {		\
		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
	}								\
	RB_AUGMENT(elm);						\
	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
		else							\
			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
	} else								\
		(head)->rbh_root = (tmp);				\
	RB_RIGHT(tmp, field) = (elm);					\
	RB_PARENT(elm, field) = (tmp);					\
	RB_AUGMENT(tmp);						\
	if ((RB_PARENT(tmp, field)))					\
		RB_AUGMENT(RB_PARENT(tmp, field));			\
} while (0)

/* Generates prototypes and inline functions */
#define	RB_PROTOTYPE(name, type, field, cmp)				\
	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
attr void name##_RB_INSERT_COLOR(struct name *, struct type *);		\
attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
attr struct type *name##_RB_REMOVE(struct name *, struct type *);	\
attr struct type *name##_RB_INSERT(struct name *, struct type *);	\
attr struct type *name##_RB_FIND(struct name *, struct type *);		\
attr struct type *name##_RB_NFIND(struct name *, struct type *);	\
attr struct type *name##_RB_NEXT(struct type *);			\
attr struct type *name##_RB_PREV(struct type *);			\
attr struct type *name##_RB_MINMAX(struct name *, int);			\
									\

/* Main rb operation.
 * Moves node close to the key of elm to top
 */
#define	RB_GENERATE(name, type, field, cmp)				\
	RB_GENERATE_INTERNAL(name, type, field, cmp,)
#define	RB_GENERATE_STATIC(name, type, field, cmp)			\
	RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
attr void								\
name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
{									\
	struct type *parent, *gparent, *tmp;				\
	while ((parent = RB_PARENT(elm, field)) &&			\
	    RB_COLOR(parent, field) == RB_RED) {			\
		gparent = RB_PARENT(parent, field);			\
		if (parent == RB_LEFT(gparent, field)) {		\
			tmp = RB_RIGHT(gparent, field);			\
			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
				RB_COLOR(tmp, field) = RB_BLACK;	\
				RB_SET_BLACKRED(parent, gparent, field);\
				elm = gparent;				\
				continue;				\
			}						\
			if (RB_RIGHT(parent, field) == elm) {		\
				RB_ROTATE_LEFT(head, parent, tmp, field);\
				tmp = parent;				\
				parent = elm;				\
				elm = tmp;				\
			}						\
			RB_SET_BLACKRED(parent, gparent, field);	\
			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
		} else {						\
			tmp = RB_LEFT(gparent, field);			\
			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
				RB_COLOR(tmp, field) = RB_BLACK;	\
				RB_SET_BLACKRED(parent, gparent, field);\
				elm = gparent;				\
				continue;				\
			}						\
			if (RB_LEFT(parent, field) == elm) {		\
				RB_ROTATE_RIGHT(head, parent, tmp, field);\
				tmp = parent;				\
				parent = elm;				\
				elm = tmp;				\
			}						\
			RB_SET_BLACKRED(parent, gparent, field);	\
			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
		}							\
	}								\
	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
}									\
									\
attr void								\
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
{									\
	struct type *tmp;						\
	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
	    elm != RB_ROOT(head)) {					\
		if (RB_LEFT(parent, field) == elm) {			\
			tmp = RB_RIGHT(parent, field);			\
			if (RB_COLOR(tmp, field) == RB_RED) {		\
				RB_SET_BLACKRED(tmp, parent, field);	\
				RB_ROTATE_LEFT(head, parent, tmp, field);\
				tmp = RB_RIGHT(parent, field);		\
			}						\
			if ((RB_LEFT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
			    (RB_RIGHT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
				RB_COLOR(tmp, field) = RB_RED;		\
				elm = parent;				\
				parent = RB_PARENT(elm, field);		\
			} else {					\
				if (RB_RIGHT(tmp, field) == NULL ||	\
				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
					struct type *oleft;		\
					if ((oleft = RB_LEFT(tmp, field)))\
						RB_COLOR(oleft, field) = RB_BLACK;\
					RB_COLOR(tmp, field) = RB_RED;	\
					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
					tmp = RB_RIGHT(parent, field);	\
				}					\
				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
				RB_COLOR(parent, field) = RB_BLACK;	\
				if (RB_RIGHT(tmp, field))		\
					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
				RB_ROTATE_LEFT(head, parent, tmp, field);\
				elm = RB_ROOT(head);			\
				break;					\
			}						\
		} else {						\
			tmp = RB_LEFT(parent, field);			\
			if (RB_COLOR(tmp, field) == RB_RED) {		\
				RB_SET_BLACKRED(tmp, parent, field);	\
				RB_ROTATE_RIGHT(head, parent, tmp, field);\
				tmp = RB_LEFT(parent, field);		\
			}						\
			if ((RB_LEFT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
			    (RB_RIGHT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
				RB_COLOR(tmp, field) = RB_RED;		\
				elm = parent;				\
				parent = RB_PARENT(elm, field);		\
			} else {					\
				if (RB_LEFT(tmp, field) == NULL ||	\
				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
					struct type *oright;		\
					if ((oright = RB_RIGHT(tmp, field)))\
						RB_COLOR(oright, field) = RB_BLACK;\
					RB_COLOR(tmp, field) = RB_RED;	\
					RB_ROTATE_LEFT(head, tmp, oright, field);\
					tmp = RB_LEFT(parent, field);	\
				}					\
				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
				RB_COLOR(parent, field) = RB_BLACK;	\
				if (RB_LEFT(tmp, field))		\
					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
				RB_ROTATE_RIGHT(head, parent, tmp, field);\
				elm = RB_ROOT(head);			\
				break;					\
			}						\
		}							\
	}								\
	if (elm)							\
		RB_COLOR(elm, field) = RB_BLACK;			\
}									\
									\
attr struct type *							\
name##_RB_REMOVE(struct name *head, struct type *elm)			\
{									\
	struct type *child, *parent, *old = elm;			\
	int color;							\
	if (RB_LEFT(elm, field) == NULL)				\
		child = RB_RIGHT(elm, field);				\
	else if (RB_RIGHT(elm, field) == NULL)				\
		child = RB_LEFT(elm, field);				\
	else {								\
		struct type *left;					\
		elm = RB_RIGHT(elm, field);				\
		while ((left = RB_LEFT(elm, field)))			\
			elm = left;					\
		child = RB_RIGHT(elm, field);				\
		parent = RB_PARENT(elm, field);				\
		color = RB_COLOR(elm, field);				\
		if (child)						\
			RB_PARENT(child, field) = parent;		\
		if (parent) {						\
			if (RB_LEFT(parent, field) == elm)		\
				RB_LEFT(parent, field) = child;		\
			else						\
				RB_RIGHT(parent, field) = child;	\
			RB_AUGMENT(parent);				\
		} else							\
			RB_ROOT(head) = child;				\
		if (RB_PARENT(elm, field) == old)			\
			parent = elm;					\
		(elm)->field = (old)->field;				\
		if (RB_PARENT(old, field)) {				\
			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
				RB_LEFT(RB_PARENT(old, field), field) = elm;\
			else						\
				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
			RB_AUGMENT(RB_PARENT(old, field));		\
		} else							\
			RB_ROOT(head) = elm;				\
		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
		if (RB_RIGHT(old, field))				\
			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
		if (parent) {						\
			left = parent;					\
			do {						\
				RB_AUGMENT(left);			\
			} while ((left = RB_PARENT(left, field)));	\
		}							\
		goto color;						\
	}								\
	parent = RB_PARENT(elm, field);					\
	color = RB_COLOR(elm, field);					\
	if (child)							\
		RB_PARENT(child, field) = parent;			\
	if (parent) {							\
		if (RB_LEFT(parent, field) == elm)			\
			RB_LEFT(parent, field) = child;			\
		else							\
			RB_RIGHT(parent, field) = child;		\
		RB_AUGMENT(parent);					\
	} else								\
		RB_ROOT(head) = child;					\
color:									\
	if (color == RB_BLACK)						\
		name##_RB_REMOVE_COLOR(head, parent, child);		\
	return (old);							\
}									\
									\
/* Inserts a node into the RB tree */					\
attr struct type *							\
name##_RB_INSERT(struct name *head, struct type *elm)			\
{									\
	struct type *tmp;						\
	struct type *parent = NULL;					\
	int comp = 0;							\
	tmp = RB_ROOT(head);						\
	while (tmp) {							\
		parent = tmp;						\
		comp = (cmp)(elm, parent);				\
		if (comp < 0)						\
			tmp = RB_LEFT(tmp, field);			\
		else if (comp > 0)					\
			tmp = RB_RIGHT(tmp, field);			\
		else							\
			return (tmp);					\
	}								\
	RB_SET(elm, parent, field);					\
	if (parent != NULL) {						\
		if (comp < 0)						\
			RB_LEFT(parent, field) = elm;			\
		else							\
			RB_RIGHT(parent, field) = elm;			\
		RB_AUGMENT(parent);					\
	} else								\
		RB_ROOT(head) = elm;					\
	name##_RB_INSERT_COLOR(head, elm);				\
	return (NULL);							\
}									\
									\
/* Finds the node with the same key as elm */				\
attr struct type *							\
name##_RB_FIND(struct name *head, struct type *elm)			\
{									\
	struct type *tmp = RB_ROOT(head);				\
	int comp;							\
	while (tmp) {							\
		comp = cmp(elm, tmp);					\
		if (comp < 0)						\
			tmp = RB_LEFT(tmp, field);			\
		else if (comp > 0)					\
			tmp = RB_RIGHT(tmp, field);			\
		else							\
			return (tmp);					\
	}								\
	return (NULL);							\
}									\
									\
/* Finds the first node greater than or equal to the search key */	\
attr struct type *							\
name##_RB_NFIND(struct name *head, struct type *elm)			\
{									\
	struct type *tmp = RB_ROOT(head);				\
	struct type *res = NULL;					\
	int comp;							\
	while (tmp) {							\
		comp = cmp(elm, tmp);					\
		if (comp < 0) {						\
			res = tmp;					\
			tmp = RB_LEFT(tmp, field);			\
		}							\
		else if (comp > 0)					\
			tmp = RB_RIGHT(tmp, field);			\
		else							\
			return (tmp);					\
	}								\
	return (res);							\
}									\
									\
/* ARGSUSED */								\
attr struct type *							\
name##_RB_NEXT(struct type *elm)					\
{									\
	if (RB_RIGHT(elm, field)) {					\
		elm = RB_RIGHT(elm, field);				\
		while (RB_LEFT(elm, field))				\
			elm = RB_LEFT(elm, field);			\
	} else {							\
		if (RB_PARENT(elm, field) &&				\
		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
			elm = RB_PARENT(elm, field);			\
		else {							\
			while (RB_PARENT(elm, field) &&			\
			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
				elm = RB_PARENT(elm, field);		\
			elm = RB_PARENT(elm, field);			\
		}							\
	}								\
	return (elm);							\
}									\
									\
/* ARGSUSED */								\
attr struct type *							\
name##_RB_PREV(struct type *elm)					\
{									\
	if (RB_LEFT(elm, field)) {					\
		elm = RB_LEFT(elm, field);				\
		while (RB_RIGHT(elm, field))				\
			elm = RB_RIGHT(elm, field);			\
	} else {							\
		if (RB_PARENT(elm, field) &&				\
		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\
			elm = RB_PARENT(elm, field);			\
		else {							\
			while (RB_PARENT(elm, field) &&			\
			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
				elm = RB_PARENT(elm, field);		\
			elm = RB_PARENT(elm, field);			\
		}							\
	}								\
	return (elm);							\
}									\
									\
attr struct type *							\
name##_RB_MINMAX(struct name *head, int val)				\
{									\
	struct type *tmp = RB_ROOT(head);				\
	struct type *parent = NULL;					\
	while (tmp) {							\
		parent = tmp;						\
		if (val < 0)						\
			tmp = RB_LEFT(tmp, field);			\
		else							\
			tmp = RB_RIGHT(tmp, field);			\
	}								\
	return (parent);						\
}

#define RB_NEGINF	-1
#define RB_INF	1

#define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
#define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
#define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
#define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)
#define RB_NEXT(name, x, y)	name##_RB_NEXT(y)
#define RB_PREV(name, x, y)	name##_RB_PREV(y)
#define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
#define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)

#define RB_FOREACH(x, name, head)					\
	for ((x) = RB_MIN(name, head);					\
	     (x) != NULL;						\
	     (x) = name##_RB_NEXT(x))

#define RB_FOREACH_SAFE(x, name, head, y)				\
	for ((x) = RB_MIN(name, head);					\
	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);		\
	     (x) = (y))

#define RB_FOREACH_REVERSE(x, name, head)				\
	for ((x) = RB_MAX(name, head);					\
	     (x) != NULL;						\
	     (x) = name##_RB_PREV(x))

#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
	for ((x) = RB_MAX(name, head);					\
	    ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);		\
	     (x) = (y))
#endif /* !HAVE_SYS_TREE */

#if !HAVE_FTS
/*
 * Compatibility for fts(3) functions.
 */
typedef struct {
	struct _ftsent *fts_cur;	/* current node */
	struct _ftsent *fts_child;	/* linked list of children */
	struct _ftsent **fts_array;	/* sort array */
	dev_t fts_dev;			/* starting device # */
	char *fts_path;			/* path for this descent */
	int fts_rfd;			/* fd for root */
	size_t fts_pathlen;		/* sizeof(path) */
	int fts_nitems;			/* elements in the sort array */
	int (*fts_compar)(const struct _ftsent **, const struct _ftsent **); /* compare function */
#define	FTS_COMFOLLOW	0x0001		/* follow command line symlinks */
#define	FTS_LOGICAL	0x0002		/* logical walk */
#define	FTS_NOCHDIR	0x0004		/* don't change directories */
#define	FTS_NOSTAT	0x0008		/* don't get stat info */
#define	FTS_PHYSICAL	0x0010		/* physical walk */
#define	FTS_SEEDOT	0x0020		/* return dot and dot-dot */
#define	FTS_XDEV	0x0040		/* don't cross devices */
#define	FTS_OPTIONMASK	0x00ff		/* valid user option mask */
#define	FTS_NAMEONLY	0x1000		/* (private) child names only */
#define	FTS_STOP	0x2000		/* (private) unrecoverable error */
	int fts_options;		/* fts_open options, global flags */
} FTS;

typedef struct _ftsent {
	struct _ftsent *fts_cycle;	/* cycle node */
	struct _ftsent *fts_parent;	/* parent directory */
	struct _ftsent *fts_link;	/* next file in directory */
	long fts_number;	        /* local numeric value */
	void *fts_pointer;	        /* local address value */
	char *fts_accpath;		/* access path */
	char *fts_path;			/* root path */
	int fts_errno;			/* errno for this node */
	int fts_symfd;			/* fd for symlink */
	size_t fts_pathlen;		/* strlen(fts_path) */
	size_t fts_namelen;		/* strlen(fts_name) */
	ino_t fts_ino;			/* inode */
	dev_t fts_dev;			/* device */
	nlink_t fts_nlink;		/* link count */
#define	FTS_ROOTPARENTLEVEL	-1
#define	FTS_ROOTLEVEL		 0
#define	FTS_MAXLEVEL		 0x7fffffff
	int fts_level;		/* depth (-1 to N) */
#define	FTS_D		 1		/* preorder directory */
#define	FTS_DC		 2		/* directory that causes cycles */
#define	FTS_DEFAULT	 3		/* none of the above */
#define	FTS_DNR		 4		/* unreadable directory */
#define	FTS_DOT		 5		/* dot or dot-dot */
#define	FTS_DP		 6		/* postorder directory */
#define	FTS_ERR		 7		/* error; errno is set */
#define	FTS_F		 8		/* regular file */
#define	FTS_INIT	 9		/* initialized only */
#define	FTS_NS		10		/* stat(2) failed */
#define	FTS_NSOK	11		/* no stat(2) requested */
#define	FTS_SL		12		/* symbolic link */
#define	FTS_SLNONE	13		/* symbolic link without target */
	unsigned short fts_info;	/* user flags for FTSENT structure */
#define	FTS_DONTCHDIR	 0x01		/* don't chdir .. to the parent */
#define	FTS_SYMFOLLOW	 0x02		/* followed a symlink to get here */
	unsigned short fts_flags;	/* private flags for FTSENT structure */
#define	FTS_AGAIN	 1		/* read node again */
#define	FTS_FOLLOW	 2		/* follow symbolic link */
#define	FTS_NOINSTR	 3		/* no instructions */
#define	FTS_SKIP	 4		/* discard node */
	unsigned short fts_instr;	/* fts_set() instructions */
	unsigned short fts_spare;	/* unused */
	struct stat *fts_statp;		/* stat(2) information */
	char fts_name[1];		/* file name */
} FTSENT;

FTSENT	*fts_children(FTS *, int);
int	 fts_close(FTS *);
FTS	*fts_open(char * const *, int,
	    int (*)(const FTSENT **, const FTSENT **));
FTSENT	*fts_read(FTS *);
int	 fts_set(FTS *, FTSENT *, int);
#endif /* !HAVE_FTS */

#ifndef nitems
#define nitems(x) (sizeof((x)) / sizeof((x)[0]))
#endif

#ifndef __cleanup
#define __cleanup(x) __attribute__((cleanup(x)))
#endif

#ifndef __noreturn
#define __noreturn __attribute__((noreturn))
#endif

#ifndef __printflike
#define __printflike(x, y) __attribute__((__format__(__printf__, x, y)))
#endif

#ifndef _IsUnused
#define _IsUnused __attribute__((__unused__))
#endif

#endif /* __MKBUILD_CONFIG_H__ */