path: root/innobase/btr/btr0btr.c

/******************************************************
The B-tree

(c) 1994-1996 Innobase Oy

Created 6/2/1994 Heikki Tuuri
*******************************************************/

#include "btr0btr.h"

#ifdef UNIV_NONINL
#include "btr0btr.ic"
#endif

#include "fsp0fsp.h"
#include "page0page.h"
#include "btr0cur.h"
#include "btr0sea.h"
#include "btr0pcur.h"
#include "rem0cmp.h"
#include "lock0lock.h"
#include "ibuf0ibuf.h"

/*
Node pointers
-------------
Leaf pages of a B-tree contain the index records stored in the
tree. On levels n > 0 we store 'node pointers' to pages on level
n - 1. For each page there is exactly one node pointer stored:
thus the our tree is an ordinary B-tree, not a B-link tree.

A node pointer contains a prefix P of an index record. The prefix
is long enough so that it determines an index record uniquely.
The file page number of the child page is added as the last
field. To the child page we can store node pointers or index records
which are >= P in the alphabetical order, but < P1 if there is
a next node pointer on the level, and P1 is its prefix.

If a node pointer with a prefix P points to a non-leaf child, 
then the leftmost record in the child must have the same
prefix P. If it points to a leaf node, the child is not required
to contain any record with a prefix equal to P. The leaf case
is decided this way to allow arbitrary deletions in a leaf node
without touching upper levels of the tree.

We have predefined a special minimum record which we
define as the smallest record in any alphabetical order.
A minimum record is denoted by setting a bit in the record
header. A minimum record acts as the prefix of a node pointer
which points to a leftmost node on any level of the tree.

File page allocation
--------------------
In the root node of a B-tree there are two file segment headers.
The leaf pages of a tree are allocated from one file segment, to
make them consecutive on disk if possible. From the other file segment
we allocate pages for the non-leaf levels of the tree.
*/

/* If this many inserts occur sequentially, it affects page split */
#define BTR_PAGE_SEQ_INSERT_LIMIT	5

/******************************************************************
Creates a new index page to the tree (not the root, and also not
used in page reorganization). */
static
void
btr_page_create(
/*============*/
	page_t*		page,	/* in: page to be created */
	dict_tree_t*	tree,	/* in: index tree */
	mtr_t*		mtr);	/* in: mtr */
/******************************************************************
Allocates a new file page to be used in an index tree. */
static
page_t*
btr_page_alloc(
/*===========*/
					/* out: new allocated page,
					x-latched */
	dict_tree_t*	tree,		/* in: index tree */
	ulint		hint_page_no,	/* in: hint of a good page */
	byte		file_direction,	/* in: direction where a possible
					page split is made */
	ulint		level,		/* in: level where the page is placed
					in the tree */
	mtr_t*		mtr);		/* in: mtr */
/******************************************************************
Frees a file page used in an index tree. */
static
void
btr_page_free(
/*==========*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in, own: page to be freed */	
	mtr_t*		mtr);	/* in: mtr */
/******************************************************************
Sets the child node file address in a node pointer. */
UNIV_INLINE
void
btr_node_ptr_set_child_page_no(
/*===========================*/
	rec_t*	rec,		/* in: node pointer record */
	ulint	page_no,	/* in: child node address */
	mtr_t*	mtr);		/* in: mtr */
/****************************************************************
Returns the upper level node pointer to a page. It is assumed that
mtr holds an x-latch on the tree. */
static
rec_t*
btr_page_get_father_node_ptr(
/*=========================*/
				/* out: pointer to node pointer record */
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page: must contain at least one
				user record */
	mtr_t*		mtr);	/* in: mtr */
/*****************************************************************
Empties an index page. */
static
void
btr_page_empty(
/*===========*/
	page_t*	page,	/* in: page to be emptied */
	mtr_t*	mtr);	/* in: mtr */
/*****************************************************************
Returns TRUE if the insert fits on the appropriate half-page
with the chosen split_rec. */
static
ibool
btr_page_insert_fits(
/*=================*/
					/* out: TRUE if fits */
	btr_cur_t*	cursor,		/* in: cursor at which insert
					should be made */
	rec_t*		split_rec,	/* in: suggestion for first record
					on upper half-page, or NULL if
					tuple should be first */
	dtuple_t*	tuple);		/* in: tuple to insert */	

/******************************************************************
Gets the root node of a tree and x-latches it. */
static
page_t*
btr_root_get(
/*=========*/
				/* out: root page, x-latched */
	dict_tree_t*	tree,	/* in: index tree */
	mtr_t*		mtr)	/* in: mtr */
{
	ulint	space;
	ulint	root_page_no;
	page_t*	root;

	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree), MTR_MEMO_X_LOCK)
	  || mtr_memo_contains(mtr, dict_tree_get_lock(tree), MTR_MEMO_S_LOCK));
	
	space = dict_tree_get_space(tree);
	root_page_no = dict_tree_get_page(tree);

	root = btr_page_get(space, root_page_no, RW_X_LATCH, mtr);
	
	return(root);
}

/*****************************************************************
Gets pointer to the previous user record in the tree. It is assumed that
the caller has appropriate latches on the page and its neighbor. */

rec_t*
btr_get_prev_user_rec(
/*==================*/
			/* out: previous user record, NULL if there is none */
	rec_t*	rec,	/* in: record on leaf level */
	mtr_t*	mtr)	/* in: mtr holding a latch on the page, and if
			needed, also to the previous page */
{
	page_t*	page;
	page_t*	prev_page;
	ulint	prev_page_no;
	rec_t*	prev_rec;
	ulint	space;

	page = buf_frame_align(rec);
	
	if (page_get_infimum_rec(page) != rec) {

		prev_rec = page_rec_get_prev(rec);

		if (page_get_infimum_rec(page) != prev_rec) {

			return(prev_rec);
		}
	}
	
	prev_page_no = btr_page_get_prev(page, mtr);
	space = buf_frame_get_space_id(page);
	
	if (prev_page_no != FIL_NULL) {

		prev_page = buf_page_get_with_no_latch(space, prev_page_no,
									mtr);
		/* The caller must already have a latch to the brother */
		ut_ad((mtr_memo_contains(mtr, buf_block_align(prev_page),
		      				MTR_MEMO_PAGE_S_FIX))
		      || (mtr_memo_contains(mtr, buf_block_align(prev_page),
		      				MTR_MEMO_PAGE_X_FIX)));

		prev_rec = page_rec_get_prev(page_get_supremum_rec(prev_page));

		return(prev_rec);
	}

	return(NULL);
}

/*****************************************************************
Gets pointer to the next user record in the tree. It is assumed that the
caller has appropriate latches on the page and its neighbor. */

rec_t*
btr_get_next_user_rec(
/*==================*/
			/* out: next user record, NULL if there is none */
	rec_t*	rec,	/* in: record on leaf level */
	mtr_t*	mtr)	/* in: mtr holding a latch on the page, and if
			needed, also to the next page */
{
	page_t*	page;
	page_t*	next_page;
	ulint	next_page_no;
	rec_t*	next_rec;
	ulint	space;

	page = buf_frame_align(rec);
	
	if (page_get_supremum_rec(page) != rec) {

		next_rec = page_rec_get_next(rec);

		if (page_get_supremum_rec(page) != next_rec) {

			return(next_rec);
		}
	}
	
	next_page_no = btr_page_get_next(page, mtr);
	space = buf_frame_get_space_id(page);
	
	if (next_page_no != FIL_NULL) {

		next_page = buf_page_get_with_no_latch(space, next_page_no,
									mtr);
		/* The caller must already have a latch to the brother */
		ut_ad((mtr_memo_contains(mtr, buf_block_align(next_page),
		      				MTR_MEMO_PAGE_S_FIX))
		      || (mtr_memo_contains(mtr, buf_block_align(next_page),
		      				MTR_MEMO_PAGE_X_FIX)));

		next_rec = page_rec_get_next(page_get_infimum_rec(next_page));

		return(next_rec);
	}

	return(NULL);
}

/******************************************************************
Creates a new index page to the tree (not the root, and also not used in
page reorganization). */
static
void
btr_page_create(
/*============*/
	page_t*		page,	/* in: page to be created */
	dict_tree_t*	tree,	/* in: index tree */
	mtr_t*		mtr)	/* in: mtr */
{
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	page_create(page, mtr);
	
	btr_page_set_index_id(page, tree->id, mtr);
}

/******************************************************************
Allocates a new file page to be used in an ibuf tree. Takes the page from
the free list of the tree, which must contain pages! */
static
page_t*
btr_page_alloc_for_ibuf(
/*====================*/
				/* out: new allocated page, x-latched */
	dict_tree_t*	tree,	/* in: index tree */
	mtr_t*		mtr)	/* in: mtr */
{
	fil_addr_t	node_addr;
	page_t*		root;
	page_t*		new_page;

	root = btr_root_get(tree, mtr);
	
	node_addr = flst_get_first(root + PAGE_HEADER
					+ PAGE_BTR_IBUF_FREE_LIST, mtr);
	ut_a(node_addr.page != FIL_NULL);

	new_page = buf_page_get(dict_tree_get_space(tree), node_addr.page,
							RW_X_LATCH, mtr);
	buf_page_dbg_add_level(new_page, SYNC_TREE_NODE_NEW);

	flst_remove(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST,
		    new_page + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST_NODE,
									mtr);
	ut_ad(flst_validate(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST, mtr));

	return(new_page);
}

/******************************************************************
Allocates a new file page to be used in an index tree. NOTE: we assume
that the caller has made the reservation for free extents! */
static
page_t*
btr_page_alloc(
/*===========*/
					/* out: new allocated page, x-latched */
	dict_tree_t*	tree,		/* in: index tree */
	ulint		hint_page_no,	/* in: hint of a good page */
	byte		file_direction,	/* in: direction where a possible
					page split is made */
	ulint		level,		/* in: level where the page is placed
					in the tree */
	mtr_t*		mtr)		/* in: mtr */
{
	fseg_header_t*	seg_header;
	page_t*		root;
	page_t*		new_page;
	ulint		new_page_no;

	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK));
	if (tree->type & DICT_IBUF) {

		return(btr_page_alloc_for_ibuf(tree, mtr));
	}

	root = btr_root_get(tree, mtr);
		
	if (level == 0) {
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
	} else {
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;
	}

	/* Parameter TRUE below states that the caller has made the
	reservation for free extents, and thus we know that a page can
	be allocated: */
	
	new_page_no = fseg_alloc_free_page_general(seg_header, hint_page_no,
						file_direction, TRUE, mtr);
	ut_a(new_page_no != FIL_NULL);

	new_page = buf_page_get(dict_tree_get_space(tree), new_page_no,
							RW_X_LATCH, mtr);
	buf_page_dbg_add_level(new_page, SYNC_TREE_NODE_NEW);
							
	return(new_page);
}	

/******************************************************************
Gets the number of pages in a B-tree. */

ulint
btr_get_size(
/*=========*/
				/* out: number of pages */
	dict_index_t*	index,	/* in: index */
	ulint		flag)	/* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
{
	fseg_header_t*	seg_header;
	page_t*		root;
	ulint		n;
	ulint		dummy;
	mtr_t		mtr;

	mtr_start(&mtr);

	mtr_s_lock(dict_tree_get_lock(index->tree), &mtr);

	root = btr_root_get(index->tree, &mtr);
		
	if (flag == BTR_N_LEAF_PAGES) {
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
		
		fseg_n_reserved_pages(seg_header, &n, &mtr);
		
	} else if (flag == BTR_TOTAL_SIZE) {
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;

		n = fseg_n_reserved_pages(seg_header, &dummy, &mtr);
		
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
		
		n += fseg_n_reserved_pages(seg_header, &dummy, &mtr);		
	} else {
		ut_a(0);
	}

	mtr_commit(&mtr);

	return(n);
}	

/******************************************************************
Frees a page used in an ibuf tree. Puts the page to the free list of the
ibuf tree. */
static
void
btr_page_free_for_ibuf(
/*===================*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page to be freed, x-latched */	
	mtr_t*		mtr)	/* in: mtr */
{
	page_t*		root;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	root = btr_root_get(tree, mtr);
	
	flst_add_first(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST,
		       page + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST_NODE, mtr);

	ut_ad(flst_validate(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST, mtr));
}

/******************************************************************
Frees a file page used in an index tree. */
static
void
btr_page_free(
/*==========*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page to be freed, x-latched */	
	mtr_t*		mtr)	/* in: mtr */
{
	fseg_header_t*	seg_header;
	page_t*		root;
	ulint		space;
	ulint		page_no;
	ulint		level;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	/* The page gets invalid for optimistic searches: increment the frame
	modify clock */

	buf_frame_modify_clock_inc(page);
	
	if (tree->type & DICT_IBUF) {

		btr_page_free_for_ibuf(tree, page, mtr);

		return;
	}

	root = btr_root_get(tree, mtr);

	level = btr_page_get_level(page, mtr);
	
	if (level == 0) {
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
	} else {
		seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;
	}

	space = buf_frame_get_space_id(page);
	page_no = buf_frame_get_page_no(page);
	
	fseg_free_page(seg_header, space, page_no, mtr);
}	

/******************************************************************
Sets the child node file address in a node pointer. */
UNIV_INLINE
void
btr_node_ptr_set_child_page_no(
/*===========================*/
	rec_t*	rec,		/* in: node pointer record */
	ulint	page_no,	/* in: child node address */
	mtr_t*	mtr)		/* in: mtr */
{
	ulint	n_fields;
	byte*	field;
	ulint	len;

	ut_ad(0 < btr_page_get_level(buf_frame_align(rec), mtr));
	
	n_fields = rec_get_n_fields(rec);

	/* The child address is in the last field */	
	field = rec_get_nth_field(rec, n_fields - 1, &len);

	ut_ad(len == 4);
	
	mlog_write_ulint(field, page_no, MLOG_4BYTES, mtr);
}

/****************************************************************
Returns the child page of a node pointer and x-latches it. */
static
page_t*
btr_node_ptr_get_child(
/*===================*/
	 			/* out: child page, x-latched */
	rec_t*	node_ptr,	/* in: node pointer */
	mtr_t*	mtr)		/* in: mtr */
{
	ulint	page_no;
	ulint	space;
	page_t*	page;
	
	space = buf_frame_get_space_id(node_ptr);
	page_no = btr_node_ptr_get_child_page_no(node_ptr);

	page = btr_page_get(space, page_no, RW_X_LATCH, mtr);
	
	return(page);
}

/****************************************************************
Returns the upper level node pointer to a page. It is assumed that mtr holds
an x-latch on the tree. */
static
rec_t*
btr_page_get_father_for_rec(
/*========================*/
				/* out: pointer to node pointer record,
				its page x-latched */
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page: must contain at least one
				user record */
	rec_t*		user_rec,/* in: user_record on page */
	mtr_t*		mtr)	/* in: mtr */
{
	mem_heap_t*	heap;
	dtuple_t*	tuple;
	btr_cur_t	cursor;
	rec_t*		node_ptr;

	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK));
	ut_ad(user_rec != page_get_supremum_rec(page));
	ut_ad(user_rec != page_get_infimum_rec(page));
	
	ut_ad(dict_tree_get_page(tree) != buf_frame_get_page_no(page));

	heap = mem_heap_create(100);

	tuple = dict_tree_build_node_ptr(tree, user_rec, 0, heap);

	/* In the following, we choose just any index from the tree as the
	first parameter for btr_cur_search_to_nth_level. */
	
	btr_cur_search_to_nth_level(UT_LIST_GET_FIRST(tree->tree_indexes),
				btr_page_get_level(page, mtr) + 1,
				tuple, PAGE_CUR_LE,
				BTR_CONT_MODIFY_TREE, &cursor, 0, mtr);

	node_ptr = btr_cur_get_rec(&cursor);

	ut_ad(btr_node_ptr_get_child_page_no(node_ptr) ==
						buf_frame_get_page_no(page));
	mem_heap_free(heap);

	return(node_ptr);
}

/****************************************************************
Returns the upper level node pointer to a page. It is assumed that
mtr holds an x-latch on the tree. */
static
rec_t*
btr_page_get_father_node_ptr(
/*=========================*/
				/* out: pointer to node pointer record */
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page: must contain at least one
				user record */
	mtr_t*		mtr)	/* in: mtr */
{
	return(btr_page_get_father_for_rec(tree, page,
		page_rec_get_next(page_get_infimum_rec(page)), mtr));
}

/****************************************************************
Creates the root node for a new index tree. */

ulint
btr_create(
/*=======*/
			/* out: page number of the created root, FIL_NULL if
			did not succeed */
	ulint	type,	/* in: type of the index */
	ulint	space,	/* in: space where created */
	dulint	index_id,/* in: index id */
	mtr_t*	mtr)	/* in: mini-transaction handle */
{
	ulint		page_no;
	buf_frame_t*	ibuf_hdr_frame;
	buf_frame_t*	frame;
	page_t*		page;

	/* Create the two new segments (one, in the case of an ibuf tree) for
	the index tree; the segment headers are put on the allocated root page
	(for an ibuf tree, not in the root, but on a separate ibuf header
	page) */

	if (type & DICT_IBUF) {
		/* Allocate first the ibuf header page */
		ibuf_hdr_frame = fseg_create(space, 0,
				IBUF_HEADER + IBUF_TREE_SEG_HEADER, mtr);

		buf_page_dbg_add_level(ibuf_hdr_frame, SYNC_TREE_NODE_NEW);

		ut_ad(buf_frame_get_page_no(ibuf_hdr_frame)
 						== IBUF_HEADER_PAGE_NO);
		/* Allocate then the next page to the segment: it will be the
 		tree root page */

 		page_no = fseg_alloc_free_page(
				ibuf_hdr_frame + IBUF_HEADER
 				+ IBUF_TREE_SEG_HEADER, IBUF_TREE_ROOT_PAGE_NO,
				FSP_UP, mtr);
		ut_ad(page_no == IBUF_TREE_ROOT_PAGE_NO);

		frame = buf_page_get(space, page_no, RW_X_LATCH, mtr);
	} else {
		frame = fseg_create(space, 0, PAGE_HEADER + PAGE_BTR_SEG_TOP,
									mtr);
	}
	
	if (frame == NULL) {

		return(FIL_NULL);
	}

	page_no = buf_frame_get_page_no(frame);
	
	buf_page_dbg_add_level(frame, SYNC_TREE_NODE_NEW);

	if (type & DICT_IBUF) {
		/* It is an insert buffer tree: initialize the free list */

		ut_ad(page_no == IBUF_TREE_ROOT_PAGE_NO);
		
		flst_init(frame + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST, mtr);
	} else {	
		/* It is a non-ibuf tree: create a file segment for leaf
		pages */
		fseg_create(space, page_no, PAGE_HEADER + PAGE_BTR_SEG_LEAF,
									mtr);
		/* The fseg create acquires a second latch on the page,
		therefore we must declare it: */
		buf_page_dbg_add_level(frame, SYNC_TREE_NODE_NEW);
	}
	
	/* Create a new index page on the the allocated segment page */
	page = page_create(frame, mtr);

	/* Set the index id of the page */
	btr_page_set_index_id(page, index_id, mtr);

	/* Set the level of the new index page */
	btr_page_set_level(page, 0, mtr);
	
	/* Set the next node and previous node fields */
	btr_page_set_next(page, FIL_NULL, mtr);
	btr_page_set_prev(page, FIL_NULL, mtr);

	/* We reset the free bits for the page to allow creation of several
	trees in the same mtr, otherwise the latch on a bitmap page would
	prevent it because of the latching order */
	
	ibuf_reset_free_bits_with_type(type, page);

	/* In the following assertion we test that two records of maximum
	allowed size fit on the root page: this fact is needed to ensure
	correctness of split algorithms */

	ut_ad(page_get_max_insert_size(page, 2) > 2 * BTR_PAGE_MAX_REC_SIZE);

	return(page_no);
}

/****************************************************************
Frees a B-tree except the root page, which MUST be freed after this
by calling btr_free_root. */

void
btr_free_but_not_root(
/*==================*/
	ulint	space,		/* in: space where created */
	ulint	root_page_no)	/* in: root page number */
{
	ibool	finished;
	page_t*	root;
	mtr_t	mtr;

leaf_loop:	
	mtr_start(&mtr);
	
	root = btr_page_get(space, root_page_no, RW_X_LATCH, &mtr);	

	/* NOTE: page hash indexes are dropped when a page is freed inside
	fsp0fsp. */

	finished = fseg_free_step(
				root + PAGE_HEADER + PAGE_BTR_SEG_LEAF, &mtr);
	mtr_commit(&mtr);

	if (!finished) {

		goto leaf_loop;
	}
top_loop:
	mtr_start(&mtr);
	
	root = btr_page_get(space, root_page_no, RW_X_LATCH, &mtr);	

	finished = fseg_free_step_not_header(
				root + PAGE_HEADER + PAGE_BTR_SEG_TOP, &mtr);
	mtr_commit(&mtr);

	if (!finished) {

		goto top_loop;
	}	
}

/****************************************************************
Frees the B-tree root page. Other tree MUST already have been freed. */

void
btr_free_root(
/*==========*/
	ulint	space,		/* in: space where created */
	ulint	root_page_no,	/* in: root page number */
	mtr_t*	mtr)		/* in: a mini-transaction which has already
				been started */
{
	ibool	finished;
	page_t*	root;

	root = btr_page_get(space, root_page_no, RW_X_LATCH, mtr);

	btr_search_drop_page_hash_index(root);	
top_loop:	
	finished = fseg_free_step(
				root + PAGE_HEADER + PAGE_BTR_SEG_TOP, mtr);
	if (!finished) {

		goto top_loop;
	}	
}

/*****************************************************************
Reorganizes an index page. */

void
btr_page_reorganize_low(
/*====================*/
	ibool	low,	/* in: TRUE if locks should not be updated, i.e.,
			there cannot exist locks on the page */
	page_t*	page,	/* in: page to be reorganized */
	mtr_t*	mtr)	/* in: mtr */
{
	page_t*	new_page;
	ulint	log_mode;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	/* Write the log record */
	mlog_write_initial_log_record(page, MLOG_PAGE_REORGANIZE, mtr);

	/* Turn logging off */
	log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);

	new_page = buf_frame_alloc();

	/* Copy the old page to temporary space */
	buf_frame_copy(new_page, page);

	btr_search_drop_page_hash_index(page);

	/* Recreate the page: note that global data on page (possible
	segment headers, next page-field, etc.) is preserved intact */

	page_create(page, mtr);
	
	/* Copy the records from the temporary space to the recreated page;
	do not copy the lock bits yet */

	page_copy_rec_list_end_no_locks(page, new_page,
					page_get_infimum_rec(new_page), mtr);
	/* Copy max trx id to recreated page */
	page_set_max_trx_id(page, page_get_max_trx_id(new_page));
	
	if (!low) {
		/* Update the record lock bitmaps */
		lock_move_reorganize_page(page, new_page);
	}

	buf_frame_free(new_page);

	/* Restore logging mode */
	mtr_set_log_mode(mtr, log_mode);
}

/*****************************************************************
Reorganizes an index page. */

void
btr_page_reorganize(
/*================*/
	page_t*	page,	/* in: page to be reorganized */
	mtr_t*	mtr)	/* in: mtr */
{
	btr_page_reorganize_low(FALSE, page, mtr);
}

/***************************************************************
Parses a redo log record of reorganizing a page. */

byte*
btr_parse_page_reorganize(
/*======================*/
			/* out: end of log record or NULL */
	byte*	ptr,	/* in: buffer */
	byte*	end_ptr,/* in: buffer end */
	page_t*	page,	/* in: page or NULL */
	mtr_t*	mtr)	/* in: mtr or NULL */
{
	ut_ad(ptr && end_ptr);

	/* The record is empty, except for the record initial part */

	if (page) {
		btr_page_reorganize_low(TRUE, page, mtr);
	}

	return(ptr);
}

/*****************************************************************
Empties an index page. */
static
void
btr_page_empty(
/*===========*/
	page_t*	page,	/* in: page to be emptied */
	mtr_t*	mtr)	/* in: mtr */
{
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	btr_search_drop_page_hash_index(page);

	/* Recreate the page: note that global data on page (possible
	segment headers, next page-field, etc.) is preserved intact */

	page_create(page, mtr);
}

/*****************************************************************
Makes tree one level higher by splitting the root, and inserts
the tuple. It is assumed that mtr contains an x-latch on the tree.
NOTE that the operation of this function must always succeed,
we cannot reverse it: therefore enough free disk space must be
guaranteed to be available before this function is called. */

rec_t*
btr_root_raise_and_insert(
/*======================*/
				/* out: inserted record */
	btr_cur_t*	cursor,	/* in: cursor at which to insert: must be
				on the root page; when the function returns,
				the cursor is positioned on the predecessor
				of the inserted record */
	dtuple_t*	tuple,	/* in: tuple to insert */
	mtr_t*		mtr)	/* in: mtr */
{
	dict_tree_t*	tree;
	page_t*		root;
	page_t*		new_page;
	ulint		new_page_no;
	rec_t*		rec;
	mem_heap_t*	heap;
	dtuple_t*	node_ptr;
	ulint		level;	
	rec_t*		node_ptr_rec;
	page_cur_t*	page_cursor;
	
	root = btr_cur_get_page(cursor);
	tree = btr_cur_get_tree(cursor);

	ut_ad(dict_tree_get_page(tree) == buf_frame_get_page_no(root));
	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK));
	ut_ad(mtr_memo_contains(mtr, buf_block_align(root),
			      				MTR_MEMO_PAGE_X_FIX));
	btr_search_drop_page_hash_index(root);

	/* Allocate a new page to the tree. Root splitting is done by first
	moving the root records to the new page, emptying the root, putting
	a node pointer to the new page, and then splitting the new page. */
	
	new_page = btr_page_alloc(tree, 0, FSP_NO_DIR,
				  btr_page_get_level(root, mtr), mtr);

	btr_page_create(new_page, tree, mtr);

	level = btr_page_get_level(root, mtr);
	
	/* Set the levels of the new index page and root page */
	btr_page_set_level(new_page, level, mtr);
	btr_page_set_level(root, level + 1, mtr);
	
	/* Set the next node and previous node fields of new page */
	btr_page_set_next(new_page, FIL_NULL, mtr);
	btr_page_set_prev(new_page, FIL_NULL, mtr);

	/* Move the records from root to the new page */

	page_move_rec_list_end(new_page, root, page_get_infimum_rec(root),
									mtr);
	/* If this is a pessimistic insert which is actually done to
	perform a pessimistic update then we have stored the lock
	information of the record to be inserted on the infimum of the
	root page: we cannot discard the lock structs on the root page */
	
	lock_update_root_raise(new_page, root);

	/* Create a memory heap where the node pointer is stored */
	heap = mem_heap_create(100);

	rec = page_rec_get_next(page_get_infimum_rec(new_page));
	new_page_no = buf_frame_get_page_no(new_page);
	
	/* Build the node pointer (= node key and page address) for the
	child */

	node_ptr = dict_tree_build_node_ptr(tree, rec, new_page_no, heap);
	
	/* Reorganize the root to get free space */
	btr_page_reorganize(root, mtr);	

	page_cursor = btr_cur_get_page_cur(cursor);
	
	/* Insert node pointer to the root */

	page_cur_set_before_first(root, page_cursor);

	node_ptr_rec = page_cur_tuple_insert(page_cursor, node_ptr, mtr);

	ut_ad(node_ptr_rec);

	/* The node pointer must be marked as the predefined minimum record,
	as there is no lower alphabetical limit to records in the leftmost
	node of a level: */

	btr_set_min_rec_mark(node_ptr_rec, mtr);
		
	/* Free the memory heap */
	mem_heap_free(heap);

	/* We play safe and reset the free bits for the new page */

/*	printf("Root raise new page no %lu\n",
					buf_frame_get_page_no(new_page)); */

	ibuf_reset_free_bits(UT_LIST_GET_FIRST(tree->tree_indexes),
								new_page);
	/* Reposition the cursor to the child node */
	page_cur_search(new_page, tuple, PAGE_CUR_LE, page_cursor);
	
	/* Split the child and insert tuple */
	return(btr_page_split_and_insert(cursor, tuple, mtr));
}	

/*****************************************************************
Decides if the page should be split at the convergence point of inserts
converging to the left. */

ibool
btr_page_get_split_rec_to_left(
/*===========================*/
				/* out: TRUE if split recommended */
	btr_cur_t*	cursor,	/* in: cursor at which to insert */
	rec_t**		split_rec) /* out: if split recommended,
				the first record on upper half page,
				or NULL if tuple to be inserted should
				be first */
{
	page_t*	page;
	rec_t*	insert_point;
	rec_t*	infimum;

	page = btr_cur_get_page(cursor);
	insert_point = btr_cur_get_rec(cursor);

	if ((page_header_get_ptr(page, PAGE_LAST_INSERT)
	    == page_rec_get_next(insert_point))
	    && (page_header_get_field(page, PAGE_DIRECTION) == PAGE_LEFT)
	    && ((page_header_get_field(page, PAGE_N_DIRECTION)
	     	 			>= BTR_PAGE_SEQ_INSERT_LIMIT)
	     	|| (page_header_get_field(page, PAGE_N_DIRECTION) + 1
	     	 			>= page_get_n_recs(page)))) {

	     	infimum = page_get_infimum_rec(page);
	     	 			
		if ((infimum != insert_point)
		    && (page_rec_get_next(infimum) != insert_point)) {

			*split_rec = insert_point;
		} else {
	     		*split_rec = page_rec_get_next(insert_point);
	     	}

		return(TRUE);
	}

	return(FALSE);
}

/*****************************************************************
Decides if the page should be split at the convergence point of inserts
converging to the right. */

ibool
btr_page_get_split_rec_to_right(
/*============================*/
				/* out: TRUE if split recommended */
	btr_cur_t*	cursor,	/* in: cursor at which to insert */
	rec_t**		split_rec) /* out: if split recommended,
				the first record on upper half page,
				or NULL if tuple to be inserted should
				be first */
{
	page_t*	page;
	rec_t*	insert_point;
	rec_t*	supremum;

	page = btr_cur_get_page(cursor);
	insert_point = btr_cur_get_rec(cursor);

	if ((page_header_get_ptr(page, PAGE_LAST_INSERT) == insert_point)
	    && (page_header_get_field(page, PAGE_DIRECTION) == PAGE_RIGHT)
	    && ((page_header_get_field(page, PAGE_N_DIRECTION)
	     	 			>= BTR_PAGE_SEQ_INSERT_LIMIT)
	     	|| (page_header_get_field(page, PAGE_N_DIRECTION) + 1
	     	 			>= page_get_n_recs(page)))) {

	     	supremum = page_get_supremum_rec(page);
	     	 			
		if ((page_rec_get_next(insert_point) != supremum)
		    && (page_rec_get_next(page_rec_get_next(insert_point))
			!= supremum)
		    && (page_rec_get_next(page_rec_get_next(
					page_rec_get_next(insert_point)))
			!= supremum)) {

			/* If there are >= 3 user records up from the insert
			point, split all but 2 off */

			*split_rec = page_rec_get_next(page_rec_get_next(
					page_rec_get_next(insert_point)));
		} else {
			/* Else split at inserted record */
	     		*split_rec = NULL;
	     	}

		return(TRUE);
	}

	return(FALSE);
}

/*****************************************************************
Calculates a split record such that the tuple will certainly fit on
its half-page when the split is performed. We assume in this function
only that the cursor page has at least one user record. */
static
rec_t*
btr_page_get_sure_split_rec(
/*========================*/
					/* out: split record, or NULL if
					tuple will be the first record on
					upper half-page */
	btr_cur_t*	cursor,		/* in: cursor at which insert
					should be made */
	dtuple_t*	tuple)		/* in: tuple to insert */	
{
	page_t*	page;
	ulint	insert_size;
	ulint	free_space;
	ulint	total_data;
	ulint	total_n_recs;
	ulint	total_space;
	ulint	incl_data;
	rec_t*	ins_rec;
	rec_t*	rec;
	rec_t*	next_rec;
	ulint	n;
	
	page = btr_cur_get_page(cursor);
	
	insert_size = rec_get_converted_size(tuple);
	free_space  = page_get_free_space_of_empty();

	/* free_space is now the free space of a created new page */

	total_data   = page_get_data_size(page) + insert_size;
	total_n_recs = page_get_n_recs(page) + 1;
	ut_ad(total_n_recs >= 2);
	total_space  = total_data + page_dir_calc_reserved_space(total_n_recs);

	n = 0;
	incl_data = 0;
	ins_rec = btr_cur_get_rec(cursor);
	rec = page_get_infimum_rec(page);

	/* We start to include records to the left half, and when the
	space reserved by them exceeds half of total_space, then if
	the included records fit on the left page, they will be put there
	if something was left over also for the right page,
	otherwise the last included record will be the first on the right
	half page */

	for (;;) {
		/* Decide the next record to include */
		if (rec == ins_rec) {
			rec = NULL;	/* NULL denotes that tuple is
					now included */
		} else if (rec == NULL) {
			rec = page_rec_get_next(ins_rec);
		} else {
			rec = page_rec_get_next(rec);
		}

		if (rec == NULL) {
			/* Include tuple */
			incl_data += insert_size;
		} else {
			incl_data += rec_get_size(rec);
		}

		n++;
		
		if (incl_data + page_dir_calc_reserved_space(n)
                    >= total_space / 2) {

                    	if (incl_data + page_dir_calc_reserved_space(n)
                    	    <= free_space) {
                    	    	/* The next record will be the first on
                    	    	the right half page if it is not the
                    	    	supremum record of page */

				if (rec == ins_rec) {
					next_rec = NULL;
				} else if (rec == NULL) {
					next_rec = page_rec_get_next(ins_rec);
				} else {
					next_rec = page_rec_get_next(rec);
				}
				if (next_rec != page_get_supremum_rec(page)) {

					return(next_rec);
				}
                    	}

			return(rec);
		}
	}
}		

/*****************************************************************
Returns TRUE if the insert fits on the appropriate half-page with the
chosen split_rec. */
static
ibool
btr_page_insert_fits(
/*=================*/
					/* out: TRUE if fits */
	btr_cur_t*	cursor,		/* in: cursor at which insert
					should be made */
	rec_t*		split_rec,	/* in: suggestion for first record
					on upper half-page, or NULL if
					tuple to be inserted should be first */
	dtuple_t*	tuple)		/* in: tuple to insert */	
{
	page_t*	page;
	ulint	insert_size;
	ulint	free_space;
	ulint	total_data;
	ulint	total_n_recs;
	rec_t*	rec;
	rec_t*	end_rec;
	
	page = btr_cur_get_page(cursor);
	
	insert_size = rec_get_converted_size(tuple);
	free_space  = page_get_free_space_of_empty();

	/* free_space is now the free space of a created new page */

	total_data   = page_get_data_size(page) + insert_size;
	total_n_recs = page_get_n_recs(page) + 1;
	
	/* We determine which records (from rec to end_rec, not including
	end_rec) will end up on the other half page from tuple when it is
	inserted. */
	
	if (split_rec == NULL) {
		rec = page_rec_get_next(page_get_infimum_rec(page));
		end_rec = page_rec_get_next(btr_cur_get_rec(cursor));

	} else if (cmp_dtuple_rec(tuple, split_rec) >= 0) {

		rec = page_rec_get_next(page_get_infimum_rec(page));
 		end_rec = split_rec;
	} else {
		rec = split_rec;
		end_rec = page_get_supremum_rec(page);
	}

	if (total_data + page_dir_calc_reserved_space(total_n_recs)
	    <= free_space) {

		/* Ok, there will be enough available space on the
		half page where the tuple is inserted */

		return(TRUE);
	}

	while (rec != end_rec) {
		/* In this loop we calculate the amount of reserved
		space after rec is removed from page. */

		total_data -= rec_get_size(rec);
		total_n_recs--;

		if (total_data + page_dir_calc_reserved_space(total_n_recs)
                    <= free_space) {

			/* Ok, there will be enough available space on the
			half page where the tuple is inserted */

			return(TRUE);
		}

		rec = page_rec_get_next(rec);
	}

	return(FALSE);
}		

/***********************************************************
Inserts a data tuple to a tree on a non-leaf level. It is assumed
that mtr holds an x-latch on the tree. */

void
btr_insert_on_non_leaf_level(
/*=========================*/
	dict_tree_t*	tree,	/* in: tree */
	ulint		level,	/* in: level, must be > 0 */
	dtuple_t*	tuple,	/* in: the record to be inserted */
	mtr_t*		mtr)	/* in: mtr */
{
	btr_cur_t	cursor;		
	ulint		err;
	rec_t*		rec;

	ut_ad(level > 0);
	
	/* In the following, choose just any index from the tree as the
	first parameter for btr_cur_search_to_nth_level. */

	btr_cur_search_to_nth_level(UT_LIST_GET_FIRST(tree->tree_indexes),
				    level, tuple, PAGE_CUR_LE,
				    BTR_CONT_MODIFY_TREE,
				    &cursor, 0, mtr);

	err = btr_cur_pessimistic_insert(BTR_NO_LOCKING_FLAG
					| BTR_KEEP_SYS_FLAG
					| BTR_NO_UNDO_LOG_FLAG,
					&cursor, tuple,
					&rec, NULL, mtr);
	ut_a(err == DB_SUCCESS);
}

/******************************************************************
Attaches the halves of an index page on the appropriate level in an
index tree. */
static
void
btr_attach_half_pages(
/*==================*/
	dict_tree_t*	tree,		/* in: the index tree */
	page_t*		page,		/* in: page to be split */
	rec_t*		split_rec,	/* in: first record on upper
					half page */
	page_t*		new_page,	/* in: the new half page */
	ulint		direction,	/* in: FSP_UP or FSP_DOWN */
	mtr_t*		mtr)		/* in: mtr */
{
	ulint		space;
	rec_t*		node_ptr;
	page_t*		prev_page;
	page_t*		next_page;
	ulint		prev_page_no;
	ulint		next_page_no;
	ulint		level;
	page_t*		lower_page;
	page_t*		upper_page;
	ulint		lower_page_no;
	ulint		upper_page_no;
	dtuple_t*	node_ptr_upper;
	mem_heap_t* 	heap;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	ut_ad(mtr_memo_contains(mtr, buf_block_align(new_page),
			      				MTR_MEMO_PAGE_X_FIX));

	/* Based on split direction, decide upper and lower pages */
	if (direction == FSP_DOWN) {

		lower_page_no = buf_frame_get_page_no(new_page);
		upper_page_no = buf_frame_get_page_no(page);
		lower_page = new_page;
		upper_page = page;

		/* Look from the tree for the node pointer to page */
		node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);

		/* Replace the address of the old child node (= page) with the 
		address of the new lower half */

		btr_node_ptr_set_child_page_no(node_ptr, lower_page_no, mtr);
	} else {
		lower_page_no = buf_frame_get_page_no(page);
		upper_page_no = buf_frame_get_page_no(new_page);
		lower_page = page;
		upper_page = new_page;
	}
				   
	/* Create a memory heap where the data tuple is stored */
	heap = mem_heap_create(100);

	/* Get the level of the split pages */
	level = btr_page_get_level(page, mtr);

	/* Build the node pointer (= node key and page address) for the upper
	half */

	node_ptr_upper = dict_tree_build_node_ptr(tree, split_rec,
							upper_page_no, heap);

	/* Insert it next to the pointer to the lower half. Note that this
	may generate recursion leading to a split on the higher level. */

	btr_insert_on_non_leaf_level(tree, level + 1, node_ptr_upper, mtr);
		
	/* Free the memory heap */
	mem_heap_free(heap);

	/* Get the previous and next pages of page */

	prev_page_no = btr_page_get_prev(page, mtr);
	next_page_no = btr_page_get_next(page, mtr);
	space = buf_frame_get_space_id(page);
	
	/* Update page links of the level */
	
	if (prev_page_no != FIL_NULL) {

		prev_page = btr_page_get(space, prev_page_no, RW_X_LATCH, mtr);

		btr_page_set_next(prev_page, lower_page_no, mtr);
	}

	if (next_page_no != FIL_NULL) {

		next_page = btr_page_get(space, next_page_no, RW_X_LATCH, mtr);

		btr_page_set_prev(next_page, upper_page_no, mtr);
	}
	
	btr_page_set_prev(lower_page, prev_page_no, mtr);
	btr_page_set_next(lower_page, upper_page_no, mtr);
	btr_page_set_level(lower_page, level, mtr);

	btr_page_set_prev(upper_page, lower_page_no, mtr);
	btr_page_set_next(upper_page, next_page_no, mtr);
	btr_page_set_level(upper_page, level, mtr);
}

/*****************************************************************
Splits an index page to halves and inserts the tuple. It is assumed
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
is released within this function! NOTE that the operation of this
function must always succeed, we cannot reverse it: therefore
enough free disk space must be guaranteed to be available before
this function is called. */

rec_t*
btr_page_split_and_insert(
/*======================*/
				/* out: inserted record; NOTE: the tree
				x-latch is released! NOTE: 2 free disk
				pages must be available! */
	btr_cur_t*	cursor,	/* in: cursor at which to insert; when the
				function returns, the cursor is positioned
				on the predecessor of the inserted record */
	dtuple_t*	tuple,	/* in: tuple to insert */
	mtr_t*		mtr)	/* in: mtr */
{
	dict_tree_t*	tree;
	page_t*		page;
	ulint		page_no;
	byte		direction;
	ulint		hint_page_no;
	page_t*		new_page;
	rec_t*		split_rec;
	page_t*		left_page;
	page_t*		right_page;
	page_t*		insert_page;
	page_cur_t*	page_cursor;
	rec_t*		first_rec;
	byte*		buf;
	rec_t*		move_limit;
	ibool		insert_will_fit;
	ulint		n_iterations = 0;
	rec_t*		rec;
func_start:
	tree = btr_cur_get_tree(cursor);
	
	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK));
	ut_ad(rw_lock_own(dict_tree_get_lock(tree), RW_LOCK_EX));

	page = btr_cur_get_page(cursor);

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	ut_ad(page_get_n_recs(page) >= 2);
	
	page_no = buf_frame_get_page_no(page);

	/* 1. Decide the split record; split_rec == NULL means that the
	tuple to be inserted should be the first record on the upper
	half-page */

	if (n_iterations > 0) {
		direction = FSP_UP;
		hint_page_no = page_no + 1;
		split_rec = btr_page_get_sure_split_rec(cursor, tuple);
		
	} else if (btr_page_get_split_rec_to_right(cursor, &split_rec)) {
		direction = FSP_UP;
		hint_page_no = page_no + 1;

	} else if (btr_page_get_split_rec_to_left(cursor, &split_rec)) {
		direction = FSP_DOWN;
		hint_page_no = page_no - 1;
	} else {
		direction = FSP_UP;
		hint_page_no = page_no + 1;
		split_rec = page_get_middle_rec(page);
	}

	/* 2. Allocate a new page to the tree */
	new_page = btr_page_alloc(tree, hint_page_no, direction,
					btr_page_get_level(page, mtr), mtr);
	btr_page_create(new_page, tree, mtr);
	
	/* 3. Calculate the first record on the upper half-page, and the
	first record (move_limit) on original page which ends up on the
	upper half */

	if (split_rec != NULL) {
		first_rec = split_rec;
		move_limit = split_rec;
	} else {
		buf = mem_alloc(rec_get_converted_size(tuple));

		first_rec = rec_convert_dtuple_to_rec(buf, tuple);
		move_limit = page_rec_get_next(btr_cur_get_rec(cursor));
	}
	
	/* 4. Do first the modifications in the tree structure */

	btr_attach_half_pages(tree, page, first_rec, new_page, direction, mtr);

	if (split_rec == NULL) {
		mem_free(buf);
	}

	/* If the split is made on the leaf level and the insert will fit
	on the appropriate half-page, we may release the tree x-latch.
	We can then move the records after releasing the tree latch,
	thus reducing the tree latch contention. */

	insert_will_fit = btr_page_insert_fits(cursor, split_rec, tuple);
	
	if (insert_will_fit && (btr_page_get_level(page, mtr) == 0)) {

		mtr_memo_release(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK);
	}

	/* 5. Move then the records to the new page */
	if (direction == FSP_DOWN) {
/*		printf("Split left\n"); */

		page_move_rec_list_start(new_page, page, move_limit, mtr);
		left_page = new_page;
		right_page = page;

		lock_update_split_left(right_page, left_page);
	} else {
/*		printf("Split right\n"); */

		page_move_rec_list_end(new_page, page, move_limit, mtr);
		left_page = page;
		right_page = new_page;

		lock_update_split_right(right_page, left_page);
	}

	/* 6. The split and the tree modification is now completed. Decide the
	page where the tuple should be inserted */

	if (split_rec == NULL) {
		insert_page = right_page;

	} else if (cmp_dtuple_rec(tuple, first_rec) >= 0) {

		insert_page = right_page;
	} else {
		insert_page = left_page;
	}

	/* 7. Reposition the cursor for insert and try insertion */
	page_cursor = btr_cur_get_page_cur(cursor);

	page_cur_search(insert_page, tuple, PAGE_CUR_LE, page_cursor);

	rec = page_cur_tuple_insert(page_cursor, tuple, mtr);

	if (rec != NULL) {
		/* Insert fit on the page: update the free bits for the
		left and right pages in the same mtr */

		ibuf_update_free_bits_for_two_pages_low(cursor->index,
							left_page,
							right_page, mtr);
		/* printf("Split and insert done %lu %lu\n",
				buf_frame_get_page_no(left_page),
				buf_frame_get_page_no(right_page)); */
		return(rec);
	}
	
	/* 8. If insert did not fit, try page reorganization */

	btr_page_reorganize(insert_page, mtr);

	page_cur_search(insert_page, tuple, PAGE_CUR_LE, page_cursor);
	rec = page_cur_tuple_insert(page_cursor, tuple, mtr);

	if (rec == NULL) {
		/* The insert did not fit on the page: loop back to the
		start of the function for a new split */
		
		/* We play safe and reset the free bits for new_page */
		ibuf_reset_free_bits(cursor->index, new_page);

		/* printf("Split second round %lu\n",
					buf_frame_get_page_no(page)); */
		n_iterations++;
		ut_ad(n_iterations < 2);
		ut_ad(!insert_will_fit);

		goto func_start;
	}

	/* Insert fit on the page: update the free bits for the
	left and right pages in the same mtr */

	ibuf_update_free_bits_for_two_pages_low(cursor->index, left_page,
							right_page, mtr);
	/* printf("Split and insert done %lu %lu\n",
				buf_frame_get_page_no(left_page),
				buf_frame_get_page_no(right_page)); */

	ut_ad(page_validate(left_page, UT_LIST_GET_FIRST(tree->tree_indexes)));
	ut_ad(page_validate(right_page, UT_LIST_GET_FIRST(tree->tree_indexes)));

	return(rec);
}

/*****************************************************************
Removes a page from the level list of pages. */
static
void
btr_level_list_remove(
/*==================*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page to remove */
	mtr_t*		mtr)	/* in: mtr */
{	
	ulint	space;
	ulint	prev_page_no;
	page_t*	prev_page;
	ulint	next_page_no;
	page_t*	next_page;
	
	ut_ad(tree && page && mtr);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	/* Get the previous and next page numbers of page */

	prev_page_no = btr_page_get_prev(page, mtr);
	next_page_no = btr_page_get_next(page, mtr);
	space = buf_frame_get_space_id(page);
	
	/* Update page links of the level */
	
	if (prev_page_no != FIL_NULL) {

		prev_page = btr_page_get(space, prev_page_no, RW_X_LATCH, mtr);

		btr_page_set_next(prev_page, next_page_no, mtr);
	}

	if (next_page_no != FIL_NULL) {

		next_page = btr_page_get(space, next_page_no, RW_X_LATCH, mtr);

		btr_page_set_prev(next_page, prev_page_no, mtr);
	}
}
	
/********************************************************************
Writes the redo log record for setting an index record as the predefined
minimum record. */
UNIV_INLINE
void
btr_set_min_rec_mark_log(
/*=====================*/
	rec_t*	rec,	/* in: record */
	mtr_t*	mtr)	/* in: mtr */
{
	mlog_write_initial_log_record(rec, MLOG_REC_MIN_MARK, mtr);

	/* Write rec offset as a 2-byte ulint */
	mlog_catenate_ulint(mtr, rec - buf_frame_align(rec), MLOG_2BYTES);
}

/********************************************************************
Parses the redo log record for setting an index record as the predefined
minimum record. */

byte*
btr_parse_set_min_rec_mark(
/*=======================*/
			/* out: end of log record or NULL */
	byte*	ptr,	/* in: buffer */
	byte*	end_ptr,/* in: buffer end */
	page_t*	page,	/* in: page or NULL */
	mtr_t*	mtr)	/* in: mtr or NULL */
{
	rec_t*	rec;

	if (end_ptr < ptr + 2) {

		return(NULL);
	}

	if (page) {
		rec = page + mach_read_from_2(ptr);

		btr_set_min_rec_mark(rec, mtr);
	}

	return(ptr + 2);
}

/********************************************************************
Sets a record as the predefined minimum record. */

void
btr_set_min_rec_mark(
/*=================*/
	rec_t*	rec,	/* in: record */
	mtr_t*	mtr)	/* in: mtr */
{
	ulint	info_bits;

	info_bits = rec_get_info_bits(rec);

	rec_set_info_bits(rec, info_bits | REC_INFO_MIN_REC_FLAG);

	btr_set_min_rec_mark_log(rec, mtr);
}

/*****************************************************************
Deletes on the upper level the node pointer to a page. */

void
btr_node_ptr_delete(
/*================*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page whose node pointer is deleted */
	mtr_t*		mtr)	/* in: mtr */
{
	rec_t*		node_ptr;
	btr_cur_t	cursor;
	ibool		compressed;
	ulint		err;
	
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	/* Delete node pointer on father page */

	node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);

	btr_cur_position(UT_LIST_GET_FIRST(tree->tree_indexes), node_ptr,
								&cursor);
	compressed = btr_cur_pessimistic_delete(&err, TRUE, &cursor, mtr);

	ut_a(err == DB_SUCCESS);

	if (!compressed) {
		btr_cur_compress_if_useful(&cursor, mtr);
	}
}

/*****************************************************************
If page is the only on its level, this function moves its records to the
father page, thus reducing the tree height. */
static
void
btr_lift_page_up(
/*=============*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page which is the only on its level;
				must not be empty: use
				btr_discard_only_page_on_level if the last
				record from the page should be removed */
	mtr_t*		mtr)	/* in: mtr */
{
	rec_t*	node_ptr;
	page_t*	father_page;
	ulint	page_level;
	
	ut_ad(btr_page_get_prev(page, mtr) == FIL_NULL);
	ut_ad(btr_page_get_next(page, mtr) == FIL_NULL);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
			      				MTR_MEMO_PAGE_X_FIX));
	node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
	father_page = buf_frame_align(node_ptr);
	
	page_level = btr_page_get_level(page, mtr);

	btr_search_drop_page_hash_index(page);
	
	/* Make the father empty */
	btr_page_empty(father_page, mtr);

	/* Move records to the father */
 	page_copy_rec_list_end(father_page, page, page_get_infimum_rec(page),
									mtr);
	lock_update_copy_and_discard(father_page, page);

	btr_page_set_level(father_page, page_level, mtr);

	/* Free the file page */
	btr_page_free(tree, page, mtr);		

	/* We play safe and reset the free bits for the father */
	ibuf_reset_free_bits(UT_LIST_GET_FIRST(tree->tree_indexes),
								father_page);
	ut_ad(page_validate(father_page,
				UT_LIST_GET_FIRST(tree->tree_indexes)));
	ut_ad(btr_check_node_ptr(tree, father_page, mtr));
}	

/*****************************************************************
Tries to merge the page first to the left immediate brother if such a
brother exists, and the node pointers to the current page and to the brother
reside on the same page. If the left brother does not satisfy these
conditions, looks at the right brother. If the page is the only one on that
level lifts the records of the page to the father page, thus reducing the
tree height. It is assumed that mtr holds an x-latch on the tree and on the
page. If cursor is on the leaf level, mtr must also hold x-latches to the
brothers, if they exist. NOTE: it is assumed that the caller has reserved
enough free extents so that the compression will always succeed if done! */

void
btr_compress(
/*=========*/
	btr_cur_t*	cursor,	/* in: cursor on the page to merge or lift;
				the page must not be empty: in record delete
				use btr_discard_page if the page would become
				empty */
	mtr_t*		mtr)	/* in: mtr */
{
	dict_tree_t*	tree;
	ulint		space;
	ulint		left_page_no;
	ulint		right_page_no;
	page_t*		merge_page;
	page_t*		father_page;
	ibool		is_left;
	page_t*		page;
	rec_t*		orig_pred;
	rec_t*		orig_succ;
	rec_t*		node_ptr;
	ulint		data_size;
	ulint		n_recs;
	ulint		max_ins_size;
	ulint		max_ins_size_reorg;
	ulint		level;
	
	page = btr_cur_get_page(cursor);
	tree = btr_cur_get_tree(cursor);

	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK));
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	level = btr_page_get_level(page, mtr);
	space = dict_tree_get_space(tree);

	left_page_no = btr_page_get_prev(page, mtr);
	right_page_no = btr_page_get_next(page, mtr);

/*	printf("Merge left page %lu right %lu \n", left_page_no,
							right_page_no); */

	node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
	father_page = buf_frame_align(node_ptr);

	/* Decide the page to which we try to merge and which will inherit
	the locks */

	if (left_page_no != FIL_NULL) {

		is_left = TRUE;
		merge_page = btr_page_get(space, left_page_no, RW_X_LATCH,
									mtr);
	} else if (right_page_no != FIL_NULL) {

		is_left = FALSE;
		merge_page = btr_page_get(space, right_page_no, RW_X_LATCH,
									mtr);
	} else {
		/* The page is the only one on the level, lift the records
		to the father */
		btr_lift_page_up(tree, page, mtr);

		return;
	}
	
	n_recs = page_get_n_recs(page);
	data_size = page_get_data_size(page);

	max_ins_size_reorg = page_get_max_insert_size_after_reorganize(
							merge_page, n_recs);
	if (data_size > max_ins_size_reorg) {

		/* No space for merge */

		return;
	}

	ut_ad(page_validate(merge_page, cursor->index));

	max_ins_size = page_get_max_insert_size(merge_page, n_recs);
	
	if (data_size > max_ins_size) {

		/* We have to reorganize merge_page */

		btr_page_reorganize(merge_page, mtr);

		ut_ad(page_validate(merge_page, cursor->index));
		ut_ad(page_get_max_insert_size(merge_page, n_recs)
							== max_ins_size_reorg);
	}

	btr_search_drop_page_hash_index(page);

	/* Remove the page from the level list */
	btr_level_list_remove(tree, page, mtr);

	if (is_left) {
		btr_node_ptr_delete(tree, page, mtr);
	} else {
		/* Replace the address of the old child node (= page) with the 
		address of the merge page to the right */

		btr_node_ptr_set_child_page_no(node_ptr, right_page_no, mtr);

		btr_node_ptr_delete(tree, merge_page, mtr);
	}
	
	/* Move records to the merge page */
	if (is_left) {
		orig_pred = page_rec_get_prev(
					page_get_supremum_rec(merge_page));
		page_copy_rec_list_start(merge_page, page,
					page_get_supremum_rec(page), mtr);

		lock_update_merge_left(merge_page, orig_pred, page);
	} else {
		orig_succ = page_rec_get_next(
					page_get_infimum_rec(merge_page));
		page_copy_rec_list_end(merge_page, page,
					page_get_infimum_rec(page), mtr);

		lock_update_merge_right(orig_succ, page);
	}

	/* We have added new records to merge_page: update its free bits */
	ibuf_update_free_bits_if_full(cursor->index, merge_page,
					UNIV_PAGE_SIZE, ULINT_UNDEFINED);
					
	ut_ad(page_validate(merge_page, cursor->index));

	/* Free the file page */
	btr_page_free(tree, page, mtr);		

	ut_ad(btr_check_node_ptr(tree, merge_page, mtr));
}	

/*****************************************************************
Discards a page that is the only page on its level. */
static
void
btr_discard_only_page_on_level(
/*===========================*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: page which is the only on its level */
	mtr_t*		mtr)	/* in: mtr */
{
	rec_t*	node_ptr;
	page_t*	father_page;
	ulint	page_level;
	
	ut_ad(btr_page_get_prev(page, mtr) == FIL_NULL);
	ut_ad(btr_page_get_next(page, mtr) == FIL_NULL);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	btr_search_drop_page_hash_index(page);

	node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
	father_page = buf_frame_align(node_ptr);

	page_level = btr_page_get_level(page, mtr);

	lock_update_discard(page_get_supremum_rec(father_page), page);

	btr_page_set_level(father_page, page_level, mtr);

	/* Free the file page */
	btr_page_free(tree, page, mtr);		

	if (buf_frame_get_page_no(father_page) == dict_tree_get_page(tree)) {
		/* The father is the root page */

		btr_page_empty(father_page, mtr);

		/* We play safe and reset the free bits for the father */
		ibuf_reset_free_bits(UT_LIST_GET_FIRST(tree->tree_indexes),
								father_page);
	} else {
		ut_ad(page_get_n_recs(father_page) == 1);

		btr_discard_only_page_on_level(tree, father_page, mtr);
	}
}	

/*****************************************************************
Discards a page from a B-tree. This is used to remove the last record from
a B-tree page: the whole page must be removed at the same time. This cannot
be used for the root page, which is allowed to be empty. */

void
btr_discard_page(
/*=============*/
	btr_cur_t*	cursor,	/* in: cursor on the page to discard: not on
				the root page */
	mtr_t*		mtr)	/* in: mtr */
{
	dict_tree_t*	tree;
	ulint		space;
	ulint		left_page_no;
	ulint		right_page_no;
	page_t*		merge_page;
	ibool		is_left;
	page_t*		page;
	rec_t*		node_ptr;
	
	page = btr_cur_get_page(cursor);
	tree = btr_cur_get_tree(cursor);

	ut_ad(dict_tree_get_page(tree) != buf_frame_get_page_no(page));
	ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
							MTR_MEMO_X_LOCK));
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	space = dict_tree_get_space(tree);
	
	/* Decide the page which will inherit the locks */

	left_page_no = btr_page_get_prev(page, mtr);
	right_page_no = btr_page_get_next(page, mtr);

	if (left_page_no != FIL_NULL) {
		is_left = TRUE;
		merge_page = btr_page_get(space, left_page_no, RW_X_LATCH,
									mtr);
	} else if (right_page_no != FIL_NULL) {
		is_left = FALSE;
		merge_page = btr_page_get(space, right_page_no, RW_X_LATCH,
									mtr);
	} else {
		btr_discard_only_page_on_level(tree, page, mtr);

		return;
	}

	btr_search_drop_page_hash_index(page);
	
	if ((left_page_no == FIL_NULL)
				&& (btr_page_get_level(page, mtr) > 0)) {

		/* We have to mark the leftmost node pointer on the right
		side page as the predefined minimum record */

		node_ptr = page_rec_get_next(page_get_infimum_rec(merge_page));

		ut_ad(node_ptr != page_get_supremum_rec(merge_page));

		btr_set_min_rec_mark(node_ptr, mtr);
	}	
	
	btr_node_ptr_delete(tree, page, mtr);

	/* Remove the page from the level list */
	btr_level_list_remove(tree, page, mtr);

	if (is_left) {
		lock_update_discard(page_get_supremum_rec(merge_page), page);
	} else {
		lock_update_discard(page_rec_get_next(
				    page_get_infimum_rec(merge_page)), page);
	}

	/* Free the file page */
	btr_page_free(tree, page, mtr);		

	ut_ad(btr_check_node_ptr(tree, merge_page, mtr));
}	

/*****************************************************************
Prints size info of a B-tree. */

void
btr_print_size(
/*===========*/
	dict_tree_t*	tree)	/* in: index tree */
{
	page_t*		root;
	fseg_header_t*	seg;
	mtr_t		mtr;

	if (tree->type & DICT_IBUF) {
		printf(
	"Sorry, cannot print info of an ibuf tree: use ibuf functions\n");

		return;
	}

	mtr_start(&mtr);
	
	root = btr_root_get(tree, &mtr);

	seg = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;

	printf("INFO OF THE NON-LEAF PAGE SEGMENT\n");
	fseg_print(seg, &mtr);

	if (!(tree->type & DICT_UNIVERSAL)) {

		seg = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;

		printf("INFO OF THE LEAF PAGE SEGMENT\n");
		fseg_print(seg, &mtr);
	}

	mtr_commit(&mtr); 	
}

/****************************************************************
Prints recursively index tree pages. */
static
void
btr_print_recursive(
/*================*/
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: index page */
	ulint		width,	/* in: print this many entries from start
				and end */
	mtr_t*		mtr)	/* in: mtr */
{
	page_cur_t	cursor;
	ulint		n_recs;
	ulint		i	= 0;
	mtr_t		mtr2;
	rec_t*		node_ptr;
	page_t*		child;
	
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	printf("NODE ON LEVEL %lu page number %lu\n",
		btr_page_get_level(page, mtr), buf_frame_get_page_no(page));
	
	page_print(page, width, width);
	
	n_recs = page_get_n_recs(page);
	
	page_cur_set_before_first(page, &cursor);
	page_cur_move_to_next(&cursor);

	while (!page_cur_is_after_last(&cursor)) {

		if (0 == btr_page_get_level(page, mtr)) {

			/* If this is the leaf level, do nothing */

		} else if ((i <= width) || (i >= n_recs - width)) {

			mtr_start(&mtr2);

			node_ptr = page_cur_get_rec(&cursor);

			child = btr_node_ptr_get_child(node_ptr, &mtr2);

			btr_print_recursive(tree, child, width, &mtr2);
			mtr_commit(&mtr2);
		}

		page_cur_move_to_next(&cursor);
		i++;
	}
}

/******************************************************************
Prints directories and other info of all nodes in the tree. */

void
btr_print_tree(
/*===========*/
	dict_tree_t*	tree,	/* in: tree */
	ulint		width)	/* in: print this many entries from start
				and end */
{
	mtr_t	mtr;
	page_t*	root;

	printf("--------------------------\n");
	printf("INDEX TREE PRINT\n");

	mtr_start(&mtr);

	root = btr_root_get(tree, &mtr);

	btr_print_recursive(tree, root, width, &mtr);

	mtr_commit(&mtr);

	btr_validate_tree(tree);
}

/****************************************************************
Checks that the node pointer to a page is appropriate. */

ibool
btr_check_node_ptr(
/*===============*/
				/* out: TRUE */
	dict_tree_t*	tree,	/* in: index tree */
	page_t*		page,	/* in: index page */
	mtr_t*		mtr)	/* in: mtr */
{
	mem_heap_t*	heap;
	rec_t*		node_ptr;
	dtuple_t*	node_ptr_tuple;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	if (dict_tree_get_page(tree) == buf_frame_get_page_no(page)) {

		return(TRUE);
	}

	node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
 
	if (btr_page_get_level(page, mtr) == 0) {

		return(TRUE);
	}
	
	heap = mem_heap_create(256);
		
	node_ptr_tuple = dict_tree_build_node_ptr(
				tree,
				page_rec_get_next(page_get_infimum_rec(page)),
				0, heap);
				
	ut_a(cmp_dtuple_rec(node_ptr_tuple, node_ptr) == 0);

	mem_heap_free(heap);

	return(TRUE);
}

/****************************************************************
Validates index tree level. */
static
void
btr_validate_level(
/*===============*/
	dict_tree_t*	tree,	/* in: index tree */
	ulint		level)	/* in: level number */
{
	ulint		space;
	mtr_t		mtr;
	page_t*		page;
	page_t*		right_page;
	page_t*		father_page;
	page_t*		right_father_page;
	rec_t*		node_ptr;
	rec_t*		right_node_ptr;
	ulint		right_page_no;
	ulint		left_page_no;
	page_cur_t	cursor;
	mem_heap_t*	heap;
	dtuple_t*	node_ptr_tuple;

	mtr_start(&mtr);

	page = btr_root_get(tree, &mtr);

	space = buf_frame_get_space_id(page);

	while (level != btr_page_get_level(page, &mtr)) {

		ut_a(btr_page_get_level(page, &mtr) > 0);

		page_cur_set_before_first(page, &cursor);
		page_cur_move_to_next(&cursor);

		node_ptr = page_cur_get_rec(&cursor);
		page = btr_node_ptr_get_child(node_ptr, &mtr);
	}

	/* Now we are on the desired level */
loop:
	mtr_x_lock(dict_tree_get_lock(tree), &mtr);

	/* Check ordering of records */
	page_validate(page, UT_LIST_GET_FIRST(tree->tree_indexes));

	ut_a(btr_page_get_level(page, &mtr) == level);

	right_page_no = btr_page_get_next(page, &mtr);
	left_page_no = btr_page_get_prev(page, &mtr);

	ut_a((page_get_n_recs(page) > 0)
	     || ((level == 0) &&
		  (buf_frame_get_page_no(page) == dict_tree_get_page(tree))));

	if (right_page_no != FIL_NULL) {

		right_page = btr_page_get(space, right_page_no, RW_X_LATCH,
									&mtr);
		ut_a(cmp_rec_rec(page_rec_get_prev(page_get_supremum_rec(page)),
			page_rec_get_next(page_get_infimum_rec(right_page)),
			UT_LIST_GET_FIRST(tree->tree_indexes)) < 0);
	}
	
	if ((level > 0) && (left_page_no == FIL_NULL)) {
		ut_a(REC_INFO_MIN_REC_FLAG & rec_get_info_bits(
			page_rec_get_next(page_get_infimum_rec(page))));
	}

	if (buf_frame_get_page_no(page) != dict_tree_get_page(tree)) {

		/* Check father node pointers */
	
		node_ptr = btr_page_get_father_node_ptr(tree, page, &mtr);

		ut_a(node_ptr == btr_page_get_father_for_rec(tree, page,
			page_rec_get_prev(page_get_supremum_rec(page)), &mtr));

		father_page = buf_frame_align(node_ptr);

		if (btr_page_get_level(page, &mtr) > 0) {
			heap = mem_heap_create(256);
		
			node_ptr_tuple = dict_tree_build_node_ptr(
						tree,
					page_rec_get_next(
						page_get_infimum_rec(page)),
						0, heap);
			ut_a(cmp_dtuple_rec(node_ptr_tuple, node_ptr) == 0);
			mem_heap_free(heap);
		}

		if (left_page_no == FIL_NULL) {
			ut_a(node_ptr == page_rec_get_next(
					page_get_infimum_rec(father_page)));
			ut_a(btr_page_get_prev(father_page, &mtr) == FIL_NULL);
		}

		if (right_page_no == FIL_NULL) {
			ut_a(node_ptr == page_rec_get_prev(
					page_get_supremum_rec(father_page)));
			ut_a(btr_page_get_next(father_page, &mtr) == FIL_NULL);
		}

		if (right_page_no != FIL_NULL) {

			right_node_ptr = btr_page_get_father_node_ptr(tree,
							right_page, &mtr);
			if (page_rec_get_next(node_ptr) !=
					page_get_supremum_rec(father_page)) {

				ut_a(right_node_ptr ==
						page_rec_get_next(node_ptr));
			} else {
				right_father_page = buf_frame_align(
							right_node_ptr);
							
				ut_a(right_node_ptr == page_rec_get_next(
					   		page_get_infimum_rec(
							right_father_page)));
				ut_a(buf_frame_get_page_no(right_father_page)
				   == btr_page_get_next(father_page, &mtr));
			}					
		}
	}

	mtr_commit(&mtr);

	if (right_page_no != FIL_NULL) {
		mtr_start(&mtr);
	
		page = btr_page_get(space, right_page_no, RW_X_LATCH, &mtr);

		goto loop;
	}
}

/******************************************************************
Checks the consistency of an index tree. */

void
btr_validate_tree(
/*==============*/
	dict_tree_t*	tree)	/* in: tree */
{
	mtr_t	mtr;
	page_t*	root;
	ulint	i;
	ulint	n;

	mtr_start(&mtr);
	mtr_x_lock(dict_tree_get_lock(tree), &mtr);

	root = btr_root_get(tree, &mtr);
	n = btr_page_get_level(root, &mtr);

	for (i = 0; i <= n; i++) {
		
		btr_validate_level(tree, n - i);
	}

	mtr_commit(&mtr);
}