1 #if !__MKBUILD_CONFIG_H__
2 #if MKBUILD
3 /*-
4 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
5 *
6 * Copyright (c) 2021 Tobias Kortkamp <tobik@FreeBSD.org>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31 #if defined(__CYGWIN__) || defined(__linux__) || defined(__MINT__)
32 # define _GNU_SOURCE
33 # define _DEFAULT_SOURCE
34 #endif
35
36 #define MKBUILD_WHICH 1
37 #include <sys/param.h>
38 #include <sys/stat.h>
39 #include <sys/types.h>
40 #include <sys/utsname.h>
41 #include <sys/wait.h>
42 #include <assert.h>
43 #include <ctype.h>
44 #include <errno.h>
45 #include <fcntl.h>
46 #include <libgen.h>
47 #include <spawn.h>
48 #include <stdarg.h>
49 #include <stdbool.h>
50 #define _WITH_GETLINE
51 #include <stdio.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <unistd.h>
55
56 #ifndef nitems
57 #define nitems(x) (sizeof((x)) / sizeof((x)[0]))
58 #endif
59
60 #ifdef PATH_MAX
61 #define MKBUILD_BUFSZ PATH_MAX
62 #else
63 #define MKBUILD_BUFSZ 4096
64 #endif
65
66 #define MKBUILD_ARRAY_MAX 128
67 #define MKBUILD_FIELD_MAX 32
68
69 extern char **environ;
70
71 enum LTOType {
72 LTO_DISABLED,
73 LTO_FULL,
74 LTO_THIN,
75 };
76
77 enum SpecMode {
78 SPEC_NONE,
79 SPEC_BIN,
80 SPEC_BUNDLE,
81 SPEC_DEFAULT_FEATURES,
82 SPEC_GEN,
83 SPEC_IF,
84 SPEC_INSTALL_DATA,
85 SPEC_INSTALL_MAN,
86 SPEC_NINJA,
87 SPEC_PKG_CONFIG,
88 SPEC_TESTS,
89 SPEC_TOOL,
90 };
91
92 struct Array {
93 void *buf[MKBUILD_ARRAY_MAX];
94 size_t len;
95 };
96
97 struct SpecFile {
98 char *name;
99 char *obj;
100 char *src;
101 };
102
103 struct SpecVar {
104 char *name;
105 struct Array *words;
106 };
107
108 struct Spec {
109 struct Array *defaults;
110 struct Array *install;
111 struct Array *testbins;
112 struct Array *files;
113 struct Array *vars;
114 enum SpecMode mode;
115 const char *name;
116 const char *generator;
117 };
118
119 struct Toolchain {
120 enum LTOType lto;
121 struct Array *ar;
122 struct Array *cc;
123 };
124
125 struct Mkbuild {
126 struct Toolchain toolchain;
127 const char *arg0;
128 struct Array *args;
129 struct Array *features;
130 struct Array *pkg_config_modules;
131 struct Array *system_features;
132 bool auto_lto;
133 bool try_lto;
134 const char *ninja;
135 const char *pkg_config;
136 const char *mkbuild_src;
137 const char *srcdir;
138 const char *builddir;
139 FILE *config_h;
140 FILE *build_ninja;
141 FILE *build_ninja_spec;
142 FILE *info;
143 FILE *log;
144 };
145
146 static const char *default_gcc_cflags[] = {
147 "-O2",
148 "-g",
149 "-W",
150 "-Wall",
151 "-Wextra",
152 "-Wmissing-prototypes",
153 "-Wstrict-prototypes",
154 "-Wwrite-strings",
155 "-Wno-unused-parameter",
156 };
157
158 static const char *default_gcc_ldflags[] = {};
159
160 static const char *tests[] = {
161 "__progname",
162 "arc4random",
163 "b64_ntop",
164 "b64_ntop_ldadd",
165 "bsd_qsort_r",
166 "capsicum",
167 "crypt",
168 "crypt_ldadd",
169 "endian_h",
170 "err",
171 "execinfo",
172 "execinfo_ldadd",
173 "explicit_bzero",
174 "fts",
175 "getexecname",
176 "getprogname",
177 "gnu_qsort_r",
178 "INFTIM",
179 "lib_socket",
180 "lib_socket_ldadd",
181 "memmem",
182 "memrchr",
183 "memset_s",
184 "mkfifoat",
185 "mknodat",
186 "osbyteorder_h",
187 "PATH_MAX",
188 "pledge",
189 "program_invocation_short_name",
190 "readpassphrase",
191 "reallocarray",
192 "recallocarray",
193 "seccomp_filter",
194 "setresgid",
195 "setresuid",
196 "SOCK_NONBLOCK",
197 "strlcat",
198 "strlcpy",
199 "strndup",
200 "strnlen",
201 "strnstr",
202 "strsep",
203 "strtonum",
204 "sys_byteorder_h",
205 "sys_endian_h",
206 "sys_mkdev_h",
207 "sys_queue",
208 "sys_sysmacros_h",
209 "sys_tree",
210 "unveil",
211 "WAIT_ANY",
212 };
213
214 static struct {
215 const char *name;
216 const char *prefix;
217 const char *ldadd[2];
218 } tests_flags[] = {
219 { "b64_ntop_ldadd", "b64_ntop", { "-lresolv" } },
220 { "crypt_ldadd", "crypt", { "-lcrypt" } },
221 { "execinfo_ldadd", "execinfo", { "-lexecinfo", "-lelf" } },
222 { "lib_socket_ldadd", "lib_socket", { "-lsocket", "-lnsl" } },
223 };
224
225 static const char *mkbuild_configure_rules = ""
226 "rule mkbuild-check\n"
227 " 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"
228 " description = $name\n"
229 "rule mkbuild-config\n"
230 " command = cat $in >$out\n"
231 " description = done.\n"
232 "";
233
234 static const char *mkbuild_pkgconf_rules = ""
235 "rule mkbuild-pkgconf-cflags\n"
236 " 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"
237 " description = $name cflags\n"
238 "rule mkbuild-pkgconf-ldadd\n"
239 " 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"
240 " description = $name ldadd\n"
241 "rule mkbuild-pkgconf-ldadd-static\n"
242 " 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"
243 " description = $name ldadd static\n"
244 "rule mkbuild-pkgconf-config\n"
245 " command = cat $in >$out\n"
246 " description = done.\n"
247 "";
248
249 #ifdef __FreeBSD__
250 // Provide pkg-config files for base libraries as a fallback
251
252 static const char *libcrypto_pc = ""
253 "prefix=/usr\n"
254 "libdir=${prefix}/lib\n"
255 "includedir=${prefix}/include\n"
256 "Description: libcrypto\n"
257 "Version: 1.1.1k\n"
258 "Name: libcrypto\n"
259 "Libs: -L${libdir} -lcrypto\n"
260 "Cflags: -I${includedir}\n"
261 "";
262
263 static const char *libssl_pc = ""
264 "prefix=/usr\n"
265 "libdir=${prefix}/lib\n"
266 "includedir=${prefix}/include\n"
267 "Description: libssl\n"
268 "Version: 1.1.1k\n"
269 "Name: libssl\n"
270 "Requires.private: libcrypto\n"
271 "Libs: -L${libdir} -lssl\n"
272 "Cflags: -I${includedir}\n"
273 "";
274
275 static const char *openssl_pc= ""
276 "prefix=/usr\n"
277 "libdir=${prefix}/lib\n"
278 "includedir=${prefix}/include\n"
279 "Description: OpenSSL\n"
280 "Version: 1.1.1k\n"
281 "Name: openssl\n"
282 "Requires: libcrypto libssl\n"
283 "";
284 #endif
285
286 static const char *mkbuild_rules = ""
287 #ifdef __APPLE__
288 "LD_START_GROUP = \n"
289 "LD_END_GROUP = \n"
290 #else
291 "LD_START_GROUP = -Wl,--start-group\n"
292 "LD_END_GROUP = -Wl,--end-group\n"
293 #endif
294 "rule configure\n"
295 " generator = true\n"
296 " command = cd $srcdir && ./configure $configure_args\n"
297 " description = reconfiguring...\n"
298 "rule cc\n"
299 " depfile = $out.d\n"
300 " deps = gcc\n"
301 " command = $CC -std=$CSTD $CFLAGS $CPPFLAGS -MD -MF $out.d -I$builddir -I$subdir -c -o $out $in\n"
302 " description = CC $name\n"
303 "rule bundle\n"
304 " command = rm -f $out && $AR rcs $out $in\n"
305 " description = BUNDLE $name\n"
306 "rule gen\n"
307 " command = $generator $in >$out\n"
308 " description = GEN $name\n"
309 " generator = false\n"
310 "rule bin\n"
311 " command = $CC $LDFLAGS -o $out $LD_START_GROUP $in $LDADD $LD_END_GROUP\n"
312 " description = BIN $name\n"
313 "rule install-program\n"
314 " command = $INSTALL_PROGRAM $in $out\n"
315 " description = INSTALL-PROGRAM $name\n"
316 "rule install-data\n"
317 " command = $INSTALL_DATA $in $out\n"
318 " description = INSTALL-DATA $name\n"
319 "rule install-man\n"
320 " command = $INSTALL_MAN $in $out\n"
321 " description = INSTALL-MAN $name\n"
322 "rule mkbuild-test\n"
323 " command = cd $srcdir && $in && touch $in.stamp \n"
324 " description = TEST $name\n"
325 "";
326
327 static struct {
328 const char *key;
329 const char *value;
330 } mkbuild_settings[] = {
331 { "AR", "ar" },
332 { "AWK", "awk" },
333 { "BUILDDIR", NULL },
334 { "SRCDIR", NULL },
335 { "CC", "cc" },
336 { "CSTD", "c99" },
337 { "CFLAGS", "" },
338 { "CPPFLAGS", "" },
339 { "LDADD", "" },
340 { "LDADD_B64_NTOP", "" },
341 { "LDADD_CRYPT", "" },
342 { "LDADD_EXECINFO", "" },
343 { "LDADD_LIB_SOCKET", "" },
344 { "LDFLAGS", "" },
345 { "FEATURES", "" },
346 { "LTO", "1" },
347 { "NINJA", NULL },
348 { "DESTDIR", "" },
349 { "PREFIX", "/usr/local" },
350 { "BINDIR", "$PREFIX/bin" },
351 { "SHAREDIR", "$PREFIX/share" },
352 { "SBINDIR", "$PREFIX/sbin" },
353 { "INCLUDEDIR", "$PREFIX/include" },
354 { "LIBDIR", "$PREFIX/lib" },
355 { "MANDIR", "$PREFIX/share/man" },
356 { "INSTALL", "install" },
357 { "INSTALL_PROGRAM", "$INSTALL -m 0555" },
358 { "INSTALL_LIB", "$INSTALL -m 0444" },
359 { "INSTALL_MAN", "$INSTALL -m 0444" },
360 { "INSTALL_DATA", "$INSTALL -m 0444" },
361 };
362
363 struct Mkbuild this;
364
365 /* Prototypes */
366 static struct Array *array_new(void);
367 static struct Array *array_append(struct Array *, const void *);
368 struct Array *array_join(struct Array *, struct Array *);
369 static struct Array *array_joinv(struct Array *, void **, const size_t);
370 static void *array_get(struct Array *, size_t);
371 static size_t array_len(struct Array *);
372 static void array_truncate(struct Array *);
373 static char *str_printf(const char *, ...);
374 static bool str_endswith(const char *, const char *);
375 static bool str_startswith(const char *, const char *);
376 static char *str_toupper(const char *);
377 static char *escape_arg(const char *, bool);
378 static bool has_feature(const char *);
379 static bool has_system_feature(const char *);
380 static void configure(void);
381 static void system_features(void);
382 static void pkg_config(void);
383 static void define(const char *, const char *, const char *);
384 static void info(const char *, ...);
385 static void debug(const char *, ...);
386 static bool ltotoolchain(void);
387 static enum LTOType test_ltotoolchain(struct Array *, struct Array *);
388 static bool test_ltotoolchain_helper(enum LTOType, struct Array *, struct Array *);
389 static void spec_write(void);
390 static void spec_build(struct Spec *, const char *, struct Array *, struct Array *);
391 static void spec_cc(struct Spec *);
392 static void spec_var(struct SpecVar *, bool);
393 static void spec_flush(struct Spec *);
394 static bool which(const char *);
395 static int run(struct Array *);
396
397 struct Array *
array_new(void)398 array_new(void)
399 {
400 return calloc(1, sizeof(struct Array));
401 }
402
403 struct Array *
array_append(struct Array * array,const void * val)404 array_append(struct Array *array, const void *val)
405 {
406 assert(array->len < MKBUILD_ARRAY_MAX);
407 array->buf[array->len++] = (void *)val;
408 return array;
409 }
410
411 struct Array *
array_join(struct Array * array,struct Array * other)412 array_join(struct Array *array, struct Array *other)
413 {
414 return array_joinv(array, other->buf, other->len);
415 }
416
417 struct Array *
array_joinv(struct Array * array,void ** vals,const size_t n)418 array_joinv(struct Array *array, void **vals, const size_t n)
419 {
420 for (size_t i = 0; i < n; i++) {
421 assert(array->len < MKBUILD_ARRAY_MAX);
422 array->buf[array->len++] = (void *)vals[i];
423 }
424 return array;
425 }
426
427 void *
array_get(struct Array * array,size_t i)428 array_get(struct Array *array, size_t i)
429 {
430 assert(i < array->len);
431 return array->buf[i];
432 }
433
434 size_t
array_len(struct Array * array)435 array_len(struct Array *array)
436 {
437 return array->len;
438 }
439
440 void
array_truncate(struct Array * array)441 array_truncate(struct Array *array)
442 {
443 array->len = 0;
444 }
445
446 char *
str_printf(const char * format,...)447 str_printf(const char *format, ...)
448 {
449 va_list ap;
450 va_start(ap, format);
451 char *buf = malloc(MKBUILD_BUFSZ);
452 vsnprintf(buf, MKBUILD_BUFSZ, format, ap);
453 va_end(ap);
454 return buf;
455 }
456
457 bool
str_endswith(const char * s,const char * end)458 str_endswith(const char *s, const char *end)
459 {
460 size_t len = strlen(end);
461 if (strlen(s) < len) {
462 return false;
463 }
464 return strncmp(s + strlen(s) - len, end, len) == 0;
465 }
466
467 bool
str_startswith(const char * s,const char * start)468 str_startswith(const char *s, const char *start)
469 {
470 size_t len = strlen(start);
471 if (strlen(s) < len) {
472 return false;
473 }
474 return strncmp(s, start, len) == 0;
475 }
476
477 struct Array *
str_split(const char * s,const char * sep)478 str_split(const char *s, const char *sep)
479 {
480 struct Array *array = array_new();
481 size_t seplen = strlen(sep);
482 const char *buf = strdup(s);
483 if (seplen > 0) {
484 char *ptr;
485 while (*buf && (ptr = strstr(buf, sep))) {
486 *ptr = 0;
487 array_append(array, buf);
488 buf = ptr + seplen;
489 }
490 }
491 array_append(array, buf);
492 return array;
493 }
494
495 char *
str_toupper(const char * s)496 str_toupper(const char *s)
497 {
498 char *buf = strdup(s);
499 size_t len = strlen(buf);
500 for (size_t i = 0; i < len; i++) {
501 buf[i] = toupper((unsigned char)buf[i]);
502 }
503 return buf;
504 }
505
506 char *
escape_arg(const char * s,bool sh)507 escape_arg(const char *s, bool sh)
508 {
509 char *buf = NULL;
510 size_t len = 0;
511
512 FILE *f = open_memstream(&buf, &len);
513 if (f == NULL) {
514 perror("open_memstream");
515 exit(1);
516 }
517
518 if (sh) {
519 fputc('\'', f);
520 }
521 size_t slen = strlen(s);
522 for (size_t i = 0; i < slen; i++) {
523 switch (s[i]) {
524 case '$':
525 case ':':
526 case ' ':
527 case '\n':
528 fputc('$', f);
529 break;
530 case '\\':
531 case '\'':
532 if (sh) {
533 fputc('\\', f);
534 }
535 break;
536 default:
537 break;
538 }
539 fputc(s[i], f);
540 }
541 if (sh) {
542 fputc('\'', f);
543 }
544
545 fclose(f);
546
547 return buf;
548 }
549
550 bool
has_feature(const char * feature)551 has_feature(const char *feature)
552 {
553 const char *notfeature;
554 if (str_startswith(feature, "!")) {
555 notfeature = feature + 1;
556 } else {
557 notfeature = str_printf("!%s", feature);
558 }
559 bool has_feature = false;
560 for (size_t i = 0; i < array_len(this.features); i++) {
561 const char *value = array_get(this.features, i);
562 if (strcmp(value, feature) == 0) {
563 has_feature = true;
564 } else if (strcmp(value, notfeature) == 0) {
565 has_feature = false;
566 }
567 }
568 return has_feature;
569 }
570
571 bool
has_system_feature(const char * feature)572 has_system_feature(const char *feature)
573 {
574 debug("==> checking system feature %s", feature);
575 const char *path = str_printf("%s/.mkbuild/test-%s", this.builddir, feature);
576 FILE *f = fopen(path, "r");
577 if (f == NULL) {
578 debug("unable to read %s", path);
579 return false;
580 }
581 if (fseek(f, -2, SEEK_END) == -1) {
582 fclose(f);
583 debug("unable to seek %s: %s", path, strerror(errno));
584 return false;
585 }
586
587 int c = fgetc(f);
588 if (c == EOF) {
589 debug("EOF for %s: %s", path, strerror(errno));
590 fclose(f);
591 return false;
592 }
593 fclose(f);
594
595 bool available = c == (unsigned char)'1';
596 if (available) {
597 debug("%s available", feature);
598 return true;
599 } else {
600 debug("%s not available", feature);
601 return false;
602 }
603 }
604
605 void
define(const char * prefix,const char * name,const char * value)606 define(const char *prefix, const char *name, const char *value)
607 {
608 fputs("#define ", this.config_h);
609 fputs(prefix, this.config_h);
610 fputs(name, this.config_h);
611 fputs(" ", this.config_h);
612 fputs(value, this.config_h);
613 fputs("\n", this.config_h);
614 }
615
616 void
info(const char * format,...)617 info(const char *format, ...)
618 {
619 va_list ap;
620 va_start(ap, format);
621 vfprintf(this.info, format, ap);
622 va_end(ap);
623 fputs("\n", this.info);
624 fflush(this.info);
625 if (this.log) {
626 fputs("=> ", this.log);
627 va_start(ap, format);
628 vfprintf(this.log, format, ap);
629 va_end(ap);
630 fputs("\n", this.log);
631 fflush(this.log);
632 }
633 }
634
635 void
debug(const char * format,...)636 debug(const char *format, ...)
637 {
638 if (this.log) {
639 va_list ap;
640 va_start(ap, format);
641 vfprintf(this.log, format, ap);
642 va_end(ap);
643 fputs("\n", this.log);
644 fflush(this.log);
645 }
646 }
647
648 int
run(struct Array * argv)649 run(struct Array *argv)
650 {
651 if (this.log) {
652 fputs("==> Executing '", this.log);
653 for (size_t i = 0; i < array_len(argv); i++) {
654 fputs(array_get(argv, i), this.log);
655 if (i == array_len(argv) - 1) {
656 fputs("'\n", this.log);
657 } else {
658 fputc(' ', this.log);
659 }
660 }
661 }
662 struct Array *args = array_join(array_new(), argv);
663 array_append(args, NULL);
664
665 posix_spawn_file_actions_t actions;
666 posix_spawn_file_actions_init(&actions);
667 posix_spawn_file_actions_addclose(&actions, STDIN_FILENO);
668 if (this.log) {
669 posix_spawn_file_actions_adddup2(&actions, fileno(this.log), STDERR_FILENO);
670 posix_spawn_file_actions_adddup2(&actions, fileno(this.log), STDOUT_FILENO);
671 } else {
672 posix_spawn_file_actions_addclose(&actions, STDERR_FILENO);
673 posix_spawn_file_actions_addclose(&actions, STDOUT_FILENO);
674 }
675
676 pid_t pid;
677 if (posix_spawnp(&pid, array_get(args, 0), &actions, NULL, (char **)args->buf, environ) != 0) {
678 debug("[FAILED: %s]", strerror(errno));
679 return 1;
680 }
681
682 int status = 1;
683 if (waitpid(pid, &status, 0) < 0) {
684 debug("[FAILED: %s]", strerror(errno));
685 return 1;
686 } else if (WIFEXITED(status)) {
687 debug("[status: %d]", WEXITSTATUS(status));
688 return WEXITSTATUS(status);
689 } else {
690 debug("[FAILED]");
691 return 1;
692 }
693 }
694
695 enum LTOType
test_ltotoolchain(struct Array * cc,struct Array * ar)696 test_ltotoolchain(struct Array *cc, struct Array *ar)
697 {
698 if (test_ltotoolchain_helper(LTO_THIN, cc, ar)) {
699 return LTO_THIN;
700 }
701
702 if (test_ltotoolchain_helper(LTO_FULL, cc, ar)) {
703 return LTO_FULL;
704 }
705
706 return LTO_DISABLED;
707 }
708
709 static struct Array *
ar_candidate(const char * path,const char * tool,struct Array * candidate)710 ar_candidate(const char *path, const char *tool, struct Array *candidate)
711 {
712 if (!strchr(path, '/')) {
713 if (str_startswith(path, tool)) {
714 char *buf = str_printf("%s%s", array_get(candidate, 0), path + strlen(tool));
715 if (which(buf)) {
716 return array_append(array_new(), buf);
717 }
718 }
719 return NULL;
720 } else {
721 char *tmp = strdup(path);
722 char *base = basename(tmp);
723 char *dir = dirname(tmp);
724 if (str_startswith(base, tool)) {
725 char *buf = str_printf("%s/%s%s", dir, array_get(candidate, 0), base + strlen(tool));
726 if (which(buf)) {
727 free(tmp);
728 return array_append(array_new(), buf);
729 }
730 }
731 free(tmp);
732 return NULL;
733 }
734 }
735
736 bool
ltotoolchain()737 ltotoolchain()
738 {
739 debug("=> LTO toolchain test");
740
741 struct Array *cc = this.toolchain.cc;
742 struct Array *ar = this.toolchain.ar;
743 enum LTOType type;
744
745 if (LTO_DISABLED != (type = test_ltotoolchain(cc, ar))) {
746 goto found;
747 }
748
749 if (!this.auto_lto) {
750 return false;
751 }
752
753 if ((ar = ar_candidate(array_get(cc, 0), "cc", array_append(array_new(), "llvm-ar"))) &&
754 (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
755 goto found;
756 }
757
758 if ((ar = ar_candidate(array_get(cc, 0), "cc", array_append(array_new(), "gcc-ar"))) &&
759 (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
760 goto found;
761 }
762
763 if ((ar = ar_candidate(array_get(cc, 0), "clang", array_append(array_new(), "llvm-ar"))) &&
764 (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
765 goto found;
766 }
767
768 if ((ar = ar_candidate(array_get(cc, 0), "gcc", array_append(array_new(), "gcc-ar"))) &&
769 (LTO_DISABLED != (type = test_ltotoolchain(cc, ar)))) {
770 goto found;
771 }
772
773 return false;
774
775 found:
776 this.toolchain.lto = type;
777 this.toolchain.ar = ar;
778 this.toolchain.cc = cc;
779
780 return true;
781 }
782
783 void
system_features()784 system_features()
785 {
786 info("checking system features...");
787
788 FILE *config_ninja = fopen("config.ninja", "w");
789 if (config_ninja == NULL) {
790 fprintf(stderr, "%s: cannot open %s/config.ninja: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
791 exit(1);
792 }
793
794 fprintf(config_ninja, "mkbuild = %s\n", this.mkbuild_src);
795 fprintf(config_ninja, "builddir = %s/.mkbuild\n", this.builddir);
796 fputs(mkbuild_configure_rules, config_ninja);
797 fprintf(config_ninja, "CC = %s\n", (const char *)array_get(this.toolchain.cc, 0));
798 for (size_t i = 0; i < nitems(tests); i++) {
799 fprintf(config_ninja, "build $builddir/test-$name: mkbuild-check $mkbuild\n name = %s\n var = %s\n",
800 tests[i], str_toupper(tests[i]));
801 fputs(" ldadd = ", config_ninja);
802 for (size_t j = 0; j < nitems(tests_flags); j++) {
803 if (strcmp(tests[i], tests_flags[j].name) == 0) {
804 for (size_t k = 0; k < nitems(tests_flags[j].ldadd) && tests_flags[j].ldadd[k]; k++) {
805 fputs(tests_flags[j].ldadd[k], config_ninja);
806 fputs(" ", config_ninja);
807 }
808 break;
809 }
810 }
811 fputs("\n", config_ninja);
812 }
813
814 fputs("build $builddir/system_features.h: mkbuild-config", config_ninja);
815 for (size_t i = 0; i < nitems(tests); i++) {
816 fputs(" $builddir/test-", config_ninja);
817 fputs(tests[i], config_ninja);
818 }
819 fputs("\n", config_ninja);
820 fclose(config_ninja);
821
822 configure();
823 }
824
825 void
configure()826 configure()
827 {
828 setenv("NINJA_STATUS", "", true);
829 setenv("SAMUFLAGS", "", true);
830
831 posix_spawn_file_actions_t actions;
832 posix_spawn_file_actions_init(&actions);
833 posix_spawn_file_actions_addclose(&actions, STDIN_FILENO);
834
835 const char *args[] = { "ninja", "-f", "config.ninja", NULL };
836 if (this.ninja) {
837 args[0] = this.ninja;
838 }
839 pid_t pid;
840 debug("==> Executing '%s -f config.ninja'", args[0]);
841 if (posix_spawnp(&pid, args[0], &actions, NULL, (char **)args, environ) != 0) {
842 if (!this.ninja && (errno == EACCES || errno == ENOENT || errno == EEXIST)) {
843 debug("==> ninja failed to run: %s", strerror(errno));
844 args[0] = "samu";
845 debug("==> Executing '%s -f config.ninja'", args[0]);
846 if (posix_spawnp(&pid, args[0], &actions, NULL, (char **)args, environ) != 0) {
847 goto error;
848 }
849 } else {
850 goto error;
851 }
852 }
853
854 int status = 1;
855 if (waitpid(pid, &status, 0) >= 0 && WIFEXITED(status)) {
856 debug("[status: %d]", WEXITSTATUS(status));
857 if (WEXITSTATUS(status) == 0) {
858 return;
859 } else {
860 fprintf(stderr, "config.ninja failed: status %d\n", WEXITSTATUS(status));
861 exit(1);
862 }
863 }
864
865 error:
866 fprintf(stderr, "'%s -f config.ninja' failed: %s\n", args[0], strerror(errno));
867 exit(1);
868 }
869
870 void
pkg_config()871 pkg_config()
872 {
873 if (array_len(this.pkg_config_modules) == 0) {
874 FILE *f = fopen("pkgconf.ninja", "w");
875 if (f == NULL) {
876 fprintf(stderr, "cannot open %s/.mkbuild/pkgconf.ninja: %s\n", this.builddir, strerror(errno));
877 exit(1);
878 }
879 fclose(f);
880 return;
881 }
882
883 info("checking for modules...");
884
885 FILE *config_ninja = fopen("config.ninja", "w");
886 if (config_ninja == NULL) {
887 fprintf(stderr, "%s: cannot open %s/config.ninja: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
888 exit(1);
889 }
890
891 #ifdef __FreeBSD__
892 FILE *libcrypto = fopen("libcrypto.pc", "w");
893 if (libcrypto == NULL) {
894 fprintf(stderr, "%s: cannot open %s/libcrypto.pc: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
895 exit(1);
896 }
897 fputs(libcrypto_pc, libcrypto);
898 fclose(libcrypto);
899
900 FILE *libssl = fopen("libssl.pc", "w");
901 if (libssl == NULL) {
902 fprintf(stderr, "%s: cannot open %s/libssl.pc: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
903 exit(1);
904 }
905 fputs(libssl_pc, libssl);
906 fclose(libssl);
907
908 FILE *openssl = fopen("openssl.pc", "w");
909 if (openssl == NULL) {
910 fprintf(stderr, "%s: cannot open %s/openssl.pc: %s\n", this.arg0, getcwd(NULL, 0), strerror(errno));
911 exit(1);
912 }
913 fputs(openssl_pc, openssl);
914 fclose(openssl);
915 #endif
916
917 fprintf(config_ninja, "builddir = %s/.mkbuild\n", this.builddir);
918 fprintf(config_ninja, "PKG_CONFIG = %s\n", this.pkg_config);
919 fputs(mkbuild_pkgconf_rules, config_ninja);
920 for (size_t i = 0; i < array_len(this.pkg_config_modules); i++) {
921 const char *module = array_get(this.pkg_config_modules, i);
922 fprintf(config_ninja, "build $builddir/pkgconf-cflags-$name: mkbuild-pkgconf-cflags\n");
923 fprintf(config_ninja, " name = %s\n", module);
924 fprintf(config_ninja, "build $builddir/pkgconf-ldadd-$name: mkbuild-pkgconf-ldadd\n");
925 fprintf(config_ninja, " name = %s\n", module);
926 fprintf(config_ninja, "build $builddir/pkgconf-ldadd-static-$name: mkbuild-pkgconf-ldadd-static\n");
927 fprintf(config_ninja, " name = %s\n", module);
928 }
929 fputs("build $builddir/pkgconf.ninja: mkbuild-pkgconf-config", config_ninja);
930 for (size_t i = 0; i < array_len(this.pkg_config_modules); i++) {
931 const char *module = array_get(this.pkg_config_modules, i);
932 fprintf(config_ninja, " $builddir/pkgconf-cflags-%s $builddir/pkgconf-ldadd-%s $builddir/pkgconf-ldadd-static-%s",
933 module, module, module);
934 }
935 fputs("\n", config_ninja);
936 fclose(config_ninja);
937
938 configure();
939 }
940
941 bool
test_ltotoolchain_helper(enum LTOType lto,struct Array * cc,struct Array * ar)942 test_ltotoolchain_helper(enum LTOType lto, struct Array *cc, struct Array *ar)
943 {
944 bool ok = false;
945 const char *cppflag = "-DTEST_SANITY=1";
946 const char *ltoarg = NULL;
947 switch (lto) {
948 case LTO_DISABLED:
949 break;
950 case LTO_FULL:
951 ltoarg = "-flto";
952 break;
953 case LTO_THIN:
954 ltoarg = "-flto=thin";
955 break;
956 }
957
958 struct Array *test0_args = array_join(array_new(), cc);
959 array_joinv(test0_args, (void **)default_gcc_cflags, nitems(default_gcc_cflags));
960 if (ltoarg) {
961 array_append(test0_args, ltoarg);
962 }
963 const char *src_file = this.mkbuild_src;
964 const char *object_file = "test-lto.o";
965 array_append(test0_args, "-c");
966 array_append(test0_args, "-o");
967 array_append(test0_args, object_file);
968 array_append(test0_args, cppflag);
969 array_append(test0_args, src_file);
970
971 struct Array *test1_args = NULL;
972 const char *archive = "libtest-lto.a";
973 test1_args = array_join(array_new(), ar);
974 array_append(test1_args, "rcs");
975 array_append(test1_args, archive);
976 array_append(test1_args, object_file);
977
978 struct Array *test2_args = array_join(array_new(), cc);
979 array_joinv(test2_args, (void **)default_gcc_ldflags, nitems(default_gcc_ldflags));
980 if (ltoarg) {
981 array_append(test2_args, ltoarg);
982 }
983 array_append(test2_args, "-o");
984 array_append(test2_args, "test-lto");
985 array_append(test2_args, archive);
986
987 if (run(test0_args) != 0) {
988 goto fail;
989 }
990 if (run(test1_args) != 0) {
991 goto fail;
992 }
993 if (run(test2_args) != 0) {
994 goto fail;
995 }
996
997 if (run(array_append(array_new(), "./test-lto")) == 0) {
998 ok = true;
999 }
1000
1001 fail:
1002 unlink(object_file);
1003 unlink(archive);
1004 unlink("test-lto");
1005
1006 return ok;
1007 }
1008
1009 void
spec_build(struct Spec * spec,const char * rule,struct Array * outputs,struct Array * inputs)1010 spec_build(struct Spec *spec, const char *rule, struct Array *outputs, struct Array *inputs)
1011 {
1012 fputs("build", this.build_ninja);
1013 if (outputs) {
1014 for (size_t i = 0; i < array_len(outputs); i++) {
1015 fputs(" ", this.build_ninja);
1016 fputs(array_get(outputs, i), this.build_ninja);
1017 }
1018 }
1019 fprintf(this.build_ninja, ": %s", rule);
1020 if (inputs) {
1021 for (size_t i = 0; i < array_len(inputs); i++) {
1022 fputs(" ", this.build_ninja);
1023 fputs(array_get(inputs, i), this.build_ninja);
1024 }
1025 }
1026 fputs("\n", this.build_ninja);
1027
1028 if (strcmp(rule, "phony") != 0) {
1029 for (size_t i = 0; i < array_len(spec->vars); i++) {
1030 spec_var(array_get(spec->vars, i), false);
1031 }
1032 }
1033 }
1034
1035 void
spec_cc(struct Spec * spec)1036 spec_cc(struct Spec *spec)
1037 {
1038 for (size_t i = 0; i < array_len(spec->files); i++) {
1039 struct SpecFile *f = array_get(spec->files, i);
1040 if (str_endswith(f->src, ".c")) {
1041 spec_build(spec, "cc", array_append(array_new(), f->obj), array_append(array_new(), f->src));
1042 spec_var(&(struct SpecVar){"name", array_append(array_new(), f->name)}, false);
1043 }
1044 }
1045 }
1046
1047 void
spec_var(struct SpecVar * var,bool global)1048 spec_var(struct SpecVar *var, bool global)
1049 {
1050 if (!global) {
1051 fputs(" ", this.build_ninja);
1052 }
1053 fprintf(this.build_ninja, "%s =", var->name);
1054 for (size_t i = 0; i < array_len(var->words); i++) {
1055 fputs(" ", this.build_ninja);
1056 fputs(array_get(var->words, i), this.build_ninja);
1057 }
1058 fputs("\n", this.build_ninja);
1059 }
1060
1061 void
spec_flush(struct Spec * spec)1062 spec_flush(struct Spec *spec)
1063 {
1064 switch (spec->mode) {
1065 case SPEC_NONE:
1066 case SPEC_NINJA:
1067 break;
1068 case SPEC_BIN:
1069 case SPEC_TOOL: {
1070 struct Array *inputs = array_new();
1071 for (size_t i = 0; i < array_len(spec->files); i++) {
1072 struct SpecFile *f = array_get(spec->files, i);
1073 array_append(inputs, f->obj);
1074 }
1075 const char *subdir = ".bin";
1076 if (spec->mode == SPEC_TOOL) {
1077 subdir = ".tool";
1078 }
1079 struct Array *outputs = array_append(array_new(), str_printf("$builddir/%s/%s", subdir, spec->name));
1080 spec_build(spec, "bin", outputs, inputs);
1081 spec_var(&(struct SpecVar){"name", array_append(array_new(), spec->name)}, false);
1082 spec_build(spec, "phony", array_append(array_new(), spec->name), outputs);
1083 spec_cc(spec);
1084 if (spec->mode == SPEC_BIN) {
1085 array_append(spec->defaults, strdup(spec->name));
1086 const char *target = str_printf("$DESTDIR$BINDIR/%s", spec->name);
1087 array_append(spec->install, target);
1088 spec_build(spec, "install-program", array_append(array_new(), target), outputs);
1089 spec_var(&(struct SpecVar){"name", array_append(array_new(), str_printf("%s $DESTDIR$BINDIR", spec->name))}, false);
1090 }
1091 break;
1092 } case SPEC_BUNDLE: {
1093 struct Array *outputs = array_append(array_new(), str_printf("$builddir/%s", spec->name));
1094 struct Array *inputs = array_new();
1095 for (size_t i = 0; i < array_len(spec->files); i++) {
1096 struct SpecFile *f = array_get(spec->files, i);
1097 array_append(inputs, f->obj);
1098 }
1099 spec_build(spec, "bundle", outputs, inputs);
1100 spec_var(&(struct SpecVar){"name", array_append(array_new(), spec->name)}, false);
1101 spec_build(spec, "phony", array_append(array_new(), spec->name), outputs);
1102 array_append(spec->defaults, strdup(spec->name));
1103 spec_cc(spec);
1104 break;
1105 } case SPEC_DEFAULT_FEATURES:
1106 for (size_t i = 0; i < array_len(spec->files); i++) {
1107 struct SpecFile *f = array_get(spec->files, i);
1108 struct Array *features = array_new();
1109 array_append(features, f->name);
1110 array_join(features, this.features);
1111 this.features = features;
1112 }
1113 break;
1114 case SPEC_IF:
1115 if (has_feature(spec->name)) {
1116 for (size_t i = 0; i < array_len(spec->vars); i++) {
1117 spec_var(array_get(spec->vars, i), true);
1118 }
1119 }
1120 break;
1121 case SPEC_GEN: {
1122 struct Array *inputs = array_new();
1123 for (size_t i = 0; i < array_len(spec->files); i++) {
1124 struct SpecFile *f = array_get(spec->files, i);
1125 array_append(inputs, f->src);
1126 }
1127 array_append(inputs, "|");
1128 array_append(inputs, spec->generator);
1129 spec_build(spec, "gen", array_append(array_new(), spec->name), inputs);
1130 spec_var(&(struct SpecVar){"name", array_append(array_new(), spec->name)}, false);
1131 if (str_endswith(spec->generator, ".awk")) {
1132 spec_var(&(struct SpecVar){"generator", array_append(array_append(array_append(array_new(), "$AWK"), "-f"), spec->generator)}, false);
1133 } else {
1134 spec_var(&(struct SpecVar){"generator", array_append(array_new(), spec->generator)}, false);
1135 }
1136 break;
1137 } case SPEC_INSTALL_DATA:
1138 for (size_t i = 0; i < array_len(spec->files); i++) {
1139 struct SpecFile *f = array_get(spec->files, i);
1140 const char *dest = str_printf("$DESTDIR$SHAREDIR/%s/%s", spec->name, f->name);
1141 spec_build(spec, "install-data", array_append(array_new(), dest), array_append(array_new(), f->src));
1142 spec_var(&(struct SpecVar){"name", array_append(array_new(), str_printf("%s %s", f->name, dest))}, false);
1143 array_append(spec->install, dest);
1144 }
1145 break;
1146 case SPEC_INSTALL_MAN:
1147 for (size_t i = 0; i < array_len(spec->files); i++) {
1148 struct SpecFile *f = array_get(spec->files, i);
1149 if (strlen(f->src) > 2 &&
1150 f->src[strlen(f->src) - 2] == '.' &&
1151 isdigit((unsigned char)f->src[strlen(f->src) - 1])) {
1152 const char category = f->src[strlen(f->src) - 1];
1153 char *base = basename(strdup(f->src));
1154 const char *dest = str_printf("$DESTDIR$MANDIR/man%c/%s", category, base);
1155 spec_build(spec, "install-man", array_append(array_new(), dest), array_append(array_new(), f->src));
1156 spec_var(&(struct SpecVar){"name", array_append(array_new(), str_printf("%s %s", f->name, dest))}, false);
1157 array_append(spec->install, dest);
1158 }
1159 }
1160 break;
1161 case SPEC_PKG_CONFIG:
1162 for (size_t i = 0; i < array_len(spec->files); i++) {
1163 struct SpecFile *f = array_get(spec->files, i);
1164 array_append(this.pkg_config_modules, f->name);
1165 }
1166 break;
1167 case SPEC_TESTS:
1168 for (size_t i = 0; i < array_len(spec->files); i++) {
1169 struct SpecFile *f = array_get(spec->files, i);
1170 if (strlen(f->obj) > 2) {
1171 const char *testbin = strndup(f->obj, strlen(f->obj) - 2);
1172 if (strlen(testbin) > strlen("$builddir/")) {
1173 spec_build(spec, "bin", array_append(array_new(), testbin), array_append(array_append(array_new(), f->obj), spec->name));
1174 const char *testbinrel = testbin + strlen("$builddir/");
1175 spec_var(&(struct SpecVar){"name", array_append(array_new(), testbinrel)}, false);
1176 const char *stamp = str_printf("%s.stamp", testbin);
1177 spec_build(spec, "mkbuild-test", array_append(array_new(), stamp), array_append(array_new(), testbin));
1178 spec_var(&(struct SpecVar){"name", array_append(array_new(), testbinrel)}, false);
1179 spec_build(spec, "phony", array_append(array_new(), testbinrel), array_append(array_new(), stamp));
1180 array_append(spec->testbins, stamp);
1181 }
1182 }
1183 }
1184 spec_cc(spec);
1185 break;
1186 }
1187
1188 spec->mode = SPEC_NONE;
1189 spec->name = "";
1190 spec->generator = "";
1191
1192 array_truncate(spec->files);
1193 array_truncate(spec->vars);
1194 }
1195
1196 void
spec_write()1197 spec_write()
1198 {
1199 fprintf(this.build_ninja, "builddir = %s\nsrcdir = %s\nsubdir = $srcdir\nmkbuild_src = %s\n%s", this.builddir, this.srcdir, this.mkbuild_src, mkbuild_rules);
1200
1201 struct Spec spec = {
1202 .defaults = array_new(),
1203 .install = array_new(),
1204 .testbins = array_new(),
1205
1206 .files = array_new(),
1207 .vars = array_new(),
1208 .mode = SPEC_NONE,
1209 .name = "",
1210 .generator = "",
1211 };
1212
1213 char *line = NULL;
1214 size_t linecap = 0;
1215 ssize_t linelen;
1216 size_t linecnt = 0;
1217 while ((linelen = getline(&line, &linecap, this.build_ninja_spec)) > 0) {
1218 linecnt++;
1219 if (linelen > 0 && line[linelen - 1] == '\n') {
1220 line[linelen - 1] = 0;
1221 linelen--;
1222 }
1223
1224 // Tokenize into fields similar to awk
1225 char *$[MKBUILD_FIELD_MAX];
1226 for (size_t i = 0; i < MKBUILD_FIELD_MAX; i++) {
1227 $[i] = "";
1228 }
1229 size_t NF = 1;
1230 $[0] = strdup(line);
1231 char *token;
1232 char *_tok = line;
1233 while (NF < MKBUILD_FIELD_MAX && (token = strtok(_tok, " \t")) != NULL) {
1234 _tok = NULL;
1235 if (strcmp(token, "") != 0) {
1236 $[NF++] = token;
1237 }
1238 }
1239
1240 if (str_startswith($[1], "#")) {
1241 continue;
1242 } else if (strcmp($[0], "") == 0) {
1243 continue;
1244 } else if (str_startswith($[0], "\t")) {
1245 if (spec.mode == SPEC_NINJA) {
1246 fprintf(this.build_ninja, "%s\n", $[0] + 1);
1247 } else if (strcmp($[2], "=") == 0 || strcmp($[2], "+=") == 0) {
1248 struct SpecVar *v = malloc(sizeof(struct SpecVar));
1249 v->name = strdup($[1]);
1250 v->words = array_new();
1251 if (strcmp($[2], "+=") == 0) {
1252 array_append(v->words, str_printf("$%s", v->name));
1253 }
1254 for (size_t i = 3; i < NF; i++) {
1255 array_append(v->words, strdup($[i]));
1256 }
1257 array_append(spec.vars, v);
1258 } else {
1259 struct SpecFile *f = malloc(sizeof(struct SpecFile));
1260 f->name = strdup($[1]);
1261 if (str_startswith($[1], "$builddir/") || str_startswith($[1], "$srcdir/")) {
1262 f->src = strdup($[1]);
1263 f->obj = strdup($[1]);
1264 } else {
1265 f->src = str_printf("$srcdir/%s", $[1]);
1266 f->obj = str_printf("$builddir/%s", $[1]);
1267 }
1268 if (str_endswith(f->obj, ".c")) {
1269 f->obj[strlen(f->obj) - 1] = 'o';
1270 }
1271 array_append(spec.files, f);
1272 }
1273 } else if (strcmp($[1], "default") == 0) {
1274 fprintf(this.build_ninja, "%s\n", $[0]);
1275 for (size_t i = 2; i < NF; i++) {
1276 array_append(spec.defaults, strdup($[i]));
1277 }
1278 } else if (strcmp($[1], "default-install") == 0) {
1279 for (size_t i = 2; i < NF; i++) {
1280 array_append(spec.install, strdup($[i]));
1281 }
1282 } else if (strcmp($[1], "include") == 0 || strcmp($[1], "subninja") == 0 || strcmp($[2], "=") == 0) {
1283 fprintf(this.build_ninja, "%s\n", $[0]);
1284 } else if (strcmp($[2], "+=") == 0) {
1285 fputs($[1], this.build_ninja);
1286 fputs(" = $", this.build_ninja);
1287 fputs($[1], this.build_ninja);
1288 for (size_t i = 3; i < NF; i++) {
1289 fputs(" ", this.build_ninja);
1290 fputs($[i], this.build_ninja);
1291 }
1292 fputs("\n", this.build_ninja);
1293 } else {
1294 spec_flush(&spec);
1295 if (strcmp($[1], "ninja") == 0) {
1296 spec.mode = SPEC_NINJA;
1297 } else if (strcmp($[1], "bin") == 0) {
1298 spec.mode = SPEC_BIN;
1299 } else if (strcmp($[1], "bundle") == 0) {
1300 spec.mode = SPEC_BUNDLE;
1301 } else if (strcmp($[1], "default-features") == 0) {
1302 spec.mode = SPEC_DEFAULT_FEATURES;
1303 } else if (strcmp($[1], "if") == 0) {
1304 spec.mode = SPEC_IF;
1305 } else if (strcmp($[1], "gen") == 0) {
1306 spec.mode = SPEC_GEN;
1307 } else if (strcmp($[1], "install-data") == 0) {
1308 spec.mode = SPEC_INSTALL_DATA;
1309 } else if (strcmp($[1], "install-man") == 0) {
1310 spec.mode = SPEC_INSTALL_MAN;
1311 } else if (strcmp($[1], "pkg-config") == 0) {
1312 spec.mode = SPEC_PKG_CONFIG;
1313 } else if (strcmp($[1], "tests") == 0) {
1314 spec.mode = SPEC_TESTS;
1315 } else if (strcmp($[1], "tool") == 0) {
1316 spec.mode = SPEC_TOOL;
1317 } else {
1318 fprintf(stderr, "unknown mode on line %zu\n", linecnt);
1319 exit(1);
1320 }
1321
1322 spec.name = strdup($[2]);
1323 if (spec.mode == SPEC_GEN) {
1324 if (strcmp($[3], "") == 0) {
1325 fprintf(stderr, "missing generator on line %zu\n", linecnt);
1326 exit(1);
1327 } else {
1328 spec.generator = strdup($[3]);
1329 }
1330 }
1331 }
1332 }
1333
1334 spec_flush(&spec);
1335 if (array_len(spec.defaults) > 0) {
1336 spec_build(&spec, "phony", array_append(array_new(), "all"), spec.defaults);
1337 fputs("default", this.build_ninja);
1338 for (size_t i = 0; i < array_len(spec.defaults); i++) {
1339 fputs(" ", this.build_ninja);
1340 fputs(array_get(spec.defaults, i), this.build_ninja);
1341 }
1342 fputs("\n", this.build_ninja);
1343 }
1344 if (array_len(spec.install) > 0) {
1345 spec_build(&spec, "phony", array_append(array_new(), "install"), spec.install);
1346 }
1347 if (array_len(spec.testbins) > 0) {
1348 spec_build(&spec, "phony", array_append(array_new(), "test"), spec.testbins);
1349 }
1350 }
1351
1352 int
main(int argc,char * argv[])1353 main(int argc, char *argv[])
1354 {
1355 this.arg0 = argv[0];
1356 this.args = array_new();
1357
1358 for (int i = 1; i < argc; i++) {
1359 bool valid = false;
1360 char *key = strdup(argv[i]);
1361 char *value = strstr(key, "=");
1362 if (value) {
1363 value[0] = 0;
1364 value++;
1365 bool append = false;
1366 if (str_endswith(key, "+")) {
1367 append = true;
1368 key[strlen(key) - 1] = 0;
1369 }
1370 for (size_t j = 0; j < nitems(mkbuild_settings); j++) {
1371 if (strcmp(key, mkbuild_settings[j].key) == 0) {
1372 valid = true;
1373 if (append && mkbuild_settings[j].value) {
1374 value = str_printf("%s %s", mkbuild_settings[j].value, escape_arg(value, false));
1375 } else {
1376 value = escape_arg(value, false);
1377 }
1378 mkbuild_settings[j].value = value;
1379 break;
1380 }
1381 }
1382 }
1383 if (!valid) {
1384 fprintf(stderr, "%s: invalid key-value: %s\n", this.arg0, argv[i]);
1385 return 1;
1386 }
1387 }
1388
1389 this.features = array_new();
1390 this.pkg_config = "pkg-config";
1391 this.pkg_config_modules = array_new();
1392 this.system_features = array_new();
1393 this.info = stderr;
1394 this.log = NULL;
1395
1396 this.toolchain.lto = LTO_DISABLED;
1397 this.auto_lto = true;
1398 this.try_lto = true;
1399 for (size_t i = 0; i < nitems(mkbuild_settings); i++) {
1400 const char *key = mkbuild_settings[i].key;
1401 const char *value = mkbuild_settings[i].value;
1402 if (value == NULL) {
1403 continue;
1404 } else if (strcmp(key, "AR") == 0) {
1405 this.toolchain.ar = str_split(value, " ");
1406 } else if (strcmp(key, "BUILDDIR") == 0) {
1407 this.builddir = strdup(value);
1408 } else if (strcmp(key, "FEATURES") == 0) {
1409 this.features = str_split(value, " ");
1410 } else if (strcmp(key, "LTO") == 0) {
1411 this.auto_lto = strcmp(value, "noauto") != 0;
1412 this.try_lto = strcmp(value, "0") != 0;
1413 } else if (strcmp(key, "NINJA") == 0) {
1414 this.ninja = strdup(value);
1415 } else if (strcmp(key, "PKG_CONFIG") == 0) {
1416 this.pkg_config = strdup(value);
1417 } else if (strcmp(key, "SRCDIR") == 0) {
1418 this.srcdir = strdup(value);
1419 } else if (strcmp(key, "CC") == 0) {
1420 this.toolchain.cc = str_split(value, " ");
1421 }
1422 }
1423
1424 this.mkbuild_src = str_printf("%s/mkbuild.c", getcwd(NULL, 0));
1425 if (this.builddir == NULL) {
1426 this.builddir = "_build";
1427 }
1428 if (this.srcdir == NULL) {
1429 this.srcdir = getcwd(NULL, 0);
1430 } else if (chdir(this.srcdir) == -1) {
1431 perror("chdir");
1432 exit(1);
1433 }
1434
1435 if ((this.build_ninja_spec = fopen("build.ninja.spec", "r")) == NULL) {
1436 fprintf(stderr, "cannot open %s/build.ninja.spec: %s\n", this.srcdir, strerror(errno));
1437 return 1;
1438 }
1439
1440 // The builddir was created by the configure script that
1441 // compiled mkbuild. We cd into it to get a normalized
1442 // path via getcwd.
1443 if (chdir(this.builddir) == -1) {
1444 perror("chdir");
1445 exit(1);
1446 }
1447 this.builddir = getcwd(NULL, 0);
1448 info("builddir: %s", this.builddir);
1449
1450 if ((this.config_h = fopen("config.h", "w")) == NULL) {
1451 fprintf(stderr, "cannot open %s/config.h: %s\n", this.builddir, strerror(errno));
1452 exit(1);
1453 }
1454
1455 if ((this.build_ninja = fopen("build.ninja", "w")) == NULL) {
1456 fprintf(stderr, "cannot open %s/build.ninja: %s\n", this.builddir, strerror(errno));
1457 return 1;
1458 }
1459
1460 // Go into $builddir/.mkbuild where we will stash
1461 // our temporary files.
1462 if (mkdir(".mkbuild", 0755) == -1 && errno != EEXIST) {
1463 perror("mkdir");
1464 exit(1);
1465 }
1466 if (chdir(".mkbuild") == -1) {
1467 perror("chdir");
1468 exit(1);
1469 }
1470
1471 if ((this.log = fopen("config.log", "a")) == NULL) {
1472 fprintf(stderr, "cannot open %s/.mkbuild/config.log: %s\n", this.builddir, strerror(errno));
1473 return 1;
1474 }
1475
1476 if (this.try_lto) {
1477 ltotoolchain();
1478 }
1479 switch (this.toolchain.lto) {
1480 case LTO_DISABLED:
1481 info("lto: disabled");
1482 break;
1483 case LTO_FULL:
1484 info("lto: full");
1485 break;
1486 case LTO_THIN:
1487 info("lto: thin");
1488 break;
1489 }
1490 info("ar: %s", array_get(this.toolchain.ar, 0));
1491 info("cc: %s", array_get(this.toolchain.cc, 0));
1492
1493 system_features();
1494 fprintf(this.config_h, "#pragma once\n#include \"%s/.mkbuild/system_features.h\"\n", this.builddir);
1495 fprintf(this.config_h, "#define __MKBUILD_CONFIG_H__ 1\n#include \"%s\"\n#undef __MKBUILD_CONFIG_H__\n", this.mkbuild_src);
1496
1497 if (has_system_feature("seccomp_filter")) {
1498 struct utsname name;
1499 if (uname(&name) == 0) {
1500 if (strcmp(name.machine, "x86_64") == 0) {
1501 define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_X86_64");
1502 } else if (strlen(name.machine) == 4 && name.machine[0] == 'i' && name.machine[2] == '8' && name.machine[3] == '6') {
1503 define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_I386");
1504 } else if (str_startswith(name.machine, "arm")) {
1505 define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_ARM");
1506 } else if (strcmp(name.machine, "aarch64") == 0) {
1507 define("", "SECCOMP_AUDIT_ARCH", "AUDIT_ARCH_AARCH64");
1508 }
1509 }
1510 }
1511
1512 for(size_t i = 0; i < nitems(mkbuild_settings); i++) {
1513 const char *value = mkbuild_settings[i].value;
1514 if (!value) {
1515 value = "";
1516 }
1517 fprintf(this.build_ninja, "%s = %s\n", mkbuild_settings[i].key, value);
1518 }
1519 fputs("CFLAGS =", this.build_ninja);
1520 for (size_t i = 0; i < nitems(default_gcc_cflags); i++) {
1521 fputs(" ", this.build_ninja);
1522 fputs(default_gcc_cflags[i], this.build_ninja);
1523 }
1524 switch (this.toolchain.lto) {
1525 case LTO_DISABLED:
1526 break;
1527 case LTO_FULL:
1528 fputs(" -flto", this.build_ninja);
1529 break;
1530 case LTO_THIN:
1531 fputs(" -flto=thin", this.build_ninja);
1532 break;
1533 }
1534 fputs(" $CFLAGS\n", this.build_ninja);
1535 fputs("LDFLAGS =", this.build_ninja);
1536 for (size_t i = 0; i < nitems(default_gcc_ldflags); i++) {
1537 fputs(" ", this.build_ninja);
1538 fputs(default_gcc_ldflags[i], this.build_ninja);
1539 }
1540 switch (this.toolchain.lto) {
1541 case LTO_DISABLED:
1542 break;
1543 case LTO_FULL:
1544 fputs(" -flto", this.build_ninja);
1545 break;
1546 case LTO_THIN:
1547 fputs(" -flto=thin", this.build_ninja);
1548 break;
1549 }
1550 fputs(" $LDFLAGS\n", this.build_ninja);
1551 fputs("AR =", this.build_ninja);
1552 for (size_t i = 0; i < array_len(this.toolchain.ar); i++) {
1553 fputs(" ", this.build_ninja);
1554 fputs(array_get(this.toolchain.ar, i), this.build_ninja);
1555 }
1556 fputs("\nCC =", this.build_ninja);
1557 for (size_t i = 0; i < array_len(this.toolchain.cc); i++) {
1558 fputs(" ", this.build_ninja);
1559 fputs(array_get(this.toolchain.cc, i), this.build_ninja);
1560 }
1561 fputs("\n", this.build_ninja);
1562
1563 for (size_t i = 0; i < nitems(tests_flags); i++) {
1564 if (has_system_feature(tests_flags[i].prefix)) {
1565 continue;
1566 } else if (has_system_feature(tests_flags[i].name)) {
1567 fprintf(this.build_ninja, "LDADD_%s", str_toupper(tests_flags[i].prefix));
1568 fputs(" = ", this.build_ninja);
1569 for (size_t j = 0; j < nitems(tests_flags[i].ldadd) && tests_flags[i].ldadd[j]; j++) {
1570 fputs(tests_flags[i].ldadd[j], this.build_ninja);
1571 fputs(" ", this.build_ninja);
1572 }
1573 fputs("\n", this.build_ninja);
1574 }
1575 }
1576
1577 fprintf(this.build_ninja, "include %s/.mkbuild/pkgconf.ninja\n", this.builddir);
1578
1579 spec_write();
1580
1581 fputs("build $builddir/config.h: configure $srcdir/configure $srcdir/build.ninja.spec $mkbuild_src\n", this.build_ninja);
1582 fputs(" configure_args =", this.build_ninja);
1583 for (int i = 1; i < argc; i++) {
1584 fputs(" ", this.build_ninja);
1585 fputs(escape_arg(argv[i], true), this.build_ninja);
1586 }
1587 fputs("\n", this.build_ninja);
1588
1589 pkg_config();
1590
1591 info("ready.");
1592
1593 fclose(this.config_h);
1594 fclose(this.build_ninja);
1595 fclose(this.build_ninja_spec);
1596 fclose(this.info);
1597 fclose(this.log);
1598
1599 return 0;
1600 }
1601 #endif /* MKBUILD */
1602 #if MKBUILD_WHICH
1603 // Based on: http://git.suckless.org/sbase/commit/7315b8686f3fcbf213113247bea980b0548ec66a.html
1604 //
1605 // MIT/X Consortium License
1606 //
1607 // © 2011 Connor Lane Smith <cls@lubutu.com>
1608 // © 2011-2016 Dimitris Papastamos <sin@2f30.org>
1609 // © 2014-2016 Laslo Hunhold <dev@frign.de>
1610 //
1611 // Permission is hereby granted, free of charge, to any person obtaining a
1612 // copy of this software and associated documentation files (the "Software"),
1613 // to deal in the Software without restriction, including without limitation
1614 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
1615 // and/or sell copies of the Software, and to permit persons to whom the
1616 // Software is furnished to do so, subject to the following conditions:
1617 //
1618 // The above copyright notice and this permission notice shall be included in
1619 // all copies or substantial portions of the Software.
1620 //
1621 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1622 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1623 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
1624 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1625 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
1626 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
1627 // DEALINGS IN THE SOFTWARE.
1628 //
1629 // Authors/contributors include:
1630 //
1631 // © 2011 Kamil Cholewiński <harry666t@gmail.com>
1632 // © 2011 Rob Pilling <robpilling@gmail.com>
1633 // © 2011 Hiltjo Posthuma <hiltjo@codemadness.org>
1634 // © 2011 pancake <pancake@youterm.com>
1635 // © 2011 Random832 <random832@fastmail.us>
1636 // © 2012 William Haddon <william@haddonthethird.net>
1637 // © 2012 Kurt H. Maier <khm@sciops.net>
1638 // © 2012 Christoph Lohmann <20h@r-36.net>
1639 // © 2012 David Galos <galosd83@students.rowan.edu>
1640 // © 2012 Robert Ransom <rransom.8774@gmail.com>
1641 // © 2013 Jakob Kramer <jakob.kramer@gmx.de>
1642 // © 2013 Anselm R Garbe <anselm@garbe.us>
1643 // © 2013 Truls Becken <truls.becken@gmail.com>
1644 // © 2013 dsp <dsp@2f30.org>
1645 // © 2013 Markus Teich <markus.teich@stusta.mhn.de>
1646 // © 2013 Jesse Ogle <jesse.p.ogle@gmail.com>
1647 // © 2013 Lorenzo Cogotti <miciamail@hotmail.it>
1648 // © 2013 Federico G. Benavento <benavento@gmail.com>
1649 // © 2013 Roberto E. Vargas Caballero <k0ga@shike2.com>
1650 // © 2013 Christian Hesse <mail@eworm.de>
1651 // © 2013 Markus Wichmann <nullplan@gmx.net>
1652 // © 2014 Silvan Jegen <s.jegen@gmail.com>
1653 // © 2014 Daniel Bainton <dpb@driftaway.org>
1654 // © 2014 Tuukka Kataja <stuge@xor.fi>
1655 // © 2014 Jeffrey Picard <jeff@jeffreypicard.com>
1656 // © 2014 Evan Gates <evan.gates@gmail.com>
1657 // © 2014 Michael Forney <mforney@mforney.org>
1658 // © 2014 Ari Malinen <ari.malinen@gmail.com>
1659 // © 2014 Brandon Mulcahy <brandon@jangler.info>
1660 // © 2014 Adria Garriga <rhaps0dy@installgentoo.com>
1661 // © 2014-2015 Greg Reagle <greg.reagle@umbc.edu>
1662 // © 2015 Tai Chi Minh Ralph Eastwood <tcmreastwood@gmail.com>
1663 // © 2015 Quentin Rameau <quinq@quinq.eu.org>
1664 // © 2015 Dionysis Grigoropoulos <info@erethon.com>
1665 // © 2015 Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
1666 // © 2016 Mattias Andrée <maandree@kth.se>
1667 // © 2016 Eivind Uggedal <eivind@uggedal.com>
1668
1669 static bool canexec(int, const char *);
1670
1671 bool
canexec(int fd,const char * name)1672 canexec(int fd, const char *name)
1673 {
1674 struct stat st;
1675
1676 if (fstatat(fd, name, &st, 0) < 0 || !S_ISREG(st.st_mode))
1677 return false;
1678 return faccessat(fd, name, X_OK, AT_EACCESS) == 0;
1679 }
1680
1681 bool
which(const char * name)1682 which(const char *name)
1683 {
1684 char *ptr, *p;
1685 size_t i, len;
1686 int dirfd;
1687 bool found = false;
1688
1689 if (strchr(name, '/')) {
1690 return canexec(AT_FDCWD, name);
1691 }
1692
1693 const char *path = getenv("PATH");
1694 if (!path)
1695 return false;
1696
1697 ptr = p = strdup(path);
1698 len = strlen(p);
1699 for (i = 0; i < len + 1; i++) {
1700 if (ptr[i] != ':' && ptr[i] != '\0')
1701 continue;
1702 ptr[i] = '\0';
1703 if ((dirfd = open(p, O_RDONLY)) >= 0) {
1704 if (canexec(dirfd, name)) {
1705 found = true;
1706 }
1707 close(dirfd);
1708 if (found)
1709 break;
1710 }
1711 p = ptr + i + 1;
1712 }
1713 free(ptr);
1714
1715 return found;
1716 }
1717 #endif /* MKBUILD_WHICH */
1718 #if TEST_SANITY
1719 int
main(int argc,char * argv[])1720 main(int argc, char *argv[])
1721 {
1722 return 0;
1723 }
1724 #endif /* TEST_SANITY */
1725 #if TEST___PROGNAME
1726 int
main(void)1727 main(void)
1728 {
1729 extern char *__progname;
1730
1731 return !__progname;
1732 }
1733 #endif /* TEST___PROGNAME */
1734 #if TEST_ARC4RANDOM
1735 #include <stdlib.h>
1736
1737 int
main(void)1738 main(void)
1739 {
1740 return (arc4random() + 1) ? 0 : 1;
1741 }
1742 #endif /* TEST_ARC4RANDOM */
1743 #if TEST_B64_NTOP || TEST_B64_NTOP_LDADD
1744 #include <netinet/in.h>
1745 #include <resolv.h>
1746
1747 int
main(void)1748 main(void)
1749 {
1750 const char *src = "hello world";
1751 char output[1024];
1752
1753 return b64_ntop((const unsigned char *)src, 11, output, sizeof(output)) > 0 ? 0 : 1;
1754 }
1755 #endif // TEST_B64_NTOP || TEST_B64_NTOP_LDADD
1756 #if TEST_CAPSICUM
1757 #include <sys/capsicum.h>
1758
1759 int
main(void)1760 main(void)
1761 {
1762 cap_enter();
1763 return(0);
1764 }
1765 #endif /* TEST_CAPSICUM */
1766 #if TEST_CRYPT || TEST_CRYPT_LDADD
1767 #if defined(__linux__)
1768 # define _GNU_SOURCE /* old glibc */
1769 # define _DEFAULT_SOURCE /* new glibc */
1770 #endif
1771 #if defined(__sun)
1772 # ifndef _XOPEN_SOURCE /* SunOS already defines */
1773 # define _XOPEN_SOURCE /* XPGx */
1774 # endif
1775 # define _XOPEN_SOURCE_EXTENDED 1 /* XPG4v2 */
1776 # ifndef __EXTENSIONS__ /* SunOS already defines */
1777 # define __EXTENSIONS__ /* reallocarray, etc. */
1778 # endif
1779 #endif
1780 #include <unistd.h>
1781
main(void)1782 int main(void)
1783 {
1784 char *v;
1785
1786 v = crypt("this_is_a_key", "123455");
1787 return v == NULL;
1788 }
1789 #endif // TEST_CRYPT || TEST_CRYPT_LDADD
1790 #if TEST_ENDIAN_H
1791 #ifdef __linux__
1792 # define _DEFAULT_SOURCE
1793 #endif
1794 #include <endian.h>
1795
1796 int
main(void)1797 main(void)
1798 {
1799 return !htole32(23);
1800 }
1801 #endif /* TEST_ENDIAN_H */
1802 #if TEST_ERR
1803 /*
1804 * Copyright (c) 2015 Ingo Schwarze <schwarze@openbsd.org>
1805 *
1806 * Permission to use, copy, modify, and distribute this software for any
1807 * purpose with or without fee is hereby granted, provided that the above
1808 * copyright notice and this permission notice appear in all copies.
1809 *
1810 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
1811 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
1812 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
1813 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
1814 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
1815 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
1816 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
1817 */
1818
1819 #include <err.h>
1820 #include <errno.h>
1821
1822 int
main(void)1823 main(void)
1824 {
1825 warnx("%d. warnx", 1);
1826 warnc(ENOENT, "%d. warn", ENOENT);
1827 warn("%d. warn", 2);
1828 err(0, "%d. err", 3);
1829 errx(0, "%d. err", 3);
1830 errc(0, ENOENT, "%d. err", 3);
1831 /* NOTREACHED */
1832 return 1;
1833 }
1834 #endif /* TEST_ERR */
1835 #if TEST_EXECINFO || TEST_EXECINFO_LDADD
1836 #include <execinfo.h>
1837 #include <unistd.h>
1838
1839 int
main(void)1840 main(void)
1841 {
1842 void *addrlist[10];
1843 size_t len = backtrace(addrlist, 10);
1844 return (backtrace_symbols_fd(addrlist, len, STDERR_FILENO) == -1);
1845 }
1846 #endif // TEST_EXECINFO || TEST_EXECINFO_LDADD
1847 #if TEST_EXPLICIT_BZERO
1848 #include <string.h>
1849
1850 int
main(void)1851 main(void)
1852 {
1853 char foo[10];
1854
1855 explicit_bzero(foo, sizeof(foo));
1856 return(0);
1857 }
1858 #endif /* TEST_EXPLICIT_BZERO */
1859 #if TEST_FTS
1860 #include <stddef.h>
1861 #include <sys/types.h>
1862 #include <sys/stat.h>
1863 #include <fts.h>
1864
1865 int
main(void)1866 main(void)
1867 {
1868 const char *argv[2];
1869 FTS *ftsp;
1870 FTSENT *entry;
1871
1872 argv[0] = ".";
1873 argv[1] = (char *)NULL;
1874
1875 ftsp = fts_open((char * const *)argv,
1876 FTS_PHYSICAL | FTS_NOCHDIR, NULL);
1877
1878 if (ftsp == NULL)
1879 return 1;
1880
1881 entry = fts_read(ftsp);
1882
1883 if (entry == NULL)
1884 return 1;
1885
1886 if (fts_set(ftsp, entry, FTS_SKIP) != 0)
1887 return 1;
1888
1889 if (fts_close(ftsp) != 0)
1890 return 1;
1891
1892 return 0;
1893 }
1894 #endif /* TEST_FTS */
1895 #if TEST_GETEXECNAME
1896 #include <stdlib.h>
1897
1898 int
main(void)1899 main(void)
1900 {
1901 const char * progname;
1902
1903 progname = getexecname();
1904 return progname == NULL;
1905 }
1906 #endif /* TEST_GETEXECNAME */
1907 #if TEST_GETPROGNAME
1908 #include <stdlib.h>
1909
1910 int
main(void)1911 main(void)
1912 {
1913 const char * progname;
1914
1915 progname = getprogname();
1916 return progname == NULL;
1917 }
1918 #endif /* TEST_GETPROGNAME */
1919 #if TEST_INFTIM
1920 /*
1921 * Linux doesn't (always?) have this.
1922 */
1923
1924 #include <poll.h>
1925 #include <stdio.h>
1926
1927 int
main(void)1928 main(void)
1929 {
1930 printf("INFTIM is defined to be %ld\n", (long)INFTIM);
1931 return 0;
1932 }
1933 #endif /* TEST_INFTIM */
1934 #if TEST_LIB_SOCKET || TEST_LIB_SOCKET_LDADD
1935 #include <sys/socket.h>
1936
1937 int
main(void)1938 main(void)
1939 {
1940 int fds[2], c;
1941
1942 c = socketpair(AF_UNIX, SOCK_STREAM, 0, fds);
1943 return c == -1;
1944 }
1945 #endif // TEST_LIB_SOCKET || TEST_LIB_SOCKET_LDADD
1946 #if TEST_MEMMEM
1947 #define _GNU_SOURCE
1948 #include <string.h>
1949
1950 int
main(void)1951 main(void)
1952 {
1953 char *a = memmem("hello, world", strlen("hello, world"), "world", strlen("world"));
1954 return(NULL == a);
1955 }
1956 #endif /* TEST_MEMMEM */
1957 #if TEST_MEMRCHR
1958 #if defined(__linux__) || defined(__MINT__)
1959 #define _GNU_SOURCE /* See test-*.c what needs this. */
1960 #endif
1961 #include <string.h>
1962
1963 int
main(void)1964 main(void)
1965 {
1966 const char *buf = "abcdef";
1967 void *res;
1968
1969 res = memrchr(buf, 'a', strlen(buf));
1970 return(NULL == res ? 1 : 0);
1971 }
1972 #endif /* TEST_MEMRCHR */
1973 #if TEST_MEMSET_S
1974 #include <string.h>
1975
main(void)1976 int main(void)
1977 {
1978 char buf[10];
1979 memset_s(buf, 0, 'c', sizeof(buf));
1980 return 0;
1981 }
1982 #endif /* TEST_MEMSET_S */
1983 #if TEST_MKFIFOAT
1984 #include <sys/stat.h>
1985 #include <fcntl.h>
1986
main(void)1987 int main(void) {
1988 mkfifoat(AT_FDCWD, "this/path/should/not/exist", 0600);
1989 return 0;
1990 }
1991 #endif /* TEST_MKFIFOAT */
1992 #if TEST_MKNODAT
1993 #include <sys/stat.h>
1994 #include <fcntl.h>
1995
main(void)1996 int main(void) {
1997 mknodat(AT_FDCWD, "this/path/should/not/exist", S_IFIFO | 0600, 0);
1998 return 0;
1999 }
2000 #endif /* TEST_MKNODAT */
2001 #if TEST_OSBYTEORDER_H
2002 #include <libkern/OSByteOrder.h>
2003
2004 int
main(void)2005 main(void)
2006 {
2007 return !OSSwapHostToLittleInt32(23);
2008 }
2009 #endif /* TEST_OSBYTEORDER_H */
2010 #if TEST_PATH_MAX
2011 /*
2012 * POSIX allows PATH_MAX to not be defined, see
2013 * http://pubs.opengroup.org/onlinepubs/9699919799/functions/sysconf.html;
2014 * the GNU Hurd is an example of a system not having it.
2015 *
2016 * Arguably, it would be better to test sysconf(_SC_PATH_MAX),
2017 * but since the individual *.c files include "config.h" before
2018 * <limits.h>, overriding an excessive value of PATH_MAX from
2019 * "config.h" is impossible anyway, so for now, the simplest
2020 * fix is to provide a value only on systems not having any.
2021 * So far, we encountered no system defining PATH_MAX to an
2022 * impractically large value, even though POSIX explicitly
2023 * allows that.
2024 *
2025 * The real fix would be to replace all static buffers of size
2026 * PATH_MAX by dynamically allocated buffers. But that is
2027 * somewhat intrusive because it touches several files and
2028 * because it requires changing struct mlink in mandocdb.c.
2029 * So i'm postponing that for now.
2030 */
2031
2032 #include <limits.h>
2033 #include <stdio.h>
2034
2035 int
main(void)2036 main(void)
2037 {
2038 printf("PATH_MAX is defined to be %ld\n", (long)PATH_MAX);
2039 return 0;
2040 }
2041 #endif /* TEST_PATH_MAX */
2042 #if TEST_PLEDGE
2043 #include <unistd.h>
2044
2045 int
main(void)2046 main(void)
2047 {
2048 return !!pledge("stdio", NULL);
2049 }
2050 #endif /* TEST_PLEDGE */
2051 #if TEST_PROGRAM_INVOCATION_SHORT_NAME
2052 #define _GNU_SOURCE /* See feature_test_macros(7) */
2053 #include <errno.h>
2054
2055 int
main(void)2056 main(void)
2057 {
2058
2059 return !program_invocation_short_name;
2060 }
2061 #endif /* TEST_PROGRAM_INVOCATION_SHORT_NAME */
2062 #if TEST_BSD_QSORT_R
2063 #define _GNU_SOURCE
2064 #include <stdlib.h>
2065 void (qsort_r)(void *base, size_t nmemb, size_t size, void *arg, int (*compar)(void *, const void *, const void *));
2066
2067 static int
int_cmp(void * arg,const void * p1,const void * p2)2068 int_cmp(void *arg, const void *p1, const void *p2)
2069 {
2070 int left = *(const int *)p1;
2071 int right = *(const int *)p2;
2072 int *flag = arg;
2073 *flag = 42;
2074 return ((left > right) - (left < right));
2075 }
2076
2077 int
main(void)2078 main(void)
2079 {
2080 int xs[] = { 3, 2, 1 };
2081 int flag = -1;
2082 qsort_r(&xs, 3, sizeof(xs[0]), &flag, int_cmp);
2083 return !(xs[0] == 1 && xs[1] == 2 && xs[2] == 3 && flag == 42);
2084 }
2085 #endif /* TEST_BSD_QSORT_R */
2086 #if TEST_GNU_QSORT_R
2087 #define _GNU_SOURCE
2088 #include <stdlib.h>
2089 void (qsort_r)(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *arg);
2090
2091 static int
int_cmp(const void * p1,const void * p2,void * arg)2092 int_cmp(const void *p1, const void *p2, void *arg)
2093 {
2094 int left = *(const int *)p1;
2095 int right = *(const int *)p2;
2096 int *flag = arg;
2097 *flag = 42;
2098 return ((left > right) - (left < right));
2099 }
2100
2101 int
main(void)2102 main(void)
2103 {
2104 int xs[] = { 3, 2, 1 };
2105 int flag = -1;
2106 qsort_r(&xs, 3, sizeof(xs[0]), int_cmp, &flag);
2107 return !(xs[0] == 1 && xs[1] == 2 && xs[2] == 3 && flag == 42);
2108 }
2109 #endif /* TEST_GNU_QSORT_R */
2110 #if TEST_READPASSPHRASE
2111 #include <stddef.h>
2112 #include <readpassphrase.h>
2113
2114 int
main(void)2115 main(void)
2116 {
2117 return !!readpassphrase("prompt: ", NULL, 0, 0);
2118 }
2119 #endif /* TEST_READPASSPHRASE */
2120 #if TEST_REALLOCARRAY
2121 #ifdef __NetBSD__
2122 # define _OPENBSD_SOURCE
2123 #endif
2124 #include <stdlib.h>
2125
2126 int
main(void)2127 main(void)
2128 {
2129 return !reallocarray(NULL, 2, 2);
2130 }
2131 #endif /* TEST_REALLOCARRAY */
2132 #if TEST_RECALLOCARRAY
2133 #include <stdlib.h>
2134
2135 int
main(void)2136 main(void)
2137 {
2138 return !recallocarray(NULL, 0, 2, 2);
2139 }
2140 #endif /* TEST_RECALLOCARRAY */
2141 #if TEST_SANDBOX_INIT
2142 #include <sandbox.h>
2143
2144 int
main(void)2145 main(void)
2146 {
2147 char *ep;
2148 int rc;
2149
2150 rc = sandbox_init(kSBXProfileNoInternet, SANDBOX_NAMED, &ep);
2151 if (-1 == rc)
2152 sandbox_free_error(ep);
2153 return(-1 == rc);
2154 }
2155 #endif /* TEST_SANDBOX_INIT */
2156 #if TEST_SECCOMP_FILTER
2157 #include <sys/prctl.h>
2158 #include <linux/seccomp.h>
2159 #include <errno.h>
2160
2161 int
main(void)2162 main(void)
2163 {
2164
2165 prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, 0);
2166 return(EFAULT == errno ? 0 : 1);
2167 }
2168 #endif /* TEST_SECCOMP_FILTER */
2169 #if TEST_SETRESGID
2170 #define _GNU_SOURCE /* linux */
2171 #include <sys/types.h>
2172 #include <unistd.h>
2173
2174 int
main(void)2175 main(void)
2176 {
2177 return setresgid(-1, -1, -1) == -1;
2178 }
2179 #endif /* TEST_SETRESGID */
2180 #if TEST_SETRESUID
2181 #define _GNU_SOURCE /* linux */
2182 #include <sys/types.h>
2183 #include <unistd.h>
2184
2185 int
main(void)2186 main(void)
2187 {
2188 return setresuid(-1, -1, -1) == -1;
2189 }
2190 #endif /* TEST_SETRESUID */
2191 #if TEST_SOCK_NONBLOCK
2192 /*
2193 * Linux doesn't (always?) have this.
2194 */
2195
2196 #include <sys/socket.h>
2197
2198 int
main(void)2199 main(void)
2200 {
2201 int fd[2];
2202 socketpair(AF_UNIX, SOCK_STREAM|SOCK_NONBLOCK, 0, fd);
2203 return 0;
2204 }
2205 #endif /* TEST_SOCK_NONBLOCK */
2206 #if TEST_STATIC
2207 int
main(void)2208 main(void)
2209 {
2210 return 0; /* not meant to do anything */
2211 }
2212 #endif /* TEST_STATIC */
2213 #if TEST_STRLCAT
2214 #include <string.h>
2215
2216 int
main(void)2217 main(void)
2218 {
2219 char buf[3] = "a";
2220 return ! (strlcat(buf, "b", sizeof(buf)) == 2 &&
2221 buf[0] == 'a' && buf[1] == 'b' && buf[2] == '\0');
2222 }
2223 #endif /* TEST_STRLCAT */
2224 #if TEST_STRLCPY
2225 #include <string.h>
2226
2227 int
main(void)2228 main(void)
2229 {
2230 char buf[2] = "";
2231 return ! (strlcpy(buf, "a", sizeof(buf)) == 1 &&
2232 buf[0] == 'a' && buf[1] == '\0');
2233 }
2234 #endif /* TEST_STRLCPY */
2235 #if TEST_STRNDUP
2236 #include <string.h>
2237
2238 int
main(void)2239 main(void)
2240 {
2241 const char *foo = "bar";
2242 char *baz;
2243
2244 baz = strndup(foo, 1);
2245 return(0 != strcmp(baz, "b"));
2246 }
2247 #endif /* TEST_STRNDUP */
2248 #if TEST_STRNLEN
2249 #include <string.h>
2250
2251 int
main(void)2252 main(void)
2253 {
2254 const char *foo = "bar";
2255 size_t sz;
2256
2257 sz = strnlen(foo, 1);
2258 return(1 != sz);
2259 }
2260 #endif /* TEST_STRNLEN */
2261 #if TEST_STRNSTR
2262 #include <string.h>
2263
2264 int
main(void)2265 main(void)
2266 {
2267 const char *foo = "bar";
2268 return(NULL == strnstr(foo, "a", 2));
2269 }
2270 #endif /* TEST_STRNSTR */
2271 #if TEST_STRSEP
2272 #include <string.h>
2273
2274 int
main(void)2275 main(void)
2276 {
2277 char *foo = strdup("foo bar");
2278 char *token = strsep(&foo, " ");
2279 return !(token && strcmp(token, "foo") == 0);
2280 }
2281 #endif // TEST_STRSEP
2282 #if TEST_STRTONUM
2283 /*
2284 * Copyright (c) 2015 Ingo Schwarze <schwarze@openbsd.org>
2285 *
2286 * Permission to use, copy, modify, and distribute this software for any
2287 * purpose with or without fee is hereby granted, provided that the above
2288 * copyright notice and this permission notice appear in all copies.
2289 *
2290 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
2291 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
2292 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
2293 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
2294 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
2295 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
2296 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
2297 */
2298 #ifdef __NetBSD__
2299 # define _OPENBSD_SOURCE
2300 #endif
2301 #include <stdlib.h>
2302
2303 int
main(void)2304 main(void)
2305 {
2306 const char *errstr;
2307
2308 if (strtonum("1", 0, 2, &errstr) != 1)
2309 return 1;
2310 if (errstr != NULL)
2311 return 2;
2312 if (strtonum("1x", 0, 2, &errstr) != 0)
2313 return 3;
2314 if (errstr == NULL)
2315 return 4;
2316 if (strtonum("2", 0, 1, &errstr) != 0)
2317 return 5;
2318 if (errstr == NULL)
2319 return 6;
2320 if (strtonum("0", 1, 2, &errstr) != 0)
2321 return 7;
2322 if (errstr == NULL)
2323 return 8;
2324 return 0;
2325 }
2326 #endif /* TEST_STRTONUM */
2327 #if TEST_SYS_BYTEORDER_H
2328 #include <sys/byteorder.h>
2329
2330 int
main(void)2331 main(void)
2332 {
2333 return !LE_32(23);
2334 }
2335 #endif /* TEST_SYS_BYTEORDER_H */
2336 #if TEST_SYS_ENDIAN_H
2337 #include <sys/endian.h>
2338
2339 int
main(void)2340 main(void)
2341 {
2342 return !htole32(23);
2343 }
2344 #endif /* TEST_SYS_ENDIAN_H */
2345 #if TEST_SYS_MKDEV_H
2346 #include <sys/types.h>
2347 #include <sys/mkdev.h>
2348
2349 int
main(void)2350 main(void)
2351 {
2352 return !minor(0);
2353 }
2354 #endif /* TEST_SYS_MKDEV_H */
2355 #if TEST_SYS_QUEUE
2356 #include <sys/queue.h>
2357 #include <stddef.h>
2358
2359 struct foo {
2360 int bar;
2361 TAILQ_ENTRY(foo) entries;
2362 };
2363
2364 TAILQ_HEAD(fooq, foo);
2365
2366 int
main(void)2367 main(void)
2368 {
2369 struct fooq foo_q, bar_q;
2370 struct foo *p, *tmp;
2371 int i = 0;
2372
2373 TAILQ_INIT(&foo_q);
2374 TAILQ_INIT(&bar_q);
2375
2376 /*
2377 * Use TAILQ_FOREACH_SAFE because some systems (e.g., Linux)
2378 * have TAILQ_FOREACH but not the safe variant.
2379 */
2380
2381 TAILQ_FOREACH_SAFE(p, &foo_q, entries, tmp)
2382 p->bar = i++;
2383
2384 /* Test for newer macros as well. */
2385
2386 TAILQ_CONCAT(&foo_q, &bar_q, entries);
2387 return 0;
2388 }
2389 #endif /* TEST_SYS_QUEUE */
2390 #if TEST_SYS_SYSMACROS_H
2391 #include <sys/sysmacros.h>
2392
2393 int
main(void)2394 main(void)
2395 {
2396 return !minor(0);
2397 }
2398 #endif /* TEST_SYS_SYSMACROS_H */
2399 #if TEST_SYS_TREE
2400 #include <sys/tree.h>
2401 #include <stdlib.h>
2402
2403 struct node {
2404 RB_ENTRY(node) entry;
2405 int i;
2406 };
2407
2408 static int
intcmp(struct node * e1,struct node * e2)2409 intcmp(struct node *e1, struct node *e2)
2410 {
2411 return (e1->i < e2->i ? -1 : e1->i > e2->i);
2412 }
2413
2414 RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
2415 RB_PROTOTYPE(inttree, node, entry, intcmp)
2416 RB_GENERATE(inttree, node, entry, intcmp)
2417
2418 int testdata[] = {
2419 20, 16, 17, 13, 3, 6, 1, 8, 2, 4
2420 };
2421
2422 int
main(void)2423 main(void)
2424 {
2425 size_t i;
2426 struct node *n;
2427
2428 for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
2429 if ((n = malloc(sizeof(struct node))) == NULL)
2430 return 1;
2431 n->i = testdata[i];
2432 RB_INSERT(inttree, &head, n);
2433 }
2434
2435 return 0;
2436 }
2437
2438 #endif /* TEST_SYS_TREE */
2439 #if TEST_UNVEIL
2440 #include <unistd.h>
2441
2442 int
main(void)2443 main(void)
2444 {
2445 return -1 != unveil(NULL, NULL);
2446 }
2447 #endif /* TEST_UNVEIL */
2448 #if TEST_WAIT_ANY
2449 #include <sys/wait.h>
2450
2451 int
main(void)2452 main(void)
2453 {
2454 int st;
2455
2456 return waitpid(WAIT_ANY, &st, WNOHANG) != -1;
2457 }
2458 #endif /* TEST_WAIT_ANY */
2459
2460 #else /* __MKBUILD_CONFIG_H__ */
2461
2462 #if HAVE_BSD_QSORT_R || HAVE_GNU_QSORT_R
2463 # define HAVE_QSORT_R 1
2464 #else
2465 # define HAVE_QSORT_R 0
2466 #endif
2467
2468 #if HAVE_B64_NTOP_LDADD
2469 #undef HAVE_B64_NTOP
2470 #define HAVE_B64_NTOP 1
2471 #endif
2472
2473 #if HAVE_CRYPT_LDADD
2474 #undef HAVE_CRYPT
2475 #define HAVE_CRYPT 1
2476 #endif
2477
2478 #if HAVE_EXECINFO_LDADD
2479 #undef HAVE_EXECINFO
2480 #define HAVE_EXECINFO 1
2481 #endif
2482
2483 #if HAVE_LIB_SOCKET_LDADD
2484 #undef HAVE_LIB_SOCKET
2485 #define HAVE_LIB_SOCKET 1
2486 #endif
2487
2488 #ifdef __cplusplus
2489 # error "Do not use C++: this is a C application."
2490 #endif
2491 #if !defined(__GNUC__) || (__GNUC__ < 4)
2492 # define __attribute__(x)
2493 #endif
2494 #if defined(__CYGWIN__) || defined(__linux__) || defined(__MINT__)
2495 # define _GNU_SOURCE /* memmem, memrchr, setresuid... */
2496 # define _DEFAULT_SOURCE /* le32toh, crypt, ... */
2497 #endif
2498 #if defined(__NetBSD__)
2499 # define _OPENBSD_SOURCE /* reallocarray, etc. */
2500 #endif
2501 #if defined(__sun)
2502 # ifndef _XOPEN_SOURCE /* SunOS already defines */
2503 # define _XOPEN_SOURCE /* XPGx */
2504 # endif
2505 # define _XOPEN_SOURCE_EXTENDED 1 /* XPG4v2 */
2506 # ifndef __EXTENSIONS__ /* SunOS already defines */
2507 # define __EXTENSIONS__ /* reallocarray, etc. */
2508 # endif
2509 #endif
2510 #if !defined(__BEGIN_DECLS)
2511 # define __BEGIN_DECLS
2512 #endif
2513 #if !defined(__END_DECLS)
2514 # define __END_DECLS
2515 #endif
2516
2517 #if !HAVE_FTS || !HAVE_MEMMEM || !HAVE_MEMRCHR || !HAVE_MKFIFOAT || \
2518 !HAVE_MKNODAT || !HAVE_QSORT_R || !HAVE_READPASSPHRASE || !HAVE_REALLOCARRAY || \
2519 !HAVE_RECALLOCARRAY || !HAVE_SETRESGID || !HAVE_SETRESUID || \
2520 !HAVE_STRLCAT || !HAVE_STRLCPY || !HAVE_STRNDUP || !HAVE_STRNLEN || !HAVE_STRNSTR
2521 #include <sys/types.h> /* size_t, mode_t, dev_t */
2522 #endif
2523
2524 #if !HAVE_ERR
2525 #include <stdarg.h> /* err(3) */
2526 #endif
2527
2528 #if !HAVE_PATH_MAX
2529 #define PATH_MAX 4096
2530 #endif
2531
2532 #if !HAVE_WAIT_ANY
2533 #define WAIT_ANY (-1) /* sys/wait.h */
2534 #define WAIT_MYPGRP 0
2535 #endif
2536
2537 #if !HAVE_INFTIM
2538 #define INFTIM (-1) /* poll.h */
2539 #endif
2540
2541 #if HAVE_OSBYTEORDER_H && !HAVE_ENDIAN_H && !HAVE_SYS_BYTEORDER_H && !HAVE_SYS_ENDIAN_H
2542 /*
2543 * endian.h compatibility with libkern/OSByteOrder.h.
2544 */
2545 #define htobe16(x) OSSwapHostToBigInt16(x)
2546 #define htole16(x) OSSwapHostToLittleInt16(x)
2547 #define be16toh(x) OSSwapBigToHostInt16(x)
2548 #define le16toh(x) OSSwapLittleToHostInt16(x)
2549 #define htobe32(x) OSSwapHostToBigInt32(x)
2550 #define htole32(x) OSSwapHostToLittleInt32(x)
2551 #define be32toh(x) OSSwapBigToHostInt32(x)
2552 #define le32toh(x) OSSwapLittleToHostInt32(x)
2553 #define htobe64(x) OSSwapHostToBigInt64(x)
2554 #define htole64(x) OSSwapHostToLittleInt64(x)
2555 #define be64toh(x) OSSwapBigToHostInt64(x)
2556 #define le64toh(x) OSSwapLittleToHostInt64(x)
2557 #endif
2558
2559 #if HAVE_SYS_BYTEORDER_H && !HAVE_ENDIAN_H && !HAVE_OSBYTEORDER_H && !HAVE_SYS_ENDIAN_H
2560 /*
2561 * endian.h compatibility with sys/byteorder.h.
2562 */
2563 #define htobe16(x) BE_16(x)
2564 #define htole16(x) LE_16(x)
2565 #define be16toh(x) BE_16(x)
2566 #define le16toh(x) LE_16(x)
2567 #define htobe32(x) BE_32(x)
2568 #define htole32(x) LE_32(x)
2569 #define be32toh(x) BE_32(x)
2570 #define le32toh(x) LE_32(x)
2571 #define htobe64(x) BE_64(x)
2572 #define htole64(x) LE_64(x)
2573 #define be64toh(x) BE_64(x)
2574 #define le64toh(x) LE_64(x)
2575 #endif
2576
2577 /*
2578 * Handle the various major()/minor() header files.
2579 * Use sys/mkdev.h before sys/sysmacros.h because SunOS
2580 * has both, where only the former works properly.
2581 */
2582 #if HAVE_SYS_MKDEV_H
2583 # define COMPAT_MAJOR_MINOR_H <sys/mkdev.h>
2584 #elif HAVE_SYS_SYSMACROS_H
2585 # define COMPAT_MAJOR_MINOR_H <sys/sysmacros.h>
2586 #else
2587 # define COMPAT_MAJOR_MINOR_H <sys/types.h>
2588 #endif
2589
2590 /*
2591 * Make it easier to include endian.h forms.
2592 */
2593 #if HAVE_ENDIAN_H
2594 # define COMPAT_ENDIAN_H <endian.h>
2595 #elif HAVE_SYS_ENDIAN_H
2596 # define COMPAT_ENDIAN_H <sys/endian.h>
2597 #elif HAVE_OSBYTEORDER_H
2598 # define COMPAT_ENDIAN_H <libkern/OSByteOrder.h>
2599 #elif HAVE_SYS_BYTEORDER_H
2600 # define COMPAT_ENDIAN_H <sys/byteorder.h>
2601 #else
2602 # warning No suitable endian.h could be found.
2603 # warning Please e-mail the maintainers with your OS.
2604 # define COMPAT_ENDIAN_H <endian.h>
2605 #endif
2606
2607 #if !HAVE_ERR
2608 /*
2609 * Compatibility functions for err(3).
2610 */
2611 extern void err(int, const char *, ...) __attribute__((noreturn));
2612 extern void errc(int, int, const char *, ...) __attribute__((noreturn));
2613 extern void errx(int, const char *, ...) __attribute__((noreturn));
2614 extern void verr(int, const char *, va_list) __attribute__((noreturn));
2615 extern void verrc(int, int, const char *, va_list) __attribute__((noreturn));
2616 extern void verrx(int, const char *, va_list) __attribute__((noreturn));
2617 extern void warn(const char *, ...);
2618 extern void warnx(const char *, ...);
2619 extern void warnc(int, const char *, ...);
2620 extern void vwarn(const char *, va_list);
2621 extern void vwarnc(int, const char *, va_list);
2622 extern void vwarnx(const char *, va_list);
2623 #endif
2624
2625 #if !HAVE_B64_NTOP
2626 /*
2627 * Compatibility for b64_ntop(3).
2628 */
2629 extern int b64_ntop(unsigned char const *, size_t, char *, size_t);
2630 extern int b64_pton(char const *, unsigned char *, size_t);
2631 #endif
2632
2633 #if !HAVE_EXPLICIT_BZERO
2634 /*
2635 * Compatibility for explicit_bzero(3).
2636 */
2637 extern void explicit_bzero(void *, size_t);
2638 #endif
2639
2640 #if !HAVE_MEMMEM
2641 /*
2642 * Compatibility for memmem(3).
2643 */
2644 void *memmem(const void *, size_t, const void *, size_t);
2645 #endif
2646
2647 #if !HAVE_MEMRCHR
2648 /*
2649 * Compatibility for memrchr(3).
2650 */
2651 void *memrchr(const void *b, int, size_t);
2652 #endif
2653
2654 #if !HAVE_GETPROGNAME
2655 /*
2656 * Compatibility for getprogname(3).
2657 */
2658 extern const char *getprogname(void);
2659 #endif
2660
2661 #if !HAVE_QSORT_R
2662 /*
2663 * Compatibility for qsort_r(3).
2664 */
2665 extern void qsort_r(void *, size_t, size_t, void *, int (*compar)(void *, const void *, const void *));
2666 #endif
2667
2668 #if !HAVE_READPASSPHRASE
2669 /*
2670 * Macros and function required for readpassphrase(3).
2671 */
2672 #define RPP_ECHO_OFF 0x00
2673 #define RPP_ECHO_ON 0x01
2674 #define RPP_REQUIRE_TTY 0x02
2675 #define RPP_FORCELOWER 0x04
2676 #define RPP_FORCEUPPER 0x08
2677 #define RPP_SEVENBIT 0x10
2678 #define RPP_STDIN 0x20
2679 char *readpassphrase(const char *, char *, size_t, int);
2680 #endif
2681
2682 #if !HAVE_REALLOCARRAY
2683 /*
2684 * Compatibility for reallocarray(3).
2685 */
2686 extern void *reallocarray(void *, size_t, size_t);
2687 #endif
2688
2689 #if !HAVE_RECALLOCARRAY
2690 /*
2691 * Compatibility for recallocarray(3).
2692 */
2693 extern void *recallocarray(void *, size_t, size_t, size_t);
2694 #endif
2695
2696 #if !HAVE_STRLCAT
2697 /*
2698 * Compatibility for strlcat(3).
2699 */
2700 extern size_t strlcat(char *, const char *, size_t);
2701 #endif
2702
2703 #if !HAVE_STRLCPY
2704 /*
2705 * Compatibility for strlcpy(3).
2706 */
2707 extern size_t strlcpy(char *, const char *, size_t);
2708 #endif
2709
2710 #if !HAVE_STRNDUP
2711 /*
2712 * Compatibility for strndup(3).
2713 */
2714 extern char *strndup(const char *, size_t);
2715 #endif
2716
2717 #if !HAVE_STRNLEN
2718 /*
2719 * Compatibility for strnlen(3).
2720 */
2721 extern size_t strnlen(const char *, size_t);
2722 #endif
2723
2724 #if !HAVE_STRNSTR
2725 /*
2726 * Compatibility for strnstr(3).
2727 */
2728 extern char *strnstr(const char *, const char *, size_t);
2729 #endif
2730
2731 #if !HAVE_STRSEP
2732 // Compatibility for strsep(3)
2733 extern char *strsep(char **, const char *);
2734 #endif
2735
2736 #if !HAVE_STRTONUM
2737 /*
2738 * Compatibility for strotnum(3).
2739 */
2740 extern long long strtonum(const char *, long long, long long, const char **);
2741 #endif
2742
2743 #if !HAVE_MKFIFOAT
2744 /*
2745 * Compatibility for mkfifoat(2).
2746 */
2747 int mkfifoat(int, const char *, mode_t);
2748 #endif
2749
2750 #if !HAVE_MKNODAT
2751 /*
2752 * Compatibility for mknodat(2).
2753 */
2754 int mknodat(int, const char *, mode_t, dev_t);
2755 #endif
2756
2757 #if !HAVE_SETRESGID
2758 /*
2759 * Compatibility for setresgid(2).
2760 */
2761 int setresgid(gid_t rgid, gid_t egid, gid_t sgid);
2762 #endif
2763
2764 #if !HAVE_SETRESUID
2765 /*
2766 * Compatibility for setresuid(2).
2767 */
2768 int setresuid(uid_t ruid, uid_t euid, uid_t suid);
2769 #endif
2770
2771 #if !HAVE_SYS_QUEUE
2772 /*
2773 * Copyright (c) 1991, 1993
2774 * The Regents of the University of California. All rights reserved.
2775 *
2776 * Redistribution and use in source and binary forms, with or without
2777 * modification, are permitted provided that the following conditions
2778 * are met:
2779 * 1. Redistributions of source code must retain the above copyright
2780 * notice, this list of conditions and the following disclaimer.
2781 * 2. Redistributions in binary form must reproduce the above copyright
2782 * notice, this list of conditions and the following disclaimer in the
2783 * documentation and/or other materials provided with the distribution.
2784 * 3. Neither the name of the University nor the names of its contributors
2785 * may be used to endorse or promote products derived from this software
2786 * without specific prior written permission.
2787 *
2788 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND
2789 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2790 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2791 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2792 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2793 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2794 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
2795 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
2796 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
2797 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
2798 * SUCH DAMAGE.
2799 *
2800 * @(#)queue.h 8.5 (Berkeley) 8/20/94
2801 */
2802
2803 /* OPENBSD ORIGINAL: sys/sys/queue.h */
2804
2805 /*
2806 * Require for OS/X and other platforms that have old/broken/incomplete
2807 * <sys/queue.h>.
2808 */
2809
2810 #undef LIST_EMPTY
2811 #undef LIST_END
2812 #undef LIST_ENTRY
2813 #undef LIST_FIRST
2814 #undef LIST_FOREACH
2815 #undef LIST_FOREACH_SAFE
2816 #undef LIST_HEAD
2817 #undef LIST_HEAD_INITIALIZER
2818 #undef LIST_INIT
2819 #undef LIST_INSERT_AFTER
2820 #undef LIST_INSERT_BEFORE
2821 #undef LIST_INSERT_HEAD
2822 #undef LIST_NEXT
2823 #undef LIST_REMOVE
2824 #undef LIST_REPLACE
2825 #undef SIMPLEQ_CONCAT
2826 #undef SIMPLEQ_EMPTY
2827 #undef SIMPLEQ_END
2828 #undef SIMPLEQ_ENTRY
2829 #undef SIMPLEQ_FIRST
2830 #undef SIMPLEQ_FOREACH
2831 #undef SIMPLEQ_FOREACH_SAFE
2832 #undef SIMPLEQ_HEAD
2833 #undef SIMPLEQ_HEAD_INITIALIZER
2834 #undef SIMPLEQ_INIT
2835 #undef SIMPLEQ_INSERT_AFTER
2836 #undef SIMPLEQ_INSERT_HEAD
2837 #undef SIMPLEQ_INSERT_TAIL
2838 #undef SIMPLEQ_NEXT
2839 #undef SIMPLEQ_REMOVE_AFTER
2840 #undef SIMPLEQ_REMOVE_HEAD
2841 #undef SLIST_EMPTY
2842 #undef SLIST_END
2843 #undef SLIST_ENTRY
2844 #undef SLIST_FIRST
2845 #undef SLIST_FOREACH
2846 #undef SLIST_FOREACH_SAFE
2847 #undef SLIST_HEAD
2848 #undef SLIST_HEAD_INITIALIZER
2849 #undef SLIST_INIT
2850 #undef SLIST_INSERT_AFTER
2851 #undef SLIST_INSERT_HEAD
2852 #undef SLIST_NEXT
2853 #undef SLIST_REMOVE
2854 #undef SLIST_REMOVE_AFTER
2855 #undef SLIST_REMOVE_HEAD
2856 #undef TAILQ_CONCAT
2857 #undef TAILQ_EMPTY
2858 #undef TAILQ_END
2859 #undef TAILQ_ENTRY
2860 #undef TAILQ_FIRST
2861 #undef TAILQ_FOREACH
2862 #undef TAILQ_FOREACH_REVERSE
2863 #undef TAILQ_FOREACH_REVERSE_SAFE
2864 #undef TAILQ_FOREACH_SAFE
2865 #undef TAILQ_HEAD
2866 #undef TAILQ_HEAD_INITIALIZER
2867 #undef TAILQ_INIT
2868 #undef TAILQ_INSERT_AFTER
2869 #undef TAILQ_INSERT_BEFORE
2870 #undef TAILQ_INSERT_HEAD
2871 #undef TAILQ_INSERT_TAIL
2872 #undef TAILQ_LAST
2873 #undef TAILQ_NEXT
2874 #undef TAILQ_PREV
2875 #undef TAILQ_REMOVE
2876 #undef TAILQ_REPLACE
2877 #undef XSIMPLEQ_EMPTY
2878 #undef XSIMPLEQ_END
2879 #undef XSIMPLEQ_ENTRY
2880 #undef XSIMPLEQ_FIRST
2881 #undef XSIMPLEQ_FOREACH
2882 #undef XSIMPLEQ_FOREACH_SAFE
2883 #undef XSIMPLEQ_HEAD
2884 #undef XSIMPLEQ_INIT
2885 #undef XSIMPLEQ_INSERT_AFTER
2886 #undef XSIMPLEQ_INSERT_HEAD
2887 #undef XSIMPLEQ_INSERT_TAIL
2888 #undef XSIMPLEQ_NEXT
2889 #undef XSIMPLEQ_REMOVE_AFTER
2890 #undef XSIMPLEQ_REMOVE_HEAD
2891 #undef XSIMPLEQ_XOR
2892
2893 /*
2894 * This file defines five types of data structures: singly-linked lists,
2895 * lists, simple queues, tail queues and XOR simple queues.
2896 *
2897 *
2898 * A singly-linked list is headed by a single forward pointer. The elements
2899 * are singly linked for minimum space and pointer manipulation overhead at
2900 * the expense of O(n) removal for arbitrary elements. New elements can be
2901 * added to the list after an existing element or at the head of the list.
2902 * Elements being removed from the head of the list should use the explicit
2903 * macro for this purpose for optimum efficiency. A singly-linked list may
2904 * only be traversed in the forward direction. Singly-linked lists are ideal
2905 * for applications with large datasets and few or no removals or for
2906 * implementing a LIFO queue.
2907 *
2908 * A list is headed by a single forward pointer (or an array of forward
2909 * pointers for a hash table header). The elements are doubly linked
2910 * so that an arbitrary element can be removed without a need to
2911 * traverse the list. New elements can be added to the list before
2912 * or after an existing element or at the head of the list. A list
2913 * may only be traversed in the forward direction.
2914 *
2915 * A simple queue is headed by a pair of pointers, one to the head of the
2916 * list and the other to the tail of the list. The elements are singly
2917 * linked to save space, so elements can only be removed from the
2918 * head of the list. New elements can be added to the list before or after
2919 * an existing element, at the head of the list, or at the end of the
2920 * list. A simple queue may only be traversed in the forward direction.
2921 *
2922 * A tail queue is headed by a pair of pointers, one to the head of the
2923 * list and the other to the tail of the list. The elements are doubly
2924 * linked so that an arbitrary element can be removed without a need to
2925 * traverse the list. New elements can be added to the list before or
2926 * after an existing element, at the head of the list, or at the end of
2927 * the list. A tail queue may be traversed in either direction.
2928 *
2929 * An XOR simple queue is used in the same way as a regular simple queue.
2930 * The difference is that the head structure also includes a "cookie" that
2931 * is XOR'd with the queue pointer (first, last or next) to generate the
2932 * real pointer value.
2933 *
2934 * For details on the use of these macros, see the queue(3) manual page.
2935 */
2936
2937 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
2938 #define _Q_INVALID ((void *)-1)
2939 #define _Q_INVALIDATE(a) (a) = _Q_INVALID
2940 #else
2941 #define _Q_INVALIDATE(a)
2942 #endif
2943
2944 /*
2945 * Singly-linked List definitions.
2946 */
2947 #define SLIST_HEAD(name, type) \
2948 struct name { \
2949 struct type *slh_first; /* first element */ \
2950 }
2951
2952 #define SLIST_HEAD_INITIALIZER(head) \
2953 { NULL }
2954
2955 #define SLIST_ENTRY(type) \
2956 struct { \
2957 struct type *sle_next; /* next element */ \
2958 }
2959
2960 /*
2961 * Singly-linked List access methods.
2962 */
2963 #define SLIST_FIRST(head) ((head)->slh_first)
2964 #define SLIST_END(head) NULL
2965 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
2966 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
2967
2968 #define SLIST_FOREACH(var, head, field) \
2969 for((var) = SLIST_FIRST(head); \
2970 (var) != SLIST_END(head); \
2971 (var) = SLIST_NEXT(var, field))
2972
2973 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
2974 for ((var) = SLIST_FIRST(head); \
2975 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \
2976 (var) = (tvar))
2977
2978 /*
2979 * Singly-linked List functions.
2980 */
2981 #define SLIST_INIT(head) { \
2982 SLIST_FIRST(head) = SLIST_END(head); \
2983 }
2984
2985 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
2986 (elm)->field.sle_next = (slistelm)->field.sle_next; \
2987 (slistelm)->field.sle_next = (elm); \
2988 } while (0)
2989
2990 #define SLIST_INSERT_HEAD(head, elm, field) do { \
2991 (elm)->field.sle_next = (head)->slh_first; \
2992 (head)->slh_first = (elm); \
2993 } while (0)
2994
2995 #define SLIST_REMOVE_AFTER(elm, field) do { \
2996 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
2997 } while (0)
2998
2999 #define SLIST_REMOVE_HEAD(head, field) do { \
3000 (head)->slh_first = (head)->slh_first->field.sle_next; \
3001 } while (0)
3002
3003 #define SLIST_REMOVE(head, elm, type, field) do { \
3004 if ((head)->slh_first == (elm)) { \
3005 SLIST_REMOVE_HEAD((head), field); \
3006 } else { \
3007 struct type *curelm = (head)->slh_first; \
3008 \
3009 while (curelm->field.sle_next != (elm)) \
3010 curelm = curelm->field.sle_next; \
3011 curelm->field.sle_next = \
3012 curelm->field.sle_next->field.sle_next; \
3013 } \
3014 _Q_INVALIDATE((elm)->field.sle_next); \
3015 } while (0)
3016
3017 /*
3018 * List definitions.
3019 */
3020 #define LIST_HEAD(name, type) \
3021 struct name { \
3022 struct type *lh_first; /* first element */ \
3023 }
3024
3025 #define LIST_HEAD_INITIALIZER(head) \
3026 { NULL }
3027
3028 #define LIST_ENTRY(type) \
3029 struct { \
3030 struct type *le_next; /* next element */ \
3031 struct type **le_prev; /* address of previous next element */ \
3032 }
3033
3034 /*
3035 * List access methods.
3036 */
3037 #define LIST_FIRST(head) ((head)->lh_first)
3038 #define LIST_END(head) NULL
3039 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
3040 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
3041
3042 #define LIST_FOREACH(var, head, field) \
3043 for((var) = LIST_FIRST(head); \
3044 (var)!= LIST_END(head); \
3045 (var) = LIST_NEXT(var, field))
3046
3047 #define LIST_FOREACH_SAFE(var, head, field, tvar) \
3048 for ((var) = LIST_FIRST(head); \
3049 (var) && ((tvar) = LIST_NEXT(var, field), 1); \
3050 (var) = (tvar))
3051
3052 /*
3053 * List functions.
3054 */
3055 #define LIST_INIT(head) do { \
3056 LIST_FIRST(head) = LIST_END(head); \
3057 } while (0)
3058
3059 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
3060 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
3061 (listelm)->field.le_next->field.le_prev = \
3062 &(elm)->field.le_next; \
3063 (listelm)->field.le_next = (elm); \
3064 (elm)->field.le_prev = &(listelm)->field.le_next; \
3065 } while (0)
3066
3067 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
3068 (elm)->field.le_prev = (listelm)->field.le_prev; \
3069 (elm)->field.le_next = (listelm); \
3070 *(listelm)->field.le_prev = (elm); \
3071 (listelm)->field.le_prev = &(elm)->field.le_next; \
3072 } while (0)
3073
3074 #define LIST_INSERT_HEAD(head, elm, field) do { \
3075 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
3076 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
3077 (head)->lh_first = (elm); \
3078 (elm)->field.le_prev = &(head)->lh_first; \
3079 } while (0)
3080
3081 #define LIST_REMOVE(elm, field) do { \
3082 if ((elm)->field.le_next != NULL) \
3083 (elm)->field.le_next->field.le_prev = \
3084 (elm)->field.le_prev; \
3085 *(elm)->field.le_prev = (elm)->field.le_next; \
3086 _Q_INVALIDATE((elm)->field.le_prev); \
3087 _Q_INVALIDATE((elm)->field.le_next); \
3088 } while (0)
3089
3090 #define LIST_REPLACE(elm, elm2, field) do { \
3091 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
3092 (elm2)->field.le_next->field.le_prev = \
3093 &(elm2)->field.le_next; \
3094 (elm2)->field.le_prev = (elm)->field.le_prev; \
3095 *(elm2)->field.le_prev = (elm2); \
3096 _Q_INVALIDATE((elm)->field.le_prev); \
3097 _Q_INVALIDATE((elm)->field.le_next); \
3098 } while (0)
3099
3100 /*
3101 * Simple queue definitions.
3102 */
3103 #define SIMPLEQ_HEAD(name, type) \
3104 struct name { \
3105 struct type *sqh_first; /* first element */ \
3106 struct type **sqh_last; /* addr of last next element */ \
3107 }
3108
3109 #define SIMPLEQ_HEAD_INITIALIZER(head) \
3110 { NULL, &(head).sqh_first }
3111
3112 #define SIMPLEQ_ENTRY(type) \
3113 struct { \
3114 struct type *sqe_next; /* next element */ \
3115 }
3116
3117 /*
3118 * Simple queue access methods.
3119 */
3120 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
3121 #define SIMPLEQ_END(head) NULL
3122 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
3123 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
3124
3125 #define SIMPLEQ_FOREACH(var, head, field) \
3126 for((var) = SIMPLEQ_FIRST(head); \
3127 (var) != SIMPLEQ_END(head); \
3128 (var) = SIMPLEQ_NEXT(var, field))
3129
3130 #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
3131 for ((var) = SIMPLEQ_FIRST(head); \
3132 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \
3133 (var) = (tvar))
3134
3135 /*
3136 * Simple queue functions.
3137 */
3138 #define SIMPLEQ_INIT(head) do { \
3139 (head)->sqh_first = NULL; \
3140 (head)->sqh_last = &(head)->sqh_first; \
3141 } while (0)
3142
3143 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
3144 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
3145 (head)->sqh_last = &(elm)->field.sqe_next; \
3146 (head)->sqh_first = (elm); \
3147 } while (0)
3148
3149 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
3150 (elm)->field.sqe_next = NULL; \
3151 *(head)->sqh_last = (elm); \
3152 (head)->sqh_last = &(elm)->field.sqe_next; \
3153 } while (0)
3154
3155 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
3156 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
3157 (head)->sqh_last = &(elm)->field.sqe_next; \
3158 (listelm)->field.sqe_next = (elm); \
3159 } while (0)
3160
3161 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
3162 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
3163 (head)->sqh_last = &(head)->sqh_first; \
3164 } while (0)
3165
3166 #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
3167 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
3168 == NULL) \
3169 (head)->sqh_last = &(elm)->field.sqe_next; \
3170 } while (0)
3171
3172 #define SIMPLEQ_CONCAT(head1, head2) do { \
3173 if (!SIMPLEQ_EMPTY((head2))) { \
3174 *(head1)->sqh_last = (head2)->sqh_first; \
3175 (head1)->sqh_last = (head2)->sqh_last; \
3176 SIMPLEQ_INIT((head2)); \
3177 } \
3178 } while (0)
3179
3180 /*
3181 * XOR Simple queue definitions.
3182 */
3183 #define XSIMPLEQ_HEAD(name, type) \
3184 struct name { \
3185 struct type *sqx_first; /* first element */ \
3186 struct type **sqx_last; /* addr of last next element */ \
3187 unsigned long sqx_cookie; \
3188 }
3189
3190 #define XSIMPLEQ_ENTRY(type) \
3191 struct { \
3192 struct type *sqx_next; /* next element */ \
3193 }
3194
3195 /*
3196 * XOR Simple queue access methods.
3197 */
3198 #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
3199 (unsigned long)(ptr)))
3200 #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
3201 #define XSIMPLEQ_END(head) NULL
3202 #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
3203 #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
3204
3205
3206 #define XSIMPLEQ_FOREACH(var, head, field) \
3207 for ((var) = XSIMPLEQ_FIRST(head); \
3208 (var) != XSIMPLEQ_END(head); \
3209 (var) = XSIMPLEQ_NEXT(head, var, field))
3210
3211 #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
3212 for ((var) = XSIMPLEQ_FIRST(head); \
3213 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
3214 (var) = (tvar))
3215
3216 /*
3217 * XOR Simple queue functions.
3218 */
3219 #define XSIMPLEQ_INIT(head) do { \
3220 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
3221 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
3222 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
3223 } while (0)
3224
3225 #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
3226 if (((elm)->field.sqx_next = (head)->sqx_first) == \
3227 XSIMPLEQ_XOR(head, NULL)) \
3228 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
3229 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
3230 } while (0)
3231
3232 #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
3233 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
3234 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
3235 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
3236 } while (0)
3237
3238 #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
3239 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
3240 XSIMPLEQ_XOR(head, NULL)) \
3241 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
3242 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
3243 } while (0)
3244
3245 #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
3246 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
3247 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
3248 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
3249 } while (0)
3250
3251 #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
3252 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
3253 (elm)->field.sqx_next)->field.sqx_next) \
3254 == XSIMPLEQ_XOR(head, NULL)) \
3255 (head)->sqx_last = \
3256 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
3257 } while (0)
3258
3259
3260 /*
3261 * Tail queue definitions.
3262 */
3263 #define TAILQ_HEAD(name, type) \
3264 struct name { \
3265 struct type *tqh_first; /* first element */ \
3266 struct type **tqh_last; /* addr of last next element */ \
3267 }
3268
3269 #define TAILQ_HEAD_INITIALIZER(head) \
3270 { NULL, &(head).tqh_first }
3271
3272 #define TAILQ_ENTRY(type) \
3273 struct { \
3274 struct type *tqe_next; /* next element */ \
3275 struct type **tqe_prev; /* address of previous next element */ \
3276 }
3277
3278 /*
3279 * Tail queue access methods.
3280 */
3281 #define TAILQ_FIRST(head) ((head)->tqh_first)
3282 #define TAILQ_END(head) NULL
3283 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
3284 #define TAILQ_LAST(head, headname) \
3285 (*(((struct headname *)((head)->tqh_last))->tqh_last))
3286 /* XXX */
3287 #define TAILQ_PREV(elm, headname, field) \
3288 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
3289 #define TAILQ_EMPTY(head) \
3290 (TAILQ_FIRST(head) == TAILQ_END(head))
3291
3292 #define TAILQ_FOREACH(var, head, field) \
3293 for((var) = TAILQ_FIRST(head); \
3294 (var) != TAILQ_END(head); \
3295 (var) = TAILQ_NEXT(var, field))
3296
3297 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
3298 for ((var) = TAILQ_FIRST(head); \
3299 (var) != TAILQ_END(head) && \
3300 ((tvar) = TAILQ_NEXT(var, field), 1); \
3301 (var) = (tvar))
3302
3303
3304 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
3305 for((var) = TAILQ_LAST(head, headname); \
3306 (var) != TAILQ_END(head); \
3307 (var) = TAILQ_PREV(var, headname, field))
3308
3309 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
3310 for ((var) = TAILQ_LAST(head, headname); \
3311 (var) != TAILQ_END(head) && \
3312 ((tvar) = TAILQ_PREV(var, headname, field), 1); \
3313 (var) = (tvar))
3314
3315 /*
3316 * Tail queue functions.
3317 */
3318 #define TAILQ_INIT(head) do { \
3319 (head)->tqh_first = NULL; \
3320 (head)->tqh_last = &(head)->tqh_first; \
3321 } while (0)
3322
3323 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
3324 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
3325 (head)->tqh_first->field.tqe_prev = \
3326 &(elm)->field.tqe_next; \
3327 else \
3328 (head)->tqh_last = &(elm)->field.tqe_next; \
3329 (head)->tqh_first = (elm); \
3330 (elm)->field.tqe_prev = &(head)->tqh_first; \
3331 } while (0)
3332
3333 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
3334 (elm)->field.tqe_next = NULL; \
3335 (elm)->field.tqe_prev = (head)->tqh_last; \
3336 *(head)->tqh_last = (elm); \
3337 (head)->tqh_last = &(elm)->field.tqe_next; \
3338 } while (0)
3339
3340 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
3341 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
3342 (elm)->field.tqe_next->field.tqe_prev = \
3343 &(elm)->field.tqe_next; \
3344 else \
3345 (head)->tqh_last = &(elm)->field.tqe_next; \
3346 (listelm)->field.tqe_next = (elm); \
3347 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
3348 } while (0)
3349
3350 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
3351 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
3352 (elm)->field.tqe_next = (listelm); \
3353 *(listelm)->field.tqe_prev = (elm); \
3354 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
3355 } while (0)
3356
3357 #define TAILQ_REMOVE(head, elm, field) do { \
3358 if (((elm)->field.tqe_next) != NULL) \
3359 (elm)->field.tqe_next->field.tqe_prev = \
3360 (elm)->field.tqe_prev; \
3361 else \
3362 (head)->tqh_last = (elm)->field.tqe_prev; \
3363 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
3364 _Q_INVALIDATE((elm)->field.tqe_prev); \
3365 _Q_INVALIDATE((elm)->field.tqe_next); \
3366 } while (0)
3367
3368 #define TAILQ_REPLACE(head, elm, elm2, field) do { \
3369 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
3370 (elm2)->field.tqe_next->field.tqe_prev = \
3371 &(elm2)->field.tqe_next; \
3372 else \
3373 (head)->tqh_last = &(elm2)->field.tqe_next; \
3374 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
3375 *(elm2)->field.tqe_prev = (elm2); \
3376 _Q_INVALIDATE((elm)->field.tqe_prev); \
3377 _Q_INVALIDATE((elm)->field.tqe_next); \
3378 } while (0)
3379
3380 #define TAILQ_CONCAT(head1, head2, field) do { \
3381 if (!TAILQ_EMPTY(head2)) { \
3382 *(head1)->tqh_last = (head2)->tqh_first; \
3383 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
3384 (head1)->tqh_last = (head2)->tqh_last; \
3385 TAILQ_INIT((head2)); \
3386 } \
3387 } while (0)
3388 #endif /* !HAVE_SYS_QUEUE */
3389
3390 #if !HAVE_SYS_TREE
3391 /*
3392 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
3393 * All rights reserved.
3394 *
3395 * Redistribution and use in source and binary forms, with or without
3396 * modification, are permitted provided that the following conditions
3397 * are met:
3398 * 1. Redistributions of source code must retain the above copyright
3399 * notice, this list of conditions and the following disclaimer.
3400 * 2. Redistributions in binary form must reproduce the above copyright
3401 * notice, this list of conditions and the following disclaimer in the
3402 * documentation and/or other materials provided with the distribution.
3403 *
3404 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
3405 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
3406 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
3407 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
3408 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
3409 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3410 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3411 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3412 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
3413 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3414 */
3415
3416 /* OPENBSD ORIGINAL: sys/sys/tree.h */
3417
3418 /*
3419 * This file defines data structures for different types of trees:
3420 * splay trees and red-black trees.
3421 *
3422 * A splay tree is a self-organizing data structure. Every operation
3423 * on the tree causes a splay to happen. The splay moves the requested
3424 * node to the root of the tree and partly rebalances it.
3425 *
3426 * This has the benefit that request locality causes faster lookups as
3427 * the requested nodes move to the top of the tree. On the other hand,
3428 * every lookup causes memory writes.
3429 *
3430 * The Balance Theorem bounds the total access time for m operations
3431 * and n inserts on an initially empty tree as O((m + n)lg n). The
3432 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
3433 *
3434 * A red-black tree is a binary search tree with the node color as an
3435 * extra attribute. It fulfills a set of conditions:
3436 * - every search path from the root to a leaf consists of the
3437 * same number of black nodes,
3438 * - each red node (except for the root) has a black parent,
3439 * - each leaf node is black.
3440 *
3441 * Every operation on a red-black tree is bounded as O(lg n).
3442 * The maximum height of a red-black tree is 2lg (n+1).
3443 */
3444
3445 #define SPLAY_HEAD(name, type) \
3446 struct name { \
3447 struct type *sph_root; /* root of the tree */ \
3448 }
3449
3450 #define SPLAY_INITIALIZER(root) \
3451 { NULL }
3452
3453 #define SPLAY_INIT(root) do { \
3454 (root)->sph_root = NULL; \
3455 } while (0)
3456
3457 #define SPLAY_ENTRY(type) \
3458 struct { \
3459 struct type *spe_left; /* left element */ \
3460 struct type *spe_right; /* right element */ \
3461 }
3462
3463 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
3464 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
3465 #define SPLAY_ROOT(head) (head)->sph_root
3466 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
3467
3468 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
3469 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
3470 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
3471 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
3472 (head)->sph_root = tmp; \
3473 } while (0)
3474
3475 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
3476 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
3477 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
3478 (head)->sph_root = tmp; \
3479 } while (0)
3480
3481 #define SPLAY_LINKLEFT(head, tmp, field) do { \
3482 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
3483 tmp = (head)->sph_root; \
3484 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
3485 } while (0)
3486
3487 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
3488 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
3489 tmp = (head)->sph_root; \
3490 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
3491 } while (0)
3492
3493 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
3494 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
3495 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
3496 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
3497 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
3498 } while (0)
3499
3500 /* Generates prototypes and inline functions */
3501
3502 #define SPLAY_PROTOTYPE(name, type, field, cmp) \
3503 void name##_SPLAY(struct name *, struct type *); \
3504 void name##_SPLAY_MINMAX(struct name *, int); \
3505 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
3506 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
3507 \
3508 /* Finds the node with the same key as elm */ \
3509 static __inline struct type * \
3510 name##_SPLAY_FIND(struct name *head, struct type *elm) \
3511 { \
3512 if (SPLAY_EMPTY(head)) \
3513 return(NULL); \
3514 name##_SPLAY(head, elm); \
3515 if ((cmp)(elm, (head)->sph_root) == 0) \
3516 return (head->sph_root); \
3517 return (NULL); \
3518 } \
3519 \
3520 static __inline struct type * \
3521 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
3522 { \
3523 name##_SPLAY(head, elm); \
3524 if (SPLAY_RIGHT(elm, field) != NULL) { \
3525 elm = SPLAY_RIGHT(elm, field); \
3526 while (SPLAY_LEFT(elm, field) != NULL) { \
3527 elm = SPLAY_LEFT(elm, field); \
3528 } \
3529 } else \
3530 elm = NULL; \
3531 return (elm); \
3532 } \
3533 \
3534 static __inline struct type * \
3535 name##_SPLAY_MIN_MAX(struct name *head, int val) \
3536 { \
3537 name##_SPLAY_MINMAX(head, val); \
3538 return (SPLAY_ROOT(head)); \
3539 }
3540
3541 /* Main splay operation.
3542 * Moves node close to the key of elm to top
3543 */
3544 #define SPLAY_GENERATE(name, type, field, cmp) \
3545 struct type * \
3546 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
3547 { \
3548 if (SPLAY_EMPTY(head)) { \
3549 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
3550 } else { \
3551 int __comp; \
3552 name##_SPLAY(head, elm); \
3553 __comp = (cmp)(elm, (head)->sph_root); \
3554 if(__comp < 0) { \
3555 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
3556 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
3557 SPLAY_LEFT((head)->sph_root, field) = NULL; \
3558 } else if (__comp > 0) { \
3559 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
3560 SPLAY_LEFT(elm, field) = (head)->sph_root; \
3561 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
3562 } else \
3563 return ((head)->sph_root); \
3564 } \
3565 (head)->sph_root = (elm); \
3566 return (NULL); \
3567 } \
3568 \
3569 struct type * \
3570 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
3571 { \
3572 struct type *__tmp; \
3573 if (SPLAY_EMPTY(head)) \
3574 return (NULL); \
3575 name##_SPLAY(head, elm); \
3576 if ((cmp)(elm, (head)->sph_root) == 0) { \
3577 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
3578 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
3579 } else { \
3580 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
3581 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
3582 name##_SPLAY(head, elm); \
3583 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
3584 } \
3585 return (elm); \
3586 } \
3587 return (NULL); \
3588 } \
3589 \
3590 void \
3591 name##_SPLAY(struct name *head, struct type *elm) \
3592 { \
3593 struct type __node, *__left, *__right, *__tmp; \
3594 int __comp; \
3595 \
3596 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
3597 __left = __right = &__node; \
3598 \
3599 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
3600 if (__comp < 0) { \
3601 __tmp = SPLAY_LEFT((head)->sph_root, field); \
3602 if (__tmp == NULL) \
3603 break; \
3604 if ((cmp)(elm, __tmp) < 0){ \
3605 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
3606 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
3607 break; \
3608 } \
3609 SPLAY_LINKLEFT(head, __right, field); \
3610 } else if (__comp > 0) { \
3611 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
3612 if (__tmp == NULL) \
3613 break; \
3614 if ((cmp)(elm, __tmp) > 0){ \
3615 SPLAY_ROTATE_LEFT(head, __tmp, field); \
3616 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
3617 break; \
3618 } \
3619 SPLAY_LINKRIGHT(head, __left, field); \
3620 } \
3621 } \
3622 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
3623 } \
3624 \
3625 /* Splay with either the minimum or the maximum element \
3626 * Used to find minimum or maximum element in tree. \
3627 */ \
3628 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
3629 { \
3630 struct type __node, *__left, *__right, *__tmp; \
3631 \
3632 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
3633 __left = __right = &__node; \
3634 \
3635 while (1) { \
3636 if (__comp < 0) { \
3637 __tmp = SPLAY_LEFT((head)->sph_root, field); \
3638 if (__tmp == NULL) \
3639 break; \
3640 if (__comp < 0){ \
3641 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
3642 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
3643 break; \
3644 } \
3645 SPLAY_LINKLEFT(head, __right, field); \
3646 } else if (__comp > 0) { \
3647 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
3648 if (__tmp == NULL) \
3649 break; \
3650 if (__comp > 0) { \
3651 SPLAY_ROTATE_LEFT(head, __tmp, field); \
3652 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
3653 break; \
3654 } \
3655 SPLAY_LINKRIGHT(head, __left, field); \
3656 } \
3657 } \
3658 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
3659 }
3660
3661 #define SPLAY_NEGINF -1
3662 #define SPLAY_INF 1
3663
3664 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
3665 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
3666 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
3667 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
3668 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
3669 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
3670 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
3671 : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
3672
3673 #define SPLAY_FOREACH(x, name, head) \
3674 for ((x) = SPLAY_MIN(name, head); \
3675 (x) != NULL; \
3676 (x) = SPLAY_NEXT(name, head, x))
3677
3678 /* Macros that define a red-black tree */
3679 #define RB_HEAD(name, type) \
3680 struct name { \
3681 struct type *rbh_root; /* root of the tree */ \
3682 }
3683
3684 #define RB_INITIALIZER(root) \
3685 { NULL }
3686
3687 #define RB_INIT(root) do { \
3688 (root)->rbh_root = NULL; \
3689 } while (0)
3690
3691 #define RB_BLACK 0
3692 #define RB_RED 1
3693 #define RB_ENTRY(type) \
3694 struct { \
3695 struct type *rbe_left; /* left element */ \
3696 struct type *rbe_right; /* right element */ \
3697 struct type *rbe_parent; /* parent element */ \
3698 int rbe_color; /* node color */ \
3699 }
3700
3701 #define RB_LEFT(elm, field) (elm)->field.rbe_left
3702 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
3703 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
3704 #define RB_COLOR(elm, field) (elm)->field.rbe_color
3705 #define RB_ROOT(head) (head)->rbh_root
3706 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
3707
3708 #define RB_SET(elm, parent, field) do { \
3709 RB_PARENT(elm, field) = parent; \
3710 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
3711 RB_COLOR(elm, field) = RB_RED; \
3712 } while (0)
3713
3714 #define RB_SET_BLACKRED(black, red, field) do { \
3715 RB_COLOR(black, field) = RB_BLACK; \
3716 RB_COLOR(red, field) = RB_RED; \
3717 } while (0)
3718
3719 #ifndef RB_AUGMENT
3720 #define RB_AUGMENT(x) do {} while (0)
3721 #endif
3722
3723 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
3724 (tmp) = RB_RIGHT(elm, field); \
3725 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
3726 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
3727 } \
3728 RB_AUGMENT(elm); \
3729 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
3730 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
3731 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
3732 else \
3733 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
3734 } else \
3735 (head)->rbh_root = (tmp); \
3736 RB_LEFT(tmp, field) = (elm); \
3737 RB_PARENT(elm, field) = (tmp); \
3738 RB_AUGMENT(tmp); \
3739 if ((RB_PARENT(tmp, field))) \
3740 RB_AUGMENT(RB_PARENT(tmp, field)); \
3741 } while (0)
3742
3743 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
3744 (tmp) = RB_LEFT(elm, field); \
3745 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
3746 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
3747 } \
3748 RB_AUGMENT(elm); \
3749 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
3750 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
3751 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
3752 else \
3753 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
3754 } else \
3755 (head)->rbh_root = (tmp); \
3756 RB_RIGHT(tmp, field) = (elm); \
3757 RB_PARENT(elm, field) = (tmp); \
3758 RB_AUGMENT(tmp); \
3759 if ((RB_PARENT(tmp, field))) \
3760 RB_AUGMENT(RB_PARENT(tmp, field)); \
3761 } while (0)
3762
3763 /* Generates prototypes and inline functions */
3764 #define RB_PROTOTYPE(name, type, field, cmp) \
3765 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
3766 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
3767 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
3768 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
3769 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
3770 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
3771 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
3772 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
3773 attr struct type *name##_RB_FIND(struct name *, struct type *); \
3774 attr struct type *name##_RB_NFIND(struct name *, struct type *); \
3775 attr struct type *name##_RB_NEXT(struct type *); \
3776 attr struct type *name##_RB_PREV(struct type *); \
3777 attr struct type *name##_RB_MINMAX(struct name *, int); \
3778 \
3779
3780 /* Main rb operation.
3781 * Moves node close to the key of elm to top
3782 */
3783 #define RB_GENERATE(name, type, field, cmp) \
3784 RB_GENERATE_INTERNAL(name, type, field, cmp,)
3785 #define RB_GENERATE_STATIC(name, type, field, cmp) \
3786 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
3787 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
3788 attr void \
3789 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
3790 { \
3791 struct type *parent, *gparent, *tmp; \
3792 while ((parent = RB_PARENT(elm, field)) && \
3793 RB_COLOR(parent, field) == RB_RED) { \
3794 gparent = RB_PARENT(parent, field); \
3795 if (parent == RB_LEFT(gparent, field)) { \
3796 tmp = RB_RIGHT(gparent, field); \
3797 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
3798 RB_COLOR(tmp, field) = RB_BLACK; \
3799 RB_SET_BLACKRED(parent, gparent, field);\
3800 elm = gparent; \
3801 continue; \
3802 } \
3803 if (RB_RIGHT(parent, field) == elm) { \
3804 RB_ROTATE_LEFT(head, parent, tmp, field);\
3805 tmp = parent; \
3806 parent = elm; \
3807 elm = tmp; \
3808 } \
3809 RB_SET_BLACKRED(parent, gparent, field); \
3810 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
3811 } else { \
3812 tmp = RB_LEFT(gparent, field); \
3813 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
3814 RB_COLOR(tmp, field) = RB_BLACK; \
3815 RB_SET_BLACKRED(parent, gparent, field);\
3816 elm = gparent; \
3817 continue; \
3818 } \
3819 if (RB_LEFT(parent, field) == elm) { \
3820 RB_ROTATE_RIGHT(head, parent, tmp, field);\
3821 tmp = parent; \
3822 parent = elm; \
3823 elm = tmp; \
3824 } \
3825 RB_SET_BLACKRED(parent, gparent, field); \
3826 RB_ROTATE_LEFT(head, gparent, tmp, field); \
3827 } \
3828 } \
3829 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
3830 } \
3831 \
3832 attr void \
3833 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
3834 { \
3835 struct type *tmp; \
3836 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
3837 elm != RB_ROOT(head)) { \
3838 if (RB_LEFT(parent, field) == elm) { \
3839 tmp = RB_RIGHT(parent, field); \
3840 if (RB_COLOR(tmp, field) == RB_RED) { \
3841 RB_SET_BLACKRED(tmp, parent, field); \
3842 RB_ROTATE_LEFT(head, parent, tmp, field);\
3843 tmp = RB_RIGHT(parent, field); \
3844 } \
3845 if ((RB_LEFT(tmp, field) == NULL || \
3846 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
3847 (RB_RIGHT(tmp, field) == NULL || \
3848 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
3849 RB_COLOR(tmp, field) = RB_RED; \
3850 elm = parent; \
3851 parent = RB_PARENT(elm, field); \
3852 } else { \
3853 if (RB_RIGHT(tmp, field) == NULL || \
3854 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
3855 struct type *oleft; \
3856 if ((oleft = RB_LEFT(tmp, field)))\
3857 RB_COLOR(oleft, field) = RB_BLACK;\
3858 RB_COLOR(tmp, field) = RB_RED; \
3859 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
3860 tmp = RB_RIGHT(parent, field); \
3861 } \
3862 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
3863 RB_COLOR(parent, field) = RB_BLACK; \
3864 if (RB_RIGHT(tmp, field)) \
3865 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
3866 RB_ROTATE_LEFT(head, parent, tmp, field);\
3867 elm = RB_ROOT(head); \
3868 break; \
3869 } \
3870 } else { \
3871 tmp = RB_LEFT(parent, field); \
3872 if (RB_COLOR(tmp, field) == RB_RED) { \
3873 RB_SET_BLACKRED(tmp, parent, field); \
3874 RB_ROTATE_RIGHT(head, parent, tmp, field);\
3875 tmp = RB_LEFT(parent, field); \
3876 } \
3877 if ((RB_LEFT(tmp, field) == NULL || \
3878 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
3879 (RB_RIGHT(tmp, field) == NULL || \
3880 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
3881 RB_COLOR(tmp, field) = RB_RED; \
3882 elm = parent; \
3883 parent = RB_PARENT(elm, field); \
3884 } else { \
3885 if (RB_LEFT(tmp, field) == NULL || \
3886 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
3887 struct type *oright; \
3888 if ((oright = RB_RIGHT(tmp, field)))\
3889 RB_COLOR(oright, field) = RB_BLACK;\
3890 RB_COLOR(tmp, field) = RB_RED; \
3891 RB_ROTATE_LEFT(head, tmp, oright, field);\
3892 tmp = RB_LEFT(parent, field); \
3893 } \
3894 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
3895 RB_COLOR(parent, field) = RB_BLACK; \
3896 if (RB_LEFT(tmp, field)) \
3897 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
3898 RB_ROTATE_RIGHT(head, parent, tmp, field);\
3899 elm = RB_ROOT(head); \
3900 break; \
3901 } \
3902 } \
3903 } \
3904 if (elm) \
3905 RB_COLOR(elm, field) = RB_BLACK; \
3906 } \
3907 \
3908 attr struct type * \
3909 name##_RB_REMOVE(struct name *head, struct type *elm) \
3910 { \
3911 struct type *child, *parent, *old = elm; \
3912 int color; \
3913 if (RB_LEFT(elm, field) == NULL) \
3914 child = RB_RIGHT(elm, field); \
3915 else if (RB_RIGHT(elm, field) == NULL) \
3916 child = RB_LEFT(elm, field); \
3917 else { \
3918 struct type *left; \
3919 elm = RB_RIGHT(elm, field); \
3920 while ((left = RB_LEFT(elm, field))) \
3921 elm = left; \
3922 child = RB_RIGHT(elm, field); \
3923 parent = RB_PARENT(elm, field); \
3924 color = RB_COLOR(elm, field); \
3925 if (child) \
3926 RB_PARENT(child, field) = parent; \
3927 if (parent) { \
3928 if (RB_LEFT(parent, field) == elm) \
3929 RB_LEFT(parent, field) = child; \
3930 else \
3931 RB_RIGHT(parent, field) = child; \
3932 RB_AUGMENT(parent); \
3933 } else \
3934 RB_ROOT(head) = child; \
3935 if (RB_PARENT(elm, field) == old) \
3936 parent = elm; \
3937 (elm)->field = (old)->field; \
3938 if (RB_PARENT(old, field)) { \
3939 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
3940 RB_LEFT(RB_PARENT(old, field), field) = elm;\
3941 else \
3942 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
3943 RB_AUGMENT(RB_PARENT(old, field)); \
3944 } else \
3945 RB_ROOT(head) = elm; \
3946 RB_PARENT(RB_LEFT(old, field), field) = elm; \
3947 if (RB_RIGHT(old, field)) \
3948 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
3949 if (parent) { \
3950 left = parent; \
3951 do { \
3952 RB_AUGMENT(left); \
3953 } while ((left = RB_PARENT(left, field))); \
3954 } \
3955 goto color; \
3956 } \
3957 parent = RB_PARENT(elm, field); \
3958 color = RB_COLOR(elm, field); \
3959 if (child) \
3960 RB_PARENT(child, field) = parent; \
3961 if (parent) { \
3962 if (RB_LEFT(parent, field) == elm) \
3963 RB_LEFT(parent, field) = child; \
3964 else \
3965 RB_RIGHT(parent, field) = child; \
3966 RB_AUGMENT(parent); \
3967 } else \
3968 RB_ROOT(head) = child; \
3969 color: \
3970 if (color == RB_BLACK) \
3971 name##_RB_REMOVE_COLOR(head, parent, child); \
3972 return (old); \
3973 } \
3974 \
3975 /* Inserts a node into the RB tree */ \
3976 attr struct type * \
3977 name##_RB_INSERT(struct name *head, struct type *elm) \
3978 { \
3979 struct type *tmp; \
3980 struct type *parent = NULL; \
3981 int comp = 0; \
3982 tmp = RB_ROOT(head); \
3983 while (tmp) { \
3984 parent = tmp; \
3985 comp = (cmp)(elm, parent); \
3986 if (comp < 0) \
3987 tmp = RB_LEFT(tmp, field); \
3988 else if (comp > 0) \
3989 tmp = RB_RIGHT(tmp, field); \
3990 else \
3991 return (tmp); \
3992 } \
3993 RB_SET(elm, parent, field); \
3994 if (parent != NULL) { \
3995 if (comp < 0) \
3996 RB_LEFT(parent, field) = elm; \
3997 else \
3998 RB_RIGHT(parent, field) = elm; \
3999 RB_AUGMENT(parent); \
4000 } else \
4001 RB_ROOT(head) = elm; \
4002 name##_RB_INSERT_COLOR(head, elm); \
4003 return (NULL); \
4004 } \
4005 \
4006 /* Finds the node with the same key as elm */ \
4007 attr struct type * \
4008 name##_RB_FIND(struct name *head, struct type *elm) \
4009 { \
4010 struct type *tmp = RB_ROOT(head); \
4011 int comp; \
4012 while (tmp) { \
4013 comp = cmp(elm, tmp); \
4014 if (comp < 0) \
4015 tmp = RB_LEFT(tmp, field); \
4016 else if (comp > 0) \
4017 tmp = RB_RIGHT(tmp, field); \
4018 else \
4019 return (tmp); \
4020 } \
4021 return (NULL); \
4022 } \
4023 \
4024 /* Finds the first node greater than or equal to the search key */ \
4025 attr struct type * \
4026 name##_RB_NFIND(struct name *head, struct type *elm) \
4027 { \
4028 struct type *tmp = RB_ROOT(head); \
4029 struct type *res = NULL; \
4030 int comp; \
4031 while (tmp) { \
4032 comp = cmp(elm, tmp); \
4033 if (comp < 0) { \
4034 res = tmp; \
4035 tmp = RB_LEFT(tmp, field); \
4036 } \
4037 else if (comp > 0) \
4038 tmp = RB_RIGHT(tmp, field); \
4039 else \
4040 return (tmp); \
4041 } \
4042 return (res); \
4043 } \
4044 \
4045 /* ARGSUSED */ \
4046 attr struct type * \
4047 name##_RB_NEXT(struct type *elm) \
4048 { \
4049 if (RB_RIGHT(elm, field)) { \
4050 elm = RB_RIGHT(elm, field); \
4051 while (RB_LEFT(elm, field)) \
4052 elm = RB_LEFT(elm, field); \
4053 } else { \
4054 if (RB_PARENT(elm, field) && \
4055 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
4056 elm = RB_PARENT(elm, field); \
4057 else { \
4058 while (RB_PARENT(elm, field) && \
4059 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
4060 elm = RB_PARENT(elm, field); \
4061 elm = RB_PARENT(elm, field); \
4062 } \
4063 } \
4064 return (elm); \
4065 } \
4066 \
4067 /* ARGSUSED */ \
4068 attr struct type * \
4069 name##_RB_PREV(struct type *elm) \
4070 { \
4071 if (RB_LEFT(elm, field)) { \
4072 elm = RB_LEFT(elm, field); \
4073 while (RB_RIGHT(elm, field)) \
4074 elm = RB_RIGHT(elm, field); \
4075 } else { \
4076 if (RB_PARENT(elm, field) && \
4077 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
4078 elm = RB_PARENT(elm, field); \
4079 else { \
4080 while (RB_PARENT(elm, field) && \
4081 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
4082 elm = RB_PARENT(elm, field); \
4083 elm = RB_PARENT(elm, field); \
4084 } \
4085 } \
4086 return (elm); \
4087 } \
4088 \
4089 attr struct type * \
4090 name##_RB_MINMAX(struct name *head, int val) \
4091 { \
4092 struct type *tmp = RB_ROOT(head); \
4093 struct type *parent = NULL; \
4094 while (tmp) { \
4095 parent = tmp; \
4096 if (val < 0) \
4097 tmp = RB_LEFT(tmp, field); \
4098 else \
4099 tmp = RB_RIGHT(tmp, field); \
4100 } \
4101 return (parent); \
4102 }
4103
4104 #define RB_NEGINF -1
4105 #define RB_INF 1
4106
4107 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
4108 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
4109 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
4110 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
4111 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
4112 #define RB_PREV(name, x, y) name##_RB_PREV(y)
4113 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
4114 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
4115
4116 #define RB_FOREACH(x, name, head) \
4117 for ((x) = RB_MIN(name, head); \
4118 (x) != NULL; \
4119 (x) = name##_RB_NEXT(x))
4120
4121 #define RB_FOREACH_SAFE(x, name, head, y) \
4122 for ((x) = RB_MIN(name, head); \
4123 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
4124 (x) = (y))
4125
4126 #define RB_FOREACH_REVERSE(x, name, head) \
4127 for ((x) = RB_MAX(name, head); \
4128 (x) != NULL; \
4129 (x) = name##_RB_PREV(x))
4130
4131 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
4132 for ((x) = RB_MAX(name, head); \
4133 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
4134 (x) = (y))
4135 #endif /* !HAVE_SYS_TREE */
4136
4137 #if !HAVE_FTS
4138 /*
4139 * Compatibility for fts(3) functions.
4140 */
4141 typedef struct {
4142 struct _ftsent *fts_cur; /* current node */
4143 struct _ftsent *fts_child; /* linked list of children */
4144 struct _ftsent **fts_array; /* sort array */
4145 dev_t fts_dev; /* starting device # */
4146 char *fts_path; /* path for this descent */
4147 int fts_rfd; /* fd for root */
4148 size_t fts_pathlen; /* sizeof(path) */
4149 int fts_nitems; /* elements in the sort array */
4150 int (*fts_compar)(const struct _ftsent **, const struct _ftsent **); /* compare function */
4151 #define FTS_COMFOLLOW 0x0001 /* follow command line symlinks */
4152 #define FTS_LOGICAL 0x0002 /* logical walk */
4153 #define FTS_NOCHDIR 0x0004 /* don't change directories */
4154 #define FTS_NOSTAT 0x0008 /* don't get stat info */
4155 #define FTS_PHYSICAL 0x0010 /* physical walk */
4156 #define FTS_SEEDOT 0x0020 /* return dot and dot-dot */
4157 #define FTS_XDEV 0x0040 /* don't cross devices */
4158 #define FTS_OPTIONMASK 0x00ff /* valid user option mask */
4159 #define FTS_NAMEONLY 0x1000 /* (private) child names only */
4160 #define FTS_STOP 0x2000 /* (private) unrecoverable error */
4161 int fts_options; /* fts_open options, global flags */
4162 } FTS;
4163
4164 typedef struct _ftsent {
4165 struct _ftsent *fts_cycle; /* cycle node */
4166 struct _ftsent *fts_parent; /* parent directory */
4167 struct _ftsent *fts_link; /* next file in directory */
4168 long fts_number; /* local numeric value */
4169 void *fts_pointer; /* local address value */
4170 char *fts_accpath; /* access path */
4171 char *fts_path; /* root path */
4172 int fts_errno; /* errno for this node */
4173 int fts_symfd; /* fd for symlink */
4174 size_t fts_pathlen; /* strlen(fts_path) */
4175 size_t fts_namelen; /* strlen(fts_name) */
4176 ino_t fts_ino; /* inode */
4177 dev_t fts_dev; /* device */
4178 nlink_t fts_nlink; /* link count */
4179 #define FTS_ROOTPARENTLEVEL -1
4180 #define FTS_ROOTLEVEL 0
4181 #define FTS_MAXLEVEL 0x7fffffff
4182 int fts_level; /* depth (-1 to N) */
4183 #define FTS_D 1 /* preorder directory */
4184 #define FTS_DC 2 /* directory that causes cycles */
4185 #define FTS_DEFAULT 3 /* none of the above */
4186 #define FTS_DNR 4 /* unreadable directory */
4187 #define FTS_DOT 5 /* dot or dot-dot */
4188 #define FTS_DP 6 /* postorder directory */
4189 #define FTS_ERR 7 /* error; errno is set */
4190 #define FTS_F 8 /* regular file */
4191 #define FTS_INIT 9 /* initialized only */
4192 #define FTS_NS 10 /* stat(2) failed */
4193 #define FTS_NSOK 11 /* no stat(2) requested */
4194 #define FTS_SL 12 /* symbolic link */
4195 #define FTS_SLNONE 13 /* symbolic link without target */
4196 unsigned short fts_info; /* user flags for FTSENT structure */
4197 #define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */
4198 #define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */
4199 unsigned short fts_flags; /* private flags for FTSENT structure */
4200 #define FTS_AGAIN 1 /* read node again */
4201 #define FTS_FOLLOW 2 /* follow symbolic link */
4202 #define FTS_NOINSTR 3 /* no instructions */
4203 #define FTS_SKIP 4 /* discard node */
4204 unsigned short fts_instr; /* fts_set() instructions */
4205 unsigned short fts_spare; /* unused */
4206 struct stat *fts_statp; /* stat(2) information */
4207 char fts_name[1]; /* file name */
4208 } FTSENT;
4209
4210 FTSENT *fts_children(FTS *, int);
4211 int fts_close(FTS *);
4212 FTS *fts_open(char * const *, int,
4213 int (*)(const FTSENT **, const FTSENT **));
4214 FTSENT *fts_read(FTS *);
4215 int fts_set(FTS *, FTSENT *, int);
4216 #endif /* !HAVE_FTS */
4217
4218 #ifndef nitems
4219 #define nitems(x) (sizeof((x)) / sizeof((x)[0]))
4220 #endif
4221
4222 #ifndef __cleanup
4223 #define __cleanup(x) __attribute__((cleanup(x)))
4224 #endif
4225
4226 #ifndef __noreturn
4227 #define __noreturn __attribute__((noreturn))
4228 #endif
4229
4230 #ifndef __printflike
4231 #define __printflike(x, y) __attribute__((__format__(__printf__, x, y)))
4232 #endif
4233
4234 #ifndef _IsUnused
4235 #define _IsUnused __attribute__((__unused__))
4236 #endif
4237
4238 #endif /* __MKBUILD_CONFIG_H__ */
4239