diff options
Diffstat (limited to 'libevent/WIN32-Code')
| -rw-r--r-- | libevent/WIN32-Code/event-config.h | 244 | ||||
| -rw-r--r-- | libevent/WIN32-Code/misc.c | 93 | ||||
| -rw-r--r-- | libevent/WIN32-Code/misc.h | 11 | ||||
| -rw-r--r-- | libevent/WIN32-Code/tree.h | 1354 | ||||
| -rw-r--r-- | libevent/WIN32-Code/win32.c | 486 |
5 files changed, 2188 insertions, 0 deletions
diff --git a/libevent/WIN32-Code/event-config.h b/libevent/WIN32-Code/event-config.h new file mode 100644 index 00000000000..3059080274b --- /dev/null +++ b/libevent/WIN32-Code/event-config.h @@ -0,0 +1,244 @@ +/* event-config.h + * Generated by autoconf; post-processed by libevent. + * 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 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 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 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. */ +/* #undef _EVENT_HAVE_GETADDRINFO */ + +/* Define to 1 if you have the `getnameinfo' function. */ +/* #undef _EVENT_HAVE_GETNAMEINFO */ + +/* 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 <inttypes.h> header file. */ +/* #undef _EVENT_HAVE_INTTYPES_H 1 */ + +/* Define to 1 if you have the `kqueue' function. */ +/* #undef _EVENT_HAVE_KQUEUE */ + +/* Define to 1 if you have the `nsl' library (-lnsl). */ +/* #undef _EVENT_HAVE_LIBNSL */ + +/* Define to 1 if you have the `resolv' library (-lresolv). */ +/* #undef _EVENT_HAVE_LIBRESOLV */ + +/* Define to 1 if you have the `rt' library (-lrt). */ +/* #undef _EVENT_HAVE_LIBRT */ + +/* Define to 1 if you have the `socket' library (-lsocket). */ +/* #undef _EVENT_HAVE_LIBSOCKET */ + +/* Define to 1 if you have the <memory.h> header file. */ +#define _EVENT_HAVE_MEMORY_H 1 + +/* 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 `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 to 1 if you have the `select' function. */ +/* #undef _EVENT_HAVE_SELECT */ + +/* 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 <signal.h> header file. */ +#define _EVENT_HAVE_SIGNAL_H 1 + +/* Define to 1 if you have the <stdarg.h> header file. */ +#define _EVENT_HAVE_STDARG_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 the system has the type `struct in6_addr'. */ +#define _EVENT_HAVE_STRUCT_IN6_ADDR 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/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/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/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 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 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 */ + +/* 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 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 "1.3.99-trunk" + +/* Define to appropriate substitue if compiler doesnt have __func__ */ +/* #undef _EVENT___func__ */ + +/* 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 `unsigned short' if <sys/types.h> does not define. */ +/* #undef _EVENT_uint16_t */ + +/* Define to `unsigned int' if <sys/types.h> does not define. */ +/* #undef _EVENT_uint32_t */ + +/* Define to `unsigned long long' if <sys/types.h> does not define. */ +/* #undef _EVENT_uint64_t */ + +/* Define to `unsigned char' if <sys/types.h> does not define. */ +/* #undef _EVENT_uint8_t */ +#endif diff --git a/libevent/WIN32-Code/misc.c b/libevent/WIN32-Code/misc.c new file mode 100644 index 00000000000..371e192beae --- /dev/null +++ b/libevent/WIN32-Code/misc.c @@ -0,0 +1,93 @@ +#include <stdio.h> +#include <string.h> +#include <windows.h> +#include <sys/timeb.h> +#include <time.h> + +#ifdef __GNUC__ +/*our prototypes for timeval and timezone are in here, just in case the above + headers don't have them*/ +#include "misc.h" +#endif + +/**************************************************************************** + * + * Function: gettimeofday(struct timeval *, struct timezone *) + * + * Purpose: Get current time of day. + * + * Arguments: tv => Place to store the curent time of day. + * tz => Ignored. + * + * Returns: 0 => Success. + * + ****************************************************************************/ + +#ifndef HAVE_GETTIMEOFDAY +int gettimeofday(struct timeval *tv, struct timezone *tz) { + struct _timeb tb; + + if(tv == NULL) + return -1; + + _ftime(&tb); + tv->tv_sec = (long) tb.time; + tv->tv_usec = ((int) tb.millitm) * 1000; + return 0; +} +#endif + +#if 0 +int +win_read(int fd, void *buf, unsigned int length) +{ + DWORD dwBytesRead; + int res = ReadFile((HANDLE) fd, buf, length, &dwBytesRead, NULL); + if (res == 0) { + DWORD error = GetLastError(); + if (error == ERROR_NO_DATA) + return (0); + return (-1); + } else + return (dwBytesRead); +} + +int +win_write(int fd, void *buf, unsigned int length) +{ + DWORD dwBytesWritten; + int res = WriteFile((HANDLE) fd, buf, length, &dwBytesWritten, NULL); + if (res == 0) { + DWORD error = GetLastError(); + if (error == ERROR_NO_DATA) + return (0); + return (-1); + } else + return (dwBytesWritten); +} + +int +socketpair(int d, int type, int protocol, int *sv) +{ + static int count; + char buf[64]; + HANDLE fd; + DWORD dwMode; + sprintf(buf, "\\\\.\\pipe\\levent-%d", count++); + /* Create a duplex pipe which will behave like a socket pair */ + fd = CreateNamedPipe(buf, PIPE_ACCESS_DUPLEX, PIPE_TYPE_BYTE | PIPE_NOWAIT, + PIPE_UNLIMITED_INSTANCES, 4096, 4096, 0, NULL); + if (fd == INVALID_HANDLE_VALUE) + return (-1); + sv[0] = (int)fd; + + fd = CreateFile(buf, GENERIC_READ|GENERIC_WRITE, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL); + if (fd == INVALID_HANDLE_VALUE) + return (-1); + dwMode = PIPE_NOWAIT; + SetNamedPipeHandleState(fd, &dwMode, NULL, NULL); + sv[1] = (int)fd; + + return (0); +} +#endif diff --git a/libevent/WIN32-Code/misc.h b/libevent/WIN32-Code/misc.h new file mode 100644 index 00000000000..aced574687c --- /dev/null +++ b/libevent/WIN32-Code/misc.h @@ -0,0 +1,11 @@ +#ifndef MISC_H +#define MISC_H + +struct timezone; +struct timeval; + +#ifndef HAVE_GETTIMEOFDAY +int gettimeofday(struct timeval *,struct timezone *); +#endif + +#endif diff --git a/libevent/WIN32-Code/tree.h b/libevent/WIN32-Code/tree.h new file mode 100644 index 00000000000..79e8d91f0eb --- /dev/null +++ b/libevent/WIN32-Code/tree.h @@ -0,0 +1,1354 @@ +/* $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_ */ +/* $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_ */ diff --git a/libevent/WIN32-Code/win32.c b/libevent/WIN32-Code/win32.c new file mode 100644 index 00000000000..8a603b7eceb --- /dev/null +++ b/libevent/WIN32-Code/win32.c @@ -0,0 +1,486 @@ +/* + * Copyright 2000-2002 Niels Provos <provos@citi.umich.edu> + * Copyright 2003 Michael A. Davis <mike@datanerds.net> + * 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. 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. + */ +#ifdef _MSC_VER +#include "./config.h" +#else +/* Avoid the windows/msvc thing. */ +#include "../config.h" +#endif + +#include <winsock2.h> +#include <windows.h> +#include <sys/types.h> +#include <sys/queue.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <errno.h> +#include <assert.h> + +#define RB_AUGMENT(x) (void)(x) +#include "./tree.h" +#include "log.h" +#include "event.h" +#include "event-internal.h" + +#define XFREE(ptr) do { if (ptr) free(ptr); } while(0) + +extern struct event_list timequeue; +extern struct event_list addqueue; +#if 0 +extern struct event_list signalqueue; +#endif + +struct win_fd_set { + u_int fd_count; + SOCKET fd_array[1]; +}; + +int evsigcaught[NSIG]; +volatile sig_atomic_t signal_caught = 0; +/* MSDN says this is required to handle SIGFPE */ +volatile double SIGFPE_REQ = 0.0f; + +#if 0 +static void signal_handler(int sig); + +void signal_process(void); +int signal_recalc(void); +#endif + +struct event_entry { + RB_ENTRY(event_entry) node; + SOCKET sock; + int read_pos; + int write_pos; + struct event *read_event; + struct event *write_event; +}; + +static int +compare(struct event_entry *a, struct event_entry *b) +{ + if (a->sock < b->sock) + return -1; + else if (a->sock > b->sock) + return 1; + else + return 0; +} + +struct win32op { + int fd_setsz; + struct win_fd_set *readset_in; + struct win_fd_set *writeset_in; + struct win_fd_set *readset_out; + struct win_fd_set *writeset_out; + struct win_fd_set *exset_out; + RB_HEAD(event_map, event_entry) event_root; + + unsigned signals_are_broken : 1; +}; + +RB_PROTOTYPE(event_map, event_entry, node, compare); +RB_GENERATE(event_map, event_entry, node, compare); + +void *win32_init (struct event_base *); +int win32_insert (void *, struct event *); +int win32_del (void *, struct event *); +int win32_dispatch (struct event_base *base, void *, struct timeval *); +void win32_dealloc (struct event_base *, void *); + +struct eventop win32ops = { + "win32", + win32_init, + win32_insert, + win32_del, + win32_dispatch, + win32_dealloc, + 0 +}; + +#define FD_SET_ALLOC_SIZE(n) ((sizeof(struct win_fd_set) + ((n)-1)*sizeof(SOCKET))) + +static int +realloc_fd_sets(struct win32op *op, size_t new_size) +{ + size_t size; + + assert(new_size >= op->readset_in->fd_count && + new_size >= op->writeset_in->fd_count); + assert(new_size >= 1); + + size = FD_SET_ALLOC_SIZE(new_size); + if (!(op->readset_in = realloc(op->readset_in, size))) + return (-1); + if (!(op->writeset_in = realloc(op->writeset_in, size))) + return (-1); + if (!(op->readset_out = realloc(op->readset_out, size))) + return (-1); + if (!(op->exset_out = realloc(op->exset_out, size))) + return (-1); + if (!(op->writeset_out = realloc(op->writeset_out, size))) + return (-1); + op->fd_setsz = new_size; + return (0); +} + +static int +timeval_to_ms(struct timeval *tv) +{ + return ((tv->tv_sec * 1000) + (tv->tv_usec / 1000)); +} + +static struct event_entry* +get_event_entry(struct win32op *op, SOCKET s, int create) +{ + struct event_entry key, *val; + key.sock = s; + val = RB_FIND(event_map, &op->event_root, &key); + if (val || !create) + return val; + if (!(val = calloc(1, sizeof(struct event_entry)))) { + event_warn("%s: calloc", __func__); + return NULL; + } + val->sock = s; + val->read_pos = val->write_pos = -1; + RB_INSERT(event_map, &op->event_root, val); + return val; +} + +static int +do_fd_set(struct win32op *op, struct event_entry *ent, int read) +{ + SOCKET s = ent->sock; + struct win_fd_set *set = read ? op->readset_in : op->writeset_in; + if (read) { + if (ent->read_pos >= 0) + return (0); + } else { + if (ent->write_pos >= 0) + return (0); + } + if (set->fd_count == op->fd_setsz) { + if (realloc_fd_sets(op, op->fd_setsz*2)) + return (-1); + /* set pointer will have changed and needs reiniting! */ + set = read ? op->readset_in : op->writeset_in; + } + set->fd_array[set->fd_count] = s; + if (read) + ent->read_pos = set->fd_count; + else + ent->write_pos = set->fd_count; + return (set->fd_count++); +} + +static int +do_fd_clear(struct win32op *op, struct event_entry *ent, int read) +{ + int i; + struct win_fd_set *set = read ? op->readset_in : op->writeset_in; + if (read) { + i = ent->read_pos; + ent->read_pos = -1; + } else { + i = ent->write_pos; + ent->write_pos = -1; + } + if (i < 0) + return (0); + if (--set->fd_count != i) { + struct event_entry *ent2; + SOCKET s2; + s2 = set->fd_array[i] = set->fd_array[set->fd_count]; + ent2 = get_event_entry(op, s2, 0); + if (!ent) /* This indicates a bug. */ + return (0); + if (read) + ent2->read_pos = i; + else + ent2->write_pos = i; + } + return (0); +} + +#define NEVENT 64 +void * +win32_init(struct event_base *_base) +{ + struct win32op *winop; + size_t size; + if (!(winop = calloc(1, sizeof(struct win32op)))) + return NULL; + winop->fd_setsz = NEVENT; + size = FD_SET_ALLOC_SIZE(NEVENT); + if (!(winop->readset_in = malloc(size))) + goto err; + if (!(winop->writeset_in = malloc(size))) + goto err; + if (!(winop->readset_out = malloc(size))) + goto err; + if (!(winop->writeset_out = malloc(size))) + goto err; + if (!(winop->exset_out = malloc(size))) + goto err; + RB_INIT(&winop->event_root); + winop->readset_in->fd_count = winop->writeset_in->fd_count = 0; + winop->readset_out->fd_count = winop->writeset_out->fd_count + = winop->exset_out->fd_count = 0; + + if (evsignal_init(_base) < 0) + winop->signals_are_broken = 1; + + return (winop); + err: + XFREE(winop->readset_in); + XFREE(winop->writeset_in); + XFREE(winop->readset_out); + XFREE(winop->writeset_out); + XFREE(winop->exset_out); + XFREE(winop); + return (NULL); +} + +int +win32_insert(void *op, struct event *ev) +{ + struct win32op *win32op = op; + struct event_entry *ent; + + if (ev->ev_events & EV_SIGNAL) { + if (win32op->signals_are_broken) + return (-1); + return (evsignal_add(ev)); + } + if (!(ev->ev_events & (EV_READ|EV_WRITE))) + return (0); + ent = get_event_entry(win32op, ev->ev_fd, 1); + if (!ent) + return (-1); /* out of memory */ + + event_debug(("%s: adding event for %d", __func__, (int)ev->ev_fd)); + if (ev->ev_events & EV_READ) { + if (do_fd_set(win32op, ent, 1)<0) + return (-1); + ent->read_event = ev; + } + if (ev->ev_events & EV_WRITE) { + if (do_fd_set(win32op, ent, 0)<0) + return (-1); + ent->write_event = ev; + } + return (0); +} + +int +win32_del(void *op, struct event *ev) +{ + struct win32op *win32op = op; + struct event_entry *ent; + + if (ev->ev_events & EV_SIGNAL) + return (evsignal_del(ev)); + + if (!(ent = get_event_entry(win32op, ev->ev_fd, 0))) + return (-1); + event_debug(("%s: Removing event for %d", __func__, ev->ev_fd)); + if (ev == ent->read_event) { + do_fd_clear(win32op, ent, 1); + ent->read_event = NULL; + } + if (ev == ent->write_event) { + do_fd_clear(win32op, ent, 0); + ent->write_event = NULL; + } + if (!ent->read_event && !ent->write_event) { + RB_REMOVE(event_map, &win32op->event_root, ent); + free(ent); + } + + return 0; +} + +static void +fd_set_copy(struct win_fd_set *out, const struct win_fd_set *in) +{ + out->fd_count = in->fd_count; + memcpy(out->fd_array, in->fd_array, in->fd_count * (sizeof(SOCKET))); +} + +/* + static void dump_fd_set(struct win_fd_set *s) + { + unsigned int i; + printf("[ "); + for(i=0;i<s->fd_count;++i) + printf("%d ",(int)s->fd_array[i]); + printf("]\n"); + } +*/ + +int +win32_dispatch(struct event_base *base, void *op, + struct timeval *tv) +{ + struct win32op *win32op = op; + int res = 0; + unsigned j, i; + int fd_count; + SOCKET s; + struct event_entry *ent; + + fd_set_copy(win32op->readset_out, win32op->readset_in); + fd_set_copy(win32op->exset_out, win32op->readset_in); + fd_set_copy(win32op->writeset_out, win32op->writeset_in); + + fd_count = + (win32op->readset_out->fd_count > win32op->writeset_out->fd_count) ? + win32op->readset_out->fd_count : win32op->writeset_out->fd_count; + + if (!fd_count) { + /* Windows doesn't like you to call select() with no sockets */ + Sleep(timeval_to_ms(tv)); + evsignal_process(base); + return (0); + } + + res = select(fd_count, + (struct fd_set*)win32op->readset_out, + (struct fd_set*)win32op->writeset_out, + (struct fd_set*)win32op->exset_out, tv); + + event_debug(("%s: select returned %d", __func__, res)); + + if(res <= 0) { + evsignal_process(base); + return res; + } else if (base->sig.evsignal_caught) { + evsignal_process(base); + } + + if (win32op->readset_out->fd_count) { + i = rand() % win32op->readset_out->fd_count; + for (j=0; j<win32op->readset_out->fd_count; ++j) { + if (++i >= win32op->readset_out->fd_count) + i = 0; + s = win32op->readset_out->fd_array[i]; + if ((ent = get_event_entry(win32op, s, 0)) && ent->read_event) + event_active(ent->read_event, EV_READ, 1); + } + } + if (win32op->exset_out->fd_count) { + i = rand() % win32op->exset_out->fd_count; + for (j=0; j<win32op->exset_out->fd_count; ++j) { + if (++i >= win32op->exset_out->fd_count) + i = 0; + s = win32op->exset_out->fd_array[i]; + if ((ent = get_event_entry(win32op, s, 0)) && ent->read_event) + event_active(ent->read_event, EV_READ, 1); + } + } + if (win32op->writeset_out->fd_count) { + i = rand() % win32op->writeset_out->fd_count; + for (j=0; j<win32op->writeset_out->fd_count; ++j) { + if (++i >= win32op->exset_out->fd_count) + i = 0; + s = win32op->writeset_out->fd_array[i]; + if ((ent = get_event_entry(win32op, s, 0)) && ent->write_event) + event_active(ent->write_event, EV_WRITE, 1); + + } + } + + return (0); +} + +void +win32_dealloc(struct event_base *_base, void *arg) +{ + struct win32op *win32op = arg; + + evsignal_dealloc(_base); + if (win32op->readset_in) + free(win32op->readset_in); + if (win32op->writeset_in) + free(win32op->writeset_in); + if (win32op->readset_out) + free(win32op->readset_out); + if (win32op->writeset_out) + free(win32op->writeset_out); + if (win32op->exset_out) + free(win32op->exset_out); + /* XXXXX free the tree. */ + + memset(win32op, 0, sizeof(win32op)); + free(win32op); +} + +#if 0 +static void +signal_handler(int sig) +{ + evsigcaught[sig]++; + signal_caught = 1; +} + +int +signal_recalc(void) +{ + struct event *ev; + + /* Reinstall our signal handler. */ + TAILQ_FOREACH(ev, &signalqueue, ev_signal_next) { + if((int)signal(EVENT_SIGNAL(ev), signal_handler) == -1) + return (-1); + } + return (0); +} + +void +signal_process(void) +{ + struct event *ev; + short ncalls; + + TAILQ_FOREACH(ev, &signalqueue, ev_signal_next) { + ncalls = evsigcaught[EVENT_SIGNAL(ev)]; + if (ncalls) { + if (!(ev->ev_events & EV_PERSIST)) + event_del(ev); + event_active(ev, EV_SIGNAL, ncalls); + } + } + + memset(evsigcaught, 0, sizeof(evsigcaught)); + signal_caught = 0; +} +#endif + |