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