diff options
Diffstat (limited to 'compat')
| -rw-r--r-- | compat/asprintf.c | 65 | ||||
| -rw-r--r-- | compat/b64_ntop.c | 182 | ||||
| -rw-r--r-- | compat/bitstring.h | 128 | ||||
| -rw-r--r-- | compat/cfmakeraw.c | 30 | ||||
| -rw-r--r-- | compat/closefrom.c | 109 | ||||
| -rw-r--r-- | compat/daemon.c | 65 | ||||
| -rw-r--r-- | compat/fgetln.c | 61 | ||||
| -rw-r--r-- | compat/forkpty-aix.c | 115 | ||||
| -rw-r--r-- | compat/forkpty-hpux.c | 87 | ||||
| -rw-r--r-- | compat/forkpty-sunos.c | 88 | ||||
| -rw-r--r-- | compat/fparseln.c | 221 | ||||
| -rw-r--r-- | compat/getopt.c | 114 | ||||
| -rw-r--r-- | compat/imsg-buffer.c | 307 | ||||
| -rw-r--r-- | compat/imsg.c | 336 | ||||
| -rw-r--r-- | compat/imsg.h | 114 | ||||
| -rw-r--r-- | compat/openat.c | 65 | ||||
| -rw-r--r-- | compat/queue.h | 568 | ||||
| -rw-r--r-- | compat/reallocarray.c | 40 | ||||
| -rw-r--r-- | compat/setenv.c | 47 | ||||
| -rw-r--r-- | compat/strcasestr.c | 60 | ||||
| -rw-r--r-- | compat/strlcat.c | 57 | ||||
| -rw-r--r-- | compat/strlcpy.c | 53 | ||||
| -rw-r--r-- | compat/strsep.c | 71 | ||||
| -rw-r--r-- | compat/strtonum.c | 67 | ||||
| -rw-r--r-- | compat/tree.h | 748 | ||||
| -rw-r--r-- | compat/unvis.c | 281 | ||||
| -rw-r--r-- | compat/vis.c | 242 | ||||
| -rw-r--r-- | compat/vis.h | 85 |
28 files changed, 4406 insertions, 0 deletions
diff --git a/compat/asprintf.c b/compat/asprintf.c new file mode 100644 index 00000000..5ed1c48c --- /dev/null +++ b/compat/asprintf.c @@ -0,0 +1,65 @@ +/* + * Copyright (c) 2006 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <stdarg.h> +#include <stdio.h> +#ifdef HAVE_STDINT_H +#include <stdint.h> +#else +#include <inttypes.h> +#endif +#include <string.h> + +#include "tmux.h" + +int +asprintf(char **ret, const char *fmt, ...) +{ + va_list ap; + int n; + + va_start(ap, fmt); + n = vasprintf(ret, fmt, ap); + va_end(ap); + + return (n); +} + +int +vasprintf(char **ret, const char *fmt, va_list ap) +{ + int n; + va_list ap2; + + va_copy(ap2, ap); + + if ((n = vsnprintf(NULL, 0, fmt, ap)) < 0) + goto error; + + *ret = xmalloc(n + 1); + if ((n = vsnprintf(*ret, n + 1, fmt, ap2)) < 0) { + free(*ret); + goto error; + } + va_end(ap2); + + return (n); + +error: + va_end(ap2); + *ret = NULL; + return (-1); +} diff --git a/compat/b64_ntop.c b/compat/b64_ntop.c new file mode 100644 index 00000000..2b4dc2d4 --- /dev/null +++ b/compat/b64_ntop.c @@ -0,0 +1,182 @@ +/* + * Copyright (c) 1996, 1998 by Internet Software Consortium. + * + * 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 INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM 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. + */ + +/* + * Portions Copyright (c) 1995 by International Business Machines, Inc. + * + * International Business Machines, Inc. (hereinafter called IBM) grants + * permission under its copyrights to use, copy, modify, and distribute this + * Software with or without fee, provided that the above copyright notice and + * all paragraphs of this notice appear in all copies, and that the name of IBM + * not be used in connection with the marketing of any product incorporating + * the Software or modifications thereof, without specific, written prior + * permission. + * + * To the extent it has a right to do so, IBM grants an immunity from suit + * under its patents, if any, for the use, sale or manufacture of products to + * the extent that such products are used for performing Domain Name System + * dynamic updates in TCP/IP networks by means of the Software. No immunity is + * granted for any product per se or for any other function of any product. + * + * THE SOFTWARE IS PROVIDED "AS IS", AND IBM DISCLAIMS ALL WARRANTIES, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, + * DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER ARISING + * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE, EVEN + * IF IBM IS APPRISED OF THE POSSIBILITY OF SUCH DAMAGES. + */ + +#include <sys/types.h> +#include <sys/param.h> +#include <sys/socket.h> + +#include <netinet/in.h> +#include <arpa/inet.h> + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define Assert(Cond) if (!(Cond)) abort() + +static const char Base64[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; +static const char Pad64 = '='; + +/* (From RFC1521 and draft-ietf-dnssec-secext-03.txt) + The following encoding technique is taken from RFC 1521 by Borenstein + and Freed. It is reproduced here in a slightly edited form for + convenience. + + A 65-character subset of US-ASCII is used, enabling 6 bits to be + represented per printable character. (The extra 65th character, "=", + is used to signify a special processing function.) + + The encoding process represents 24-bit groups of input bits as output + strings of 4 encoded characters. Proceeding from left to right, a + 24-bit input group is formed by concatenating 3 8-bit input groups. + These 24 bits are then treated as 4 concatenated 6-bit groups, each + of which is translated into a single digit in the base64 alphabet. + + Each 6-bit group is used as an index into an array of 64 printable + characters. The character referenced by the index is placed in the + output string. + + Table 1: The Base64 Alphabet + + Value Encoding Value Encoding Value Encoding Value Encoding + 0 A 17 R 34 i 51 z + 1 B 18 S 35 j 52 0 + 2 C 19 T 36 k 53 1 + 3 D 20 U 37 l 54 2 + 4 E 21 V 38 m 55 3 + 5 F 22 W 39 n 56 4 + 6 G 23 X 40 o 57 5 + 7 H 24 Y 41 p 58 6 + 8 I 25 Z 42 q 59 7 + 9 J 26 a 43 r 60 8 + 10 K 27 b 44 s 61 9 + 11 L 28 c 45 t 62 + + 12 M 29 d 46 u 63 / + 13 N 30 e 47 v + 14 O 31 f 48 w (pad) = + 15 P 32 g 49 x + 16 Q 33 h 50 y + + Special processing is performed if fewer than 24 bits are available + at the end of the data being encoded. A full encoding quantum is + always completed at the end of a quantity. When fewer than 24 input + bits are available in an input group, zero bits are added (on the + right) to form an integral number of 6-bit groups. Padding at the + end of the data is performed using the '=' character. + + Since all base64 input is an integral number of octets, only the + ------------------------------------------------- + following cases can arise: + + (1) the final quantum of encoding input is an integral + multiple of 24 bits; here, the final unit of encoded + output will be an integral multiple of 4 characters + with no "=" padding, + (2) the final quantum of encoding input is exactly 8 bits; + here, the final unit of encoded output will be two + characters followed by two "=" padding characters, or + (3) the final quantum of encoding input is exactly 16 bits; + here, the final unit of encoded output will be three + characters followed by one "=" padding character. + */ + +int +b64_ntop(uint8_t const *src, size_t srclength, char *target, size_t targsize) { + size_t datalength = 0; + uint8_t input[3]; + uint8_t output[4]; + size_t i; + + while (2 < srclength) { + input[0] = *src++; + input[1] = *src++; + input[2] = *src++; + srclength -= 3; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + output[3] = input[2] & 0x3f; + Assert(output[0] < 64); + Assert(output[1] < 64); + Assert(output[2] < 64); + Assert(output[3] < 64); + + if (datalength + 4 > targsize) + return (-1); + target[datalength++] = Base64[output[0]]; + target[datalength++] = Base64[output[1]]; + target[datalength++] = Base64[output[2]]; + target[datalength++] = Base64[output[3]]; + } + + /* Now we worry about padding. */ + if (0 != srclength) { + /* Get what's left. */ + input[0] = input[1] = input[2] = '\0'; + for (i = 0; i < srclength; i++) + input[i] = *src++; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + Assert(output[0] < 64); + Assert(output[1] < 64); + Assert(output[2] < 64); + + if (datalength + 4 > targsize) + return (-1); + target[datalength++] = Base64[output[0]]; + target[datalength++] = Base64[output[1]]; + if (srclength == 1) + target[datalength++] = Pad64; + else + target[datalength++] = Base64[output[2]]; + target[datalength++] = Pad64; + } + if (datalength >= targsize) + return (-1); + target[datalength] = '\0'; /* Returned value doesn't count \0. */ + return (datalength); +} diff --git a/compat/bitstring.h b/compat/bitstring.h new file mode 100644 index 00000000..8fc3423e --- /dev/null +++ b/compat/bitstring.h @@ -0,0 +1,128 @@ +/* $OpenBSD: bitstring.h,v 1.5 2003/06/02 19:34:12 millert Exp $ */ +/* $NetBSD: bitstring.h,v 1.5 1997/05/14 15:49:55 pk Exp $ */ + +/* + * Copyright (c) 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Paul Vixie. + * + * 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. + * + * @(#)bitstring.h 8.1 (Berkeley) 7/19/93 + */ + +#ifndef _BITSTRING_H_ +#define _BITSTRING_H_ + +/* modified for SV/AT and bitstring bugfix by M.R.Murphy, 11oct91 + * bitstr_size changed gratuitously, but shorter + * bit_alloc spelling error fixed + * the following were efficient, but didn't work, they've been made to + * work, but are no longer as efficient :-) + * bit_nclear, bit_nset, bit_ffc, bit_ffs + */ +typedef unsigned char bitstr_t; + +/* internal macros */ + /* byte of the bitstring bit is in */ +#define _bit_byte(bit) \ + ((bit) >> 3) + + /* mask for the bit within its byte */ +#define _bit_mask(bit) \ + (1 << ((bit)&0x7)) + +/* external macros */ + /* bytes in a bitstring of nbits bits */ +#define bitstr_size(nbits) \ + (((nbits) + 7) >> 3) + + /* allocate a bitstring */ +#define bit_alloc(nbits) \ + (bitstr_t *)calloc((size_t)bitstr_size(nbits), sizeof(bitstr_t)) + + /* allocate a bitstring on the stack */ +#define bit_decl(name, nbits) \ + ((name)[bitstr_size(nbits)]) + + /* is bit N of bitstring name set? */ +#define bit_test(name, bit) \ + ((name)[_bit_byte(bit)] & _bit_mask(bit)) + + /* set bit N of bitstring name */ +#define bit_set(name, bit) \ + ((name)[_bit_byte(bit)] |= _bit_mask(bit)) + + /* clear bit N of bitstring name */ +#define bit_clear(name, bit) \ + ((name)[_bit_byte(bit)] &= ~_bit_mask(bit)) + + /* clear bits start ... stop in bitstring */ +#define bit_nclear(name, start, stop) do { \ + register bitstr_t *_name = name; \ + register int _start = start, _stop = stop; \ + while (_start <= _stop) { \ + bit_clear(_name, _start); \ + _start++; \ + } \ +} while(0) + + /* set bits start ... stop in bitstring */ +#define bit_nset(name, start, stop) do { \ + register bitstr_t *_name = name; \ + register int _start = start, _stop = stop; \ + while (_start <= _stop) { \ + bit_set(_name, _start); \ + _start++; \ + } \ +} while(0) + + /* find first bit clear in name */ +#define bit_ffc(name, nbits, value) do { \ + register bitstr_t *_name = name; \ + register int _bit, _nbits = nbits, _value = -1; \ + for (_bit = 0; _bit < _nbits; ++_bit) \ + if (!bit_test(_name, _bit)) { \ + _value = _bit; \ + break; \ + } \ + *(value) = _value; \ +} while(0) + + /* find first bit set in name */ +#define bit_ffs(name, nbits, value) do { \ + register bitstr_t *_name = name; \ + register int _bit, _nbits = nbits, _value = -1; \ + for (_bit = 0; _bit < _nbits; ++_bit) \ + if (bit_test(_name, _bit)) { \ + _value = _bit; \ + break; \ + } \ + *(value) = _value; \ +} while(0) + +#endif /* !_BITSTRING_H_ */ diff --git a/compat/cfmakeraw.c b/compat/cfmakeraw.c new file mode 100644 index 00000000..d8794081 --- /dev/null +++ b/compat/cfmakeraw.c @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2013 Dagobert Michelsen + * Copyright (c) 2013 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <string.h> + +#include "tmux.h" + +void +cfmakeraw(struct termios *tio) +{ + tio->c_iflag &= ~(IGNBRK|BRKINT|PARMRK|ISTRIP|INLCR|IGNCR|ICRNL|IXON); + tio->c_oflag &= ~OPOST; + tio->c_lflag &= ~(ECHO|ECHONL|ICANON|ISIG|IEXTEN); + tio->c_cflag &= ~(CSIZE|PARENB); + tio->c_cflag |= CS8; +} diff --git a/compat/closefrom.c b/compat/closefrom.c new file mode 100644 index 00000000..8c650aa5 --- /dev/null +++ b/compat/closefrom.c @@ -0,0 +1,109 @@ +/* + * Copyright (c) 2004-2005 Todd C. Miller <Todd.Miller@courtesan.com> + * + * 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 HAVE_CLOSEFROM + +#include <sys/types.h> +#include <sys/param.h> +#include <unistd.h> +#include <stdio.h> +#ifdef HAVE_FCNTL_H +# include <fcntl.h> +#endif +#include <limits.h> +#include <stdlib.h> +#include <stddef.h> +#include <string.h> +#include <unistd.h> +#ifdef HAVE_DIRENT_H +# include <dirent.h> +# define NAMLEN(dirent) strlen((dirent)->d_name) +#else +# define dirent direct +# define NAMLEN(dirent) (dirent)->d_namlen +# ifdef HAVE_SYS_NDIR_H +# include <sys/ndir.h> +# endif +# ifdef HAVE_SYS_DIR_H +# include <sys/dir.h> +# endif +# ifdef HAVE_NDIR_H +# include <ndir.h> +# endif +#endif + +#include "tmux.h" + +#ifndef OPEN_MAX +# define OPEN_MAX 256 +#endif + +#if 0 +__unused static const char rcsid[] = "$Sudo: closefrom.c,v 1.11 2006/08/17 15:26:54 millert Exp $"; +#endif /* lint */ + +/* + * Close all file descriptors greater than or equal to lowfd. + */ +#ifdef HAVE_FCNTL_CLOSEM +void +closefrom(int lowfd) +{ + (void) fcntl(lowfd, F_CLOSEM, 0); +} +#else +void +closefrom(int lowfd) +{ + long fd, maxfd; +#if defined(HAVE_DIRFD) && defined(HAVE_PROC_PID) + char fdpath[PATH_MAX], *endp; + struct dirent *dent; + DIR *dirp; + int len; + + /* Check for a /proc/$$/fd directory. */ + len = snprintf(fdpath, sizeof(fdpath), "/proc/%ld/fd", (long)getpid()); + if (len > 0 && (size_t)len <= sizeof(fdpath) && (dirp = opendir(fdpath))) { + while ((dent = readdir(dirp)) != NULL) { + fd = strtol(dent->d_name, &endp, 10); + if (dent->d_name != endp && *endp == '\0' && + fd >= 0 && fd < INT_MAX && fd >= lowfd && fd != dirfd(dirp)) + (void) close((int) fd); + } + (void) closedir(dirp); + } else +#endif + { + /* + * Fall back on sysconf() or getdtablesize(). We avoid checking + * resource limits since it is possible to open a file descriptor + * and then drop the rlimit such that it is below the open fd. + */ +#ifdef HAVE_SYSCONF + maxfd = sysconf(_SC_OPEN_MAX); +#else + maxfd = getdtablesize(); +#endif /* HAVE_SYSCONF */ + if (maxfd < 0) + maxfd = OPEN_MAX; + + for (fd = lowfd; fd < maxfd; fd++) + (void) close((int) fd); + } +} +#endif /* !HAVE_FCNTL_CLOSEM */ +#endif /* HAVE_CLOSEFROM */ diff --git a/compat/daemon.c b/compat/daemon.c new file mode 100644 index 00000000..3e87874b --- /dev/null +++ b/compat/daemon.c @@ -0,0 +1,65 @@ +/* $OpenBSD: daemon.c,v 1.6 2005/08/08 08:05:33 espie Exp $ */ +/*- + * Copyright (c) 1990, 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. + */ + +#include <fcntl.h> +#include <unistd.h> +#include <stdlib.h> + +#include "tmux.h" + +int +daemon(int nochdir, int noclose) +{ + int fd; + + switch (fork()) { + case -1: + return (-1); + case 0: + break; + default: + _exit(0); + } + + if (setsid() == -1) + return (-1); + + if (!nochdir) + (void)chdir("/"); + + if (!noclose && (fd = open(_PATH_DEVNULL, O_RDWR, 0)) != -1) { + (void)dup2(fd, STDIN_FILENO); + (void)dup2(fd, STDOUT_FILENO); + (void)dup2(fd, STDERR_FILENO); + if (fd > 2) + (void)close (fd); + } + return (0); +} diff --git a/compat/fgetln.c b/compat/fgetln.c new file mode 100644 index 00000000..0ad6378a --- /dev/null +++ b/compat/fgetln.c @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2015 Joerg Jung <jung@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * portable fgetln() version, NOT reentrant + */ + +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> + +#include "tmux.h" + +char * +fgetln(FILE *fp, size_t *len) +{ + static char *buf = NULL; + static size_t bufsz = 0; + size_t r = 0; + char *p; + int c, e; + + if (!fp || !len) { + errno = EINVAL; + return NULL; + } + if (!buf) { + if (!(buf = calloc(1, BUFSIZ))) + return NULL; + bufsz = BUFSIZ; + } + while ((c = getc(fp)) != EOF) { + buf[r++] = c; + if (r == bufsz) { + if (!(p = reallocarray(buf, 2, bufsz))) { + e = errno; + free(buf); + errno = e; + buf = NULL, bufsz = 0; + return NULL; + } + buf = p, bufsz = 2 * bufsz; + } + if (c == '\n') + break; + } + return (*len = r) ? buf : NULL; +} diff --git a/compat/forkpty-aix.c b/compat/forkpty-aix.c new file mode 100644 index 00000000..2557ebf7 --- /dev/null +++ b/compat/forkpty-aix.c @@ -0,0 +1,115 @@ +/* + * Copyright (c) 2009 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <sys/types.h> +#include <sys/ioctl.h> + +#include <fcntl.h> +#include <stdlib.h> +#include <stropts.h> +#include <unistd.h> +#include <errno.h> + +#include "tmux.h" + +pid_t +forkpty(int *master, unused char *name, struct termios *tio, struct winsize *ws) +{ + int slave = -1, fd, pipe_fd[2]; + char *path, dummy; + pid_t pid; + + if (pipe(pipe_fd) == -1) + return (-1); + + if ((*master = open("/dev/ptc", O_RDWR|O_NOCTTY)) == -1) + goto out; + + if ((path = ttyname(*master)) == NULL) + goto out; + + if (name != NULL) + strlcpy(name, path, TTY_NAME_MAX); + + if ((slave = open(path, O_RDWR|O_NOCTTY)) == -1) + goto out; + + switch (pid = fork()) { + case -1: + goto out; + case 0: + close(*master); + + close(pipe_fd[1]); + while (read(pipe_fd[0], &dummy, 1) == -1) { + if (errno != EINTR) + break; + } + close(pipe_fd[0]); + + fd = open(_PATH_TTY, O_RDWR|O_NOCTTY); + if (fd >= 0) { + ioctl(fd, TIOCNOTTY, NULL); + close(fd); + } + + if (setsid() < 0) + fatal("setsid"); + + fd = open(_PATH_TTY, O_RDWR|O_NOCTTY); + if (fd >= 0) + fatalx("open succeeded (failed to disconnect)"); + + fd = open(path, O_RDWR); + if (fd < 0) + fatal("open failed"); + close(fd); + + fd = open("/dev/tty", O_WRONLY); + if (fd < 0) + fatal("open failed"); + close(fd); + + if (tio != NULL && tcsetattr(slave, TCSAFLUSH, tio) == -1) + fatal("tcsetattr failed"); + if (ioctl(slave, TIOCSWINSZ, ws) == -1) + fatal("ioctl failed"); + + dup2(slave, 0); + dup2(slave, 1); + dup2(slave, 2); + if (slave > 2) + close(slave); + + return (0); + } + + close(slave); + + close(pipe_fd[0]); + close(pipe_fd[1]); + return (pid); + +out: + if (*master != -1) + close(*master); + if (slave != -1) + close(slave); + + close(pipe_fd[0]); + close(pipe_fd[1]); + return (-1); +} diff --git a/compat/forkpty-hpux.c b/compat/forkpty-hpux.c new file mode 100644 index 00000000..09b27d08 --- /dev/null +++ b/compat/forkpty-hpux.c @@ -0,0 +1,87 @@ +/* + * Copyright (c) 2008 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <sys/types.h> +#include <sys/ioctl.h> + +#include <fcntl.h> +#include <stdlib.h> +#include <stropts.h> +#include <unistd.h> + +#include "tmux.h" + +pid_t +forkpty(int *master, char *name, struct termios *tio, struct winsize *ws) +{ + int slave = -1; + char *path; + pid_t pid; + + if ((*master = open("/dev/ptmx", O_RDWR|O_NOCTTY)) == -1) + return (-1); + if (grantpt(*master) != 0) + goto out; + if (unlockpt(*master) != 0) + goto out; + + if ((path = ptsname(*master)) == NULL) + goto out; + if (name != NULL) + strlcpy(name, path, TTY_NAME_MAX); + if ((slave = open(path, O_RDWR|O_NOCTTY)) == -1) + goto out; + + switch (pid = fork()) { + case -1: + goto out; + case 0: + close(*master); + + setsid(); +#ifdef TIOCSCTTY + if (ioctl(slave, TIOCSCTTY, NULL) == -1) + fatal("ioctl failed"); +#endif + + if (ioctl(slave, I_PUSH, "ptem") == -1) + fatal("ioctl failed"); + if (ioctl(slave, I_PUSH, "ldterm") == -1) + fatal("ioctl failed"); + + if (tio != NULL && tcsetattr(slave, TCSAFLUSH, tio) == -1) + fatal("tcsetattr failed"); + if (ioctl(slave, TIOCSWINSZ, ws) == -1) + fatal("ioctl failed"); + + dup2(slave, 0); + dup2(slave, 1); + dup2(slave, 2); + if (slave > 2) + close(slave); + return (0); + } + + close(slave); + return (pid); + +out: + if (*master != -1) + close(*master); + if (slave != -1) + close(slave); + return (-1); +} diff --git a/compat/forkpty-sunos.c b/compat/forkpty-sunos.c new file mode 100644 index 00000000..9abda46c --- /dev/null +++ b/compat/forkpty-sunos.c @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2008 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <sys/types.h> +#include <sys/ioctl.h> + +#include <fcntl.h> +#include <stdlib.h> +#include <strings.h> +#include <stropts.h> +#include <unistd.h> + +#include "tmux.h" + +pid_t +forkpty(int *master, char *name, struct termios *tio, struct winsize *ws) +{ + int slave = -1; + char *path; + pid_t pid; + + if ((*master = open("/dev/ptmx", O_RDWR|O_NOCTTY)) == -1) + return (-1); + if (grantpt(*master) != 0) + goto out; + if (unlockpt(*master) != 0) + goto out; + + if ((path = ptsname(*master)) == NULL) + goto out; + if (name != NULL) + strlcpy(name, path, TTY_NAME_MAX); + if ((slave = open(path, O_RDWR|O_NOCTTY)) == -1) + goto out; + + switch (pid = fork()) { + case -1: + goto out; + case 0: + close(*master); + + setsid(); +#ifdef TIOCSCTTY + if (ioctl(slave, TIOCSCTTY, NULL) == -1) + fatal("ioctl failed"); +#endif + + if (ioctl(slave, I_PUSH, "ptem") == -1) + fatal("ioctl failed"); + if (ioctl(slave, I_PUSH, "ldterm") == -1) + fatal("ioctl failed"); + + if (tio != NULL && tcsetattr(slave, TCSAFLUSH, tio) == -1) + fatal("tcsetattr failed"); + if (ioctl(slave, TIOCSWINSZ, ws) == -1) + fatal("ioctl failed"); + + dup2(slave, 0); + dup2(slave, 1); + dup2(slave, 2); + if (slave > 2) + close(slave); + return (0); + } + + close(slave); + return (pid); + +out: + if (*master != -1) + close(*master); + if (slave != -1) + close(slave); + return (-1); +} diff --git a/compat/fparseln.c b/compat/fparseln.c new file mode 100644 index 00000000..348bfa14 --- /dev/null +++ b/compat/fparseln.c @@ -0,0 +1,221 @@ +/* $OpenBSD: fparseln.c,v 1.6 2005/08/02 21:46:23 espie Exp $ */ +/* $NetBSD: fparseln.c,v 1.7 1999/07/02 15:49:12 simonb Exp $ */ + +/* + * Copyright (c) 1997 Christos Zoulas. 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by Christos Zoulas. + * 4. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * 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. + */ + +/* OPENBSD ORIGINAL: lib/libutil/fparseln.c */ + +#include <sys/types.h> + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +#include "tmux.h" + +/* + * fparseln() specific operation flags. + */ +#define FPARSELN_UNESCESC 0x01 +#define FPARSELN_UNESCCONT 0x02 +#define FPARSELN_UNESCCOMM 0x04 +#define FPARSELN_UNESCREST 0x08 +#define FPARSELN_UNESCALL 0x0f + +static int isescaped(const char *, const char *, int); + +/* isescaped(): + * Return true if the character in *p that belongs to a string + * that starts in *sp, is escaped by the escape character esc. + */ +static int +isescaped(const char *sp, const char *p, int esc) +{ + const char *cp; + size_t ne; + + /* No escape character */ + if (esc == '\0') + return 1; + + /* Count the number of escape characters that precede ours */ + for (ne = 0, cp = p; --cp >= sp && *cp == esc; ne++) + continue; + + /* Return true if odd number of escape characters */ + return (ne & 1) != 0; +} + + +/* fparseln(): + * Read a line from a file parsing continuations ending in \ + * and eliminating trailing newlines, or comments starting with + * the comment char. + */ +char * +fparseln(FILE *fp, size_t *size, size_t *lineno, const char str[3], + int flags) +{ + static const char dstr[3] = { '\\', '\\', '#' }; + char *buf = NULL, *ptr, *cp, esc, con, nl, com; + size_t s, len = 0; + int cnt = 1; + + if (str == NULL) + str = dstr; + + esc = str[0]; + con = str[1]; + com = str[2]; + + /* + * XXX: it would be cool to be able to specify the newline character, + * but unfortunately, fgetln does not let us + */ + nl = '\n'; + + while (cnt) { + cnt = 0; + + if (lineno) + (*lineno)++; + + if ((ptr = fgetln(fp, &s)) == NULL) + break; + + if (s && com) { /* Check and eliminate comments */ + for (cp = ptr; cp < ptr + s; cp++) + if (*cp == com && !isescaped(ptr, cp, esc)) { + s = cp - ptr; + cnt = s == 0 && buf == NULL; + break; + } + } + + if (s && nl) { /* Check and eliminate newlines */ + cp = &ptr[s - 1]; + + if (*cp == nl) + s--; /* forget newline */ + } + + if (s && con) { /* Check and eliminate continuations */ + cp = &ptr[s - 1]; + + if (*cp == con && !isescaped(ptr, cp, esc)) { + s--; /* forget escape */ + cnt = 1; + } + } + + if (s == 0 && buf != NULL) + continue; + + if ((cp = realloc(buf, len + s + 1)) == NULL) { + free(buf); + return NULL; + } + buf = cp; + + (void) memcpy(buf + len, ptr, s); + len += s; + buf[len] = '\0'; + } + + if ((flags & FPARSELN_UNESCALL) != 0 && esc && buf != NULL && + strchr(buf, esc) != NULL) { + ptr = cp = buf; + while (cp[0] != '\0') { + int skipesc; + + while (cp[0] != '\0' && cp[0] != esc) + *ptr++ = *cp++; + if (cp[0] == '\0' || cp[1] == '\0') + break; + + skipesc = 0; + if (cp[1] == com) + skipesc += (flags & FPARSELN_UNESCCOMM); + if (cp[1] == con) + skipesc += (flags & FPARSELN_UNESCCONT); + if (cp[1] == esc) + skipesc += (flags & FPARSELN_UNESCESC); + if (cp[1] != com && cp[1] != con && cp[1] != esc) + skipesc = (flags & FPARSELN_UNESCREST); + + if (skipesc) + cp++; + else + *ptr++ = *cp++; + *ptr++ = *cp++; + } + *ptr = '\0'; + len = strlen(buf); + } + + if (size) + *size = len; + return buf; +} + +#ifdef TEST + +int main(int, char **); + +int +main(argc, argv) + int argc; + char **argv; +{ + char *ptr; + size_t size, line; + + line = 0; + while ((ptr = fparseln(stdin, &size, &line, NULL, + FPARSELN_UNESCALL)) != NULL) + printf("line %d (%d) |%s|\n", line, size, ptr); + return 0; +} + +/* + +# This is a test +line 1 +line 2 \ +line 3 # Comment +line 4 \# Not comment \\\\ + +# And a comment \ +line 5 \\\ +line 6 + +*/ + +#endif /* TEST */ diff --git a/compat/getopt.c b/compat/getopt.c new file mode 100644 index 00000000..9cd3b3d2 --- /dev/null +++ b/compat/getopt.c @@ -0,0 +1,114 @@ +/* + * Copyright (c) 1987, 1993, 1994 + * 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. + */ + +/* OPENBSD ORIGINAL: lib/libc/stdlib/getopt.c */ + +#include "tmux.h" + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +int BSDopterr = 1, /* if error message should be printed */ + BSDoptind = 1, /* index into parent argv vector */ + BSDoptopt, /* character checked for validity */ + BSDoptreset; /* reset getopt */ +char *BSDoptarg; /* argument associated with option */ + +#define BADCH (int)'?' +#define BADARG (int)':' +#define EMSG "" + +/* + * getopt -- + * Parse argc/argv argument vector. + */ +int +BSDgetopt(int nargc, char *const *nargv, const char *ostr) +{ + static const char *place = EMSG; /* option letter processing */ + char *oli; /* option letter list index */ + + if (ostr == NULL) + return (-1); + + if (BSDoptreset || !*place) { /* update scanning pointer */ + BSDoptreset = 0; + if (BSDoptind >= nargc || *(place = nargv[BSDoptind]) != '-') { + place = EMSG; + return (-1); + } + if (place[1] && *++place == '-') { /* found "--" */ + if (place[1]) + return (BADCH); + ++BSDoptind; + place = EMSG; + return (-1); + } + } /* option letter okay? */ + if ((BSDoptopt = (int)*place++) == (int)':' || + !(oli = strchr(ostr, BSDoptopt))) { + /* + * if the user didn't specify '-' as an option, + * assume it means -1. + */ + if (BSDoptopt == (int)'-') + return (-1); + if (!*place) + ++BSDoptind; + if (BSDopterr && *ostr != ':') + (void)fprintf(stderr, + "%s: unknown option -- %c\n", __progname, BSDoptopt); + return (BADCH); + } + if (*++oli != ':') { /* don't need argument */ + BSDoptarg = NULL; + if (!*place) + ++BSDoptind; + } + else { /* need an argument */ + if (*place) /* no white space */ + BSDoptarg = (char *)place; + else if (nargc <= ++BSDoptind) { /* no arg */ + place = EMSG; + if (*ostr == ':') + return (BADARG); + if (BSDopterr) + (void)fprintf(stderr, + "%s: option requires an argument -- %c\n", + __progname, BSDoptopt); + return (BADCH); + } + else /* white space */ + BSDoptarg = nargv[BSDoptind]; + place = EMSG; + ++BSDoptind; + } + return (BSDoptopt); /* dump back option letter */ +} diff --git a/compat/imsg-buffer.c b/compat/imsg-buffer.c new file mode 100644 index 00000000..241c4f4d --- /dev/null +++ b/compat/imsg-buffer.c @@ -0,0 +1,307 @@ +/* $OpenBSD: imsg-buffer.c,v 1.7 2015/07/12 18:40:49 nicm Exp $ */ + +/* + * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org> + * + * 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 <sys/types.h> +#include <sys/socket.h> +#include <sys/uio.h> + +#include <limits.h> +#include <errno.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "tmux.h" +#include "imsg.h" + +int ibuf_realloc(struct ibuf *, size_t); +void ibuf_enqueue(struct msgbuf *, struct ibuf *); +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); +} + +int +ibuf_realloc(struct ibuf *buf, size_t len) +{ + u_char *b; + + /* on static buffers max is eq size and so the following fails */ + if (buf->wpos + len > buf->max) { + errno = ERANGE; + return (-1); + } + + b = realloc(buf->buf, buf->wpos + len); + 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 (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 (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 (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) +{ + free(buf->buf); + 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 (buf->rpos + n >= buf->wpos) { + 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; + 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; + iov[i].iov_base = buf->buf + buf->rpos; + iov[i].iov_len = buf->wpos - buf->rpos; + i++; + if (buf->fd != -1) + break; + } + + msg.msg_iov = iov; + msg.msg_iovlen = i; + + if (buf != NULL && buf->fd != -1) { + 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) = buf->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 (buf != NULL && buf->fd != -1) { + close(buf->fd); + buf->fd = -1; + } + + msgbuf_drain(msgbuf, n); + + return (1); +} + +void +ibuf_enqueue(struct msgbuf *msgbuf, struct ibuf *buf) +{ + TAILQ_INSERT_TAIL(&msgbuf->bufs, buf, entry); + msgbuf->queued++; +} + +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); +} diff --git a/compat/imsg.c b/compat/imsg.c new file mode 100644 index 00000000..6c9bee68 --- /dev/null +++ b/compat/imsg.c @@ -0,0 +1,336 @@ +/* $OpenBSD: imsg.c,v 1.9 2015/07/12 18:40:49 nicm Exp $ */ + +/* + * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org> + * + * 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 <sys/types.h> +#include <sys/socket.h> +#include <sys/uio.h> + +#include <errno.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "tmux.h" +#include "imsg.h" + +int imsg_fd_overhead = 0; + +int imsg_get_fd(struct imsgbuf *); + +int available_fds(unsigned int); + +/* + * The original code calls getdtablecount() which is OpenBSD specific. Use + * available_fds() from OpenSMTPD instead. + */ +int +available_fds(unsigned int n) +{ + unsigned int i; + int ret, fds[256]; + + if (n > (sizeof(fds)/sizeof(fds[0]))) + return (1); + + ret = 0; + for (i = 0; i < n; i++) { + fds[i] = -1; + if ((fds[i] = socket(AF_INET, SOCK_DGRAM, 0)) < 0) { + if (errno == EAFNOSUPPORT || errno == EPROTONOSUPPORT) + fds[i] = socket(AF_INET6, SOCK_DGRAM, 0); + if (fds[i] < 0) { + ret = 1; + break; + } + } + } + + for (i = 0; i < n && fds[i] >= 0; i++) + close(fds[i]); + + return (ret); +} + +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 (available_fds(imsg_fd_overhead + + (CMSG_SPACE(sizeof(int))-CMSG_SPACE(0))/sizeof(int))) { + errno = EAGAIN; + free(ifd); + return (-1); + } + + if ((n = recvmsg(ibuf->fd, &msg, 0)) == -1) { + if (errno == EMSGSIZE) + goto fail; + if (errno != EINTR && errno != EAGAIN) + goto fail; + goto again; + } + + 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: + if (ifd) + 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 ((imsg->data = malloc(datalen)) == NULL) + return (-1); + + if (imsg->hdr.flags & IMSGF_HASFD) + imsg->fd = imsg_get_fd(ibuf); + else + imsg->fd = -1; + + 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, u_int32_t type, u_int32_t peerid, + pid_t pid, int fd, const void *data, u_int16_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, u_int32_t type, u_int32_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, u_int32_t type, u_int32_t peerid, + pid_t pid, u_int16_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, u_int16_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 = (u_int16_t)msg->wpos; + + ibuf_close(&ibuf->w, msg); +} + +void +imsg_free(struct imsg *imsg) +{ + free(imsg->data); +} + +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); +} diff --git a/compat/imsg.h b/compat/imsg.h new file mode 100644 index 00000000..06fe1bc1 --- /dev/null +++ b/compat/imsg.h @@ -0,0 +1,114 @@ +/* $OpenBSD: imsg.h,v 1.3 2013/12/26 17:32:33 eric Exp $ */ + +/* + * Copyright (c) 2006, 2007 Pierre-Yves Ritschard <pyr@openbsd.org> + * Copyright (c) 2006, 2007, 2008 Reyk Floeter <reyk@openbsd.org> + * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org> + * + * 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 "tmux.h" + +#ifndef _IMSG_H_ +#define _IMSG_H_ + +#define IBUF_READ_SIZE 65535 +#define IMSG_HEADER_SIZE sizeof(struct imsg_hdr) +#define MAX_IMSGSIZE 16384 + +struct ibuf { + TAILQ_ENTRY(ibuf) entry; + u_char *buf; + size_t size; + size_t max; + size_t wpos; + size_t rpos; + int fd; +}; + +struct msgbuf { + TAILQ_HEAD(, ibuf) bufs; + u_int32_t queued; + int fd; +}; + +struct ibuf_read { + u_char buf[IBUF_READ_SIZE]; + u_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 { + u_int32_t type; + u_int16_t len; + u_int16_t flags; + u_int32_t peerid; + u_int32_t pid; +}; + +struct imsg { + struct imsg_hdr hdr; + int fd; + void *data; +}; + + +/* 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 *, u_int32_t, u_int32_t, pid_t, + int, const void *, u_int16_t); +int imsg_composev(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, + int, const struct iovec *, int); +struct ibuf *imsg_create(struct imsgbuf *, u_int32_t, u_int32_t, pid_t, + u_int16_t); +int imsg_add(struct ibuf *, const void *, u_int16_t); +void imsg_close(struct imsgbuf *, struct ibuf *); +void imsg_free(struct imsg *); +int imsg_flush(struct imsgbuf *); +void imsg_clear(struct imsgbuf *); + +#endif diff --git a/compat/openat.c b/compat/openat.c new file mode 100644 index 00000000..d003e53d --- /dev/null +++ b/compat/openat.c @@ -0,0 +1,65 @@ +/* + * Copyright (c) 2013 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <errno.h> +#include <fcntl.h> +#include <stdarg.h> +#include <unistd.h> + +#include "tmux.h" + +int +openat(int fd, const char *path, int flags, ...) +{ + mode_t mode; + va_list ap; + int dotfd, retval, saved_errno; + + if (flags & O_CREAT) { + va_start(ap, flags); + mode = va_arg(ap, mode_t); + va_end(ap); + } else + mode = 0; + + dotfd = -1; + if (fd != AT_FDCWD) { + dotfd = open(".", O_RDONLY); + if (dotfd == -1) + return (-1); + if (fchdir(fd) != 0) { + saved_errno = errno; + close(dotfd); + errno = saved_errno; + return (-1); + } + } + + retval = open(path, flags, mode); + + if (dotfd != -1) { + if (fchdir(dotfd) != 0) { + saved_errno = errno; + close(retval); + close(dotfd); + errno = saved_errno; + return (-1); + } + close(dotfd); + } + + return (retval); +} diff --git a/compat/queue.h b/compat/queue.h new file mode 100644 index 00000000..622301d1 --- /dev/null +++ b/compat/queue.h @@ -0,0 +1,568 @@ +/* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ +/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ + +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + */ + +#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 circular queues. + * + * + * A singly-linked list is headed by a single forward pointer. The elements + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary elements. New elements can be + * added to the list after an existing element or at the head of the list. + * Elements being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A simple queue is headed by a pair of pointers, one the head of the + * list and the other to the tail of the list. The elements are singly + * linked to save space, so elements can only be removed from the + * head of the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the + * list. A simple queue may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * A circle queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the list. + * A circle queue may be traversed in either direction, but has a more + * complex end of list detection. + * + * For details on the use of these macros, see the queue(3) manual page. + */ + +#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) +#define _Q_INVALIDATE(a) (a) = ((void *)-1) +#else +#define _Q_INVALIDATE(a) +#endif + +/* + * Singly-linked List definitions. + */ +#define SLIST_HEAD(name, type) \ +struct name { \ + struct type *slh_first; /* first element */ \ +} + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ +struct { \ + struct type *sle_next; /* next element */ \ +} + +/* + * Singly-linked List access methods. + */ +#define SLIST_FIRST(head) ((head)->slh_first) +#define SLIST_END(head) NULL +#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_FOREACH(var, head, field) \ + for((var) = SLIST_FIRST(head); \ + (var) != SLIST_END(head); \ + (var) = SLIST_NEXT(var, field)) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST(head); \ + (var) && ((tvar) = SLIST_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Singly-linked List functions. + */ +#define SLIST_INIT(head) { \ + SLIST_FIRST(head) = SLIST_END(head); \ +} + +#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ + (elm)->field.sle_next = (slistelm)->field.sle_next; \ + (slistelm)->field.sle_next = (elm); \ +} while (0) + +#define SLIST_INSERT_HEAD(head, elm, field) do { \ + (elm)->field.sle_next = (head)->slh_first; \ + (head)->slh_first = (elm); \ +} while (0) + +#define SLIST_REMOVE_AFTER(elm, field) do { \ + (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \ +} while (0) + +#define SLIST_REMOVE_HEAD(head, field) do { \ + (head)->slh_first = (head)->slh_first->field.sle_next; \ +} while (0) + +#define SLIST_REMOVE(head, elm, type, field) do { \ + if ((head)->slh_first == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->slh_first; \ + \ + while (curelm->field.sle_next != (elm)) \ + curelm = curelm->field.sle_next; \ + curelm->field.sle_next = \ + curelm->field.sle_next->field.sle_next; \ + _Q_INVALIDATE((elm)->field.sle_next); \ + } \ +} while (0) + +/* + * List definitions. + */ +#define LIST_HEAD(name, type) \ +struct name { \ + struct type *lh_first; /* first element */ \ +} + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ +struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ +} + +/* + * List access methods + */ +#define LIST_FIRST(head) ((head)->lh_first) +#define LIST_END(head) NULL +#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_FOREACH(var, head, field) \ + for((var) = LIST_FIRST(head); \ + (var)!= LIST_END(head); \ + (var) = LIST_NEXT(var, field)) + +#define LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST(head); \ + (var) && ((tvar) = LIST_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * List functions. + */ +#define LIST_INIT(head) do { \ + LIST_FIRST(head) = LIST_END(head); \ +} while (0) + +#define LIST_INSERT_AFTER(listelm, elm, field) do { \ + if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ + (listelm)->field.le_next->field.le_prev = \ + &(elm)->field.le_next; \ + (listelm)->field.le_next = (elm); \ + (elm)->field.le_prev = &(listelm)->field.le_next; \ +} while (0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + (elm)->field.le_next = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &(elm)->field.le_next; \ +} while (0) + +#define LIST_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.le_next = (head)->lh_first) != NULL) \ + (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ +} while (0) + +#define LIST_REMOVE(elm, field) do { \ + if ((elm)->field.le_next != NULL) \ + (elm)->field.le_next->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = (elm)->field.le_next; \ + _Q_INVALIDATE((elm)->field.le_prev); \ + _Q_INVALIDATE((elm)->field.le_next); \ +} while (0) + +#define LIST_REPLACE(elm, elm2, field) do { \ + if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ + (elm2)->field.le_next->field.le_prev = \ + &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + _Q_INVALIDATE((elm)->field.le_prev); \ + _Q_INVALIDATE((elm)->field.le_next); \ +} while (0) + +/* + * Simple queue definitions. + */ +#define SIMPLEQ_HEAD(name, type) \ +struct name { \ + struct type *sqh_first; /* first element */ \ + struct type **sqh_last; /* addr of last next element */ \ +} + +#define SIMPLEQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).sqh_first } + +#define SIMPLEQ_ENTRY(type) \ +struct { \ + struct type *sqe_next; /* next element */ \ +} + +/* + * Simple queue access methods. + */ +#define SIMPLEQ_FIRST(head) ((head)->sqh_first) +#define SIMPLEQ_END(head) NULL +#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) +#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + +#define SIMPLEQ_FOREACH(var, head, field) \ + for((var) = SIMPLEQ_FIRST(head); \ + (var) != SIMPLEQ_END(head); \ + (var) = SIMPLEQ_NEXT(var, field)) + +#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SIMPLEQ_FIRST(head); \ + (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Simple queue functions. + */ +#define SIMPLEQ_INIT(head) do { \ + (head)->sqh_first = NULL; \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (0) + +#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (head)->sqh_first = (elm); \ +} while (0) + +#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.sqe_next = NULL; \ + *(head)->sqh_last = (elm); \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (0) + +#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (listelm)->field.sqe_next = (elm); \ +} while (0) + +#define SIMPLEQ_REMOVE_HEAD(head, field) do { \ + if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (0) + +#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ + if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ + == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (0) + +/* + * Tail queue definitions. + */ +#define TAILQ_HEAD(name, type) \ +struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ +} + +#define TAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).tqh_first } + +#define TAILQ_ENTRY(type) \ +struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ +} + +/* + * tail queue access methods + */ +#define TAILQ_FIRST(head) ((head)->tqh_first) +#define TAILQ_END(head) NULL +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) +/* XXX */ +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) +#define TAILQ_EMPTY(head) \ + (TAILQ_FIRST(head) == TAILQ_END(head)) + +#define TAILQ_FOREACH(var, head, field) \ + for((var) = TAILQ_FIRST(head); \ + (var) != TAILQ_END(head); \ + (var) = TAILQ_NEXT(var, field)) + +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST(head); \ + (var) != TAILQ_END(head) && \ + ((tvar) = TAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) + + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for((var) = TAILQ_LAST(head, headname); \ + (var) != TAILQ_END(head); \ + (var) = TAILQ_PREV(var, headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = TAILQ_LAST(head, headname); \ + (var) != TAILQ_END(head) && \ + ((tvar) = TAILQ_PREV(var, headname, field), 1); \ + (var) = (tvar)) + +/* + * Tail queue functions. + */ +#define TAILQ_INIT(head) do { \ + (head)->tqh_first = NULL; \ + (head)->tqh_last = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ + (head)->tqh_first->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.tqe_next = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ + (elm)->field.tqe_next->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + (elm)->field.tqe_next = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_REMOVE(head, elm, field) do { \ + if (((elm)->field.tqe_next) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ + _Q_INVALIDATE((elm)->field.tqe_prev); \ + _Q_INVALIDATE((elm)->field.tqe_next); \ +} while (0) + +#define TAILQ_REPLACE(head, elm, elm2, field) do { \ + if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ + (elm2)->field.tqe_next->field.tqe_prev = \ + &(elm2)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm2)->field.tqe_next; \ + (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ + *(elm2)->field.tqe_prev = (elm2); \ + _Q_INVALIDATE((elm)->field.tqe_prev); \ + _Q_INVALIDATE((elm)->field.tqe_next); \ +} while (0) + +/* + * Circular queue definitions. + */ +#define CIRCLEQ_HEAD(name, type) \ +struct name { \ + struct type *cqh_first; /* first element */ \ + struct type *cqh_last; /* last element */ \ +} + +#define CIRCLEQ_HEAD_INITIALIZER(head) \ + { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } + +#define CIRCLEQ_ENTRY(type) \ +struct { \ + struct type *cqe_next; /* next element */ \ + struct type *cqe_prev; /* previous element */ \ +} + +/* + * Circular queue access methods + */ +#define CIRCLEQ_FIRST(head) ((head)->cqh_first) +#define CIRCLEQ_LAST(head) ((head)->cqh_last) +#define CIRCLEQ_END(head) ((void *)(head)) +#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) +#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) +#define CIRCLEQ_EMPTY(head) \ + (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) + +#define CIRCLEQ_FOREACH(var, head, field) \ + for((var) = CIRCLEQ_FIRST(head); \ + (var) != CIRCLEQ_END(head); \ + (var) = CIRCLEQ_NEXT(var, field)) + +#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = CIRCLEQ_FIRST(head); \ + (var) != CIRCLEQ_END(head) && \ + ((tvar) = CIRCLEQ_NEXT(var, field), 1); \ + (var) = (tvar)) + +#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ + for((var) = CIRCLEQ_LAST(head); \ + (var) != CIRCLEQ_END(head); \ + (var) = CIRCLEQ_PREV(var, field)) + +#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = CIRCLEQ_LAST(head, headname); \ + (var) != CIRCLEQ_END(head) && \ + ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \ + (var) = (tvar)) + +/* + * Circular queue functions. + */ +#define CIRCLEQ_INIT(head) do { \ + (head)->cqh_first = CIRCLEQ_END(head); \ + (head)->cqh_last = CIRCLEQ_END(head); \ +} while (0) + +#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + (elm)->field.cqe_next = (listelm)->field.cqe_next; \ + (elm)->field.cqe_prev = (listelm); \ + if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ + (head)->cqh_last = (elm); \ + else \ + (listelm)->field.cqe_next->field.cqe_prev = (elm); \ + (listelm)->field.cqe_next = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ + (elm)->field.cqe_next = (listelm); \ + (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ + if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ + (head)->cqh_first = (elm); \ + else \ + (listelm)->field.cqe_prev->field.cqe_next = (elm); \ + (listelm)->field.cqe_prev = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ + (elm)->field.cqe_next = (head)->cqh_first; \ + (elm)->field.cqe_prev = CIRCLEQ_END(head); \ + if ((head)->cqh_last == CIRCLEQ_END(head)) \ + (head)->cqh_last = (elm); \ + else \ + (head)->cqh_first->field.cqe_prev = (elm); \ + (head)->cqh_first = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.cqe_next = CIRCLEQ_END(head); \ + (elm)->field.cqe_prev = (head)->cqh_last; \ + if ((head)->cqh_first == CIRCLEQ_END(head)) \ + (head)->cqh_first = (elm); \ + else \ + (head)->cqh_last->field.cqe_next = (elm); \ + (head)->cqh_last = (elm); \ +} while (0) + +#define CIRCLEQ_REMOVE(head, elm, field) do { \ + if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ + (head)->cqh_last = (elm)->field.cqe_prev; \ + else \ + (elm)->field.cqe_next->field.cqe_prev = \ + (elm)->field.cqe_prev; \ + if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ + (head)->cqh_first = (elm)->field.cqe_next; \ + else \ + (elm)->field.cqe_prev->field.cqe_next = \ + (elm)->field.cqe_next; \ + _Q_INVALIDATE((elm)->field.cqe_prev); \ + _Q_INVALIDATE((elm)->field.cqe_next); \ +} while (0) + +#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ + if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ + CIRCLEQ_END(head)) \ + (head).cqh_last = (elm2); \ + else \ + (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ + if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ + CIRCLEQ_END(head)) \ + (head).cqh_first = (elm2); \ + else \ + (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ + _Q_INVALIDATE((elm)->field.cqe_prev); \ + _Q_INVALIDATE((elm)->field.cqe_next); \ +} while (0) + +#endif /* !_SYS_QUEUE_H_ */ diff --git a/compat/reallocarray.c b/compat/reallocarray.c new file mode 100644 index 00000000..f4705fcd --- /dev/null +++ b/compat/reallocarray.c @@ -0,0 +1,40 @@ +/* $OpenBSD: reallocarray.c,v 1.3 2015/09/13 08:31:47 guenther Exp $ */ +/* + * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net> + * + * 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 <sys/types.h> +#include <errno.h> +#include <stdint.h> +#include <stdlib.h> + +#include "tmux.h" + +/* + * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX + * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW + */ +#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4)) + +void * +reallocarray(void *optr, size_t nmemb, size_t size) +{ + if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && + nmemb > 0 && SIZE_MAX / nmemb < size) { + errno = ENOMEM; + return NULL; + } + return realloc(optr, size * nmemb); +} diff --git a/compat/setenv.c b/compat/setenv.c new file mode 100644 index 00000000..b16b08cf --- /dev/null +++ b/compat/setenv.c @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2010 Dagobert Michelsen + * Copyright (c) 2010 Nicholas Marriott <nicholas.marriott@gmail.com> + * + * 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 <stdlib.h> +#include <string.h> + +#include "tmux.h" + +int +setenv(const char *name, const char *value, unused int overwrite) +{ + char *newval; + + xasprintf(&newval, "%s=%s", name, value); + return (putenv(newval)); +} + +int +unsetenv(const char *name) +{ + char **envptr; + int namelen; + + namelen = strlen(name); + for (envptr = environ; *envptr != NULL; envptr++) { + if (strncmp(name, *envptr, namelen) == 0 && + ((*envptr)[namelen] == '=' || (*envptr)[namelen] == '\0')) + break; + } + for (; *envptr != NULL; envptr++) + *envptr = *(envptr + 1); + return (0); +} diff --git a/compat/strcasestr.c b/compat/strcasestr.c new file mode 100644 index 00000000..aa74c017 --- /dev/null +++ b/compat/strcasestr.c @@ -0,0 +1,60 @@ +/* $OpenBSD: strcasestr.c,v 1.3 2006/03/31 05:34:55 deraadt Exp $ */ +/* $NetBSD: strcasestr.c,v 1.2 2005/02/09 21:35:47 kleink Exp $ */ + +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <ctype.h> +#include <string.h> + +/* + * Find the first occurrence of find in s, ignore case. + */ +char * +strcasestr(const char *s, const char *find) +{ + char c, sc; + size_t len; + + if ((c = *find++) != 0) { + c = (char)tolower((unsigned char)c); + len = strlen(find); + do { + do { + if ((sc = *s++) == 0) + return (NULL); + } while ((char)tolower((unsigned char)sc) != c); + } while (strncasecmp(s, find, len) != 0); + s--; + } + return ((char *)s); +} diff --git a/compat/strlcat.c b/compat/strlcat.c new file mode 100644 index 00000000..e081c4f6 --- /dev/null +++ b/compat/strlcat.c @@ -0,0 +1,57 @@ +/* $OpenBSD: strlcat.c,v 1.13 2005/08/08 08:05:37 espie Exp $ */ + +/* + * Copyright (c) 1998 Todd C. Miller <Todd.Miller@courtesan.com> + * + * 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 <sys/types.h> +#include <string.h> + +#include "tmux.h" + +/* + * Appends src to string dst of size siz (unlike strncat, siz is the + * full size of dst, not space left). At most siz-1 characters + * will be copied. Always NUL terminates (unless siz <= strlen(dst)). + * Returns strlen(src) + MIN(siz, strlen(initial dst)). + * If retval >= siz, truncation occurred. + */ +size_t +strlcat(char *dst, const char *src, size_t siz) +{ + char *d = dst; + const char *s = src; + size_t n = siz; + size_t dlen; + + /* Find the end of dst and adjust bytes left but don't go past end */ + while (n-- != 0 && *d != '\0') + d++; + dlen = d - dst; + n = siz - dlen; + + if (n == 0) + return(dlen + strlen(s)); + while (*s != '\0') { + if (n != 1) { + *d++ = *s; + n--; + } + s++; + } + *d = '\0'; + + return(dlen + (s - src)); /* count does not include NUL */ +} diff --git a/compat/strlcpy.c b/compat/strlcpy.c new file mode 100644 index 00000000..d6e8e77c --- /dev/null +++ b/compat/strlcpy.c @@ -0,0 +1,53 @@ +/* $OpenBSD: strlcpy.c,v 1.10 2005/08/08 08:05:37 espie Exp $ */ + +/* + * Copyright (c) 1998 Todd C. Miller <Todd.Miller@courtesan.com> + * + * 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 <sys/types.h> +#include <string.h> + +#include "tmux.h" + +/* + * Copy src to string dst of size siz. At most siz-1 characters + * will be copied. Always NUL terminates (unless siz == 0). + * Returns strlen(src); if retval >= siz, truncation occurred. + */ +size_t +strlcpy(char *dst, const char *src, size_t siz) +{ + char *d = dst; + const char *s = src; + size_t n = siz; + + /* Copy as many bytes as will fit */ + if (n != 0 && --n != 0) { + do { + if ((*d++ = *s++) == 0) + break; + } while (--n != 0); + } + + /* Not enough room in dst, add NUL and traverse rest of src */ + if (n == 0) { + if (siz != 0) + *d = '\0'; /* NUL-terminate dst */ + while (*s++) + ; + } + + return(s - src - 1); /* count does not include NUL */ +} diff --git a/compat/strsep.c b/compat/strsep.c new file mode 100644 index 00000000..c44bc5b2 --- /dev/null +++ b/compat/strsep.c @@ -0,0 +1,71 @@ +/* $OpenBSD: strsep.c,v 1.6 2005/08/08 08:05:37 espie Exp $ */ + +/*- + * Copyright (c) 1990, 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. + */ + +#include <string.h> +#include <stdio.h> + +/* + * Get next token from string *stringp, where tokens are possibly-empty + * strings separated by characters from delim. + * + * Writes NULs into the string at *stringp to end tokens. + * delim need not remain constant from call to call. + * On return, *stringp points past the last NUL written (if there might + * be further tokens), or is NULL (if there are definitely no more tokens). + * + * If *stringp is NULL, strsep returns NULL. + */ +char * +strsep(char **stringp, const char *delim) +{ + char *s; + const char *spanp; + int c, sc; + char *tok; + + if ((s = *stringp) == NULL) + return (NULL); + for (tok = s;;) { + c = *s++; + spanp = delim; + do { + if ((sc = *spanp++) == c) { + if (c == 0) + s = NULL; + else + s[-1] = 0; + *stringp = s; + return (tok); + } + } while (sc != 0); + } + /* NOTREACHED */ +} diff --git a/compat/strtonum.c b/compat/strtonum.c new file mode 100644 index 00000000..4c7b0c9f --- /dev/null +++ b/compat/strtonum.c @@ -0,0 +1,67 @@ +/* $OpenBSD: strtonum.c,v 1.6 2004/08/03 19:38:01 millert Exp $ */ + +/* + * Copyright (c) 2004 Ted Unangst and Todd Miller + * All rights reserved. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <errno.h> +#include <limits.h> +#include <stdlib.h> + +#include "tmux.h" + +#define INVALID 1 +#define TOOSMALL 2 +#define TOOLARGE 3 + +long long +strtonum(const char *numstr, long long minval, long long maxval, + const char **errstrp) +{ + long long ll = 0; + char *ep; + int error = 0; + struct errval { + const char *errstr; + int err; + } ev[4] = { + { NULL, 0 }, + { "invalid", EINVAL }, + { "too small", ERANGE }, + { "too large", ERANGE }, + }; + + ev[0].err = errno; + errno = 0; + if (minval > maxval) + error = INVALID; + else { + ll = strtoll(numstr, &ep, 10); + if (numstr == ep || *ep != '\0') + error = INVALID; + else if ((ll == LLONG_MIN && errno == ERANGE) || ll < minval) + error = TOOSMALL; + else if ((ll == LLONG_MAX && errno == ERANGE) || ll > maxval) + error = TOOLARGE; + } + if (errstrp != NULL) + *errstrp = ev[error].errstr; + errno = ev[error].err; + if (error) + ll = 0; + + return (ll); +} diff --git a/compat/tree.h b/compat/tree.h new file mode 100644 index 00000000..80d0f538 --- /dev/null +++ b/compat/tree.h @@ -0,0 +1,748 @@ +/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * 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_ + +/* + * 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)) + +#endif /* _SYS_TREE_H_ */ diff --git a/compat/unvis.c b/compat/unvis.c new file mode 100644 index 00000000..e1f09ec9 --- /dev/null +++ b/compat/unvis.c @@ -0,0 +1,281 @@ +/* $OpenBSD: unvis.c,v 1.12 2005/08/08 08:05:34 espie Exp $ */ +/*- + * Copyright (c) 1989, 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. + */ + +#include <sys/types.h> +#include <ctype.h> + +#include "tmux.h" + +/* + * decode driven by state machine + */ +#define S_GROUND 0 /* haven't seen escape char */ +#define S_START 1 /* start decoding special sequence */ +#define S_META 2 /* metachar started (M) */ +#define S_META1 3 /* metachar more, regular char (-) */ +#define S_CTRL 4 /* control char started (^) */ +#define S_OCTAL2 5 /* octal digit 2 */ +#define S_OCTAL3 6 /* octal digit 3 */ + +#define isoctal(c) (((u_char)(c)) >= '0' && ((u_char)(c)) <= '7') + +/* + * unvis - decode characters previously encoded by vis + */ +int +unvis(char *cp, char c, int *astate, int flag) +{ + + if (flag & UNVIS_END) { + if (*astate == S_OCTAL2 || *astate == S_OCTAL3) { + *astate = S_GROUND; + return (UNVIS_VALID); + } + return (*astate == S_GROUND ? UNVIS_NOCHAR : UNVIS_SYNBAD); + } + + switch (*astate) { + + case S_GROUND: + *cp = 0; + if (c == '\\') { + *astate = S_START; + return (0); + } + *cp = c; + return (UNVIS_VALID); + + case S_START: + switch(c) { + case '\\': + *cp = c; + *astate = S_GROUND; + return (UNVIS_VALID); + case '0': case '1': case '2': case '3': + case '4': case '5': case '6': case '7': + *cp = (c - '0'); + *astate = S_OCTAL2; + return (0); + case 'M': + *cp = (char) 0200; + *astate = S_META; + return (0); + case '^': + *astate = S_CTRL; + return (0); + case 'n': + *cp = '\n'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 'r': + *cp = '\r'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 'b': + *cp = '\b'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 'a': + *cp = '\007'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 'v': + *cp = '\v'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 't': + *cp = '\t'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 'f': + *cp = '\f'; + *astate = S_GROUND; + return (UNVIS_VALID); + case 's': + *cp = ' '; + *astate = S_GROUND; + return (UNVIS_VALID); + case 'E': + *cp = '\033'; + *astate = S_GROUND; + return (UNVIS_VALID); + case '\n': + /* + * hidden newline + */ + *astate = S_GROUND; + return (UNVIS_NOCHAR); + case '$': + /* + * hidden marker + */ + *astate = S_GROUND; + return (UNVIS_NOCHAR); + } + *astate = S_GROUND; + return (UNVIS_SYNBAD); + + case S_META: + if (c == '-') + *astate = S_META1; + else if (c == '^') + *astate = S_CTRL; + else { + *astate = S_GROUND; + return (UNVIS_SYNBAD); + } + return (0); + + case S_META1: + *astate = S_GROUND; + *cp |= c; + return (UNVIS_VALID); + + case S_CTRL: + if (c == '?') + *cp |= 0177; + else + *cp |= c & 037; + *astate = S_GROUND; + return (UNVIS_VALID); + + case S_OCTAL2: /* second possible octal digit */ + if (isoctal(c)) { + /* + * yes - and maybe a third + */ + *cp = (*cp << 3) + (c - '0'); + *astate = S_OCTAL3; + return (0); + } + /* + * no - done with current sequence, push back passed char + */ + *astate = S_GROUND; + return (UNVIS_VALIDPUSH); + + case S_OCTAL3: /* third possible octal digit */ + *astate = S_GROUND; + if (isoctal(c)) { + *cp = (*cp << 3) + (c - '0'); + return (UNVIS_VALID); + } + /* + * we were done, push back passed char + */ + return (UNVIS_VALIDPUSH); + + default: + /* + * decoder in unknown state - (probably uninitialized) + */ + *astate = S_GROUND; + return (UNVIS_SYNBAD); + } +} + +/* + * strunvis - decode src into dst + * + * Number of chars decoded into dst is returned, -1 on error. + * Dst is null terminated. + */ + +int +strunvis(char *dst, const char *src) +{ + char c; + char *start = dst; + int state = 0; + + while ((c = *src++)) { + again: + switch (unvis(dst, c, &state, 0)) { + case UNVIS_VALID: + dst++; + break; + case UNVIS_VALIDPUSH: + dst++; + goto again; + case 0: + case UNVIS_NOCHAR: + break; + default: + *dst = '\0'; + return (-1); + } + } + if (unvis(dst, c, &state, UNVIS_END) == UNVIS_VALID) + dst++; + *dst = '\0'; + return (dst - start); +} + +ssize_t +strnunvis(char *dst, const char *src, size_t sz) +{ + char c, p; + char *start = dst, *end = dst + sz - 1; + int state = 0; + + if (sz > 0) + *end = '\0'; + while ((c = *src++)) { + again: + switch (unvis(&p, c, &state, 0)) { + case UNVIS_VALID: + if (dst < end) + *dst = p; + dst++; + break; + case UNVIS_VALIDPUSH: + if (dst < end) + *dst = p; + dst++; + goto again; + case 0: + case UNVIS_NOCHAR: + break; + default: + if (dst <= end) + *dst = '\0'; + return (-1); + } + } + if (unvis(&p, c, &state, UNVIS_END) == UNVIS_VALID) { + if (dst < end) + *dst = p; + dst++; + } + if (dst <= end) + *dst = '\0'; + return (dst - start); +} + diff --git a/compat/vis.c b/compat/vis.c new file mode 100644 index 00000000..82b42be9 --- /dev/null +++ b/compat/vis.c @@ -0,0 +1,242 @@ +/* $OpenBSD: vis.c,v 1.24 2015/07/20 01:52:28 millert Exp $ */ +/*- + * Copyright (c) 1989, 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. + */ + +#include <sys/types.h> +#include <errno.h> +#include <ctype.h> +#include <limits.h> +#include <string.h> +#include <stdlib.h> + +#include "tmux.h" + +#define isoctal(c) (((u_char)(c)) >= '0' && ((u_char)(c)) <= '7') +#define isvisible(c,flag) \ + (((c) == '\\' || (flag & VIS_ALL) == 0) && \ + (((u_int)(c) <= UCHAR_MAX && isascii((u_char)(c)) && \ + (((c) != '*' && (c) != '?' && (c) != '[' && (c) != '#') || \ + (flag & VIS_GLOB) == 0) && isgraph((u_char)(c))) || \ + ((flag & VIS_SP) == 0 && (c) == ' ') || \ + ((flag & VIS_TAB) == 0 && (c) == '\t') || \ + ((flag & VIS_NL) == 0 && (c) == '\n') || \ + ((flag & VIS_SAFE) && ((c) == '\b' || \ + (c) == '\007' || (c) == '\r' || \ + isgraph((u_char)(c)))))) + +/* + * vis - visually encode characters + */ +char * +vis(char *dst, int c, int flag, int nextc) +{ + if (isvisible(c, flag)) { + if ((c == '"' && (flag & VIS_DQ) != 0) || + (c == '\\' && (flag & VIS_NOSLASH) == 0)) + *dst++ = '\\'; + *dst++ = c; + *dst = '\0'; + return (dst); + } + + if (flag & VIS_CSTYLE) { + switch(c) { + case '\n': + *dst++ = '\\'; + *dst++ = 'n'; + goto done; + case '\r': + *dst++ = '\\'; + *dst++ = 'r'; + goto done; + case '\b': + *dst++ = '\\'; + *dst++ = 'b'; + goto done; + case '\a': + *dst++ = '\\'; + *dst++ = 'a'; + goto done; + case '\v': + *dst++ = '\\'; + *dst++ = 'v'; + goto done; + case '\t': + *dst++ = '\\'; + *dst++ = 't'; + goto done; + case '\f': + *dst++ = '\\'; + *dst++ = 'f'; + goto done; + case ' ': + *dst++ = '\\'; + *dst++ = 's'; + goto done; + case '\0': + *dst++ = '\\'; + *dst++ = '0'; + if (isoctal(nextc)) { + *dst++ = '0'; + *dst++ = '0'; + } + goto done; + } + } + if (((c & 0177) == ' ') || (flag & VIS_OCTAL) || + ((flag & VIS_GLOB) && (c == '*' || c == '?' || c == '[' || c == '#'))) { + *dst++ = '\\'; + *dst++ = ((u_char)c >> 6 & 07) + '0'; + *dst++ = ((u_char)c >> 3 & 07) + '0'; + *dst++ = ((u_char)c & 07) + '0'; + goto done; + } + if ((flag & VIS_NOSLASH) == 0) + *dst++ = '\\'; + if (c & 0200) { + c &= 0177; + *dst++ = 'M'; + } + if (iscntrl((u_char)c)) { + *dst++ = '^'; + if (c == 0177) + *dst++ = '?'; + else + *dst++ = c + '@'; + } else { + *dst++ = '-'; + *dst++ = c; + } +done: + *dst = '\0'; + return (dst); +} + +/* + * strvis, strnvis, strvisx - visually encode characters from src into dst + * + * Dst must be 4 times the size of src to account for possible + * expansion. The length of dst, not including the trailing NULL, + * is returned. + * + * Strnvis will write no more than siz-1 bytes (and will NULL terminate). + * The number of bytes needed to fully encode the string is returned. + * + * Strvisx encodes exactly len bytes from src into dst. + * This is useful for encoding a block of data. + */ +int +strvis(char *dst, const char *src, int flag) +{ + char c; + char *start; + + for (start = dst; (c = *src);) + dst = vis(dst, c, flag, *++src); + *dst = '\0'; + return (dst - start); +} + +int +strnvis(char *dst, const char *src, size_t siz, int flag) +{ + char *start, *end; + char tbuf[5]; + int c, i; + + i = 0; + for (start = dst, end = start + siz - 1; (c = *src) && dst < end; ) { + if (isvisible(c, flag)) { + if ((c == '"' && (flag & VIS_DQ) != 0) || + (c == '\\' && (flag & VIS_NOSLASH) == 0)) { + /* need space for the extra '\\' */ + if (dst + 1 >= end) { + i = 2; + break; + } + *dst++ = '\\'; + } + i = 1; + *dst++ = c; + src++; + } else { + i = vis(tbuf, c, flag, *++src) - tbuf; + if (dst + i <= end) { + memcpy(dst, tbuf, i); + dst += i; + } else { + src--; + break; + } + } + } + if (siz > 0) + *dst = '\0'; + if (dst + i > end) { + /* adjust return value for truncation */ + while ((c = *src)) + dst += vis(tbuf, c, flag, *++src) - tbuf; + } + return (dst - start); +} + +int +stravis(char **outp, const char *src, int flag) +{ + char *buf; + int len, serrno; + + buf = calloc(4, strlen(src) + 1); + if (buf == NULL) + return -1; + len = strvis(buf, src, flag); + serrno = errno; + *outp = realloc(buf, len + 1); + if (*outp == NULL) { + *outp = buf; + errno = serrno; + } + return (len); +} + +int +strvisx(char *dst, const char *src, size_t len, int flag) +{ + char c; + char *start; + + for (start = dst; len > 1; len--) { + c = *src; + dst = vis(dst, c, flag, *++src); + } + if (len) + dst = vis(dst, *src, flag, '\0'); + *dst = '\0'; + return (dst - start); +} diff --git a/compat/vis.h b/compat/vis.h new file mode 100644 index 00000000..9f12d236 --- /dev/null +++ b/compat/vis.h @@ -0,0 +1,85 @@ +/* $OpenBSD: vis.h,v 1.15 2015/07/20 01:52:27 millert Exp $ */ +/* $NetBSD: vis.h,v 1.4 1994/10/26 00:56:41 cgd Exp $ */ + +/*- + * Copyright (c) 1990 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. + * + * @(#)vis.h 5.9 (Berkeley) 4/3/91 + */ + +#ifndef _VIS_H_ +#define _VIS_H_ + +/* + * to select alternate encoding format + */ +#define VIS_OCTAL 0x01 /* use octal \ddd format */ +#define VIS_CSTYLE 0x02 /* use \[nrft0..] where appropriate */ + +/* + * to alter set of characters encoded (default is to encode all + * non-graphic except space, tab, and newline). + */ +#define VIS_SP 0x04 /* also encode space */ +#define VIS_TAB 0x08 /* also encode tab */ +#define VIS_NL 0x10 /* also encode newline */ +#define VIS_WHITE (VIS_SP | VIS_TAB | VIS_NL) +#define VIS_SAFE 0x20 /* only encode "unsafe" characters */ +#define VIS_DQ 0x200 /* backslash-escape double quotes */ +#define VIS_ALL 0x400 /* encode all characters */ + +/* + * other + */ +#define VIS_NOSLASH 0x40 /* inhibit printing '\' */ +#define VIS_GLOB 0x100 /* encode glob(3) magics and '#' */ + +/* + * unvis return codes + */ +#define UNVIS_VALID 1 /* character valid */ +#define UNVIS_VALIDPUSH 2 /* character valid, push back passed char */ +#define UNVIS_NOCHAR 3 /* valid sequence, no character produced */ +#define UNVIS_SYNBAD -1 /* unrecognized escape sequence */ +#define UNVIS_ERROR -2 /* decoder in unknown state (unrecoverable) */ + +/* + * unvis flags + */ +#define UNVIS_END 1 /* no more characters */ + +char *vis(char *, int, int, int); +int strvis(char *, const char *, int); +int stravis(char **, const char *, int); +int strnvis(char *, const char *, size_t, int); +int strvisx(char *, const char *, size_t, int); +int strunvis(char *, const char *); +int unvis(char *, char, int *, int); +ssize_t strnunvis(char *, const char *, size_t); + +#endif /* !_VIS_H_ */ |