List:Commits« Previous MessageNext Message »
From:Vladislav Vaintroub Date:December 17 2008 1:01pm
Subject:bzr commit into mysql-6.0-bugteam branch (vvaintroub:2813) Bug#41218
View as plain text  
#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#41218Vladislav Vaintroub17 Dec