From: Date: December 4 2008 10:21am Subject: bzr commit into mysql-6.0 branch (vvaintroub:2681) Bug#41218 List-Archive: http://lists.mysql.com/commits/60577 X-Bug: 41218 Message-Id: <0KBC009VCI090I70@fe-emea-10.sun.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7BIT #At file:///G:/bzr/mysql-6.0-wtf-threadpool/ 2681 Vladislav Vaintroub 2008-12-04 Bug#41218 - Windows port for thread pooling * add porting stuff (Win32-Code subdirectory )from libevent distribution * add libevent library to CMake build * adopt code in scheduler Replace pipes that were used as communication mechanism with libevent with sockets. libevent cannot work with pipes on Windows - this is a limitation of Winsock's select(). added: extra/libevent/CMakeLists.txt extra/libevent/WIN32-Code/ extra/libevent/WIN32-Code/config.h extra/libevent/WIN32-Code/misc.c extra/libevent/WIN32-Code/misc.h extra/libevent/WIN32-Code/tree.h extra/libevent/WIN32-Code/win32.c modified: CMakeLists.txt extra/libevent/Makefile.am extra/libevent/evutil.h include/config-win.h sql/CMakeLists.txt sql/mysqld.cc sql/scheduler.cc per-file messages: CMakeLists.txt compile libevent on Windows extra/libevent/CMakeLists.txt compile libevent on Windows extra/libevent/Makefile.am compile libevent on Windows extra/libevent/WIN32-Code compile libevent on Windows extra/libevent/WIN32-Code/config.h compile libevent on Windows extra/libevent/WIN32-Code/misc.c compile libevent on Windows extra/libevent/WIN32-Code/misc.h compile libevent on Windows extra/libevent/WIN32-Code/tree.h compile libevent on Windows extra/libevent/WIN32-Code/win32.c compile libevent on Windows extra/libevent/evutil.h compile libevent on Windows include/config-win.h compile libevent on Windows sql/CMakeLists.txt link mysqld with libevent sql/mysqld.cc pool of threads only works with sockets on Windows. Abort if named pipe or shared memory protocol used. sql/scheduler.cc Use sockets as communication mechanism with libevent instead of pipes Pipes do not work on windows - a limitation of win32 libevent , underlying select() does not support anything but sockets. === modified file 'CMakeLists.txt' --- a/CMakeLists.txt 2008-11-05 10:19:19 +0000 +++ b/CMakeLists.txt 2008-12-04 09:21:32 +0000 @@ -269,6 +269,7 @@ ADD_SUBDIRECTORY(mysys) ADD_SUBDIRECTORY(scripts) ADD_SUBDIRECTORY(zlib) ADD_SUBDIRECTORY(extra/yassl) +ADD_SUBDIRECTORY(extra/libevent) ADD_SUBDIRECTORY(extra/yassl/taocrypt) ADD_SUBDIRECTORY(extra) ADD_SUBDIRECTORY(storage/heap) === added file 'extra/libevent/CMakeLists.txt' --- a/extra/libevent/CMakeLists.txt 1970-01-01 00:00:00 +0000 +++ b/extra/libevent/CMakeLists.txt 2008-12-04 09:21:32 +0000 @@ -0,0 +1,34 @@ +INCLUDE_DIRECTORIES( + ${CMAKE_SOURCE_DIR}/extra/libevent + ${CMAKE_SOURCE_DIR}/extra/libevent/compat + ${CMAKE_SOURCE_DIR}/extra/libevent/WIN32-Code) + +IF(MSVC) + ADD_DEFINITIONS("-DWIN32 -DHAVE_CONFIG_H") +ENDIF(MSVC) + +SET(LIBEVENT_SOURCES + buffer.c + evbuffer.c + event.c + evutil.c + log.c + signal.c + strlcpy.c + WIN32-Code/win32.c + WIN32-Code/config.h + WIN32-Code/misc.c + WIN32-Code/misc.h + event-internal.h + event.h + evsignal.h + evutil.h + log.h + min_heap.h + strlcpy-internal.h + ) + +CONFIGURE_FILE(WIN32-Code/config.h event-config.h COPYONLY) +IF(NOT SOURCE_SUBLIBS) + ADD_LIBRARY(libevent ${LIBEVENT_SOURCES}) +ENDIF(NOT SOURCE_SUBLIBS) === modified file 'extra/libevent/Makefile.am' --- a/extra/libevent/Makefile.am 2008-04-29 03:50:47 +0000 +++ b/extra/libevent/Makefile.am 2008-12-04 09:21:32 +0000 @@ -5,7 +5,9 @@ EXTRA_DIST = README compat/sys signal.c devpoll.c epoll_sub.c evdns.c event_tagging.c evrpc.c http.c \ log.c select.c strlcpy.c \ evdns.h event.h evrpc-internal.h evsignal.h http-internal.h log.h \ - min_heap.h event-internal.h evhttp.h evrpc.h evutil.h strlcpy-internal.h + min_heap.h event-internal.h evhttp.h evrpc.h evutil.h strlcpy-internal.h \ + WIN32-Code/misc.c WIN32-Code/misc.h WIN32-Code/config.h WIN32-Code/tree.h \ + WIN32-Code/win32.c CMakeLists.txt DISTCLEANFILES = event-config.h === added directory 'extra/libevent/WIN32-Code' === added file 'extra/libevent/WIN32-Code/config.h' --- a/extra/libevent/WIN32-Code/config.h 1970-01-01 00:00:00 +0000 +++ b/extra/libevent/WIN32-Code/config.h 2008-12-04 09:21:32 +0000 @@ -0,0 +1,247 @@ +/* config.h. Generated by configure. */ +/* config.h.in. Generated from configure.in by autoheader. */ + +/* Define if clock_gettime is available in libc */ +/* #undef DNS_USE_CPU_CLOCK_FOR_ID */ + +/* Define if no secure id variant is available */ +#define DNS_USE_FTIME_FOR_ID 1 + +/* Define if no secure id variant is available */ +/* #define DNS_USE_GETTIMEOFDAY_FOR_ID 1 */ + +/* Define to 1 if you have the `clock_gettime' function. */ +/* #undef HAVE_CLOCK_GETTIME */ + +/* Define if /dev/poll is available */ +/* #undef HAVE_DEVPOLL */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_DLFCN_H */ + +/* Define if your system supports the epoll system calls */ +/* #undef HAVE_EPOLL */ + +/* Define to 1 if you have the `epoll_ctl' function. */ +/* #undef HAVE_EPOLL_CTL */ + +/* Define if your system supports event ports */ +/* #undef HAVE_EVENT_PORTS */ + +/* Define to 1 if you have the `fcntl' function. */ +/* #undef HAVE_FCNTL */ + +/* Define to 1 if you have the header file. */ +#define HAVE_FCNTL_H 1 + +/* Define to 1 if you have the `getaddrinfo' function. */ +/* #undef HAVE_GETADDRINFO */ + +/* Define to 1 if you have the `getnameinfo' function. */ +/* #undef HAVE_GETNAMEINFO */ + +/* Define to 1 if you have the `gettimeofday' function. */ +/* #define HAVE_GETTIMEOFDAY 1 */ + +/* Define to 1 if you have the `inet_ntop' function. */ +/* #undef HAVE_INET_NTOP */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_INTTYPES_H 1 */ + +/* Define to 1 if you have the `kqueue' function. */ +/* #undef HAVE_KQUEUE */ + +/* Define to 1 if you have the `nsl' library (-lnsl). */ +/* #undef HAVE_LIBNSL */ + +/* Define to 1 if you have the `resolv' library (-lresolv). */ +/* #undef HAVE_LIBRESOLV */ + +/* Define to 1 if you have the `rt' library (-lrt). */ +/* #undef HAVE_LIBRT */ + +/* Define to 1 if you have the `socket' library (-lsocket). */ +/* #undef HAVE_LIBSOCKET */ + +/* Define to 1 if you have the header file. */ +#define HAVE_MEMORY_H 1 + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_NETINET_IN6_H */ + +/* Define to 1 if you have the `poll' function. */ +/* #undef HAVE_POLL */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_POLL_H */ + +/* Define to 1 if you have the `port_create' function. */ +/* #undef HAVE_PORT_CREATE */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_PORT_H */ + +/* Define to 1 if you have the `select' function. */ +/* #undef HAVE_SELECT */ + +/* Define if F_SETFD is defined in */ +/* #undef HAVE_SETFD */ + +/* Define to 1 if you have the `sigaction' function. */ +/* #undef HAVE_SIGACTION */ + +/* Define to 1 if you have the `signal' function. */ +#define HAVE_SIGNAL 1 + +/* Define to 1 if you have the header file. */ +#define HAVE_SIGNAL_H 1 + +/* Define to 1 if you have the header file. */ +#define HAVE_STDARG_H 1 + +/* Define to 1 if you have the header file. */ +/* #define HAVE_STDINT_H 1 */ + +/* Define to 1 if you have the header file. */ +#define HAVE_STDLIB_H 1 + +/* Define to 1 if you have the header file. */ +#define HAVE_STRINGS_H 1 + +/* Define to 1 if you have the header file. */ +#define HAVE_STRING_H 1 + +/* Define to 1 if you have the `strlcpy' function. */ +/* #undef HAVE_STRLCPY */ + +/* Define to 1 if you have the `strsep' function. */ +/* #undef HAVE_STRSEP */ + +/* Define to 1 if you have the `strtok_r' function. */ +/* #undef HAVE_STRTOK_R */ + +/* Define to 1 if the system has the type `struct in6_addr'. */ +#define HAVE_STRUCT_IN6_ADDR 1 + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_DEVPOLL_H */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_EPOLL_H */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_EVENT_H */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_IOCTL_H */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_QUEUE_H */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_SELECT_H */ + +/* Define to 1 if you have the header file. */ +/* #undef HAVE_SYS_SOCKET_H */ + +/* Define to 1 if you have the header file. */ +/* #define HAVE_SYS_STAT_H 1 */ + +/* Define to 1 if you have the header file. */ +/* #define HAVE_SYS_TIME_H 1 */ + +/* Define to 1 if you have the header file. */ +/* #define HAVE_SYS_TYPES_H 1 */ + +/* Define if TAILQ_FOREACH is defined in */ +/* #undef HAVE_TAILQFOREACH */ + +/* Define if timeradd is defined in */ +/* #undef HAVE_TIMERADD */ + +/* Define if timerclear is defined in */ +/* #define HAVE_TIMERCLEAR 1 */ + +/* Define if timercmp is defined in */ +#define HAVE_TIMERCMP 1 + +/* Define if timerisset is defined in */ +#define HAVE_TIMERISSET 1 + +/* Define to 1 if you have the header file. */ +/* #define HAVE_UNISTD_H 1 */ + +/* Define to 1 if you have the `vasprintf' function. */ +/* #undef HAVE_VASPRINTF */ + +/* Define if kqueue works correctly with pipes */ +/* #undef HAVE_WORKING_KQUEUE */ + +/* Name of package */ +#ifndef PACKAGE +#define PACKAGE "libevent" +#endif + +/* Define to the address where bug reports for this package should be sent. */ +#define PACKAGE_BUGREPORT "" + +/* Define to the full name of this package. */ +#define PACKAGE_NAME "" + +/* Define to the full name and version of this package. */ +#define PACKAGE_STRING "" + +/* Define to the one symbol short name of this package. */ +#define PACKAGE_TARNAME "" + +/* Define to the version of this package. */ +#define PACKAGE_VERSION "" + +/* Define to 1 if you have the ANSI C header files. */ +#define STDC_HEADERS 1 + +/* Define to 1 if you can safely include both and . */ +#define TIME_WITH_SYS_TIME 1 + +/* Version number of package */ +#define VERSION "1.3.99-trunk" + +#ifndef __func__ +/* Define to appropriate substitue if compiler doesnt have __func__ */ +#if defined(_MSC_VER) && _MSC_VER < 1300 +#define __func__ "??" +#else +#define __func__ __FUNCTION__ +#endif +#endif + +/* Define to empty if `const' does not conform to ANSI C. */ +/* #undef 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 __cplusplus +#define inline __inline +#endif + +/* Define to `int' if does not define. */ +/* #undef pid_t */ + +/* Define to `unsigned' if does not define. */ +/* #undef size_t */ + +/* Define to unsigned int if you dont have it */ +#define socklen_t unsigned int + +/* Define to `unsigned short' if does not define. */ +#define uint16_t unsigned short + +/* Define to `unsigned int' if does not define. */ +#define uint32_t unsigned int + +/* Define to `unsigned long long' if does not define. */ +#define uint64_t __uint64_t + +/* Define to `unsigned char' if does not define. */ +#define uint8_t unsigned char === added file 'extra/libevent/WIN32-Code/misc.c' --- a/extra/libevent/WIN32-Code/misc.c 1970-01-01 00:00:00 +0000 +++ b/extra/libevent/WIN32-Code/misc.c 2008-12-04 09:21:32 +0000 @@ -0,0 +1,38 @@ +#include +#include +#include +#include +#include + +#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 === added file 'extra/libevent/WIN32-Code/misc.h' --- a/extra/libevent/WIN32-Code/misc.h 1970-01-01 00:00:00 +0000 +++ b/extra/libevent/WIN32-Code/misc.h 2008-12-04 09:21:32 +0000 @@ -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 === added file 'extra/libevent/WIN32-Code/tree.h' --- a/extra/libevent/WIN32-Code/tree.h 1970-01-01 00:00:00 +0000 +++ b/extra/libevent/WIN32-Code/tree.h 2008-12-04 09:21:32 +0000 @@ -0,0 +1,1354 @@ +/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ +/* + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _SYS_TREE_H_ +#define _SYS_TREE_H_ + +/* + * 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 + * 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_ */ === added file 'extra/libevent/WIN32-Code/win32.c' --- a/extra/libevent/WIN32-Code/win32.c 1970-01-01 00:00:00 +0000 +++ b/extra/libevent/WIN32-Code/win32.c 2008-12-04 09:21:32 +0000 @@ -0,0 +1,471 @@ +/* + * Copyright 2000-2002 Niels Provos + * Copyright 2003 Michael A. Davis + * 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#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; +}; + +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; + + evsignal_init(_base); + + 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) { + 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;ifd_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; + int i; + int fd_count; + + 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); + } + + for (i=0; ireadset_out->fd_count; ++i) { + struct event_entry *ent; + SOCKET 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); + } + for (i=0; iexset_out->fd_count; ++i) { + struct event_entry *ent; + SOCKET 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); + } + for (i=0; iwriteset_out->fd_count; ++i) { + struct event_entry *ent; + SOCKET 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); + } + +#if 0 + if (signal_recalc() == -1) + return (-1); +#endif + + 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 + === modified file 'extra/libevent/evutil.h' --- a/extra/libevent/evutil.h 2008-04-28 17:52:20 +0000 +++ b/extra/libevent/evutil.h 2008-12-04 09:21:32 +0000 @@ -55,8 +55,8 @@ extern "C" { #define ev_uint64_t uint64_t #define ev_int64_t int64_t #elif defined(WIN32) -#define ev_uint64_t __uint64_t -#define ev_int64_t __int64_t +#define ev_uint64_t unsigned __int64 +#define ev_int64_t __int64 #elif _EVENT_SIZEOF_LONG_LONG == 8 #define ev_uint64_t unsigned long long #define ev_int64_t long long === modified file 'include/config-win.h' --- a/include/config-win.h 2008-07-23 08:52:08 +0000 +++ b/include/config-win.h 2008-12-04 09:21:32 +0000 @@ -433,3 +433,7 @@ inline double ulonglong2double(ulonglong #define HAVE_CHARSET_utf8mb3 1 #define HAVE_UCA_COLLATIONS 1 #define HAVE_BOOL 1 +#ifndef EMBEDDED_LIBRARY +#define HAVE_LIBEVENT 1 +#define HAVE_POOL_OF_THREADS 1 +#endif === modified file 'sql/CMakeLists.txt' --- a/sql/CMakeLists.txt 2008-11-12 01:37:42 +0000 +++ b/sql/CMakeLists.txt 2008-12-04 09:21:32 +0000 @@ -20,6 +20,7 @@ INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR}/ ${CMAKE_SOURCE_DIR}/regex ${CMAKE_SOURCE_DIR}/zlib ${CMAKE_SOURCE_DIR}/sql/backup + ${CMAKE_SOURCE_DIR}/extra/libevent ) SET_SOURCE_FILES_PROPERTIES(${CMAKE_SOURCE_DIR}/sql/sql_yacc.h @@ -82,7 +83,7 @@ ADD_EXECUTABLE(mysqld TARGET_LINK_LIBRARIES(mysqld heap myisam myisammrg mysys yassl zlib dbug yassl - taocrypt strings vio regex) + taocrypt strings vio regex libevent) TARGET_LINK_LIBRARIES(mysqld backup) === modified file 'sql/mysqld.cc' --- a/sql/mysqld.cc 2008-11-15 17:02:01 +0000 +++ b/sql/mysqld.cc 2008-12-04 09:21:32 +0000 @@ -4381,6 +4381,13 @@ static void handle_connections_methods() sql_print_error("TCP/IP, --shared-memory, or --named-pipe should be configured on NT OS"); unireg_abort(1); // Will not return } + if((hPipe != INVALID_HANDLE_VALUE || opt_enable_shared_memory) && + global_system_variables.thread_handling== SCHEDULER_POOL_OF_THREADS) + { + sql_print_error("thread_handling=pool-of-threads cannot be used with "\ + "shared memory or named pipe protocols"); + unireg_abort(1); + } #endif pthread_mutex_lock(&LOCK_thread_count); === modified file 'sql/scheduler.cc' --- a/sql/scheduler.cc 2008-10-17 17:47:16 +0000 +++ b/sql/scheduler.cc 2008-12-04 09:21:32 +0000 @@ -105,8 +105,8 @@ static struct event thd_kill_event; static pthread_mutex_t LOCK_thd_add; /* protects thds_need_adding */ static LIST *thds_need_adding; /* list of thds to add to libevent queue */ -static int thd_add_pipe[2]; /* pipe to signal add a connection to libevent*/ -static int thd_kill_pipe[2]; /* pipe to signal kill a connection in libevent */ +static int thd_add_socketpair[2]; /* pipe to signal add a connection to libevent*/ +static int thd_kill_socketpair[2]; /* pipe to signal kill a connection in libevent */ /* LOCK_event_loop protects the non-thread safe libevent calls (event_add and @@ -132,16 +132,26 @@ void libevent_kill_thd_callback(int Fd, Returns TRUE if there is an error. */ -static bool init_pipe(int pipe_fds[]) +static bool init_socketpair(int sock_pair[]) { - int flags; - return pipe(pipe_fds) < 0 || - (flags= fcntl(pipe_fds[0], F_GETFL)) == -1 || - fcntl(pipe_fds[0], F_SETFL, flags | O_NONBLOCK) == -1 || - (flags= fcntl(pipe_fds[1], F_GETFL)) == -1 || - fcntl(pipe_fds[1], F_SETFL, flags | O_NONBLOCK) == -1; + sock_pair[0]= sock_pair[1]= -1; + if (evutil_socketpair( AF_UNIX, SOCK_STREAM,0, sock_pair) < 0) + return true; + if(evutil_make_socket_nonblocking(sock_pair[0]) == -1) + return true; + if(evutil_make_socket_nonblocking(sock_pair[1]) == -1) + return true; + return false; + } +static void close_socketpair(int sock_pair[]) +{ + if(sock_pair[0] != -1) + closesocket(sock_pair[0]); + if(sock_pair[1] != -1) + closesocket(sock_pair[1]); +} /* thd_scheduler keeps the link between THD and events. @@ -272,23 +282,22 @@ static bool libevent_init(void) pthread_mutex_init(&LOCK_event_loop, NULL); pthread_mutex_init(&LOCK_thd_add, NULL); - /* set up the pipe used to add new thds to the event pool */ - if (init_pipe(thd_add_pipe)) + /* set up sockets used to add new thds to the event pool */ + if (init_socketpair(thd_add_socketpair)) { - sql_print_error("init_pipe(thd_add_pipe) error in libevent_init\n"); + sql_print_error("init_socketpair(thd_add_socketpair) error in libevent_init\n"); DBUG_RETURN(1); } - /* set up the pipe used to kill thds in the event queue */ - if (init_pipe(thd_kill_pipe)) + /* set up sockets used to kill thds in the event queue */ + if (init_socketpair(thd_kill_socketpair)) { - sql_print_error("init_pipe(thd_kill_pipe) error in libevent_init\n"); - close(thd_add_pipe[0]); - close(thd_add_pipe[1]); + sql_print_error("init_socketpair(thd_kill_socketpair) error in libevent_init\n"); + close_socketpair(thd_add_socketpair); DBUG_RETURN(1); } - event_set(&thd_add_event, thd_add_pipe[0], EV_READ|EV_PERSIST, + event_set(&thd_add_event, thd_add_socketpair[0], EV_READ|EV_PERSIST, libevent_add_thd_callback, NULL); - event_set(&thd_kill_event, thd_kill_pipe[0], EV_READ|EV_PERSIST, + event_set(&thd_kill_event, thd_kill_socketpair[0], EV_READ|EV_PERSIST, libevent_kill_thd_callback, NULL); if (event_add(&thd_add_event, NULL) || event_add(&thd_kill_event, NULL)) @@ -358,7 +367,7 @@ void libevent_kill_thd_callback(int Fd, /* clear the pending events */ char c; - while (read(Fd, &c, sizeof(c)) == sizeof(c)) + while (recv(Fd, &c, sizeof(c),0) == sizeof(c)) {} LIST* list= thds_waiting_for_io; @@ -383,7 +392,7 @@ void libevent_kill_thd_callback(int Fd, /* This is used to add connections to the pool. This callback is invoked from - the libevent event_loop() call whenever the thd_add_pipe[1] pipe has a byte + the libevent event_loop() call whenever the thd_add_socketpair[1] has a byte written to it. NOTES @@ -396,7 +405,7 @@ void libevent_add_thd_callback(int Fd, s /* clear the pending events */ char c; - while (read(Fd, &c, sizeof(c)) == sizeof(c)) + while (recv(Fd, &c, sizeof(c),0) == sizeof(c)) {} pthread_mutex_lock(&LOCK_thd_add); @@ -487,7 +496,7 @@ static void libevent_post_kill_notificat later. */ char c= 0; - write(thd_kill_pipe[1], &c, sizeof(c)); + send(thd_kill_socketpair[1], &c, sizeof(c),0); } @@ -666,7 +675,7 @@ static bool libevent_needs_immediate_pro This call does not actually register the event with libevent. Instead, it places the THD onto a queue and signals libevent by writing - a byte into thd_add_pipe, which will cause our libevent_add_thd_callback to + a byte into thd_add_socketpair, which will cause our libevent_add_thd_callback to be invoked which will find the THD on the queue and add it to libevent. */ @@ -679,7 +688,7 @@ static void libevent_thd_add(THD* thd) /* queue for libevent */ thds_need_adding= list_add(thds_need_adding, &thd->scheduler.list); /* notify libevent */ - write(thd_add_pipe[1], &c, sizeof(c)); + send(thd_add_socketpair[1], &c, sizeof(c),0); pthread_mutex_unlock(&LOCK_thd_add); } @@ -701,18 +710,15 @@ static void libevent_end() { /* wake up the event loop */ char c= 0; - write(thd_add_pipe[1], &c, sizeof(c)); - + send(thd_add_socketpair[1], &c, sizeof(c),0); pthread_cond_wait(&COND_thread_count, &LOCK_thread_count); } (void) pthread_mutex_unlock(&LOCK_thread_count); event_del(&thd_add_event); - close(thd_add_pipe[0]); - close(thd_add_pipe[1]); + close_socketpair(thd_add_socketpair);; event_del(&thd_kill_event); - close(thd_kill_pipe[0]); - close(thd_kill_pipe[1]); + close_socketpair(thd_kill_socketpair); event_base_free(base); (void) pthread_mutex_destroy(&LOCK_event_loop);