configure (64894B)
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.1.17" 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 CPPFLAGS= 68 LDFLAGS= 69 DESTDIR= 70 PREFIX="/usr/local" 71 BINDIR= 72 SBINDIR= 73 INCLUDEDIR= 74 LIBDIR= 75 MANDIR= 76 SHAREDIR= 77 INSTALL="install" 78 INSTALL_PROGRAM= 79 INSTALL_LIB= 80 INSTALL_MAN= 81 INSTALL_DATA= 82 83 #---------------------------------------------------------------------- 84 # Allow certain variables to be overriden on the command line. 85 #---------------------------------------------------------------------- 86 87 for keyvals in "$@" 88 do 89 key=`echo $keyvals | cut -s -d '=' -f 1` 90 if [ -z "$key" ] 91 then 92 echo "$0: invalid key-value: $keyvals" 1>&2 93 exit 1 94 fi 95 val=`echo $keyvals | cut -d '=' -f 2-` 96 case "$key" in 97 LDADD) 98 LDADD="$val" ;; 99 LDFLAGS) 100 LDFLAGS="$val" ;; 101 CPPFLAGS) 102 CPPFLAGS="$val" ;; 103 DESTDIR) 104 DESTDIR="$val" ;; 105 PREFIX) 106 PREFIX="$val" ;; 107 MANDIR) 108 MANDIR="$val" ;; 109 LIBDIR) 110 LIBDIR="$val" ;; 111 BINDIR) 112 BINDIR="$val" ;; 113 SHAREDIR) 114 SHAREDIR="$val" ;; 115 SBINDIR) 116 SBINDIR="$val" ;; 117 INCLUDEDIR) 118 INCLUDEDIR="$val" ;; 119 *) 120 echo "$0: invalid key: $key" 1>&2 121 exit 1 122 esac 123 done 124 125 126 #---------------------------------------------------------------------- 127 # These are the values that will be pushed into config.h after we test 128 # for whether they're supported or not. 129 # Each of these must have a runtest(), below. 130 # Please sort by alpha, for clarity. 131 # You WANT to change this. 132 #---------------------------------------------------------------------- 133 134 HAVE_ARC4RANDOM= 135 HAVE_B64_NTOP= 136 HAVE_CAPSICUM= 137 HAVE_ENDIAN_H= 138 HAVE_ERR= 139 HAVE_EXPLICIT_BZERO= 140 HAVE_GETEXECNAME= 141 HAVE_GETPROGNAME= 142 HAVE_INFTIM= 143 HAVE_MD5= 144 HAVE_MEMMEM= 145 HAVE_MEMRCHR= 146 HAVE_MEMSET_S= 147 HAVE_PATH_MAX= 148 HAVE_PLEDGE= 149 HAVE_PROGRAM_INVOCATION_SHORT_NAME= 150 HAVE_READPASSPHRASE= 151 HAVE_REALLOCARRAY= 152 HAVE_RECALLOCARRAY= 153 HAVE_SANDBOX_INIT= 154 HAVE_SECCOMP_FILTER= 155 HAVE_SOCK_NONBLOCK= 156 HAVE_STRLCAT= 157 HAVE_STRLCPY= 158 HAVE_STRNDUP= 159 HAVE_STRNLEN= 160 HAVE_STRTONUM= 161 HAVE_SYS_QUEUE= 162 HAVE_SYS_TREE= 163 HAVE_SYSTRACE= 164 HAVE_UNVEIL= 165 HAVE_ZLIB= 166 HAVE___PROGNAME= 167 168 #---------------------------------------------------------------------- 169 # Allow configure.local to override all variables, default settings, 170 # command-line arguments, and tested features, above. 171 # You PROBABLY DO NOT want to change this. 172 #---------------------------------------------------------------------- 173 174 if [ -r ./configure.local ]; then 175 echo "configure.local: reading..." 1>&2 176 echo "configure.local: reading..." 1>&3 177 cat ./configure.local 1>&3 178 . ./configure.local 179 else 180 echo "configure.local: no (fully automatic configuration)" 1>&2 181 echo "configure.local: no (fully automatic configuration)" 1>&3 182 fi 183 184 echo 1>&3 185 186 #---------------------------------------------------------------------- 187 # Infrastructure for running tests. 188 # These consists of a series of functions that will attempt to run the 189 # given test file and record its exit into a HAVE_xxx variable. 190 # You DO NOT want to change this. 191 #---------------------------------------------------------------------- 192 193 COMP="${CC} ${CFLAGS} ${CPPFLAGS} -Wno-unused -Werror" 194 195 # Check whether this HAVE_ setting is manually overridden. 196 # If yes, use the override, if no, do not decide anything yet. 197 # Arguments: lower-case test name, manual value 198 199 ismanual() { 200 [ -z "${3}" ] && return 1 201 echo "${1}: manual (HAVE_${2}=${3})" 1>&2 202 echo "${1}: manual (HAVE_${2}=${3})" 1>&3 203 echo 1>&3 204 return 0 205 } 206 207 # Run a single autoconfiguration test. 208 # In case of success, enable the feature. 209 # In case of failure, do not decide anything yet. 210 # Arguments: lower-case test name, upper-case test name, additional 211 # CFLAGS, additional LIBS. 212 213 singletest() { 214 extralib="" 215 cat 1>&3 << __HEREDOC__ 216 ${1}: testing... 217 ${COMP} -DTEST_${2} ${3} -o test-${1} tests.c ${4} 218 __HEREDOC__ 219 if ${COMP} -DTEST_${2} ${3} -o "test-${1}" tests.c ${4} 1>&3 2>&3; then 220 echo "${1}: ${CC} succeeded" 1>&3 221 else 222 if [ -n "${5}" ] ; then 223 echo "${1}: ${CC} failed with $? (retrying)" 1>&3 224 cat 1>&3 << __HEREDOC__ 225 ${1}: testing... 226 ${COMP} -DTEST_${2} ${3} -o test-${1} tests.c ${5} 227 __HEREDOC__ 228 if ${COMP} -DTEST_${2} ${3} -o "test-${1}" tests.c ${5} 1>&3 2>&3; then 229 echo "${1}: ${CC} succeeded" 1>&3 230 extralib="(with ${5})" 231 else 232 echo "${1}: ${CC} failed with $?" 1>&3 233 echo 1>&3 234 return 1 235 fi 236 else 237 echo "${1}: ${CC} failed with $?" 1>&3 238 echo 1>&3 239 return 1 240 fi 241 fi 242 243 echo "${1}: yes ${extralib}" 1>&2 244 echo "${1}: yes ${extralib}" 1>&3 245 echo 1>&3 246 eval HAVE_${2}=1 247 rm "test-${1}" 248 return 0 249 250 # Don't actually run the test: none of our tests check for 251 # run-time behaviour. 252 # if ./test-${1} 1>&3 2>&3; then 253 # echo "${1}: yes" 1>&2 254 # echo "${1}: yes" 1>&3 255 # echo 1>&3 256 # eval HAVE_${2}=1 257 # rm "test-${1}" 258 # return 0 259 # else 260 # echo "${1}: execution failed with $?" 1>&3 261 # echo 1>&3 262 # rm "test-${1}" 263 # return 1 264 # fi 265 } 266 267 # Run a complete autoconfiguration test, including the check for 268 # a manual override and disabling the feature on failure. 269 # Arguments: lower case name, upper case name, additional CFLAGS, 270 # additional LDADD, alternative LDADD. 271 272 runtest() { 273 eval _manual=\${HAVE_${2}} 274 ismanual "${1}" "${2}" "${_manual}" && return 0 275 singletest "${1}" "${2}" "${3}" "${4}" "${5}" && return 0 276 echo "${1}: no" 1>&2 277 eval HAVE_${2}=0 278 return 1 279 } 280 281 #---------------------------------------------------------------------- 282 # Begin running the tests themselves. 283 # All of your tests must be defined here. 284 # Please sort as the HAVE_xxxx values were defined. 285 # You WANT to change this. 286 # It consists of the following columns: 287 # runtest 288 # (1) test file 289 # (2) macro to set 290 # (3) argument to cc *before* -o 291 # (4) argument to cc *after* 292 # (5) alternative argument to cc *after* 293 #---------------------------------------------------------------------- 294 295 runtest arc4random ARC4RANDOM || true 296 runtest b64_ntop B64_NTOP "" "" "-lresolv" || true 297 runtest capsicum CAPSICUM || true 298 runtest endian_h ENDIAN_H || true 299 runtest err ERR || true 300 runtest explicit_bzero EXPLICIT_BZERO || true 301 runtest getexecname GETEXECNAME || true 302 runtest getprogname GETPROGNAME || true 303 runtest INFTIM INFTIM || true 304 runtest md5 MD5 "" "" "-lmd" || true 305 runtest memmem MEMMEM || true 306 runtest memrchr MEMRCHR || true 307 runtest memset_s MEMSET_S || true 308 runtest PATH_MAX PATH_MAX || true 309 runtest pledge PLEDGE || true 310 runtest program_invocation_short_name PROGRAM_INVOCATION_SHORT_NAME || true 311 runtest readpassphrase READPASSPHRASE || true 312 runtest reallocarray REALLOCARRAY || true 313 runtest recallocarray RECALLOCARRAY || true 314 runtest sandbox_init SANDBOX_INIT "-Wno-deprecated" || true 315 runtest seccomp-filter SECCOMP_FILTER || true 316 runtest SOCK_NONBLOCK SOCK_NONBLOCK || true 317 runtest strlcat STRLCAT || true 318 runtest strlcpy STRLCPY || true 319 runtest strndup STRNDUP || true 320 runtest strnlen STRNLEN || true 321 runtest strtonum STRTONUM || true 322 runtest sys_queue SYS_QUEUE || true 323 runtest sys_tree SYS_TREE || true 324 runtest systrace SYSTRACE || true 325 runtest unveil UNVEIL || true 326 runtest zlib ZLIB "" "-lz" || true 327 runtest __progname __PROGNAME || true 328 329 #---------------------------------------------------------------------- 330 # Output writing: generate the config.h file. 331 # This file contains all of the HAVE_xxxx variables necessary for 332 # compiling your source. 333 # You must include "config.h" BEFORE any other variables. 334 # You WANT to change this. 335 #---------------------------------------------------------------------- 336 337 exec > config.h 338 339 # Start with prologue. 340 341 cat << __HEREDOC__ 342 #ifndef OCONFIGURE_CONFIG_H 343 #define OCONFIGURE_CONFIG_H 344 #ifdef __cplusplus 345 #error "Do not use C++: this is a C application." 346 #endif 347 #if !defined(__GNUC__) || (__GNUC__ < 4) 348 #define __attribute__(x) 349 #endif 350 #if defined(__linux__) || defined(__MINT__) 351 #define _GNU_SOURCE /* See test-*.c what needs this. */ 352 #endif 353 #if !defined(__BEGIN_DECLS) 354 # define __BEGIN_DECLS 355 #endif 356 #if !defined(__END_DECLS) 357 # define __END_DECLS 358 #endif 359 __HEREDOC__ 360 361 # This is just for size_t. 362 # Most of these functions, in the real world, pull in <string.h> or 363 # someting that pulls in support for size_t. 364 # Our function declarations are standalone, so specify them here. 365 366 [ ${HAVE_MD5} -eq 0 -o \ 367 ${HAVE_READPASSPHRASE} -eq 0 -o \ 368 ${HAVE_REALLOCARRAY} -eq 0 -o \ 369 ${HAVE_RECALLOCARRAY} -eq 0 -o \ 370 ${HAVE_STRLCAT} -eq 0 -o \ 371 ${HAVE_STRLCPY} -eq 0 -o \ 372 ${HAVE_STRNDUP} -eq 0 -o \ 373 ${HAVE_STRNLEN} -eq 0 ] \ 374 && echo "#include <sys/types.h>" 375 376 [ ${HAVE_ERR} -eq 0 ] \ 377 && echo "#include <stdarg.h>" 378 379 # Now we handle our HAVE_xxxx values. 380 # Most will just be defined as 0 or 1. 381 382 [ ${HAVE_PATH_MAX} -eq 0 ] \ 383 && echo "#define PATH_MAX 4096" 384 385 [ ${HAVE_INFTIM} -eq 0 ] \ 386 && echo "#define INFTIM (-1)" 387 388 cat << __HEREDOC__ 389 #define HAVE_ARC4RANDOM ${HAVE_ARC4RANDOM} 390 #define HAVE_B64_NTOP ${HAVE_B64_NTOP} 391 #define HAVE_CAPSICUM ${HAVE_CAPSICUM} 392 #define HAVE_ENDIAN_H ${HAVE_ENDIAN_H} 393 #define HAVE_ERR ${HAVE_ERR} 394 #define HAVE_EXPLICIT_BZERO ${HAVE_EXPLICIT_BZERO} 395 #define HAVE_GETEXECNAME ${HAVE_GETEXECNAME} 396 #define HAVE_GETPROGNAME ${HAVE_GETPROGNAME} 397 #define HAVE_INFTIM ${HAVE_INFTIM} 398 #define HAVE_MD5 ${HAVE_MD5} 399 #define HAVE_MEMMEM ${HAVE_MEMMEM} 400 #define HAVE_MEMRCHR ${HAVE_MEMRCHR} 401 #define HAVE_MEMSET_S ${HAVE_MEMSET_S} 402 #define HAVE_PATH_MAX ${HAVE_PATH_MAX} 403 #define HAVE_PLEDGE ${HAVE_PLEDGE} 404 #define HAVE_PROGRAM_INVOCATION_SHORT_NAME ${HAVE_PROGRAM_INVOCATION_SHORT_NAME} 405 #define HAVE_READPASSPHRASE ${HAVE_READPASSPHRASE} 406 #define HAVE_REALLOCARRAY ${HAVE_REALLOCARRAY} 407 #define HAVE_RECALLOCARRAY ${HAVE_RECALLOCARRAY} 408 #define HAVE_SANDBOX_INIT ${HAVE_SANDBOX_INIT} 409 #define HAVE_SECCOMP_FILTER ${HAVE_SECCOMP_FILTER} 410 #define HAVE_SOCK_NONBLOCK ${HAVE_SOCK_NONBLOCK} 411 #define HAVE_STRLCAT ${HAVE_STRLCAT} 412 #define HAVE_STRLCPY ${HAVE_STRLCPY} 413 #define HAVE_STRNDUP ${HAVE_STRNDUP} 414 #define HAVE_STRNLEN ${HAVE_STRNLEN} 415 #define HAVE_STRTONUM ${HAVE_STRTONUM} 416 #define HAVE_SYS_QUEUE ${HAVE_SYS_QUEUE} 417 #define HAVE_SYS_TREE ${HAVE_SYS_TREE} 418 #define HAVE_SYSTRACE ${HAVE_SYSTRACE} 419 #define HAVE_UNVEIL ${HAVE_UNVEIL} 420 #define HAVE_ZLIB ${HAVE_ZLIB} 421 #define HAVE___PROGNAME ${HAVE___PROGNAME} 422 __HEREDOC__ 423 424 # Now we do our function declarations for missing functions. 425 426 if [ ${HAVE_ERR} -eq 0 ]; then 427 echo "extern void err(int, const char *, ...);" 428 echo "extern void errx(int, const char *, ...);" 429 echo "extern void warn(const char *, ...);" 430 echo "extern void warnx(const char *, ...);" 431 echo "extern void vwarn(const char *, va_list);" 432 echo "extern void vwarnx(const char *, va_list);" 433 fi 434 435 if [ ${HAVE_MD5} -eq 0 ]; then 436 echo "#define MD5_BLOCK_LENGTH 64" 437 echo "#define MD5_DIGEST_LENGTH 16" 438 echo "#define MD5_DIGEST_STRING_LENGTH (MD5_DIGEST_LENGTH * 2 + 1)" 439 cat <<!! 440 typedef struct MD5Context { 441 u_int32_t state[4]; 442 u_int64_t count; 443 u_int8_t buffer[MD5_BLOCK_LENGTH]; 444 } MD5_CTX; 445 !! 446 echo "extern void MD5Init(MD5_CTX *);" 447 echo "extern void MD5Update(MD5_CTX *, const u_int8_t *, size_t);" 448 echo "extern void MD5Pad(MD5_CTX *);" 449 echo "extern void MD5Transform(u_int32_t [4], const u_int8_t [MD5_BLOCK_LENGTH]);" 450 echo "extern char *MD5End(MD5_CTX *, char *);" 451 echo "extern void MD5Final(u_int8_t [MD5_DIGEST_LENGTH], MD5_CTX *);"; 452 fi 453 454 if [ ${HAVE_SECCOMP_FILTER} -eq 1 ]; then 455 arch=`uname -m 2>/dev/null || echo unknown` 456 case "$arch" in 457 x86_64) 458 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_X86_64" 459 ;; 460 i*86) 461 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_I386" 462 ;; 463 arm*) 464 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_ARM" 465 ;; 466 aarch64) 467 echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_AARCH64" 468 ;; 469 esac 470 fi 471 472 if [ ${HAVE_B64_NTOP} -eq 0 ]; then 473 echo "extern int b64_ntop(unsigned char const *, size_t, char *, size_t);"; 474 echo "extern int b64_pton(char const *, unsigned char *, size_t);" 475 fi 476 477 if [ ${HAVE_EXPLICIT_BZERO} -eq 0 ]; then 478 echo "extern void explicit_bzero(void *, size_t);" 479 fi 480 481 if [ ${HAVE_MEMMEM} -eq 0 ]; then 482 echo "void *memmem(const void *, size_t, const void *, size_t);" 483 fi 484 485 if [ ${HAVE_MEMRCHR} -eq 0 ]; then 486 echo "void *memrchr(const void *b, int, size_t);" 487 fi 488 489 if [ ${HAVE_GETPROGNAME} -eq 0 ]; then 490 echo "extern const char *getprogname(void);" 491 fi 492 493 if [ ${HAVE_READPASSPHRASE} -eq 0 ]; then 494 echo "#define RPP_ECHO_OFF 0x00" 495 echo "#define RPP_ECHO_ON 0x01" 496 echo "#define RPP_REQUIRE_TTY 0x02" 497 echo "#define RPP_FORCELOWER 0x04" 498 echo "#define RPP_FORCEUPPER 0x08" 499 echo "#define RPP_SEVENBIT 0x10" 500 echo "#define RPP_STDIN 0x20" 501 echo "char *readpassphrase(const char *, char *, size_t, int);" 502 fi 503 504 if [ ${HAVE_REALLOCARRAY} -eq 0 ]; then 505 echo "extern void *reallocarray(void *, size_t, size_t);" 506 fi 507 508 if [ ${HAVE_RECALLOCARRAY} -eq 0 ]; then 509 echo "extern void *recallocarray(void *, size_t, size_t, size_t);" 510 fi 511 512 if [ ${HAVE_STRLCAT} -eq 0 ]; then 513 echo "extern size_t strlcat(char *, const char *, size_t);" 514 fi 515 516 if [ ${HAVE_STRLCPY} -eq 0 ]; then 517 echo "extern size_t strlcpy(char *, const char *, size_t);" 518 fi 519 520 if [ ${HAVE_STRNDUP} -eq 0 ]; then 521 echo "extern char *strndup(const char *, size_t);" 522 fi 523 524 if [ ${HAVE_STRNLEN} -eq 0 ]; then 525 echo "extern size_t strnlen(const char *, size_t);" 526 fi 527 528 if [ ${HAVE_STRTONUM} -eq 0 ]; then 529 echo "extern long long strtonum(const char *, long long, long long, const char **);" 530 fi 531 532 if [ ${HAVE_SYS_QUEUE} -eq 0 ]; then 533 cat << __HEREDOC__ 534 /* \$OpenBSD$ */ 535 /* \$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp \$ */ 536 537 /* 538 * Copyright (c) 1991, 1993 539 * The Regents of the University of California. All rights reserved. 540 * 541 * Redistribution and use in source and binary forms, with or without 542 * modification, are permitted provided that the following conditions 543 * are met: 544 * 1. Redistributions of source code must retain the above copyright 545 * notice, this list of conditions and the following disclaimer. 546 * 2. Redistributions in binary form must reproduce the above copyright 547 * notice, this list of conditions and the following disclaimer in the 548 * documentation and/or other materials provided with the distribution. 549 * 3. Neither the name of the University nor the names of its contributors 550 * may be used to endorse or promote products derived from this software 551 * without specific prior written permission. 552 * 553 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 554 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 555 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 556 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 557 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 558 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 559 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 560 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 561 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 562 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 563 * SUCH DAMAGE. 564 * 565 * @(#)queue.h 8.5 (Berkeley) 8/20/94 566 */ 567 568 /* OPENBSD ORIGINAL: sys/sys/queue.h */ 569 570 /* 571 * Require for OS/X and other platforms that have old/broken/incomplete 572 * <sys/queue.h>. 573 */ 574 #undef SLIST_HEAD 575 #undef SLIST_HEAD_INITIALIZER 576 #undef SLIST_ENTRY 577 #undef SLIST_FOREACH_PREVPTR 578 #undef SLIST_FOREACH_SAFE 579 #undef SLIST_FIRST 580 #undef SLIST_END 581 #undef SLIST_EMPTY 582 #undef SLIST_NEXT 583 #undef SLIST_FOREACH 584 #undef SLIST_INIT 585 #undef SLIST_INSERT_AFTER 586 #undef SLIST_INSERT_HEAD 587 #undef SLIST_REMOVE_HEAD 588 #undef SLIST_REMOVE_AFTER 589 #undef SLIST_REMOVE 590 #undef SLIST_REMOVE_NEXT 591 #undef LIST_HEAD 592 #undef LIST_HEAD_INITIALIZER 593 #undef LIST_ENTRY 594 #undef LIST_FIRST 595 #undef LIST_END 596 #undef LIST_EMPTY 597 #undef LIST_NEXT 598 #undef LIST_FOREACH 599 #undef LIST_FOREACH_SAFE 600 #undef LIST_INIT 601 #undef LIST_INSERT_AFTER 602 #undef LIST_INSERT_BEFORE 603 #undef LIST_INSERT_HEAD 604 #undef LIST_REMOVE 605 #undef LIST_REPLACE 606 #undef SIMPLEQ_HEAD 607 #undef SIMPLEQ_HEAD_INITIALIZER 608 #undef SIMPLEQ_ENTRY 609 #undef SIMPLEQ_FIRST 610 #undef SIMPLEQ_END 611 #undef SIMPLEQ_EMPTY 612 #undef SIMPLEQ_NEXT 613 #undef SIMPLEQ_FOREACH 614 #undef SIMPLEQ_FOREACH_SAFE 615 #undef SIMPLEQ_INIT 616 #undef SIMPLEQ_INSERT_HEAD 617 #undef SIMPLEQ_INSERT_TAIL 618 #undef SIMPLEQ_INSERT_AFTER 619 #undef SIMPLEQ_REMOVE_HEAD 620 #undef TAILQ_HEAD 621 #undef TAILQ_HEAD_INITIALIZER 622 #undef TAILQ_ENTRY 623 #undef TAILQ_FIRST 624 #undef TAILQ_END 625 #undef TAILQ_NEXT 626 #undef TAILQ_LAST 627 #undef TAILQ_PREV 628 #undef TAILQ_EMPTY 629 #undef TAILQ_FOREACH 630 #undef TAILQ_FOREACH_REVERSE 631 #undef TAILQ_FOREACH_SAFE 632 #undef TAILQ_FOREACH_REVERSE_SAFE 633 #undef TAILQ_INIT 634 #undef TAILQ_INSERT_HEAD 635 #undef TAILQ_INSERT_TAIL 636 #undef TAILQ_INSERT_AFTER 637 #undef TAILQ_INSERT_BEFORE 638 #undef TAILQ_REMOVE 639 #undef TAILQ_REPLACE 640 #undef CIRCLEQ_HEAD 641 #undef CIRCLEQ_HEAD_INITIALIZER 642 #undef CIRCLEQ_ENTRY 643 #undef CIRCLEQ_FIRST 644 #undef CIRCLEQ_LAST 645 #undef CIRCLEQ_END 646 #undef CIRCLEQ_NEXT 647 #undef CIRCLEQ_PREV 648 #undef CIRCLEQ_EMPTY 649 #undef CIRCLEQ_FOREACH 650 #undef CIRCLEQ_FOREACH_REVERSE 651 #undef CIRCLEQ_INIT 652 #undef CIRCLEQ_INSERT_AFTER 653 #undef CIRCLEQ_INSERT_BEFORE 654 #undef CIRCLEQ_INSERT_HEAD 655 #undef CIRCLEQ_INSERT_TAIL 656 #undef CIRCLEQ_REMOVE 657 #undef CIRCLEQ_REPLACE 658 659 /* 660 * This file defines five types of data structures: singly-linked lists, 661 * lists, simple queues, tail queues, and circular queues. 662 * 663 * 664 * A singly-linked list is headed by a single forward pointer. The elements 665 * are singly linked for minimum space and pointer manipulation overhead at 666 * the expense of O(n) removal for arbitrary elements. New elements can be 667 * added to the list after an existing element or at the head of the list. 668 * Elements being removed from the head of the list should use the explicit 669 * macro for this purpose for optimum efficiency. A singly-linked list may 670 * only be traversed in the forward direction. Singly-linked lists are ideal 671 * for applications with large datasets and few or no removals or for 672 * implementing a LIFO queue. 673 * 674 * A list is headed by a single forward pointer (or an array of forward 675 * pointers for a hash table header). The elements are doubly linked 676 * so that an arbitrary element can be removed without a need to 677 * traverse the list. New elements can be added to the list before 678 * or after an existing element or at the head of the list. A list 679 * may only be traversed in the forward direction. 680 * 681 * A simple queue is headed by a pair of pointers, one the head of the 682 * list and the other to the tail of the list. The elements are singly 683 * linked to save space, so elements can only be removed from the 684 * head of the list. New elements can be added to the list before or after 685 * an existing element, at the head of the list, or at the end of the 686 * list. A simple queue may only be traversed in the forward direction. 687 * 688 * A tail queue is headed by a pair of pointers, one to the head of the 689 * list and the other to the tail of the list. The elements are doubly 690 * linked so that an arbitrary element can be removed without a need to 691 * traverse the list. New elements can be added to the list before or 692 * after an existing element, at the head of the list, or at the end of 693 * the list. A tail queue may be traversed in either direction. 694 * 695 * A circle queue is headed by a pair of pointers, one to the head of the 696 * list and the other to the tail of the list. The elements are doubly 697 * linked so that an arbitrary element can be removed without a need to 698 * traverse the list. New elements can be added to the list before or after 699 * an existing element, at the head of the list, or at the end of the list. 700 * A circle queue may be traversed in either direction, but has a more 701 * complex end of list detection. 702 * 703 * For details on the use of these macros, see the queue(3) manual page. 704 */ 705 706 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) 707 #define _Q_INVALIDATE(a) (a) = ((void *)-1) 708 #else 709 #define _Q_INVALIDATE(a) 710 #endif 711 712 /* 713 * Singly-linked List definitions. 714 */ 715 #define SLIST_HEAD(name, type) \\ 716 struct name { \\ 717 struct type *slh_first; /* first element */ \\ 718 } 719 720 #define SLIST_HEAD_INITIALIZER(head) \\ 721 { NULL } 722 723 #define SLIST_ENTRY(type) \\ 724 struct { \\ 725 struct type *sle_next; /* next element */ \\ 726 } 727 728 /* 729 * Singly-linked List access methods. 730 */ 731 #define SLIST_FIRST(head) ((head)->slh_first) 732 #define SLIST_END(head) NULL 733 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) 734 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 735 736 #define SLIST_FOREACH(var, head, field) \\ 737 for((var) = SLIST_FIRST(head); \\ 738 (var) != SLIST_END(head); \\ 739 (var) = SLIST_NEXT(var, field)) 740 741 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \\ 742 for ((var) = SLIST_FIRST(head); \\ 743 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \\ 744 (var) = (tvar)) 745 746 /* 747 * Singly-linked List functions. 748 */ 749 #define SLIST_INIT(head) { \\ 750 SLIST_FIRST(head) = SLIST_END(head); \\ 751 } 752 753 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \\ 754 (elm)->field.sle_next = (slistelm)->field.sle_next; \\ 755 (slistelm)->field.sle_next = (elm); \\ 756 } while (0) 757 758 #define SLIST_INSERT_HEAD(head, elm, field) do { \\ 759 (elm)->field.sle_next = (head)->slh_first; \\ 760 (head)->slh_first = (elm); \\ 761 } while (0) 762 763 #define SLIST_REMOVE_AFTER(elm, field) do { \\ 764 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \\ 765 } while (0) 766 767 #define SLIST_REMOVE_HEAD(head, field) do { \\ 768 (head)->slh_first = (head)->slh_first->field.sle_next; \\ 769 } while (0) 770 771 #define SLIST_REMOVE(head, elm, type, field) do { \\ 772 if ((head)->slh_first == (elm)) { \\ 773 SLIST_REMOVE_HEAD((head), field); \\ 774 } else { \\ 775 struct type *curelm = (head)->slh_first; \\ 776 \\ 777 while (curelm->field.sle_next != (elm)) \\ 778 curelm = curelm->field.sle_next; \\ 779 curelm->field.sle_next = \\ 780 curelm->field.sle_next->field.sle_next; \\ 781 _Q_INVALIDATE((elm)->field.sle_next); \\ 782 } \\ 783 } while (0) 784 785 /* 786 * List definitions. 787 */ 788 #define LIST_HEAD(name, type) \\ 789 struct name { \\ 790 struct type *lh_first; /* first element */ \\ 791 } 792 793 #define LIST_HEAD_INITIALIZER(head) \\ 794 { NULL } 795 796 #define LIST_ENTRY(type) \\ 797 struct { \\ 798 struct type *le_next; /* next element */ \\ 799 struct type **le_prev; /* address of previous next element */ \\ 800 } 801 802 /* 803 * List access methods 804 */ 805 #define LIST_FIRST(head) ((head)->lh_first) 806 #define LIST_END(head) NULL 807 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) 808 #define LIST_NEXT(elm, field) ((elm)->field.le_next) 809 810 #define LIST_FOREACH(var, head, field) \\ 811 for((var) = LIST_FIRST(head); \\ 812 (var)!= LIST_END(head); \\ 813 (var) = LIST_NEXT(var, field)) 814 815 #define LIST_FOREACH_SAFE(var, head, field, tvar) \\ 816 for ((var) = LIST_FIRST(head); \\ 817 (var) && ((tvar) = LIST_NEXT(var, field), 1); \\ 818 (var) = (tvar)) 819 820 /* 821 * List functions. 822 */ 823 #define LIST_INIT(head) do { \\ 824 LIST_FIRST(head) = LIST_END(head); \\ 825 } while (0) 826 827 #define LIST_INSERT_AFTER(listelm, elm, field) do { \\ 828 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \\ 829 (listelm)->field.le_next->field.le_prev = \\ 830 &(elm)->field.le_next; \\ 831 (listelm)->field.le_next = (elm); \\ 832 (elm)->field.le_prev = &(listelm)->field.le_next; \\ 833 } while (0) 834 835 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \\ 836 (elm)->field.le_prev = (listelm)->field.le_prev; \\ 837 (elm)->field.le_next = (listelm); \\ 838 *(listelm)->field.le_prev = (elm); \\ 839 (listelm)->field.le_prev = &(elm)->field.le_next; \\ 840 } while (0) 841 842 #define LIST_INSERT_HEAD(head, elm, field) do { \\ 843 if (((elm)->field.le_next = (head)->lh_first) != NULL) \\ 844 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\\ 845 (head)->lh_first = (elm); \\ 846 (elm)->field.le_prev = &(head)->lh_first; \\ 847 } while (0) 848 849 #define LIST_REMOVE(elm, field) do { \\ 850 if ((elm)->field.le_next != NULL) \\ 851 (elm)->field.le_next->field.le_prev = \\ 852 (elm)->field.le_prev; \\ 853 *(elm)->field.le_prev = (elm)->field.le_next; \\ 854 _Q_INVALIDATE((elm)->field.le_prev); \\ 855 _Q_INVALIDATE((elm)->field.le_next); \\ 856 } while (0) 857 858 #define LIST_REPLACE(elm, elm2, field) do { \\ 859 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \\ 860 (elm2)->field.le_next->field.le_prev = \\ 861 &(elm2)->field.le_next; \\ 862 (elm2)->field.le_prev = (elm)->field.le_prev; \\ 863 *(elm2)->field.le_prev = (elm2); \\ 864 _Q_INVALIDATE((elm)->field.le_prev); \\ 865 _Q_INVALIDATE((elm)->field.le_next); \\ 866 } while (0) 867 868 /* 869 * Simple queue definitions. 870 */ 871 #define SIMPLEQ_HEAD(name, type) \\ 872 struct name { \\ 873 struct type *sqh_first; /* first element */ \\ 874 struct type **sqh_last; /* addr of last next element */ \\ 875 } 876 877 #define SIMPLEQ_HEAD_INITIALIZER(head) \\ 878 { NULL, &(head).sqh_first } 879 880 #define SIMPLEQ_ENTRY(type) \\ 881 struct { \\ 882 struct type *sqe_next; /* next element */ \\ 883 } 884 885 /* 886 * Simple queue access methods. 887 */ 888 #define SIMPLEQ_FIRST(head) ((head)->sqh_first) 889 #define SIMPLEQ_END(head) NULL 890 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) 891 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 892 893 #define SIMPLEQ_FOREACH(var, head, field) \\ 894 for((var) = SIMPLEQ_FIRST(head); \\ 895 (var) != SIMPLEQ_END(head); \\ 896 (var) = SIMPLEQ_NEXT(var, field)) 897 898 #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \\ 899 for ((var) = SIMPLEQ_FIRST(head); \\ 900 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \\ 901 (var) = (tvar)) 902 903 /* 904 * Simple queue functions. 905 */ 906 #define SIMPLEQ_INIT(head) do { \\ 907 (head)->sqh_first = NULL; \\ 908 (head)->sqh_last = &(head)->sqh_first; \\ 909 } while (0) 910 911 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \\ 912 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \\ 913 (head)->sqh_last = &(elm)->field.sqe_next; \\ 914 (head)->sqh_first = (elm); \\ 915 } while (0) 916 917 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \\ 918 (elm)->field.sqe_next = NULL; \\ 919 *(head)->sqh_last = (elm); \\ 920 (head)->sqh_last = &(elm)->field.sqe_next; \\ 921 } while (0) 922 923 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\ 924 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\\ 925 (head)->sqh_last = &(elm)->field.sqe_next; \\ 926 (listelm)->field.sqe_next = (elm); \\ 927 } while (0) 928 929 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \\ 930 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \\ 931 (head)->sqh_last = &(head)->sqh_first; \\ 932 } while (0) 933 934 #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \\ 935 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \\ 936 == NULL) \\ 937 (head)->sqh_last = &(elm)->field.sqe_next; \\ 938 } while (0) 939 940 /* 941 * Tail queue definitions. 942 */ 943 #define TAILQ_HEAD(name, type) \\ 944 struct name { \\ 945 struct type *tqh_first; /* first element */ \\ 946 struct type **tqh_last; /* addr of last next element */ \\ 947 } 948 949 #define TAILQ_HEAD_INITIALIZER(head) \\ 950 { NULL, &(head).tqh_first } 951 952 #define TAILQ_ENTRY(type) \\ 953 struct { \\ 954 struct type *tqe_next; /* next element */ \\ 955 struct type **tqe_prev; /* address of previous next element */ \\ 956 } 957 958 /* 959 * tail queue access methods 960 */ 961 #define TAILQ_FIRST(head) ((head)->tqh_first) 962 #define TAILQ_END(head) NULL 963 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 964 #define TAILQ_LAST(head, headname) \\ 965 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 966 /* XXX */ 967 #define TAILQ_PREV(elm, headname, field) \\ 968 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 969 #define TAILQ_EMPTY(head) \\ 970 (TAILQ_FIRST(head) == TAILQ_END(head)) 971 972 #define TAILQ_FOREACH(var, head, field) \\ 973 for((var) = TAILQ_FIRST(head); \\ 974 (var) != TAILQ_END(head); \\ 975 (var) = TAILQ_NEXT(var, field)) 976 977 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \\ 978 for ((var) = TAILQ_FIRST(head); \\ 979 (var) != TAILQ_END(head) && \\ 980 ((tvar) = TAILQ_NEXT(var, field), 1); \\ 981 (var) = (tvar)) 982 983 984 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \\ 985 for((var) = TAILQ_LAST(head, headname); \\ 986 (var) != TAILQ_END(head); \\ 987 (var) = TAILQ_PREV(var, headname, field)) 988 989 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \\ 990 for ((var) = TAILQ_LAST(head, headname); \\ 991 (var) != TAILQ_END(head) && \\ 992 ((tvar) = TAILQ_PREV(var, headname, field), 1); \\ 993 (var) = (tvar)) 994 995 /* 996 * Tail queue functions. 997 */ 998 #define TAILQ_INIT(head) do { \\ 999 (head)->tqh_first = NULL; \\ 1000 (head)->tqh_last = &(head)->tqh_first; \\ 1001 } while (0) 1002 1003 #define TAILQ_INSERT_HEAD(head, elm, field) do { \\ 1004 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \\ 1005 (head)->tqh_first->field.tqe_prev = \\ 1006 &(elm)->field.tqe_next; \\ 1007 else \\ 1008 (head)->tqh_last = &(elm)->field.tqe_next; \\ 1009 (head)->tqh_first = (elm); \\ 1010 (elm)->field.tqe_prev = &(head)->tqh_first; \\ 1011 } while (0) 1012 1013 #define TAILQ_INSERT_TAIL(head, elm, field) do { \\ 1014 (elm)->field.tqe_next = NULL; \\ 1015 (elm)->field.tqe_prev = (head)->tqh_last; \\ 1016 *(head)->tqh_last = (elm); \\ 1017 (head)->tqh_last = &(elm)->field.tqe_next; \\ 1018 } while (0) 1019 1020 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \\ 1021 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\\ 1022 (elm)->field.tqe_next->field.tqe_prev = \\ 1023 &(elm)->field.tqe_next; \\ 1024 else \\ 1025 (head)->tqh_last = &(elm)->field.tqe_next; \\ 1026 (listelm)->field.tqe_next = (elm); \\ 1027 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \\ 1028 } while (0) 1029 1030 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \\ 1031 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \\ 1032 (elm)->field.tqe_next = (listelm); \\ 1033 *(listelm)->field.tqe_prev = (elm); \\ 1034 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \\ 1035 } while (0) 1036 1037 #define TAILQ_REMOVE(head, elm, field) do { \\ 1038 if (((elm)->field.tqe_next) != NULL) \\ 1039 (elm)->field.tqe_next->field.tqe_prev = \\ 1040 (elm)->field.tqe_prev; \\ 1041 else \\ 1042 (head)->tqh_last = (elm)->field.tqe_prev; \\ 1043 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \\ 1044 _Q_INVALIDATE((elm)->field.tqe_prev); \\ 1045 _Q_INVALIDATE((elm)->field.tqe_next); \\ 1046 } while (0) 1047 1048 #define TAILQ_REPLACE(head, elm, elm2, field) do { \\ 1049 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \\ 1050 (elm2)->field.tqe_next->field.tqe_prev = \\ 1051 &(elm2)->field.tqe_next; \\ 1052 else \\ 1053 (head)->tqh_last = &(elm2)->field.tqe_next; \\ 1054 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \\ 1055 *(elm2)->field.tqe_prev = (elm2); \\ 1056 _Q_INVALIDATE((elm)->field.tqe_prev); \\ 1057 _Q_INVALIDATE((elm)->field.tqe_next); \\ 1058 } while (0) 1059 1060 /* 1061 * Circular queue definitions. 1062 */ 1063 #define CIRCLEQ_HEAD(name, type) \\ 1064 struct name { \\ 1065 struct type *cqh_first; /* first element */ \\ 1066 struct type *cqh_last; /* last element */ \\ 1067 } 1068 1069 #define CIRCLEQ_HEAD_INITIALIZER(head) \\ 1070 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } 1071 1072 #define CIRCLEQ_ENTRY(type) \\ 1073 struct { \\ 1074 struct type *cqe_next; /* next element */ \\ 1075 struct type *cqe_prev; /* previous element */ \\ 1076 } 1077 1078 /* 1079 * Circular queue access methods 1080 */ 1081 #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 1082 #define CIRCLEQ_LAST(head) ((head)->cqh_last) 1083 #define CIRCLEQ_END(head) ((void *)(head)) 1084 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 1085 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 1086 #define CIRCLEQ_EMPTY(head) \\ 1087 (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) 1088 1089 #define CIRCLEQ_FOREACH(var, head, field) \\ 1090 for((var) = CIRCLEQ_FIRST(head); \\ 1091 (var) != CIRCLEQ_END(head); \\ 1092 (var) = CIRCLEQ_NEXT(var, field)) 1093 1094 #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \\ 1095 for ((var) = CIRCLEQ_FIRST(head); \\ 1096 (var) != CIRCLEQ_END(head) && \\ 1097 ((tvar) = CIRCLEQ_NEXT(var, field), 1); \\ 1098 (var) = (tvar)) 1099 1100 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \\ 1101 for((var) = CIRCLEQ_LAST(head); \\ 1102 (var) != CIRCLEQ_END(head); \\ 1103 (var) = CIRCLEQ_PREV(var, field)) 1104 1105 #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \\ 1106 for ((var) = CIRCLEQ_LAST(head, headname); \\ 1107 (var) != CIRCLEQ_END(head) && \\ 1108 ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \\ 1109 (var) = (tvar)) 1110 1111 /* 1112 * Circular queue functions. 1113 */ 1114 #define CIRCLEQ_INIT(head) do { \\ 1115 (head)->cqh_first = CIRCLEQ_END(head); \\ 1116 (head)->cqh_last = CIRCLEQ_END(head); \\ 1117 } while (0) 1118 1119 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\ 1120 (elm)->field.cqe_next = (listelm)->field.cqe_next; \\ 1121 (elm)->field.cqe_prev = (listelm); \\ 1122 if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \\ 1123 (head)->cqh_last = (elm); \\ 1124 else \\ 1125 (listelm)->field.cqe_next->field.cqe_prev = (elm); \\ 1126 (listelm)->field.cqe_next = (elm); \\ 1127 } while (0) 1128 1129 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \\ 1130 (elm)->field.cqe_next = (listelm); \\ 1131 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \\ 1132 if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \\ 1133 (head)->cqh_first = (elm); \\ 1134 else \\ 1135 (listelm)->field.cqe_prev->field.cqe_next = (elm); \\ 1136 (listelm)->field.cqe_prev = (elm); \\ 1137 } while (0) 1138 1139 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \\ 1140 (elm)->field.cqe_next = (head)->cqh_first; \\ 1141 (elm)->field.cqe_prev = CIRCLEQ_END(head); \\ 1142 if ((head)->cqh_last == CIRCLEQ_END(head)) \\ 1143 (head)->cqh_last = (elm); \\ 1144 else \\ 1145 (head)->cqh_first->field.cqe_prev = (elm); \\ 1146 (head)->cqh_first = (elm); \\ 1147 } while (0) 1148 1149 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \\ 1150 (elm)->field.cqe_next = CIRCLEQ_END(head); \\ 1151 (elm)->field.cqe_prev = (head)->cqh_last; \\ 1152 if ((head)->cqh_first == CIRCLEQ_END(head)) \\ 1153 (head)->cqh_first = (elm); \\ 1154 else \\ 1155 (head)->cqh_last->field.cqe_next = (elm); \\ 1156 (head)->cqh_last = (elm); \\ 1157 } while (0) 1158 1159 #define CIRCLEQ_REMOVE(head, elm, field) do { \\ 1160 if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \\ 1161 (head)->cqh_last = (elm)->field.cqe_prev; \\ 1162 else \\ 1163 (elm)->field.cqe_next->field.cqe_prev = \\ 1164 (elm)->field.cqe_prev; \\ 1165 if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \\ 1166 (head)->cqh_first = (elm)->field.cqe_next; \\ 1167 else \\ 1168 (elm)->field.cqe_prev->field.cqe_next = \\ 1169 (elm)->field.cqe_next; \\ 1170 _Q_INVALIDATE((elm)->field.cqe_prev); \\ 1171 _Q_INVALIDATE((elm)->field.cqe_next); \\ 1172 } while (0) 1173 1174 #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \\ 1175 if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \\ 1176 CIRCLEQ_END(head)) \\ 1177 (head).cqh_last = (elm2); \\ 1178 else \\ 1179 (elm2)->field.cqe_next->field.cqe_prev = (elm2); \\ 1180 if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \\ 1181 CIRCLEQ_END(head)) \\ 1182 (head).cqh_first = (elm2); \\ 1183 else \\ 1184 (elm2)->field.cqe_prev->field.cqe_next = (elm2); \\ 1185 _Q_INVALIDATE((elm)->field.cqe_prev); \\ 1186 _Q_INVALIDATE((elm)->field.cqe_next); \\ 1187 } while (0) 1188 __HEREDOC__ 1189 fi 1190 1191 if [ ${HAVE_SYS_TREE} -eq 0 ]; then 1192 cat << __HEREDOC__ 1193 /* \$OpenBSD$ */ 1194 /* 1195 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 1196 * All rights reserved. 1197 * 1198 * Redistribution and use in source and binary forms, with or without 1199 * modification, are permitted provided that the following conditions 1200 * are met: 1201 * 1. Redistributions of source code must retain the above copyright 1202 * notice, this list of conditions and the following disclaimer. 1203 * 2. Redistributions in binary form must reproduce the above copyright 1204 * notice, this list of conditions and the following disclaimer in the 1205 * documentation and/or other materials provided with the distribution. 1206 * 1207 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1208 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1209 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1210 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1211 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 1212 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1213 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1214 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1215 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 1216 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1217 */ 1218 1219 /* OPENBSD ORIGINAL: sys/sys/tree.h */ 1220 1221 /* 1222 * This file defines data structures for different types of trees: 1223 * splay trees and red-black trees. 1224 * 1225 * A splay tree is a self-organizing data structure. Every operation 1226 * on the tree causes a splay to happen. The splay moves the requested 1227 * node to the root of the tree and partly rebalances it. 1228 * 1229 * This has the benefit that request locality causes faster lookups as 1230 * the requested nodes move to the top of the tree. On the other hand, 1231 * every lookup causes memory writes. 1232 * 1233 * The Balance Theorem bounds the total access time for m operations 1234 * and n inserts on an initially empty tree as O((m + n)lg n). The 1235 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 1236 * 1237 * A red-black tree is a binary search tree with the node color as an 1238 * extra attribute. It fulfills a set of conditions: 1239 * - every search path from the root to a leaf consists of the 1240 * same number of black nodes, 1241 * - each red node (except for the root) has a black parent, 1242 * - each leaf node is black. 1243 * 1244 * Every operation on a red-black tree is bounded as O(lg n). 1245 * The maximum height of a red-black tree is 2lg (n+1). 1246 */ 1247 1248 #define SPLAY_HEAD(name, type) \\ 1249 struct name { \\ 1250 struct type *sph_root; /* root of the tree */ \\ 1251 } 1252 1253 #define SPLAY_INITIALIZER(root) \\ 1254 { NULL } 1255 1256 #define SPLAY_INIT(root) do { \\ 1257 (root)->sph_root = NULL; \\ 1258 } while (0) 1259 1260 #define SPLAY_ENTRY(type) \\ 1261 struct { \\ 1262 struct type *spe_left; /* left element */ \\ 1263 struct type *spe_right; /* right element */ \\ 1264 } 1265 1266 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 1267 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 1268 #define SPLAY_ROOT(head) (head)->sph_root 1269 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 1270 1271 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 1272 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \\ 1273 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \\ 1274 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \\ 1275 (head)->sph_root = tmp; \\ 1276 } while (0) 1277 1278 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \\ 1279 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \\ 1280 SPLAY_LEFT(tmp, field) = (head)->sph_root; \\ 1281 (head)->sph_root = tmp; \\ 1282 } while (0) 1283 1284 #define SPLAY_LINKLEFT(head, tmp, field) do { \\ 1285 SPLAY_LEFT(tmp, field) = (head)->sph_root; \\ 1286 tmp = (head)->sph_root; \\ 1287 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \\ 1288 } while (0) 1289 1290 #define SPLAY_LINKRIGHT(head, tmp, field) do { \\ 1291 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \\ 1292 tmp = (head)->sph_root; \\ 1293 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \\ 1294 } while (0) 1295 1296 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \\ 1297 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \\ 1298 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\\ 1299 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \\ 1300 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \\ 1301 } while (0) 1302 1303 /* Generates prototypes and inline functions */ 1304 1305 #define SPLAY_PROTOTYPE(name, type, field, cmp) \\ 1306 void name##_SPLAY(struct name *, struct type *); \\ 1307 void name##_SPLAY_MINMAX(struct name *, int); \\ 1308 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \\ 1309 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \\ 1310 \\ 1311 /* Finds the node with the same key as elm */ \\ 1312 static __inline struct type * \\ 1313 name##_SPLAY_FIND(struct name *head, struct type *elm) \\ 1314 { \\ 1315 if (SPLAY_EMPTY(head)) \\ 1316 return(NULL); \\ 1317 name##_SPLAY(head, elm); \\ 1318 if ((cmp)(elm, (head)->sph_root) == 0) \\ 1319 return (head->sph_root); \\ 1320 return (NULL); \\ 1321 } \\ 1322 \\ 1323 static __inline struct type * \\ 1324 name##_SPLAY_NEXT(struct name *head, struct type *elm) \\ 1325 { \\ 1326 name##_SPLAY(head, elm); \\ 1327 if (SPLAY_RIGHT(elm, field) != NULL) { \\ 1328 elm = SPLAY_RIGHT(elm, field); \\ 1329 while (SPLAY_LEFT(elm, field) != NULL) { \\ 1330 elm = SPLAY_LEFT(elm, field); \\ 1331 } \\ 1332 } else \\ 1333 elm = NULL; \\ 1334 return (elm); \\ 1335 } \\ 1336 \\ 1337 static __inline struct type * \\ 1338 name##_SPLAY_MIN_MAX(struct name *head, int val) \\ 1339 { \\ 1340 name##_SPLAY_MINMAX(head, val); \\ 1341 return (SPLAY_ROOT(head)); \\ 1342 } 1343 1344 /* Main splay operation. 1345 * Moves node close to the key of elm to top 1346 */ 1347 #define SPLAY_GENERATE(name, type, field, cmp) \\ 1348 struct type * \\ 1349 name##_SPLAY_INSERT(struct name *head, struct type *elm) \\ 1350 { \\ 1351 if (SPLAY_EMPTY(head)) { \\ 1352 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \\ 1353 } else { \\ 1354 int __comp; \\ 1355 name##_SPLAY(head, elm); \\ 1356 __comp = (cmp)(elm, (head)->sph_root); \\ 1357 if(__comp < 0) { \\ 1358 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\\ 1359 SPLAY_RIGHT(elm, field) = (head)->sph_root; \\ 1360 SPLAY_LEFT((head)->sph_root, field) = NULL; \\ 1361 } else if (__comp > 0) { \\ 1362 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\\ 1363 SPLAY_LEFT(elm, field) = (head)->sph_root; \\ 1364 SPLAY_RIGHT((head)->sph_root, field) = NULL; \\ 1365 } else \\ 1366 return ((head)->sph_root); \\ 1367 } \\ 1368 (head)->sph_root = (elm); \\ 1369 return (NULL); \\ 1370 } \\ 1371 \\ 1372 struct type * \\ 1373 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \\ 1374 { \\ 1375 struct type *__tmp; \\ 1376 if (SPLAY_EMPTY(head)) \\ 1377 return (NULL); \\ 1378 name##_SPLAY(head, elm); \\ 1379 if ((cmp)(elm, (head)->sph_root) == 0) { \\ 1380 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \\ 1381 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\\ 1382 } else { \\ 1383 __tmp = SPLAY_RIGHT((head)->sph_root, field); \\ 1384 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\\ 1385 name##_SPLAY(head, elm); \\ 1386 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \\ 1387 } \\ 1388 return (elm); \\ 1389 } \\ 1390 return (NULL); \\ 1391 } \\ 1392 \\ 1393 void \\ 1394 name##_SPLAY(struct name *head, struct type *elm) \\ 1395 { \\ 1396 struct type __node, *__left, *__right, *__tmp; \\ 1397 int __comp; \\ 1398 \\ 1399 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\\ 1400 __left = __right = &__node; \\ 1401 \\ 1402 while ((__comp = (cmp)(elm, (head)->sph_root))) { \\ 1403 if (__comp < 0) { \\ 1404 __tmp = SPLAY_LEFT((head)->sph_root, field); \\ 1405 if (__tmp == NULL) \\ 1406 break; \\ 1407 if ((cmp)(elm, __tmp) < 0){ \\ 1408 SPLAY_ROTATE_RIGHT(head, __tmp, field); \\ 1409 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\\ 1410 break; \\ 1411 } \\ 1412 SPLAY_LINKLEFT(head, __right, field); \\ 1413 } else if (__comp > 0) { \\ 1414 __tmp = SPLAY_RIGHT((head)->sph_root, field); \\ 1415 if (__tmp == NULL) \\ 1416 break; \\ 1417 if ((cmp)(elm, __tmp) > 0){ \\ 1418 SPLAY_ROTATE_LEFT(head, __tmp, field); \\ 1419 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\\ 1420 break; \\ 1421 } \\ 1422 SPLAY_LINKRIGHT(head, __left, field); \\ 1423 } \\ 1424 } \\ 1425 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \\ 1426 } \\ 1427 \\ 1428 /* Splay with either the minimum or the maximum element \\ 1429 * Used to find minimum or maximum element in tree. \\ 1430 */ \\ 1431 void name##_SPLAY_MINMAX(struct name *head, int __comp) \\ 1432 { \\ 1433 struct type __node, *__left, *__right, *__tmp; \\ 1434 \\ 1435 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\\ 1436 __left = __right = &__node; \\ 1437 \\ 1438 while (1) { \\ 1439 if (__comp < 0) { \\ 1440 __tmp = SPLAY_LEFT((head)->sph_root, field); \\ 1441 if (__tmp == NULL) \\ 1442 break; \\ 1443 if (__comp < 0){ \\ 1444 SPLAY_ROTATE_RIGHT(head, __tmp, field); \\ 1445 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\\ 1446 break; \\ 1447 } \\ 1448 SPLAY_LINKLEFT(head, __right, field); \\ 1449 } else if (__comp > 0) { \\ 1450 __tmp = SPLAY_RIGHT((head)->sph_root, field); \\ 1451 if (__tmp == NULL) \\ 1452 break; \\ 1453 if (__comp > 0) { \\ 1454 SPLAY_ROTATE_LEFT(head, __tmp, field); \\ 1455 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\\ 1456 break; \\ 1457 } \\ 1458 SPLAY_LINKRIGHT(head, __left, field); \\ 1459 } \\ 1460 } \\ 1461 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \\ 1462 } 1463 1464 #define SPLAY_NEGINF -1 1465 #define SPLAY_INF 1 1466 1467 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 1468 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 1469 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 1470 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 1471 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \\ 1472 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 1473 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \\ 1474 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 1475 1476 #define SPLAY_FOREACH(x, name, head) \\ 1477 for ((x) = SPLAY_MIN(name, head); \\ 1478 (x) != NULL; \\ 1479 (x) = SPLAY_NEXT(name, head, x)) 1480 1481 /* Macros that define a red-black tree */ 1482 #define RB_HEAD(name, type) \\ 1483 struct name { \\ 1484 struct type *rbh_root; /* root of the tree */ \\ 1485 } 1486 1487 #define RB_INITIALIZER(root) \\ 1488 { NULL } 1489 1490 #define RB_INIT(root) do { \\ 1491 (root)->rbh_root = NULL; \\ 1492 } while (0) 1493 1494 #define RB_BLACK 0 1495 #define RB_RED 1 1496 #define RB_ENTRY(type) \\ 1497 struct { \\ 1498 struct type *rbe_left; /* left element */ \\ 1499 struct type *rbe_right; /* right element */ \\ 1500 struct type *rbe_parent; /* parent element */ \\ 1501 int rbe_color; /* node color */ \\ 1502 } 1503 1504 #define RB_LEFT(elm, field) (elm)->field.rbe_left 1505 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 1506 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 1507 #define RB_COLOR(elm, field) (elm)->field.rbe_color 1508 #define RB_ROOT(head) (head)->rbh_root 1509 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 1510 1511 #define RB_SET(elm, parent, field) do { \\ 1512 RB_PARENT(elm, field) = parent; \\ 1513 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \\ 1514 RB_COLOR(elm, field) = RB_RED; \\ 1515 } while (0) 1516 1517 #define RB_SET_BLACKRED(black, red, field) do { \\ 1518 RB_COLOR(black, field) = RB_BLACK; \\ 1519 RB_COLOR(red, field) = RB_RED; \\ 1520 } while (0) 1521 1522 #ifndef RB_AUGMENT 1523 #define RB_AUGMENT(x) do {} while (0) 1524 #endif 1525 1526 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \\ 1527 (tmp) = RB_RIGHT(elm, field); \\ 1528 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \\ 1529 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \\ 1530 } \\ 1531 RB_AUGMENT(elm); \\ 1532 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \\ 1533 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \\ 1534 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \\ 1535 else \\ 1536 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \\ 1537 } else \\ 1538 (head)->rbh_root = (tmp); \\ 1539 RB_LEFT(tmp, field) = (elm); \\ 1540 RB_PARENT(elm, field) = (tmp); \\ 1541 RB_AUGMENT(tmp); \\ 1542 if ((RB_PARENT(tmp, field))) \\ 1543 RB_AUGMENT(RB_PARENT(tmp, field)); \\ 1544 } while (0) 1545 1546 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \\ 1547 (tmp) = RB_LEFT(elm, field); \\ 1548 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \\ 1549 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \\ 1550 } \\ 1551 RB_AUGMENT(elm); \\ 1552 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \\ 1553 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \\ 1554 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \\ 1555 else \\ 1556 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \\ 1557 } else \\ 1558 (head)->rbh_root = (tmp); \\ 1559 RB_RIGHT(tmp, field) = (elm); \\ 1560 RB_PARENT(elm, field) = (tmp); \\ 1561 RB_AUGMENT(tmp); \\ 1562 if ((RB_PARENT(tmp, field))) \\ 1563 RB_AUGMENT(RB_PARENT(tmp, field)); \\ 1564 } while (0) 1565 1566 /* Generates prototypes and inline functions */ 1567 #define RB_PROTOTYPE(name, type, field, cmp) \\ 1568 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 1569 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \\ 1570 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 1571 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \\ 1572 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \\ 1573 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\\ 1574 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \\ 1575 attr struct type *name##_RB_INSERT(struct name *, struct type *); \\ 1576 attr struct type *name##_RB_FIND(struct name *, struct type *); \\ 1577 attr struct type *name##_RB_NFIND(struct name *, struct type *); \\ 1578 attr struct type *name##_RB_NEXT(struct type *); \\ 1579 attr struct type *name##_RB_PREV(struct type *); \\ 1580 attr struct type *name##_RB_MINMAX(struct name *, int); \\ 1581 \\ 1582 1583 /* Main rb operation. 1584 * Moves node close to the key of elm to top 1585 */ 1586 #define RB_GENERATE(name, type, field, cmp) \\ 1587 RB_GENERATE_INTERNAL(name, type, field, cmp,) 1588 #define RB_GENERATE_STATIC(name, type, field, cmp) \\ 1589 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 1590 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \\ 1591 attr void \\ 1592 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \\ 1593 { \\ 1594 struct type *parent, *gparent, *tmp; \\ 1595 while ((parent = RB_PARENT(elm, field)) && \\ 1596 RB_COLOR(parent, field) == RB_RED) { \\ 1597 gparent = RB_PARENT(parent, field); \\ 1598 if (parent == RB_LEFT(gparent, field)) { \\ 1599 tmp = RB_RIGHT(gparent, field); \\ 1600 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \\ 1601 RB_COLOR(tmp, field) = RB_BLACK; \\ 1602 RB_SET_BLACKRED(parent, gparent, field);\\ 1603 elm = gparent; \\ 1604 continue; \\ 1605 } \\ 1606 if (RB_RIGHT(parent, field) == elm) { \\ 1607 RB_ROTATE_LEFT(head, parent, tmp, field);\\ 1608 tmp = parent; \\ 1609 parent = elm; \\ 1610 elm = tmp; \\ 1611 } \\ 1612 RB_SET_BLACKRED(parent, gparent, field); \\ 1613 RB_ROTATE_RIGHT(head, gparent, tmp, field); \\ 1614 } else { \\ 1615 tmp = RB_LEFT(gparent, field); \\ 1616 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \\ 1617 RB_COLOR(tmp, field) = RB_BLACK; \\ 1618 RB_SET_BLACKRED(parent, gparent, field);\\ 1619 elm = gparent; \\ 1620 continue; \\ 1621 } \\ 1622 if (RB_LEFT(parent, field) == elm) { \\ 1623 RB_ROTATE_RIGHT(head, parent, tmp, field);\\ 1624 tmp = parent; \\ 1625 parent = elm; \\ 1626 elm = tmp; \\ 1627 } \\ 1628 RB_SET_BLACKRED(parent, gparent, field); \\ 1629 RB_ROTATE_LEFT(head, gparent, tmp, field); \\ 1630 } \\ 1631 } \\ 1632 RB_COLOR(head->rbh_root, field) = RB_BLACK; \\ 1633 } \\ 1634 \\ 1635 attr void \\ 1636 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \\ 1637 { \\ 1638 struct type *tmp; \\ 1639 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \\ 1640 elm != RB_ROOT(head)) { \\ 1641 if (RB_LEFT(parent, field) == elm) { \\ 1642 tmp = RB_RIGHT(parent, field); \\ 1643 if (RB_COLOR(tmp, field) == RB_RED) { \\ 1644 RB_SET_BLACKRED(tmp, parent, field); \\ 1645 RB_ROTATE_LEFT(head, parent, tmp, field);\\ 1646 tmp = RB_RIGHT(parent, field); \\ 1647 } \\ 1648 if ((RB_LEFT(tmp, field) == NULL || \\ 1649 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\\ 1650 (RB_RIGHT(tmp, field) == NULL || \\ 1651 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\\ 1652 RB_COLOR(tmp, field) = RB_RED; \\ 1653 elm = parent; \\ 1654 parent = RB_PARENT(elm, field); \\ 1655 } else { \\ 1656 if (RB_RIGHT(tmp, field) == NULL || \\ 1657 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\\ 1658 struct type *oleft; \\ 1659 if ((oleft = RB_LEFT(tmp, field)))\\ 1660 RB_COLOR(oleft, field) = RB_BLACK;\\ 1661 RB_COLOR(tmp, field) = RB_RED; \\ 1662 RB_ROTATE_RIGHT(head, tmp, oleft, field);\\ 1663 tmp = RB_RIGHT(parent, field); \\ 1664 } \\ 1665 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\\ 1666 RB_COLOR(parent, field) = RB_BLACK; \\ 1667 if (RB_RIGHT(tmp, field)) \\ 1668 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\\ 1669 RB_ROTATE_LEFT(head, parent, tmp, field);\\ 1670 elm = RB_ROOT(head); \\ 1671 break; \\ 1672 } \\ 1673 } else { \\ 1674 tmp = RB_LEFT(parent, field); \\ 1675 if (RB_COLOR(tmp, field) == RB_RED) { \\ 1676 RB_SET_BLACKRED(tmp, parent, field); \\ 1677 RB_ROTATE_RIGHT(head, parent, tmp, field);\\ 1678 tmp = RB_LEFT(parent, field); \\ 1679 } \\ 1680 if ((RB_LEFT(tmp, field) == NULL || \\ 1681 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\\ 1682 (RB_RIGHT(tmp, field) == NULL || \\ 1683 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\\ 1684 RB_COLOR(tmp, field) = RB_RED; \\ 1685 elm = parent; \\ 1686 parent = RB_PARENT(elm, field); \\ 1687 } else { \\ 1688 if (RB_LEFT(tmp, field) == NULL || \\ 1689 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\\ 1690 struct type *oright; \\ 1691 if ((oright = RB_RIGHT(tmp, field)))\\ 1692 RB_COLOR(oright, field) = RB_BLACK;\\ 1693 RB_COLOR(tmp, field) = RB_RED; \\ 1694 RB_ROTATE_LEFT(head, tmp, oright, field);\\ 1695 tmp = RB_LEFT(parent, field); \\ 1696 } \\ 1697 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\\ 1698 RB_COLOR(parent, field) = RB_BLACK; \\ 1699 if (RB_LEFT(tmp, field)) \\ 1700 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\\ 1701 RB_ROTATE_RIGHT(head, parent, tmp, field);\\ 1702 elm = RB_ROOT(head); \\ 1703 break; \\ 1704 } \\ 1705 } \\ 1706 } \\ 1707 if (elm) \\ 1708 RB_COLOR(elm, field) = RB_BLACK; \\ 1709 } \\ 1710 \\ 1711 attr struct type * \\ 1712 name##_RB_REMOVE(struct name *head, struct type *elm) \\ 1713 { \\ 1714 struct type *child, *parent, *old = elm; \\ 1715 int color; \\ 1716 if (RB_LEFT(elm, field) == NULL) \\ 1717 child = RB_RIGHT(elm, field); \\ 1718 else if (RB_RIGHT(elm, field) == NULL) \\ 1719 child = RB_LEFT(elm, field); \\ 1720 else { \\ 1721 struct type *left; \\ 1722 elm = RB_RIGHT(elm, field); \\ 1723 while ((left = RB_LEFT(elm, field))) \\ 1724 elm = left; \\ 1725 child = RB_RIGHT(elm, field); \\ 1726 parent = RB_PARENT(elm, field); \\ 1727 color = RB_COLOR(elm, field); \\ 1728 if (child) \\ 1729 RB_PARENT(child, field) = parent; \\ 1730 if (parent) { \\ 1731 if (RB_LEFT(parent, field) == elm) \\ 1732 RB_LEFT(parent, field) = child; \\ 1733 else \\ 1734 RB_RIGHT(parent, field) = child; \\ 1735 RB_AUGMENT(parent); \\ 1736 } else \\ 1737 RB_ROOT(head) = child; \\ 1738 if (RB_PARENT(elm, field) == old) \\ 1739 parent = elm; \\ 1740 (elm)->field = (old)->field; \\ 1741 if (RB_PARENT(old, field)) { \\ 1742 if (RB_LEFT(RB_PARENT(old, field), field) == old)\\ 1743 RB_LEFT(RB_PARENT(old, field), field) = elm;\\ 1744 else \\ 1745 RB_RIGHT(RB_PARENT(old, field), field) = elm;\\ 1746 RB_AUGMENT(RB_PARENT(old, field)); \\ 1747 } else \\ 1748 RB_ROOT(head) = elm; \\ 1749 RB_PARENT(RB_LEFT(old, field), field) = elm; \\ 1750 if (RB_RIGHT(old, field)) \\ 1751 RB_PARENT(RB_RIGHT(old, field), field) = elm; \\ 1752 if (parent) { \\ 1753 left = parent; \\ 1754 do { \\ 1755 RB_AUGMENT(left); \\ 1756 } while ((left = RB_PARENT(left, field))); \\ 1757 } \\ 1758 goto color; \\ 1759 } \\ 1760 parent = RB_PARENT(elm, field); \\ 1761 color = RB_COLOR(elm, field); \\ 1762 if (child) \\ 1763 RB_PARENT(child, field) = parent; \\ 1764 if (parent) { \\ 1765 if (RB_LEFT(parent, field) == elm) \\ 1766 RB_LEFT(parent, field) = child; \\ 1767 else \\ 1768 RB_RIGHT(parent, field) = child; \\ 1769 RB_AUGMENT(parent); \\ 1770 } else \\ 1771 RB_ROOT(head) = child; \\ 1772 color: \\ 1773 if (color == RB_BLACK) \\ 1774 name##_RB_REMOVE_COLOR(head, parent, child); \\ 1775 return (old); \\ 1776 } \\ 1777 \\ 1778 /* Inserts a node into the RB tree */ \\ 1779 attr struct type * \\ 1780 name##_RB_INSERT(struct name *head, struct type *elm) \\ 1781 { \\ 1782 struct type *tmp; \\ 1783 struct type *parent = NULL; \\ 1784 int comp = 0; \\ 1785 tmp = RB_ROOT(head); \\ 1786 while (tmp) { \\ 1787 parent = tmp; \\ 1788 comp = (cmp)(elm, parent); \\ 1789 if (comp < 0) \\ 1790 tmp = RB_LEFT(tmp, field); \\ 1791 else if (comp > 0) \\ 1792 tmp = RB_RIGHT(tmp, field); \\ 1793 else \\ 1794 return (tmp); \\ 1795 } \\ 1796 RB_SET(elm, parent, field); \\ 1797 if (parent != NULL) { \\ 1798 if (comp < 0) \\ 1799 RB_LEFT(parent, field) = elm; \\ 1800 else \\ 1801 RB_RIGHT(parent, field) = elm; \\ 1802 RB_AUGMENT(parent); \\ 1803 } else \\ 1804 RB_ROOT(head) = elm; \\ 1805 name##_RB_INSERT_COLOR(head, elm); \\ 1806 return (NULL); \\ 1807 } \\ 1808 \\ 1809 /* Finds the node with the same key as elm */ \\ 1810 attr struct type * \\ 1811 name##_RB_FIND(struct name *head, struct type *elm) \\ 1812 { \\ 1813 struct type *tmp = RB_ROOT(head); \\ 1814 int comp; \\ 1815 while (tmp) { \\ 1816 comp = cmp(elm, tmp); \\ 1817 if (comp < 0) \\ 1818 tmp = RB_LEFT(tmp, field); \\ 1819 else if (comp > 0) \\ 1820 tmp = RB_RIGHT(tmp, field); \\ 1821 else \\ 1822 return (tmp); \\ 1823 } \\ 1824 return (NULL); \\ 1825 } \\ 1826 \\ 1827 /* Finds the first node greater than or equal to the search key */ \\ 1828 attr struct type * \\ 1829 name##_RB_NFIND(struct name *head, struct type *elm) \\ 1830 { \\ 1831 struct type *tmp = RB_ROOT(head); \\ 1832 struct type *res = NULL; \\ 1833 int comp; \\ 1834 while (tmp) { \\ 1835 comp = cmp(elm, tmp); \\ 1836 if (comp < 0) { \\ 1837 res = tmp; \\ 1838 tmp = RB_LEFT(tmp, field); \\ 1839 } \\ 1840 else if (comp > 0) \\ 1841 tmp = RB_RIGHT(tmp, field); \\ 1842 else \\ 1843 return (tmp); \\ 1844 } \\ 1845 return (res); \\ 1846 } \\ 1847 \\ 1848 /* ARGSUSED */ \\ 1849 attr struct type * \\ 1850 name##_RB_NEXT(struct type *elm) \\ 1851 { \\ 1852 if (RB_RIGHT(elm, field)) { \\ 1853 elm = RB_RIGHT(elm, field); \\ 1854 while (RB_LEFT(elm, field)) \\ 1855 elm = RB_LEFT(elm, field); \\ 1856 } else { \\ 1857 if (RB_PARENT(elm, field) && \\ 1858 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \\ 1859 elm = RB_PARENT(elm, field); \\ 1860 else { \\ 1861 while (RB_PARENT(elm, field) && \\ 1862 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\\ 1863 elm = RB_PARENT(elm, field); \\ 1864 elm = RB_PARENT(elm, field); \\ 1865 } \\ 1866 } \\ 1867 return (elm); \\ 1868 } \\ 1869 \\ 1870 /* ARGSUSED */ \\ 1871 attr struct type * \\ 1872 name##_RB_PREV(struct type *elm) \\ 1873 { \\ 1874 if (RB_LEFT(elm, field)) { \\ 1875 elm = RB_LEFT(elm, field); \\ 1876 while (RB_RIGHT(elm, field)) \\ 1877 elm = RB_RIGHT(elm, field); \\ 1878 } else { \\ 1879 if (RB_PARENT(elm, field) && \\ 1880 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \\ 1881 elm = RB_PARENT(elm, field); \\ 1882 else { \\ 1883 while (RB_PARENT(elm, field) && \\ 1884 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\\ 1885 elm = RB_PARENT(elm, field); \\ 1886 elm = RB_PARENT(elm, field); \\ 1887 } \\ 1888 } \\ 1889 return (elm); \\ 1890 } \\ 1891 \\ 1892 attr struct type * \\ 1893 name##_RB_MINMAX(struct name *head, int val) \\ 1894 { \\ 1895 struct type *tmp = RB_ROOT(head); \\ 1896 struct type *parent = NULL; \\ 1897 while (tmp) { \\ 1898 parent = tmp; \\ 1899 if (val < 0) \\ 1900 tmp = RB_LEFT(tmp, field); \\ 1901 else \\ 1902 tmp = RB_RIGHT(tmp, field); \\ 1903 } \\ 1904 return (parent); \\ 1905 } 1906 1907 #define RB_NEGINF -1 1908 #define RB_INF 1 1909 1910 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 1911 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 1912 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 1913 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 1914 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 1915 #define RB_PREV(name, x, y) name##_RB_PREV(y) 1916 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 1917 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 1918 1919 #define RB_FOREACH(x, name, head) \\ 1920 for ((x) = RB_MIN(name, head); \\ 1921 (x) != NULL; \\ 1922 (x) = name##_RB_NEXT(x)) 1923 1924 #define RB_FOREACH_SAFE(x, name, head, y) \\ 1925 for ((x) = RB_MIN(name, head); \\ 1926 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \\ 1927 (x) = (y)) 1928 1929 #define RB_FOREACH_REVERSE(x, name, head) \\ 1930 for ((x) = RB_MAX(name, head); \\ 1931 (x) != NULL; \\ 1932 (x) = name##_RB_PREV(x)) 1933 1934 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \\ 1935 for ((x) = RB_MAX(name, head); \\ 1936 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \\ 1937 (x) = (y)) 1938 __HEREDOC__ 1939 fi 1940 1941 cat << __HEREDOC__ 1942 #endif /*!OCONFIGURE_CONFIG_H*/ 1943 __HEREDOC__ 1944 1945 echo "config.h: written" 1>&2 1946 echo "config.h: written" 1>&3 1947 1948 #---------------------------------------------------------------------- 1949 # Now we go to generate our Makefile.configure. 1950 # This file is simply a bunch of Makefile variables. 1951 # They'll work in both GNUmakefile and BSDmakefile. 1952 # You MIGHT want to change this. 1953 #---------------------------------------------------------------------- 1954 1955 exec > Makefile.configure 1956 1957 [ -z "${BINDIR}" ] && BINDIR="${PREFIX}/bin" 1958 [ -z "${SBINDIR}" ] && SBINDIR="${PREFIX}/sbin" 1959 [ -z "${INCLUDEDIR}" ] && INCLUDEDIR="${PREFIX}/include" 1960 [ -z "${LIBDIR}" ] && LIBDIR="${PREFIX}/lib" 1961 [ -z "${MANDIR}" ] && MANDIR="${PREFIX}/man" 1962 [ -z "${SHAREDIR}" ] && SHAREDIR="${PREFIX}/share" 1963 1964 [ -z "${INSTALL_PROGRAM}" ] && INSTALL_PROGRAM="${INSTALL} -m 0555" 1965 [ -z "${INSTALL_LIB}" ] && INSTALL_LIB="${INSTALL} -m 0444" 1966 [ -z "${INSTALL_MAN}" ] && INSTALL_MAN="${INSTALL} -m 0444" 1967 [ -z "${INSTALL_DATA}" ] && INSTALL_DATA="${INSTALL} -m 0444" 1968 1969 cat << __HEREDOC__ 1970 CC = ${CC} 1971 CFLAGS = ${CFLAGS} 1972 CPPFLAGS = ${CPPFLAGS} 1973 LDADD = ${LDADD} 1974 LDFLAGS = ${LDFLAGS} 1975 STATIC = ${STATIC} 1976 PREFIX = ${PREFIX} 1977 BINDIR = ${BINDIR} 1978 SHAREDIR = ${SHAREDIR} 1979 SBINDIR = ${SBINDIR} 1980 INCLUDEDIR = ${INCLUDEDIR} 1981 LIBDIR = ${LIBDIR} 1982 MANDIR = ${MANDIR} 1983 INSTALL = ${INSTALL} 1984 INSTALL_PROGRAM = ${INSTALL_PROGRAM} 1985 INSTALL_LIB = ${INSTALL_LIB} 1986 INSTALL_MAN = ${INSTALL_MAN} 1987 INSTALL_DATA = ${INSTALL_DATA} 1988 __HEREDOC__ 1989 1990 echo "Makefile.configure: written" 1>&2 1991 echo "Makefile.configure: written" 1>&3 1992 1993 exit 0