~drizzle-trunk/drizzle/development

/******************************************************

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"

#include "trx0trx.h"

/*

Latching strategy of the InnoDB B-tree

--------------------------------------

A tree latch protects all non-leaf nodes of the tree. Each node of a tree

also has a latch of its own.

A B-tree operation normally first acquires an S-latch on the tree. It

searches down the tree and releases the tree latch when it has the

leaf node latch. To save CPU time we do not acquire any latch on

non-leaf nodes of the tree during a search, those pages are only bufferfixed.

If an operation needs to restructure the tree, it acquires an X-latch on

the tree before searching to a leaf node. If it needs, for example, to

split a leaf,

(1) InnoDB decides the split point in the leaf,

(2) allocates a new page,

(3) inserts the appropriate node pointer to the first non-leaf level,

(4) releases the tree X-latch,

(5) and then moves records from the leaf to the new allocated page.

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.

*/

/****************************************************************

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_index_t*	index,	/* 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 */

	const ulint*	offsets,	/* in: rec_get_offsets(

					split_rec, cursor->index) */

	dtuple_t*	tuple,		/* in: tuple to insert */

	mem_heap_t*	heap);		/* in: temporary memory heap */

/******************************************************************

Gets the root node of a tree and x-latches it. */

page_t*

btr_root_get(

/*=========*/

				/* out: root page, x-latched */

	dict_index_t*	index,	/* in: index tree */

	mtr_t*		mtr)	/* in: mtr */

{

	ulint	space;

	ulint	root_page_no;

	page_t*	root;

	space = dict_index_get_space(index);

	root_page_no = dict_index_get_page(index);

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

	ut_a((ibool)!!page_is_comp(root) == dict_table_is_comp(index->table));

	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;

	ulint	space;

	if (!page_rec_is_infimum(rec)) {

		rec_t*	prev_rec = page_rec_get_prev(rec);

		if (!page_rec_is_infimum(prev_rec)) {

			return(prev_rec);

		}

	}

	page = buf_frame_align(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)));

		ut_a(page_is_comp(prev_page) == page_is_comp(page));

#ifdef UNIV_BTR_DEBUG

		ut_a(btr_page_get_next(prev_page, mtr)

		     == buf_frame_get_page_no(page));

#endif /* UNIV_BTR_DEBUG */

		return(page_rec_get_prev(page_get_supremum_rec(prev_page)));

	}

	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;

	ulint	space;

	if (!page_rec_is_supremum(rec)) {

		rec_t*	next_rec = page_rec_get_next(rec);

		if (!page_rec_is_supremum(next_rec)) {

			return(next_rec);

		}

	}

	page = buf_frame_align(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)));

#ifdef UNIV_BTR_DEBUG

		ut_a(btr_page_get_prev(next_page, mtr)

		     == buf_frame_get_page_no(page));

#endif /* UNIV_BTR_DEBUG */

		ut_a(page_is_comp(next_page) == page_is_comp(page));

		return(page_rec_get_next(page_get_infimum_rec(next_page)));

	}

	return(NULL);

}

/******************************************************************

Creates a new index page (not the root, and also not

used in page reorganization). */

static

void

btr_page_create(

/*============*/

	page_t*		page,	/* in: page to be created */

	dict_index_t*	index,	/* in: index */

	mtr_t*		mtr)	/* in: mtr */

{

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),

				MTR_MEMO_PAGE_X_FIX));

	page_create(page, mtr, dict_table_is_comp(index->table));

	buf_block_align(page)->check_index_page_at_flush = TRUE;

	btr_page_set_index_id(page, index->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_index_t*	index,	/* in: index tree */

	mtr_t*		mtr)	/* in: mtr */

{

	fil_addr_t	node_addr;

	page_t*		root;

	page_t*		new_page;

	root = btr_root_get(index, 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_index_get_space(index), node_addr.page,

				RW_X_LATCH, mtr);

#ifdef UNIV_SYNC_DEBUG

	buf_page_dbg_add_level(new_page, SYNC_TREE_NODE_NEW);

#endif /* UNIV_SYNC_DEBUG */

	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! */

page_t*

btr_page_alloc(

/*===========*/

					/* out: new allocated page, x-latched;

					NULL if out of space */

	dict_index_t*	index,		/* in: index */

	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;

	if (index->type & DICT_IBUF) {

		return(btr_page_alloc_for_ibuf(index, mtr));

	}

	root = btr_root_get(index, 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);

	if (new_page_no == FIL_NULL) {

		return(NULL);

	}

	new_page = buf_page_get(dict_index_get_space(index), new_page_no,

				RW_X_LATCH, mtr);

#ifdef UNIV_SYNC_DEBUG

	buf_page_dbg_add_level(new_page, SYNC_TREE_NODE_NEW);

#endif /* UNIV_SYNC_DEBUG */

	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_index_get_lock(index), &mtr);

	root = btr_root_get(index, &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_error;

	}

	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_index_t*	index,	/* 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(index, 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. Can be used also to (BLOB)

external storage pages, because the page level 0 can be given as an

argument. */

void

btr_page_free_low(

/*==============*/

	dict_index_t*	index,	/* in: index tree */

	page_t*		page,	/* in: page to be freed, x-latched */

	ulint		level,	/* in: page level */

	mtr_t*		mtr)	/* in: mtr */

{

	fseg_header_t*	seg_header;

	page_t*		root;

	ulint		space;

	ulint		page_no;

	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 (index->type & DICT_IBUF) {

		btr_page_free_for_ibuf(index, page, mtr);

		return;

	}

	root = btr_root_get(index, 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);

}

/******************************************************************

Frees a file page used in an index tree. NOTE: cannot free field external

storage pages because the page must contain info on its level. */

void

btr_page_free(

/*==========*/

	dict_index_t*	index,	/* in: index tree */

	page_t*		page,	/* in: page to be freed, x-latched */

	mtr_t*		mtr)	/* in: mtr */

{

	ulint		level;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),

				MTR_MEMO_PAGE_X_FIX));

	level = btr_page_get_level(page, mtr);

	btr_page_free_low(index, page, level, 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 */

	const ulint*	offsets,/* in: array returned by rec_get_offsets() */

	ulint		page_no,/* in: child node address */

	mtr_t*		mtr)	/* in: mtr */

{

	byte*	field;

	ulint	len;

	ut_ad(rec_offs_validate(rec, NULL, offsets));

	ut_ad(0 < btr_page_get_level(buf_frame_align(rec), mtr));

	ut_ad(!rec_offs_comp(offsets) || rec_get_node_ptr_flag(rec));

	/* The child address is in the last field */

	field = rec_get_nth_field(rec, offsets,

				  rec_offs_n_fields(offsets) - 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 */

	const ulint*	offsets,/* in: array returned by rec_get_offsets() */

	mtr_t*		mtr)	/* in: mtr */

{

	ulint	page_no;

	ulint	space;

	page_t*	page;

	ut_ad(rec_offs_validate(node_ptr, NULL, offsets));

	space = buf_frame_get_space_id(node_ptr);

	page_no = btr_node_ptr_get_child_page_no(node_ptr, offsets);

	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_index_t*	index,	/* 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;

	ulint		offsets_[REC_OFFS_NORMAL_SIZE];

	ulint*		offsets	= offsets_;

	*offsets_ = (sizeof offsets_) / sizeof *offsets_;

	ut_ad(mtr_memo_contains(mtr, dict_index_get_lock(index),

				MTR_MEMO_X_LOCK));

	ut_a(page_rec_is_user_rec(user_rec));

	ut_ad(dict_index_get_page(index) != buf_frame_get_page_no(page));

	heap = mem_heap_create(100);

	tuple = dict_index_build_node_ptr(index, user_rec, 0, heap,

					  btr_page_get_level(page, mtr));

	btr_cur_search_to_nth_level(index,

				    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);

	offsets = rec_get_offsets(node_ptr, index, offsets,

				  ULINT_UNDEFINED, &heap);

	if (UNIV_UNLIKELY(btr_node_ptr_get_child_page_no(node_ptr, offsets)

			  != buf_frame_get_page_no(page))) {

		rec_t*	print_rec;

		fputs("InnoDB: Dump of the child page:\n", stderr);

		buf_page_print(buf_frame_align(page));

		fputs("InnoDB: Dump of the parent page:\n", stderr);

		buf_page_print(buf_frame_align(node_ptr));

		fputs("InnoDB: Corruption of an index tree: table ", stderr);

		ut_print_name(stderr, NULL, TRUE, index->table_name);

		fputs(", index ", stderr);

		ut_print_name(stderr, NULL, FALSE, index->name);

		fprintf(stderr, ",\n"

			"InnoDB: father ptr page no %lu, child page no %lu\n",

			(ulong)

			btr_node_ptr_get_child_page_no(node_ptr, offsets),

			(ulong) buf_frame_get_page_no(page));

		print_rec = page_rec_get_next(page_get_infimum_rec(page));

		offsets = rec_get_offsets(print_rec, index,

					  offsets, ULINT_UNDEFINED, &heap);

		page_rec_print(print_rec, offsets);

		offsets = rec_get_offsets(node_ptr, index, offsets,

					  ULINT_UNDEFINED, &heap);

		page_rec_print(node_ptr, offsets);

		fputs("InnoDB: You should dump + drop + reimport the table"

		      " to fix the\n"

		      "InnoDB: corruption. If the crash happens at "

		      "the database startup, see\n"

		      "InnoDB: http://dev.mysql.com/doc/refman/5.1/en/"

		      "forcing-recovery.html about\n"

		      "InnoDB: forcing recovery. "

		      "Then dump + drop + reimport.\n", stderr);

	}

	ut_a(btr_node_ptr_get_child_page_no(node_ptr, offsets)

	     == 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_index_t*	index,	/* 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(

		       index, 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 */

	ulint	comp,	/* in: nonzero=compact page format */

	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);

#ifdef UNIV_SYNC_DEBUG

		buf_page_dbg_add_level(ibuf_hdr_frame, SYNC_TREE_NODE_NEW);

#endif /* UNIV_SYNC_DEBUG */

		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);

#ifdef UNIV_SYNC_DEBUG

	buf_page_dbg_add_level(frame, SYNC_TREE_NODE_NEW);

#endif /* UNIV_SYNC_DEBUG */

	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: */

#ifdef UNIV_SYNC_DEBUG

		buf_page_dbg_add_level(frame, SYNC_TREE_NODE_NEW);

#endif /* UNIV_SYNC_DEBUG */

	}

	/* Create a new index page on the the allocated segment page */

	page = page_create(frame, mtr, comp);

	buf_block_align(page)->check_index_page_at_flush = TRUE;

	/* 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. */

static

void

btr_page_reorganize_low(

/*====================*/

	ibool		recovery,/* in: TRUE if called in recovery:

				locks should not be updated, i.e.,

				there cannot exist locks on the

				page, and a hash index should not be

				dropped: it cannot exist */

	page_t*		page,	/* in: page to be reorganized */

	dict_index_t*	index,	/* in: record descriptor */

	mtr_t*		mtr)	/* in: mtr */

{

	page_t*	new_page;

	ulint	log_mode;

	ulint	data_size1;

	ulint	data_size2;

	ulint	max_ins_size1;

	ulint	max_ins_size2;

	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),

				MTR_MEMO_PAGE_X_FIX));

	ut_ad(!!page_is_comp(page) == dict_table_is_comp(index->table));

	data_size1 = page_get_data_size(page);

	max_ins_size1 = page_get_max_insert_size_after_reorganize(page, 1);

	/* Write the log record */

	mlog_open_and_write_index(mtr, page, index, page_is_comp(page)

				  ? MLOG_COMP_PAGE_REORGANIZE

				  : MLOG_PAGE_REORGANIZE, 0);

	/* 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);

	if (!recovery) {

		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, page_is_comp(page));

	buf_block_align(page)->check_index_page_at_flush = TRUE;

	/* 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),

					index, mtr);

	/* Copy max trx id to recreated page */

	page_set_max_trx_id(page, page_get_max_trx_id(new_page));

	if (!recovery) {

		/* Update the record lock bitmaps */

		lock_move_reorganize_page(page, new_page);

	}