1#! /bin/sh 2# 3# Copyright (c) 2014, 2015, 2016 Ingo Schwarze <schwarze@openbsd.org> 4# Copyright (c) 2017, 2018 Kristaps Dzonsons <kristaps@bsd.lv> 5# 6# Permission to use, copy, modify, and distribute this software for any 7# purpose with or without fee is hereby granted, provided that the above 8# copyright notice and this permission notice appear in all copies. 9# 10# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 18OCONFIGURE_VERSION="0.3.4" 19 20# 21# This script outputs two files: config.h and Makefile.configure. 22# It tries to read from configure.local, which contains predefined 23# values we won't autoconfigure. 24# 25# If you want to use configure with your project, have your GNUmakefile 26# or BSDmakefile---whichever---try to import/include Makefile.configure 27# at the beginning of the file. 28# 29# Like so (note no quotes, no period, etc.): 30# 31# include Makefile.configure 32# 33# If it exists, configure was run; otherwise, it wasn't. 34# 35# You'll probably want to change parts of this file. I've noted the 36# parts that you'll probably change in the section documentation. 37# 38# See https://github.com/kristapsdz/oconfigure for more. 39 40set -e 41 42#---------------------------------------------------------------------- 43# Prepare for running: move aside previous configure runs. 44# Output file descriptor usage: 45# 1 (stdout): config.h or Makefile.configure 46# 2 (stderr): original stderr, usually to the console 47# 3: config.log 48# You DO NOT want to change this. 49#---------------------------------------------------------------------- 50 51[ -w config.log ] && mv config.log config.log.old 52[ -w config.h ] && mv config.h config.h.old 53 54exec 3> config.log 55echo "config.log: writing..." 56 57# GNU submake prints different output if invoked recursively, which 58# messes up CC and CFLAGS detection. Pass --no-print-directory if 59# we have a MAKELEVEL (GNU and FreeBSD make) and the argument is 60# allowed. 61 62MAKE_FLAGS="" 63 64if [ -n "${MAKELEVEL}" ]; then 65 if [ "${MAKELEVEL}" -gt 0 ] ; then 66 MAKE_FLAGS="--no-print-directory" 67 echo "all:" | make ${MAKE_FLAGS} -sf - 2>/dev/null || MAKE_FLAGS="" 68 fi 69fi 70 71if [ -n "$MAKE_FLAGS" ]; then 72 echo "GNU submake detected: using --no-print-directory" 1>&2 73 echo "GNU submake detected: using --no-print-directory" 1>&3 74fi 75 76#---------------------------------------------------------------------- 77# Initialize all variables here such that nothing can leak in from the 78# environment except for CC and CFLAGS, which we might have passed in. 79#---------------------------------------------------------------------- 80 81AR=`printf "all:\\n\\t@echo \\\$(AR)\\n" | make ${MAKE_FLAGS} -sf -` 82CC=`printf "all:\\n\\t@echo \\\$(CC)\\n" | make ${MAKE_FLAGS} -sf -` 83CFLAGS=`printf "all:\\n\\t@echo \\\$(CFLAGS)\\n" | make ${MAKE_FLAGS} -sf -` 84CFLAGS="${CFLAGS} -g -W -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes" 85CFLAGS="${CFLAGS} -Wwrite-strings -Wno-unused-parameter" 86LDADD= 87LDADD_B64_NTOP= 88LDADD_CRYPT= 89LDADD_EXECINFO= 90LDADD_MD5= 91LDADD_SHA2= 92LDADD_LIB_SOCKET= 93LDADD_STATIC= 94CPPFLAGS= 95LDFLAGS= 96DESTDIR= 97PREFIX="/usr/local" 98BINDIR= 99SBINDIR= 100INCLUDEDIR= 101LIBDIR= 102MANDIR= 103SHAREDIR= 104INSTALL="install" 105INSTALL_PROGRAM= 106INSTALL_LIB= 107INSTALL_MAN= 108INSTALL_DATA= 109LTO=auto 110 111# SunOS sets "cc", but this doesn't exist. 112# It does have gcc, so try that instead. 113# Prefer clang, though. 114 115command -v ${CC} 2>/dev/null 1>&2 || { 116 echo "${CC} not found: trying clang" 1>&2 117 echo "${CC} not found: trying clang" 1>&3 118 CC=clang 119 command -v ${CC} 2>/dev/null 1>&2 || { 120 echo "${CC} not found: trying gcc" 1>&2 121 echo "${CC} not found: trying gcc" 1>&3 122 CC=gcc 123 command -v ${CC} 2>/dev/null 1>&2 || { 124 echo "gcc not found: giving up" 1>&2 125 echo "gcc not found: giving up" 1>&3 126 exit 1 127 } 128 } 129} 130 131#---------------------------------------------------------------------- 132# Allow certain variables to be overriden on the command line. 133#---------------------------------------------------------------------- 134 135for keyvals in "$@" 136do 137 key=`echo $keyvals | cut -s -d '=' -f 1` 138 if [ -z "$key" ] 139 then 140 echo "$0: invalid key-value: $keyvals" 1>&2 141 exit 1 142 fi 143 val=`echo $keyvals | cut -d '=' -f 2-` 144 case "$key" in 145 LDADD) 146 LDADD="$val" ;; 147 LDFLAGS) 148 LDFLAGS="$val" ;; 149 CPPFLAGS) 150 CPPFLAGS="$val" ;; 151 DESTDIR) 152 DESTDIR="$val" ;; 153 PREFIX) 154 PREFIX="$val" ;; 155 MANDIR) 156 MANDIR="$val" ;; 157 LIBDIR) 158 LIBDIR="$val" ;; 159 BINDIR) 160 BINDIR="$val" ;; 161 SHAREDIR) 162 SHAREDIR="$val" ;; 163 SBINDIR) 164 SBINDIR="$val" ;; 165 INCLUDEDIR) 166 INCLUDEDIR="$val" ;; 167 LTO) 168 LTO="$val" ;; 169 *) 170 echo "$0: invalid key: $key" 1>&2 171 exit 1 172 esac 173done 174 175 176#---------------------------------------------------------------------- 177# These are the values that will be pushed into config.h after we test 178# for whether they're supported or not. 179# Each of these must have a runtest(), below. 180# Please sort by alpha, for clarity. 181# You WANT to change this. 182#---------------------------------------------------------------------- 183 184HAVE_ARC4RANDOM= 185HAVE_B64_NTOP= 186HAVE_CAPSICUM= 187HAVE_CRYPT= 188HAVE_ENDIAN_H= 189HAVE_ERR= 190HAVE_EXECINFO= 191HAVE_EXPLICIT_BZERO= 192HAVE_FTS= 193HAVE_GETEXECNAME= 194HAVE_GETPROGNAME= 195HAVE_INFTIM= 196HAVE_MD5= 197HAVE_MEMMEM= 198HAVE_MEMRCHR= 199HAVE_MEMSET_S= 200HAVE_MKFIFOAT= 201HAVE_MKNODAT= 202HAVE_OSBYTEORDER_H= 203HAVE_PATH_MAX= 204HAVE_PLEDGE= 205HAVE_PROGRAM_INVOCATION_SHORT_NAME= 206HAVE_BSD_QSORT_R= 207HAVE_GNU_QSORT_R= 208HAVE_QSORT_R= 209HAVE_READPASSPHRASE= 210HAVE_REALLOCARRAY= 211HAVE_RECALLOCARRAY= 212HAVE_SANDBOX_INIT= 213HAVE_SECCOMP_FILTER= 214HAVE_SETRESGID= 215HAVE_SETRESUID= 216HAVE_SOCK_NONBLOCK= 217HAVE_SHA2= 218HAVE_SHA2_H= 219HAVE_STRLCAT= 220HAVE_STRLCPY= 221HAVE_STRNDUP= 222HAVE_STRNLEN= 223HAVE_STRNSTR= 224HAVE_STRTONUM= 225HAVE_SYS_BYTEORDER_H= 226HAVE_SYS_ENDIAN_H= 227HAVE_SYS_MKDEV_H= 228HAVE_SYS_QUEUE= 229HAVE_SYS_SYSMACROS= 230HAVE_SYS_TREE= 231HAVE_SYSTRACE=0 232HAVE_UNVEIL= 233HAVE_WAIT_ANY= 234HAVE___PROGNAME= 235 236#---------------------------------------------------------------------- 237# Allow configure.local to override all variables, default settings, 238# command-line arguments, and tested features, above. 239# You PROBABLY DO NOT want to change this. 240#---------------------------------------------------------------------- 241 242if [ -r ./configure.local ]; then 243 echo "configure.local: reading..." 1>&2 244 echo "configure.local: reading..." 1>&3 245 cat ./configure.local 1>&3 246 . ./configure.local 247else 248 echo "configure.local: no (fully automatic configuration)" 1>&2 249 echo "configure.local: no (fully automatic configuration)" 1>&3 250fi 251 252echo 1>&3 253 254#---------------------------------------------------------------------- 255# Infrastructure for running tests. 256# These consists of a series of functions that will attempt to run the 257# given test file and record its exit into a HAVE_xxx variable. 258# You DO NOT want to change this. 259#---------------------------------------------------------------------- 260 261COMP="${CC} ${CFLAGS} ${CPPFLAGS} -Wno-unused -Werror" 262 263singleltotest() { 264 command -v $1 2>/dev/null 1>&2 || return 1 265cat >test-lto.c << __HEREDOC__ 266int main(int argc, char *argv[]) { return 0; } 267__HEREDOC__ 268 cat 1>&3 << __HEREDOC__ 269lto: testing... 270${COMP} -c -flto=thin -o test-lto.o test-lto.c 1>&3 2>&3 && $1 rcs test-lto.a test-lto.o 1>&3 2>&3 && ${COMP} -flto=thin -o test-lto test-lto.a ${LDFLAGS} 271__HEREDOC__ 272 if ${COMP} -c -flto=thin -o test-lto.o test-lto.c 1>&3 2>&3 && $1 rcs test-lto.a test-lto.o 1>&3 2>&3 && ${COMP} -flto=thin -o test-lto test-lto.a ${LDFLAGS} 1>&3 2>&3; then 273 AR=$1 274 LTO=thin 275 rm -f test-lto.a test-lto.c test-lto.o test-lto 276 return 0 277 else 278 cat 1>&3 << __HEREDOC__ 279lto: testing... 280${COMP} -c -flto -o test-lto.o test-lto.c 1>&3 2>&3 && $1 rcs test-lto.a test-lto.o 1>&3 2>&3 && ${COMP} -flto -o test-lto test-lto.a ${LDFLAGS} 281__HEREDOC__ 282 if ${COMP} -c -flto -o test-lto.o test-lto.c 1>&3 2>&3 && $1 rcs test-lto.a test-lto.o 1>&3 2>&3 && ${COMP} -flto -o test-lto test-lto.a ${LDFLAGS} 1>&3 2>&3; then 283 AR=$1 284 LTO=full 285 rm -f test-lto.a test-lto.c test-lto.o test-lto 286 return 0 287 fi 288 fi 289 290 return 1 291} 292 293runltotest() { 294 if [ ! "${LTO}" = "0" ]; then 295 singleltotest ${AR} || \ 296 singleltotest "$(which $(echo ${CC} | sed 's,clang,llvm-ar,'))" || \ 297 singleltotest "$(dirname $(which ${CC}))/llvm-ar" || \ 298 singleltotest "$(which $(echo ${CC} | sed 's,gcc,gcc-ar,'))" || \ 299 singleltotest "$(dirname $(which ${CC}))/gcc-ar" || \ 300 singleltotest "$(which $(readlink $(which ${CC})) | sed 's,gcc,gcc-ar,')" || \ 301 LTO=disabled 302 fi 303 304 if [ "${LTO}" = "thin" ]; then 305 echo "lto: thin" 306 echo "AR: ${AR}" 307 echo "CC: ${CC}" 308 CFLAGS="${CFLAGS} -flto=thin" 309 LDFLAGS="${LDFLAGS} -flto=thin" 310 elif [ "${LTO}" = "full" ]; then 311 echo "lto: full" 312 echo "AR: ${AR}" 313 echo "CC: ${CC}" 314 CFLAGS="${CFLAGS} -flto" 315 LDFLAGS="${LDFLAGS} -flto" 316 else 317 echo "lto: disabled" 318 fi 319 320 return 0 321} 322 323# Check whether this HAVE_ setting is manually overridden. 324# If yes, use the override, if no, do not decide anything yet. 325# Arguments: lower-case test name, manual value 326 327ismanual() { 328 [ -z "${3}" ] && return 1 329 echo "${1}: manual (HAVE_${2}=${3})" 1>&2 330 echo "${1}: manual (HAVE_${2}=${3})" 1>&3 331 echo 1>&3 332 return 0 333} 334 335# Run a single autoconfiguration test. 336# In case of success, enable the feature. 337# In case of failure, do not decide anything yet. 338# Arguments: lower-case test name, upper-case test name, additional 339# CFLAGS, additional LIBS. 340 341singletest() { 342 extralib="" 343 tests_c="$(dirname "$0")/tests.c" 344 cat 1>&3 << __HEREDOC__ 345${1}: testing... 346${COMP} -DTEST_${2} ${3} -o test-${1} ${tests_c} ${LDFLAGS} ${4} 347__HEREDOC__ 348 if ${COMP} -DTEST_${2} ${3} -o "test-${1}" ${tests_c} ${LDFLAGS} ${4} 1>&3 2>&3; then 349 echo "${1}: ${CC} succeeded" 1>&3 350 else 351 if [ -n "${5}" ] ; then 352 echo "${1}: ${CC} failed with $? (retrying)" 1>&3 353 cat 1>&3 << __HEREDOC__ 354${1}: testing... 355${COMP} -DTEST_${2} ${3} -o test-${1} tests.c ${LDFLAGS} ${5} 356__HEREDOC__ 357 if ${COMP} -DTEST_${2} ${3} -o "test-${1}" ${tests_c} ${LDFLAGS} ${5} 1>&3 2>&3; then 358 echo "${1}: ${CC} succeeded" 1>&3 359 extralib="(with ${5})" 360 else 361 echo "${1}: ${CC} failed with $?" 1>&3 362 echo 1>&3 363 return 1 364 fi 365 else 366 echo "${1}: ${CC} failed with $?" 1>&3 367 echo 1>&3 368 return 1 369 fi 370 fi 371 372 if [ -n "${extralib}" ] 373 then 374 eval "LDADD_${2}=\"${5}\"" 375 elif [ -n "${4}" ] 376 then 377 eval "LDADD_${2}=\"${4}\"" 378 fi 379 380 echo "${1}: yes ${extralib}" 1>&2 381 echo "${1}: yes ${extralib}" 1>&3 382 echo 1>&3 383 eval HAVE_${2}=1 384 rm "test-${1}" 385 return 0 386} 387 388# Run a complete autoconfiguration test, including the check for 389# a manual override and disabling the feature on failure. 390# Arguments: lower case name, upper case name, additional CFLAGS, 391# additional LDADD, alternative LDADD. 392 393runtest() { 394 eval _manual=\${HAVE_${2}} 395 ismanual "${1}" "${2}" "${_manual}" && return 0 396 singletest "${1}" "${2}" "${3}" "${4}" "${5}" && return 0 397 echo "${1}: no" 1>&2 398 eval HAVE_${2}=0 399 return 1 400} 401 402#---------------------------------------------------------------------- 403# Begin running the tests themselves. 404# All of your tests must be defined here. 405# Please sort as the HAVE_xxxx values were defined. 406# You WANT to change this. 407# It consists of the following columns: 408# runtest 409# (1) test file 410# (2) macro to set 411# (3) argument to cc *before* -o 412# (4) argument to cc *after* 413# (5) alternative argument to cc *after* 414#---------------------------------------------------------------------- 415 416runltotest 417runtest arc4random ARC4RANDOM || true 418runtest b64_ntop B64_NTOP "" "" "-lresolv" || true 419runtest capsicum CAPSICUM || true 420runtest crypt CRYPT "" "" "-lcrypt" || true 421runtest endian_h ENDIAN_H || true 422runtest err ERR || true 423runtest execinfo EXECINFO "" "" "-lexecinfo" || true 424runtest explicit_bzero EXPLICIT_BZERO || true 425runtest fts FTS || true 426runtest getexecname GETEXECNAME || true 427runtest getprogname GETPROGNAME || true 428runtest INFTIM INFTIM || true 429runtest lib_socket LIB_SOCKET "" "" "-lsocket -lnsl" || true 430runtest md5 MD5 "" "" "-lmd" || true 431runtest memmem MEMMEM || true 432runtest memrchr MEMRCHR || true 433runtest memset_s MEMSET_S || true 434runtest mkfifoat MKFIFOAT || true 435runtest mknodat MKNODAT || true 436runtest osbyteorder_h OSBYTEORDER_H || true 437runtest PATH_MAX PATH_MAX || true 438runtest pledge PLEDGE || true 439runtest program_invocation_short_name PROGRAM_INVOCATION_SHORT_NAME || true 440runtest "BSD qsort_r" BSD_QSORT_R || true 441runtest "GNU qsort_r" GNU_QSORT_R || true 442runtest readpassphrase READPASSPHRASE || true 443runtest reallocarray REALLOCARRAY || true 444runtest recallocarray RECALLOCARRAY || true 445runtest sandbox_init SANDBOX_INIT "-Wno-deprecated" || true 446runtest seccomp-filter SECCOMP_FILTER || true 447runtest setresgid SETRESGID || true 448runtest setresuid SETRESUID || true 449runtest sha2 SHA2 "" "" "-lmd" || true 450runtest SOCK_NONBLOCK SOCK_NONBLOCK || true 451runtest static STATIC "" "-static" || true 452runtest strlcat STRLCAT || true 453runtest strlcpy STRLCPY || true 454runtest strndup STRNDUP || true 455runtest strnlen STRNLEN || true 456runtest strnstr STRNSTR || true 457runtest strtonum STRTONUM || true 458runtest sys_byteorder_h SYS_BYTEORDER_H || true 459runtest sys_endian_h SYS_ENDIAN_H || true 460runtest sys_mkdev_h SYS_MKDEV_H || true 461runtest sys_sysmacros_h SYS_SYSMACROS_H || true 462runtest sys_queue SYS_QUEUE || true 463runtest sys_tree SYS_TREE || true 464runtest unveil UNVEIL || true 465runtest WAIT_ANY WAIT_ANY || true 466runtest __progname __PROGNAME || true 467 468if [ ${HAVE_BSD_QSORT_R} -eq 1 -o ${HAVE_GNU_QSORT_R} -eq 1 ] 469then 470 HAVE_QSORT_R=1 471else 472 HAVE_QSORT_R=0 473fi 474 475#---------------------------------------------------------------------- 476# Output writing: generate the config.h file. 477# This file contains all of the HAVE_xxxx variables necessary for 478# compiling your source. 479# You must include "config.h" BEFORE any other variables. 480# You WANT to change this. 481#---------------------------------------------------------------------- 482 483exec > config.h 484 485# Start with prologue. 486 487cat << __HEREDOC__ 488#ifndef OCONFIGURE_CONFIG_H 489#define OCONFIGURE_CONFIG_H 490 491#ifdef __cplusplus 492# error "Do not use C++: this is a C application." 493#endif 494#if !defined(__GNUC__) || (__GNUC__ < 4) 495# define __attribute__(x) 496#endif 497#if defined(__linux__) || defined(__MINT__) 498# define _GNU_SOURCE /* memmem, memrchr, setresuid... */ 499# define _DEFAULT_SOURCE /* le32toh, crypt, ... */ 500#endif 501#if defined(__NetBSD__) 502# define _OPENBSD_SOURCE /* reallocarray, etc. */ 503#endif 504#if defined(__sun) 505# ifndef _XOPEN_SOURCE /* SunOS already defines */ 506# define _XOPEN_SOURCE /* XPGx */ 507# endif 508# define _XOPEN_SOURCE_EXTENDED 1 /* XPG4v2 */ 509# ifndef __EXTENSIONS__ /* SunOS already defines */ 510# define __EXTENSIONS__ /* reallocarray, etc. */ 511# endif 512#endif 513#if !defined(__BEGIN_DECLS) 514# define __BEGIN_DECLS 515#endif 516#if !defined(__END_DECLS) 517# define __END_DECLS 518#endif 519 520__HEREDOC__ 521 522# This is just for size_t, mode_t, and dev_t. 523# Most of these functions, in the real world, pull in <string.h> or 524# someting that pulls in support for size_t. 525# Our function declarations are standalone, so specify them here. 526 527if [ ${HAVE_FTS} -eq 0 -o \ 528 ${HAVE_MD5} -eq 0 -o \ 529 ${HAVE_MEMMEM} -eq 0 -o \ 530 ${HAVE_MEMRCHR} -eq 0 -o \ 531 ${HAVE_MKFIFOAT} -eq 0 -o \ 532 ${HAVE_MKNODAT} -eq 0 -o \ 533 ${HAVE_QSORT_R} -eq 0 -o \ 534 ${HAVE_READPASSPHRASE} -eq 0 -o \ 535 ${HAVE_REALLOCARRAY} -eq 0 -o \ 536 ${HAVE_RECALLOCARRAY} -eq 0 -o \ 537 ${HAVE_SETRESGID} -eq 0 -o \ 538 ${HAVE_SETRESUID} -eq 0 -o \ 539 ${HAVE_SHA2} -eq 0 -o \ 540 ${HAVE_STRLCAT} -eq 0 -o \ 541 ${HAVE_STRLCPY} -eq 0 -o \ 542 ${HAVE_STRNDUP} -eq 0 -o \ 543 ${HAVE_STRNLEN} -eq 0 -o \ 544 ${HAVE_STRNSTR} -eq 0 ] 545then 546 echo "#include <sys/types.h> /* size_t, mode_t, dev_t */ " 547 echo 548fi 549 550if [ ${HAVE_MD5} -eq 0 -o \ 551 ${HAVE_SHA2} -eq 0 ] 552then 553 echo "#include <stdint.h> /* C99 [u]int[nn]_t types */" 554 echo 555fi 556 557if [ ${HAVE_ERR} -eq 0 ] 558then 559 echo "#include <stdarg.h> /* err(3) */" 560 echo 561fi 562 563# Now we handle our HAVE_xxxx values. 564# Most will just be defined as 0 or 1. 565 566if [ ${HAVE_PATH_MAX} -eq 0 ] 567then 568 echo "#define PATH_MAX 4096" 569 echo 570fi 571 572if [ ${HAVE_WAIT_ANY} -eq 0 ] 573then 574 echo "#define WAIT_ANY (-1) /* sys/wait.h */" 575 echo "#define WAIT_MYPGRP 0" 576 echo 577fi 578 579 580if [ ${HAVE_INFTIM} -eq 0 ] 581then 582 echo "#define INFTIM (-1) /* poll.h */" 583 echo 584fi 585 586cat << __HEREDOC__ 587#ifndef nitems 588#define nitems(x) (sizeof((x)) / sizeof((x)[0])) 589#endif 590 591#ifndef __cleanup 592#define __cleanup(x) __attribute__((cleanup(x))) 593#endif 594 595#ifndef __noreturn 596#define __noreturn __attribute__((noreturn)) 597#endif 598 599#ifndef __printflike 600#define __printflike(x, y) __attribute__((__format__(__printf__, x, y))) 601#endif 602 603#ifndef _IsUnused 604#define _IsUnused __attribute__((__unused__)) 605#endif 606 607/* 608 * Results of configuration feature-testing. 609 */ 610#define HAVE_ARC4RANDOM ${HAVE_ARC4RANDOM} 611#define HAVE_B64_NTOP ${HAVE_B64_NTOP} 612#define HAVE_CAPSICUM ${HAVE_CAPSICUM} 613#define HAVE_CRYPT ${HAVE_CRYPT} 614#define HAVE_ENDIAN_H ${HAVE_ENDIAN_H} 615#define HAVE_ERR ${HAVE_ERR} 616#define HAVE_EXECINFO ${HAVE_EXECINFO} 617#define HAVE_EXPLICIT_BZERO ${HAVE_EXPLICIT_BZERO} 618#define HAVE_FTS ${HAVE_FTS} 619#define HAVE_GETEXECNAME ${HAVE_GETEXECNAME} 620#define HAVE_GETPROGNAME ${HAVE_GETPROGNAME} 621#define HAVE_INFTIM ${HAVE_INFTIM} 622#define HAVE_MD5 ${HAVE_MD5} 623#define HAVE_MEMMEM ${HAVE_MEMMEM} 624#define HAVE_MEMRCHR ${HAVE_MEMRCHR} 625#define HAVE_MEMSET_S ${HAVE_MEMSET_S} 626#define HAVE_MKFIFOAT ${HAVE_MKFIFOAT} 627#define HAVE_MKNODAT ${HAVE_MKNODAT} 628#define HAVE_OSBYTEORDER_H ${HAVE_OSBYTEORDER_H} 629#define HAVE_PATH_MAX ${HAVE_PATH_MAX} 630#define HAVE_PLEDGE ${HAVE_PLEDGE} 631#define HAVE_PROGRAM_INVOCATION_SHORT_NAME ${HAVE_PROGRAM_INVOCATION_SHORT_NAME} 632#define HAVE_BSD_QSORT_R ${HAVE_BSD_QSORT_R} 633#define HAVE_GNU_QSORT_R ${HAVE_GNU_QSORT_R} 634#define HAVE_QSORT_R ${HAVE_QSORT_R} 635#define HAVE_READPASSPHRASE ${HAVE_READPASSPHRASE} 636#define HAVE_REALLOCARRAY ${HAVE_REALLOCARRAY} 637#define HAVE_RECALLOCARRAY ${HAVE_RECALLOCARRAY} 638#define HAVE_SANDBOX_INIT ${HAVE_SANDBOX_INIT} 639#define HAVE_SECCOMP_FILTER ${HAVE_SECCOMP_FILTER} 640#define HAVE_SETRESGID ${HAVE_SETRESGID} 641#define HAVE_SETRESUID ${HAVE_SETRESUID} 642#define HAVE_SHA2 ${HAVE_SHA2} 643#define HAVE_SHA2_H ${HAVE_SHA2} 644#define HAVE_SOCK_NONBLOCK ${HAVE_SOCK_NONBLOCK} 645#define HAVE_STRLCAT ${HAVE_STRLCAT} 646#define HAVE_STRLCPY ${HAVE_STRLCPY} 647#define HAVE_STRNDUP ${HAVE_STRNDUP} 648#define HAVE_STRNLEN ${HAVE_STRNLEN} 649#define HAVE_STRNSTR ${HAVE_STRNSTR} 650#define HAVE_STRTONUM ${HAVE_STRTONUM} 651#define HAVE_SYS_BYTEORDER_H ${HAVE_SYS_BYTEORDER_H} 652#define HAVE_SYS_ENDIAN_H ${HAVE_SYS_ENDIAN_H} 653#define HAVE_SYS_MKDEV_H ${HAVE_SYS_MKDEV_H} 654#define HAVE_SYS_QUEUE ${HAVE_SYS_QUEUE} 655#define HAVE_SYS_SYSMACROS_H ${HAVE_SYS_SYSMACROS_H} 656#define HAVE_SYS_TREE ${HAVE_SYS_TREE} 657#define HAVE_SYSTRACE ${HAVE_SYSTRACE} 658#define HAVE_UNVEIL ${HAVE_UNVEIL} 659#define HAVE_WAIT_ANY ${HAVE_WAIT_ANY} 660#define HAVE___PROGNAME ${HAVE___PROGNAME} 661 662__HEREDOC__ 663 664# Compat for libkern/OSByteOrder.h in place of endian.h. 665 666[ ${HAVE_OSBYTEORDER_H} -eq 1 -a \ 667 ${HAVE_ENDIAN_H} -eq 0 -a \ 668 ${HAVE_SYS_BYTEORDER_H} -eq 0 -a \ 669 ${HAVE_SYS_ENDIAN_H} -eq 0 ] \ 670 && cat << __HEREDOC__ 671/* 672 * endian.h compatibility with libkern/OSByteOrder.h. 673 */ 674#define htobe16(x) OSSwapHostToBigInt16(x) 675#define htole16(x) OSSwapHostToLittleInt16(x) 676#define be16toh(x) OSSwapBigToHostInt16(x) 677#define le16toh(x) OSSwapLittleToHostInt16(x) 678#define htobe32(x) OSSwapHostToBigInt32(x) 679#define htole32(x) OSSwapHostToLittleInt32(x) 680#define be32toh(x) OSSwapBigToHostInt32(x) 681#define le32toh(x) OSSwapLittleToHostInt32(x) 682#define htobe64(x) OSSwapHostToBigInt64(x) 683#define htole64(x) OSSwapHostToLittleInt64(x) 684#define be64toh(x) OSSwapBigToHostInt64(x) 685#define le64toh(x) OSSwapLittleToHostInt64(x) 686 687__HEREDOC__ 688 689[ ${HAVE_SYS_BYTEORDER_H} -eq 1 -a \ 690 ${HAVE_ENDIAN_H} -eq 0 -a \ 691 ${HAVE_OSBYTEORDER_H} -eq 0 -a \ 692 ${HAVE_SYS_ENDIAN_H} -eq 0 ] \ 693 && cat << __HEREDOC__ 694/* 695 * endian.h compatibility with sys/byteorder.h. 696 */ 697#define htobe16(x) BE_16(x) 698#define htole16(x) LE_16(x) 699#define be16toh(x) BE_16(x) 700#define le16toh(x) LE_16(x) 701#define htobe32(x) BE_32(x) 702#define htole32(x) LE_32(x) 703#define be32toh(x) BE_32(x) 704#define le32toh(x) LE_32(x) 705#define htobe64(x) BE_64(x) 706#define htole64(x) LE_64(x) 707#define be64toh(x) BE_64(x) 708#define le64toh(x) LE_64(x) 709 710__HEREDOC__ 711 712# Make minor()/major()/makedev() easier to use. 713 714cat << __HEREDOC__ 715/* 716 * Handle the various major()/minor() header files. 717 * Use sys/mkdev.h before sys/sysmacros.h because SunOS 718 * has both, where only the former works properly. 719 */ 720#if HAVE_SYS_MKDEV_H 721# define COMPAT_MAJOR_MINOR_H <sys/mkdev.h> 722#elif HAVE_SYS_SYSMACROS_H 723# define COMPAT_MAJOR_MINOR_H <sys/sysmacros.h> 724#else 725# define COMPAT_MAJOR_MINOR_H <sys/types.h> 726#endif 727 728__HEREDOC__ 729 730# Make endian.h easier by providing a COMPAT_ENDIAN_H. 731 732cat << __HEREDOC__ 733/* 734 * Make it easier to include endian.h forms. 735 */ 736#if HAVE_ENDIAN_H 737# define COMPAT_ENDIAN_H <endian.h> 738#elif HAVE_SYS_ENDIAN_H 739# define COMPAT_ENDIAN_H <sys/endian.h> 740#elif HAVE_OSBYTEORDER_H 741# define COMPAT_ENDIAN_H <libkern/OSByteOrder.h> 742#elif HAVE_SYS_BYTEORDER_H 743# define COMPAT_ENDIAN_H <sys/byteorder.h> 744#else 745# warning No suitable endian.h could be found. 746# warning Please e-mail the maintainers with your OS. 747# define COMPAT_ENDIAN_H <endian.h> 748#endif 749 750__HEREDOC__ 751 752# Now we do our function declarations for missing functions. 753 754[ ${HAVE_ERR} -eq 0 ] && \ 755 cat << __HEREDOC__ 756/* 757 * Compatibility functions for err(3). 758 */ 759extern void err(int, const char *, ...) __attribute__((noreturn)); 760extern void errc(int, int, const char *, ...) __attribute__((noreturn)); 761extern void errx(int, const char *, ...) __attribute__((noreturn)); 762extern void verr(int, const char *, va_list) __attribute__((noreturn)); 763extern void verrc(int, int, const char *, va_list) __attribute__((noreturn)); 764extern void verrx(int, const char *, va_list) __attribute__((noreturn)); 765extern void warn(const char *, ...); 766extern void warnx(const char *, ...); 767extern void warnc(int, const char *, ...); 768extern void vwarn(const char *, va_list); 769extern void vwarnc(int, const char *, va_list); 770extern void vwarnx(const char *, va_list); 771__HEREDOC__ 772 773[ ${HAVE_MD5} -eq 0 ] && \ 774 cat << __HEREDOC__ 775/* 776 * Compatibility for md4(3). 777 */ 778#define MD5_BLOCK_LENGTH 64 779#define MD5_DIGEST_LENGTH 16 780#define MD5_DIGEST_STRING_LENGTH (MD5_DIGEST_LENGTH * 2 + 1) 781 782typedef struct MD5Context { 783 uint32_t state[4]; 784 uint64_t count; 785 uint8_t buffer[MD5_BLOCK_LENGTH]; 786} MD5_CTX; 787 788extern void MD5Init(MD5_CTX *); 789extern void MD5Update(MD5_CTX *, const uint8_t *, size_t); 790extern void MD5Pad(MD5_CTX *); 791extern void MD5Transform(uint32_t [4], const uint8_t [MD5_BLOCK_LENGTH]); 792extern char *MD5End(MD5_CTX *, char *); 793extern void MD5Final(uint8_t [MD5_DIGEST_LENGTH], MD5_CTX *); 794 795__HEREDOC__ 796 797[ ${HAVE_SHA2} -eq 0 ] && \ 798 cat << __HEREDOC__ 799/* 800 * Compatibility for sha2(3). 801 */ 802 803/*** SHA-256/384/512 Various Length Definitions ***********************/ 804#define SHA256_BLOCK_LENGTH 64 805#define SHA256_DIGEST_LENGTH 32 806#define SHA256_DIGEST_STRING_LENGTH (SHA256_DIGEST_LENGTH * 2 + 1) 807#define SHA384_BLOCK_LENGTH 128 808#define SHA384_DIGEST_LENGTH 48 809#define SHA384_DIGEST_STRING_LENGTH (SHA384_DIGEST_LENGTH * 2 + 1) 810#define SHA512_BLOCK_LENGTH 128 811#define SHA512_DIGEST_LENGTH 64 812#define SHA512_DIGEST_STRING_LENGTH (SHA512_DIGEST_LENGTH * 2 + 1) 813#define SHA512_256_BLOCK_LENGTH 128 814#define SHA512_256_DIGEST_LENGTH 32 815#define SHA512_256_DIGEST_STRING_LENGTH (SHA512_256_DIGEST_LENGTH * 2 + 1) 816 817/*** SHA-224/256/384/512 Context Structure *******************************/ 818typedef struct _SHA2_CTX { 819 union { 820 uint32_t st32[8]; 821 uint64_t st64[8]; 822 } state; 823 uint64_t bitcount[2]; 824 uint8_t buffer[SHA512_BLOCK_LENGTH]; 825} SHA2_CTX; 826 827void SHA256Init(SHA2_CTX *); 828void SHA256Transform(uint32_t state[8], const uint8_t [SHA256_BLOCK_LENGTH]); 829void SHA256Update(SHA2_CTX *, const uint8_t *, size_t); 830void SHA256Pad(SHA2_CTX *); 831void SHA256Final(uint8_t [SHA256_DIGEST_LENGTH], SHA2_CTX *); 832char *SHA256End(SHA2_CTX *, char *); 833char *SHA256File(const char *, char *); 834char *SHA256FileChunk(const char *, char *, off_t, off_t); 835char *SHA256Data(const uint8_t *, size_t, char *); 836 837void SHA384Init(SHA2_CTX *); 838void SHA384Transform(uint64_t state[8], const uint8_t [SHA384_BLOCK_LENGTH]); 839void SHA384Update(SHA2_CTX *, const uint8_t *, size_t); 840void SHA384Pad(SHA2_CTX *); 841void SHA384Final(uint8_t [SHA384_DIGEST_LENGTH], SHA2_CTX *); 842char *SHA384End(SHA2_CTX *, char *); 843char *SHA384File(const char *, char *); 844char *SHA384FileChunk(const char *, char *, off_t, off_t); 845char *SHA384Data(const uint8_t *, size_t, char *); 846 847void SHA512Init(SHA2_CTX *); 848void SHA512Transform(uint64_t state[8], const uint8_t [SHA512_BLOCK_LENGTH]); 849void SHA512Update(SHA2_CTX *, const uint8_t *, size_t); 850void SHA512Pad(SHA2_CTX *); 851void SHA512Final(uint8_t [SHA512_DIGEST_LENGTH], SHA2_CTX *); 852char *SHA512End(SHA2_CTX *, char *); 853char *SHA512File(const char *, char *); 854char *SHA512FileChunk(const char *, char *, off_t, off_t); 855char *SHA512Data(const uint8_t *, size_t, char *); 856 857__HEREDOC__ 858 859if [ ${HAVE_SECCOMP_FILTER} -eq 1 ]; then 860 arch=$(uname -m 2>/dev/null || echo unknown) 861 case "$arch" in 862 x86_64) 863 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_X86_64" 864 ;; 865 i*86) 866 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_I386" 867 ;; 868 arm*) 869 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_ARM" 870 ;; 871 aarch64) 872 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_AARCH64" 873 ;; 874 esac 875 echo 876fi 877 878[ ${HAVE_B64_NTOP} -eq 0 ] && \ 879 cat << __HEREDOC__ 880/* 881 * Compatibility for b64_ntop(3). 882 */ 883extern int b64_ntop(unsigned char const *, size_t, char *, size_t); 884extern int b64_pton(char const *, unsigned char *, size_t); 885 886__HEREDOC__ 887 888[ ${HAVE_EXPLICIT_BZERO} -eq 0 ] && \ 889 cat << __HEREDOC__ 890/* 891 * Compatibility for explicit_bzero(3). 892 */ 893extern void explicit_bzero(void *, size_t); 894 895__HEREDOC__ 896 897[ ${HAVE_MEMMEM} -eq 0 ] && \ 898 cat << __HEREDOC__ 899/* 900 * Compatibility for memmem(3). 901 */ 902void *memmem(const void *, size_t, const void *, size_t); 903 904__HEREDOC__ 905 906[ ${HAVE_MEMRCHR} -eq 0 ] && \ 907 cat << __HEREDOC__ 908/* 909 * Compatibility for memrchr(3). 910 */ 911void *memrchr(const void *b, int, size_t); 912 913__HEREDOC__ 914 915[ ${HAVE_GETPROGNAME} -eq 0 ] && \ 916 cat << __HEREDOC__ 917/* 918 * Compatibility for getprogname(3). 919 */ 920extern const char *getprogname(void); 921 922__HEREDOC__ 923 924[ ${HAVE_QSORT_R} -eq 0 ] && \ 925 cat << __HEREDOC__ 926/* 927 * Compatibility for qsort_r(3). 928 */ 929extern void qsort_r(void *, size_t, size_t, void *, int (*compar)(void *, const void *, const void *)); 930 931__HEREDOC__ 932 933[ ${HAVE_READPASSPHRASE} -eq 0 ] && \ 934 cat << __HEREDOC__ 935/* 936 * Macros and function required for readpassphrase(3). 937 */ 938#define RPP_ECHO_OFF 0x00 939#define RPP_ECHO_ON 0x01 940#define RPP_REQUIRE_TTY 0x02 941#define RPP_FORCELOWER 0x04 942#define RPP_FORCEUPPER 0x08 943#define RPP_SEVENBIT 0x10 944#define RPP_STDIN 0x20 945char *readpassphrase(const char *, char *, size_t, int); 946 947__HEREDOC__ 948 949[ ${HAVE_REALLOCARRAY} -eq 0 ] && \ 950 cat << __HEREDOC__ 951/* 952 * Compatibility for reallocarray(3). 953 */ 954extern void *reallocarray(void *, size_t, size_t); 955 956__HEREDOC__ 957 958[ ${HAVE_RECALLOCARRAY} -eq 0 ] && \ 959 cat << __HEREDOC__ 960/* 961 * Compatibility for recallocarray(3). 962 */ 963extern void *recallocarray(void *, size_t, size_t, size_t); 964 965__HEREDOC__ 966 967[ ${HAVE_STRLCAT} -eq 0 ] && \ 968 cat << __HEREDOC__ 969/* 970 * Compatibility for strlcat(3). 971 */ 972extern size_t strlcat(char *, const char *, size_t); 973 974__HEREDOC__ 975 976[ ${HAVE_STRLCPY} -eq 0 ] && \ 977 cat << __HEREDOC__ 978/* 979 * Compatibility for strlcpy(3). 980 */ 981extern size_t strlcpy(char *, const char *, size_t); 982 983__HEREDOC__ 984 985[ ${HAVE_STRNDUP} -eq 0 ] && \ 986 cat << __HEREDOC__ 987/* 988 * Compatibility for strndup(3). 989 */ 990extern char *strndup(const char *, size_t); 991 992__HEREDOC__ 993 994[ ${HAVE_STRNLEN} -eq 0 ] && \ 995 cat << __HEREDOC__ 996/* 997 * Compatibility for strnlen(3). 998 */ 999extern size_t strnlen(const char *, size_t); 1000 1001__HEREDOC__ 1002 1003[ ${HAVE_STRNSTR} -eq 0 ] && \ 1004 cat << __HEREDOC__ 1005/* 1006 * Compatibility for strnstr(3). 1007 */ 1008extern char *strnstr(const char *, const char *, size_t); 1009 1010__HEREDOC__ 1011 1012[ ${HAVE_STRTONUM} -eq 0 ] && \ 1013 cat << __HEREDOC__ 1014/* 1015 * Compatibility for strotnum(3). 1016 */ 1017extern long long strtonum(const char *, long long, long long, const char **); 1018 1019__HEREDOC__ 1020 1021[ ${HAVE_MKFIFOAT} -eq 0 ] && \ 1022 cat << __HEREDOC__ 1023/* 1024 * Compatibility for mkfifoat(2). 1025 */ 1026int mkfifoat(int, const char *, mode_t); 1027 1028__HEREDOC__ 1029 1030[ ${HAVE_MKNODAT} -eq 0 ] && \ 1031 cat << __HEREDOC__ 1032/* 1033 * Compatibility for mknodat(2). 1034 */ 1035int mknodat(int, const char *, mode_t, dev_t); 1036 1037__HEREDOC__ 1038 1039[ ${HAVE_SETRESGID} -eq 0 ] && \ 1040 cat << __HEREDOC__ 1041/* 1042 * Compatibility for setresgid(2). 1043 */ 1044int setresgid(gid_t rgid, gid_t egid, gid_t sgid); 1045 1046__HEREDOC__ 1047 1048[ ${HAVE_SETRESUID} -eq 0 ] && \ 1049 cat << __HEREDOC__ 1050/* 1051 * Compatibility for setresuid(2). 1052 */ 1053int setresuid(uid_t ruid, uid_t euid, uid_t suid); 1054 1055__HEREDOC__ 1056 1057if [ ${HAVE_SYS_QUEUE} -eq 0 ]; then 1058 cat << __HEREDOC__ 1059/* 1060 * A compatible version of OpenBSD <sys/queue.h>. 1061 */ 1062/* 1063 * Copyright (c) 1991, 1993 1064 * The Regents of the University of California. All rights reserved. 1065 * 1066 * Redistribution and use in source and binary forms, with or without 1067 * modification, are permitted provided that the following conditions 1068 * are met: 1069 * 1. Redistributions of source code must retain the above copyright 1070 * notice, this list of conditions and the following disclaimer. 1071 * 2. Redistributions in binary form must reproduce the above copyright 1072 * notice, this list of conditions and the following disclaimer in the 1073 * documentation and/or other materials provided with the distribution. 1074 * 3. Neither the name of the University nor the names of its contributors 1075 * may be used to endorse or promote products derived from this software 1076 * without specific prior written permission. 1077 * 1078 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND 1079 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1080 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1081 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 1082 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1083 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 1084 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 1085 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 1086 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 1087 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 1088 * SUCH DAMAGE. 1089 * 1090 * @(#)queue.h 8.5 (Berkeley) 8/20/94 1091 */ 1092 1093/* OPENBSD ORIGINAL: sys/sys/queue.h */ 1094 1095/* 1096 * Require for OS/X and other platforms that have old/broken/incomplete 1097 * <sys/queue.h>. 1098 */ 1099 1100#undef LIST_EMPTY 1101#undef LIST_END 1102#undef LIST_ENTRY 1103#undef LIST_FIRST 1104#undef LIST_FOREACH 1105#undef LIST_FOREACH_SAFE 1106#undef LIST_HEAD 1107#undef LIST_HEAD_INITIALIZER 1108#undef LIST_INIT 1109#undef LIST_INSERT_AFTER 1110#undef LIST_INSERT_BEFORE 1111#undef LIST_INSERT_HEAD 1112#undef LIST_NEXT 1113#undef LIST_REMOVE 1114#undef LIST_REPLACE 1115#undef SIMPLEQ_CONCAT 1116#undef SIMPLEQ_EMPTY 1117#undef SIMPLEQ_END 1118#undef SIMPLEQ_ENTRY 1119#undef SIMPLEQ_FIRST 1120#undef SIMPLEQ_FOREACH 1121#undef SIMPLEQ_FOREACH_SAFE 1122#undef SIMPLEQ_HEAD 1123#undef SIMPLEQ_HEAD_INITIALIZER 1124#undef SIMPLEQ_INIT 1125#undef SIMPLEQ_INSERT_AFTER 1126#undef SIMPLEQ_INSERT_HEAD 1127#undef SIMPLEQ_INSERT_TAIL 1128#undef SIMPLEQ_NEXT 1129#undef SIMPLEQ_REMOVE_AFTER 1130#undef SIMPLEQ_REMOVE_HEAD 1131#undef SLIST_EMPTY 1132#undef SLIST_END 1133#undef SLIST_ENTRY 1134#undef SLIST_FIRST 1135#undef SLIST_FOREACH 1136#undef SLIST_FOREACH_SAFE 1137#undef SLIST_HEAD 1138#undef SLIST_HEAD_INITIALIZER 1139#undef SLIST_INIT 1140#undef SLIST_INSERT_AFTER 1141#undef SLIST_INSERT_HEAD 1142#undef SLIST_NEXT 1143#undef SLIST_REMOVE 1144#undef SLIST_REMOVE_AFTER 1145#undef SLIST_REMOVE_HEAD 1146#undef TAILQ_CONCAT 1147#undef TAILQ_EMPTY 1148#undef TAILQ_END 1149#undef TAILQ_ENTRY 1150#undef TAILQ_FIRST 1151#undef TAILQ_FOREACH 1152#undef TAILQ_FOREACH_REVERSE 1153#undef TAILQ_FOREACH_REVERSE_SAFE 1154#undef TAILQ_FOREACH_SAFE 1155#undef TAILQ_HEAD 1156#undef TAILQ_HEAD_INITIALIZER 1157#undef TAILQ_INIT 1158#undef TAILQ_INSERT_AFTER 1159#undef TAILQ_INSERT_BEFORE 1160#undef TAILQ_INSERT_HEAD 1161#undef TAILQ_INSERT_TAIL 1162#undef TAILQ_LAST 1163#undef TAILQ_NEXT 1164#undef TAILQ_PREV 1165#undef TAILQ_REMOVE 1166#undef TAILQ_REPLACE 1167#undef XSIMPLEQ_EMPTY 1168#undef XSIMPLEQ_END 1169#undef XSIMPLEQ_ENTRY 1170#undef XSIMPLEQ_FIRST 1171#undef XSIMPLEQ_FOREACH 1172#undef XSIMPLEQ_FOREACH_SAFE 1173#undef XSIMPLEQ_HEAD 1174#undef XSIMPLEQ_INIT 1175#undef XSIMPLEQ_INSERT_AFTER 1176#undef XSIMPLEQ_INSERT_HEAD 1177#undef XSIMPLEQ_INSERT_TAIL 1178#undef XSIMPLEQ_NEXT 1179#undef XSIMPLEQ_REMOVE_AFTER 1180#undef XSIMPLEQ_REMOVE_HEAD 1181#undef XSIMPLEQ_XOR 1182 1183/* 1184 * This file defines five types of data structures: singly-linked lists, 1185 * lists, simple queues, tail queues and XOR simple queues. 1186 * 1187 * 1188 * A singly-linked list is headed by a single forward pointer. The elements 1189 * are singly linked for minimum space and pointer manipulation overhead at 1190 * the expense of O(n) removal for arbitrary elements. New elements can be 1191 * added to the list after an existing element or at the head of the list. 1192 * Elements being removed from the head of the list should use the explicit 1193 * macro for this purpose for optimum efficiency. A singly-linked list may 1194 * only be traversed in the forward direction. Singly-linked lists are ideal 1195 * for applications with large datasets and few or no removals or for 1196 * implementing a LIFO queue. 1197 * 1198 * A list is headed by a single forward pointer (or an array of forward 1199 * pointers for a hash table header). The elements are doubly linked 1200 * so that an arbitrary element can be removed without a need to 1201 * traverse the list. New elements can be added to the list before 1202 * or after an existing element or at the head of the list. A list 1203 * may only be traversed in the forward direction. 1204 * 1205 * A simple queue is headed by a pair of pointers, one to the head of the 1206 * list and the other to the tail of the list. The elements are singly 1207 * linked to save space, so elements can only be removed from the 1208 * head of the list. New elements can be added to the list before or after 1209 * an existing element, at the head of the list, or at the end of the 1210 * list. A simple queue may only be traversed in the forward direction. 1211 * 1212 * A tail queue is headed by a pair of pointers, one to the head of the 1213 * list and the other to the tail of the list. The elements are doubly 1214 * linked so that an arbitrary element can be removed without a need to 1215 * traverse the list. New elements can be added to the list before or 1216 * after an existing element, at the head of the list, or at the end of 1217 * the list. A tail queue may be traversed in either direction. 1218 * 1219 * An XOR simple queue is used in the same way as a regular simple queue. 1220 * The difference is that the head structure also includes a "cookie" that 1221 * is XOR'd with the queue pointer (first, last or next) to generate the 1222 * real pointer value. 1223 * 1224 * For details on the use of these macros, see the queue(3) manual page. 1225 */ 1226 1227#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) 1228#define _Q_INVALID ((void *)-1) 1229#define _Q_INVALIDATE(a) (a) = _Q_INVALID 1230#else 1231#define _Q_INVALIDATE(a) 1232#endif 1233 1234/* 1235 * Singly-linked List definitions. 1236 */ 1237#define SLIST_HEAD(name, type) \\ 1238struct name { \\ 1239 struct type *slh_first; /* first element */ \\ 1240} 1241 1242#define SLIST_HEAD_INITIALIZER(head) \\ 1243 { NULL } 1244 1245#define SLIST_ENTRY(type) \\ 1246struct { \\ 1247 struct type *sle_next; /* next element */ \\ 1248} 1249 1250/* 1251 * Singly-linked List access methods. 1252 */ 1253#define SLIST_FIRST(head) ((head)->slh_first) 1254#define SLIST_END(head) NULL 1255#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) 1256#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 1257 1258#define SLIST_FOREACH(var, head, field) \\ 1259 for((var) = SLIST_FIRST(head); \\ 1260 (var) != SLIST_END(head); \\ 1261 (var) = SLIST_NEXT(var, field)) 1262 1263#define SLIST_FOREACH_SAFE(var, head, field, tvar) \\ 1264 for ((var) = SLIST_FIRST(head); \\ 1265 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \\ 1266 (var) = (tvar)) 1267 1268/* 1269 * Singly-linked List functions. 1270 */ 1271#define SLIST_INIT(head) { \\ 1272 SLIST_FIRST(head) = SLIST_END(head); \\ 1273} 1274 1275#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \\ 1276 (elm)->field.sle_next = (slistelm)->field.sle_next; \\ 1277 (slistelm)->field.sle_next = (elm); \\ 1278} while (0) 1279 1280#define SLIST_INSERT_HEAD(head, elm, field) do { \\ 1281 (elm)->field.sle_next = (head)->slh_first; \\ 1282 (head)->slh_first = (elm); \\ 1283} while (0) 1284 1285#define SLIST_REMOVE_AFTER(elm, field) do { \\ 1286 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \\ 1287} while (0) 1288 1289#define SLIST_REMOVE_HEAD(head, field) do { \\ 1290 (head)->slh_first = (head)->slh_first->field.sle_next; \\ 1291} while (0) 1292 1293#define SLIST_REMOVE(head, elm, type, field) do { \\ 1294 if ((head)->slh_first == (elm)) { \\ 1295 SLIST_REMOVE_HEAD((head), field); \\ 1296 } else { \\ 1297 struct type *curelm = (head)->slh_first; \\ 1298 \\ 1299 while (curelm->field.sle_next != (elm)) \\ 1300 curelm = curelm->field.sle_next; \\ 1301 curelm->field.sle_next = \\ 1302 curelm->field.sle_next->field.sle_next; \\ 1303 } \\ 1304 _Q_INVALIDATE((elm)->field.sle_next); \\ 1305} while (0) 1306 1307/* 1308 * List definitions. 1309 */ 1310#define LIST_HEAD(name, type) \\ 1311struct name { \\ 1312 struct type *lh_first; /* first element */ \\ 1313} 1314 1315#define LIST_HEAD_INITIALIZER(head) \\ 1316 { NULL } 1317 1318#define LIST_ENTRY(type) \\ 1319struct { \\ 1320 struct type *le_next; /* next element */ \\ 1321 struct type **le_prev; /* address of previous next element */ \\ 1322} 1323 1324/* 1325 * List access methods. 1326 */ 1327#define LIST_FIRST(head) ((head)->lh_first) 1328#define LIST_END(head) NULL 1329#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) 1330#define LIST_NEXT(elm, field) ((elm)->field.le_next) 1331 1332#define LIST_FOREACH(var, head, field) \\ 1333 for((var) = LIST_FIRST(head); \\ 1334 (var)!= LIST_END(head); \\ 1335 (var) = LIST_NEXT(var, field)) 1336 1337#define LIST_FOREACH_SAFE(var, head, field, tvar) \\ 1338 for ((var) = LIST_FIRST(head); \\ 1339 (var) && ((tvar) = LIST_NEXT(var, field), 1); \\ 1340 (var) = (tvar)) 1341 1342/* 1343 * List functions. 1344 */ 1345#define LIST_INIT(head) do { \\ 1346 LIST_FIRST(head) = LIST_END(head); \\ 1347} while (0) 1348 1349#define LIST_INSERT_AFTER(listelm, elm, field) do { \\ 1350 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \\ 1351 (listelm)->field.le_next->field.le_prev = \\ 1352 &(elm)->field.le_next; \\ 1353 (listelm)->field.le_next = (elm); \\ 1354 (elm)->field.le_prev = &(listelm)->field.le_next; \\ 1355} while (0) 1356 1357#define LIST_INSERT_BEFORE(listelm, elm, field) do { \\ 1358 (elm)->field.le_prev = (listelm)->field.le_prev; \\ 1359 (elm)->field.le_next = (listelm); \\ 1360 *(listelm)->field.le_prev = (elm); \\ 1361 (listelm)->field.le_prev = &(elm)->field.le_next; \\ 1362} while (0) 1363 1364#define LIST_INSERT_HEAD(head, elm, field) do { \\ 1365 if (((elm)->field.le_next = (head)->lh_first) != NULL) \\ 1366 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\\ 1367 (head)->lh_first = (elm); \\ 1368 (elm)->field.le_prev = &(head)->lh_first; \\ 1369} while (0) 1370 1371#define LIST_REMOVE(elm, field) do { \\ 1372 if ((elm)->field.le_next != NULL) \\ 1373 (elm)->field.le_next->field.le_prev = \\ 1374 (elm)->field.le_prev; \\ 1375 *(elm)->field.le_prev = (elm)->field.le_next; \\ 1376 _Q_INVALIDATE((elm)->field.le_prev); \\ 1377 _Q_INVALIDATE((elm)->field.le_next); \\ 1378} while (0) 1379 1380#define LIST_REPLACE(elm, elm2, field) do { \\ 1381 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \\ 1382 (elm2)->field.le_next->field.le_prev = \\ 1383 &(elm2)->field.le_next; \\ 1384 (elm2)->field.le_prev = (elm)->field.le_prev; \\ 1385 *(elm2)->field.le_prev = (elm2); \\ 1386 _Q_INVALIDATE((elm)->field.le_prev); \\ 1387 _Q_INVALIDATE((elm)->field.le_next); \\ 1388} while (0) 1389 1390/* 1391 * Simple queue definitions. 1392 */ 1393#define SIMPLEQ_HEAD(name, type) \\ 1394struct name { \\ 1395 struct type *sqh_first; /* first element */ \\ 1396 struct type **sqh_last; /* addr of last next element */ \\ 1397} 1398 1399#define SIMPLEQ_HEAD_INITIALIZER(head) \\ 1400 { NULL, &(head).sqh_first } 1401 1402#define SIMPLEQ_ENTRY(type) \\ 1403struct { \\ 1404 struct type *sqe_next; /* next element */ \\ 1405} 1406 1407/* 1408 * Simple queue access methods. 1409 */ 1410#define SIMPLEQ_FIRST(head) ((head)->sqh_first) 1411#define SIMPLEQ_END(head) NULL 1412#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) 1413#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 1414 1415#define SIMPLEQ_FOREACH(var, head, field) \\ 1416 for((var) = SIMPLEQ_FIRST(head); \\ 1417 (var) != SIMPLEQ_END(head); \\ 1418 (var) = SIMPLEQ_NEXT(var, field)) 1419 1420#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \\ 1421 for ((var) = SIMPLEQ_FIRST(head); \\ 1422 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \\ 1423 (var) = (tvar)) 1424 1425/* 1426 * Simple queue functions. 1427 */ 1428#define SIMPLEQ_INIT(head) do { \\ 1429 (head)->sqh_first = NULL; \\ 1430 (head)->sqh_last = &(head)->sqh_first; \\ 1431} while (0) 1432 1433#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \\ 1434 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \\ 1435 (head)->sqh_last = &(elm)->field.sqe_next; \\ 1436 (head)->sqh_first = (elm); \\ 1437} while (0) 1438 1439#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \\ 1440 (elm)->field.sqe_next = NULL; \\ 1441 *(head)->sqh_last = (elm); \\ 1442 (head)->sqh_last = &(elm)->field.sqe_next; \\ 1443} while (0) 1444 1445#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\ 1446 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\\ 1447 (head)->sqh_last = &(elm)->field.sqe_next; \\ 1448 (listelm)->field.sqe_next = (elm); \\ 1449} while (0) 1450 1451#define SIMPLEQ_REMOVE_HEAD(head, field) do { \\ 1452 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \\ 1453 (head)->sqh_last = &(head)->sqh_first; \\ 1454} while (0) 1455 1456#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \\ 1457 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \\ 1458 == NULL) \\ 1459 (head)->sqh_last = &(elm)->field.sqe_next; \\ 1460} while (0) 1461 1462#define SIMPLEQ_CONCAT(head1, head2) do { \\ 1463 if (!SIMPLEQ_EMPTY((head2))) { \\ 1464 *(head1)->sqh_last = (head2)->sqh_first; \\ 1465 (head1)->sqh_last = (head2)->sqh_last; \\ 1466 SIMPLEQ_INIT((head2)); \\ 1467 } \\ 1468} while (0) 1469 1470/* 1471 * XOR Simple queue definitions. 1472 */ 1473#define XSIMPLEQ_HEAD(name, type) \\ 1474struct name { \\ 1475 struct type *sqx_first; /* first element */ \\ 1476 struct type **sqx_last; /* addr of last next element */ \\ 1477 unsigned long sqx_cookie; \\ 1478} 1479 1480#define XSIMPLEQ_ENTRY(type) \\ 1481struct { \\ 1482 struct type *sqx_next; /* next element */ \\ 1483} 1484 1485/* 1486 * XOR Simple queue access methods. 1487 */ 1488#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \\ 1489 (unsigned long)(ptr))) 1490#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first)) 1491#define XSIMPLEQ_END(head) NULL 1492#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head)) 1493#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next)) 1494 1495 1496#define XSIMPLEQ_FOREACH(var, head, field) \\ 1497 for ((var) = XSIMPLEQ_FIRST(head); \\ 1498 (var) != XSIMPLEQ_END(head); \\ 1499 (var) = XSIMPLEQ_NEXT(head, var, field)) 1500 1501#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \\ 1502 for ((var) = XSIMPLEQ_FIRST(head); \\ 1503 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \\ 1504 (var) = (tvar)) 1505 1506/* 1507 * XOR Simple queue functions. 1508 */ 1509#define XSIMPLEQ_INIT(head) do { \\ 1510 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \\ 1511 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \\ 1512 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \\ 1513} while (0) 1514 1515#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \\ 1516 if (((elm)->field.sqx_next = (head)->sqx_first) == \\ 1517 XSIMPLEQ_XOR(head, NULL)) \\ 1518 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \\ 1519 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \\ 1520} while (0) 1521 1522#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \\ 1523 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \\ 1524 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \\ 1525 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \\ 1526} while (0) 1527 1528#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\ 1529 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \\ 1530 XSIMPLEQ_XOR(head, NULL)) \\ 1531 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \\ 1532 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \\ 1533} while (0) 1534 1535#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \\ 1536 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \\ 1537 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \\ 1538 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \\ 1539} while (0) 1540 1541#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \\ 1542 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \\ 1543 (elm)->field.sqx_next)->field.sqx_next) \\ 1544 == XSIMPLEQ_XOR(head, NULL)) \\ 1545 (head)->sqx_last = \\ 1546 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \\ 1547} while (0) 1548 1549 1550/* 1551 * Tail queue definitions. 1552 */ 1553#define TAILQ_HEAD(name, type) \\ 1554struct name { \\ 1555 struct type *tqh_first; /* first element */ \\ 1556 struct type **tqh_last; /* addr of last next element */ \\ 1557} 1558 1559#define TAILQ_HEAD_INITIALIZER(head) \\ 1560 { NULL, &(head).tqh_first } 1561 1562#define TAILQ_ENTRY(type) \\ 1563struct { \\ 1564 struct type *tqe_next; /* next element */ \\ 1565 struct type **tqe_prev; /* address of previous next element */ \\ 1566} 1567 1568/* 1569 * Tail queue access methods. 1570 */ 1571#define TAILQ_FIRST(head) ((head)->tqh_first) 1572#define TAILQ_END(head) NULL 1573#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 1574#define TAILQ_LAST(head, headname) \\ 1575 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 1576/* XXX */ 1577#define TAILQ_PREV(elm, headname, field) \\ 1578 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 1579#define TAILQ_EMPTY(head) \\ 1580 (TAILQ_FIRST(head) == TAILQ_END(head)) 1581 1582#define TAILQ_FOREACH(var, head, field) \\ 1583 for((var) = TAILQ_FIRST(head); \\ 1584 (var) != TAILQ_END(head); \\ 1585 (var) = TAILQ_NEXT(var, field)) 1586 1587#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \\ 1588 for ((var) = TAILQ_FIRST(head); \\ 1589 (var) != TAILQ_END(head) && \\ 1590 ((tvar) = TAILQ_NEXT(var, field), 1); \\ 1591 (var) = (tvar)) 1592 1593 1594#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \\ 1595 for((var) = TAILQ_LAST(head, headname); \\ 1596 (var) != TAILQ_END(head); \\ 1597 (var) = TAILQ_PREV(var, headname, field)) 1598 1599#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \\ 1600 for ((var) = TAILQ_LAST(head, headname); \\ 1601 (var) != TAILQ_END(head) && \\ 1602 ((tvar) = TAILQ_PREV(var, headname, field), 1); \\ 1603 (var) = (tvar)) 1604 1605/* 1606 * Tail queue functions. 1607 */ 1608#define TAILQ_INIT(head) do { \\ 1609 (head)->tqh_first = NULL; \\ 1610 (head)->tqh_last = &(head)->tqh_first; \\ 1611} while (0) 1612 1613#define TAILQ_INSERT_HEAD(head, elm, field) do { \\ 1614 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \\ 1615 (head)->tqh_first->field.tqe_prev = \\ 1616 &(elm)->field.tqe_next; \\ 1617 else \\ 1618 (head)->tqh_last = &(elm)->field.tqe_next; \\ 1619 (head)->tqh_first = (elm); \\ 1620 (elm)->field.tqe_prev = &(head)->tqh_first; \\ 1621} while (0) 1622 1623#define TAILQ_INSERT_TAIL(head, elm, field) do { \\ 1624 (elm)->field.tqe_next = NULL; \\ 1625 (elm)->field.tqe_prev = (head)->tqh_last; \\ 1626 *(head)->tqh_last = (elm); \\ 1627 (head)->tqh_last = &(elm)->field.tqe_next; \\ 1628} while (0) 1629 1630#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \\ 1631 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\\ 1632 (elm)->field.tqe_next->field.tqe_prev = \\ 1633 &(elm)->field.tqe_next; \\ 1634 else \\ 1635 (head)->tqh_last = &(elm)->field.tqe_next; \\ 1636 (listelm)->field.tqe_next = (elm); \\ 1637 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \\ 1638} while (0) 1639 1640#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \\ 1641 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \\ 1642 (elm)->field.tqe_next = (listelm); \\ 1643 *(listelm)->field.tqe_prev = (elm); \\ 1644 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \\ 1645} while (0) 1646 1647#define TAILQ_REMOVE(head, elm, field) do { \\ 1648 if (((elm)->field.tqe_next) != NULL) \\ 1649 (elm)->field.tqe_next->field.tqe_prev = \\ 1650 (elm)->field.tqe_prev; \\ 1651 else \\ 1652 (head)->tqh_last = (elm)->field.tqe_prev; \\ 1653 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \\ 1654 _Q_INVALIDATE((elm)->field.tqe_prev); \\ 1655 _Q_INVALIDATE((elm)->field.tqe_next); \\ 1656} while (0) 1657 1658#define TAILQ_REPLACE(head, elm, elm2, field) do { \\ 1659 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \\ 1660 (elm2)->field.tqe_next->field.tqe_prev = \\ 1661 &(elm2)->field.tqe_next; \\ 1662 else \\ 1663 (head)->tqh_last = &(elm2)->field.tqe_next; \\ 1664 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \\ 1665 *(elm2)->field.tqe_prev = (elm2); \\ 1666 _Q_INVALIDATE((elm)->field.tqe_prev); \\ 1667 _Q_INVALIDATE((elm)->field.tqe_next); \\ 1668} while (0) 1669 1670#define TAILQ_CONCAT(head1, head2, field) do { \\ 1671 if (!TAILQ_EMPTY(head2)) { \\ 1672 *(head1)->tqh_last = (head2)->tqh_first; \\ 1673 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \\ 1674 (head1)->tqh_last = (head2)->tqh_last; \\ 1675 TAILQ_INIT((head2)); \\ 1676 } \\ 1677} while (0) 1678 1679__HEREDOC__ 1680fi 1681 1682if [ ${HAVE_SYS_TREE} -eq 0 ]; then 1683 cat << __HEREDOC__ 1684/* 1685 * A compatible version of OpenBSD <sys/tree.h>. 1686 */ 1687/* 1688 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 1689 * All rights reserved. 1690 * 1691 * Redistribution and use in source and binary forms, with or without 1692 * modification, are permitted provided that the following conditions 1693 * are met: 1694 * 1. Redistributions of source code must retain the above copyright 1695 * notice, this list of conditions and the following disclaimer. 1696 * 2. Redistributions in binary form must reproduce the above copyright 1697 * notice, this list of conditions and the following disclaimer in the 1698 * documentation and/or other materials provided with the distribution. 1699 * 1700 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR 1701 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1702 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1703 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1704 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 1705 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1706 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1707 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1708 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 1709 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1710 */ 1711 1712/* OPENBSD ORIGINAL: sys/sys/tree.h */ 1713 1714/* 1715 * This file defines data structures for different types of trees: 1716 * splay trees and red-black trees. 1717 * 1718 * A splay tree is a self-organizing data structure. Every operation 1719 * on the tree causes a splay to happen. The splay moves the requested 1720 * node to the root of the tree and partly rebalances it. 1721 * 1722 * This has the benefit that request locality causes faster lookups as 1723 * the requested nodes move to the top of the tree. On the other hand, 1724 * every lookup causes memory writes. 1725 * 1726 * The Balance Theorem bounds the total access time for m operations 1727 * and n inserts on an initially empty tree as O((m + n)lg n). The 1728 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 1729 * 1730 * A red-black tree is a binary search tree with the node color as an 1731 * extra attribute. It fulfills a set of conditions: 1732 * - every search path from the root to a leaf consists of the 1733 * same number of black nodes, 1734 * - each red node (except for the root) has a black parent, 1735 * - each leaf node is black. 1736 * 1737 * Every operation on a red-black tree is bounded as O(lg n). 1738 * The maximum height of a red-black tree is 2lg (n+1). 1739 */ 1740 1741#define SPLAY_HEAD(name, type) \\ 1742struct name { \\ 1743 struct type *sph_root; /* root of the tree */ \\ 1744} 1745 1746#define SPLAY_INITIALIZER(root) \\ 1747 { NULL } 1748 1749#define SPLAY_INIT(root) do { \\ 1750 (root)->sph_root = NULL; \\ 1751} while (0) 1752 1753#define SPLAY_ENTRY(type) \\ 1754struct { \\ 1755 struct type *spe_left; /* left element */ \\ 1756 struct type *spe_right; /* right element */ \\ 1757} 1758 1759#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 1760#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 1761#define SPLAY_ROOT(head) (head)->sph_root 1762#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 1763 1764/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 1765#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \\ 1766 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \\ 1767 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \\ 1768 (head)->sph_root = tmp; \\ 1769} while (0) 1770 1771#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \\ 1772 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \\ 1773 SPLAY_LEFT(tmp, field) = (head)->sph_root; \\ 1774 (head)->sph_root = tmp; \\ 1775} while (0) 1776 1777#define SPLAY_LINKLEFT(head, tmp, field) do { \\ 1778 SPLAY_LEFT(tmp, field) = (head)->sph_root; \\ 1779 tmp = (head)->sph_root; \\ 1780 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \\ 1781} while (0) 1782 1783#define SPLAY_LINKRIGHT(head, tmp, field) do { \\ 1784 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \\ 1785 tmp = (head)->sph_root; \\ 1786 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \\ 1787} while (0) 1788 1789#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \\ 1790 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \\ 1791 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\\ 1792 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \\ 1793 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \\ 1794} while (0) 1795 1796/* Generates prototypes and inline functions */ 1797 1798#define SPLAY_PROTOTYPE(name, type, field, cmp) \\ 1799void name##_SPLAY(struct name *, struct type *); \\ 1800void name##_SPLAY_MINMAX(struct name *, int); \\ 1801struct type *name##_SPLAY_INSERT(struct name *, struct type *); \\ 1802struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \\ 1803 \\ 1804/* Finds the node with the same key as elm */ \\ 1805static __inline struct type * \\ 1806name##_SPLAY_FIND(struct name *head, struct type *elm) \\ 1807{ \\ 1808 if (SPLAY_EMPTY(head)) \\ 1809 return(NULL); \\ 1810 name##_SPLAY(head, elm); \\ 1811 if ((cmp)(elm, (head)->sph_root) == 0) \\ 1812 return (head->sph_root); \\ 1813 return (NULL); \\ 1814} \\ 1815 \\ 1816static __inline struct type * \\ 1817name##_SPLAY_NEXT(struct name *head, struct type *elm) \\ 1818{ \\ 1819 name##_SPLAY(head, elm); \\ 1820 if (SPLAY_RIGHT(elm, field) != NULL) { \\ 1821 elm = SPLAY_RIGHT(elm, field); \\ 1822 while (SPLAY_LEFT(elm, field) != NULL) { \\ 1823 elm = SPLAY_LEFT(elm, field); \\ 1824 } \\ 1825 } else \\ 1826 elm = NULL; \\ 1827 return (elm); \\ 1828} \\ 1829 \\ 1830static __inline struct type * \\ 1831name##_SPLAY_MIN_MAX(struct name *head, int val) \\ 1832{ \\ 1833 name##_SPLAY_MINMAX(head, val); \\ 1834 return (SPLAY_ROOT(head)); \\ 1835} 1836 1837/* Main splay operation. 1838 * Moves node close to the key of elm to top 1839 */ 1840#define SPLAY_GENERATE(name, type, field, cmp) \\ 1841struct type * \\ 1842name##_SPLAY_INSERT(struct name *head, struct type *elm) \\ 1843{ \\ 1844 if (SPLAY_EMPTY(head)) { \\ 1845 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \\ 1846 } else { \\ 1847 int __comp; \\ 1848 name##_SPLAY(head, elm); \\ 1849 __comp = (cmp)(elm, (head)->sph_root); \\ 1850 if(__comp < 0) { \\ 1851 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\\ 1852 SPLAY_RIGHT(elm, field) = (head)->sph_root; \\ 1853 SPLAY_LEFT((head)->sph_root, field) = NULL; \\ 1854 } else if (__comp > 0) { \\ 1855 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\\ 1856 SPLAY_LEFT(elm, field) = (head)->sph_root; \\ 1857 SPLAY_RIGHT((head)->sph_root, field) = NULL; \\ 1858 } else \\ 1859 return ((head)->sph_root); \\ 1860 } \\ 1861 (head)->sph_root = (elm); \\ 1862 return (NULL); \\ 1863} \\ 1864 \\ 1865struct type * \\ 1866name##_SPLAY_REMOVE(struct name *head, struct type *elm) \\ 1867{ \\ 1868 struct type *__tmp; \\ 1869 if (SPLAY_EMPTY(head)) \\ 1870 return (NULL); \\ 1871 name##_SPLAY(head, elm); \\ 1872 if ((cmp)(elm, (head)->sph_root) == 0) { \\ 1873 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \\ 1874 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\\ 1875 } else { \\ 1876 __tmp = SPLAY_RIGHT((head)->sph_root, field); \\ 1877 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\\ 1878 name##_SPLAY(head, elm); \\ 1879 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \\ 1880 } \\ 1881 return (elm); \\ 1882 } \\ 1883 return (NULL); \\ 1884} \\ 1885 \\ 1886void \\ 1887name##_SPLAY(struct name *head, struct type *elm) \\ 1888{ \\ 1889 struct type __node, *__left, *__right, *__tmp; \\ 1890 int __comp; \\ 1891\\ 1892 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\\ 1893 __left = __right = &__node; \\ 1894\\ 1895 while ((__comp = (cmp)(elm, (head)->sph_root))) { \\ 1896 if (__comp < 0) { \\ 1897 __tmp = SPLAY_LEFT((head)->sph_root, field); \\ 1898 if (__tmp == NULL) \\ 1899 break; \\ 1900 if ((cmp)(elm, __tmp) < 0){ \\ 1901 SPLAY_ROTATE_RIGHT(head, __tmp, field); \\ 1902 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\\ 1903 break; \\ 1904 } \\ 1905 SPLAY_LINKLEFT(head, __right, field); \\ 1906 } else if (__comp > 0) { \\ 1907 __tmp = SPLAY_RIGHT((head)->sph_root, field); \\ 1908 if (__tmp == NULL) \\ 1909 break; \\ 1910 if ((cmp)(elm, __tmp) > 0){ \\ 1911 SPLAY_ROTATE_LEFT(head, __tmp, field); \\ 1912 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\\ 1913 break; \\ 1914 } \\ 1915 SPLAY_LINKRIGHT(head, __left, field); \\ 1916 } \\ 1917 } \\ 1918 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \\ 1919} \\ 1920 \\ 1921/* Splay with either the minimum or the maximum element \\ 1922 * Used to find minimum or maximum element in tree. \\ 1923 */ \\ 1924void name##_SPLAY_MINMAX(struct name *head, int __comp) \\ 1925{ \\ 1926 struct type __node, *__left, *__right, *__tmp; \\ 1927\\ 1928 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\\ 1929 __left = __right = &__node; \\ 1930\\ 1931 while (1) { \\ 1932 if (__comp < 0) { \\ 1933 __tmp = SPLAY_LEFT((head)->sph_root, field); \\ 1934 if (__tmp == NULL) \\ 1935 break; \\ 1936 if (__comp < 0){ \\ 1937 SPLAY_ROTATE_RIGHT(head, __tmp, field); \\ 1938 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\\ 1939 break; \\ 1940 } \\ 1941 SPLAY_LINKLEFT(head, __right, field); \\ 1942 } else if (__comp > 0) { \\ 1943 __tmp = SPLAY_RIGHT((head)->sph_root, field); \\ 1944 if (__tmp == NULL) \\ 1945 break; \\ 1946 if (__comp > 0) { \\ 1947 SPLAY_ROTATE_LEFT(head, __tmp, field); \\ 1948 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\\ 1949 break; \\ 1950 } \\ 1951 SPLAY_LINKRIGHT(head, __left, field); \\ 1952 } \\ 1953 } \\ 1954 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \\ 1955} 1956 1957#define SPLAY_NEGINF -1 1958#define SPLAY_INF 1 1959 1960#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 1961#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 1962#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 1963#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 1964#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \\ 1965 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 1966#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \\ 1967 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 1968 1969#define SPLAY_FOREACH(x, name, head) \\ 1970 for ((x) = SPLAY_MIN(name, head); \\ 1971 (x) != NULL; \\ 1972 (x) = SPLAY_NEXT(name, head, x)) 1973 1974/* Macros that define a red-black tree */ 1975#define RB_HEAD(name, type) \\ 1976struct name { \\ 1977 struct type *rbh_root; /* root of the tree */ \\ 1978} 1979 1980#define RB_INITIALIZER(root) \\ 1981 { NULL } 1982 1983#define RB_INIT(root) do { \\ 1984 (root)->rbh_root = NULL; \\ 1985} while (0) 1986 1987#define RB_BLACK 0 1988#define RB_RED 1 1989#define RB_ENTRY(type) \\ 1990struct { \\ 1991 struct type *rbe_left; /* left element */ \\ 1992 struct type *rbe_right; /* right element */ \\ 1993 struct type *rbe_parent; /* parent element */ \\ 1994 int rbe_color; /* node color */ \\ 1995} 1996 1997#define RB_LEFT(elm, field) (elm)->field.rbe_left 1998#define RB_RIGHT(elm, field) (elm)->field.rbe_right 1999#define RB_PARENT(elm, field) (elm)->field.rbe_parent 2000#define RB_COLOR(elm, field) (elm)->field.rbe_color 2001#define RB_ROOT(head) (head)->rbh_root 2002#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 2003 2004#define RB_SET(elm, parent, field) do { \\ 2005 RB_PARENT(elm, field) = parent; \\ 2006 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \\ 2007 RB_COLOR(elm, field) = RB_RED; \\ 2008} while (0) 2009 2010#define RB_SET_BLACKRED(black, red, field) do { \\ 2011 RB_COLOR(black, field) = RB_BLACK; \\ 2012 RB_COLOR(red, field) = RB_RED; \\ 2013} while (0) 2014 2015#ifndef RB_AUGMENT 2016#define RB_AUGMENT(x) do {} while (0) 2017#endif 2018 2019#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \\ 2020 (tmp) = RB_RIGHT(elm, field); \\ 2021 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \\ 2022 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \\ 2023 } \\ 2024 RB_AUGMENT(elm); \\ 2025 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \\ 2026 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \\ 2027 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \\ 2028 else \\ 2029 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \\ 2030 } else \\ 2031 (head)->rbh_root = (tmp); \\ 2032 RB_LEFT(tmp, field) = (elm); \\ 2033 RB_PARENT(elm, field) = (tmp); \\ 2034 RB_AUGMENT(tmp); \\ 2035 if ((RB_PARENT(tmp, field))) \\ 2036 RB_AUGMENT(RB_PARENT(tmp, field)); \\ 2037} while (0) 2038 2039#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \\ 2040 (tmp) = RB_LEFT(elm, field); \\ 2041 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \\ 2042 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \\ 2043 } \\ 2044 RB_AUGMENT(elm); \\ 2045 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \\ 2046 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \\ 2047 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \\ 2048 else \\ 2049 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \\ 2050 } else \\ 2051 (head)->rbh_root = (tmp); \\ 2052 RB_RIGHT(tmp, field) = (elm); \\ 2053 RB_PARENT(elm, field) = (tmp); \\ 2054 RB_AUGMENT(tmp); \\ 2055 if ((RB_PARENT(tmp, field))) \\ 2056 RB_AUGMENT(RB_PARENT(tmp, field)); \\ 2057} while (0) 2058 2059/* Generates prototypes and inline functions */ 2060#define RB_PROTOTYPE(name, type, field, cmp) \\ 2061 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 2062#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \\ 2063 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 2064#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \\ 2065attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \\ 2066attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\\ 2067attr struct type *name##_RB_REMOVE(struct name *, struct type *); \\ 2068attr struct type *name##_RB_INSERT(struct name *, struct type *); \\ 2069attr struct type *name##_RB_FIND(struct name *, struct type *); \\ 2070attr struct type *name##_RB_NFIND(struct name *, struct type *); \\ 2071attr struct type *name##_RB_NEXT(struct type *); \\ 2072attr struct type *name##_RB_PREV(struct type *); \\ 2073attr struct type *name##_RB_MINMAX(struct name *, int); \\ 2074 \\ 2075 2076/* Main rb operation. 2077 * Moves node close to the key of elm to top 2078 */ 2079#define RB_GENERATE(name, type, field, cmp) \\ 2080 RB_GENERATE_INTERNAL(name, type, field, cmp,) 2081#define RB_GENERATE_STATIC(name, type, field, cmp) \\ 2082 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 2083#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \\ 2084attr void \\ 2085name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \\ 2086{ \\ 2087 struct type *parent, *gparent, *tmp; \\ 2088 while ((parent = RB_PARENT(elm, field)) && \\ 2089 RB_COLOR(parent, field) == RB_RED) { \\ 2090 gparent = RB_PARENT(parent, field); \\ 2091 if (parent == RB_LEFT(gparent, field)) { \\ 2092 tmp = RB_RIGHT(gparent, field); \\ 2093 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \\ 2094 RB_COLOR(tmp, field) = RB_BLACK; \\ 2095 RB_SET_BLACKRED(parent, gparent, field);\\ 2096 elm = gparent; \\ 2097 continue; \\ 2098 } \\ 2099 if (RB_RIGHT(parent, field) == elm) { \\ 2100 RB_ROTATE_LEFT(head, parent, tmp, field);\\ 2101 tmp = parent; \\ 2102 parent = elm; \\ 2103 elm = tmp; \\ 2104 } \\ 2105 RB_SET_BLACKRED(parent, gparent, field); \\ 2106 RB_ROTATE_RIGHT(head, gparent, tmp, field); \\ 2107 } else { \\ 2108 tmp = RB_LEFT(gparent, field); \\ 2109 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \\ 2110 RB_COLOR(tmp, field) = RB_BLACK; \\ 2111 RB_SET_BLACKRED(parent, gparent, field);\\ 2112 elm = gparent; \\ 2113 continue; \\ 2114 } \\ 2115 if (RB_LEFT(parent, field) == elm) { \\ 2116 RB_ROTATE_RIGHT(head, parent, tmp, field);\\ 2117 tmp = parent; \\ 2118 parent = elm; \\ 2119 elm = tmp; \\ 2120 } \\ 2121 RB_SET_BLACKRED(parent, gparent, field); \\ 2122 RB_ROTATE_LEFT(head, gparent, tmp, field); \\ 2123 } \\ 2124 } \\ 2125 RB_COLOR(head->rbh_root, field) = RB_BLACK; \\ 2126} \\ 2127 \\ 2128attr void \\ 2129name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \\ 2130{ \\ 2131 struct type *tmp; \\ 2132 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \\ 2133 elm != RB_ROOT(head)) { \\ 2134 if (RB_LEFT(parent, field) == elm) { \\ 2135 tmp = RB_RIGHT(parent, field); \\ 2136 if (RB_COLOR(tmp, field) == RB_RED) { \\ 2137 RB_SET_BLACKRED(tmp, parent, field); \\ 2138 RB_ROTATE_LEFT(head, parent, tmp, field);\\ 2139 tmp = RB_RIGHT(parent, field); \\ 2140 } \\ 2141 if ((RB_LEFT(tmp, field) == NULL || \\ 2142 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\\ 2143 (RB_RIGHT(tmp, field) == NULL || \\ 2144 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\\ 2145 RB_COLOR(tmp, field) = RB_RED; \\ 2146 elm = parent; \\ 2147 parent = RB_PARENT(elm, field); \\ 2148 } else { \\ 2149 if (RB_RIGHT(tmp, field) == NULL || \\ 2150 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\\ 2151 struct type *oleft; \\ 2152 if ((oleft = RB_LEFT(tmp, field)))\\ 2153 RB_COLOR(oleft, field) = RB_BLACK;\\ 2154 RB_COLOR(tmp, field) = RB_RED; \\ 2155 RB_ROTATE_RIGHT(head, tmp, oleft, field);\\ 2156 tmp = RB_RIGHT(parent, field); \\ 2157 } \\ 2158 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\\ 2159 RB_COLOR(parent, field) = RB_BLACK; \\ 2160 if (RB_RIGHT(tmp, field)) \\ 2161 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\\ 2162 RB_ROTATE_LEFT(head, parent, tmp, field);\\ 2163 elm = RB_ROOT(head); \\ 2164 break; \\ 2165 } \\ 2166 } else { \\ 2167 tmp = RB_LEFT(parent, field); \\ 2168 if (RB_COLOR(tmp, field) == RB_RED) { \\ 2169 RB_SET_BLACKRED(tmp, parent, field); \\ 2170 RB_ROTATE_RIGHT(head, parent, tmp, field);\\ 2171 tmp = RB_LEFT(parent, field); \\ 2172 } \\ 2173 if ((RB_LEFT(tmp, field) == NULL || \\ 2174 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\\ 2175 (RB_RIGHT(tmp, field) == NULL || \\ 2176 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\\ 2177 RB_COLOR(tmp, field) = RB_RED; \\ 2178 elm = parent; \\ 2179 parent = RB_PARENT(elm, field); \\ 2180 } else { \\ 2181 if (RB_LEFT(tmp, field) == NULL || \\ 2182 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\\ 2183 struct type *oright; \\ 2184 if ((oright = RB_RIGHT(tmp, field)))\\ 2185 RB_COLOR(oright, field) = RB_BLACK;\\ 2186 RB_COLOR(tmp, field) = RB_RED; \\ 2187 RB_ROTATE_LEFT(head, tmp, oright, field);\\ 2188 tmp = RB_LEFT(parent, field); \\ 2189 } \\ 2190 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\\ 2191 RB_COLOR(parent, field) = RB_BLACK; \\ 2192 if (RB_LEFT(tmp, field)) \\ 2193 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\\ 2194 RB_ROTATE_RIGHT(head, parent, tmp, field);\\ 2195 elm = RB_ROOT(head); \\ 2196 break; \\ 2197 } \\ 2198 } \\ 2199 } \\ 2200 if (elm) \\ 2201 RB_COLOR(elm, field) = RB_BLACK; \\ 2202} \\ 2203 \\ 2204attr struct type * \\ 2205name##_RB_REMOVE(struct name *head, struct type *elm) \\ 2206{ \\ 2207 struct type *child, *parent, *old = elm; \\ 2208 int color; \\ 2209 if (RB_LEFT(elm, field) == NULL) \\ 2210 child = RB_RIGHT(elm, field); \\ 2211 else if (RB_RIGHT(elm, field) == NULL) \\ 2212 child = RB_LEFT(elm, field); \\ 2213 else { \\ 2214 struct type *left; \\ 2215 elm = RB_RIGHT(elm, field); \\ 2216 while ((left = RB_LEFT(elm, field))) \\ 2217 elm = left; \\ 2218 child = RB_RIGHT(elm, field); \\ 2219 parent = RB_PARENT(elm, field); \\ 2220 color = RB_COLOR(elm, field); \\ 2221 if (child) \\ 2222 RB_PARENT(child, field) = parent; \\ 2223 if (parent) { \\ 2224 if (RB_LEFT(parent, field) == elm) \\ 2225 RB_LEFT(parent, field) = child; \\ 2226 else \\ 2227 RB_RIGHT(parent, field) = child; \\ 2228 RB_AUGMENT(parent); \\ 2229 } else \\ 2230 RB_ROOT(head) = child; \\ 2231 if (RB_PARENT(elm, field) == old) \\ 2232 parent = elm; \\ 2233 (elm)->field = (old)->field; \\ 2234 if (RB_PARENT(old, field)) { \\ 2235 if (RB_LEFT(RB_PARENT(old, field), field) == old)\\ 2236 RB_LEFT(RB_PARENT(old, field), field) = elm;\\ 2237 else \\ 2238 RB_RIGHT(RB_PARENT(old, field), field) = elm;\\ 2239 RB_AUGMENT(RB_PARENT(old, field)); \\ 2240 } else \\ 2241 RB_ROOT(head) = elm; \\ 2242 RB_PARENT(RB_LEFT(old, field), field) = elm; \\ 2243 if (RB_RIGHT(old, field)) \\ 2244 RB_PARENT(RB_RIGHT(old, field), field) = elm; \\ 2245 if (parent) { \\ 2246 left = parent; \\ 2247 do { \\ 2248 RB_AUGMENT(left); \\ 2249 } while ((left = RB_PARENT(left, field))); \\ 2250 } \\ 2251 goto color; \\ 2252 } \\ 2253 parent = RB_PARENT(elm, field); \\ 2254 color = RB_COLOR(elm, field); \\ 2255 if (child) \\ 2256 RB_PARENT(child, field) = parent; \\ 2257 if (parent) { \\ 2258 if (RB_LEFT(parent, field) == elm) \\ 2259 RB_LEFT(parent, field) = child; \\ 2260 else \\ 2261 RB_RIGHT(parent, field) = child; \\ 2262 RB_AUGMENT(parent); \\ 2263 } else \\ 2264 RB_ROOT(head) = child; \\ 2265color: \\ 2266 if (color == RB_BLACK) \\ 2267 name##_RB_REMOVE_COLOR(head, parent, child); \\ 2268 return (old); \\ 2269} \\ 2270 \\ 2271/* Inserts a node into the RB tree */ \\ 2272attr struct type * \\ 2273name##_RB_INSERT(struct name *head, struct type *elm) \\ 2274{ \\ 2275 struct type *tmp; \\ 2276 struct type *parent = NULL; \\ 2277 int comp = 0; \\ 2278 tmp = RB_ROOT(head); \\ 2279 while (tmp) { \\ 2280 parent = tmp; \\ 2281 comp = (cmp)(elm, parent); \\ 2282 if (comp < 0) \\ 2283 tmp = RB_LEFT(tmp, field); \\ 2284 else if (comp > 0) \\ 2285 tmp = RB_RIGHT(tmp, field); \\ 2286 else \\ 2287 return (tmp); \\ 2288 } \\ 2289 RB_SET(elm, parent, field); \\ 2290 if (parent != NULL) { \\ 2291 if (comp < 0) \\ 2292 RB_LEFT(parent, field) = elm; \\ 2293 else \\ 2294 RB_RIGHT(parent, field) = elm; \\ 2295 RB_AUGMENT(parent); \\ 2296 } else \\ 2297 RB_ROOT(head) = elm; \\ 2298 name##_RB_INSERT_COLOR(head, elm); \\ 2299 return (NULL); \\ 2300} \\ 2301 \\ 2302/* Finds the node with the same key as elm */ \\ 2303attr struct type * \\ 2304name##_RB_FIND(struct name *head, struct type *elm) \\ 2305{ \\ 2306 struct type *tmp = RB_ROOT(head); \\ 2307 int comp; \\ 2308 while (tmp) { \\ 2309 comp = cmp(elm, tmp); \\ 2310 if (comp < 0) \\ 2311 tmp = RB_LEFT(tmp, field); \\ 2312 else if (comp > 0) \\ 2313 tmp = RB_RIGHT(tmp, field); \\ 2314 else \\ 2315 return (tmp); \\ 2316 } \\ 2317 return (NULL); \\ 2318} \\ 2319 \\ 2320/* Finds the first node greater than or equal to the search key */ \\ 2321attr struct type * \\ 2322name##_RB_NFIND(struct name *head, struct type *elm) \\ 2323{ \\ 2324 struct type *tmp = RB_ROOT(head); \\ 2325 struct type *res = NULL; \\ 2326 int comp; \\ 2327 while (tmp) { \\ 2328 comp = cmp(elm, tmp); \\ 2329 if (comp < 0) { \\ 2330 res = tmp; \\ 2331 tmp = RB_LEFT(tmp, field); \\ 2332 } \\ 2333 else if (comp > 0) \\ 2334 tmp = RB_RIGHT(tmp, field); \\ 2335 else \\ 2336 return (tmp); \\ 2337 } \\ 2338 return (res); \\ 2339} \\ 2340 \\ 2341/* ARGSUSED */ \\ 2342attr struct type * \\ 2343name##_RB_NEXT(struct type *elm) \\ 2344{ \\ 2345 if (RB_RIGHT(elm, field)) { \\ 2346 elm = RB_RIGHT(elm, field); \\ 2347 while (RB_LEFT(elm, field)) \\ 2348 elm = RB_LEFT(elm, field); \\ 2349 } else { \\ 2350 if (RB_PARENT(elm, field) && \\ 2351 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \\ 2352 elm = RB_PARENT(elm, field); \\ 2353 else { \\ 2354 while (RB_PARENT(elm, field) && \\ 2355 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\\ 2356 elm = RB_PARENT(elm, field); \\ 2357 elm = RB_PARENT(elm, field); \\ 2358 } \\ 2359 } \\ 2360 return (elm); \\ 2361} \\ 2362 \\ 2363/* ARGSUSED */ \\ 2364attr struct type * \\ 2365name##_RB_PREV(struct type *elm) \\ 2366{ \\ 2367 if (RB_LEFT(elm, field)) { \\ 2368 elm = RB_LEFT(elm, field); \\ 2369 while (RB_RIGHT(elm, field)) \\ 2370 elm = RB_RIGHT(elm, field); \\ 2371 } else { \\ 2372 if (RB_PARENT(elm, field) && \\ 2373 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \\ 2374 elm = RB_PARENT(elm, field); \\ 2375 else { \\ 2376 while (RB_PARENT(elm, field) && \\ 2377 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\\ 2378 elm = RB_PARENT(elm, field); \\ 2379 elm = RB_PARENT(elm, field); \\ 2380 } \\ 2381 } \\ 2382 return (elm); \\ 2383} \\ 2384 \\ 2385attr struct type * \\ 2386name##_RB_MINMAX(struct name *head, int val) \\ 2387{ \\ 2388 struct type *tmp = RB_ROOT(head); \\ 2389 struct type *parent = NULL; \\ 2390 while (tmp) { \\ 2391 parent = tmp; \\ 2392 if (val < 0) \\ 2393 tmp = RB_LEFT(tmp, field); \\ 2394 else \\ 2395 tmp = RB_RIGHT(tmp, field); \\ 2396 } \\ 2397 return (parent); \\ 2398} 2399 2400#define RB_NEGINF -1 2401#define RB_INF 1 2402 2403#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 2404#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 2405#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 2406#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 2407#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 2408#define RB_PREV(name, x, y) name##_RB_PREV(y) 2409#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 2410#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 2411 2412#define RB_FOREACH(x, name, head) \\ 2413 for ((x) = RB_MIN(name, head); \\ 2414 (x) != NULL; \\ 2415 (x) = name##_RB_NEXT(x)) 2416 2417#define RB_FOREACH_SAFE(x, name, head, y) \\ 2418 for ((x) = RB_MIN(name, head); \\ 2419 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \\ 2420 (x) = (y)) 2421 2422#define RB_FOREACH_REVERSE(x, name, head) \\ 2423 for ((x) = RB_MAX(name, head); \\ 2424 (x) != NULL; \\ 2425 (x) = name##_RB_PREV(x)) 2426 2427#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \\ 2428 for ((x) = RB_MAX(name, head); \\ 2429 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \\ 2430 (x) = (y)) 2431 2432__HEREDOC__ 2433fi 2434 2435cat << __HEREDOC__ 2436#endif /*!OCONFIGURE_CONFIG_H*/ 2437__HEREDOC__ 2438 2439if [ ${HAVE_FTS} -eq 0 ]; then 2440 cat << __HEREDOC__ 2441/* 2442 * Compatibility for fts(3) functions. 2443 */ 2444typedef struct { 2445 struct _ftsent *fts_cur; /* current node */ 2446 struct _ftsent *fts_child; /* linked list of children */ 2447 struct _ftsent **fts_array; /* sort array */ 2448 dev_t fts_dev; /* starting device # */ 2449 char *fts_path; /* path for this descent */ 2450 int fts_rfd; /* fd for root */ 2451 size_t fts_pathlen; /* sizeof(path) */ 2452 int fts_nitems; /* elements in the sort array */ 2453 int (*fts_compar)(const struct _ftsent **, const struct _ftsent **); /* compare function */ 2454#define FTS_COMFOLLOW 0x0001 /* follow command line symlinks */ 2455#define FTS_LOGICAL 0x0002 /* logical walk */ 2456#define FTS_NOCHDIR 0x0004 /* don't change directories */ 2457#define FTS_NOSTAT 0x0008 /* don't get stat info */ 2458#define FTS_PHYSICAL 0x0010 /* physical walk */ 2459#define FTS_SEEDOT 0x0020 /* return dot and dot-dot */ 2460#define FTS_XDEV 0x0040 /* don't cross devices */ 2461#define FTS_OPTIONMASK 0x00ff /* valid user option mask */ 2462#define FTS_NAMEONLY 0x1000 /* (private) child names only */ 2463#define FTS_STOP 0x2000 /* (private) unrecoverable error */ 2464 int fts_options; /* fts_open options, global flags */ 2465} FTS; 2466 2467typedef struct _ftsent { 2468 struct _ftsent *fts_cycle; /* cycle node */ 2469 struct _ftsent *fts_parent; /* parent directory */ 2470 struct _ftsent *fts_link; /* next file in directory */ 2471 long fts_number; /* local numeric value */ 2472 void *fts_pointer; /* local address value */ 2473 char *fts_accpath; /* access path */ 2474 char *fts_path; /* root path */ 2475 int fts_errno; /* errno for this node */ 2476 int fts_symfd; /* fd for symlink */ 2477 size_t fts_pathlen; /* strlen(fts_path) */ 2478 size_t fts_namelen; /* strlen(fts_name) */ 2479 ino_t fts_ino; /* inode */ 2480 dev_t fts_dev; /* device */ 2481 nlink_t fts_nlink; /* link count */ 2482#define FTS_ROOTPARENTLEVEL -1 2483#define FTS_ROOTLEVEL 0 2484#define FTS_MAXLEVEL 0x7fffffff 2485 int fts_level; /* depth (-1 to N) */ 2486#define FTS_D 1 /* preorder directory */ 2487#define FTS_DC 2 /* directory that causes cycles */ 2488#define FTS_DEFAULT 3 /* none of the above */ 2489#define FTS_DNR 4 /* unreadable directory */ 2490#define FTS_DOT 5 /* dot or dot-dot */ 2491#define FTS_DP 6 /* postorder directory */ 2492#define FTS_ERR 7 /* error; errno is set */ 2493#define FTS_F 8 /* regular file */ 2494#define FTS_INIT 9 /* initialized only */ 2495#define FTS_NS 10 /* stat(2) failed */ 2496#define FTS_NSOK 11 /* no stat(2) requested */ 2497#define FTS_SL 12 /* symbolic link */ 2498#define FTS_SLNONE 13 /* symbolic link without target */ 2499 unsigned short fts_info; /* user flags for FTSENT structure */ 2500#define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */ 2501#define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */ 2502 unsigned short fts_flags; /* private flags for FTSENT structure */ 2503#define FTS_AGAIN 1 /* read node again */ 2504#define FTS_FOLLOW 2 /* follow symbolic link */ 2505#define FTS_NOINSTR 3 /* no instructions */ 2506#define FTS_SKIP 4 /* discard node */ 2507 unsigned short fts_instr; /* fts_set() instructions */ 2508 unsigned short fts_spare; /* unused */ 2509 struct stat *fts_statp; /* stat(2) information */ 2510 char fts_name[1]; /* file name */ 2511} FTSENT; 2512 2513FTSENT *fts_children(FTS *, int); 2514int fts_close(FTS *); 2515FTS *fts_open(char * const *, int, 2516 int (*)(const FTSENT **, const FTSENT **)); 2517FTSENT *fts_read(FTS *); 2518int fts_set(FTS *, FTSENT *, int); 2519 2520__HEREDOC__ 2521fi 2522 2523echo "config.h: written" 1>&2 2524echo "config.h: written" 1>&3 2525 2526#---------------------------------------------------------------------- 2527# Now we go to generate our Makefile.configure. 2528# This file is simply a bunch of Makefile variables. 2529# They'll work in both GNUmakefile and BSDmakefile. 2530# You MIGHT want to change this. 2531#---------------------------------------------------------------------- 2532 2533exec > Makefile.configure 2534 2535[ -z "${BINDIR}" ] && BINDIR="${PREFIX}/bin" 2536[ -z "${SBINDIR}" ] && SBINDIR="${PREFIX}/sbin" 2537[ -z "${INCLUDEDIR}" ] && INCLUDEDIR="${PREFIX}/include" 2538[ -z "${LIBDIR}" ] && LIBDIR="${PREFIX}/lib" 2539[ -z "${MANDIR}" ] && MANDIR="${PREFIX}/share/man" 2540[ -z "${SHAREDIR}" ] && SHAREDIR="${PREFIX}/share" 2541 2542[ -z "${INSTALL_PROGRAM}" ] && INSTALL_PROGRAM="${INSTALL} -m 0555" 2543[ -z "${INSTALL_LIB}" ] && INSTALL_LIB="${INSTALL} -m 0444" 2544[ -z "${INSTALL_MAN}" ] && INSTALL_MAN="${INSTALL} -m 0444" 2545[ -z "${INSTALL_DATA}" ] && INSTALL_DATA="${INSTALL} -m 0444" 2546 2547cat << __HEREDOC__ 2548AR = ${AR} 2549CC = ${CC} 2550CFLAGS = ${CFLAGS} 2551CPPFLAGS = ${CPPFLAGS} 2552LDADD = ${LDADD} 2553LDADD_B64_NTOP = ${LDADD_B64_NTOP} 2554LDADD_CRYPT = ${LDADD_CRYPT} 2555LDADD_EXECINFO = ${LDADD_EXECINFO} 2556LDADD_LIB_SOCKET = ${LDADD_LIB_SOCKET} 2557LDADD_MD5 = ${LDADD_MD5} 2558LDADD_SHA2 = ${LDADD_SHA2} 2559LDADD_STATIC = ${LDADD_STATIC} 2560LDFLAGS = ${LDFLAGS} 2561STATIC = ${STATIC} 2562PREFIX = ${PREFIX} 2563BINDIR = ${BINDIR} 2564SHAREDIR = ${SHAREDIR} 2565SBINDIR = ${SBINDIR} 2566INCLUDEDIR = ${INCLUDEDIR} 2567LIBDIR = ${LIBDIR} 2568MANDIR = ${MANDIR} 2569INSTALL = ${INSTALL} 2570INSTALL_PROGRAM = ${INSTALL_PROGRAM} 2571INSTALL_LIB = ${INSTALL_LIB} 2572INSTALL_MAN = ${INSTALL_MAN} 2573INSTALL_DATA = ${INSTALL_DATA} 2574__HEREDOC__ 2575 2576echo "Makefile.configure: written" 1>&2 2577echo "Makefile.configure: written" 1>&3 2578 2579exit 0 2580