diff options
author | Kirill Volinsky <Mataes2007@gmail.com> | 2017-11-29 09:33:41 +0300 |
---|---|---|
committer | Kirill Volinsky <Mataes2007@gmail.com> | 2017-11-29 09:33:41 +0300 |
commit | 89f3cf8bbb9dc1fa0fe72f6af6638ac086c7e011 (patch) | |
tree | 5be9a7ae2255b9ad420bed266b90b1f98059964a /libs/libevent/src/WIN32-Code | |
parent | e28c4adb361a87e143eb8cb2af449e3bcb3375b1 (diff) |
libevent, telegram, whatsapp moved to deprecated coz doesn't work
Diffstat (limited to 'libs/libevent/src/WIN32-Code')
-rw-r--r-- | libs/libevent/src/WIN32-Code/getopt.c | 149 | ||||
-rw-r--r-- | libs/libevent/src/WIN32-Code/getopt.h | 33 | ||||
-rw-r--r-- | libs/libevent/src/WIN32-Code/getopt_long.c | 233 | ||||
-rw-r--r-- | libs/libevent/src/WIN32-Code/nmake/evconfig-private.h | 6 | ||||
-rw-r--r-- | libs/libevent/src/WIN32-Code/nmake/event2/event-config.h | 360 | ||||
-rw-r--r-- | libs/libevent/src/WIN32-Code/tree.h | 677 |
6 files changed, 0 insertions, 1458 deletions
diff --git a/libs/libevent/src/WIN32-Code/getopt.c b/libs/libevent/src/WIN32-Code/getopt.c deleted file mode 100644 index 0fcba5d915..0000000000 --- a/libs/libevent/src/WIN32-Code/getopt.c +++ /dev/null @@ -1,149 +0,0 @@ -/* $NetBSD: getopt.c,v 1.16 1999/12/02 13:15:56 kleink Exp $ */ - -/* - * Copyright (c) 1987, 1993, 1994, 1995 - * 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 names of the copyright holders 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 COPYRIGHT HOLDERS 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. - */ - -#if 0 -static char sccsid[] = "@(#)getopt.c 8.3 (Berkeley) 4/27/95"; -#endif - -#include <assert.h> -#include <errno.h> -#include <stdio.h> -#include <string.h> - -#define __P(x) x -#define _DIAGASSERT(x) assert(x) - -#ifdef __weak_alias -__weak_alias(getopt,_getopt); -#endif - - -int opterr = 1, /* if error message should be printed */ - optind = 1, /* index into parent argv vector */ - optopt, /* character checked for validity */ - optreset; /* reset getopt */ -char *optarg; /* argument associated with option */ - -static char * _progname __P((char *)); -int getopt_internal __P((int, char * const *, const char *)); - -static char * -_progname(nargv0) - char * nargv0; -{ - char * tmp; - - _DIAGASSERT(nargv0 != NULL); - - tmp = strrchr(nargv0, '/'); - if (tmp) - tmp++; - else - tmp = nargv0; - return(tmp); -} - -#define BADCH (int)'?' -#define BADARG (int)':' -#define EMSG "" - -/* - * getopt -- - * Parse argc/argv argument vector. - */ -int -getopt(nargc, nargv, ostr) - int nargc; - char * const nargv[]; - const char *ostr; -{ - static char *__progname = 0; - static char *place = EMSG; /* option letter processing */ - char *oli; /* option letter list index */ - __progname = __progname?__progname:_progname(*nargv); - - _DIAGASSERT(nargv != NULL); - _DIAGASSERT(ostr != NULL); - - if (optreset || !*place) { /* update scanning pointer */ - optreset = 0; - if (optind >= nargc || *(place = nargv[optind]) != '-') { - place = EMSG; - return (-1); - } - if (place[1] && *++place == '-' /* found "--" */ - && place[1] == '\0') { - ++optind; - place = EMSG; - return (-1); - } - } /* option letter okay? */ - if ((optopt = (int)*place++) == (int)':' || - !(oli = strchr(ostr, optopt))) { - /* - * if the user didn't specify '-' as an option, - * assume it means -1. - */ - if (optopt == (int)'-') - return (-1); - if (!*place) - ++optind; - if (opterr && *ostr != ':') - (void)fprintf(stderr, - "%s: illegal option -- %c\n", __progname, optopt); - return (BADCH); - } - if (*++oli != ':') { /* don't need argument */ - optarg = NULL; - if (!*place) - ++optind; - } - else { /* need an argument */ - if (*place) /* no white space */ - optarg = place; - else if (nargc <= ++optind) { /* no arg */ - place = EMSG; - if (*ostr == ':') - return (BADARG); - if (opterr) - (void)fprintf(stderr, - "%s: option requires an argument -- %c\n", - __progname, optopt); - return (BADCH); - } - else /* white space */ - optarg = nargv[optind]; - place = EMSG; - ++optind; - } - return (optopt); /* dump back option letter */ -} - diff --git a/libs/libevent/src/WIN32-Code/getopt.h b/libs/libevent/src/WIN32-Code/getopt.h deleted file mode 100644 index 796f455050..0000000000 --- a/libs/libevent/src/WIN32-Code/getopt.h +++ /dev/null @@ -1,33 +0,0 @@ -#ifndef __GETOPT_H__ -#define __GETOPT_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -extern int opterr; /* if error message should be printed */ -extern int optind; /* index into parent argv vector */ -extern int optopt; /* character checked for validity */ -extern int optreset; /* reset getopt */ -extern char *optarg; /* argument associated with option */ - -struct option -{ - const char *name; - int has_arg; - int *flag; - int val; -}; - -#define no_argument 0 -#define required_argument 1 -#define optional_argument 2 - -int getopt(int, char**, const char*); -int getopt_long(int, char**, const char*, const struct option*, int*); - -#ifdef __cplusplus -} -#endif - -#endif /* __GETOPT_H__ */ diff --git a/libs/libevent/src/WIN32-Code/getopt_long.c b/libs/libevent/src/WIN32-Code/getopt_long.c deleted file mode 100644 index 03f0c01a15..0000000000 --- a/libs/libevent/src/WIN32-Code/getopt_long.c +++ /dev/null @@ -1,233 +0,0 @@ - -/* - * Copyright (c) 1987, 1993, 1994, 1996 - * 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 names of the copyright holders 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 COPYRIGHT HOLDERS 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 <assert.h> -#include <errno.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include "getopt.h" - -extern int opterr; /* if error message should be printed */ -extern int optind; /* index into parent argv vector */ -extern int optopt; /* character checked for validity */ -extern int optreset; /* reset getopt */ -extern char *optarg; /* argument associated with option */ - -#define __P(x) x -#define _DIAGASSERT(x) assert(x) - -static char * __progname __P((char *)); -int getopt_internal __P((int, char * const *, const char *)); - -static char * -__progname(nargv0) - char * nargv0; -{ - char * tmp; - - _DIAGASSERT(nargv0 != NULL); - - tmp = strrchr(nargv0, '/'); - if (tmp) - tmp++; - else - tmp = nargv0; - return(tmp); -} - -#define BADCH (int)'?' -#define BADARG (int)':' -#define EMSG "" - -/* - * getopt -- - * Parse argc/argv argument vector. - */ -int -getopt_internal(nargc, nargv, ostr) - int nargc; - char * const *nargv; - const char *ostr; -{ - static char *place = EMSG; /* option letter processing */ - char *oli; /* option letter list index */ - - _DIAGASSERT(nargv != NULL); - _DIAGASSERT(ostr != NULL); - - if (optreset || !*place) { /* update scanning pointer */ - optreset = 0; - if (optind >= nargc || *(place = nargv[optind]) != '-') { - place = EMSG; - return (-1); - } - if (place[1] && *++place == '-') { /* found "--" */ - /* ++optind; */ - place = EMSG; - return (-2); - } - } /* option letter okay? */ - if ((optopt = (int)*place++) == (int)':' || - !(oli = strchr(ostr, optopt))) { - /* - * if the user didn't specify '-' as an option, - * assume it means -1. - */ - if (optopt == (int)'-') - return (-1); - if (!*place) - ++optind; - if (opterr && *ostr != ':') - (void)fprintf(stderr, - "%s: illegal option -- %c\n", __progname(nargv[0]), optopt); - return (BADCH); - } - if (*++oli != ':') { /* don't need argument */ - optarg = NULL; - if (!*place) - ++optind; - } else { /* need an argument */ - if (*place) /* no white space */ - optarg = place; - else if (nargc <= ++optind) { /* no arg */ - place = EMSG; - if ((opterr) && (*ostr != ':')) - (void)fprintf(stderr, - "%s: option requires an argument -- %c\n", - __progname(nargv[0]), optopt); - return (BADARG); - } else /* white space */ - optarg = nargv[optind]; - place = EMSG; - ++optind; - } - return (optopt); /* dump back option letter */ -} - -#if 0 -/* - * getopt -- - * Parse argc/argv argument vector. - */ -int -getopt2(nargc, nargv, ostr) - int nargc; - char * const *nargv; - const char *ostr; -{ - int retval; - - if ((retval = getopt_internal(nargc, nargv, ostr)) == -2) { - retval = -1; - ++optind; - } - return(retval); -} -#endif - -/* - * getopt_long -- - * Parse argc/argv argument vector. - */ -int -getopt_long(nargc, nargv, options, long_options, index) - int nargc; - char ** nargv; - const char * options; - const struct option * long_options; - int * index; -{ - int retval; - - _DIAGASSERT(nargv != NULL); - _DIAGASSERT(options != NULL); - _DIAGASSERT(long_options != NULL); - /* index may be NULL */ - - if ((retval = getopt_internal(nargc, nargv, options)) == -2) { - char *current_argv = nargv[optind++] + 2, *has_equal; - int i, current_argv_len, match = -1; - - if (*current_argv == '\0') { - return(-1); - } - if ((has_equal = strchr(current_argv, '=')) != NULL) { - current_argv_len = has_equal - current_argv; - has_equal++; - } else - current_argv_len = strlen(current_argv); - - for (i = 0; long_options[i].name; i++) { - if (strncmp(current_argv, long_options[i].name, current_argv_len)) - continue; - - if (strlen(long_options[i].name) == (unsigned)current_argv_len) { - match = i; - break; - } - if (match == -1) - match = i; - } - if (match != -1) { - if (long_options[match].has_arg == required_argument || - long_options[match].has_arg == optional_argument) { - if (has_equal) - optarg = has_equal; - else - optarg = nargv[optind++]; - } - if ((long_options[match].has_arg == required_argument) - && (optarg == NULL)) { - /* - * Missing argument, leading : - * indicates no error should be generated - */ - if ((opterr) && (*options != ':')) - (void)fprintf(stderr, - "%s: option requires an argument -- %s\n", - __progname(nargv[0]), current_argv); - return (BADARG); - } - } else { /* No matching argument */ - if ((opterr) && (*options != ':')) - (void)fprintf(stderr, - "%s: illegal option -- %s\n", __progname(nargv[0]), current_argv); - return (BADCH); - } - if (long_options[match].flag) { - *long_options[match].flag = long_options[match].val; - retval = 0; - } else - retval = long_options[match].val; - if (index) - *index = match; - } - return(retval); -} diff --git a/libs/libevent/src/WIN32-Code/nmake/evconfig-private.h b/libs/libevent/src/WIN32-Code/nmake/evconfig-private.h deleted file mode 100644 index 88e206272b..0000000000 --- a/libs/libevent/src/WIN32-Code/nmake/evconfig-private.h +++ /dev/null @@ -1,6 +0,0 @@ -#if !defined(EVENT_EVCONFIG__PRIVATE_H_) && !defined(__MINGW32__) -#define EVENT_EVCONFIG__PRIVATE_H_ - -/* Nothing to see here. Move along. */ - -#endif diff --git a/libs/libevent/src/WIN32-Code/nmake/event2/event-config.h b/libs/libevent/src/WIN32-Code/nmake/event2/event-config.h deleted file mode 100644 index 8cbf190289..0000000000 --- a/libs/libevent/src/WIN32-Code/nmake/event2/event-config.h +++ /dev/null @@ -1,360 +0,0 @@ -/* event2/event-config.h - * - * This file was generated by autoconf when libevent was built, and post- - * processed by Libevent so that its macros would have a uniform prefix. - * - * DO NOT EDIT THIS FILE. - * - * Do not rely on macros in this file existing in later versions. - */ -#ifndef EVENT_CONFIG_H__ -#define EVENT_CONFIG_H__ -/* config.h. Generated by configure. */ -/* config.h.in. Generated from configure.in by autoheader. */ - -/* Define if libevent should not allow replacing the mm functions */ -/* #undef EVENT__DISABLE_MM_REPLACEMENT */ - -/* Define if libevent should not be compiled with thread support */ -/* #undef EVENT__DISABLE_THREAD_SUPPORT */ - -/* Define if clock_gettime is available in libc */ -/* #undef _EVENT_DNS_USE_CPU_CLOCK_FOR_ID */ - -/* Define is no secure id variant is available */ -/* #define _EVENT_DNS_USE_GETTIMEOFDAY_FOR_ID 1 */ -#define EVENT_DNS_USE_FTIME_FOR_ID_ 1 - -/* Define to 1 if you have the <arpa/inet.h> header file. */ -/* #undef EVENT__HAVE_ARPA_INET_H */ - -/* Define to 1 if you have the `clock_gettime' function. */ -/* #undef EVENT__HAVE_CLOCK_GETTIME */ - -/* Define if /dev/poll is available */ -/* #undef EVENT__HAVE_DEVPOLL */ - -/* Define to 1 if you have the <dlfcn.h> header file. */ -/* #undef EVENT__HAVE_DLFCN_H */ - -/* Define if your system supports the epoll system calls */ -/* #undef EVENT__HAVE_EPOLL */ - -/* Define to 1 if you have the `epoll_ctl' function. */ -/* #undef EVENT__HAVE_EPOLL_CTL */ - -/* Define to 1 if you have the `eventfd' function. */ -/* #undef EVENT__HAVE_EVENTFD */ - -/* Define if your system supports event ports */ -/* #undef EVENT__HAVE_EVENT_PORTS */ - -/* Define to 1 if you have the `fcntl' function. */ -/* #undef EVENT__HAVE_FCNTL */ - -/* Define to 1 if you have the <fcntl.h> header file. */ -#define EVENT__HAVE_FCNTL_H 1 - -/* Define to 1 if you have the `getaddrinfo' function. */ -#define EVENT__HAVE_GETADDRINFO 1 - -/* Define to 1 if you have the `getnameinfo' function. */ -#define EVENT__HAVE_GETNAMEINFO 1 - -/* Define to 1 if you have the `getprotobynumber' function. */ -#define EVENT__HAVE_GETPROTOBYNUMBER 1 - -/* Define to 1 if you have the `getservbyname' function. */ -#define EVENT__HAVE_GETSERVBYNAME 1 - -/* Define to 1 if you have the `gettimeofday' function. */ -/* #define EVENT__HAVE_GETTIMEOFDAY 1 */ - -/* Define to 1 if you have the `inet_ntop' function. */ -/* #undef EVENT__HAVE_INET_NTOP */ - -/* Define to 1 if you have the `inet_pton' function. */ -/* #undef EVENT__HAVE_INET_PTON */ - -/* Define to 1 if you have the <inttypes.h> header file. */ -/* #define EVENT__HAVE_INTTYPES_H 1 */ - -/* Define to 1 if you have the `kqueue' function. */ -/* #undef EVENT__HAVE_KQUEUE */ - -/* Define if the system has zlib */ -/* #undef EVENT__HAVE_LIBZ */ - -/* Define to 1 if you have the <memory.h> header file. */ -#define EVENT__HAVE_MEMORY_H 1 - -/* Define to 1 if you have the `mmap' function. */ -/* #undef EVENT__HAVE_MMAP */ - -/* Define to 1 if you have the <netinet/in6.h> header file. */ -/* #undef EVENT__HAVE_NETINET_IN6_H */ - -/* Define to 1 if you have the <netinet/in.h> header file. */ -/* #undef EVENT__HAVE_NETINET_IN_H */ - -/* Define to 1 if you have the `pipe' function. */ -/* #undef EVENT__HAVE_PIPE */ - -/* Define to 1 if you have the `poll' function. */ -/* #undef EVENT__HAVE_POLL */ - -/* Define to 1 if you have the <poll.h> header file. */ -/* #undef EVENT__HAVE_POLL_H */ - -/* Define to 1 if you have the `port_create' function. */ -/* #undef EVENT__HAVE_PORT_CREATE */ - -/* Define to 1 if you have the <port.h> header file. */ -/* #undef EVENT__HAVE_PORT_H */ - -/* Define if you have POSIX threads libraries and header files. */ -/* #undef EVENT__HAVE_PTHREAD */ - -/* Define if we have pthreads on this system */ -/* #undef EVENT__HAVE_PTHREADS */ - -/* Define to 1 if the system has the type `sa_family_t'. */ -/* #undef EVENT__HAVE_SA_FAMILY_T */ - -/* Define to 1 if you have the `select' function. */ -/* #undef EVENT__HAVE_SELECT */ - -/* Define to 1 if you have the `sendfile' function. */ -/* #undef EVENT__HAVE_SENDFILE */ - -/* Define if F_SETFD is defined in <fcntl.h> */ -/* #undef EVENT__HAVE_SETFD */ - -/* Define to 1 if you have the `sigaction' function. */ -/* #undef EVENT__HAVE_SIGACTION */ - -/* Define to 1 if you have the `signal' function. */ -#define EVENT__HAVE_SIGNAL 1 - -/* Define to 1 if you have the `splice' function. */ -/* #undef EVENT__HAVE_SPLICE */ - -/* Define to 1 if you have the <stdarg.h> header file. */ -#define EVENT__HAVE_STDARG_H 1 - -/* Define to 1 if you have the <stddef.h> header file. */ -#define EVENT__HAVE_STDDEF_H 1 - -/* Define to 1 if you have the <stdint.h> header file. */ -/* #define EVENT__HAVE_STDINT_H 1 */ - -/* Define to 1 if you have the <stdlib.h> header file. */ -#define EVENT__HAVE_STDLIB_H 1 - -/* Define to 1 if you have the <strings.h> header file. */ -#define EVENT__HAVE_STRINGS_H 1 - -/* Define to 1 if you have the <string.h> header file. */ -#define EVENT__HAVE_STRING_H 1 - -/* Define to 1 if you have the `strlcpy' function. */ -/* #undef EVENT__HAVE_STRLCPY */ - -/* Define to 1 if you have the `strsep' function. */ -/* #undef EVENT__HAVE_STRSEP */ - -/* Define to 1 if you have the `strtok_r' function. */ -/* #undef EVENT__HAVE_STRTOK_R */ - -/* Define to 1 if you have the `strtoll' function. */ -/* #define EVENT__HAVE_STRTOLL 1 */ - -#define EVENT__HAVE_STRUCT_ADDRINFO 1 - -/* Define to 1 if the system has the type `struct in6_addr'. */ -#define EVENT__HAVE_STRUCT_IN6_ADDR 1 - -/* Define to 1 if `s6_addr16' is member of `struct in6_addr'. */ -#define EVENT__HAVE_STRUCT_IN6_ADDR_S6_ADDR16 1 - -/* Define to 1 if `s6_addr32' is member of `struct in6_addr'. */ -#define EVENT__HAVE_STRUCT_IN6_ADDR_S6_ADDR32 1 - -/* Define to 1 if the system has the type `struct sockaddr_in6'. */ -#define EVENT__HAVE_STRUCT_SOCKADDR_IN6 1 - -/* Define to 1 if `sin6_len' is member of `struct sockaddr_in6'. */ -/* #undef EVENT__HAVE_STRUCT_SOCKADDR_IN6_SIN6_LEN */ - -/* Define to 1 if `sin_len' is member of `struct sockaddr_in'. */ -/* #undef EVENT__HAVE_STRUCT_SOCKADDR_IN_SIN_LEN */ - -/* Define to 1 if the system has the type `struct sockaddr_storage'. */ -#define EVENT__HAVE_STRUCT_SOCKADDR_STORAGE 1 - -/* Define to 1 if you have the <sys/devpoll.h> header file. */ -/* #undef EVENT__HAVE_SYS_DEVPOLL_H */ - -/* Define to 1 if you have the <sys/epoll.h> header file. */ -/* #undef EVENT__HAVE_SYS_EPOLL_H */ - -/* Define to 1 if you have the <sys/eventfd.h> header file. */ -/* #undef EVENT__HAVE_SYS_EVENTFD_H */ - -/* Define to 1 if you have the <sys/event.h> header file. */ -/* #undef EVENT__HAVE_SYS_EVENT_H */ - -/* Define to 1 if you have the <sys/ioctl.h> header file. */ -/* #undef EVENT__HAVE_SYS_IOCTL_H */ - -/* Define to 1 if you have the <sys/mman.h> header file. */ -/* #undef EVENT__HAVE_SYS_MMAN_H */ - -/* Define to 1 if you have the <sys/param.h> header file. */ -/* #define EVENT__HAVE_SYS_PARAM_H 1 */ - -/* Define to 1 if you have the <sys/queue.h> header file. */ -/* #undef EVENT__HAVE_SYS_QUEUE_H */ - -/* Define to 1 if you have the <sys/select.h> header file. */ -/* #undef EVENT__HAVE_SYS_SELECT_H */ - -/* Define to 1 if you have the <sys/sendfile.h> header file. */ -/* #undef EVENT__HAVE_SYS_SENDFILE_H */ - -/* Define to 1 if you have the <sys/socket.h> header file. */ -/* #undef EVENT__HAVE_SYS_SOCKET_H */ - -/* Define to 1 if you have the <sys/stat.h> header file. */ -#define EVENT__HAVE_SYS_STAT_H 1 - -/* Define to 1 if you have the <sys/time.h> header file. */ -/* #define EVENT__HAVE_SYS_TIME_H 1 */ - -/* Define to 1 if you have the <sys/types.h> header file. */ -#define EVENT__HAVE_SYS_TYPES_H 1 - -/* Define to 1 if you have the <sys/uio.h> header file. */ -/* #undef EVENT__HAVE_SYS_UIO_H */ - -/* Define if TAILQ_FOREACH is defined in <sys/queue.h> */ -/* #undef EVENT__HAVE_TAILQFOREACH */ - -/* Define if timeradd is defined in <sys/time.h> */ -/* #undef EVENT__HAVE_TIMERADD */ - -/* Define if timerclear is defined in <sys/time.h> */ -#define EVENT__HAVE_TIMERCLEAR 1 - -/* Define if timercmp is defined in <sys/time.h> */ -#define EVENT__HAVE_TIMERCMP 1 - -/* Define if timerisset is defined in <sys/time.h> */ -#define EVENT__HAVE_TIMERISSET 1 - -/* Define to 1 if the system has the type `uint16_t'. */ -/* #define EVENT__HAVE_UINT16_T 1 */ - -/* Define to 1 if the system has the type `uint32_t'. */ -/* #define EVENT__HAVE_UINT32_T 1 */ - -/* Define to 1 if the system has the type `uint64_t'. */ -/* #define EVENT__HAVE_UINT64_T 1 */ - -/* Define to 1 if the system has the type `uint8_t'. */ -/* #define EVENT__HAVE_UINT8_T 1 */ - -/* Define to 1 if you have the <unistd.h> header file. */ -/* #define EVENT__HAVE_UNISTD_H 1 */ - -/* Define to 1 if you have the `vasprintf' function. */ -/* #undef EVENT__HAVE_VASPRINTF */ - -/* Define if kqueue works correctly with pipes */ -/* #undef EVENT__HAVE_WORKING_KQUEUE */ - -/* Numeric representation of the version */ -#define EVENT__NUMERIC_VERSION 0x02010500 - -/* Name of package */ -#define EVENT__PACKAGE "libevent" - -/* Define to the address where bug reports for this package should be sent. */ -#define EVENT__PACKAGE_BUGREPORT "" - -/* Define to the full name of this package. */ -#define EVENT__PACKAGE_NAME "" - -/* Define to the full name and version of this package. */ -#define EVENT__PACKAGE_STRING "" - -/* Define to the one symbol short name of this package. */ -#define EVENT__PACKAGE_TARNAME "" - -/* Define to the version of this package. */ -#define EVENT__PACKAGE_VERSION "" - -/* Define to necessary symbol if this constant uses a non-standard name on - your system. */ -/* #undef EVENT__PTHREAD_CREATE_JOINABLE */ - -/* The size of a `int', as computed by sizeof. */ -#define EVENT__SIZEOF_INT 4 - -/* The size of a `long', as computed by sizeof. */ -#define EVENT__SIZEOF_LONG 4 - -/* The size of a `long long', as computed by sizeof. */ -#define EVENT__SIZEOF_LONG_LONG 8 - -/* The size of a `short', as computed by sizeof. */ -#define EVENT__SIZEOF_SHORT 2 - -/* The size of `size_t', as computed by sizeof. */ -#ifdef _WIN64 -#define EVENT__SIZEOF_SIZE_T 8 -#else -#define EVENT__SIZEOF_SIZE_T 4 -#endif - -/* The size of `void *', as computed by sizeof. */ -#ifdef _WIN64 -#define EVENT__SIZEOF_VOID_P 8 -#else -#define EVENT__SIZEOF_VOID_P 4 -#endif - -/* Define to 1 if you have the ANSI C header files. */ -#define EVENT__STDC_HEADERS 1 - -/* Define to 1 if you can safely include both <sys/time.h> and <time.h>. */ -#define EVENT__TIME_WITH_SYS_TIME 1 - -/* Version number of package */ -#define EVENT__VERSION "2.1.5-beta" - -/* Define to appropriate substitue if compiler doesnt have __func__ */ -#define EVENT____func__ __FUNCTION__ - -/* Define to empty if `const' does not conform to ANSI C. */ -/* #undef EVENT__const */ - -/* Define to `__inline__' or `__inline' if that's what the C compiler - calls it, or to nothing if 'inline' is not supported under any name. */ -#ifndef _EVENT___cplusplus -#define EVENT__inline __inline -#endif - -/* Define to `int' if <sys/types.h> does not define. */ -/* #undef EVENT__pid_t */ - -/* Define to `unsigned' if <sys/types.h> does not define. */ -/* #undef EVENT__size_t */ - -/* Define to unsigned int if you dont have it */ -#define EVENT__socklen_t unsigned int - -/* Define to `int' if <sys/types.h> does not define. */ -#define EVENT__ssize_t SSIZE_T - -#endif diff --git a/libs/libevent/src/WIN32-Code/tree.h b/libs/libevent/src/WIN32-Code/tree.h deleted file mode 100644 index 2ccfbf20ac..0000000000 --- a/libs/libevent/src/WIN32-Code/tree.h +++ /dev/null @@ -1,677 +0,0 @@ -/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art 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-back 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) -#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) \ -void name##_RB_INSERT_COLOR(struct name *, struct type *); \ -void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -struct type *name##_RB_REMOVE(struct name *, struct type *); \ -struct type *name##_RB_INSERT(struct name *, struct type *); \ -struct type *name##_RB_FIND(struct name *, struct type *); \ -struct type *name##_RB_NEXT(struct type *); \ -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) \ -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; \ -} \ - \ -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; \ -} \ - \ -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 */ \ -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 */ \ -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); \ -} \ - \ -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); \ -} \ - \ -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_NEXT(name, x, y) name##_RB_NEXT(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)) - -#endif /* _SYS_TREE_H_ */ |