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