move to storage/innobase

11 files changed, 3976 insertions, 0 deletions

diff --git a/storage/innobase/ut/ut0bh.cc b/storage/innobase/ut/ut0bh.cc
new file mode 100644
index 00000000000..1a3038a0d71
--- /dev/null
+++ b/storage/innobase/ut/ut0bh.cc
@@ -0,0 +1,159 @@
+/***************************************************************************//**
+
+Copyright (c) 2010, 2011, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/******************************************************************//**
+@file ut/ut0bh.cc
+Binary min-heap implementation.
+
+Created 2010-05-28 by Sunny Bains
+*******************************************************/
+
+#include "ut0bh.h"
+#include "ut0mem.h"
+
+#ifdef UNIV_NONINL
+#include "ut0bh.ic"
+#endif
+
+#include <string.h>
+
+/**********************************************************************//**
+Create a binary heap.
+@return a new binary heap */
+UNIV_INTERN
+ib_bh_t*
+ib_bh_create(
+/*=========*/
+	ib_bh_cmp_t	compare,		/*!< in: comparator */
+	ulint		sizeof_elem,		/*!< in: size of one element */
+	ulint		max_elems)		/*!< in: max elements allowed */
+{
+	ulint		sz;
+	ib_bh_t*	ib_bh;
+
+	sz = sizeof(*ib_bh) + (sizeof_elem * max_elems);
+
+	ib_bh = (ib_bh_t*) ut_malloc(sz);
+	memset(ib_bh, 0x0, sz);
+
+	ib_bh->compare = compare;
+	ib_bh->max_elems = max_elems;
+	ib_bh->sizeof_elem = sizeof_elem;
+
+	return(ib_bh);
+}
+
+/**********************************************************************//**
+Free a binary heap.
+@return a new binary heap */
+UNIV_INTERN
+void
+ib_bh_free(
+/*=======*/
+	ib_bh_t*	ib_bh)			/*!< in/own: instance */
+{
+	ut_free(ib_bh);
+}
+
+/**********************************************************************//**
+Add an element to the binary heap. Note: The element is copied.
+@return pointer to added element or NULL if full. */
+UNIV_INTERN
+void*
+ib_bh_push(
+/*=======*/
+	ib_bh_t*	ib_bh,			/*!< in/out: instance */
+	const void*	elem)			/*!< in: element to add */
+{
+	void*		ptr;
+
+	if (ib_bh_is_full(ib_bh)) {
+		return(NULL);
+	} else if (ib_bh_is_empty(ib_bh)) {
+		++ib_bh->n_elems;
+		return(ib_bh_set(ib_bh, 0, elem));
+	} else {
+		ulint	i;
+
+		i = ib_bh->n_elems;
+
+		++ib_bh->n_elems;
+
+		for (ptr = ib_bh_get(ib_bh, i >> 1);
+		     i > 0 && ib_bh->compare(ptr, elem) > 0;
+		     i >>= 1, ptr = ib_bh_get(ib_bh, i >> 1)) {
+
+			ib_bh_set(ib_bh, i, ptr);
+		}
+
+		ptr = ib_bh_set(ib_bh, i, elem);
+	}
+
+	return(ptr);
+}
+
+/**********************************************************************//**
+Remove the first element from the binary heap. */
+UNIV_INTERN
+void
+ib_bh_pop(
+/*======*/
+	ib_bh_t*	ib_bh)			/*!< in/out: instance */
+{
+	byte*		ptr;
+	byte*		last;
+	ulint		parent = 0;
+
+	if (ib_bh_is_empty(ib_bh)) {
+		return;
+	} else if (ib_bh_size(ib_bh) == 1) {
+		--ib_bh->n_elems;
+		return;
+	}
+
+	last = (byte*) ib_bh_last(ib_bh);
+
+	/* Start from the child node */
+	ptr = (byte*) ib_bh_get(ib_bh, 1);
+
+	while (ptr < last) {
+		/* If the "right" child node is < "left" child node */
+		if (ib_bh->compare(ptr + ib_bh->sizeof_elem, ptr) < 0) {
+			ptr += ib_bh->sizeof_elem;
+		}
+
+		if (ib_bh->compare(last, ptr) <= 0) {
+			break;
+		}
+
+		ib_bh_set(ib_bh, parent, ptr);
+
+		parent = (ptr - (byte*) ib_bh_first(ib_bh))
+		       / ib_bh->sizeof_elem;
+
+		if ((parent << 1) >= ib_bh_size(ib_bh)) {
+			break;
+		}
+
+		ptr = (byte*) ib_bh_get(ib_bh, parent << 1);
+	}
+
+	--ib_bh->n_elems;
+
+	ib_bh_set(ib_bh, parent, last);
+}
diff --git a/storage/innobase/ut/ut0byte.cc b/storage/innobase/ut/ut0byte.cc
new file mode 100644
index 00000000000..bc592edc6bf
--- /dev/null
+++ b/storage/innobase/ut/ut0byte.cc
@@ -0,0 +1,30 @@
+/*****************************************************************************
+
+Copyright (c) 1994, 2009, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/***************************************************************//**
+@file ut/ut0byte.cc
+Byte utilities
+
+Created 5/11/1994 Heikki Tuuri
+********************************************************************/
+
+#include "ut0byte.h"
+
+#ifdef UNIV_NONINL
+#include "ut0byte.ic"
+#endif
diff --git a/storage/innobase/ut/ut0crc32.cc b/storage/innobase/ut/ut0crc32.cc
new file mode 100644
index 00000000000..1caf27ebae3
--- /dev/null
+++ b/storage/innobase/ut/ut0crc32.cc
@@ -0,0 +1,318 @@
+/*****************************************************************************
+
+Copyright (C) 2009, 2010 Facebook, Inc. All Rights Reserved.
+Copyright (c) 2011, 2011, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/***************************************************************//**
+@file ut/ut0crc32.cc
+CRC32 implementation from Facebook, based on the zlib implementation.
+
+Created Aug 8, 2011, Vasil Dimov, based on mysys/my_crc32.c and
+mysys/my_perf.c, contributed by Facebook under the following license.
+********************************************************************/
+
+/* Copyright (C) 2009-2010 Facebook, Inc.  All Rights Reserved.
+
+   Dual licensed under BSD license and GPLv2.
+
+   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 FACEBOOK, INC. ``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 FACEBOOK, INC. 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.
+
+   This program is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by the Free
+   Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful, but WITHOUT
+   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+   more details.
+
+   You should have received a copy of the GNU General Public License along with
+   this program; if not, write to the Free Software Foundation, Inc.,
+   51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
+
+/* The below CRC32 implementation is based on the implementation included with
+ * zlib with modifications to process 8 bytes at a time and using SSE 4.2
+ * extentions when available.  The polynomial constant has been changed to
+ * match the one used by SSE 4.2 and does not return the same value as the
+ * version used by zlib.  This implementation only supports 64-bit
+ * little-endian processors.  The original zlib copyright notice follows. */
+
+/* crc32.c -- compute the CRC-32 of a buf stream
+ * Copyright (C) 1995-2005 Mark Adler
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ *
+ * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
+ * CRC methods: exclusive-oring 32 bits of buf at a time, and pre-computing
+ * tables for updating the shift register in one step with three exclusive-ors
+ * instead of four steps with four exclusive-ors.  This results in about a
+ * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
+ */
+
+#include "univ.i"
+#include "ut0crc32.h"
+
+#include <string.h>
+
+ib_ut_crc32_t	ut_crc32;
+
+/* Precalculated table used to generate the CRC32 if the CPU does not
+have support for it */
+static ib_uint32_t	ut_crc32_slice8_table[8][256];
+static ibool		ut_crc32_slice8_table_initialized = FALSE;
+
+/* Flag that tells whether the CPU supports CRC32 or not */
+UNIV_INTERN bool	ut_crc32_sse2_enabled = false;
+
+/********************************************************************//**
+Initializes the table that is used to generate the CRC32 if the CPU does
+not have support for it. */
+static
+void
+ut_crc32_slice8_table_init()
+/*========================*/
+{
+	/* bit-reversed poly 0x1EDC6F41 (from SSE42 crc32 instruction) */
+	static const ib_uint32_t	poly = 0x82f63b78;
+	ib_uint32_t			n;
+	ib_uint32_t			k;
+	ib_uint32_t			c;
+
+	for (n = 0; n < 256; n++) {
+		c = n;
+		for (k = 0; k < 8; k++) {
+			c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
+		}
+		ut_crc32_slice8_table[0][n] = c;
+	}
+
+	for (n = 0; n < 256; n++) {
+		c = ut_crc32_slice8_table[0][n];
+		for (k = 1; k < 8; k++) {
+			c = ut_crc32_slice8_table[0][c & 0xFF] ^ (c >> 8);
+			ut_crc32_slice8_table[k][n] = c;
+		}
+	}
+
+	ut_crc32_slice8_table_initialized = TRUE;
+}
+
+#if defined(__GNUC__) && defined(__x86_64__)
+/********************************************************************//**
+Fetches CPU info */
+static
+void
+ut_cpuid(
+/*=====*/
+	ib_uint32_t	vend[3],	/*!< out: CPU vendor */
+	ib_uint32_t*	model,		/*!< out: CPU model */
+	ib_uint32_t*	family,		/*!< out: CPU family */
+	ib_uint32_t*	stepping,	/*!< out: CPU stepping */
+	ib_uint32_t*	features_ecx,	/*!< out: CPU features ecx */
+	ib_uint32_t*	features_edx)	/*!< out: CPU features edx */
+{
+	ib_uint32_t	sig;
+	asm("cpuid" : "=b" (vend[0]), "=c" (vend[2]), "=d" (vend[1]) : "a" (0));
+	asm("cpuid" : "=a" (sig), "=c" (*features_ecx), "=d" (*features_edx)
+	    : "a" (1)
+	    : "ebx");
+
+	*model = ((sig >> 4) & 0xF);
+	*family = ((sig >> 8) & 0xF);
+	*stepping = (sig & 0xF);
+
+	if (memcmp(vend, "GenuineIntel", 12) == 0
+	    || (memcmp(vend, "AuthenticAMD", 12) == 0 && *family == 0xF)) {
+
+		*model += (((sig >> 16) & 0xF) << 4);
+		*family += ((sig >> 20) & 0xFF);
+	}
+}
+
+/* opcodes taken from objdump of "crc32b (%%rdx), %%rcx"
+for RHEL4 support (GCC 3 doesn't support this instruction) */
+#define ut_crc32_sse42_byte \
+	asm(".byte 0xf2, 0x48, 0x0f, 0x38, 0xf0, 0x0a" \
+	    : "=c"(crc) : "c"(crc), "d"(buf)); \
+	len--, buf++
+
+/* opcodes taken from objdump of "crc32q (%%rdx), %%rcx"
+for RHEL4 support (GCC 3 doesn't support this instruction) */
+#define ut_crc32_sse42_quadword \
+	asm(".byte 0xf2, 0x48, 0x0f, 0x38, 0xf1, 0x0a" \
+	    : "=c"(crc) : "c"(crc), "d"(buf)); \
+	len -= 8, buf += 8
+#endif /* defined(__GNUC__) && defined(__x86_64__) */
+
+/********************************************************************//**
+Calculates CRC32 using CPU instructions.
+@return CRC-32C (polynomial 0x11EDC6F41) */
+UNIV_INLINE
+ib_uint32_t
+ut_crc32_sse42(
+/*===========*/
+	const byte*	buf,	/*!< in: data over which to calculate CRC32 */
+	ulint		len)	/*!< in: data length */
+{
+#if defined(__GNUC__) && defined(__x86_64__)
+	ib_uint64_t	crc = (ib_uint32_t) (-1);
+
+	ut_a(ut_crc32_sse2_enabled);
+
+	while (len && ((ulint) buf & 7)) {
+		ut_crc32_sse42_byte;
+	}
+
+	while (len >= 32) {
+		ut_crc32_sse42_quadword;
+		ut_crc32_sse42_quadword;
+		ut_crc32_sse42_quadword;
+		ut_crc32_sse42_quadword;
+	}
+
+	while (len >= 8) {
+		ut_crc32_sse42_quadword;
+	}
+
+	while (len) {
+		ut_crc32_sse42_byte;
+	}
+
+	return((ib_uint32_t) ((~crc) & 0xFFFFFFFF));
+#else
+	ut_error;
+	/* silence compiler warning about unused parameters */
+	return((ib_uint32_t) buf[len]);
+#endif /* defined(__GNUC__) && defined(__x86_64__) */
+}
+
+#define ut_crc32_slice8_byte \
+	crc = (crc >> 8) ^ ut_crc32_slice8_table[0][(crc ^ *buf++) & 0xFF]; \
+	len--
+
+#define ut_crc32_slice8_quadword \
+	crc ^= *(ib_uint64_t*) buf; \
+	crc = ut_crc32_slice8_table[7][(crc      ) & 0xFF] ^ \
+	      ut_crc32_slice8_table[6][(crc >>  8) & 0xFF] ^ \
+	      ut_crc32_slice8_table[5][(crc >> 16) & 0xFF] ^ \
+	      ut_crc32_slice8_table[4][(crc >> 24) & 0xFF] ^ \
+	      ut_crc32_slice8_table[3][(crc >> 32) & 0xFF] ^ \
+	      ut_crc32_slice8_table[2][(crc >> 40) & 0xFF] ^ \
+	      ut_crc32_slice8_table[1][(crc >> 48) & 0xFF] ^ \
+	      ut_crc32_slice8_table[0][(crc >> 56)]; \
+	len -= 8, buf += 8
+
+/********************************************************************//**
+Calculates CRC32 manually.
+@return CRC-32C (polynomial 0x11EDC6F41) */
+UNIV_INLINE
+ib_uint32_t
+ut_crc32_slice8(
+/*============*/
+	const byte*	buf,	/*!< in: data over which to calculate CRC32 */
+	ulint		len)	/*!< in: data length */
+{
+	ib_uint64_t	crc = (ib_uint32_t) (-1);
+
+	ut_a(ut_crc32_slice8_table_initialized);
+
+	while (len && ((ulint) buf & 7)) {
+		ut_crc32_slice8_byte;
+	}
+
+	while (len >= 32) {
+		ut_crc32_slice8_quadword;
+		ut_crc32_slice8_quadword;
+		ut_crc32_slice8_quadword;
+		ut_crc32_slice8_quadword;
+	}
+
+	while (len >= 8) {
+		ut_crc32_slice8_quadword;
+	}
+
+	while (len) {
+		ut_crc32_slice8_byte;
+	}
+
+	return((ib_uint32_t) ((~crc) & 0xFFFFFFFF));
+}
+
+/********************************************************************//**
+Initializes the data structures used by ut_crc32(). Does not do any
+allocations, would not hurt if called twice, but would be pointless. */
+UNIV_INTERN
+void
+ut_crc32_init()
+/*===========*/
+{
+#if defined(__GNUC__) && defined(__x86_64__)
+	ib_uint32_t	vend[3];
+	ib_uint32_t	model;
+	ib_uint32_t	family;
+	ib_uint32_t	stepping;
+	ib_uint32_t	features_ecx;
+	ib_uint32_t	features_edx;
+
+	ut_cpuid(vend, &model, &family, &stepping,
+		 &features_ecx, &features_edx);
+
+	/* Valgrind does not understand the CRC32 instructions:
+
+	vex amd64->IR: unhandled instruction bytes: 0xF2 0x48 0xF 0x38 0xF0 0xA
+	valgrind: Unrecognised instruction at address 0xad3db5.
+	Your program just tried to execute an instruction that Valgrind
+	did not recognise.  There are two possible reasons for this.
+	1. Your program has a bug and erroneously jumped to a non-code
+	   location.  If you are running Memcheck and you just saw a
+	   warning about a bad jump, it's probably your program's fault.
+	2. The instruction is legitimate but Valgrind doesn't handle it,
+	   i.e. it's Valgrind's fault.  If you think this is the case or
+	   you are not sure, please let us know and we'll try to fix it.
+	Either way, Valgrind will now raise a SIGILL signal which will
+	probably kill your program.
+
+	*/
+#ifndef UNIV_DEBUG_VALGRIND
+	ut_crc32_sse2_enabled = (features_ecx >> 20) & 1;
+#endif /* UNIV_DEBUG_VALGRIND */
+
+#endif /* defined(__GNUC__) && defined(__x86_64__) */
+
+	if (ut_crc32_sse2_enabled) {
+		ut_crc32 = ut_crc32_sse42;
+	} else {
+		ut_crc32_slice8_table_init();
+		ut_crc32 = ut_crc32_slice8;
+	}
+}
diff --git a/storage/innobase/ut/ut0dbg.cc b/storage/innobase/ut/ut0dbg.cc
new file mode 100644
index 00000000000..a1cad144da4
--- /dev/null
+++ b/storage/innobase/ut/ut0dbg.cc
@@ -0,0 +1,139 @@
+/*****************************************************************************
+
+Copyright (c) 1994, 2009, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/*****************************************************************//**
+@file ut/ut0dbg.cc
+Debug utilities for Innobase.
+
+Created 1/30/1994 Heikki Tuuri
+**********************************************************************/
+
+#include "univ.i"
+#include "ut0dbg.h"
+#ifndef UNIV_HOTBACKUP
+# include "ha_prototypes.h"
+#endif /* !UNIV_HOTBACKUP */
+
+#if defined(__GNUC__) && (__GNUC__ > 2)
+#else
+/** This is used to eliminate compiler warnings */
+UNIV_INTERN ulint	ut_dbg_zero	= 0;
+#endif
+
+/*************************************************************//**
+Report a failed assertion. */
+UNIV_INTERN
+void
+ut_dbg_assertion_failed(
+/*====================*/
+	const char* expr,	/*!< in: the failed assertion (optional) */
+	const char* file,	/*!< in: source file containing the assertion */
+	ulint line)		/*!< in: line number of the assertion */
+{
+	ut_print_timestamp(stderr);
+#ifdef UNIV_HOTBACKUP
+	fprintf(stderr, "  InnoDB: Assertion failure in file %s line %lu\n",
+		file, line);
+#else /* UNIV_HOTBACKUP */
+	fprintf(stderr,
+		"  InnoDB: Assertion failure in thread %lu"
+		" in file %s line %lu\n",
+		os_thread_pf(os_thread_get_curr_id()),
+		innobase_basename(file), line);
+#endif /* UNIV_HOTBACKUP */
+	if (expr) {
+		fprintf(stderr,
+			"InnoDB: Failing assertion: %s\n", expr);
+	}
+
+	fputs("InnoDB: We intentionally generate a memory trap.\n"
+	      "InnoDB: Submit a detailed bug report"
+	      " to http://bugs.mysql.com.\n"
+	      "InnoDB: If you get repeated assertion failures"
+	      " or crashes, even\n"
+	      "InnoDB: immediately after the mysqld startup, there may be\n"
+	      "InnoDB: corruption in the InnoDB tablespace. Please refer to\n"
+	      "InnoDB: " REFMAN "forcing-innodb-recovery.html\n"
+	      "InnoDB: about forcing recovery.\n", stderr);
+}
+
+#ifdef UNIV_COMPILE_TEST_FUNCS
+
+#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/resource.h>
+
+#include <unistd.h>
+
+#ifndef timersub
+#define timersub(a, b, r)						\
+	do {								\
+		(r)->tv_sec = (a)->tv_sec - (b)->tv_sec;		\
+		(r)->tv_usec = (a)->tv_usec - (b)->tv_usec;		\
+		if ((r)->tv_usec < 0) {					\
+			(r)->tv_sec--;					\
+			(r)->tv_usec += 1000000;			\
+		}							\
+	} while (0)
+#endif /* timersub */
+
+/*******************************************************************//**
+Resets a speedo (records the current time in it). */
+UNIV_INTERN
+void
+speedo_reset(
+/*=========*/
+	speedo_t*	speedo)	/*!< out: speedo */
+{
+	gettimeofday(&speedo->tv, NULL);
+
+	getrusage(RUSAGE_SELF, &speedo->ru);
+}
+
+/*******************************************************************//**
+Shows the time elapsed and usage statistics since the last reset of a
+speedo. */
+UNIV_INTERN
+void
+speedo_show(
+/*========*/
+	const speedo_t*	speedo)	/*!< in: speedo */
+{
+	struct rusage	ru_now;
+	struct timeval	tv_now;
+	struct timeval	tv_diff;
+
+	getrusage(RUSAGE_SELF, &ru_now);
+
+	gettimeofday(&tv_now, NULL);
+
+#define PRINT_TIMEVAL(prefix, tvp)		\
+	fprintf(stderr, "%s% 5ld.%06ld sec\n",	\
+		prefix, (tvp)->tv_sec, (tvp)->tv_usec)
+
+	timersub(&tv_now, &speedo->tv, &tv_diff);
+	PRINT_TIMEVAL("real", &tv_diff);
+
+	timersub(&ru_now.ru_utime, &speedo->ru.ru_utime, &tv_diff);
+	PRINT_TIMEVAL("user", &tv_diff);
+
+	timersub(&ru_now.ru_stime, &speedo->ru.ru_stime, &tv_diff);
+	PRINT_TIMEVAL("sys ", &tv_diff);
+}
+
+#endif /* UNIV_COMPILE_TEST_FUNCS */
diff --git a/storage/innobase/ut/ut0list.cc b/storage/innobase/ut/ut0list.cc
new file mode 100644
index 00000000000..f906061d185
--- /dev/null
+++ b/storage/innobase/ut/ut0list.cc
@@ -0,0 +1,203 @@
+/*****************************************************************************
+
+Copyright (c) 2006, 2011, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/*******************************************************************//**
+@file ut/ut0list.cc
+A double-linked list
+
+Created 4/26/2006 Osku Salerma
+************************************************************************/
+
+#include "ut0list.h"
+#ifdef UNIV_NONINL
+#include "ut0list.ic"
+#endif
+
+/****************************************************************//**
+Create a new list.
+@return	list */
+UNIV_INTERN
+ib_list_t*
+ib_list_create(void)
+/*=================*/
+{
+	ib_list_t*	list;
+
+	list = static_cast<ib_list_t*>(mem_alloc(sizeof(*list)));
+
+	list->first = NULL;
+	list->last = NULL;
+	list->is_heap_list = FALSE;
+
+	return(list);
+}
+
+/****************************************************************//**
+Create a new list using the given heap. ib_list_free MUST NOT BE CALLED for
+lists created with this function.
+@return	list */
+UNIV_INTERN
+ib_list_t*
+ib_list_create_heap(
+/*================*/
+	mem_heap_t*	heap)	/*!< in: memory heap to use */
+{
+	ib_list_t*	list;
+
+	list = static_cast<ib_list_t*>(mem_heap_alloc(heap, sizeof(*list)));
+
+	list->first = NULL;
+	list->last = NULL;
+	list->is_heap_list = TRUE;
+
+	return(list);
+}
+
+/****************************************************************//**
+Free a list. */
+UNIV_INTERN
+void
+ib_list_free(
+/*=========*/
+	ib_list_t*	list)	/*!< in: list */
+{
+	ut_a(!list->is_heap_list);
+
+	/* We don't check that the list is empty because it's entirely valid
+	to e.g. have all the nodes allocated from a single heap that is then
+	freed after the list itself is freed. */
+
+	mem_free(list);
+}
+
+/****************************************************************//**
+Add the data to the start of the list.
+@return	new list node */
+UNIV_INTERN
+ib_list_node_t*
+ib_list_add_first(
+/*==============*/
+	ib_list_t*	list,	/*!< in: list */
+	void*		data,	/*!< in: data */
+	mem_heap_t*	heap)	/*!< in: memory heap to use */
+{
+	return(ib_list_add_after(list, ib_list_get_first(list), data, heap));
+}
+
+/****************************************************************//**
+Add the data to the end of the list.
+@return	new list node */
+UNIV_INTERN
+ib_list_node_t*
+ib_list_add_last(
+/*=============*/
+	ib_list_t*	list,	/*!< in: list */
+	void*		data,	/*!< in: data */
+	mem_heap_t*	heap)	/*!< in: memory heap to use */
+{
+	return(ib_list_add_after(list, ib_list_get_last(list), data, heap));
+}
+
+/****************************************************************//**
+Add the data after the indicated node.
+@return	new list node */
+UNIV_INTERN
+ib_list_node_t*
+ib_list_add_after(
+/*==============*/
+	ib_list_t*	list,		/*!< in: list */
+	ib_list_node_t*	prev_node,	/*!< in: node preceding new node (can
+					be NULL) */
+	void*		data,		/*!< in: data */
+	mem_heap_t*	heap)		/*!< in: memory heap to use */
+{
+	ib_list_node_t*	node;
+
+	node = static_cast<ib_list_node_t*>(
+		mem_heap_alloc(heap, sizeof(*node)));
+
+	node->data = data;
+
+	if (!list->first) {
+		/* Empty list. */
+
+		ut_a(!prev_node);
+
+		node->prev = NULL;
+		node->next = NULL;
+
+		list->first = node;
+		list->last = node;
+	} else if (!prev_node) {
+		/* Start of list. */
+
+		node->prev = NULL;
+		node->next = list->first;
+
+		list->first->prev = node;
+
+		list->first = node;
+	} else {
+		/* Middle or end of list. */
+
+		node->prev = prev_node;
+		node->next = prev_node->next;
+
+		prev_node->next = node;
+
+		if (node->next) {
+			node->next->prev = node;
+		} else {
+			list->last = node;
+		}
+	}
+
+	return(node);
+}
+
+/****************************************************************//**
+Remove the node from the list. */
+UNIV_INTERN
+void
+ib_list_remove(
+/*===========*/
+	ib_list_t*	list,	/*!< in: list */
+	ib_list_node_t*	node)	/*!< in: node to remove */
+{
+	if (node->prev) {
+		node->prev->next = node->next;
+	} else {
+		/* First item in list. */
+
+		ut_ad(list->first == node);
+
+		list->first = node->next;
+	}
+
+	if (node->next) {
+		node->next->prev = node->prev;
+	} else {
+		/* Last item in list. */
+
+		ut_ad(list->last == node);
+
+		list->last = node->prev;
+	}
+
+	node->prev = node->next = NULL;
+}
diff --git a/storage/innobase/ut/ut0mem.cc b/storage/innobase/ut/ut0mem.cc
new file mode 100644
index 00000000000..2bb5d9ce332
--- /dev/null
+++ b/storage/innobase/ut/ut0mem.cc
@@ -0,0 +1,609 @@
+/*****************************************************************************
+
+Copyright (c) 1994, 2011, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/********************************************************************//**
+@file ut/ut0mem.cc
+Memory primitives
+
+Created 5/11/1994 Heikki Tuuri
+*************************************************************************/
+
+#include "ut0mem.h"
+
+#ifdef UNIV_NONINL
+#include "ut0mem.ic"
+#endif
+
+#ifndef UNIV_HOTBACKUP
+# include "os0thread.h"
+# include "srv0srv.h"
+
+#include <stdlib.h>
+
+/** The total amount of memory currently allocated from the operating
+system with os_mem_alloc_large() or malloc().  Does not count malloc()
+if srv_use_sys_malloc is set.  Protected by ut_list_mutex. */
+UNIV_INTERN ulint		ut_total_allocated_memory	= 0;
+
+/** Mutex protecting ut_total_allocated_memory and ut_mem_block_list */
+UNIV_INTERN os_fast_mutex_t	ut_list_mutex;
+
+#ifdef UNIV_PFS_MUTEX
+/* Key to register server_mutex with performance schema */
+UNIV_INTERN mysql_pfs_key_t	ut_list_mutex_key;
+#endif
+
+/** Dynamically allocated memory block */
+struct ut_mem_block_t{
+	UT_LIST_NODE_T(ut_mem_block_t) mem_block_list;
+			/*!< mem block list node */
+	ulint	size;	/*!< size of allocated memory */
+	ulint	magic_n;/*!< magic number (UT_MEM_MAGIC_N) */
+};
+
+/** The value of ut_mem_block_t::magic_n.  Used in detecting
+memory corruption. */
+#define UT_MEM_MAGIC_N	1601650166
+
+/** List of all memory blocks allocated from the operating system
+with malloc.  Protected by ut_list_mutex. */
+static UT_LIST_BASE_NODE_T(ut_mem_block_t)   ut_mem_block_list;
+
+/** Flag: has ut_mem_block_list been initialized? */
+static ibool  ut_mem_block_list_inited = FALSE;
+
+/** A dummy pointer for generating a null pointer exception in
+ut_malloc_low() */
+static ulint*	ut_mem_null_ptr	= NULL;
+
+/**********************************************************************//**
+Initializes the mem block list at database startup. */
+UNIV_INTERN
+void
+ut_mem_init(void)
+/*=============*/
+{
+	ut_a(!ut_mem_block_list_inited);
+	os_fast_mutex_init(ut_list_mutex_key, &ut_list_mutex);
+	UT_LIST_INIT(ut_mem_block_list);
+	ut_mem_block_list_inited = TRUE;
+}
+#endif /* !UNIV_HOTBACKUP */
+
+/**********************************************************************//**
+Allocates memory.
+@return	own: allocated memory */
+UNIV_INTERN
+void*
+ut_malloc_low(
+/*==========*/
+	ulint	n,		/*!< in: number of bytes to allocate */
+	ibool	assert_on_error)/*!< in: if TRUE, we crash mysqld if the
+				memory cannot be allocated */
+{
+#ifndef UNIV_HOTBACKUP
+	ulint	retry_count;
+	void*	ret;
+
+	if (UNIV_LIKELY(srv_use_sys_malloc)) {
+		ret = malloc(n);
+		ut_a(ret || !assert_on_error);
+
+		return(ret);
+	}
+
+	ut_ad((sizeof(ut_mem_block_t) % 8) == 0); /* check alignment ok */
+	ut_a(ut_mem_block_list_inited);
+
+	retry_count = 0;
+retry:
+	os_fast_mutex_lock(&ut_list_mutex);
+
+	ret = malloc(n + sizeof(ut_mem_block_t));
+
+	if (ret == NULL && retry_count < 60) {
+		if (retry_count == 0) {
+			ut_print_timestamp(stderr);
+
+			fprintf(stderr,
+				"  InnoDB: Error: cannot allocate"
+				" %lu bytes of\n"
+				"InnoDB: memory with malloc!"
+				" Total allocated memory\n"
+				"InnoDB: by InnoDB %lu bytes."
+				" Operating system errno: %lu\n"
+				"InnoDB: Check if you should"
+				" increase the swap file or\n"
+				"InnoDB: ulimits of your operating system.\n"
+				"InnoDB: On FreeBSD check you"
+				" have compiled the OS with\n"
+				"InnoDB: a big enough maximum process size.\n"
+				"InnoDB: Note that in most 32-bit"
+				" computers the process\n"
+				"InnoDB: memory space is limited"
+				" to 2 GB or 4 GB.\n"
+				"InnoDB: We keep retrying"
+				" the allocation for 60 seconds...\n",
+				(ulong) n, (ulong) ut_total_allocated_memory,
+#ifdef __WIN__
+				(ulong) GetLastError()
+#else
+				(ulong) errno
+#endif
+				);
+		}
+
+		os_fast_mutex_unlock(&ut_list_mutex);
+
+		/* Sleep for a second and retry the allocation; maybe this is
+		just a temporary shortage of memory */
+
+		os_thread_sleep(1000000);
+
+		retry_count++;
+
+		goto retry;
+	}
+
+	if (ret == NULL) {
+		/* Flush stderr to make more probable that the error
+		message gets in the error file before we generate a seg
+		fault */
+
+		fflush(stderr);
+
+		os_fast_mutex_unlock(&ut_list_mutex);
+
+		/* Make an intentional seg fault so that we get a stack
+		trace */
+		if (assert_on_error) {
+			ut_print_timestamp(stderr);
+
+			fprintf(stderr,
+				"  InnoDB: We now intentionally"
+				" generate a seg fault so that\n"
+				"InnoDB: on Linux we get a stack trace.\n");
+
+			if (*ut_mem_null_ptr) ut_mem_null_ptr = 0;
+		} else {
+			return(NULL);
+		}
+	}
+
+	UNIV_MEM_ALLOC(ret, n + sizeof(ut_mem_block_t));
+
+	((ut_mem_block_t*) ret)->size = n + sizeof(ut_mem_block_t);
+	((ut_mem_block_t*) ret)->magic_n = UT_MEM_MAGIC_N;
+
+	ut_total_allocated_memory += n + sizeof(ut_mem_block_t);
+
+	UT_LIST_ADD_FIRST(mem_block_list, ut_mem_block_list,
+			  ((ut_mem_block_t*) ret));
+	os_fast_mutex_unlock(&ut_list_mutex);
+
+	return((void*)((byte*) ret + sizeof(ut_mem_block_t)));
+#else /* !UNIV_HOTBACKUP */
+	void*	ret = malloc(n);
+	ut_a(ret || !assert_on_error);
+
+	return(ret);
+#endif /* !UNIV_HOTBACKUP */
+}
+
+/**********************************************************************//**
+Frees a memory block allocated with ut_malloc. Freeing a NULL pointer is
+a nop. */
+UNIV_INTERN
+void
+ut_free(
+/*====*/
+	void* ptr)  /*!< in, own: memory block, can be NULL */
+{
+#ifndef UNIV_HOTBACKUP
+	ut_mem_block_t* block;
+
+	if (ptr == NULL) {
+		return;
+	} else if (UNIV_LIKELY(srv_use_sys_malloc)) {
+		free(ptr);
+		return;
+	}
+
+	block = (ut_mem_block_t*)((byte*) ptr - sizeof(ut_mem_block_t));
+
+	os_fast_mutex_lock(&ut_list_mutex);
+
+	ut_a(block->magic_n == UT_MEM_MAGIC_N);
+	ut_a(ut_total_allocated_memory >= block->size);
+
+	ut_total_allocated_memory -= block->size;
+
+	UT_LIST_REMOVE(mem_block_list, ut_mem_block_list, block);
+	free(block);
+
+	os_fast_mutex_unlock(&ut_list_mutex);
+#else /* !UNIV_HOTBACKUP */
+	free(ptr);
+#endif /* !UNIV_HOTBACKUP */
+}
+
+#ifndef UNIV_HOTBACKUP
+/**********************************************************************//**
+Implements realloc. This is needed by /pars/lexyy.cc. Otherwise, you should not
+use this function because the allocation functions in mem0mem.h are the
+recommended ones in InnoDB.
+
+man realloc in Linux, 2004:
+
+       realloc()  changes the size of the memory block pointed to
+       by ptr to size bytes.  The contents will be  unchanged  to
+       the minimum of the old and new sizes; newly allocated mem-
+       ory will be uninitialized.  If ptr is NULL,  the	 call  is
+       equivalent  to malloc(size); if size is equal to zero, the
+       call is equivalent to free(ptr).	 Unless ptr is	NULL,  it
+       must  have  been	 returned by an earlier call to malloc(),
+       calloc() or realloc().
+
+RETURN VALUE
+       realloc() returns a pointer to the newly allocated memory,
+       which is suitably aligned for any kind of variable and may
+       be different from ptr, or NULL if the  request  fails.  If
+       size  was equal to 0, either NULL or a pointer suitable to
+       be passed to free() is returned.	 If realloc()  fails  the
+       original	 block	is  left  untouched  - it is not freed or
+       moved.
+@return	own: pointer to new mem block or NULL */
+UNIV_INTERN
+void*
+ut_realloc(
+/*=======*/
+	void*	ptr,	/*!< in: pointer to old block or NULL */
+	ulint	size)	/*!< in: desired size */
+{
+	ut_mem_block_t* block;
+	ulint		old_size;
+	ulint		min_size;
+	void*		new_ptr;
+
+	if (UNIV_LIKELY(srv_use_sys_malloc)) {
+		return(realloc(ptr, size));
+	}
+
+	if (ptr == NULL) {
+
+		return(ut_malloc(size));
+	}
+
+	if (size == 0) {
+		ut_free(ptr);
+
+		return(NULL);
+	}
+
+	block = (ut_mem_block_t*)((byte*) ptr - sizeof(ut_mem_block_t));
+
+	ut_a(block->magic_n == UT_MEM_MAGIC_N);
+
+	old_size = block->size - sizeof(ut_mem_block_t);
+
+	if (size < old_size) {
+		min_size = size;
+	} else {
+		min_size = old_size;
+	}
+
+	new_ptr = ut_malloc(size);
+
+	if (new_ptr == NULL) {
+
+		return(NULL);
+	}
+
+	/* Copy the old data from ptr */
+	ut_memcpy(new_ptr, ptr, min_size);
+
+	ut_free(ptr);
+
+	return(new_ptr);
+}
+
+/**********************************************************************//**
+Frees in shutdown all allocated memory not freed yet. */
+UNIV_INTERN
+void
+ut_free_all_mem(void)
+/*=================*/
+{
+	ut_mem_block_t* block;
+
+	ut_a(ut_mem_block_list_inited);
+	ut_mem_block_list_inited = FALSE;
+	os_fast_mutex_free(&ut_list_mutex);
+
+	while ((block = UT_LIST_GET_FIRST(ut_mem_block_list))) {
+
+		ut_a(block->magic_n == UT_MEM_MAGIC_N);
+		ut_a(ut_total_allocated_memory >= block->size);
+
+		ut_total_allocated_memory -= block->size;
+
+		UT_LIST_REMOVE(mem_block_list, ut_mem_block_list, block);
+		free(block);
+	}
+
+	if (ut_total_allocated_memory != 0) {
+		fprintf(stderr,
+			"InnoDB: Warning: after shutdown"
+			" total allocated memory is %lu\n",
+			(ulong) ut_total_allocated_memory);
+	}
+
+	ut_mem_block_list_inited = FALSE;
+}
+#endif /* !UNIV_HOTBACKUP */
+
+/**********************************************************************//**
+Copies up to size - 1 characters from the NUL-terminated string src to
+dst, NUL-terminating the result. Returns strlen(src), so truncation
+occurred if the return value >= size.
+@return	strlen(src) */
+UNIV_INTERN
+ulint
+ut_strlcpy(
+/*=======*/
+	char*		dst,	/*!< in: destination buffer */
+	const char*	src,	/*!< in: source buffer */
+	ulint		size)	/*!< in: size of destination buffer */
+{
+	ulint	src_size = strlen(src);
+
+	if (size != 0) {
+		ulint	n = ut_min(src_size, size - 1);
+
+		memcpy(dst, src, n);
+		dst[n] = '\0';
+	}
+
+	return(src_size);
+}
+
+/**********************************************************************//**
+Like ut_strlcpy, but if src doesn't fit in dst completely, copies the last
+(size - 1) bytes of src, not the first.
+@return	strlen(src) */
+UNIV_INTERN
+ulint
+ut_strlcpy_rev(
+/*===========*/
+	char*		dst,	/*!< in: destination buffer */
+	const char*	src,	/*!< in: source buffer */
+	ulint		size)	/*!< in: size of destination buffer */
+{
+	ulint	src_size = strlen(src);
+
+	if (size != 0) {
+		ulint	n = ut_min(src_size, size - 1);
+
+		memcpy(dst, src + src_size - n, n + 1);
+	}
+
+	return(src_size);
+}
+
+#ifndef UNIV_HOTBACKUP
+/**********************************************************************//**
+Return the number of times s2 occurs in s1. Overlapping instances of s2
+are only counted once.
+@return	the number of times s2 occurs in s1 */
+UNIV_INTERN
+ulint
+ut_strcount(
+/*========*/
+	const char*	s1,	/*!< in: string to search in */
+	const char*	s2)	/*!< in: string to search for */
+{
+	ulint	count = 0;
+	ulint	len = strlen(s2);
+
+	if (len == 0) {
+
+		return(0);
+	}
+
+	for (;;) {
+		s1 = strstr(s1, s2);
+
+		if (!s1) {
+
+			break;
+		}
+
+		count++;
+		s1 += len;
+	}
+
+	return(count);
+}
+
+/********************************************************************
+Concatenate 3 strings.*/
+
+char*
+ut_str3cat(
+/*=======*/
+				/* out, own: concatenated string, must be
+				freed with mem_free() */
+	const char*	s1,	/* in: string 1 */
+	const char*	s2,	/* in: string 2 */
+	const char*	s3)	/* in: string 3 */
+{
+	char*	s;
+	ulint	s1_len = strlen(s1);
+	ulint	s2_len = strlen(s2);
+	ulint	s3_len = strlen(s3);
+
+	s = static_cast<char*>(mem_alloc(s1_len + s2_len + s3_len + 1));
+
+	memcpy(s, s1, s1_len);
+	memcpy(s + s1_len, s2, s2_len);
+	memcpy(s + s1_len + s2_len, s3, s3_len);
+
+	s[s1_len + s2_len + s3_len] = '\0';
+
+	return(s);
+}
+/**********************************************************************//**
+Replace every occurrence of s1 in str with s2. Overlapping instances of s1
+are only replaced once.
+@return	own: modified string, must be freed with mem_free() */
+UNIV_INTERN
+char*
+ut_strreplace(
+/*==========*/
+	const char*	str,	/*!< in: string to operate on */
+	const char*	s1,	/*!< in: string to replace */
+	const char*	s2)	/*!< in: string to replace s1 with */
+{
+	char*		new_str;
+	char*		ptr;
+	const char*	str_end;
+	ulint		str_len = strlen(str);
+	ulint		s1_len = strlen(s1);
+	ulint		s2_len = strlen(s2);
+	ulint		count = 0;
+	int		len_delta = (int) s2_len - (int) s1_len;
+
+	str_end = str + str_len;
+
+	if (len_delta <= 0) {
+		len_delta = 0;
+	} else {
+		count = ut_strcount(str, s1);
+	}
+
+	new_str = static_cast<char*>(
+		mem_alloc(str_len + count * len_delta + 1));
+
+	ptr = new_str;
+
+	while (str) {
+		const char*	next = strstr(str, s1);
+
+		if (!next) {
+			next = str_end;
+		}
+
+		memcpy(ptr, str, next - str);
+		ptr += next - str;
+
+		if (next == str_end) {
+
+			break;
+		}
+
+		memcpy(ptr, s2, s2_len);
+		ptr += s2_len;
+
+		str = next + s1_len;
+	}
+
+	*ptr = '\0';
+
+	return(new_str);
+}
+
+#ifdef UNIV_COMPILE_TEST_FUNCS
+
+void
+test_ut_str_sql_format()
+{
+	char	buf[128];
+	ulint	ret;
+
+#define CALL_AND_TEST(str, str_len, buf, buf_size, ret_expected, buf_expected)\
+	do {\
+		ibool	ok = TRUE;\
+		memset(buf, 'x', 10);\
+		buf[10] = '\0';\
+		fprintf(stderr, "TESTING \"%s\", %lu, %lu\n",\
+			str, (ulint) str_len, (ulint) buf_size);\
+		ret = ut_str_sql_format(str, str_len, buf, buf_size);\
+		if (ret != ret_expected) {\
+			fprintf(stderr, "expected ret %lu, got %lu\n",\
+				(ulint) ret_expected, ret);\
+			ok = FALSE;\
+		}\
+		if (strcmp((char*) buf, buf_expected) != 0) {\
+			fprintf(stderr, "expected buf \"%s\", got \"%s\"\n",\
+				buf_expected, buf);\
+			ok = FALSE;\
+		}\
+		if (ok) {\
+			fprintf(stderr, "OK: %lu, \"%s\"\n\n",\
+				(ulint) ret, buf);\
+		} else {\
+			return;\
+		}\
+	} while (0)
+
+	CALL_AND_TEST("abcd", 4, buf, 0, 0, "xxxxxxxxxx");
+
+	CALL_AND_TEST("abcd", 4, buf, 1, 1, "");
+
+	CALL_AND_TEST("abcd", 4, buf, 2, 1, "");
+
+	CALL_AND_TEST("abcd", 0, buf, 3, 3, "''");
+	CALL_AND_TEST("abcd", 1, buf, 3, 1, "");
+	CALL_AND_TEST("abcd", 2, buf, 3, 1, "");
+	CALL_AND_TEST("abcd", 3, buf, 3, 1, "");
+	CALL_AND_TEST("abcd", 4, buf, 3, 1, "");
+
+	CALL_AND_TEST("abcd", 0, buf, 4, 3, "''");
+	CALL_AND_TEST("abcd", 1, buf, 4, 4, "'a'");
+	CALL_AND_TEST("abcd", 2, buf, 4, 4, "'a'");
+	CALL_AND_TEST("abcd", 3, buf, 4, 4, "'a'");
+	CALL_AND_TEST("abcd", 4, buf, 4, 4, "'a'");
+	CALL_AND_TEST("abcde", 5, buf, 4, 4, "'a'");
+	CALL_AND_TEST("'", 1, buf, 4, 3, "''");
+	CALL_AND_TEST("''", 2, buf, 4, 3, "''");
+	CALL_AND_TEST("a'", 2, buf, 4, 4, "'a'");
+	CALL_AND_TEST("'a", 2, buf, 4, 3, "''");
+	CALL_AND_TEST("ab", 2, buf, 4, 4, "'a'");
+
+	CALL_AND_TEST("abcdef", 0, buf, 5, 3, "''");
+	CALL_AND_TEST("abcdef", 1, buf, 5, 4, "'a'");
+	CALL_AND_TEST("abcdef", 2, buf, 5, 5, "'ab'");
+	CALL_AND_TEST("abcdef", 3, buf, 5, 5, "'ab'");
+	CALL_AND_TEST("abcdef", 4, buf, 5, 5, "'ab'");
+	CALL_AND_TEST("abcdef", 5, buf, 5, 5, "'ab'");
+	CALL_AND_TEST("abcdef", 6, buf, 5, 5, "'ab'");
+	CALL_AND_TEST("'", 1, buf, 5, 5, "''''");
+	CALL_AND_TEST("''", 2, buf, 5, 5, "''''");
+	CALL_AND_TEST("a'", 2, buf, 5, 4, "'a'");
+	CALL_AND_TEST("'a", 2, buf, 5, 5, "''''");
+	CALL_AND_TEST("ab", 2, buf, 5, 5, "'ab'");
+	CALL_AND_TEST("abc", 3, buf, 5, 5, "'ab'");
+
+	CALL_AND_TEST("ab", 2, buf, 6, 5, "'ab'");
+
+	CALL_AND_TEST("a'b'c", 5, buf, 32, 10, "'a''b''c'");
+	CALL_AND_TEST("a'b'c'", 6, buf, 32, 12, "'a''b''c'''");
+}
+
+#endif /* UNIV_COMPILE_TEST_FUNCS */
+#endif /* !UNIV_HOTBACKUP */
diff --git a/storage/innobase/ut/ut0rbt.cc b/storage/innobase/ut/ut0rbt.cc
new file mode 100644
index 00000000000..e93844af600
--- /dev/null
+++ b/storage/innobase/ut/ut0rbt.cc
@@ -0,0 +1,1328 @@
+/***************************************************************************//**
+
+Copyright (c) 2007, 2010, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+/********************************************************************//**
+Red-Black tree implementation
+
+(c) 2007 Oracle/Innobase Oy
+
+Created 2007-03-20 Sunny Bains
+***********************************************************************/
+
+#include "ut0rbt.h"
+
+/**********************************************************************//**
+Definition of a red-black tree
+==============================
+
+A red-black tree is a binary search tree which has the following
+red-black properties:
+
+   1. Every node is either red or black.
+   2. Every leaf (NULL - in our case tree->nil) is black.
+   3. If a node is red, then both its children are black.
+   4. Every simple path from a node to a descendant leaf contains the
+      same number of black nodes.
+
+   from (3) above, the implication is that on any path from the root
+   to a leaf, red nodes must not be adjacent.
+
+   However, any number of black nodes may appear in a sequence.
+ */
+
+#if	defined(IB_RBT_TESTING)
+#warning "Testing enabled!"
+#endif
+
+#define ROOT(t)		(t->root->left)
+#define	SIZEOF_NODE(t)	((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
+
+/**********************************************************************//**
+Print out the sub-tree recursively. */
+static
+void
+rbt_print_subtree(
+/*==============*/
+	const ib_rbt_t*		tree,		/*!< in: tree to traverse */
+	const ib_rbt_node_t*	node,		/*!< in: node to print */
+	ib_rbt_print_node	print)		/*!< in: print key function */
+{
+	/* FIXME: Doesn't do anything yet */
+	if (node != tree->nil) {
+		print(node);
+		rbt_print_subtree(tree, node->left, print);
+		rbt_print_subtree(tree, node->right, print);
+	}
+}
+
+/**********************************************************************//**
+Verify that the keys are in order.
+@return	TRUE of OK. FALSE if not ordered */
+static
+ibool
+rbt_check_ordering(
+/*===============*/
+	const ib_rbt_t*		tree)		/*!< in: tree to verfify */
+{
+	const ib_rbt_node_t*	node;
+	const ib_rbt_node_t*	prev = NULL;
+
+	/* Iterate over all the nodes, comparing each node with the prev */
+	for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
+
+		if (prev) {
+			int	result;
+
+			if (tree->cmp_arg) {
+				result = tree->compare_with_arg(
+					tree->cmp_arg, prev->value,
+					node->value);
+			} else {
+				result = tree->compare(
+					prev->value, node->value);
+			}
+
+			if (result >= 0) {
+				return(FALSE);
+			}
+		}
+
+		prev = node;
+	}
+
+	return(TRUE);
+}
+
+/**********************************************************************//**
+Check that every path from the root to the leaves has the same count.
+Count is expressed in the number of black nodes.
+@return	0 on failure else black height of the subtree */
+static
+ibool
+rbt_count_black_nodes(
+/*==================*/
+	const ib_rbt_t*		tree,		/*!< in: tree to verify */
+	const ib_rbt_node_t*	node)		/*!< in: start of sub-tree */
+{
+	ulint	result;
+
+	if (node != tree->nil) {
+		ulint	left_height = rbt_count_black_nodes(tree, node->left);
+
+		ulint	right_height = rbt_count_black_nodes(tree, node->right);
+
+		if (left_height == 0
+		    || right_height == 0
+		    || left_height != right_height) {
+
+			result = 0;
+		} else if (node->color == IB_RBT_RED) {
+
+			/* Case 3 */
+			if (node->left->color != IB_RBT_BLACK
+			    || node->right->color != IB_RBT_BLACK) {
+
+				result = 0;
+			} else {
+				result = left_height;
+			}
+		/* Check if it's anything other than RED or BLACK. */
+		} else if (node->color != IB_RBT_BLACK) {
+
+			result = 0;
+		} else {
+
+			result = right_height + 1;
+		}
+	} else {
+		result = 1;
+	}
+
+	return(result);
+}
+
+/**********************************************************************//**
+Turn the node's right child's left sub-tree into node's right sub-tree.
+This will also make node's right child it's parent. */
+static
+void
+rbt_rotate_left(
+/*============*/
+	const ib_rbt_node_t*	nil,		/*!< in: nil node of the tree */
+	ib_rbt_node_t*		node)		/*!< in: node to rotate */
+{
+	ib_rbt_node_t*	right = node->right;
+
+	node->right = right->left;
+
+	if (right->left != nil) {
+		right->left->parent = node;
+	}
+
+	/* Right's new parent was node's parent. */
+	right->parent = node->parent;
+
+	/* Since root's parent is tree->nil and root->parent->left points
+	back to root, we can avoid the check. */
+	if (node == node->parent->left) {
+		/* Node was on the left of its parent. */
+		node->parent->left = right;
+	} else {
+		/* Node must have been on the right. */
+		node->parent->right = right;
+	}
+
+	/* Finally, put node on right's left. */
+	right->left = node;
+	node->parent = right;
+}
+
+/**********************************************************************//**
+Turn the node's left child's right sub-tree into node's left sub-tree.
+This also make node's left child it's parent. */
+static
+void
+rbt_rotate_right(
+/*=============*/
+	const ib_rbt_node_t*	nil,		/*!< in: nil node of tree */
+	ib_rbt_node_t*		node)		/*!< in: node to rotate */
+{
+	ib_rbt_node_t*	left = node->left;
+
+	node->left = left->right;
+
+	if (left->right != nil) {
+		left->right->parent = node;
+	}
+
+	/* Left's new parent was node's parent. */
+	left->parent = node->parent;
+
+	/* Since root's parent is tree->nil and root->parent->left points
+	back to root, we can avoid the check. */
+	if (node == node->parent->right) {
+	    /* Node was on the left of its parent. */
+            node->parent->right = left;
+	} else {
+	    /* Node must have been on the left. */
+            node->parent->left = left;
+	}
+
+	/* Finally, put node on left's right. */
+	left->right = node;
+	node->parent = left;
+}
+
+/**********************************************************************//**
+Append a node to the tree. */
+static
+ib_rbt_node_t*
+rbt_tree_add_child(
+/*===============*/
+	const ib_rbt_t*	tree,
+	ib_rbt_bound_t*	parent,
+	ib_rbt_node_t*	node)
+{
+	/* Cast away the const. */
+	ib_rbt_node_t*	last = (ib_rbt_node_t*) parent->last;
+
+	if (last == tree->root || parent->result < 0) {
+		last->left = node;
+	} else {
+		/* FIXME: We don't handle duplicates (yet)! */
+		ut_a(parent->result != 0);
+
+		last->right = node;
+	}
+
+	node->parent = last;
+
+	return(node);
+}
+
+/**********************************************************************//**
+Generic binary tree insert */
+static
+ib_rbt_node_t*
+rbt_tree_insert(
+/*============*/
+	ib_rbt_t*	tree,
+	const void*	key,
+	ib_rbt_node_t*	node)
+{
+	ib_rbt_bound_t	parent;
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	parent.result = 0;
+	parent.last = tree->root;
+
+	/* Regular binary search. */
+	while (current != tree->nil) {
+
+		parent.last = current;
+
+		if (tree->cmp_arg) {
+			parent.result = tree->compare_with_arg(
+				tree->cmp_arg, key, current->value);
+		} else {
+			parent.result = tree->compare(key, current->value);
+		}
+
+		if (parent.result < 0) {
+			current = current->left;
+		} else {
+			current = current->right;
+		}
+	}
+
+	ut_a(current == tree->nil);
+
+	rbt_tree_add_child(tree, &parent, node);
+
+	return(node);
+}
+
+/**********************************************************************//**
+Balance a tree after inserting a node. */
+static
+void
+rbt_balance_tree(
+/*=============*/
+	const ib_rbt_t*	tree,			/*!< in: tree to balance */
+	ib_rbt_node_t*	node)			/*!< in: node that was inserted */
+{
+	const ib_rbt_node_t*	nil = tree->nil;
+	ib_rbt_node_t*		parent = node->parent;
+
+	/* Restore the red-black property. */
+	node->color = IB_RBT_RED;
+
+	while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
+		ib_rbt_node_t*	grand_parent = parent->parent;
+
+		if (parent == grand_parent->left) {
+			ib_rbt_node_t*	uncle = grand_parent->right;
+
+			if (uncle->color == IB_RBT_RED) {
+
+				/* Case 1 - change the colors. */
+				uncle->color = IB_RBT_BLACK;
+				parent->color = IB_RBT_BLACK;
+				grand_parent->color = IB_RBT_RED;
+
+				/* Move node up the tree. */
+				node = grand_parent;
+
+			} else {
+
+				if (node == parent->right) {
+					/* Right is a black node and node is
+					to the right, case 2 - move node
+					up and rotate. */
+					node = parent;
+					rbt_rotate_left(nil, node);
+				}
+
+				grand_parent = node->parent->parent;
+
+				/* Case 3. */
+				node->parent->color = IB_RBT_BLACK;
+				grand_parent->color = IB_RBT_RED;
+
+				rbt_rotate_right(nil, grand_parent);
+			}
+
+		} else {
+			ib_rbt_node_t*	uncle = grand_parent->left;
+
+			if (uncle->color == IB_RBT_RED) {
+
+				/* Case 1 - change the colors. */
+				uncle->color = IB_RBT_BLACK;
+				parent->color = IB_RBT_BLACK;
+				grand_parent->color = IB_RBT_RED;
+
+				/* Move node up the tree. */
+				node = grand_parent;
+
+			} else {
+
+				if (node == parent->left) {
+					/* Left is a black node and node is to
+					the right, case 2 - move node up and
+					rotate. */
+					node = parent;
+					rbt_rotate_right(nil, node);
+				}
+
+				grand_parent = node->parent->parent;
+
+				/* Case 3. */
+				node->parent->color = IB_RBT_BLACK;
+				grand_parent->color = IB_RBT_RED;
+
+				rbt_rotate_left(nil, grand_parent);
+			}
+		}
+
+		parent = node->parent;
+	}
+
+	/* Color the root black. */
+	ROOT(tree)->color = IB_RBT_BLACK;
+}
+
+/**********************************************************************//**
+Find the given node's successor.
+@return	successor node or NULL if no successor */
+static
+ib_rbt_node_t*
+rbt_find_successor(
+/*===============*/
+	const ib_rbt_t*		tree,		/*!< in: rb tree */
+	const ib_rbt_node_t*	current)	/*!< in: this is declared const
+						because it can be called via
+						rbt_next() */
+{
+	const ib_rbt_node_t*	nil = tree->nil;
+	ib_rbt_node_t*		next = current->right;
+
+	/* Is there a sub-tree to the right that we can follow. */
+	if (next != nil) {
+
+		/* Follow the left most links of the current right child. */
+		while (next->left != nil) {
+			next = next->left;
+		}
+
+	} else { /* We will have to go up the tree to find the successor. */
+		ib_rbt_node_t*	parent = current->parent;
+
+		/* Cast away the const. */
+		next = (ib_rbt_node_t*) current;
+
+		while (parent != tree->root && next == parent->right) {
+			next = parent;
+			parent = next->parent;
+		}
+
+		next = (parent == tree->root) ? NULL : parent;
+	}
+
+	return(next);
+}
+
+/**********************************************************************//**
+Find the given node's precedecessor.
+@return	predecessor node or NULL if no predecesor */
+static
+ib_rbt_node_t*
+rbt_find_predecessor(
+/*=================*/
+	const ib_rbt_t*		tree,		/*!< in: rb tree */
+	const ib_rbt_node_t*	current)	/*!< in: this is declared const
+						because it can be called via
+						rbt_prev() */
+{
+	const ib_rbt_node_t*	nil = tree->nil;
+	ib_rbt_node_t*		prev = current->left;
+
+	/* Is there a sub-tree to the left that we can follow. */
+	if (prev != nil) {
+
+		/* Follow the right most links of the current left child. */
+		while (prev->right != nil) {
+			prev = prev->right;
+		}
+
+	} else { /* We will have to go up the tree to find the precedecessor. */
+		ib_rbt_node_t*	parent = current->parent;
+
+		/* Cast away the const. */
+		prev = (ib_rbt_node_t*) current;
+
+		while (parent != tree->root && prev == parent->left) {
+			prev = parent;
+			parent = prev->parent;
+		}
+
+		prev = (parent == tree->root) ? NULL : parent;
+	}
+
+	return(prev);
+}
+
+/**********************************************************************//**
+Replace node with child. After applying transformations eject becomes
+an orphan. */
+static
+void
+rbt_eject_node(
+/*===========*/
+	ib_rbt_node_t*	eject,			/*!< in: node to eject */
+	ib_rbt_node_t*	node)			/*!< in: node to replace with */
+{
+	/* Update the to be ejected node's parent's child pointers. */
+	if (eject->parent->left == eject) {
+		eject->parent->left = node;
+	} else if (eject->parent->right == eject) {
+		eject->parent->right = node;
+	} else {
+		ut_a(0);
+	}
+	/* eject is now an orphan but otherwise its pointers
+	and color are left intact. */
+
+	node->parent = eject->parent;
+}
+
+/**********************************************************************//**
+Replace a node with another node. */
+static
+void
+rbt_replace_node(
+/*=============*/
+	ib_rbt_node_t*	replace,		/*!< in: node to replace */
+	ib_rbt_node_t*	node)			/*!< in: node to replace with */
+{
+	ib_rbt_color_t	color = node->color;
+
+	/* Update the node pointers. */
+	node->left = replace->left;
+	node->right = replace->right;
+
+	/* Update the child node pointers. */
+	node->left->parent = node;
+	node->right->parent = node;
+
+	/* Make the parent of replace point to node. */
+	rbt_eject_node(replace, node);
+
+	/* Swap the colors. */
+	node->color = replace->color;
+	replace->color = color;
+}
+
+/**********************************************************************//**
+Detach node from the tree replacing it with one of it's children.
+@return	the child node that now occupies the position of the detached node */
+static
+ib_rbt_node_t*
+rbt_detach_node(
+/*============*/
+	const ib_rbt_t*	tree,			/*!< in: rb tree */
+	ib_rbt_node_t*	node)			/*!< in: node to detach */
+{
+	ib_rbt_node_t*		child;
+	const ib_rbt_node_t*	nil = tree->nil;
+
+	if (node->left != nil && node->right != nil) {
+		/* Case where the node to be deleted has two children. */
+		ib_rbt_node_t*	successor = rbt_find_successor(tree, node);
+
+		ut_a(successor != nil);
+		ut_a(successor->parent != nil);
+		ut_a(successor->left == nil);
+
+		child = successor->right;
+
+		/* Remove the successor node and replace with its child. */
+		rbt_eject_node(successor, child);
+
+		/* Replace the node to delete with its successor node. */
+		rbt_replace_node(node, successor);
+	} else {
+		ut_a(node->left == nil || node->right == nil);
+
+		child = (node->left != nil) ? node->left : node->right;
+
+		/* Replace the node to delete with one of it's children. */
+		rbt_eject_node(node, child);
+	}
+
+	/* Reset the node links. */
+	node->parent = node->right = node->left = tree->nil;
+
+	return(child);
+}
+
+/**********************************************************************//**
+Rebalance the right sub-tree after deletion.
+@return	node to rebalance if more rebalancing required else NULL */
+static
+ib_rbt_node_t*
+rbt_balance_right(
+/*==============*/
+	const ib_rbt_node_t*	nil,		/*!< in: rb tree nil node */
+	ib_rbt_node_t*		parent,		/*!< in: parent node */
+	ib_rbt_node_t*		sibling)	/*!< in: sibling node */
+{
+	ib_rbt_node_t*		node = NULL;
+
+	ut_a(sibling != nil);
+
+	/* Case 3. */
+	if (sibling->color == IB_RBT_RED) {
+
+		parent->color = IB_RBT_RED;
+		sibling->color = IB_RBT_BLACK;
+
+		rbt_rotate_left(nil, parent);
+
+		sibling = parent->right;
+
+		ut_a(sibling != nil);
+	}
+
+	/* Since this will violate case 3 because of the change above. */
+	if (sibling->left->color == IB_RBT_BLACK
+	    && sibling->right->color == IB_RBT_BLACK) {
+
+		node = parent; /* Parent needs to be rebalanced too. */
+		sibling->color = IB_RBT_RED;
+
+	} else {
+		if (sibling->right->color == IB_RBT_BLACK) {
+
+			ut_a(sibling->left->color == IB_RBT_RED);
+
+			sibling->color = IB_RBT_RED;
+			sibling->left->color = IB_RBT_BLACK;
+
+			rbt_rotate_right(nil, sibling);
+
+			sibling = parent->right;
+			ut_a(sibling != nil);
+		}
+
+		sibling->color = parent->color;
+		sibling->right->color = IB_RBT_BLACK;
+
+		parent->color = IB_RBT_BLACK;
+
+		rbt_rotate_left(nil, parent);
+	}
+
+	return(node);
+}
+
+/**********************************************************************//**
+Rebalance the left sub-tree after deletion.
+@return	node to rebalance if more rebalancing required else NULL */
+static
+ib_rbt_node_t*
+rbt_balance_left(
+/*=============*/
+	const ib_rbt_node_t*	nil,		/*!< in: rb tree nil node */
+	ib_rbt_node_t*		parent,		/*!< in: parent node */
+	ib_rbt_node_t*		sibling)	/*!< in: sibling node */
+{
+	ib_rbt_node_t*	node = NULL;
+
+	ut_a(sibling != nil);
+
+	/* Case 3. */
+	if (sibling->color == IB_RBT_RED) {
+
+		parent->color = IB_RBT_RED;
+		sibling->color = IB_RBT_BLACK;
+
+		rbt_rotate_right(nil, parent);
+		sibling = parent->left;
+
+		ut_a(sibling != nil);
+	}
+
+	/* Since this will violate case 3 because of the change above. */
+	if (sibling->right->color == IB_RBT_BLACK
+	    && sibling->left->color == IB_RBT_BLACK) {
+
+		node = parent; /* Parent needs to be rebalanced too. */
+		sibling->color = IB_RBT_RED;
+
+	} else {
+		if (sibling->left->color == IB_RBT_BLACK) {
+
+			ut_a(sibling->right->color == IB_RBT_RED);
+
+			sibling->color = IB_RBT_RED;
+			sibling->right->color = IB_RBT_BLACK;
+
+			rbt_rotate_left(nil, sibling);
+
+			sibling = parent->left;
+
+			ut_a(sibling != nil);
+		}
+
+		sibling->color = parent->color;
+		sibling->left->color = IB_RBT_BLACK;
+
+		parent->color = IB_RBT_BLACK;
+
+		rbt_rotate_right(nil, parent);
+	}
+
+	return(node);
+}
+
+/**********************************************************************//**
+Delete the node and rebalance the tree if necessary */
+static
+void
+rbt_remove_node_and_rebalance(
+/*==========================*/
+	ib_rbt_t*		tree,		/*!< in: rb tree */
+	ib_rbt_node_t*		node)		/*!< in: node to remove */
+{
+	/* Detach node and get the node that will be used
+	as rebalance start. */
+	ib_rbt_node_t*	child = rbt_detach_node(tree, node);
+
+	if (node->color == IB_RBT_BLACK) {
+		ib_rbt_node_t*	last = child;
+
+		ROOT(tree)->color = IB_RBT_RED;
+
+		while (child && child->color == IB_RBT_BLACK) {
+			ib_rbt_node_t*	parent = child->parent;
+
+			/* Did the deletion cause an imbalance in the
+			parents left sub-tree. */
+			if (parent->left == child) {
+
+				child = rbt_balance_right(
+					tree->nil, parent, parent->right);
+
+			} else if (parent->right == child) {
+
+				child = rbt_balance_left(
+					tree->nil, parent, parent->left);
+
+			} else {
+				ut_error;
+			}
+
+			if (child) {
+				last = child;
+			}
+		}
+
+		ut_a(last);
+
+		last->color = IB_RBT_BLACK;
+		ROOT(tree)->color = IB_RBT_BLACK;
+	}
+
+	/* Note that we have removed a node from the tree. */
+	--tree->n_nodes;
+}
+
+/**********************************************************************//**
+Recursively free the nodes. */
+static
+void
+rbt_free_node(
+/*==========*/
+	ib_rbt_node_t*	node,			/*!< in: node to free */
+	ib_rbt_node_t*	nil)			/*!< in: rb tree nil node */
+{
+	if (node != nil) {
+		rbt_free_node(node->left, nil);
+		rbt_free_node(node->right, nil);
+
+		ut_free(node);
+	}
+}
+
+/**********************************************************************//**
+Free all the nodes and free the tree. */
+UNIV_INTERN
+void
+rbt_free(
+/*=====*/
+	ib_rbt_t*	tree)			/*!< in: rb tree to free */
+{
+	rbt_free_node(tree->root, tree->nil);
+	ut_free(tree->nil);
+	ut_free(tree);
+}
+
+/**********************************************************************//**
+Create an instance of a red black tree, whose comparison function takes
+an argument
+@return	an empty rb tree */
+UNIV_INTERN
+ib_rbt_t*
+rbt_create_arg_cmp(
+/*===============*/
+	size_t		sizeof_value,		/*!< in: sizeof data item */
+	ib_rbt_arg_compare
+			compare,		/*!< in: fn to compare items */
+	void*		cmp_arg)		/*!< in: compare fn arg */
+{
+	ib_rbt_t*       tree;
+
+	ut_a(cmp_arg);
+
+	tree = rbt_create(sizeof_value, NULL);
+	tree->cmp_arg = cmp_arg;
+	tree->compare_with_arg = compare;
+
+	return(tree);
+}
+
+/**********************************************************************//**
+Create an instance of a red black tree.
+@return	an empty rb tree */
+UNIV_INTERN
+ib_rbt_t*
+rbt_create(
+/*=======*/
+	size_t		sizeof_value,		/*!< in: sizeof data item */
+	ib_rbt_compare	compare)		/*!< in: fn to compare items */
+{
+	ib_rbt_t*	tree;
+	ib_rbt_node_t*	node;
+
+	tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
+	memset(tree, 0, sizeof(*tree));
+
+	tree->sizeof_value = sizeof_value;
+
+	/* Create the sentinel (NIL) node. */
+	node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
+	memset(node, 0, sizeof(*node));
+
+	node->color = IB_RBT_BLACK;
+	node->parent = node->left = node->right = node;
+
+	/* Create the "fake" root, the real root node will be the
+	left child of this node. */
+	node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
+	memset(node, 0, sizeof(*node));
+
+	node->color = IB_RBT_BLACK;
+	node->parent = node->left = node->right = tree->nil;
+
+	tree->compare = compare;
+
+	return(tree);
+}
+
+/**********************************************************************//**
+Generic insert of a value in the rb tree.
+@return	inserted node */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_insert(
+/*=======*/
+	ib_rbt_t*	tree,			/*!< in: rb tree */
+	const void*	key,			/*!< in: key for ordering */
+	const void*	value)			/*!< in: value of key, this value
+						is copied to the node */
+{
+	ib_rbt_node_t*	node;
+
+	/* Create the node that will hold the value data. */
+	node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
+
+	memcpy(node->value, value, tree->sizeof_value);
+	node->parent = node->left = node->right = tree->nil;
+
+	/* Insert in the tree in the usual way. */
+	rbt_tree_insert(tree, key, node);
+	rbt_balance_tree(tree, node);
+
+	++tree->n_nodes;
+
+	return(node);
+}
+
+/**********************************************************************//**
+Add a new node to the tree, useful for data that is pre-sorted.
+@return	appended node */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_add_node(
+/*=========*/
+	ib_rbt_t*	tree,			/*!< in: rb tree */
+	ib_rbt_bound_t*	parent,			/*!< in: bounds */
+	const void*	value)			/*!< in: this value is copied
+						to the node */
+{
+	ib_rbt_node_t*	node;
+
+	/* Create the node that will hold the value data */
+	node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
+
+	memcpy(node->value, value, tree->sizeof_value);
+	node->parent = node->left = node->right = tree->nil;
+
+	/* If tree is empty */
+	if (parent->last == NULL) {
+		parent->last = tree->root;
+	}
+
+	/* Append the node, the hope here is that the caller knows
+	what s/he is doing. */
+	rbt_tree_add_child(tree, parent, node);
+	rbt_balance_tree(tree, node);
+
+	++tree->n_nodes;
+
+#if	defined(IB_RBT_TESTING)
+	ut_a(rbt_validate(tree));
+#endif
+	return(node);
+}
+
+/**********************************************************************//**
+Find a matching node in the rb tree.
+@return	NULL if not found else the node where key was found */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_lookup(
+/*=======*/
+	const ib_rbt_t*	tree,			/*!< in: rb tree */
+	const void*	key)			/*!< in: key to use for search */
+{
+	const ib_rbt_node_t*	current = ROOT(tree);
+
+	/* Regular binary search. */
+	while (current != tree->nil) {
+		int	result;
+
+		if (tree->cmp_arg) {
+			result = tree->compare_with_arg(
+				tree->cmp_arg, key, current->value);
+		} else {
+			result = tree->compare(key, current->value);
+		}
+
+		if (result < 0) {
+			current = current->left;
+		} else if (result > 0) {
+			current = current->right;
+		} else {
+			break;
+		}
+	}
+
+	return(current != tree->nil ? current : NULL);
+}
+
+/**********************************************************************//**
+Delete a node indentified by key.
+@return	TRUE if success FALSE if not found */
+UNIV_INTERN
+ibool
+rbt_delete(
+/*=======*/
+	ib_rbt_t*	tree,			/*!< in: rb tree */
+	const void*	key)			/*!< in: key to delete */
+{
+	ibool		deleted = FALSE;
+	ib_rbt_node_t*	node = (ib_rbt_node_t*) rbt_lookup(tree, key);
+
+	if (node) {
+		rbt_remove_node_and_rebalance(tree, node);
+
+		ut_free(node);
+		deleted = TRUE;
+	}
+
+	return(deleted);
+}
+
+/**********************************************************************//**
+Remove a node from the rb tree, the node is not free'd, that is the
+callers responsibility.
+@return	deleted node but without the const */
+UNIV_INTERN
+ib_rbt_node_t*
+rbt_remove_node(
+/*============*/
+	ib_rbt_t*		tree,		/*!< in: rb tree */
+	const ib_rbt_node_t*	const_node)	/*!< in: node to delete, this
+						is a fudge and declared const
+						because the caller can access
+						only const nodes */
+{
+	/* Cast away the const. */
+	rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
+
+	/* This is to make it easier to do something like this:
+		ut_free(rbt_remove_node(node));
+	*/
+
+	return((ib_rbt_node_t*) const_node);
+}
+
+/**********************************************************************//**
+Find the node that has the lowest key that is >= key.
+@return	node satisfying the lower bound constraint or NULL */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_lower_bound(
+/*============*/
+	const ib_rbt_t*	tree,			/*!< in: rb tree */
+	const void*	key)			/*!< in: key to search */
+{
+	ib_rbt_node_t*	lb_node = NULL;
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	while (current != tree->nil) {
+		int	result;
+
+		if (tree->cmp_arg) {
+			result = tree->compare_with_arg(
+				tree->cmp_arg, key, current->value);
+		} else {
+			result = tree->compare(key, current->value);
+		}
+
+		if (result > 0) {
+
+			current = current->right;
+
+		} else if (result < 0) {
+
+			lb_node = current;
+			current = current->left;
+
+		} else {
+			lb_node = current;
+			break;
+		}
+	}
+
+	return(lb_node);
+}
+
+/**********************************************************************//**
+Find the node that has the greatest key that is <= key.
+@return	node satisfying the upper bound constraint or NULL */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_upper_bound(
+/*============*/
+	const ib_rbt_t*	tree,			/*!< in: rb tree */
+	const void*	key)			/*!< in: key to search */
+{
+	ib_rbt_node_t*	ub_node = NULL;
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	while (current != tree->nil) {
+		int	result;
+
+		if (tree->cmp_arg) {
+			result = tree->compare_with_arg(
+				tree->cmp_arg, key, current->value);
+		} else {
+			result = tree->compare(key, current->value);
+		}
+
+		if (result > 0) {
+
+			ub_node = current;
+			current = current->right;
+
+		} else if (result < 0) {
+
+			current = current->left;
+
+		} else {
+			ub_node = current;
+			break;
+		}
+	}
+
+	return(ub_node);
+}
+
+/**********************************************************************//**
+Find the node that has the greatest key that is <= key.
+@return	value of result */
+UNIV_INTERN
+int
+rbt_search(
+/*=======*/
+	const ib_rbt_t*	tree,			/*!< in: rb tree */
+	ib_rbt_bound_t*	parent,			/*!< in: search bounds */
+	const void*	key)			/*!< in: key to search */
+{
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	/* Every thing is greater than the NULL root. */
+	parent->result = 1;
+	parent->last = NULL;
+
+	while (current != tree->nil) {
+
+		parent->last = current;
+
+		if (tree->cmp_arg) {
+			parent->result = tree->compare_with_arg(
+				tree->cmp_arg, key, current->value);
+		} else {
+			parent->result = tree->compare(key, current->value);
+		}
+
+		if (parent->result > 0) {
+			current = current->right;
+		} else if (parent->result < 0) {
+			current = current->left;
+		} else {
+			break;
+		}
+	}
+
+	return(parent->result);
+}
+
+/**********************************************************************//**
+Find the node that has the greatest key that is <= key. But use the
+supplied comparison function.
+@return	value of result */
+UNIV_INTERN
+int
+rbt_search_cmp(
+/*===========*/
+	const ib_rbt_t*	tree,			/*!< in: rb tree */
+	ib_rbt_bound_t*	parent,			/*!< in: search bounds */
+	const void*	key,			/*!< in: key to search */
+	ib_rbt_compare	compare,		/*!< in: fn to compare items */
+	ib_rbt_arg_compare
+			arg_compare)		/*!< in: fn to compare items
+						with argument */
+{
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	/* Every thing is greater than the NULL root. */
+	parent->result = 1;
+	parent->last = NULL;
+
+	while (current != tree->nil) {
+
+		parent->last = current;
+
+		if (arg_compare) {
+			ut_ad(tree->cmp_arg);
+			parent->result = arg_compare(
+				tree->cmp_arg, key, current->value);
+		} else {
+			parent->result = compare(key, current->value);
+		}
+
+		if (parent->result > 0) {
+			current = current->right;
+		} else if (parent->result < 0) {
+			current = current->left;
+		} else {
+			break;
+		}
+	}
+
+	return(parent->result);
+}
+
+/**********************************************************************//**
+Return the left most node in the tree. */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_first(
+/*======*/
+						/* out leftmost node or NULL */
+	const ib_rbt_t*	tree)			/* in: rb tree */
+{
+	ib_rbt_node_t*	first = NULL;
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	while (current != tree->nil) {
+		first = current;
+		current = current->left;
+	}
+
+	return(first);
+}
+
+/**********************************************************************//**
+Return the right most node in the tree.
+@return	the rightmost node or NULL */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_last(
+/*=====*/
+	const ib_rbt_t*	tree)			/*!< in: rb tree */
+{
+	ib_rbt_node_t*	last = NULL;
+	ib_rbt_node_t*	current = ROOT(tree);
+
+	while (current != tree->nil) {
+		last = current;
+		current = current->right;
+	}
+
+	return(last);
+}
+
+/**********************************************************************//**
+Return the next node.
+@return	node next from current */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_next(
+/*=====*/
+	const ib_rbt_t*		tree,		/*!< in: rb tree */
+	const ib_rbt_node_t*	current)	/*!< in: current node */
+{
+	return(current ? rbt_find_successor(tree, current) : NULL);
+}
+
+/**********************************************************************//**
+Return the previous node.
+@return	node prev from current */
+UNIV_INTERN
+const ib_rbt_node_t*
+rbt_prev(
+/*=====*/
+	const ib_rbt_t*		tree,		/*!< in: rb tree */
+	const ib_rbt_node_t*	current)	/*!< in: current node */
+{
+	return(current ? rbt_find_predecessor(tree, current) : NULL);
+}
+
+/**********************************************************************//**
+Reset the tree. Delete all the nodes. */
+UNIV_INTERN
+void
+rbt_clear(
+/*======*/
+	ib_rbt_t*	tree)			/*!< in: rb tree */
+{
+	rbt_free_node(ROOT(tree), tree->nil);
+
+	tree->n_nodes = 0;
+	tree->root->left = tree->root->right = tree->nil;
+}
+
+/**********************************************************************//**
+Merge the node from dst into src. Return the number of nodes merged.
+@return	no. of recs merged */
+UNIV_INTERN
+ulint
+rbt_merge_uniq(
+/*===========*/
+	ib_rbt_t*	dst,			/*!< in: dst rb tree */
+	const ib_rbt_t*	src)			/*!< in: src rb tree */
+{
+	ib_rbt_bound_t		parent;
+	ulint			n_merged = 0;
+	const	ib_rbt_node_t*	src_node = rbt_first(src);
+
+	if (rbt_empty(src) || dst == src) {
+		return(0);
+	}
+
+	for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
+
+		if (rbt_search(dst, &parent, src_node->value) != 0) {
+			rbt_add_node(dst, &parent, src_node->value);
+			++n_merged;
+		}
+	}
+
+	return(n_merged);
+}
+
+/**********************************************************************//**
+Merge the node from dst into src. Return the number of nodes merged.
+Delete the nodes from src after copying node to dst. As a side effect
+the duplicates will be left untouched in the src.
+@return	no. of recs merged */
+UNIV_INTERN
+ulint
+rbt_merge_uniq_destructive(
+/*=======================*/
+	ib_rbt_t*	dst,			/*!< in: dst rb tree */
+	ib_rbt_t*	src)			/*!< in: src rb tree */
+{
+	ib_rbt_bound_t	parent;
+	ib_rbt_node_t*	src_node;
+	ulint		old_size = rbt_size(dst);
+
+	if (rbt_empty(src) || dst == src) {
+		return(0);
+	}
+
+	for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
+		ib_rbt_node_t*	prev = src_node;
+
+		src_node = (ib_rbt_node_t*) rbt_next(src, prev);
+
+		/* Skip duplicates. */
+		if (rbt_search(dst, &parent, prev->value) != 0) {
+
+			/* Remove and reset the node but preserve
+			the node (data) value. */
+			rbt_remove_node_and_rebalance(src, prev);
+
+			/* The nil should be taken from the dst tree. */
+			prev->parent = prev->left = prev->right = dst->nil;
+			rbt_tree_add_child(dst, &parent, prev);
+			rbt_balance_tree(dst, prev);
+
+			++dst->n_nodes;
+		}
+	}
+
+#if	defined(IB_RBT_TESTING)
+	ut_a(rbt_validate(dst));
+	ut_a(rbt_validate(src));
+#endif
+	return(rbt_size(dst) - old_size);
+}
+
+/**********************************************************************//**
+Check that every path from the root to the leaves has the same count and
+the tree nodes are in order.
+@return	TRUE if OK FALSE otherwise */
+UNIV_INTERN
+ibool
+rbt_validate(
+/*=========*/
+	const ib_rbt_t*	tree)		/*!< in: RB tree to validate */
+{
+	if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
+		return(rbt_check_ordering(tree));
+	}
+
+	return(FALSE);
+}
+
+/**********************************************************************//**
+Iterate over the tree in depth first order. */
+UNIV_INTERN
+void
+rbt_print(
+/*======*/
+	const ib_rbt_t*		tree,		/*!< in: tree to traverse */
+	ib_rbt_print_node	print)		/*!< in: print function */
+{
+	rbt_print_subtree(tree, ROOT(tree), print);
+}
diff --git a/storage/innobase/ut/ut0rnd.cc b/storage/innobase/ut/ut0rnd.cc
new file mode 100644
index 00000000000..3b4d7381181
--- /dev/null
+++ b/storage/innobase/ut/ut0rnd.cc
@@ -0,0 +1,97 @@
+/*****************************************************************************
+
+Copyright (c) 1994, 2009, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/***************************************************************//**
+@file ut/ut0rnd.cc
+Random numbers and hashing
+
+Created 5/11/1994 Heikki Tuuri
+********************************************************************/
+
+#include "ut0rnd.h"
+
+#ifdef UNIV_NONINL
+#include "ut0rnd.ic"
+#endif
+
+/** These random numbers are used in ut_find_prime */
+/*@{*/
+#define	UT_RANDOM_1	1.0412321
+#define	UT_RANDOM_2	1.1131347
+#define UT_RANDOM_3	1.0132677
+/*@}*/
+
+/** Seed value of ut_rnd_gen_ulint(). */
+UNIV_INTERN ulint	ut_rnd_ulint_counter = 65654363;
+
+/***********************************************************//**
+Looks for a prime number slightly greater than the given argument.
+The prime is chosen so that it is not near any power of 2.
+@return	prime */
+UNIV_INTERN
+ulint
+ut_find_prime(
+/*==========*/
+	ulint	n)	/*!< in: positive number > 100 */
+{
+	ulint	pow2;
+	ulint	i;
+
+	n += 100;
+
+	pow2 = 1;
+	while (pow2 * 2 < n) {
+		pow2 = 2 * pow2;
+	}
+
+	if ((double) n < 1.05 * (double) pow2) {
+		n = (ulint) ((double) n * UT_RANDOM_1);
+	}
+
+	pow2 = 2 * pow2;
+
+	if ((double) n > 0.95 * (double) pow2) {
+		n = (ulint) ((double) n * UT_RANDOM_2);
+	}
+
+	if (n > pow2 - 20) {
+		n += 30;
+	}
+
+	/* Now we have n far enough from powers of 2. To make
+	n more random (especially, if it was not near
+	a power of 2), we then multiply it by a random number. */
+
+	n = (ulint) ((double) n * UT_RANDOM_3);
+
+	for (;; n++) {
+		i = 2;
+		while (i * i <= n) {
+			if (n % i == 0) {
+				goto next_n;
+			}
+			i++;
+		}
+
+		/* Found a prime */
+		break;
+next_n:		;
+	}
+
+	return(n);
+}
diff --git a/storage/innobase/ut/ut0ut.cc b/storage/innobase/ut/ut0ut.cc
new file mode 100644
index 00000000000..68446cc85ef
--- /dev/null
+++ b/storage/innobase/ut/ut0ut.cc
@@ -0,0 +1,840 @@
+/*****************************************************************************
+
+Copyright (c) 1994, 2014, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/***************************************************************//**
+@file ut/ut0ut.cc
+Various utilities for Innobase.
+
+Created 5/11/1994 Heikki Tuuri
+********************************************************************/
+
+#include "ut0ut.h"
+
+#ifndef UNIV_INNOCHECKSUM
+
+#include "ut0sort.h"
+#include "os0thread.h" /* thread-ID */
+
+#ifdef UNIV_NONINL
+#include "ut0ut.ic"
+#endif
+
+#include <stdarg.h>
+#include <string.h>
+#include <ctype.h>
+
+#ifndef UNIV_HOTBACKUP
+# include "trx0trx.h"
+# include "ha_prototypes.h"
+# include "mysql_com.h" /* NAME_LEN */
+#endif /* UNIV_HOTBACKUP */
+
+/** A constant to prevent the compiler from optimizing ut_delay() away. */
+UNIV_INTERN ibool	ut_always_false	= FALSE;
+
+#ifdef __WIN__
+/*****************************************************************//**
+NOTE: The Windows epoch starts from 1601/01/01 whereas the Unix
+epoch starts from 1970/1/1. For selection of constant see:
+http://support.microsoft.com/kb/167296/ */
+#define WIN_TO_UNIX_DELTA_USEC  ((ib_int64_t) 11644473600000000ULL)
+
+
+/*****************************************************************//**
+This is the Windows version of gettimeofday(2).
+@return	0 if all OK else -1 */
+static
+int
+ut_gettimeofday(
+/*============*/
+	struct timeval*	tv,	/*!< out: Values are relative to Unix epoch */
+	void*		tz)	/*!< in: not used */
+{
+	FILETIME	ft;
+	ib_int64_t	tm;
+
+	if (!tv) {
+		errno = EINVAL;
+		return(-1);
+	}
+
+	GetSystemTimeAsFileTime(&ft);
+
+	tm = (ib_int64_t) ft.dwHighDateTime << 32;
+	tm |= ft.dwLowDateTime;
+
+	ut_a(tm >= 0);	/* If tm wraps over to negative, the quotient / 10
+			does not work */
+
+	tm /= 10;	/* Convert from 100 nsec periods to usec */
+
+	/* If we don't convert to the Unix epoch the value for
+	struct timeval::tv_sec will overflow.*/
+	tm -= WIN_TO_UNIX_DELTA_USEC;
+
+	tv->tv_sec  = (long) (tm / 1000000L);
+	tv->tv_usec = (long) (tm % 1000000L);
+
+	return(0);
+}
+#else
+/** An alias for gettimeofday(2).  On Microsoft Windows, we have to
+reimplement this function. */
+#define	ut_gettimeofday		gettimeofday
+#endif
+
+/**********************************************************//**
+Returns system time. We do not specify the format of the time returned:
+the only way to manipulate it is to use the function ut_difftime.
+@return	system time */
+UNIV_INTERN
+ib_time_t
+ut_time(void)
+/*=========*/
+{
+	return(time(NULL));
+}
+
+#ifndef UNIV_HOTBACKUP
+/**********************************************************//**
+Returns system time.
+Upon successful completion, the value 0 is returned; otherwise the
+value -1 is returned and the global variable errno is set to indicate the
+error.
+@return	0 on success, -1 otherwise */
+UNIV_INTERN
+int
+ut_usectime(
+/*========*/
+	ulint*	sec,	/*!< out: seconds since the Epoch */
+	ulint*	ms)	/*!< out: microseconds since the Epoch+*sec */
+{
+	struct timeval	tv;
+	int		ret;
+	int		errno_gettimeofday;
+	int		i;
+
+	for (i = 0; i < 10; i++) {
+
+		ret = ut_gettimeofday(&tv, NULL);
+
+		if (ret == -1) {
+			errno_gettimeofday = errno;
+			ut_print_timestamp(stderr);
+			fprintf(stderr, "  InnoDB: gettimeofday(): %s\n",
+				strerror(errno_gettimeofday));
+			os_thread_sleep(100000);  /* 0.1 sec */
+			errno = errno_gettimeofday;
+		} else {
+			break;
+		}
+	}
+
+	if (ret != -1) {
+		*sec = (ulint) tv.tv_sec;
+		*ms  = (ulint) tv.tv_usec;
+	}
+
+	return(ret);
+}
+
+/**********************************************************//**
+Returns the number of microseconds since epoch. Similar to
+time(3), the return value is also stored in *tloc, provided
+that tloc is non-NULL.
+@return	us since epoch */
+UNIV_INTERN
+ullint
+ut_time_us(
+/*=======*/
+	ullint*	tloc)	/*!< out: us since epoch, if non-NULL */
+{
+	struct timeval	tv;
+	ullint		us;
+
+	ut_gettimeofday(&tv, NULL);
+
+	us = (ullint) tv.tv_sec * 1000000 + tv.tv_usec;
+
+	if (tloc != NULL) {
+		*tloc = us;
+	}
+
+	return(us);
+}
+
+/**********************************************************//**
+Returns the number of milliseconds since some epoch.  The
+value may wrap around.  It should only be used for heuristic
+purposes.
+@return	ms since epoch */
+UNIV_INTERN
+ulint
+ut_time_ms(void)
+/*============*/
+{
+	struct timeval	tv;
+
+	ut_gettimeofday(&tv, NULL);
+
+	return((ulint) tv.tv_sec * 1000 + tv.tv_usec / 1000);
+}
+#endif /* !UNIV_HOTBACKUP */
+
+/**********************************************************//**
+Returns the difference of two times in seconds.
+@return	time2 - time1 expressed in seconds */
+UNIV_INTERN
+double
+ut_difftime(
+/*========*/
+	ib_time_t	time2,	/*!< in: time */
+	ib_time_t	time1)	/*!< in: time */
+{
+	return(difftime(time2, time1));
+}
+
+#endif /* !UNIV_INNOCHECKSUM */
+
+/**********************************************************//**
+Prints a timestamp to a file. */
+UNIV_INTERN
+void
+ut_print_timestamp(
+/*===============*/
+	FILE*  file) /*!< in: file where to print */
+{
+	ulint thread_id = 0;
+
+#ifndef UNIV_INNOCHECKSUM
+	thread_id = os_thread_pf(os_thread_get_curr_id());
+#endif
+
+#ifdef __WIN__
+	SYSTEMTIME cal_tm;
+
+	GetLocalTime(&cal_tm);
+
+	fprintf(file, "%d-%02d-%02d %02d:%02d:%02d %lx",
+		(int) cal_tm.wYear,
+		(int) cal_tm.wMonth,
+		(int) cal_tm.wDay,
+		(int) cal_tm.wHour,
+		(int) cal_tm.wMinute,
+		(int) cal_tm.wSecond,
+		thread_id);
+#else
+	struct tm* cal_tm_ptr;
+	time_t	   tm;
+
+#ifdef HAVE_LOCALTIME_R
+	struct tm  cal_tm;
+	time(&tm);
+	localtime_r(&tm, &cal_tm);
+	cal_tm_ptr = &cal_tm;
+#else
+	time(&tm);
+	cal_tm_ptr = localtime(&tm);
+#endif
+	fprintf(file, "%d-%02d-%02d %02d:%02d:%02d %lx",
+		cal_tm_ptr->tm_year + 1900,
+		cal_tm_ptr->tm_mon + 1,
+		cal_tm_ptr->tm_mday,
+		cal_tm_ptr->tm_hour,
+		cal_tm_ptr->tm_min,
+		cal_tm_ptr->tm_sec,
+		thread_id);
+#endif
+}
+
+#ifndef UNIV_INNOCHECKSUM
+
+/**********************************************************//**
+Sprintfs a timestamp to a buffer, 13..14 chars plus terminating NUL. */
+UNIV_INTERN
+void
+ut_sprintf_timestamp(
+/*=================*/
+	char*	buf) /*!< in: buffer where to sprintf */
+{
+#ifdef __WIN__
+	SYSTEMTIME cal_tm;
+
+	GetLocalTime(&cal_tm);
+
+	sprintf(buf, "%02d%02d%02d %2d:%02d:%02d",
+		(int) cal_tm.wYear % 100,
+		(int) cal_tm.wMonth,
+		(int) cal_tm.wDay,
+		(int) cal_tm.wHour,
+		(int) cal_tm.wMinute,
+		(int) cal_tm.wSecond);
+#else
+	struct tm* cal_tm_ptr;
+	time_t	   tm;
+
+#ifdef HAVE_LOCALTIME_R
+	struct tm  cal_tm;
+	time(&tm);
+	localtime_r(&tm, &cal_tm);
+	cal_tm_ptr = &cal_tm;
+#else
+	time(&tm);
+	cal_tm_ptr = localtime(&tm);
+#endif
+	sprintf(buf, "%02d%02d%02d %2d:%02d:%02d",
+		cal_tm_ptr->tm_year % 100,
+		cal_tm_ptr->tm_mon + 1,
+		cal_tm_ptr->tm_mday,
+		cal_tm_ptr->tm_hour,
+		cal_tm_ptr->tm_min,
+		cal_tm_ptr->tm_sec);
+#endif
+}
+
+#ifdef UNIV_HOTBACKUP
+/**********************************************************//**
+Sprintfs a timestamp to a buffer with no spaces and with ':' characters
+replaced by '_'. */
+UNIV_INTERN
+void
+ut_sprintf_timestamp_without_extra_chars(
+/*=====================================*/
+	char*	buf) /*!< in: buffer where to sprintf */
+{
+#ifdef __WIN__
+	SYSTEMTIME cal_tm;
+
+	GetLocalTime(&cal_tm);
+
+	sprintf(buf, "%02d%02d%02d_%2d_%02d_%02d",
+		(int) cal_tm.wYear % 100,
+		(int) cal_tm.wMonth,
+		(int) cal_tm.wDay,
+		(int) cal_tm.wHour,
+		(int) cal_tm.wMinute,
+		(int) cal_tm.wSecond);
+#else
+	struct tm* cal_tm_ptr;
+	time_t	   tm;
+
+#ifdef HAVE_LOCALTIME_R
+	struct tm  cal_tm;
+	time(&tm);
+	localtime_r(&tm, &cal_tm);
+	cal_tm_ptr = &cal_tm;
+#else
+	time(&tm);
+	cal_tm_ptr = localtime(&tm);
+#endif
+	sprintf(buf, "%02d%02d%02d_%2d_%02d_%02d",
+		cal_tm_ptr->tm_year % 100,
+		cal_tm_ptr->tm_mon + 1,
+		cal_tm_ptr->tm_mday,
+		cal_tm_ptr->tm_hour,
+		cal_tm_ptr->tm_min,
+		cal_tm_ptr->tm_sec);
+#endif
+}
+
+/**********************************************************//**
+Returns current year, month, day. */
+UNIV_INTERN
+void
+ut_get_year_month_day(
+/*==================*/
+	ulint*	year,	/*!< out: current year */
+	ulint*	month,	/*!< out: month */
+	ulint*	day)	/*!< out: day */
+{
+#ifdef __WIN__
+	SYSTEMTIME cal_tm;
+
+	GetLocalTime(&cal_tm);
+
+	*year = (ulint) cal_tm.wYear;
+	*month = (ulint) cal_tm.wMonth;
+	*day = (ulint) cal_tm.wDay;
+#else
+	struct tm* cal_tm_ptr;
+	time_t	   tm;
+
+#ifdef HAVE_LOCALTIME_R
+	struct tm  cal_tm;
+	time(&tm);
+	localtime_r(&tm, &cal_tm);
+	cal_tm_ptr = &cal_tm;
+#else
+	time(&tm);
+	cal_tm_ptr = localtime(&tm);
+#endif
+	*year = (ulint) cal_tm_ptr->tm_year + 1900;
+	*month = (ulint) cal_tm_ptr->tm_mon + 1;
+	*day = (ulint) cal_tm_ptr->tm_mday;
+#endif
+}
+#endif /* UNIV_HOTBACKUP */
+
+#ifndef UNIV_HOTBACKUP
+/*************************************************************//**
+Runs an idle loop on CPU. The argument gives the desired delay
+in microseconds on 100 MHz Pentium + Visual C++.
+@return	dummy value */
+UNIV_INTERN
+ulint
+ut_delay(
+/*=====*/
+	ulint	delay)	/*!< in: delay in microseconds on 100 MHz Pentium */
+{
+	ulint	i, j;
+
+	j = 0;
+
+	for (i = 0; i < delay * 50; i++) {
+		j += i;
+		UT_RELAX_CPU();
+	}
+
+	if (ut_always_false) {
+		ut_always_false = (ibool) j;
+	}
+
+	return(j);
+}
+#endif /* !UNIV_HOTBACKUP */
+
+/*************************************************************//**
+Prints the contents of a memory buffer in hex and ascii. */
+UNIV_INTERN
+void
+ut_print_buf(
+/*=========*/
+	FILE*		file,	/*!< in: file where to print */
+	const void*	buf,	/*!< in: memory buffer */
+	ulint		len)	/*!< in: length of the buffer */
+{
+	const byte*	data;
+	ulint		i;
+
+	UNIV_MEM_ASSERT_RW(buf, len);
+
+	fprintf(file, " len %lu; hex ", len);
+
+	for (data = (const byte*) buf, i = 0; i < len; i++) {
+		fprintf(file, "%02lx", (ulong)*data++);
+	}
+
+	fputs("; asc ", file);
+
+	data = (const byte*) buf;
+
+	for (i = 0; i < len; i++) {
+		int	c = (int) *data++;
+		putc(isprint(c) ? c : ' ', file);
+	}
+
+	putc(';', file);
+}
+
+/**********************************************************************//**
+Sort function for ulint arrays. */
+UNIV_INTERN
+void
+ut_ulint_sort(
+/*==========*/
+	ulint*	arr,		/*!< in/out: array to sort */
+	ulint*	aux_arr,	/*!< in/out: aux array to use in sort */
+	ulint	low,		/*!< in: lower bound */
+	ulint	high)		/*!< in: upper bound */
+{
+	UT_SORT_FUNCTION_BODY(ut_ulint_sort, arr, aux_arr, low, high,
+			      ut_ulint_cmp);
+}
+
+/*************************************************************//**
+Calculates fast the number rounded up to the nearest power of 2.
+@return	first power of 2 which is >= n */
+UNIV_INTERN
+ulint
+ut_2_power_up(
+/*==========*/
+	ulint	n)	/*!< in: number != 0 */
+{
+	ulint	res;
+
+	res = 1;
+
+	ut_ad(n > 0);
+
+	while (res < n) {
+		res = res * 2;
+	}
+
+	return(res);
+}
+
+/**********************************************************************//**
+Outputs a NUL-terminated file name, quoted with apostrophes. */
+UNIV_INTERN
+void
+ut_print_filename(
+/*==============*/
+	FILE*		f,	/*!< in: output stream */
+	const char*	name)	/*!< in: name to print */
+{
+	putc('\'', f);
+	for (;;) {
+		int	c = *name++;
+		switch (c) {
+		case 0:
+			goto done;
+		case '\'':
+			putc(c, f);
+			/* fall through */
+		default:
+			putc(c, f);
+		}
+	}
+done:
+	putc('\'', f);
+}
+#ifndef UNIV_HOTBACKUP
+/**********************************************************************//**
+Outputs a fixed-length string, quoted as an SQL identifier.
+If the string contains a slash '/', the string will be
+output as two identifiers separated by a period (.),
+as in SQL database_name.identifier. */
+UNIV_INTERN
+void
+ut_print_name(
+/*==========*/
+	FILE*		f,	/*!< in: output stream */
+	const trx_t*	trx,	/*!< in: transaction */
+	ibool		table_id,/*!< in: TRUE=print a table name,
+				FALSE=print other identifier */
+	const char*	name)	/*!< in: name to print */
+{
+	ut_print_namel(f, trx, table_id, name, strlen(name));
+}
+
+/**********************************************************************//**
+Outputs a fixed-length string, quoted as an SQL identifier.
+If the string contains a slash '/', the string will be
+output as two identifiers separated by a period (.),
+as in SQL database_name.identifier. */
+UNIV_INTERN
+void
+ut_print_namel(
+/*===========*/
+	FILE*		f,	/*!< in: output stream */
+	const trx_t*	trx,	/*!< in: transaction (NULL=no quotes) */
+	ibool		table_id,/*!< in: TRUE=print a table name,
+				FALSE=print other identifier */
+	const char*	name,	/*!< in: name to print */
+	ulint		namelen)/*!< in: length of name */
+{
+	/* 2 * NAME_LEN for database and table name,
+	and some slack for the #mysql50# prefix and quotes */
+	char		buf[3 * NAME_LEN];
+	const char*	bufend;
+
+	bufend = innobase_convert_name(buf, sizeof buf,
+				       name, namelen,
+				       trx ? trx->mysql_thd : NULL,
+				       table_id);
+
+	fwrite(buf, 1, bufend - buf, f);
+}
+
+/**********************************************************************//**
+Formats a table or index name, quoted as an SQL identifier. If the name
+contains a slash '/', the result will contain two identifiers separated by
+a period (.), as in SQL database_name.identifier.
+@return pointer to 'formatted' */
+UNIV_INTERN
+char*
+ut_format_name(
+/*===========*/
+	const char*	name,		/*!< in: table or index name, must be
+					'\0'-terminated */
+	ibool		is_table,	/*!< in: if TRUE then 'name' is a table
+					name */
+	char*		formatted,	/*!< out: formatted result, will be
+					'\0'-terminated */
+	ulint		formatted_size)	/*!< out: no more than this number of
+					bytes will be written to 'formatted' */
+{
+	switch (formatted_size) {
+	case 1:
+		formatted[0] = '\0';
+		/* FALL-THROUGH */
+	case 0:
+		return(formatted);
+	}
+
+	char*	end;
+
+	end = innobase_convert_name(formatted, formatted_size,
+				    name, strlen(name), NULL, is_table);
+
+	/* If the space in 'formatted' was completely used, then sacrifice
+	the last character in order to write '\0' at the end. */
+	if ((ulint) (end - formatted) == formatted_size) {
+		end--;
+	}
+
+	ut_a((ulint) (end - formatted) < formatted_size);
+
+	*end = '\0';
+
+	return(formatted);
+}
+
+/**********************************************************************//**
+Catenate files. */
+UNIV_INTERN
+void
+ut_copy_file(
+/*=========*/
+	FILE*	dest,	/*!< in: output file */
+	FILE*	src)	/*!< in: input file to be appended to output */
+{
+	long	len = ftell(src);
+	char	buf[4096];
+
+	rewind(src);
+	do {
+		size_t	maxs = len < (long) sizeof buf
+			? (size_t) len
+			: sizeof buf;
+		size_t	size = fread(buf, 1, maxs, src);
+		fwrite(buf, 1, size, dest);
+		len -= (long) size;
+		if (size < maxs) {
+			break;
+		}
+	} while (len > 0);
+}
+#endif /* !UNIV_HOTBACKUP */
+
+#ifdef __WIN__
+# include <stdarg.h>
+/**********************************************************************//**
+A substitute for vsnprintf(3), formatted output conversion into
+a limited buffer. Note: this function DOES NOT return the number of
+characters that would have been printed if the buffer was unlimited because
+VC's _vsnprintf() returns -1 in this case and we would need to call
+_vscprintf() in addition to estimate that but we would need another copy
+of "ap" for that and VC does not provide va_copy(). */
+UNIV_INTERN
+void
+ut_vsnprintf(
+/*=========*/
+	char*		str,	/*!< out: string */
+	size_t		size,	/*!< in: str size */
+	const char*	fmt,	/*!< in: format */
+	va_list		ap)	/*!< in: format values */
+{
+	_vsnprintf(str, size, fmt, ap);
+	str[size - 1] = '\0';
+}
+
+/**********************************************************************//**
+A substitute for snprintf(3), formatted output conversion into
+a limited buffer.
+@return number of characters that would have been printed if the size
+were unlimited, not including the terminating '\0'. */
+UNIV_INTERN
+int
+ut_snprintf(
+/*========*/
+	char*		str,	/*!< out: string */
+	size_t		size,	/*!< in: str size */
+	const char*	fmt,	/*!< in: format */
+	...)			/*!< in: format values */
+{
+	int	res;
+	va_list	ap1;
+	va_list	ap2;
+
+	va_start(ap1, fmt);
+	va_start(ap2, fmt);
+
+	res = _vscprintf(fmt, ap1);
+	ut_a(res != -1);
+
+	if (size > 0) {
+		_vsnprintf(str, size, fmt, ap2);
+
+		if ((size_t) res >= size) {
+			str[size - 1] = '\0';
+		}
+	}
+
+	va_end(ap1);
+	va_end(ap2);
+
+	return(res);
+}
+#endif /* __WIN__ */
+
+/*************************************************************//**
+Convert an error number to a human readable text message. The
+returned string is static and should not be freed or modified.
+@return	string, describing the error */
+UNIV_INTERN
+const char*
+ut_strerr(
+/*======*/
+	dberr_t	num)	/*!< in: error number */
+{
+	switch (num) {
+	case DB_SUCCESS:
+		return("Success");
+	case DB_SUCCESS_LOCKED_REC:
+		return("Success, record lock created");
+	case DB_ERROR:
+		return("Generic error");
+	case DB_READ_ONLY:
+		return("Read only transaction");
+	case DB_INTERRUPTED:
+		return("Operation interrupted");
+	case DB_OUT_OF_MEMORY:
+		return("Cannot allocate memory");
+	case DB_OUT_OF_FILE_SPACE:
+		return("Out of disk space");
+	case DB_LOCK_WAIT:
+		return("Lock wait");
+	case DB_DEADLOCK:
+		return("Deadlock");
+	case DB_ROLLBACK:
+		return("Rollback");
+	case DB_DUPLICATE_KEY:
+		return("Duplicate key");
+	case DB_QUE_THR_SUSPENDED:
+		return("The queue thread has been suspended");
+	case DB_MISSING_HISTORY:
+		return("Required history data has been deleted");
+	case DB_CLUSTER_NOT_FOUND:
+		return("Cluster not found");
+	case DB_TABLE_NOT_FOUND:
+		return("Table not found");
+	case DB_MUST_GET_MORE_FILE_SPACE:
+		return("More file space needed");
+	case DB_TABLE_IS_BEING_USED:
+		return("Table is being used");
+	case DB_TOO_BIG_RECORD:
+		return("Record too big");
+	case DB_TOO_BIG_INDEX_COL:
+		return("Index columns size too big");
+	case DB_LOCK_WAIT_TIMEOUT:
+		return("Lock wait timeout");
+	case DB_NO_REFERENCED_ROW:
+		return("Referenced key value not found");
+	case DB_ROW_IS_REFERENCED:
+		return("Row is referenced");
+	case DB_CANNOT_ADD_CONSTRAINT:
+		return("Cannot add constraint");
+	case DB_CORRUPTION:
+		return("Data structure corruption");
+	case DB_CANNOT_DROP_CONSTRAINT:
+		return("Cannot drop constraint");
+	case DB_NO_SAVEPOINT:
+		return("No such savepoint");
+	case DB_TABLESPACE_EXISTS:
+		return("Tablespace already exists");
+	case DB_TABLESPACE_DELETED:
+		return("Tablespace deleted or being deleted");
+	case DB_TABLESPACE_NOT_FOUND:
+		return("Tablespace not found");
+	case DB_LOCK_TABLE_FULL:
+		return("Lock structs have exhausted the buffer pool");
+	case DB_FOREIGN_DUPLICATE_KEY:
+		return("Foreign key activated with duplicate keys");
+	case DB_FOREIGN_EXCEED_MAX_CASCADE:
+		return("Foreign key cascade delete/update exceeds max depth");
+	case DB_TOO_MANY_CONCURRENT_TRXS:
+		return("Too many concurrent transactions");
+	case DB_UNSUPPORTED:
+		return("Unsupported");
+	case DB_INVALID_NULL:
+		return("NULL value encountered in NOT NULL column");
+	case DB_STATS_DO_NOT_EXIST:
+		return("Persistent statistics do not exist");
+	case DB_FAIL:
+		return("Failed, retry may succeed");
+	case DB_OVERFLOW:
+		return("Overflow");
+	case DB_UNDERFLOW:
+		return("Underflow");
+	case DB_STRONG_FAIL:
+		return("Failed, retry will not succeed");
+	case DB_ZIP_OVERFLOW:
+		return("Zip overflow");
+	case DB_RECORD_NOT_FOUND:
+		return("Record not found");
+	case DB_CHILD_NO_INDEX:
+		return("No index on referencing keys in referencing table");
+	case DB_PARENT_NO_INDEX:
+		return("No index on referenced keys in referenced table");
+	case DB_FTS_INVALID_DOCID:
+		return("FTS Doc ID cannot be zero");
+	case DB_INDEX_CORRUPT:
+		return("Index corrupted");
+	case DB_UNDO_RECORD_TOO_BIG:
+		return("Undo record too big");
+	case DB_END_OF_INDEX:
+		return("End of index");
+	case DB_IO_ERROR:
+		return("I/O error");
+	case DB_TABLE_IN_FK_CHECK:
+		return("Table is being used in foreign key check");
+	case DB_DATA_MISMATCH:
+		return("data mismatch");
+	case DB_SCHEMA_NOT_LOCKED:
+		return("schema not locked");
+	case DB_NOT_FOUND:
+		return("not found");
+	case DB_ONLINE_LOG_TOO_BIG:
+		return("Log size exceeded during online index creation");
+	case DB_DICT_CHANGED:
+		return("Table dictionary has changed");
+	case DB_IDENTIFIER_TOO_LONG:
+		return("Identifier name is too long");
+	case DB_FTS_EXCEED_RESULT_CACHE_LIMIT:
+		return("FTS query exceeds result cache limit");
+	case DB_TEMP_FILE_WRITE_FAILURE:
+		return("Temp file write failure");
+	case DB_FTS_TOO_MANY_WORDS_IN_PHRASE:
+		return("Too many words in a FTS phrase or proximity search");
+	case DB_TOO_BIG_FOR_REDO:
+		return("BLOB record length is greater than 10%% of redo log");
+
+	/* do not add default: in order to produce a warning if new code
+	is added to the enum but not added here */
+	}
+
+	/* we abort here because if unknown error code is given, this could
+	mean that memory corruption has happened and someone's error-code
+	variable has been overwritten with bogus data */
+	ut_error;
+
+	/* NOT REACHED */
+	return("Unknown error");
+}
+#endif /* !UNIV_INNOCHECKSUM */
diff --git a/storage/innobase/ut/ut0vec.cc b/storage/innobase/ut/ut0vec.cc
new file mode 100644
index 00000000000..5842d9f1c0e
--- /dev/null
+++ b/storage/innobase/ut/ut0vec.cc
@@ -0,0 +1,78 @@
+/*****************************************************************************
+
+Copyright (c) 2006, 2011, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+/*******************************************************************//**
+@file ut/ut0vec.cc
+A vector of pointers to data items
+
+Created 4/6/2006 Osku Salerma
+************************************************************************/
+
+#include "ut0vec.h"
+#ifdef UNIV_NONINL
+#include "ut0vec.ic"
+#endif
+#include "mem0mem.h"
+
+/********************************************************************
+Create a new vector with the given initial size. */
+UNIV_INTERN
+ib_vector_t*
+ib_vector_create(
+/*=============*/
+					/* out: vector */
+	ib_alloc_t*	allocator,	/* in: vector allocator */
+	ulint		sizeof_value,	/* in: size of data item */
+	ulint		size)		/* in: initial size */
+{
+	ib_vector_t*	vec;
+
+	ut_a(size > 0);
+
+	vec = static_cast<ib_vector_t*>(
+		allocator->mem_malloc(allocator, sizeof(*vec)));
+
+	vec->used = 0;
+	vec->total = size;
+	vec->allocator = allocator;
+	vec->sizeof_value = sizeof_value;
+
+	vec->data = static_cast<void*>(
+		allocator->mem_malloc(allocator, vec->sizeof_value * size));
+
+	return(vec);
+}
+
+/********************************************************************
+Resize the vector, currently the vector can only grow and we
+expand the number of elements it can hold by 2 times. */
+UNIV_INTERN
+void
+ib_vector_resize(
+/*=============*/
+	ib_vector_t*	vec)		/* in: vector */
+{
+	ulint		new_total = vec->total * 2;
+	ulint		old_size = vec->used * vec->sizeof_value;
+	ulint		new_size = new_total * vec->sizeof_value;
+
+	vec->data = static_cast<void*>(vec->allocator->mem_resize(
+		vec->allocator, vec->data, old_size, new_size));
+
+	vec->total = new_total;
+}
diff --git a/storage/innobase/ut/ut0wqueue.cc b/storage/innobase/ut/ut0wqueue.cc
new file mode 100644
index 00000000000..d1ba36b3b00
--- /dev/null
+++ b/storage/innobase/ut/ut0wqueue.cc
@@ -0,0 +1,175 @@
+/*****************************************************************************
+
+Copyright (c) 2006, 2011, Oracle and/or its affiliates. All Rights Reserved.
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
+
+*****************************************************************************/
+
+#include "ut0wqueue.h"
+
+/*******************************************************************//**
+@file ut/ut0wqueue.cc
+A work queue
+
+Created 4/26/2006 Osku Salerma
+************************************************************************/
+
+/****************************************************************//**
+Create a new work queue.
+@return	work queue */
+UNIV_INTERN
+ib_wqueue_t*
+ib_wqueue_create(void)
+/*===================*/
+{
+	ib_wqueue_t*	wq = static_cast<ib_wqueue_t*>(mem_alloc(sizeof(*wq)));
+
+	/* Function ib_wqueue_create() has not been used anywhere,
+	not necessary to instrument this mutex */
+	mutex_create(PFS_NOT_INSTRUMENTED, &wq->mutex, SYNC_WORK_QUEUE);
+
+	wq->items = ib_list_create();
+	wq->event = os_event_create();
+
+	return(wq);
+}
+
+/****************************************************************//**
+Free a work queue. */
+UNIV_INTERN
+void
+ib_wqueue_free(
+/*===========*/
+	ib_wqueue_t*	wq)	/*!< in: work queue */
+{
+	mutex_free(&wq->mutex);
+	ib_list_free(wq->items);
+	os_event_free(wq->event);
+
+	mem_free(wq);
+}
+
+/****************************************************************//**
+Add a work item to the queue. */
+UNIV_INTERN
+void
+ib_wqueue_add(
+/*==========*/
+	ib_wqueue_t*	wq,	/*!< in: work queue */
+	void*		item,	/*!< in: work item */
+	mem_heap_t*	heap)	/*!< in: memory heap to use for allocating the
+				list node */
+{
+	mutex_enter(&wq->mutex);
+
+	ib_list_add_last(wq->items, item, heap);
+	os_event_set(wq->event);
+
+	mutex_exit(&wq->mutex);
+}
+
+/****************************************************************//**
+Wait for a work item to appear in the queue.
+@return	work item */
+UNIV_INTERN
+void*
+ib_wqueue_wait(
+/*===========*/
+	ib_wqueue_t*	wq)	/*!< in: work queue */
+{
+	ib_list_node_t*	node;
+
+	for (;;) {
+		os_event_wait(wq->event);
+
+		mutex_enter(&wq->mutex);
+
+		node = ib_list_get_first(wq->items);
+
+		if (node) {
+			ib_list_remove(wq->items, node);
+
+			if (!ib_list_get_first(wq->items)) {
+				/* We must reset the event when the list
+				gets emptied. */
+				os_event_reset(wq->event);
+			}
+
+			break;
+		}
+
+		mutex_exit(&wq->mutex);
+	}
+
+	mutex_exit(&wq->mutex);
+
+	return(node->data);
+}
+
+
+/********************************************************************
+Wait for a work item to appear in the queue for specified time. */
+
+void*
+ib_wqueue_timedwait(
+/*================*/
+					/* out: work item or NULL on timeout*/
+	ib_wqueue_t*	wq,		/* in: work queue */
+	ib_time_t	wait_in_usecs)	/* in: wait time in micro seconds */
+{
+	ib_list_node_t*	node = NULL;
+
+	for (;;) {
+		ulint		error;
+		ib_int64_t	sig_count;
+
+		mutex_enter(&wq->mutex);
+
+		node = ib_list_get_first(wq->items);
+
+		if (node) {
+			ib_list_remove(wq->items, node);
+
+			mutex_exit(&wq->mutex);
+			break;
+		}
+
+		sig_count = os_event_reset(wq->event);
+
+		mutex_exit(&wq->mutex);
+
+		error = os_event_wait_time_low(wq->event,
+					       (ulint) wait_in_usecs,
+					       sig_count);
+
+		if (error == OS_SYNC_TIME_EXCEEDED) {
+			break;
+		}
+	}
+
+	return(node ? node->data : NULL);
+}
+
+/********************************************************************
+Check if queue is empty. */
+
+ibool
+ib_wqueue_is_empty(
+/*===============*/
+					/* out: TRUE if queue empty
+					else FALSE */
+	const ib_wqueue_t*	wq)	/* in: work queue */
+{
+	return(ib_list_is_empty(wq->items));
+}