commit ab1569eef4b24cb2522e98f12538870f05dde92c from: Omar Polo date: Sat May 06 09:16:14 2023 UTC add a configure script and rework the make infrastructure don't depend on bsd.prog.mk & co; first step to make it portable. commit - 39c4991909529bea37b8687953a237b9f743f571 commit + ab1569eef4b24cb2522e98f12538870f05dde92c blob - de5c155a5176aaee6a31b63c70e7ae8c3d666af2 blob + c70b4ee8689d9109dfb7707637d04f290201af91 --- .gitignore +++ .gitignore @@ -1,4 +1,6 @@ -www -**/obj **/*.[od] +**/config.h +**/config.mk **/tags +config.log +config.log.old blob - /dev/null blob + 6d5e7ffb83940f3518c98bd667a2a4da4db3012f (mode 644) --- /dev/null +++ .mblaze/Makefile @@ -0,0 +1,19 @@ +DISTFILES = Makefile filter seq + +all: + false + +dist: + mkdir -p ${DESTDIR}/ + ${INSTALL} -m 0644 ${DISTFILES} ${DESTDIR}/ + +install: + mkdir -p ${DESTDIR}${SHAREDIR}/gotmarc/mblaze + ${INSTALL_DATA} filter seq ${DESTDIR}${SHAREDIR}/gotmarc/mblaze + +uninstall: + rm -f ${DESTDIR}${SHAREDIR}/gotmarc/mblaze/filter + rm -f ${DESTDIR}${SHAREDIR}/gotmarc/mblaze/seq + +.PHONY: all dist install uninstall +include ../config.mk blob - 6a924576f2109adf453c165eda2e23b9e673ea5d blob + a1651b26abf1162272caf1b743cf8d77375ea21d --- Makefile +++ Makefile @@ -1,34 +1,100 @@ -OUTDIR = /var/www/marc +include config.mk -.PHONY: all images dirs gzip scaleimgs +# -- build-related variables -- -all: dirs images ${OUTDIR}/style.css +VERSION = 0.1 +DISTNAME = gotmarc-${VERSION} -images: ${OUTDIR}/got@2x.png ${OUTDIR}/got.png ${OUTDIR}/got-tiny@2x.png \ - ${OUTDIR}/got-tiny.png +# -- public targets -- -${OUTDIR}/got@2x.png: images/got.orig.png - cp $? $@ -${OUTDIR}/got.png: images/got.png - cp $? $@ -${OUTDIR}/got-tiny@2x.png: images/got-tiny@2x.png - cp $? $@ -${OUTDIR}/got-tiny.png: images/got-tiny.png - cp $? $@ -${OUTDIR}/style.css: style.css - cp $? $@ +all: msearchd +.PHONY: all msearchd tags clean distclean install uninstall -dirs: - @mkdir -p ${OUTDIR}/mail/ - @mkdir -p ${OUTDIR}/parts/ - @mkdir -p ${OUTDIR}/text/ - @mkdir -p ${OUTDIR}/thread/ +msearchd: + ${MAKE} -C msearchd -gzip: - gzip -fkr ${OUTDIR} +tags: + ${MAKE} -C msearchd tags -scaleimgs: - convert images/got.orig.png -resize 200x200 images/got.png - convert images/got.orig.png -resize 128x128 images/got-tiny@2x.png - convert images/got.orig.png -resize 64x64 images/got-tiny.png - optipng -o7 -zm1-9 images/*.png +clean: + ${MAKE} -C msearchd clean + +distclean: clean + ${MAKE} -C msearchd distclean + rm -f config.log config.log.old config.mk + +install: + mkdir -p ${DESTDIR}${BINDIR} + ${INSTALL_PROGRAM} gmimport ${DESTDIR}${BINDIR} + sed -e "/^libexec=/s@=.*@=${LIBEXEC}/gotmarc@" \ + -e "/^mblaze=/s@=.*@=${SHAREDIR}/gotmarc/mblaze@" \ + -e "/^tmpldir=/s@=.*@=${REAL_SYSCONFDIR}/gotmarc@" \ + gotmarc > ${DESTDIR}${BINDIR}/gotmarc + chmod 0755 ${DESTDIR}${BINDIR}/gotmarc + mkdir -p ${DESTDIR}${LIBEXEC}/gotmarc + ${INSTALL_PROGRAM} filter-ignore ${DESTDIR}${LIBEXEC}/gotmarc + ${INSTALL_PROGRAM} mexp ${DESTDIR}${LIBEXEC}/gotmarc + ${INSTALL_PROGRAM} mkindex ${DESTDIR}${LIBEXEC}/gotmarc + ${INSTALL_PROGRAM} pe ${DESTDIR}${LIBEXEC}/gotmarc + mkdir -p ${DESTDIR}${SYSCONFDIR}/gotmarc + ${INSTALL_DATA} style.css ${DESTDIR}${SYSCONFDIR}/gotmarc/ + mkdir -p ${DESTDIR}${PERL_LIB} + ${INSTALL_DATA} GotMArc.pm ${DESTDIR}${PERL_LIB} + mkdir -p ${DESTDIR}${MANDIR}/man1 + ${INSTALL_MAN} gmimport.1 ${DESTDIR}${MANDIR}/man1/ + ${INSTALL_MAN} gotmarc.1 ${DESTDIR}${MANDIR}/man1/ + mkdir -p ${DESTDIR}${MANDIR}/man7 + ${INSTALL_MAN} gotmarc.7 ${DESTDIR}${MANDIR}/man7/ + ${MAKE} -C .mblaze install + ${MAKE} -C msearchd install + ${MAKE} -C templates install + +uninstall: + rm -f ${DESTDIR}${BINDIR}/gmimport + rm -f ${DESTDIR}${BINDIR}/gotmarc + rm -f ${DESTDIR}${LIBEXEC}/gotmarc/filter-ignore + rm -f ${DESTDIR}${LIBEXEC}/gotmarc/mexp + rm -f ${DESTDIR}${LIBEXEC}/gotmarc/mkindex + rm -f ${DESTDIR}${LIBEXEC}/gotmarc/pe + rm -f ${DESTDIR}${SYSCONFDIR}/gotmarc/style.css + rm -f ${DESTDIR}${PERL_LIB}/GotMArc.pm + rm -f ${DESTDIR}${MANDIR}/man1/gmimport.1 + rm -f ${DESTDIR}${MANDIR}/man1/gotmarc.1 + rm -f ${DESTDIR}${MANDIR}/man7/gotmarc.7 + ${MAKE} -C .mblaze uninstall + ${MAKE} -C msearchd uninstall + ${MAKE} -C templates uninstall + +# -- maintainer targets -- + +PRIVKEY = missing-PRIVKEY +PUBKEY = missing-PUBKEY +DISTFILES = GotMArc.pm Makefile README TODO configure \ + filter-ignore gmimport gmimport.1 gotmarc gotmarc.1 \ + gotmarc.7 mexp mkindex pe style.css + +release: + sed -i -e '/^RELEASE=/s/no/yes/' configure + ${MAKE} ${DISTNAME}.sha256.sig + sed -i -e '/^RELEASE=/s/yes/no/' configure + +dist: ${DISTNAME}.sha256 + +${DISTNAME}.sha256.sig: ${DISTNAME}.sha256 + signify -S -e -m ${DISTNAME}.sha256 -s ${PRIVKEY} + +${DISTNAME}.sha256: ${DISTNAME}.tar.gz + sha256 ${DISTNAME}.tar.gz > $@ + +${DISTNAME}.tar.gz: ${DISTFILES} + mkdir -p .dist/${DISTNAME} + ${INSTALL} -m 0644 ${DISTFILES} .dist/${DISTNAME} + cd .dist/${DISTNAME} && chmod 0755 configure filter-ignore \ + gmimport gotmarc mexp mkindex pe + ${MAKE} -C .mblaze DESTDIR=${PWD}/.dist/${DISTNAME}/.mblaze dist + ${MAKE} -C templates DESTDIR=${PWD}/.dist/${DISTNAME}/templates dist + ${MAKE} -C msearchd DESTDIR=${PWD}/.dist/${DISTNAME}/msearchd dist + cd .dist && tar czf ../$@ ${DISTNAME} + rm -rf .dist + +.PHONY: release ${DISTNAME}.tar.gz blob - /dev/null blob + 0b4b4b2f623a09caab45ee4cb27aa43b1250a6b4 (mode 755) --- /dev/null +++ configure @@ -0,0 +1,139 @@ +#!/bin/sh +# +# Copyright (c) 2014, 2015, 2016 Ingo Schwarze +# Copyright (c) 2017, 2018 Kristaps Dzonsons +# Copyright (c) 2022, 2023 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. + +set -e + +RELEASE=no + +usage() +{ + echo "usage: $0 [--help] [--option=value] [OPTION=VALUE]" >&2 + exit 1 +} + +PKG_CONFIG= +if command -v pkg-config 2>/dev/null >&2; then + PKG_CONFIG=pkg-config +fi + +while [ $# -gt 0 ]; do + key="${1%%=*}" + val="${1#*=}" + + if [ "$key" = --help ]; then + usage + fi + + if [ "$key" = "$1" ]; then + # if no --x=y, look at the next arg + if !shift 2>/dev/null; then + echo "$0: missing value for $key" >&2 + exit 1 + fi + val="$1" + fi + + case "$key" in + --mandir) key=MANDIR ;; + --perllib) key=PERL_LIB ;; + --prefix) key=PREFIX ;; + --sharedir) key=SHAREDIR ;; + --statedir) key=STATEDIR ;; + --sysconfdir) key=SYSCONFDIR ;; + esac + + case "$key" in + CC) CC="$val" ;; + CFLAGS) CFLAGS="$val" ;; + LDFLAGS) LDFLAGS="$val" ;; + MANDIR) MANDIR="$val" ;; + PERL_LIB) PERL_LIB="$val" ;; + PKG_CONFIG) PKG_CONFIG="$val" ;; + PREFIX) PREFIX="$val" ;; + SHAREDIR) SHAREDIR="$val" ;; + STATEDIR) STATECONFDIR="$val" ;; + SYSCONFDIR) SYSCONFDIR="$val" ;; + esac + + shift +done + +CC=${CC:-cc} +CFLAGS=${CFLAGS:--O2 -pipe} +PREFIX=${PREFIX-/usr/local} +STATEDIR=${STATEDIR-/var} +SYSCONFDIR=${SYSCONFDIR-/etc} + +pkgconfig=${PKG_CONFIG} +if [ "$pkgconfig" = no ]; then + pkgconfig= +fi + +export CC CFLAGS LDFLAGS PERL_LIB PREFIX STATEDIR SYSCONFDIR pkgconfig + +mv config.log config.log.old 2>/dev/null || true + +exec 3> config.log +echo "config.log: writing..." + +echo >&2 +echo "running configure for \`msearchd':" >&2 +(cd msearchd && ./configure) +echo >&2 +echo "returning to the configure for \`gotmarc':" >&2 + +exec > config.mk +echo "config.mk: writing...">&2 + +cat <&2 +echo "Now run \`make' to compile." >&2 +echo >&2 blob - 90adab2a1714da3460e0d3092ed3e9bd54471225 blob + f68c8822c88972b288430c02fc19e884ea2e14c0 --- gotmarc +++ gotmarc @@ -12,6 +12,7 @@ usage() { exit 1 } +# changed at install-time libexec=. mblaze=.mblaze tmpldir=templates/ blob - 462c8b0bd449b0c98af98d839dfc5cea85fe5010 blob + a68c48a2948930217e368f701ccd3892bb313bfd --- msearchd/Makefile +++ msearchd/Makefile @@ -1,30 +1,58 @@ +include config.mk +include ../config.mk + PROG = msearchd SRCS = msearchd.c fcgi.c server.c MAN = msearchd.8 -#DEBUG = -O0 -g -DDEBUG +OBJS = ${SRCS:.c=.o} ${COMPATS:.c=.o} -CDIAGFLAGS = -Wall -Wuninitialized -Wunused -CDIAGFLAGS += -Wmissing-prototypes -Wstrict-prototypes -CDIAGFLAGS += -Werror +# -- public targets -- -WARNINGS = Yes +all: ${PROG} -CPPFLAGS += -I/usr/local/include +.PHONY: all tags clean distclean install uninstall dist -LIBSQLITE3 = /usr/local/lib/libsqlite3.a +tags: + ctags ${SRCS} -LDADD = -levent -lsqlite3 -DPADD = ${LIBEVENT} ${LIBSQLITE3} -LDFLAGS = -L/usr/local/lib +clean: + rm -f *.[do] compat/*.[do] test/*.[do] -PREFIX ?= /usr/local -SBINDIR ?= ${PREFIX}/sbin -MANDIR ?= ${PREFIX}/man/man -RCDIR ?= /etc/rc.d/ +distclean: clean + rm -f config.h config.mk -realinstall: - install -m 0755 ${PROG} ${DESTDIR}${SBINDIR} - install -m 0555 ${.CURDIR}/${PROG}.rc ${DESTDIR}${RCDIR}/${PROG} +install: + mkdir -p ${DESTDIR}${MANDIR}/man8 + ${INSTALL_MAN} msearchd.8 ${DESTDIR}${MANDIR}/man8 + mkdir -p ${DESTDIR}${SBINDIR} + ${INSTALL_PROGRAM} ${PROG} ${DESTDIR}${SBINDIR} + mkdir -p ${DESTDIR}${SYSCONFDIR}/gotmarc + ${INSTALL_DATA} schema.sql ${DESTDIR}${SYSCONFDIR}/gotmarc -.include +uninstall: + rm -f ${DESTDIR}${MANDIR}/man8/msearchd.8 + rm -f ${DESTDIR}${SBINDIR}/${PROG} + rm -f ${DESTDIR}${SYSCONFDIR}/gotmarc/schema.sql + +# -- internal build targets -- + +${PROG}: ${OBJS} + ${CC} -o $@ ${CFLAGS} ${OBJS} ${LDFLAGS} + +# -- maintainer targets -- + +DISTFILES = Makefile configure ${SRCS} msearchd.h msearchd.8 schema.sql + +dist: + mkdir -p ${DESTDIR}/ + ${INSTALL} -m 0644 ${DISTFILES} ${DESTDIR}/ + chmod 0755 ${DESTDIR}/configure + ${MAKE} -C compat DESTDIR=${DESTDIR}/compat dist + ${MAKE} -C tests DESTDIR=${DESTDIR}/tests dist + +# -- dependencies -- + +-include fcgi.d +-include msearchd.d +-include server.d blob - /dev/null blob + b8bf7900f54ab221659ca2c3de7995af595a1f31 (mode 644) --- /dev/null +++ msearchd/compat/Makefile @@ -0,0 +1,15 @@ +DISTFILES = Makefile err.c event.h freezero.c getdtablecount.c \ + getdtablesize.c getprogname.c pledge.c recallocarray.c \ + setproctitle.c setresgid.c setresuid.c stdlib.h string.h \ + strlcat.c strlcpy.c strtonum.c unistd.h unveil.c vasprintf.c + +all: + false + +dist: + mkdir -p ${DESTDIR}/ + ${INSTALL} -m 0644 ${DISTFILES} ${DESTDIR}/ + ${MAKE} -C imsg DESTDIR=${DESTDIR}/imsg dist + ${MAKE} -C sys DESTDIR=${DESTDIR}/sys dist + +include ../../config.mk blob - /dev/null blob + cb22b6f52cad3fa05f5724b548c6977192539497 (mode 644) --- /dev/null +++ msearchd/compat/err.c @@ -0,0 +1,82 @@ +/* + * Copyright (c) 2021 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 +#include +#include +#include +#include + +static void vwarn_impl(const char*, va_list); +static void vwarnx_impl(const char*, va_list); + +static void +vwarn_impl(const char *fmt, va_list ap) +{ + fprintf(stderr, "%s: ", getprogname()); + vfprintf(stderr, fmt, ap); + fprintf(stderr, ": %s\n", strerror(errno)); +} + +static void +vwarnx_impl(const char *fmt, va_list ap) +{ + fprintf(stderr, "%s: ", getprogname()); + vfprintf(stderr, fmt, ap); + fprintf(stderr, "\n"); +} + +void +err(int ret, const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vwarn_impl(fmt, ap); + va_end(ap); + exit(ret); +} + +void +errx(int ret, const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vwarnx_impl(fmt, ap); + va_end(ap); + exit(ret); +} + +void +warn(const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vwarn_impl(fmt, ap); + va_end(ap); +} + +void +warnx(const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + vwarnx_impl(fmt, ap); + va_end(ap); +} blob - /dev/null blob + c89fc77a8db4036318b9dde961b9a30e9212af89 (mode 644) --- /dev/null +++ msearchd/compat/event.h @@ -0,0 +1,13 @@ +#include_next "event.h" + +#include "../config.h" + +#if !HAVE_EVENT_ASR_RUN +struct asr_query; +struct asr_result; +struct event_asr; + +struct event_asr *event_asr_run(struct asr_query *, + void (*cb)(struct asr_result *, void *), void *); +void event_asr_abort(struct event_asr *); +#endif blob - /dev/null blob + 0f83c59fffbfacccfe8af6db827e93f0bb9997ed (mode 644) --- /dev/null +++ msearchd/compat/freezero.c @@ -0,0 +1,28 @@ +/* + * Copyright (c) 2021 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 +#include + +void +freezero(void *ptr, size_t len) +{ + if (ptr == NULL) + return; + + memset(ptr, 0, len); + free(ptr); +} blob - /dev/null blob + f6fe14a6f40035e080311b006af986bf1b9a3131 (mode 644) --- /dev/null +++ msearchd/compat/getdtablecount.c @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2021 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. + */ + +/* + * XXX: on linux it's possible to glob("/proc/$pid/fd/ *") to know the + * dtablecount. + */ + +#include "../config.h" + +int getdtablecount(void); + +int +getdtablecount(void) +{ + return 0; +} blob - /dev/null blob + c0a18609fdaa36944e1a72debf4fd70cf2a9e450 (mode 644) --- /dev/null +++ msearchd/compat/getdtablesize.c @@ -0,0 +1,25 @@ +/* + * Copyright (c) 2021 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 + +int getdtablesize(void); + +int +getdtablesize(void) +{ + return sysconf(_SC_OPEN_MAX); +} blob - /dev/null blob + 4aff31e40afec0da1d5879697964a3032efab9c5 (mode 644) --- /dev/null +++ msearchd/compat/getprogname.c @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2021 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" + +const char *getprogname(void); + +#if HAVE___PROGNAME + +const char * +getprogname(void) +{ + extern const char *__progname; + + return __progname; +} + +#elif HAVE_GETEXECNAME + +const char * +getprogname(void) +{ + return getexecname(); +} + +#else + +const char * +getprogname(void) +{ + return "galileo"; +} + +#endif blob - /dev/null blob + c636257f676bb601044ce9c4213871d3751d1f2f (mode 644) --- /dev/null +++ msearchd/compat/imsg/Makefile @@ -0,0 +1,11 @@ +DISTFILES = Makefile imsg-buffer.c imsg.c imsg.h + +all: + false + +dist: + mkdir -p ${DESTDIR}/ + ${INSTALL} -m 0644 ${DISTFILES} ${DESTDIR}/ + +.PHONY: all dist +include ../../../config.mk blob - /dev/null blob + 7abea4e0debb0a22243abaa74c5cb9c58e4d06df (mode 644) --- /dev/null +++ msearchd/compat/imsg/imsg-buffer.c @@ -0,0 +1,321 @@ +/* $OpenBSD: imsg-buffer.c,v 1.14 2022/04/23 08:57:52 tobias Exp $ */ + +/* + * Copyright (c) 2003, 2004 Henning Brauer + * + * 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 + +#include +#include +#include +#include +#include + +#include "imsg.h" + +static int ibuf_realloc(struct ibuf *, size_t); +static void ibuf_enqueue(struct msgbuf *, struct ibuf *); +static void ibuf_dequeue(struct msgbuf *, struct ibuf *); + +struct ibuf * +ibuf_open(size_t len) +{ + struct ibuf *buf; + + if ((buf = calloc(1, sizeof(struct ibuf))) == NULL) + return (NULL); + if ((buf->buf = malloc(len)) == NULL) { + free(buf); + return (NULL); + } + buf->size = buf->max = len; + buf->fd = -1; + + return (buf); +} + +struct ibuf * +ibuf_dynamic(size_t len, size_t max) +{ + struct ibuf *buf; + + if (max < len) + return (NULL); + + if ((buf = ibuf_open(len)) == NULL) + return (NULL); + + if (max > 0) + buf->max = max; + + return (buf); +} + +static int +ibuf_realloc(struct ibuf *buf, size_t len) +{ + unsigned char *b; + + /* on static buffers max is eq size and so the following fails */ + if (len > SIZE_MAX - buf->wpos || buf->wpos + len > buf->max) { + errno = ERANGE; + return (-1); + } + + b = recallocarray(buf->buf, buf->size, buf->wpos + len, 1); + if (b == NULL) + return (-1); + buf->buf = b; + buf->size = buf->wpos + len; + + return (0); +} + +int +ibuf_add(struct ibuf *buf, const void *data, size_t len) +{ + if (len > SIZE_MAX - buf->wpos) { + errno = ERANGE; + return (-1); + } + + if (buf->wpos + len > buf->size) + if (ibuf_realloc(buf, len) == -1) + return (-1); + + memcpy(buf->buf + buf->wpos, data, len); + buf->wpos += len; + return (0); +} + +void * +ibuf_reserve(struct ibuf *buf, size_t len) +{ + void *b; + + if (len > SIZE_MAX - buf->wpos) { + errno = ERANGE; + return (NULL); + } + + if (buf->wpos + len > buf->size) + if (ibuf_realloc(buf, len) == -1) + return (NULL); + + b = buf->buf + buf->wpos; + buf->wpos += len; + return (b); +} + +void * +ibuf_seek(struct ibuf *buf, size_t pos, size_t len) +{ + /* only allowed to seek in already written parts */ + if (len > SIZE_MAX - pos || pos + len > buf->wpos) + return (NULL); + + return (buf->buf + pos); +} + +size_t +ibuf_size(struct ibuf *buf) +{ + return (buf->wpos); +} + +size_t +ibuf_left(struct ibuf *buf) +{ + return (buf->max - buf->wpos); +} + +void +ibuf_close(struct msgbuf *msgbuf, struct ibuf *buf) +{ + ibuf_enqueue(msgbuf, buf); +} + +int +ibuf_write(struct msgbuf *msgbuf) +{ + struct iovec iov[IOV_MAX]; + struct ibuf *buf; + unsigned int i = 0; + ssize_t n; + + memset(&iov, 0, sizeof(iov)); + TAILQ_FOREACH(buf, &msgbuf->bufs, entry) { + if (i >= IOV_MAX) + break; + iov[i].iov_base = buf->buf + buf->rpos; + iov[i].iov_len = buf->wpos - buf->rpos; + i++; + } + +again: + if ((n = writev(msgbuf->fd, iov, i)) == -1) { + if (errno == EINTR) + goto again; + if (errno == ENOBUFS) + errno = EAGAIN; + return (-1); + } + + if (n == 0) { /* connection closed */ + errno = 0; + return (0); + } + + msgbuf_drain(msgbuf, n); + + return (1); +} + +void +ibuf_free(struct ibuf *buf) +{ + if (buf == NULL) + return; + freezero(buf->buf, buf->size); + free(buf); +} + +void +msgbuf_init(struct msgbuf *msgbuf) +{ + msgbuf->queued = 0; + msgbuf->fd = -1; + TAILQ_INIT(&msgbuf->bufs); +} + +void +msgbuf_drain(struct msgbuf *msgbuf, size_t n) +{ + struct ibuf *buf, *next; + + for (buf = TAILQ_FIRST(&msgbuf->bufs); buf != NULL && n > 0; + buf = next) { + next = TAILQ_NEXT(buf, entry); + if (n >= buf->wpos - buf->rpos) { + n -= buf->wpos - buf->rpos; + ibuf_dequeue(msgbuf, buf); + } else { + buf->rpos += n; + n = 0; + } + } +} + +void +msgbuf_clear(struct msgbuf *msgbuf) +{ + struct ibuf *buf; + + while ((buf = TAILQ_FIRST(&msgbuf->bufs)) != NULL) + ibuf_dequeue(msgbuf, buf); +} + +int +msgbuf_write(struct msgbuf *msgbuf) +{ + struct iovec iov[IOV_MAX]; + struct ibuf *buf, *buf0 = NULL; + unsigned int i = 0; + ssize_t n; + struct msghdr msg; + struct cmsghdr *cmsg; + union { + struct cmsghdr hdr; + char buf[CMSG_SPACE(sizeof(int))]; + } cmsgbuf; + + memset(&iov, 0, sizeof(iov)); + memset(&msg, 0, sizeof(msg)); + memset(&cmsgbuf, 0, sizeof(cmsgbuf)); + TAILQ_FOREACH(buf, &msgbuf->bufs, entry) { + if (i >= IOV_MAX) + break; + if (i > 0 && buf->fd != -1) + break; + iov[i].iov_base = buf->buf + buf->rpos; + iov[i].iov_len = buf->wpos - buf->rpos; + i++; + if (buf->fd != -1) + buf0 = buf; + } + + msg.msg_iov = iov; + msg.msg_iovlen = i; + + if (buf0 != NULL) { + msg.msg_control = (caddr_t)&cmsgbuf.buf; + msg.msg_controllen = sizeof(cmsgbuf.buf); + cmsg = CMSG_FIRSTHDR(&msg); + cmsg->cmsg_len = CMSG_LEN(sizeof(int)); + cmsg->cmsg_level = SOL_SOCKET; + cmsg->cmsg_type = SCM_RIGHTS; + *(int *)CMSG_DATA(cmsg) = buf0->fd; + } + +again: + if ((n = sendmsg(msgbuf->fd, &msg, 0)) == -1) { + if (errno == EINTR) + goto again; + if (errno == ENOBUFS) + errno = EAGAIN; + return (-1); + } + + if (n == 0) { /* connection closed */ + errno = 0; + return (0); + } + + /* + * assumption: fd got sent if sendmsg sent anything + * this works because fds are passed one at a time + */ + if (buf0 != NULL) { + close(buf0->fd); + buf0->fd = -1; + } + + msgbuf_drain(msgbuf, n); + + return (1); +} + +static void +ibuf_enqueue(struct msgbuf *msgbuf, struct ibuf *buf) +{ + TAILQ_INSERT_TAIL(&msgbuf->bufs, buf, entry); + msgbuf->queued++; +} + +static void +ibuf_dequeue(struct msgbuf *msgbuf, struct ibuf *buf) +{ + TAILQ_REMOVE(&msgbuf->bufs, buf, entry); + + if (buf->fd != -1) + close(buf->fd); + + msgbuf->queued--; + ibuf_free(buf); +} blob - /dev/null blob + b381b1edd4711442af6ada9266a4ba09e4c2e000 (mode 644) --- /dev/null +++ msearchd/compat/imsg/imsg.c @@ -0,0 +1,303 @@ +/* $OpenBSD: imsg.c,v 1.17 2022/01/28 10:41:44 claudio Exp $ */ + +/* + * Copyright (c) 2003, 2004 Henning Brauer + * + * 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 + +#include +#include +#include +#include + +#include "imsg.h" + +int imsg_fd_overhead = 0; + +static int imsg_get_fd(struct imsgbuf *); + +void +imsg_init(struct imsgbuf *ibuf, int fd) +{ + msgbuf_init(&ibuf->w); + memset(&ibuf->r, 0, sizeof(ibuf->r)); + ibuf->fd = fd; + ibuf->w.fd = fd; + ibuf->pid = getpid(); + TAILQ_INIT(&ibuf->fds); +} + +ssize_t +imsg_read(struct imsgbuf *ibuf) +{ + struct msghdr msg; + struct cmsghdr *cmsg; + union { + struct cmsghdr hdr; + char buf[CMSG_SPACE(sizeof(int) * 1)]; + } cmsgbuf; + struct iovec iov; + ssize_t n = -1; + int fd; + struct imsg_fd *ifd; + + memset(&msg, 0, sizeof(msg)); + memset(&cmsgbuf, 0, sizeof(cmsgbuf)); + + iov.iov_base = ibuf->r.buf + ibuf->r.wpos; + iov.iov_len = sizeof(ibuf->r.buf) - ibuf->r.wpos; + msg.msg_iov = &iov; + msg.msg_iovlen = 1; + msg.msg_control = &cmsgbuf.buf; + msg.msg_controllen = sizeof(cmsgbuf.buf); + + if ((ifd = calloc(1, sizeof(struct imsg_fd))) == NULL) + return (-1); + +again: + if (getdtablecount() + imsg_fd_overhead + + (int)((CMSG_SPACE(sizeof(int))-CMSG_SPACE(0))/sizeof(int)) + >= getdtablesize()) { + errno = EAGAIN; + free(ifd); + return (-1); + } + + if ((n = recvmsg(ibuf->fd, &msg, 0)) == -1) { + if (errno == EINTR) + goto again; + goto fail; + } + + ibuf->r.wpos += n; + + for (cmsg = CMSG_FIRSTHDR(&msg); cmsg != NULL; + cmsg = CMSG_NXTHDR(&msg, cmsg)) { + if (cmsg->cmsg_level == SOL_SOCKET && + cmsg->cmsg_type == SCM_RIGHTS) { + int i; + int j; + + /* + * We only accept one file descriptor. Due to C + * padding rules, our control buffer might contain + * more than one fd, and we must close them. + */ + j = ((char *)cmsg + cmsg->cmsg_len - + (char *)CMSG_DATA(cmsg)) / sizeof(int); + for (i = 0; i < j; i++) { + fd = ((int *)CMSG_DATA(cmsg))[i]; + if (ifd != NULL) { + ifd->fd = fd; + TAILQ_INSERT_TAIL(&ibuf->fds, ifd, + entry); + ifd = NULL; + } else + close(fd); + } + } + /* we do not handle other ctl data level */ + } + +fail: + free(ifd); + return (n); +} + +ssize_t +imsg_get(struct imsgbuf *ibuf, struct imsg *imsg) +{ + size_t av, left, datalen; + + av = ibuf->r.wpos; + + if (IMSG_HEADER_SIZE > av) + return (0); + + memcpy(&imsg->hdr, ibuf->r.buf, sizeof(imsg->hdr)); + if (imsg->hdr.len < IMSG_HEADER_SIZE || + imsg->hdr.len > MAX_IMSGSIZE) { + errno = ERANGE; + return (-1); + } + if (imsg->hdr.len > av) + return (0); + datalen = imsg->hdr.len - IMSG_HEADER_SIZE; + ibuf->r.rptr = ibuf->r.buf + IMSG_HEADER_SIZE; + if (datalen == 0) + imsg->data = NULL; + else if ((imsg->data = malloc(datalen)) == NULL) + return (-1); + + if (imsg->hdr.flags & IMSGF_HASFD) + imsg->fd = imsg_get_fd(ibuf); + else + imsg->fd = -1; + + if (datalen != 0) + memcpy(imsg->data, ibuf->r.rptr, datalen); + + if (imsg->hdr.len < av) { + left = av - imsg->hdr.len; + memmove(&ibuf->r.buf, ibuf->r.buf + imsg->hdr.len, left); + ibuf->r.wpos = left; + } else + ibuf->r.wpos = 0; + + return (datalen + IMSG_HEADER_SIZE); +} + +int +imsg_compose(struct imsgbuf *ibuf, uint32_t type, uint32_t peerid, pid_t pid, + int fd, const void *data, uint16_t datalen) +{ + struct ibuf *wbuf; + + if ((wbuf = imsg_create(ibuf, type, peerid, pid, datalen)) == NULL) + return (-1); + + if (imsg_add(wbuf, data, datalen) == -1) + return (-1); + + wbuf->fd = fd; + + imsg_close(ibuf, wbuf); + + return (1); +} + +int +imsg_composev(struct imsgbuf *ibuf, uint32_t type, uint32_t peerid, pid_t pid, + int fd, const struct iovec *iov, int iovcnt) +{ + struct ibuf *wbuf; + int i, datalen = 0; + + for (i = 0; i < iovcnt; i++) + datalen += iov[i].iov_len; + + if ((wbuf = imsg_create(ibuf, type, peerid, pid, datalen)) == NULL) + return (-1); + + for (i = 0; i < iovcnt; i++) + if (imsg_add(wbuf, iov[i].iov_base, iov[i].iov_len) == -1) + return (-1); + + wbuf->fd = fd; + + imsg_close(ibuf, wbuf); + + return (1); +} + +/* ARGSUSED */ +struct ibuf * +imsg_create(struct imsgbuf *ibuf, uint32_t type, uint32_t peerid, pid_t pid, + uint16_t datalen) +{ + struct ibuf *wbuf; + struct imsg_hdr hdr; + + datalen += IMSG_HEADER_SIZE; + if (datalen > MAX_IMSGSIZE) { + errno = ERANGE; + return (NULL); + } + + hdr.type = type; + hdr.flags = 0; + hdr.peerid = peerid; + if ((hdr.pid = pid) == 0) + hdr.pid = ibuf->pid; + if ((wbuf = ibuf_dynamic(datalen, MAX_IMSGSIZE)) == NULL) { + return (NULL); + } + if (imsg_add(wbuf, &hdr, sizeof(hdr)) == -1) + return (NULL); + + return (wbuf); +} + +int +imsg_add(struct ibuf *msg, const void *data, uint16_t datalen) +{ + if (datalen) + if (ibuf_add(msg, data, datalen) == -1) { + ibuf_free(msg); + return (-1); + } + return (datalen); +} + +void +imsg_close(struct imsgbuf *ibuf, struct ibuf *msg) +{ + struct imsg_hdr *hdr; + + hdr = (struct imsg_hdr *)msg->buf; + + hdr->flags &= ~IMSGF_HASFD; + if (msg->fd != -1) + hdr->flags |= IMSGF_HASFD; + + hdr->len = (uint16_t)msg->wpos; + + ibuf_close(&ibuf->w, msg); +} + +void +imsg_free(struct imsg *imsg) +{ + freezero(imsg->data, imsg->hdr.len - IMSG_HEADER_SIZE); +} + +static int +imsg_get_fd(struct imsgbuf *ibuf) +{ + int fd; + struct imsg_fd *ifd; + + if ((ifd = TAILQ_FIRST(&ibuf->fds)) == NULL) + return (-1); + + fd = ifd->fd; + TAILQ_REMOVE(&ibuf->fds, ifd, entry); + free(ifd); + + return (fd); +} + +int +imsg_flush(struct imsgbuf *ibuf) +{ + while (ibuf->w.queued) + if (msgbuf_write(&ibuf->w) <= 0) + return (-1); + return (0); +} + +void +imsg_clear(struct imsgbuf *ibuf) +{ + int fd; + + msgbuf_clear(&ibuf->w); + while ((fd = imsg_get_fd(ibuf)) != -1) + close(fd); +} blob - /dev/null blob + 9e19bedb893decd22b167421d22c86500cc3d217 (mode 644) --- /dev/null +++ msearchd/compat/imsg/imsg.h @@ -0,0 +1,114 @@ +/* $OpenBSD: imsg.h,v 1.6 2021/01/13 09:56:28 claudio Exp $ */ + +/* + * Copyright (c) 2006, 2007 Pierre-Yves Ritschard + * Copyright (c) 2006, 2007, 2008 Reyk Floeter + * Copyright (c) 2003, 2004 Henning Brauer + * + * 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. + */ + +#ifndef _IMSG_H_ +#define _IMSG_H_ + +#include + +#define IBUF_READ_SIZE 65535 +#define IMSG_HEADER_SIZE sizeof(struct imsg_hdr) +#define MAX_IMSGSIZE 16384 + +struct ibuf { + TAILQ_ENTRY(ibuf) entry; + unsigned char *buf; + size_t size; + size_t max; + size_t wpos; + size_t rpos; + int fd; +}; + +struct msgbuf { + TAILQ_HEAD(, ibuf) bufs; + uint32_t queued; + int fd; +}; + +struct ibuf_read { + unsigned char buf[IBUF_READ_SIZE]; + unsigned char *rptr; + size_t wpos; +}; + +struct imsg_fd { + TAILQ_ENTRY(imsg_fd) entry; + int fd; +}; + +struct imsgbuf { + TAILQ_HEAD(, imsg_fd) fds; + struct ibuf_read r; + struct msgbuf w; + int fd; + pid_t pid; +}; + +#define IMSGF_HASFD 1 + +struct imsg_hdr { + uint32_t type; + uint16_t len; + uint16_t flags; + uint32_t peerid; + uint32_t pid; +}; + +struct imsg { + struct imsg_hdr hdr; + int fd; + void *data; +}; + +struct iovec; + +/* buffer.c */ +struct ibuf *ibuf_open(size_t); +struct ibuf *ibuf_dynamic(size_t, size_t); +int ibuf_add(struct ibuf *, const void *, size_t); +void *ibuf_reserve(struct ibuf *, size_t); +void *ibuf_seek(struct ibuf *, size_t, size_t); +size_t ibuf_size(struct ibuf *); +size_t ibuf_left(struct ibuf *); +void ibuf_close(struct msgbuf *, struct ibuf *); +int ibuf_write(struct msgbuf *); +void ibuf_free(struct ibuf *); +void msgbuf_init(struct msgbuf *); +void msgbuf_clear(struct msgbuf *); +int msgbuf_write(struct msgbuf *); +void msgbuf_drain(struct msgbuf *, size_t); + +/* imsg.c */ +void imsg_init(struct imsgbuf *, int); +ssize_t imsg_read(struct imsgbuf *); +ssize_t imsg_get(struct imsgbuf *, struct imsg *); +int imsg_compose(struct imsgbuf *, uint32_t, uint32_t, pid_t, int, + const void *, uint16_t); +int imsg_composev(struct imsgbuf *, uint32_t, uint32_t, pid_t, int, + const struct iovec *, int); +struct ibuf *imsg_create(struct imsgbuf *, uint32_t, uint32_t, pid_t, uint16_t); +int imsg_add(struct ibuf *, const void *, uint16_t); +void imsg_close(struct imsgbuf *, struct ibuf *); +void imsg_free(struct imsg *); +int imsg_flush(struct imsgbuf *); +void imsg_clear(struct imsgbuf *); + +#endif blob - /dev/null blob + e564f5e6f17add39aa7f62c26706c7f33020f747 (mode 644) --- /dev/null +++ msearchd/compat/pledge.c @@ -0,0 +1,7 @@ +int pledge(const char *, const char *); + +int +pledge(const char *promises, const char *execpromises) +{ + return 0; +} blob - /dev/null blob + 763552dc901ea6b8a38268ec0c436a8319de0182 (mode 644) --- /dev/null +++ msearchd/compat/recallocarray.c @@ -0,0 +1,88 @@ +/* $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 +#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 + 4504b69fb16b99333a1028491adda8c8bb0de5a5 (mode 644) --- /dev/null +++ msearchd/compat/setproctitle.c @@ -0,0 +1,56 @@ +/* + * Copyright (c) 2016 Nicholas Marriott + * + * 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 MIND, 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 + +#include "../config.h" + +void setproctitle(const char *, ...); + +#if HAVE_PR_SET_NAME + +#include + +void +setproctitle(const char *fmt, ...) +{ + char title[16], name[16], *cp; + va_list ap; + int used; + + va_start(ap, fmt); + vsnprintf(title, sizeof title, fmt, ap); + va_end(ap); + + used = snprintf(name, sizeof name, "%s: %s", getprogname(), title); + if (used >= (int)sizeof name) { + cp = strrchr(name, ' '); + if (cp != NULL) + *cp = '\0'; + } + prctl(PR_SET_NAME, name); +} +#else +void +setproctitle(const char *fmt, ...) +{ + (void)fmt; +} +#endif blob - /dev/null blob + ec625cd0abbff37a6be1700a1cd73e0f67bd2079 (mode 644) --- /dev/null +++ msearchd/compat/setresgid.c @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2004, 2005 Darren Tucker (dtucker at zip com au). + * + * 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 + +int +setresgid(gid_t rgid, gid_t egid, gid_t sgid) +{ + /* this is the only configuration tested */ + + if (rgid != egid || egid != sgid) + return -1; + + if (setregid(rgid, egid) == -1) + return -1; + + return 0; +} blob - /dev/null blob + a033d99ab249e10501c2f99de973d2d3242757f8 (mode 644) --- /dev/null +++ msearchd/compat/setresuid.c @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2004, 2005 Darren Tucker (dtucker at zip com au). + * + * 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 + +int +setresuid(uid_t ruid, uid_t euid, uid_t suid) +{ + uid_t ouid; + int ret = -1; + + /* Allow only the tested configuration. */ + + if (ruid != euid || euid != suid) { + errno = ENOSYS; + return -1; + } + ouid = getuid(); + + if ((ret = setreuid(euid, euid)) == -1) + return -1; + + /* + * When real, effective and saved uids are the same and we have + * changed uids, sanity check that we cannot restore the old uid. + */ + + if (ruid == euid && euid == suid && ouid != ruid && + setuid(ouid) != -1 && seteuid(ouid) != -1) { + errno = EINVAL; + return -1; + } + + /* + * Finally, check that the real and effective uids are what we + * expect. + */ + if (getuid() != ruid || geteuid() != euid) { + errno = EACCES; + return -1; + } + + return ret; +} blob - /dev/null blob + a9bac69f267bb7ef4314d165ddbf70dedcdc5393 (mode 644) --- /dev/null +++ msearchd/compat/stdlib.h @@ -0,0 +1,31 @@ +#include_next "stdlib.h" + +#include "../config.h" + +#ifndef __dead +# define __dead __attribute__((noreturn)) +#endif + +#if !HAVE_GETPROGNAME +const char *getprogname(void); +#endif + +#if !HAVE_SETPROCTITLE +const char *setproctitle(const char *, ...); +#endif + +#if !HAVE_FREEZERO +void freezero(void *, size_t); +#endif + +#if !HAVE_REALLOCARRAY +void *reallocarray(void *, size_t, size_t); +#endif + +#if !HAVE_RECALLOCARRAY +void *recallocarray(void *, size_t, size_t, size_t); +#endif + +#if !HAVE_STRTONUM +long long strtonum(const char *, long long, long long, const char **); +#endif blob - /dev/null blob + 94e0bbb402c943b022f5b444df9d90f0081a8d66 (mode 644) --- /dev/null +++ msearchd/compat/string.h @@ -0,0 +1,11 @@ +#include_next "string.h" + +#include "../config.h" + +#if !HAVE_STRLCPY +size_t strlcpy(char *, const char *, size_t); +#endif + +#if !HAVE_STRLCAT +size_t strlcat(char *, const char *, size_t); +#endif blob - /dev/null blob + 1c19062bf839da6e099ffca1dddcdb4070a44edf (mode 644) --- /dev/null +++ msearchd/compat/strlcat.c @@ -0,0 +1,53 @@ +/* + * Copyright (c) 1998, 2015 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. + */ + +#include +#include + +/* + * Appends src to string dst of size dsize (unlike strncat, dsize is the + * full size of dst, not space left). At most dsize-1 characters + * will be copied. Always NUL terminates (unless dsize <= strlen(dst)). + * Returns strlen(src) + MIN(dsize, strlen(initial dst)). + * If retval >= dsize, truncation occurred. + */ +size_t +strlcat(char *dst, const char *src, size_t dsize) +{ + const char *odst = dst; + const char *osrc = src; + size_t n = dsize; + size_t dlen; + + /* Find the end of dst and adjust bytes left but don't go past end. */ + while (n-- != 0 && *dst != '\0') + dst++; + dlen = dst - odst; + n = dsize - dlen; + + if (n-- == 0) + return(dlen + strlen(src)); + while (*src != '\0') { + if (n != 0) { + *dst++ = *src; + n--; + } + src++; + } + *dst = '\0'; + + return(dlen + (src - osrc)); /* count does not include NUL */ +} blob - /dev/null blob + 177ff7269492ec85c2196e31edc425107a958e4b (mode 644) --- /dev/null +++ msearchd/compat/strlcpy.c @@ -0,0 +1,48 @@ +/* + * Copyright (c) 1998, 2015 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. + */ + +#include +#include + +/* + * Copy string src to buffer dst of size dsize. At most dsize-1 + * chars will be copied. Always NUL terminates (unless dsize == 0). + * Returns strlen(src); if retval >= dsize, truncation occurred. + */ +size_t +strlcpy(char *dst, const char *src, size_t dsize) +{ + const char *osrc = src; + size_t nleft = dsize; + + /* Copy as many bytes as will fit. */ + if (nleft != 0) { + while (--nleft != 0) { + if ((*dst++ = *src++) == '\0') + break; + } + } + + /* Not enough room in dst, add NUL and traverse rest of src. */ + if (nleft == 0) { + if (dsize != 0) + *dst = '\0'; /* NUL-terminate dst */ + while (*src++) + ; + } + + return(src - osrc - 1); /* count does not include NUL */ +} blob - /dev/null blob + e1807693138c2fc6b662ac9d8859fa0f2431c360 (mode 644) --- /dev/null +++ msearchd/compat/strtonum.c @@ -0,0 +1,63 @@ +/* + * 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 + +#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 + 7a4a7d04a35fabbceb208c67135abcc5aba94972 (mode 644) --- /dev/null +++ msearchd/compat/sys/Makefile @@ -0,0 +1,11 @@ +DISTFILES = Makefile queue.h tree.h + +all: + false + +dist: + mkdir -p ${DESTDIR}/ + ${INSTALL} -m 0644 ${DISTFILES} ${DESTDIR}/ + +.PHONY: all dist +include ../../../config.mk blob - /dev/null blob + bc1568be67482bf033c0da484f8bd9fd41426d03 (mode 644) --- /dev/null +++ msearchd/compat/sys/queue.h @@ -0,0 +1,631 @@ +/* $OpenBSD: queue.h,v 1.46 2020/12/30 13:33:12 millert 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 + */ + +#ifndef _SYS_QUEUE_H_ +#define _SYS_QUEUE_H_ + +/* + * This file defines five types of data structures: singly-linked lists, + * lists, simple queues, tail queues and XOR simple 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 to 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. + * + * An XOR simple queue is used in the same way as a regular simple queue. + * The difference is that the head structure also includes a "cookie" that + * is XOR'd with the queue pointer (first, last or next) to generate the + * real pointer value. + * + * 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_INVALID ((void *)-1) +#define _Q_INVALIDATE(a) (a) = _Q_INVALID +#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) + +#define SIMPLEQ_CONCAT(head1, head2) do { \ + if (!SIMPLEQ_EMPTY((head2))) { \ + *(head1)->sqh_last = (head2)->sqh_first; \ + (head1)->sqh_last = (head2)->sqh_last; \ + SIMPLEQ_INIT((head2)); \ + } \ +} while (0) + +/* + * XOR Simple queue definitions. + */ +#define XSIMPLEQ_HEAD(name, type) \ +struct name { \ + struct type *sqx_first; /* first element */ \ + struct type **sqx_last; /* addr of last next element */ \ + unsigned long sqx_cookie; \ +} + +#define XSIMPLEQ_ENTRY(type) \ +struct { \ + struct type *sqx_next; /* next element */ \ +} + +/* + * XOR Simple queue access methods. + */ +#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \ + (unsigned long)(ptr))) +#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first)) +#define XSIMPLEQ_END(head) NULL +#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head)) +#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next)) + + +#define XSIMPLEQ_FOREACH(var, head, field) \ + for ((var) = XSIMPLEQ_FIRST(head); \ + (var) != XSIMPLEQ_END(head); \ + (var) = XSIMPLEQ_NEXT(head, var, field)) + +#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = XSIMPLEQ_FIRST(head); \ + (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \ + (var) = (tvar)) + +/* + * XOR Simple queue functions. + */ +#define XSIMPLEQ_INIT(head) do { \ + arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \ + (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ +} while (0) + +#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.sqx_next = (head)->sqx_first) == \ + XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ + (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \ +} while (0) + +#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \ + *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ +} while (0) + +#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \ + XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ + (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \ +} while (0) + +#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \ + if (((head)->sqx_first = XSIMPLEQ_XOR(head, \ + (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ +} while (0) + +#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ + if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \ + (elm)->field.sqx_next)->field.sqx_next) \ + == XSIMPLEQ_XOR(head, NULL)) \ + (head)->sqx_last = \ + XSIMPLEQ_XOR(head, &(elm)->field.sqx_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) + +#define TAILQ_CONCAT(head1, head2, field) do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ +} while (0) + +/* + * Singly-linked Tail queue declarations. + */ +#define STAILQ_HEAD(name, type) \ +struct name { \ + struct type *stqh_first; /* first element */ \ + struct type **stqh_last; /* addr of last next element */ \ +} + +#define STAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).stqh_first } + +#define STAILQ_ENTRY(type) \ +struct { \ + struct type *stqe_next; /* next element */ \ +} + +/* + * Singly-linked Tail queue access methods. + */ +#define STAILQ_FIRST(head) ((head)->stqh_first) +#define STAILQ_END(head) NULL +#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head)) +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) + +#define STAILQ_FOREACH(var, head, field) \ + for ((var) = STAILQ_FIRST(head); \ + (var) != STAILQ_END(head); \ + (var) = STAILQ_NEXT(var, field)) + +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = STAILQ_FIRST(head); \ + (var) && ((tvar) = STAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Singly-linked Tail queue functions. + */ +#define STAILQ_INIT(head) do { \ + STAILQ_FIRST((head)) = NULL; \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +#define STAILQ_INSERT_HEAD(head, elm, field) do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_FIRST((head)) = (elm); \ +} while (0) + +#define STAILQ_INSERT_TAIL(head, elm, field) do { \ + STAILQ_NEXT((elm), field) = NULL; \ + *(head)->stqh_last = (elm); \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ +} while (0) + +#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((elm), field)) == NULL)\ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_NEXT((elm), field) = (elm); \ +} while (0) + +#define STAILQ_REMOVE_HEAD(head, field) do { \ + if ((STAILQ_FIRST((head)) = \ + STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +#define STAILQ_REMOVE_AFTER(head, elm, field) do { \ + if ((STAILQ_NEXT(elm, field) = \ + STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ +} while (0) + +#define STAILQ_REMOVE(head, elm, type, field) do { \ + if (STAILQ_FIRST((head)) == (elm)) { \ + STAILQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->stqh_first; \ + while (STAILQ_NEXT(curelm, field) != (elm)) \ + curelm = STAILQ_NEXT(curelm, field); \ + STAILQ_REMOVE_AFTER(head, curelm, field); \ + } \ +} while (0) + +#define STAILQ_CONCAT(head1, head2) do { \ + if (!STAILQ_EMPTY((head2))) { \ + *(head1)->stqh_last = (head2)->stqh_first; \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_INIT((head2)); \ + } \ +} while (0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) ? NULL : \ + ((struct type *)(void *) \ + ((char *)((head)->stqh_last) - offsetof(struct type, field)))) + +#endif /* !_SYS_QUEUE_H_ */ blob - /dev/null blob + fb56e32567bed50a2455b9b8fb87e809bba9acd0 (mode 644) --- /dev/null +++ msearchd/compat/sys/tree.h @@ -0,0 +1,1012 @@ +/* $OpenBSD: tree.h,v 1.30 2020/10/10 18:03:41 otto 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 + +/* + * Local modifications: + * - dropped __unused + * - __inline -> inline + */ + +/* + * 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 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 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 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; \ + \ +static inline void \ +_name##_RBT_INIT(struct _name *head) \ +{ \ + _rb_init(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ +{ \ + return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_FIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_ROOT(struct _name *head) \ +{ \ + return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline int \ +_name##_RBT_EMPTY(struct _name *head) \ +{ \ + return _rb_empty(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MIN(struct _name *head) \ +{ \ + return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MAX(struct _name *head) \ +{ \ + return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline void \ +_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ +{ \ + _rb_set_left(_name##_RBT_TYPE, elm, left); \ +} \ + \ +static inline void \ +_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ +{ \ + _rb_set_right(_name##_RBT_TYPE, elm, right); \ +} \ + \ +static inline void \ +_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ +{ \ + _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ +} \ + \ +static inline void \ +_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ +{ \ + _rb_poison(_name##_RBT_TYPE, elm, poison); \ +} \ + \ +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 + 6452b2bf184aa60b92f3c0f69f6f9e3e50b52dcc (mode 644) --- /dev/null +++ msearchd/compat/unistd.h @@ -0,0 +1,27 @@ +#include_next "unistd.h" + +#include "../config.h" + +#if !HAVE_PLEGDE +int pledge(const char *, const char *); +#endif + +#if !HAVE_UNVEIL +int unveil(const char *, const char *); +#endif + +#if !HAVE_GETDTABLECOUNT +int getdtablecount(void); +#endif + +#if !HAVE_GETDTABLESIZE +int getdtablesize(void); +#endif + +#if !HAVE_SETRESGID +int setresgid(gid_t, gid_t, gid_t); +#endif + +#if !HAVE_SETRESUID +int setresuid(uid_t, uid_t, uid_t); +#endif blob - /dev/null blob + a6fd562ca3f2e3974dba47e0b5029eabffd51e9e (mode 644) --- /dev/null +++ msearchd/compat/unveil.c @@ -0,0 +1,7 @@ +int unveil(const char *, const char *); + +int +unveil(const char *path, const char *permissions) +{ + return 0; +} blob - /dev/null blob + 8d012e94124300b10529531bbfb0ea93cf36eca3 (mode 644) --- /dev/null +++ msearchd/compat/vasprintf.c @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2015 Ingo Schwarze + * + * 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. + * + * This fallback implementation is not efficient: + * It does the formatting twice. + * Short of fiddling with the unknown internals of the system's + * printf(3) or completely reimplementing printf(3), i can't think + * of another portable solution. + */ + +#include +#include +#include + +int +vasprintf(char **ret, const char *format, va_list ap) +{ + char buf[2]; + va_list ap2; + int sz; + + va_copy(ap2, ap); + sz = vsnprintf(buf, sizeof(buf), format, ap2); + va_end(ap2); + + if (sz != -1 && (*ret = malloc(sz + 1)) != NULL) { + if (vsnprintf(*ret, sz + 1, format, ap) == sz) + return sz; + free(*ret); + } + *ret = NULL; + return -1; +} blob - /dev/null blob + 54d89744ed6dc62d3a6774eb593141c685fd7eb6 (mode 755) --- /dev/null +++ msearchd/configure @@ -0,0 +1,217 @@ +#!/bin/sh +# +# Copyright (c) 2014, 2015, 2016 Ingo Schwarze +# Copyright (c) 2017, 2018 Kristaps Dzonsons +# Copyright (c) 2022, 2023 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. + +CDIAGFLAGS="-Wall -Wuninitialized -Wunused -Wmissing-prototypes" +CDIAGFLAGS="${CDIAGFLAGS} -Wstrict-prototypes -Wno-pointer-sign" + +# don't ship releases with -Werror +test "$RELEASE" = no && CDIAGFLAGS="${CDIAGFLAGS} -Werror" + +COMPATS= + +push_cflags() { + if ! echo "$CFLAGS" | grep -q -e "$1"; then + CFLAGS="${CFLAGS+$CFLAGS } $1" + fi +} + +push_ldflags() { + if ! echo "$LDFLAGS" | grep -q -e "$1"; then + LDFLAGS="${LDFLAGS+$LDFLAGS } $1" + fi +} + +# singletest name var extra-cflags extra-libs msg +singletest() { + msg="$5" + if [ -z "$msg" ]; then + if [ -n "$3" ]; then + msg=" ($3)" + elif [ -n "$4" ]; then + msg=" ($4)" + fi + elif [ "$msg" = no ]; then + msg="" + fi + + cat >&3 <&3 2>&3; + then + rm -f test-$1 test-$1.d + + echo "$1: $CC$msg succeeded" >&3 + echo "$1$msg: yes" + echo >&3 + + return 0 + fi + + echo "$1: $CC$msg failed with $?" >&3 + echo "$1$msg: no" + echo >&3 + + rm -f test-$1 test-$1.d + + return 1 +} + +# runtest name var extra-cflags extra-libs pkgconfig-name +runtest() { + if singletest "$1" "$2" "" ""; then + eval HAVE_$2=1 + return 0 + fi + + if [ -n "$3" -o -n "$4" ]; then + echo "retrying with ${3+$3 }$4" >&3 + if singletest "$1" "$2" "$3" "$4"; then + if [ -n "$3" ]; then + push_cflags "$3" + fi + if [ -n "$4" ]; then + push_ldflags "$4" + fi + eval HAVE_$2=1 + return 0 + fi + fi + + if [ -n "$5" -a -n "$pkgconfig" ]; then + if $pkgconfig "$5"; then + cflags="$($pkgconfig --cflags "$5")" + ldflags="$($pkgconfig --libs "$5")" + echo "retrying with $pkgconfig" >&3 + if singletest "$1" "$2" "$cflags" "$ldflags"; then + push_cflags "$cflags" + push_ldflags "$ldflags" + eval HAVE_$2=1 + return 0 + fi + fi + fi + + if [ -f compat/$1.c ]; then + COMPATS="${COMPATS+$COMPATS }compat/$1.c" + fi + + eval HAVE_$2=0 + return 1 +} + +if singletest MMD _MMD -MMD >/dev/null; then + push_cflags -MMD + echo "adding -MMD to CFLAGS" >&2 + echo "adding -MMD to CFLAGS" >&3 +fi + +if ! singletest WAIT_ANY WAIT_ANY; then + push_cflags -DWAIT_ANY=-1 +fi + +runtest __progname __PROGNAME || true +runtest err ERR || true +runtest freezero FREEZERO || true +runtest getdtablecount GETDTABLECOUNT || true +runtest getdtablesize GETDTABLESIZE || true +runtest getexecname GETEXECNAME || true +runtest getprogname GETPROGNAME || true +runtest imsg IMSG "" -lutil libimsg || true +runtest libevent LIBEVENT "" -levent libevent_core || true +runtest pledge PLEDGE || true +runtest recallocarray RECALLOCARRAY -D_OPENBSD_SOURCE || true +runtest setgroups SETGROUPS -D_BSD_SOURCE || true +runtest setproctitle SETPROCTITLE || true +runtest setresgid SETRESGID -D_GNU_SOURCE || true +runtest setresuid SETRESUID -D_GNU_SOURCE || true +runtest sqlite3 SQLITE3 "" -lsqlite3 sqlite3 || true +runtest strlcat STRLCAT || true +runtest strlcpy STRLCPY || true +runtest strtonum STRTONUM || true +runtest sys_queue SYS_QUEUE || true +runtest sys_tree SYS_TREE || true +runtest unveil UNVEIL || true +runtest vasprintf VASPRINTF -D_GNU_SOURCE || true + +if [ "$HAVE_IMSG" -eq 0 ]; then + echo do not have imsg, $HAVE_IMSG + CFLAGS="-I compat/imsg ${CFLAGS}" + COMPATS="compat/imsg/imsg.c compat/imsg/imsg-buffer.c $COMPATS" +fi + +if [ "$HAVE_SYS_QUEUE" -eq 0 -o "$HAVE_SYS_TREE" -eq 0 ]; then + CFLAGS="-I compat/sys $CFLAGS" +fi + +if [ -n "$COMPATS" ]; then + CFLAGS="-I compat $CFLAGS" +fi + +CFLAGS="$CFLAGS $CDIAGFLAGS" + +exec > config.h +echo "config.h writing..." >&2 + +cat < config.mk +echo "config.mk: writing..." >&2 + +cat < + +int +main(void) +{ + return WAIT_ANY; +} blob - /dev/null blob + 1964c2b48a27a9f94f4a1fa7427b63f653b7b3c2 (mode 644) --- /dev/null +++ msearchd/tests/__progname.c @@ -0,0 +1,10 @@ +#include + +extern const char *__progname; + +int +main(void) +{ + puts(__progname); + return 0; +} blob - /dev/null blob + 93eb816d939712b0bb93d05c88810f247ead41f7 (mode 644) --- /dev/null +++ msearchd/tests/err.c @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + warnx("%d. warnx", 1); + warn("%d. warn", 2); + err(0, "%d. err", 3); + return 1; +} blob - /dev/null blob + 1b15cbfca63d973754b5a508ee3f2dd5def3bbe9 (mode 644) --- /dev/null +++ msearchd/tests/freezero.c @@ -0,0 +1,24 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + freezero(NULL, 0); + return 0; +} blob - /dev/null blob + 67558279c11e1dd7ba8d29d10ba83b9b00e3fd68 (mode 644) --- /dev/null +++ msearchd/tests/getdtablecount.c @@ -0,0 +1,23 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + return getdtablecount() == 0; +} blob - /dev/null blob + 86fdae393a79943e168e0bef67adb83e5751218c (mode 644) --- /dev/null +++ msearchd/tests/getdtablesize.c @@ -0,0 +1,23 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + return getdtablesize() == 0; +} blob - /dev/null blob + 2c53cab9c23171ab5aeb4c66a5851dba8d12de51 (mode 644) --- /dev/null +++ msearchd/tests/getexecname.c @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + const char *progname; + + progname = getexecname(); + return (progname == NULL); +} blob - /dev/null blob + 57c0e2b059de0ac1a0662f96d0fe211a8f30e3db (mode 644) --- /dev/null +++ msearchd/tests/getprogname.c @@ -0,0 +1,23 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + return getprogname() == NULL; +} blob - /dev/null blob + 71fa2697d95bb8a131941bc54e6cb900e84c9691 (mode 644) --- /dev/null +++ msearchd/tests/imsg.c @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2021 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 +#include +#include +#include +#include + +int +main(void) +{ + struct imsgbuf buf; + + imsg_init(&buf, -1); + return 0; +} blob - /dev/null blob + e0b63cd9b08fac391097b56a76185ca4816924eb (mode 644) --- /dev/null +++ msearchd/tests/libevent.c @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2021 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 + +#include + +int +main(void) +{ + event_init(); + return 0; +} blob - /dev/null blob + 8878b01d6c97df185cfb7031e92b28545e0025a9 (mode 644) --- /dev/null +++ msearchd/tests/pledge.c @@ -0,0 +1,10 @@ +#include +#include + +int +main(void) +{ + if (pledge("stdio", NULL) == -1) + return 1; + return 0; +} blob - /dev/null blob + e0c60d7118f8b94719e18fa5efadb3daf9b36833 (mode 644) --- /dev/null +++ msearchd/tests/recallocarray.c @@ -0,0 +1,11 @@ +#include + +int +main(void) +{ + void *p; + + if ((p = calloc(2, 2)) == NULL) + return 1; + return !recallocarray(p, 2, 3, 2); +} blob - /dev/null blob + 3c972c73ae245c44960d431c192d4cc52f95994a (mode 644) --- /dev/null +++ msearchd/tests/setgroups.c @@ -0,0 +1,33 @@ +/* + * Copyright (c) 2021 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 +#include +#include +#include + +int +main(void) +{ + struct passwd *pw; + + pw = getpwnam("www"); + if (pw == NULL) + return 1; + + setgroups(1, &pw->pw_gid); + return 0; +} blob - /dev/null blob + d54a63e74996e9df0d6a249669510f7cad852ecd (mode 644) --- /dev/null +++ msearchd/tests/setproctitle.c @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2021 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. + */ + +/* + * FreeBSD has setproctitle in a different header than OpenBSD. + */ + +#include + +#include +#include + +int +main(void) +{ + setproctitle("%s", "frobnicator"); + return 0; +} blob - /dev/null blob + 616458f82280192cdb500175616ed252dfe19928 (mode 644) --- /dev/null +++ msearchd/tests/setresgid.c @@ -0,0 +1,8 @@ +#include +#include + +int +main(void) +{ + return setresgid(-1, -1, -1) == -1; +} blob - /dev/null blob + 0f3f65c864ef1d839583399c33676500daf4c72a (mode 644) --- /dev/null +++ msearchd/tests/setresuid.c @@ -0,0 +1,8 @@ +#include +#include + +int +main(void) +{ + return setresuid(-1, -1, -1) == -1; +} blob - /dev/null blob + 82b00642219beb04454c23fd43b4152f2b8715bd (mode 644) --- /dev/null +++ msearchd/tests/sqlite3.c @@ -0,0 +1,15 @@ +/* public domain */ + +#include +#include + +int +main(void) +{ + sqlite3 *db; + + sqlite3_open_v2("dummy", &db, SQLITE_OPEN_READONLY, NULL); + sqlite3_close(db); + + return (0); +} blob - /dev/null blob + 0a005c57f59ab5c0b9c5cb707940cb875ce21dbb (mode 644) --- /dev/null +++ msearchd/tests/strlcat.c @@ -0,0 +1,25 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + char buf[3] = "a"; + return ! (strlcat(buf, "b", sizeof(buf)) == 2 && + buf[0] == 'a' && buf[1] == 'b' && buf[2] == '\0'); +} blob - /dev/null blob + d1789354e72631744c3a953289693faa450da222 (mode 644) --- /dev/null +++ msearchd/tests/strlcpy.c @@ -0,0 +1,25 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + char buf[2] = ""; + return ! (strlcpy(buf, "a", sizeof(buf)) == 1 && + buf[0] == 'a' && buf[1] == '\0'); +} blob - /dev/null blob + 6e2aad2efbc46b09473e200b9a648019bdde8554 (mode 644) --- /dev/null +++ msearchd/tests/strtonum.c @@ -0,0 +1,27 @@ +/* + * Copyright (c) 2021 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 + +int +main(void) +{ + const char *str = "42", *errstr; + int res; + + res = strtonum(str, 1, 64, &errstr); + return res != 42 || errstr != NULL; +} blob - /dev/null blob + 81d3c6166446ea4d4da6944141bfff27fe02d9a5 (mode 644) --- /dev/null +++ msearchd/tests/sys_queue.c @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2021 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 + +#include + +TAILQ_HEAD(tailhead, entry) head; +struct entry { + TAILQ_ENTRY(entry) entries; +} *np, *nt; + +int +main(void) +{ + TAILQ_INIT(&head); + TAILQ_FOREACH_SAFE(np, &head, entries, nt) { + /* nop */; + } + + return 0; +} blob - /dev/null blob + 795c578610adb6931f3ba912d4a0152822d044c2 (mode 644) --- /dev/null +++ msearchd/tests/sys_tree.c @@ -0,0 +1,40 @@ +/* + * Copyright (c) 2021 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 + +#include + +struct node { + int id; + SPLAY_ENTRY(node) nodes; +}; +SPLAY_HEAD(node_tree, node); + +int +node_cmp(struct node *a, struct node *b) +{ + return (a->id - b->id); +} + +SPLAY_PROTOTYPE(node_tree, node, nodes, node_cmp); +SPLAY_GENERATE(node_tree, node, nodes, node_cmp); + +int +main(void) +{ + return 0; +} blob - /dev/null blob + 0582be2a1f74f3d5d0728115dd45ac33a069ee81 (mode 644) --- /dev/null +++ msearchd/tests/unveil.c @@ -0,0 +1,10 @@ +#include +#include + +int +main(void) +{ + if (unveil(".", "r") == -1) + return 1; + return 0; +} blob - /dev/null blob + 2d1ac0b1d15ccd93ef5b50e92cb00d65f009f3b0 (mode 644) --- /dev/null +++ msearchd/tests/vasprintf.c @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2021 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 +#include +#include + +static int testfn(char **, const char*, ...); + +static int +testfn(char **ret, const char *fmt, ...) +{ + va_list ap; + int irc; + + va_start(ap, fmt); + irc = vasprintf(ret, fmt, ap); + va_end(ap); + + return irc; +} + +int +main(void) +{ + char *ret; + + if (testfn(&ret, "%s.", "Text") != 5) + return 1; + if (strcmp(ret, "Text.")) + return 2; + return 0; +} blob - /dev/null blob + 3cdc0706ba979b3e31b3d45017d2d5b5e04ab998 (mode 644) --- /dev/null +++ templates/Makefile @@ -0,0 +1,20 @@ +DISTFILES = Makefile foot.html head.html index-header.html \ + logo-small.html search-header.html search.html + +all: + false + +dist: + mkdir -p ${DESTDIR}/ + ${INSTALL} -m 0644 ${DISTFILES} ${DESTDIR}/ + +install: + mkdir -p ${DESTDIR}${SYSCONFDIR}/gotmarc/ + ${INSTALL_DATA} ${DISTFILES} ${DESTDIR}${SYSCONFDIR}/gotmarc/ + +uninstall: + rm -f ${DESTDIR}${SYSCONFDIR}/gotmarc/${DISTFILES} + +.PHONY: all dist install uninstall + +include ../config.mk