commit a81bb85acb3a8d030132e5e229f582260be75a37 from: Martijn van Duren date: Thu Feb 19 16:25:19 2026 UTC Add autoconf portability goob commit - 79ef769fe9b996ba9e1c27eaa688876757e101dc commit + a81bb85acb3a8d030132e5e229f582260be75a37 blob - /dev/null blob + 8a4b2a25854b21549c1f70c8a7adff3f3f34ab95 (mode 644) --- /dev/null +++ .gitignore @@ -0,0 +1,19 @@ +aclocal.m4 +autom4te.cache +**/GNUmakefile.in +**/GNUmakefile +**/Makefile.in +compat/Makefile +compat/libasr/Makefile +compat/libasr/libasr.la +configure +configure~ +config.h* +config.log +config.status +etc/* +**/*.o +**/*.Po +**/.dirstamp +filter-dkimverify +stamp-h1 blob - d67f26cb5a48875ee95b2b25245c60656d3cba7c (mode 644) blob + /dev/null --- Makefile.gnu +++ /dev/null @@ -1,58 +0,0 @@ -LOCALBASE?= /usr/local/ - -PROG= filter-admdscrub -MAN= filter-admdscrub.8 -BINDIR= ${LOCALBASE}/libexec/opensmtpd/ -MANDIR= ${LOCALBASE}/share/man/man8 - -BINOWN?= root -BINGRP?= root -BINPERM?= 755 - -SRCS+= main.c mheader.c - -CFLAGS+=-I${LOCALBASE}/include -CFLAGS+=-Wall -I${.CURDIR} -CFLAGS+=-Wstrict-prototypes -Wmissing-prototypes -CFLAGS+=-Wmissing-declarations -CFLAGS+=-Wshadow -Wpointer-arith -Wcast-qual -CFLAGS+=-Wsign-compare -CFLAGS+=-I${CURDIR} -I${CURDIR}/openbsd-compat/ - -LDFLAGS+=-L${LOCALBASE}/lib -LDLIBS+=-levent -lopensmtpd - -INSTALL?= install - -NEED_STRLCAT?= 1 -NEED_PLEDGE?= 1 - -.PHONY: all -all: ${PROG} - -ifeq (${NEED_STRLCAT}, 1) -SRCS+= ${CURDIR}/openbsd-compat/strlcat.c -CFLAGS+= -DNEED_STRLCAT=1 - -strlcat.o: ${CURDIR}/openbsd-compat/strlcat.c - ${CC} ${CFLAGS} -c -o strlcat.o ${CURDIR}/openbsd-compat/strlcat.c -endif -ifeq (${NEED_PLEDGE}, 1) -CFLAGS+= -DNEED_PLEDGE=1 -endif - -${SRCS:.c=.d}:%.d:%.c - ${CC} ${CFLAGS} -MM $< >$@ - -OBJS= ${notdir ${SRCS:.c=.o}} - -${PROG}: ${OBJS} - ${CC} ${LDFLAGS} -o $@ $^ ${LDLIBS} - -.PHONY: clean -clean: - rm -f *.d *.o ${PROG} - -.PHONY: install -install: ${PROG} - ${INSTALL} -o ${BINOWN} -g ${BINGRP} -m ${BINPERM} ${PROG} ${BINDIR} blob - /dev/null blob + 2f45530a92fea9e93b99a28354bfcddb58a88ee3 (mode 644) --- /dev/null +++ GNUmakefile.am @@ -0,0 +1,8 @@ +smtpd_libexecdir = $(libexecsmtpddir) +smtpd_libexec_PROGRAMS = filter-admdscrub + +filter_admdscrub_SOURCES = main.c mheader.c compat.h + +LDADD = $(LIBOBJS) + +dist_man8_MANS = filter-admdscrub.8 blob - 9341020157c935717ea17bb4a8f7fee78fc277db blob + 085c0e8b6d2570327fefc1df0e04a9d99b87ced4 --- main.c +++ main.c @@ -22,7 +22,7 @@ #include #include -#include "openbsd-compat.h" +#include "compat.h" #include "opensmtpd.h" #include "mheader.h" blob - /dev/null blob + 70027cbf3cf809c67ca8b5cff38df304aa29bcf6 (mode 755) --- /dev/null +++ bootstrap @@ -0,0 +1,3 @@ +#!/bin/sh + +exec autoreconf -vfi blob - /dev/null blob + c71918cbb42013c6235d5b9e7086c1e4e527eaad (mode 644) --- /dev/null +++ compat/fgetln.c @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2015 Joerg Jung + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * portable fgetln() version, NOT reentrant + */ + +#include +#include +#include + +#include "compat.h" + +char * +fgetln(FILE *fp, size_t *len) +{ + static char *buf = NULL; + static size_t bufsz = 0; + size_t r = 0; + char *p; + int c, e; + + if (!fp || !len) { + errno = EINVAL; + return NULL; + } + if (!buf) { + if (!(buf = calloc(1, BUFSIZ))) + return NULL; + bufsz = BUFSIZ; + } + while ((c = getc(fp)) != EOF) { + buf[r++] = c; + if (r == bufsz) { + if (!(p = reallocarray(buf, 2, bufsz))) { + e = errno; + free(buf); + errno = e; + buf = NULL, bufsz = 0; + return NULL; + } + buf = p, bufsz = 2 * bufsz; + } + if (c == '\n') + break; + } + return (*len = r) ? buf : NULL; +} blob - /dev/null blob + a12eb220f52fd230cbbec83e2892133a6dcbeaeb (mode 644) --- /dev/null +++ compat/reallocarray.c @@ -0,0 +1,40 @@ +/* $OpenBSD: reallocarray.c,v 1.3 2015/09/13 08:31:47 guenther Exp $ */ +/* + * Copyright (c) 2008 Otto Moerbeek + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "compat.h" + +#include +#include +#include +#include + +/* + * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX + * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW + */ +#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4)) + +void * +reallocarray(void *optr, size_t nmemb, size_t size) +{ + if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && + nmemb > 0 && SIZE_MAX / nmemb < size) { + errno = ENOMEM; + return NULL; + } + return realloc(optr, size * nmemb); +} blob - /dev/null blob + d227d0e849aaa3a3bf1de6a7d8de7ac3489f6ee4 (mode 644) --- /dev/null +++ compat/recallocarray.c @@ -0,0 +1,90 @@ +/* $OpenBSD: recallocarray.c,v 1.2 2021/03/18 11:16:58 claudio Exp $ */ +/* + * Copyright (c) 2008, 2017 Otto Moerbeek + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "compat.h" + +#include +#include +#include +#include +#include + +/* + * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX + * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW + */ +#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4)) + +/* + * Even though specified in POSIX, the PAGESIZE and PAGE_SIZE + * macros have very poor portability. Since we only use this + * to avoid free() overhead for small shrinking, simply pick + * an arbitrary number. + */ +#define getpagesize() (1UL << 12) + +void * +recallocarray(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size) +{ + size_t oldsize, newsize; + void *newptr; + + if (ptr == NULL) + return calloc(newnmemb, size); + + if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && + newnmemb > 0 && SIZE_MAX / newnmemb < size) { + errno = ENOMEM; + return NULL; + } + newsize = newnmemb * size; + + if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && + oldnmemb > 0 && SIZE_MAX / oldnmemb < size) { + errno = EINVAL; + return NULL; + } + oldsize = oldnmemb * size; + + /* + * Don't bother too much if we're shrinking just a bit, + * we do not shrink for series of small steps, oh well. + */ + if (newsize <= oldsize) { + size_t d = oldsize - newsize; + + if (d < oldsize / 2 && d < (size_t)getpagesize()) { + memset((char *)ptr + newsize, 0, d); + return ptr; + } + } + + newptr = malloc(newsize); + if (newptr == NULL) + return NULL; + + if (newsize > oldsize) { + memcpy(newptr, ptr, oldsize); + memset((char *)newptr + oldsize, 0, newsize - oldsize); + } else + memcpy(newptr, ptr, newsize); + + explicit_bzero(ptr, oldsize); + free(ptr); + + return newptr; +} blob - /dev/null blob + 047a11314fd504b1a417ecf0593654866498e382 (mode 644) --- /dev/null +++ compat/strcasestr.c @@ -0,0 +1,60 @@ +/* $OpenBSD: strcasestr.c,v 1.4 2015/08/31 02:53:57 guenther Exp $ */ +/* $NetBSD: strcasestr.c,v 1.2 2005/02/09 21:35:47 kleink Exp $ */ + +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include +#include + +/* + * Find the first occurrence of find in s, ignore case. + */ +char * +strcasestr(const char *s, const char *find) +{ + char c, sc; + size_t len; + + if ((c = *find++) != 0) { + c = (char)tolower((unsigned char)c); + len = strlen(find); + do { + do { + if ((sc = *s++) == 0) + return (NULL); + } while ((char)tolower((unsigned char)sc) != c); + } while (strncasecmp(s, find, len) != 0); + s--; + } + return ((char *)s); +} blob - /dev/null blob + c8ef4467047133812140534353112d6a15ee06e9 (mode 644) --- /dev/null +++ compat/strtonum.c @@ -0,0 +1,67 @@ +/* $OpenBSD: strtonum.c,v 1.8 2015/09/13 08:31:48 guenther Exp $ */ + +/* + * Copyright (c) 2004 Ted Unangst and Todd Miller + * All rights reserved. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include +#include + +#include "compat.h" + +#define INVALID 1 +#define TOOSMALL 2 +#define TOOLARGE 3 + +long long +strtonum(const char *numstr, long long minval, long long maxval, + const char **errstrp) +{ + long long ll = 0; + int error = 0; + char *ep; + struct errval { + const char *errstr; + int err; + } ev[4] = { + { NULL, 0 }, + { "invalid", EINVAL }, + { "too small", ERANGE }, + { "too large", ERANGE }, + }; + + ev[0].err = errno; + errno = 0; + if (minval > maxval) { + error = INVALID; + } else { + ll = strtoll(numstr, &ep, 10); + if (numstr == ep || *ep != '\0') + error = INVALID; + else if ((ll == LLONG_MIN && errno == ERANGE) || ll < minval) + error = TOOSMALL; + else if ((ll == LLONG_MAX && errno == ERANGE) || ll > maxval) + error = TOOLARGE; + } + if (errstrp != NULL) + *errstrp = ev[error].errstr; + errno = ev[error].err; + if (error) + ll = 0; + + return (ll); +} blob - /dev/null blob + 2b93c79b074fa1f16d4c62751600ee2dd9b016b7 (mode 644) --- /dev/null +++ compat.h @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2025 Omar Polo + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "config.h" +#include + +#ifndef timespecsub +#define timespecsub(a, b, result) \ + do { \ + (result)->tv_sec = (a)->tv_sec - (b)->tv_sec; \ + (result)->tv_nsec = (a)->tv_nsec - (b)->tv_nsec; \ + if ((result)->tv_nsec < 0) { \ + --(result)->tv_sec; \ + (result)->tv_nsec += 1000000000L; \ + } \ + } while (0) +#endif + +#if !defined(SA_LEN) +# if defined(HAVE_STRUCT_SOCKADDR_SA_LEN) +# define SA_LEN(x) ((x)->sa_len) +# else +# define SA_LEN(x) ((x)->sa_family == AF_INET6 ? \ + sizeof(struct sockaddr_in6) : \ + sizeof(struct sockaddr_in)) +# endif +#endif + +#ifndef __dead +#define __dead __attribute__((__noreturn__)) +#endif + +#ifndef HAVE_FGETLN +char *fgetln(FILE *, size_t *); +#endif + +#ifndef HAVE_PLEDGE +#define pledge(a, b) (0) +#endif + +#ifndef HAVE_REALLOCARRAY +void *reallocarray(void *, size_t, size_t); +#endif + +#ifndef HAVE_RECALLOCARRAY +void *recallocarray(void *, size_t, size_t, size_t); +#endif + +#ifndef HAVE_STRCASESTR +char *strcasestr(const char *, const char *); +#endif + +#ifndef HAVE_STRTONUM +long long strtonum(const char *, long long, long long, const char **); +#endif blob - 35233f5f2393673d5624e76fe0451556294d7a12 (mode 644) blob + /dev/null --- openbsd-compat/explicit_bzero.c +++ /dev/null @@ -1,15 +0,0 @@ -/* $OpenBSD: explicit_bzero.c,v 1.4 2015/08/31 02:53:57 guenther Exp $ */ -/* - * Public domain. - * Written by Matthew Dempsky. - */ - -#include "openbsd-compat.h" - -#include - -void -explicit_bzero(void *buf, size_t len) -{ - memset(buf, 0, len); -} blob - b142c5d7f5b60b9eecd9bc79df3bc793505acb49 (mode 644) blob + /dev/null --- openbsd-compat/openbsd-compat.h +++ /dev/null @@ -1,54 +0,0 @@ -/* $Id: openbsd-compat.h,v 1.51 2010/10/07 10:25:29 djm Exp $ */ - -/* - * Copyright (c) 1999-2003 Damien Miller. All rights reserved. - * Copyright (c) 2003 Ben Lindstrom. All rights reserved. - * Copyright (c) 2002 Tim Rice. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ -#include - -#ifdef NEED_EXPLICIT_BZERO -void explicit_bzero(void *p, size_t n); -#endif -#ifdef NEED_RECALLOCARRAY -void *recallocarray(void *, size_t, size_t, size_t); -#endif -#ifdef NEED_REALLOCARRAY -void *reallocarray(void *, size_t, size_t); -#endif -#ifdef NEED_STRLCAT -size_t strlcat(char *dst, const char *src, size_t size); -#endif -#ifdef NEED_STRLCPY -size_t strlcpy(char *dst, const char *src, size_t size); -#endif -#ifdef NEED_STRTONUM -long long strtonum(const char *nptr, long long minval, long long maxval, const char **errstr); -#endif -#ifdef NEED_PLEDGE -static inline int -pledge(const char *promises, const char *execpromises) -{ - return 0; -} -#endif blob - 840171219741eae591837d011ac207ea241b3507 (mode 644) blob + /dev/null --- openbsd-compat/reallocarray.c +++ /dev/null @@ -1,42 +0,0 @@ -/* $OpenBSD: reallocarray.c,v 1.1 2014/05/08 21:43:49 deraadt Exp $ */ -/* - * Copyright (c) 2008 Otto Moerbeek - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -/* OPENBSD ORIGINAL: lib/libc/stdlib/reallocarray.c */ - -#include "openbsd-compat.h" - -#include -#include -#include -#include - -/* - * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX - * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW - */ -#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4)) - -void * -reallocarray(void *optr, size_t nmemb, size_t size) -{ - if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && - nmemb > 0 && SIZE_MAX / nmemb < size) { - errno = ENOMEM; - return NULL; - } - return realloc(optr, size * nmemb); -} blob - df7a23bb369a3be4684464cc641b4509badb6ae0 (mode 644) blob + /dev/null --- openbsd-compat/recallocarray.c +++ /dev/null @@ -1,84 +0,0 @@ -/* $OpenBSD: recallocarray.c,v 1.1 2017/03/06 18:44:21 otto Exp $ */ -/* - * Copyright (c) 2008, 2017 Otto Moerbeek - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -/* OPENBSD ORIGINAL: lib/libc/stdlib/recallocarray.c */ - -#include -#include -#include -#include -#include - -#include "openbsd-compat.h" - -/* - * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX - * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW - */ -#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4)) - -void * -recallocarray(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size) -{ - size_t oldsize, newsize; - void *newptr; - - if (ptr == NULL) - return calloc(newnmemb, size); - - if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && - newnmemb > 0 && SIZE_MAX / newnmemb < size) { - errno = ENOMEM; - return NULL; - } - newsize = newnmemb * size; - - if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && - oldnmemb > 0 && SIZE_MAX / oldnmemb < size) { - errno = EINVAL; - return NULL; - } - oldsize = oldnmemb * size; - - /* - * Don't bother too much if we're shrinking just a bit, - * we do not shrink for series of small steps, oh well. - */ - if (newsize <= oldsize) { - size_t d = oldsize - newsize; - - if (d < oldsize / 2 && d < (size_t)getpagesize()) { - memset((char *)ptr + newsize, 0, d); - return ptr; - } - } - - newptr = malloc(newsize); - if (newptr == NULL) - return NULL; - - if (newsize > oldsize) { - memcpy(newptr, ptr, oldsize); - memset((char *)newptr + oldsize, 0, newsize - oldsize); - } else - memcpy(newptr, ptr, newsize); - - explicit_bzero(ptr, oldsize); - free(ptr); - - return newptr; -} blob - 53b6d0bec6d5dd2cf949b74d769903e073196b6e (mode 644) blob + /dev/null --- openbsd-compat/strlcat.c +++ /dev/null @@ -1,59 +0,0 @@ -/* $OpenBSD: strlcat.c,v 1.13 2005/08/08 08:05:37 espie Exp $ */ - -/* - * Copyright (c) 1998 Todd C. Miller - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -/* OPENBSD ORIGINAL: lib/libc/string/strlcat.c */ - -#include "openbsd-compat.h" - -#include -#include - -/* - * Appends src to string dst of size siz (unlike strncat, siz is the - * full size of dst, not space left). At most siz-1 characters - * will be copied. Always NUL terminates (unless siz <= strlen(dst)). - * Returns strlen(src) + MIN(siz, strlen(initial dst)). - * If retval >= siz, truncation occurred. - */ -size_t -strlcat(char *dst, const char *src, size_t siz) -{ - char *d = dst; - const char *s = src; - size_t n = siz; - size_t dlen; - - /* Find the end of dst and adjust bytes left but don't go past end */ - while (n-- != 0 && *d != '\0') - d++; - dlen = d - dst; - n = siz - dlen; - - if (n == 0) - return(dlen + strlen(s)); - while (*s != '\0') { - if (n != 1) { - *d++ = *s; - n--; - } - s++; - } - *d = '\0'; - - return(dlen + (s - src)); /* count does not include NUL */ -} blob - b393c327d29109876ac8ec112af1a2ad58f3cce6 (mode 644) blob + /dev/null --- openbsd-compat/strlcpy.c +++ /dev/null @@ -1,55 +0,0 @@ -/* $OpenBSD: strlcpy.c,v 1.11 2006/05/05 15:27:38 millert Exp $ */ - -/* - * Copyright (c) 1998 Todd C. Miller - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -/* OPENBSD ORIGINAL: lib/libc/string/strlcpy.c */ - -#include "openbsd-compat.h" - -#include -#include - -/* - * Copy src to string dst of size siz. At most siz-1 characters - * will be copied. Always NUL terminates (unless siz == 0). - * Returns strlen(src); if retval >= siz, truncation occurred. - */ -size_t -strlcpy(char *dst, const char *src, size_t siz) -{ - char *d = dst; - const char *s = src; - size_t n = siz; - - /* Copy as many bytes as will fit */ - if (n != 0) { - while (--n != 0) { - if ((*d++ = *s++) == '\0') - break; - } - } - - /* Not enough room in dst, add NUL and traverse rest of src */ - if (n == 0) { - if (siz != 0) - *d = '\0'; /* NUL-terminate dst */ - while (*s++) - ; - } - - return(s - src - 1); /* count does not include NUL */ -} blob - bb37f2eff144c2e8d273be0f4ddc07134712d929 (mode 644) blob + /dev/null --- openbsd-compat/strtonum.c +++ /dev/null @@ -1,72 +0,0 @@ -/* $OpenBSD: strtonum.c,v 1.6 2004/08/03 19:38:01 millert Exp $ */ - -/* - * Copyright (c) 2004 Ted Unangst and Todd Miller - * All rights reserved. - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -/* OPENBSD ORIGINAL: lib/libc/stdlib/strtonum.c */ - -#include "openbsd-compat.h" - -#ifndef HAVE_STRTONUM -#include -#include -#include - -#define INVALID 1 -#define TOOSMALL 2 -#define TOOLARGE 3 - -long long -strtonum(const char *numstr, long long minval, long long maxval, - const char **errstrp) -{ - long long ll = 0; - char *ep; - int error = 0; - struct errval { - const char *errstr; - int err; - } ev[4] = { - { NULL, 0 }, - { "invalid", EINVAL }, - { "too small", ERANGE }, - { "too large", ERANGE }, - }; - - ev[0].err = errno; - errno = 0; - if (minval > maxval) - error = INVALID; - else { - ll = strtoll(numstr, &ep, 10); - if (numstr == ep || *ep != '\0') - error = INVALID; - else if ((ll == LLONG_MIN && errno == ERANGE) || ll < minval) - error = TOOSMALL; - else if ((ll == LLONG_MAX && errno == ERANGE) || ll > maxval) - error = TOOLARGE; - } - if (errstrp != NULL) - *errstrp = ev[error].errstr; - errno = ev[error].err; - if (error) - ll = 0; - - return (ll); -} - -#endif /* HAVE_STRTONUM */ blob - 28aaaa37a8ce5f186d0efae40695fe4bd5c7fde4 (mode 644) blob + /dev/null --- openbsd-compat/sys/queue.h +++ /dev/null @@ -1,653 +0,0 @@ -/* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ -/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ - -/* - * Copyright (c) 1991, 1993 - * The Regents of the University of California. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)queue.h 8.5 (Berkeley) 8/20/94 - */ - -/* OPENBSD ORIGINAL: sys/sys/queue.h */ - -#ifndef _FAKE_QUEUE_H_ -#define _FAKE_QUEUE_H_ - -/* - * Require for OS/X and other platforms that have old/broken/incomplete - * . - */ -#undef SLIST_HEAD -#undef SLIST_HEAD_INITIALIZER -#undef SLIST_ENTRY -#undef SLIST_FOREACH_PREVPTR -#undef SLIST_FIRST -#undef SLIST_END -#undef SLIST_EMPTY -#undef SLIST_NEXT -#undef SLIST_FOREACH -#undef SLIST_INIT -#undef SLIST_INSERT_AFTER -#undef SLIST_INSERT_HEAD -#undef SLIST_REMOVE_HEAD -#undef SLIST_REMOVE -#undef SLIST_REMOVE_NEXT -#undef LIST_HEAD -#undef LIST_HEAD_INITIALIZER -#undef LIST_ENTRY -#undef LIST_FIRST -#undef LIST_END -#undef LIST_EMPTY -#undef LIST_NEXT -#undef LIST_FOREACH -#undef LIST_INIT -#undef LIST_INSERT_AFTER -#undef LIST_INSERT_BEFORE -#undef LIST_INSERT_HEAD -#undef LIST_REMOVE -#undef LIST_REPLACE -#undef SIMPLEQ_HEAD -#undef SIMPLEQ_HEAD_INITIALIZER -#undef SIMPLEQ_ENTRY -#undef SIMPLEQ_FIRST -#undef SIMPLEQ_END -#undef SIMPLEQ_EMPTY -#undef SIMPLEQ_NEXT -#undef SIMPLEQ_FOREACH -#undef SIMPLEQ_INIT -#undef SIMPLEQ_INSERT_HEAD -#undef SIMPLEQ_INSERT_TAIL -#undef SIMPLEQ_INSERT_AFTER -#undef SIMPLEQ_REMOVE_HEAD -#undef TAILQ_HEAD -#undef TAILQ_HEAD_INITIALIZER -#undef TAILQ_ENTRY -#undef TAILQ_FIRST -#undef TAILQ_END -#undef TAILQ_NEXT -#undef TAILQ_LAST -#undef TAILQ_PREV -#undef TAILQ_EMPTY -#undef TAILQ_FOREACH -#undef TAILQ_FOREACH_REVERSE -#undef TAILQ_INIT -#undef TAILQ_INSERT_HEAD -#undef TAILQ_INSERT_TAIL -#undef TAILQ_INSERT_AFTER -#undef TAILQ_INSERT_BEFORE -#undef TAILQ_REMOVE -#undef TAILQ_REPLACE -#undef CIRCLEQ_HEAD -#undef CIRCLEQ_HEAD_INITIALIZER -#undef CIRCLEQ_ENTRY -#undef CIRCLEQ_FIRST -#undef CIRCLEQ_LAST -#undef CIRCLEQ_END -#undef CIRCLEQ_NEXT -#undef CIRCLEQ_PREV -#undef CIRCLEQ_EMPTY -#undef CIRCLEQ_FOREACH -#undef CIRCLEQ_FOREACH_REVERSE -#undef CIRCLEQ_INIT -#undef CIRCLEQ_INSERT_AFTER -#undef CIRCLEQ_INSERT_BEFORE -#undef CIRCLEQ_INSERT_HEAD -#undef CIRCLEQ_INSERT_TAIL -#undef CIRCLEQ_REMOVE -#undef CIRCLEQ_REPLACE - -/* - * This file defines five types of data structures: singly-linked lists, - * lists, simple queues, tail queues, and circular queues. - * - * - * A singly-linked list is headed by a single forward pointer. The elements - * are singly linked for minimum space and pointer manipulation overhead at - * the expense of O(n) removal for arbitrary elements. New elements can be - * added to the list after an existing element or at the head of the list. - * Elements being removed from the head of the list should use the explicit - * macro for this purpose for optimum efficiency. A singly-linked list may - * only be traversed in the forward direction. Singly-linked lists are ideal - * for applications with large datasets and few or no removals or for - * implementing a LIFO queue. - * - * A list is headed by a single forward pointer (or an array of forward - * pointers for a hash table header). The elements are doubly linked - * so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before - * or after an existing element or at the head of the list. A list - * may only be traversed in the forward direction. - * - * A simple queue is headed by a pair of pointers, one the head of the - * list and the other to the tail of the list. The elements are singly - * linked to save space, so elements can only be removed from the - * head of the list. New elements can be added to the list before or after - * an existing element, at the head of the list, or at the end of the - * list. A simple queue may only be traversed in the forward direction. - * - * A tail queue is headed by a pair of pointers, one to the head of the - * list and the other to the tail of the list. The elements are doubly - * linked so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before or - * after an existing element, at the head of the list, or at the end of - * the list. A tail queue may be traversed in either direction. - * - * A circle queue is headed by a pair of pointers, one to the head of the - * list and the other to the tail of the list. The elements are doubly - * linked so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before or after - * an existing element, at the head of the list, or at the end of the list. - * A circle queue may be traversed in either direction, but has a more - * complex end of list detection. - * - * For details on the use of these macros, see the queue(3) manual page. - */ - -#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) -#define _Q_INVALIDATE(a) (a) = ((void *)-1) -#else -#define _Q_INVALIDATE(a) -#endif - -/* - * Singly-linked List definitions. - */ -#define SLIST_HEAD(name, type) \ -struct name { \ - struct type *slh_first; /* first element */ \ -} - -#define SLIST_HEAD_INITIALIZER(head) \ - { NULL } - -#define SLIST_ENTRY(type) \ -struct { \ - struct type *sle_next; /* next element */ \ -} - -/* - * Singly-linked List access methods. - */ -#define SLIST_FIRST(head) ((head)->slh_first) -#define SLIST_END(head) NULL -#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) -#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) - -#define SLIST_FOREACH(var, head, field) \ - for((var) = SLIST_FIRST(head); \ - (var) != SLIST_END(head); \ - (var) = SLIST_NEXT(var, field)) - -#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = SLIST_FIRST(head); \ - (var) && ((tvar) = SLIST_NEXT(var, field), 1); \ - (var) = (tvar)) - -/* - * Singly-linked List functions. - */ -#define SLIST_INIT(head) { \ - SLIST_FIRST(head) = SLIST_END(head); \ -} - -#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ - (elm)->field.sle_next = (slistelm)->field.sle_next; \ - (slistelm)->field.sle_next = (elm); \ -} while (0) - -#define SLIST_INSERT_HEAD(head, elm, field) do { \ - (elm)->field.sle_next = (head)->slh_first; \ - (head)->slh_first = (elm); \ -} while (0) - -#define SLIST_REMOVE_AFTER(elm, field) do { \ - (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \ -} while (0) - -#define SLIST_REMOVE_HEAD(head, field) do { \ - (head)->slh_first = (head)->slh_first->field.sle_next; \ -} while (0) - -#define SLIST_REMOVE(head, elm, type, field) do { \ - if ((head)->slh_first == (elm)) { \ - SLIST_REMOVE_HEAD((head), field); \ - } else { \ - struct type *curelm = (head)->slh_first; \ - \ - while (curelm->field.sle_next != (elm)) \ - curelm = curelm->field.sle_next; \ - curelm->field.sle_next = \ - curelm->field.sle_next->field.sle_next; \ - _Q_INVALIDATE((elm)->field.sle_next); \ - } \ -} while (0) - -/* - * List definitions. - */ -#define LIST_HEAD(name, type) \ -struct name { \ - struct type *lh_first; /* first element */ \ -} - -#define LIST_HEAD_INITIALIZER(head) \ - { NULL } - -#define LIST_ENTRY(type) \ -struct { \ - struct type *le_next; /* next element */ \ - struct type **le_prev; /* address of previous next element */ \ -} - -/* - * List access methods - */ -#define LIST_FIRST(head) ((head)->lh_first) -#define LIST_END(head) NULL -#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) -#define LIST_NEXT(elm, field) ((elm)->field.le_next) - -#define LIST_FOREACH(var, head, field) \ - for((var) = LIST_FIRST(head); \ - (var)!= LIST_END(head); \ - (var) = LIST_NEXT(var, field)) - -#define LIST_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = LIST_FIRST(head); \ - (var) && ((tvar) = LIST_NEXT(var, field), 1); \ - (var) = (tvar)) - -/* - * List functions. - */ -#define LIST_INIT(head) do { \ - LIST_FIRST(head) = LIST_END(head); \ -} while (0) - -#define LIST_INSERT_AFTER(listelm, elm, field) do { \ - if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ - (listelm)->field.le_next->field.le_prev = \ - &(elm)->field.le_next; \ - (listelm)->field.le_next = (elm); \ - (elm)->field.le_prev = &(listelm)->field.le_next; \ -} while (0) - -#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ - (elm)->field.le_prev = (listelm)->field.le_prev; \ - (elm)->field.le_next = (listelm); \ - *(listelm)->field.le_prev = (elm); \ - (listelm)->field.le_prev = &(elm)->field.le_next; \ -} while (0) - -#define LIST_INSERT_HEAD(head, elm, field) do { \ - if (((elm)->field.le_next = (head)->lh_first) != NULL) \ - (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ - (head)->lh_first = (elm); \ - (elm)->field.le_prev = &(head)->lh_first; \ -} while (0) - -#define LIST_REMOVE(elm, field) do { \ - if ((elm)->field.le_next != NULL) \ - (elm)->field.le_next->field.le_prev = \ - (elm)->field.le_prev; \ - *(elm)->field.le_prev = (elm)->field.le_next; \ - _Q_INVALIDATE((elm)->field.le_prev); \ - _Q_INVALIDATE((elm)->field.le_next); \ -} while (0) - -#define LIST_REPLACE(elm, elm2, field) do { \ - if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ - (elm2)->field.le_next->field.le_prev = \ - &(elm2)->field.le_next; \ - (elm2)->field.le_prev = (elm)->field.le_prev; \ - *(elm2)->field.le_prev = (elm2); \ - _Q_INVALIDATE((elm)->field.le_prev); \ - _Q_INVALIDATE((elm)->field.le_next); \ -} while (0) - -/* - * Simple queue definitions. - */ -#define SIMPLEQ_HEAD(name, type) \ -struct name { \ - struct type *sqh_first; /* first element */ \ - struct type **sqh_last; /* addr of last next element */ \ -} - -#define SIMPLEQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).sqh_first } - -#define SIMPLEQ_ENTRY(type) \ -struct { \ - struct type *sqe_next; /* next element */ \ -} - -/* - * Simple queue access methods. - */ -#define SIMPLEQ_FIRST(head) ((head)->sqh_first) -#define SIMPLEQ_END(head) NULL -#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) -#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) - -#define SIMPLEQ_FOREACH(var, head, field) \ - for((var) = SIMPLEQ_FIRST(head); \ - (var) != SIMPLEQ_END(head); \ - (var) = SIMPLEQ_NEXT(var, field)) - -#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = SIMPLEQ_FIRST(head); \ - (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \ - (var) = (tvar)) - -/* - * Simple queue functions. - */ -#define SIMPLEQ_INIT(head) do { \ - (head)->sqh_first = NULL; \ - (head)->sqh_last = &(head)->sqh_first; \ -} while (0) - -#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ - if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ - (head)->sqh_last = &(elm)->field.sqe_next; \ - (head)->sqh_first = (elm); \ -} while (0) - -#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ - (elm)->field.sqe_next = NULL; \ - *(head)->sqh_last = (elm); \ - (head)->sqh_last = &(elm)->field.sqe_next; \ -} while (0) - -#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ - if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ - (head)->sqh_last = &(elm)->field.sqe_next; \ - (listelm)->field.sqe_next = (elm); \ -} while (0) - -#define SIMPLEQ_REMOVE_HEAD(head, field) do { \ - if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ - (head)->sqh_last = &(head)->sqh_first; \ -} while (0) - -#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ - if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ - == NULL) \ - (head)->sqh_last = &(elm)->field.sqe_next; \ -} while (0) - -/* - * Tail queue definitions. - */ -#define TAILQ_HEAD(name, type) \ -struct name { \ - struct type *tqh_first; /* first element */ \ - struct type **tqh_last; /* addr of last next element */ \ -} - -#define TAILQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).tqh_first } - -#define TAILQ_ENTRY(type) \ -struct { \ - struct type *tqe_next; /* next element */ \ - struct type **tqe_prev; /* address of previous next element */ \ -} - -/* - * tail queue access methods - */ -#define TAILQ_FIRST(head) ((head)->tqh_first) -#define TAILQ_END(head) NULL -#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) -#define TAILQ_LAST(head, headname) \ - (*(((struct headname *)((head)->tqh_last))->tqh_last)) -/* XXX */ -#define TAILQ_PREV(elm, headname, field) \ - (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) -#define TAILQ_EMPTY(head) \ - (TAILQ_FIRST(head) == TAILQ_END(head)) - -#define TAILQ_FOREACH(var, head, field) \ - for((var) = TAILQ_FIRST(head); \ - (var) != TAILQ_END(head); \ - (var) = TAILQ_NEXT(var, field)) - -#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = TAILQ_FIRST(head); \ - (var) != TAILQ_END(head) && \ - ((tvar) = TAILQ_NEXT(var, field), 1); \ - (var) = (tvar)) - - -#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ - for((var) = TAILQ_LAST(head, headname); \ - (var) != TAILQ_END(head); \ - (var) = TAILQ_PREV(var, headname, field)) - -#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ - for ((var) = TAILQ_LAST(head, headname); \ - (var) != TAILQ_END(head) && \ - ((tvar) = TAILQ_PREV(var, headname, field), 1); \ - (var) = (tvar)) - -/* - * Tail queue functions. - */ -#define TAILQ_INIT(head) do { \ - (head)->tqh_first = NULL; \ - (head)->tqh_last = &(head)->tqh_first; \ -} while (0) - -#define TAILQ_INSERT_HEAD(head, elm, field) do { \ - if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ - (head)->tqh_first->field.tqe_prev = \ - &(elm)->field.tqe_next; \ - else \ - (head)->tqh_last = &(elm)->field.tqe_next; \ - (head)->tqh_first = (elm); \ - (elm)->field.tqe_prev = &(head)->tqh_first; \ -} while (0) - -#define TAILQ_INSERT_TAIL(head, elm, field) do { \ - (elm)->field.tqe_next = NULL; \ - (elm)->field.tqe_prev = (head)->tqh_last; \ - *(head)->tqh_last = (elm); \ - (head)->tqh_last = &(elm)->field.tqe_next; \ -} while (0) - -#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ - if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ - (elm)->field.tqe_next->field.tqe_prev = \ - &(elm)->field.tqe_next; \ - else \ - (head)->tqh_last = &(elm)->field.tqe_next; \ - (listelm)->field.tqe_next = (elm); \ - (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ -} while (0) - -#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ - (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ - (elm)->field.tqe_next = (listelm); \ - *(listelm)->field.tqe_prev = (elm); \ - (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ -} while (0) - -#define TAILQ_REMOVE(head, elm, field) do { \ - if (((elm)->field.tqe_next) != NULL) \ - (elm)->field.tqe_next->field.tqe_prev = \ - (elm)->field.tqe_prev; \ - else \ - (head)->tqh_last = (elm)->field.tqe_prev; \ - *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ - _Q_INVALIDATE((elm)->field.tqe_prev); \ - _Q_INVALIDATE((elm)->field.tqe_next); \ -} while (0) - -#define TAILQ_REPLACE(head, elm, elm2, field) do { \ - if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ - (elm2)->field.tqe_next->field.tqe_prev = \ - &(elm2)->field.tqe_next; \ - else \ - (head)->tqh_last = &(elm2)->field.tqe_next; \ - (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ - *(elm2)->field.tqe_prev = (elm2); \ - _Q_INVALIDATE((elm)->field.tqe_prev); \ - _Q_INVALIDATE((elm)->field.tqe_next); \ -} while (0) - -/* - * Circular queue definitions. - */ -#define CIRCLEQ_HEAD(name, type) \ -struct name { \ - struct type *cqh_first; /* first element */ \ - struct type *cqh_last; /* last element */ \ -} - -#define CIRCLEQ_HEAD_INITIALIZER(head) \ - { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } - -#define CIRCLEQ_ENTRY(type) \ -struct { \ - struct type *cqe_next; /* next element */ \ - struct type *cqe_prev; /* previous element */ \ -} - -/* - * Circular queue access methods - */ -#define CIRCLEQ_FIRST(head) ((head)->cqh_first) -#define CIRCLEQ_LAST(head) ((head)->cqh_last) -#define CIRCLEQ_END(head) ((void *)(head)) -#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) -#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) -#define CIRCLEQ_EMPTY(head) \ - (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) - -#define CIRCLEQ_FOREACH(var, head, field) \ - for((var) = CIRCLEQ_FIRST(head); \ - (var) != CIRCLEQ_END(head); \ - (var) = CIRCLEQ_NEXT(var, field)) - -#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = CIRCLEQ_FIRST(head); \ - (var) != CIRCLEQ_END(head) && \ - ((tvar) = CIRCLEQ_NEXT(var, field), 1); \ - (var) = (tvar)) - -#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ - for((var) = CIRCLEQ_LAST(head); \ - (var) != CIRCLEQ_END(head); \ - (var) = CIRCLEQ_PREV(var, field)) - -#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ - for ((var) = CIRCLEQ_LAST(head, headname); \ - (var) != CIRCLEQ_END(head) && \ - ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \ - (var) = (tvar)) - -/* - * Circular queue functions. - */ -#define CIRCLEQ_INIT(head) do { \ - (head)->cqh_first = CIRCLEQ_END(head); \ - (head)->cqh_last = CIRCLEQ_END(head); \ -} while (0) - -#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ - (elm)->field.cqe_next = (listelm)->field.cqe_next; \ - (elm)->field.cqe_prev = (listelm); \ - if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ - (head)->cqh_last = (elm); \ - else \ - (listelm)->field.cqe_next->field.cqe_prev = (elm); \ - (listelm)->field.cqe_next = (elm); \ -} while (0) - -#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ - (elm)->field.cqe_next = (listelm); \ - (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ - if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ - (head)->cqh_first = (elm); \ - else \ - (listelm)->field.cqe_prev->field.cqe_next = (elm); \ - (listelm)->field.cqe_prev = (elm); \ -} while (0) - -#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ - (elm)->field.cqe_next = (head)->cqh_first; \ - (elm)->field.cqe_prev = CIRCLEQ_END(head); \ - if ((head)->cqh_last == CIRCLEQ_END(head)) \ - (head)->cqh_last = (elm); \ - else \ - (head)->cqh_first->field.cqe_prev = (elm); \ - (head)->cqh_first = (elm); \ -} while (0) - -#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ - (elm)->field.cqe_next = CIRCLEQ_END(head); \ - (elm)->field.cqe_prev = (head)->cqh_last; \ - if ((head)->cqh_first == CIRCLEQ_END(head)) \ - (head)->cqh_first = (elm); \ - else \ - (head)->cqh_last->field.cqe_next = (elm); \ - (head)->cqh_last = (elm); \ -} while (0) - -#define CIRCLEQ_REMOVE(head, elm, field) do { \ - if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ - (head)->cqh_last = (elm)->field.cqe_prev; \ - else \ - (elm)->field.cqe_next->field.cqe_prev = \ - (elm)->field.cqe_prev; \ - if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ - (head)->cqh_first = (elm)->field.cqe_next; \ - else \ - (elm)->field.cqe_prev->field.cqe_next = \ - (elm)->field.cqe_next; \ - _Q_INVALIDATE((elm)->field.cqe_prev); \ - _Q_INVALIDATE((elm)->field.cqe_next); \ -} while (0) - -#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ - if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ - CIRCLEQ_END(head)) \ - (head).cqh_last = (elm2); \ - else \ - (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ - if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ - CIRCLEQ_END(head)) \ - (head).cqh_first = (elm2); \ - else \ - (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ - _Q_INVALIDATE((elm)->field.cqe_prev); \ - _Q_INVALIDATE((elm)->field.cqe_next); \ -} while (0) - -#endif /* !_FAKE_QUEUE_H_ */ blob - 753b3cfd5979bc41f8370e63c245656d0bbaa611 (mode 644) blob + /dev/null --- openbsd-compat/sys/tree.h +++ /dev/null @@ -1,1006 +0,0 @@ -/* $OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $ */ -/* - * Copyright 2002 Niels Provos - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef _SYS_TREE_H_ -#define _SYS_TREE_H_ - -#include - -/* - * This file defines data structures for different types of trees: - * splay trees and red-black trees. - * - * A splay tree is a self-organizing data structure. Every operation - * on the tree causes a splay to happen. The splay moves the requested - * node to the root of the tree and partly rebalances it. - * - * This has the benefit that request locality causes faster lookups as - * the requested nodes move to the top of the tree. On the other hand, - * every lookup causes memory writes. - * - * The Balance Theorem bounds the total access time for m operations - * and n inserts on an initially empty tree as O((m + n)lg n). The - * amortized cost for a sequence of m accesses to a splay tree is O(lg n); - * - * A red-black tree is a binary search tree with the node color as an - * extra attribute. It fulfills a set of conditions: - * - every search path from the root to a leaf consists of the - * same number of black nodes, - * - each red node (except for the root) has a black parent, - * - each leaf node is black. - * - * Every operation on a red-black tree is bounded as O(lg n). - * The maximum height of a red-black tree is 2lg (n+1). - */ - -#define SPLAY_HEAD(name, type) \ -struct name { \ - struct type *sph_root; /* root of the tree */ \ -} - -#define SPLAY_INITIALIZER(root) \ - { NULL } - -#define SPLAY_INIT(root) do { \ - (root)->sph_root = NULL; \ -} while (0) - -#define SPLAY_ENTRY(type) \ -struct { \ - struct type *spe_left; /* left element */ \ - struct type *spe_right; /* right element */ \ -} - -#define SPLAY_LEFT(elm, field) (elm)->field.spe_left -#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right -#define SPLAY_ROOT(head) (head)->sph_root -#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) - -/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ -#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ -} while (0) - -#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ -} while (0) - -#define SPLAY_LINKLEFT(head, tmp, field) do { \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ -} while (0) - -#define SPLAY_LINKRIGHT(head, tmp, field) do { \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ -} while (0) - -#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ - SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ -} while (0) - -/* Generates prototypes and inline functions */ - -#define SPLAY_PROTOTYPE(name, type, field, cmp) \ -void name##_SPLAY(struct name *, struct type *); \ -void name##_SPLAY_MINMAX(struct name *, int); \ -struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ -struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ - \ -/* Finds the node with the same key as elm */ \ -static __unused __inline struct type * \ -name##_SPLAY_FIND(struct name *head, struct type *elm) \ -{ \ - if (SPLAY_EMPTY(head)) \ - return(NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) \ - return (head->sph_root); \ - return (NULL); \ -} \ - \ -static __unused __inline struct type * \ -name##_SPLAY_NEXT(struct name *head, struct type *elm) \ -{ \ - name##_SPLAY(head, elm); \ - if (SPLAY_RIGHT(elm, field) != NULL) { \ - elm = SPLAY_RIGHT(elm, field); \ - while (SPLAY_LEFT(elm, field) != NULL) { \ - elm = SPLAY_LEFT(elm, field); \ - } \ - } else \ - elm = NULL; \ - return (elm); \ -} \ - \ -static __unused __inline struct type * \ -name##_SPLAY_MIN_MAX(struct name *head, int val) \ -{ \ - name##_SPLAY_MINMAX(head, val); \ - return (SPLAY_ROOT(head)); \ -} - -/* Main splay operation. - * Moves node close to the key of elm to top - */ -#define SPLAY_GENERATE(name, type, field, cmp) \ -struct type * \ -name##_SPLAY_INSERT(struct name *head, struct type *elm) \ -{ \ - if (SPLAY_EMPTY(head)) { \ - SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ - } else { \ - int __comp; \ - name##_SPLAY(head, elm); \ - __comp = (cmp)(elm, (head)->sph_root); \ - if(__comp < 0) { \ - SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ - SPLAY_RIGHT(elm, field) = (head)->sph_root; \ - SPLAY_LEFT((head)->sph_root, field) = NULL; \ - } else if (__comp > 0) { \ - SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ - SPLAY_LEFT(elm, field) = (head)->sph_root; \ - SPLAY_RIGHT((head)->sph_root, field) = NULL; \ - } else \ - return ((head)->sph_root); \ - } \ - (head)->sph_root = (elm); \ - return (NULL); \ -} \ - \ -struct type * \ -name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *__tmp; \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) { \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ - } else { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ - name##_SPLAY(head, elm); \ - SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ - } \ - return (elm); \ - } \ - return (NULL); \ -} \ - \ -void \ -name##_SPLAY(struct name *head, struct type *elm) \ -{ \ - struct type __node, *__left, *__right, *__tmp; \ - int __comp; \ -\ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ - __left = __right = &__node; \ -\ - while ((__comp = (cmp)(elm, (head)->sph_root))) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) < 0){ \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) > 0){ \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ -} \ - \ -/* Splay with either the minimum or the maximum element \ - * Used to find minimum or maximum element in tree. \ - */ \ -void name##_SPLAY_MINMAX(struct name *head, int __comp) \ -{ \ - struct type __node, *__left, *__right, *__tmp; \ -\ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ - __left = __right = &__node; \ -\ - while (1) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp < 0){ \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ -} - -#define SPLAY_NEGINF -1 -#define SPLAY_INF 1 - -#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) -#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) -#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) -#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) -#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ - : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) -#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ - : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) - -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); \ - (x) != NULL; \ - (x) = SPLAY_NEXT(name, head, x)) - -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = NULL; \ -} while (0) - -#define RB_BLACK 0 -#define RB_RED 1 -#define RB_ENTRY(type) \ -struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ -} - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ -} while (0) - -#define RB_SET_BLACKRED(black, red, field) do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ -} while (0) - -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) -#endif - -#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) - -#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) - -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ -attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ -attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ -attr struct type *name##_RB_INSERT(struct name *, struct type *); \ -attr struct type *name##_RB_FIND(struct name *, struct type *); \ -attr struct type *name##_RB_NFIND(struct name *, struct type *); \ -attr struct type *name##_RB_NEXT(struct type *); \ -attr struct type *name##_RB_PREV(struct type *); \ -attr struct type *name##_RB_MINMAX(struct name *, int); \ - \ - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp,) -#define RB_GENERATE_STATIC(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ -attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ -{ \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) && \ - RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ -} \ - \ -attr void \ -name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ -{ \ - struct type *tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ - elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ - struct type *oleft; \ - if ((oleft = RB_LEFT(tmp, field)))\ - RB_COLOR(oleft, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ - struct type *oright; \ - if ((oright = RB_RIGHT(tmp, field)))\ - RB_COLOR(oright, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ -} \ - \ -attr struct type * \ -name##_RB_REMOVE(struct name *head, struct type *elm) \ -{ \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type *left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field))) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old)\ - RB_LEFT(RB_PARENT(old, field), field) = elm;\ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm;\ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field))); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ -color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ -} \ - \ -/* Inserts a node into the RB tree */ \ -attr struct type * \ -name##_RB_INSERT(struct name *head, struct type *elm) \ -{ \ - struct type *tmp; \ - struct type *parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ -} \ - \ -/* Finds the node with the same key as elm */ \ -attr struct type * \ -name##_RB_FIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ -} \ - \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RB_NFIND(struct name *head, struct type *elm) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_NEXT(struct type *elm) \ -{ \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_PREV(struct type *elm) \ -{ \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ -} \ - \ -attr struct type * \ -name##_RB_MINMAX(struct name *head, int val) \ -{ \ - struct type *tmp = RB_ROOT(head); \ - struct type *parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ -} - -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ - (x) = (y)) - - -/* - * Copyright (c) 2016 David Gwynne - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -struct rb_type { - int (*t_compare)(const void *, const void *); - void (*t_augment)(void *); - unsigned int t_offset; /* offset of rb_entry in type */ -}; - -struct rb_tree { - struct rb_entry *rbt_root; -}; - -struct rb_entry { - struct rb_entry *rbt_parent; - struct rb_entry *rbt_left; - struct rb_entry *rbt_right; - unsigned int rbt_color; -}; - -#define RBT_HEAD(_name, _type) \ -struct _name { \ - struct rb_tree rbh_root; \ -} - -#define RBT_ENTRY(_type) struct rb_entry - -static inline void -_rb_init(struct rb_tree *rbt) -{ - rbt->rbt_root = NULL; -} - -static inline int -_rb_empty(struct rb_tree *rbt) -{ - return (rbt->rbt_root == NULL); -} - -void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); -void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); -void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); -void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); -void *_rb_root(const struct rb_type *, struct rb_tree *); -void *_rb_min(const struct rb_type *, struct rb_tree *); -void *_rb_max(const struct rb_type *, struct rb_tree *); -void *_rb_next(const struct rb_type *, void *); -void *_rb_prev(const struct rb_type *, void *); -void *_rb_left(const struct rb_type *, void *); -void *_rb_right(const struct rb_type *, void *); -void *_rb_parent(const struct rb_type *, void *); -void _rb_set_left(const struct rb_type *, void *, void *); -void _rb_set_right(const struct rb_type *, void *, void *); -void _rb_set_parent(const struct rb_type *, void *, void *); -void _rb_poison(const struct rb_type *, void *, unsigned long); -int _rb_check(const struct rb_type *, void *, unsigned long); - -#define RBT_INITIALIZER(_head) { { NULL } } - -#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ -extern const struct rb_type *const _name##_RBT_TYPE; \ - \ -__unused static inline void \ -_name##_RBT_INIT(struct _name *head) \ -{ \ - _rb_init(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ -{ \ - return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ -{ \ - return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_FIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_ROOT(struct _name *head) \ -{ \ - return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline int \ -_name##_RBT_EMPTY(struct _name *head) \ -{ \ - return _rb_empty(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MIN(struct _name *head) \ -{ \ - return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MAX(struct _name *head) \ -{ \ - return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NEXT(struct _type *elm) \ -{ \ - return _rb_next(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PREV(struct _type *elm) \ -{ \ - return _rb_prev(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_LEFT(struct _type *elm) \ -{ \ - return _rb_left(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_RIGHT(struct _type *elm) \ -{ \ - return _rb_right(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PARENT(struct _type *elm) \ -{ \ - return _rb_parent(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline void \ -_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ -{ \ - return _rb_set_left(_name##_RBT_TYPE, elm, left); \ -} \ - \ -__unused static inline void \ -_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ -{ \ - return _rb_set_right(_name##_RBT_TYPE, elm, right); \ -} \ - \ -__unused static inline void \ -_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ -{ \ - return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ -} \ - \ -__unused static inline void \ -_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_poison(_name##_RBT_TYPE, elm, poison); \ -} \ - \ -__unused static inline int \ -_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_check(_name##_RBT_TYPE, elm, poison); \ -} - -#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ -static int \ -_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ -{ \ - const struct _type *l = lptr, *r = rptr; \ - return _cmp(l, r); \ -} \ -static const struct rb_type _name##_RBT_INFO = { \ - _name##_RBT_COMPARE, \ - _aug, \ - offsetof(struct _type, _field), \ -}; \ -const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO - -#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ -static void \ -_name##_RBT_AUGMENT(void *ptr) \ -{ \ - struct _type *p = ptr; \ - return _aug(p); \ -} \ -RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) - -#define RBT_GENERATE(_name, _type, _field, _cmp) \ - RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) - -#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) -#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) -#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) -#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) -#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) -#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) -#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) -#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) -#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) -#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) -#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) -#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) -#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) -#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) -#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l) -#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r) -#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p) -#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) -#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) - -#define RBT_FOREACH(_e, _name, _head) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_NEXT(_name, (_e))) - -#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ - (_e) = (_n)) - -#define RBT_FOREACH_REVERSE(_e, _name, _head) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_PREV(_name, (_e))) - -#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ - (_e) = (_n)) - -#endif /* _SYS_TREE_H_ */ blob - /dev/null blob + 5dcdc1abfd21fa2e57f1cb9c51d27135d6bd4cfd (mode 644) --- /dev/null +++ configure.ac @@ -0,0 +1,70 @@ +AC_INIT([filter-admdscrub], [v0.3], [misc@opensmtpd.org], [filter-admdscrub], [https://src.imperialat.at/?action=summary&path=filter-admdscrub.git]) +AC_CONFIG_AUX_DIR(etc) +AC_CONFIG_LIBOBJ_DIR(compat) +AC_CANONICAL_HOST +AM_INIT_AUTOMAKE([-Wall foreign subdir-objects]) +AC_PROG_CC +AC_USE_SYSTEM_EXTENSIONS + +AC_ARG_WITH([libexecsmtpddir], + [AS_HELP_STRING([--with-libexecsmtpddir=DIR], ["OpenSMTPD libexec binary location [LIBEXECDIR/smtpd]"])], + [libexecsmtpddir=$withval], + [libexecsmtpddir="\${libexecdir}/smtpd"]) +AC_SUBST([libexecsmtpddir], [$libexecsmtpddir]) + +PKG_PROG_PKG_CONFIG + +AC_REPLACE_FUNCS([fgetln strtonum reallocarray recallocarray strcasestr]) + +AC_CHECK_FUNC([pledge]) + +dnl on OpenBSD, make sure to use libevent from base +case "$host_os" in +*openbsd*) + AC_SEARCH_LIBS([event_init], [event], [], + [AC_MSG_ERROR([requires libevent])]) + ;; +*) + PKG_CHECK_MODULES([libevent2], [libevent_core >= 2], [ + AC_DEFINE([HAVE_EVENT2], 1, [1 if using event2]) + CFLAGS="$libevent2_CFLAGS $CFLAGS" + LIBS="$libevent2_LIBS $LIBS" + ], [AC_MSG_ERROR([requires libevent])]) + ;; +esac + +AC_SEARCH_LIBS([osmtpd_run], [opensmtpd], [], [ + AC_MSG_ERROR([cannot find libopensmtpd]) +]) + +# check compiler flags +AC_DEFUN([CC_ADD_CHECK_FLAGS], [ + AC_MSG_CHECKING([if $CC supports $1 flag]) + old_CFLAGS="$CFLAGS" + CFLAGS="$CFLAGS -Werror $1" + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([],[])], [ + AC_MSG_RESULT(yes) + CFLAGS="$old_CFLAGS $1" + ], [ + AC_MSG_RESULT(no) + CFLAGS="$old_CFLAGS" + ]) +]) +CC_ADD_CHECK_FLAGS([-Wall]) +CC_ADD_CHECK_FLAGS([-Wstrict-prototypes]) +CC_ADD_CHECK_FLAGS([-Wmissing-prototypes]) +CC_ADD_CHECK_FLAGS([-Wmissing-declarations]) +CC_ADD_CHECK_FLAGS([-Wshadow]) +dnl CC_ADD_CHECK_FLAGS([-Wcast-qual]) +CC_ADD_CHECK_FLAGS([-Wpointer-arith]) +CC_ADD_CHECK_FLAGS([-Wsign-compare]) + +CC_ADD_CHECK_FLAGS([-Wno-pointer-sign]) +CC_ADD_CHECK_FLAGS([-Wno-unused-function]) +CC_ADD_CHECK_FLAGS([-Wno-deprecated-declarations]) + +AC_SUBST([AM_CFLAGS]) +AC_CONFIG_HEADERS([config.h]) +AC_CONFIG_FILES([GNUmakefile]) + +AC_OUTPUT