#At file:///G:/bzr/mysql-6.0-bugteam/
2813 Vladislav Vaintroub 2008-12-17
merge fix for Bug#41218
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/buffer.c
extra/libevent/evbuffer.c
extra/libevent/evutil.c
extra/libevent/evutil.h
include/config-win.h
sql/CMakeLists.txt
sql/mysqld.cc
sql/scheduler.cc
=== modified file 'CMakeLists.txt'
--- a/CMakeLists.txt 2008-12-01 14:59:09 +0000
+++ b/CMakeLists.txt 2008-12-17 13:00:49 +0000
@@ -262,6 +262,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-17 13:00:49 +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 ${CMAKE_SOURCE_DIR}/extra/libevent/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-17 13:00:49 +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-17 13:00:49 +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 <dlfcn.h> 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 <fcntl.h> 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 <inttypes.h> 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 <memory.h> header file. */
+#define HAVE_MEMORY_H 1
+
+/* Define to 1 if you have the <netinet/in6.h> 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 <poll.h> 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 <port.h> 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 <fcntl.h> */
+/* #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 <signal.h> header file. */
+#define HAVE_SIGNAL_H 1
+
+/* Define to 1 if you have the <stdarg.h> header file. */
+#define HAVE_STDARG_H 1
+
+/* Define to 1 if you have the <stdint.h> header file. */
+/* #define HAVE_STDINT_H 1 */
+
+/* Define to 1 if you have the <stdlib.h> header file. */
+#define HAVE_STDLIB_H 1
+
+/* Define to 1 if you have the <strings.h> header file. */
+#define HAVE_STRINGS_H 1
+
+/* Define to 1 if you have the <string.h> 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 <sys/devpoll.h> header file. */
+/* #undef HAVE_SYS_DEVPOLL_H */
+
+/* Define to 1 if you have the <sys/epoll.h> header file. */
+/* #undef HAVE_SYS_EPOLL_H */
+
+/* Define to 1 if you have the <sys/event.h> header file. */
+/* #undef HAVE_SYS_EVENT_H */
+
+/* Define to 1 if you have the <sys/ioctl.h> header file. */
+/* #undef HAVE_SYS_IOCTL_H */
+
+/* Define to 1 if you have the <sys/queue.h> header file. */
+/* #undef HAVE_SYS_QUEUE_H */
+
+/* Define to 1 if you have the <sys/select.h> header file. */
+/* #undef HAVE_SYS_SELECT_H */
+
+/* Define to 1 if you have the <sys/socket.h> header file. */
+/* #undef HAVE_SYS_SOCKET_H */
+
+/* Define to 1 if you have the <sys/stat.h> header file. */
+/* #define HAVE_SYS_STAT_H 1 */
+
+/* Define to 1 if you have the <sys/time.h> header file. */
+/* #define HAVE_SYS_TIME_H 1 */
+
+/* Define to 1 if you have the <sys/types.h> header file. */
+/* #define HAVE_SYS_TYPES_H 1 */
+
+/* Define if TAILQ_FOREACH is defined in <sys/queue.h> */
+/* #undef HAVE_TAILQFOREACH */
+
+/* Define if timeradd is defined in <sys/time.h> */
+/* #undef HAVE_TIMERADD */
+
+/* Define if timerclear is defined in <sys/time.h> */
+/* #define HAVE_TIMERCLEAR 1 */
+
+/* Define if timercmp is defined in <sys/time.h> */
+#define HAVE_TIMERCMP 1
+
+/* Define if timerisset is defined in <sys/time.h> */
+#define HAVE_TIMERISSET 1
+
+/* Define to 1 if you have the <unistd.h> 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 <sys/time.h> and <time.h>. */
+#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 <sys/types.h> does not define. */
+/* #undef pid_t */
+
+/* Define to `unsigned' if <sys/types.h> 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 <sys/types.h> does not define. */
+#define uint16_t unsigned short
+
+/* Define to `unsigned int' if <sys/types.h> does not define. */
+#define uint32_t unsigned int
+
+/* Define to `unsigned long long' if <sys/types.h> does not define. */
+#define uint64_t __uint64_t
+
+/* Define to `unsigned char' if <sys/types.h> 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-17 13:00:49 +0000
@@ -0,0 +1,38 @@
+#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
=== 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-17 13:00:49 +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-17 13:00:49 +0000
@@ -0,0 +1,1354 @@
+/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
+/*
+ * Copyright 2002 Niels Provos <provos@stripped>
+ * 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@stripped>
+ * 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-17 13:00:49 +0000
@@ -0,0 +1,471 @@
+/*
+ * Copyright 2000-2002 Niels Provos <provos@stripped>
+ * Copyright 2003 Michael A. Davis <mike@stripped>
+ * 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;
+};
+
+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 = (int)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;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;
+ u_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; i<win32op->readset_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; i<win32op->exset_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; i<win32op->writeset_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/buffer.c'
--- a/extra/libevent/buffer.c 2008-04-28 17:52:20 +0000
+++ b/extra/libevent/buffer.c 2008-12-17 13:00:49 +0000
@@ -203,7 +203,7 @@ evbuffer_remove(struct evbuffer *buf, vo
memcpy(data, buf->buffer, nread);
evbuffer_drain(buf, nread);
- return (nread);
+ return (int)(nread);
}
/*
@@ -360,7 +360,7 @@ evbuffer_read(struct evbuffer *buf, int
#if defined(FIONREAD)
#ifdef WIN32
- long lng = n;
+ long lng = (long)n;
if (ioctlsocket(fd, FIONREAD, &lng) == -1 || (n=lng) == 0) {
#else
if (ioctl(fd, FIONREAD, &n) == -1 || n == 0) {
@@ -375,7 +375,7 @@ evbuffer_read(struct evbuffer *buf, int
* data we should read, we artifically limit it.
*/
if (n > buf->totallen << 2)
- n = buf->totallen << 2;
+ n = (int)(buf->totallen << 2);
if (n < EVBUFFER_MAX_READ)
n = EVBUFFER_MAX_READ;
}
@@ -417,7 +417,7 @@ evbuffer_write(struct evbuffer *buffer,
#ifndef WIN32
n = write(fd, buffer->buffer, buffer->off);
#else
- n = send(fd, buffer->buffer, buffer->off, 0);
+ n = send(fd, buffer->buffer, (int)buffer->off, 0);
#endif
if (n == -1)
return (-1);
=== modified file 'extra/libevent/evbuffer.c'
--- a/extra/libevent/evbuffer.c 2008-04-28 17:52:20 +0000
+++ b/extra/libevent/evbuffer.c 2008-12-17 13:00:49 +0000
@@ -109,7 +109,7 @@ bufferevent_readcb(int fd, short event,
* read more data than would make us reach the watermark.
*/
if (bufev->wm_read.high != 0)
- howmuch = bufev->wm_read.high;
+ howmuch = (int)bufev->wm_read.high;
res = evbuffer_read(bufev->input, fd, howmuch);
if (res == -1) {
=== modified file 'extra/libevent/evutil.c'
--- a/extra/libevent/evutil.c 2008-04-28 17:52:20 +0000
+++ b/extra/libevent/evutil.c 2008-12-17 13:00:49 +0000
@@ -88,7 +88,7 @@ evutil_socketpair(int family, int type,
return -1;
}
- listener = socket(AF_INET, type, 0);
+ listener = (int)socket(AF_INET, type, 0);
if (listener < 0)
return -1;
memset(&listen_addr, 0, sizeof(listen_addr));
@@ -101,7 +101,7 @@ evutil_socketpair(int family, int type,
if (listen(listener, 1) == -1)
goto tidy_up_and_fail;
- connector = socket(AF_INET, type, 0);
+ connector = (int)socket(AF_INET, type, 0);
if (connector < 0)
goto tidy_up_and_fail;
/* We want to find out the port number to connect to. */
@@ -115,7 +115,7 @@ evutil_socketpair(int family, int type,
goto tidy_up_and_fail;
size = sizeof(listen_addr);
- acceptor = accept(listener, (struct sockaddr *) &listen_addr, &size);
+ acceptor = (int)accept(listener, (struct sockaddr *) &listen_addr, &size);
if (acceptor < 0)
goto tidy_up_and_fail;
if (size != sizeof(listen_addr))
=== 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-17 13:00:49 +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-12-07 17:41:29 +0000
+++ b/include/config-win.h 2008-12-17 13:00:49 +0000
@@ -442,3 +442,7 @@ inline ulonglong double2ulonglong(double
#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-06 18:39:27 +0000
+++ b/sql/CMakeLists.txt 2008-12-17 13:00:49 +0000
@@ -26,6 +26,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
@@ -87,9 +88,10 @@ ADD_EXECUTABLE(mysqld
${PROJECT_SOURCE_DIR}/sql/lex_hash.h)
TARGET_LINK_LIBRARIES(mysqld
- heap myisam myisammrg mysys yassl zlib debug dbug yassl
+ heap myisam myisammrg mysys yassl zlib debug dbug yassl libevent
taocrypt strings vio regex ws2_32)
+
TARGET_LINK_LIBRARIES(mysqld backup)
SET_TARGET_PROPERTIES(mysqld PROPERTIES OUTPUT_NAME mysqld${MYSQLD_EXE_SUFFIX})
=== modified file 'sql/mysqld.cc'
--- a/sql/mysqld.cc 2008-12-08 15:32:57 +0000
+++ b/sql/mysqld.cc 2008-12-17 13:00:49 +0000
@@ -4377,6 +4377,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-17 13:00:49 +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_pair[2]; /* pipe to signal add a connection to libevent*/
+static int thd_kill_pair[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,21 @@ 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;
+ return (evutil_socketpair(AF_UNIX, SOCK_STREAM, 0, sock_pair) < 0 ||
+ evutil_make_socket_nonblocking(sock_pair[0]) == -1 ||
+ evutil_make_socket_nonblocking(sock_pair[1]) == -1);
}
+static void close_socketpair(int sock_pair[])
+{
+ if (sock_pair[0] != -1)
+ EVUTIL_CLOSESOCKET(sock_pair[0]);
+ if (sock_pair[1] != -1)
+ EVUTIL_CLOSESOCKET(sock_pair[1]);
+}
/*
thd_scheduler keeps the link between THD and events.
@@ -175,7 +180,7 @@ bool thd_scheduler::init(THD *parent_thd
return TRUE;
}
- event_set(io_event, parent_thd->net.vio->sd, EV_READ,
+ event_set(io_event, (int)parent_thd->net.vio->sd, EV_READ,
libevent_io_callback, (void*)parent_thd);
list.data= parent_thd;
@@ -272,23 +277,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_pair))
{
- sql_print_error("init_pipe(thd_add_pipe) error in libevent_init\n");
+ sql_print_error("init_socketpair(thd_add_spair) 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_pair))
{
- 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_pair) error in libevent_init\n");
+ close_socketpair(thd_add_pair);
DBUG_RETURN(1);
}
- event_set(&thd_add_event, thd_add_pipe[0], EV_READ|EV_PERSIST,
+ event_set(&thd_add_event, thd_add_pair[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_pair[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 +362,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 +387,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_pair[1] has a byte
written to it.
NOTES
@@ -396,7 +400,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 +491,7 @@ static void libevent_post_kill_notificat
later.
*/
char c= 0;
- write(thd_kill_pipe[1], &c, sizeof(c));
+ send(thd_kill_pair[1], &c, sizeof(c), 0);
}
@@ -666,7 +670,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_pair, 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 +683,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_pair[1], &c, sizeof(c), 0);
pthread_mutex_unlock(&LOCK_thd_add);
}
@@ -701,18 +705,15 @@ static void libevent_end()
{
/* wake up the event loop */
char c= 0;
- write(thd_add_pipe[1], &c, sizeof(c));
-
+ send(thd_add_pair[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_pair);
event_del(&thd_kill_event);
- close(thd_kill_pipe[0]);
- close(thd_kill_pipe[1]);
+ close_socketpair(thd_kill_pair);
event_base_free(base);
(void) pthread_mutex_destroy(&LOCK_event_loop);
| Thread |
|---|
| • bzr commit into mysql-6.0-bugteam branch (vvaintroub:2813) Bug#41218 | Vladislav Vaintroub | 17 Dec |
