diff options
author | Josh Gao <jmgao@google.com> | 2017-08-10 12:30:25 -0700 |
---|---|---|
committer | Josh Gao <jmgao@google.com> | 2017-08-10 12:30:47 -0700 |
commit | 83a0c9c65a60a92d3ea5542596b3ba56db492c37 (patch) | |
tree | 64bb0c050c4db9ad9d721e05e3e199bfd02e60b0 /WIN32-Code | |
parent | af241a5c8c2cde0fab7d7d563276c1095b00e3b4 (diff) | |
download | libevent-83a0c9c65a60a92d3ea5542596b3ba56db492c37.tar.gz |
Revert "Upgrade to 2.1.8-stable (2017-01-22)." and "Probably Mac build fix?"android-o-iot-preview-5o-iot-preview-5
This reverts commits 2a572d125a91a4aafd3ad8ce87259fc640fa0763 and
af241a5c8c2cde0fab7d7d563276c1095b00e3b4, which break tombstoned.
Bug: http://b/64543673
Test: manual + treehugger
Diffstat (limited to 'WIN32-Code')
-rw-r--r-- | WIN32-Code/nmake/evconfig-private.h | 6 | ||||
-rw-r--r-- | WIN32-Code/nmake/event2/event-config.h | 360 | ||||
-rw-r--r-- | WIN32-Code/tree.h | 677 |
3 files changed, 0 insertions, 1043 deletions
diff --git a/WIN32-Code/nmake/evconfig-private.h b/WIN32-Code/nmake/evconfig-private.h deleted file mode 100644 index 88e2062..0000000 --- a/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/WIN32-Code/nmake/event2/event-config.h b/WIN32-Code/nmake/event2/event-config.h deleted file mode 100644 index e6ed3aa..0000000 --- a/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 0x02010800 - -/* 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.8-stable" - -/* 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/WIN32-Code/tree.h b/WIN32-Code/tree.h deleted file mode 100644 index 2ccfbf2..0000000 --- a/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_ */ |