diff options
author | Guilhem Bichot <guilhem@mysql.com> | 2009-08-04 13:25:19 +0200 |
---|---|---|
committer | Guilhem Bichot <guilhem@mysql.com> | 2009-08-04 13:25:19 +0200 |
commit | b57e4dbd88671df86e2cf39aff5178976d710b64 (patch) | |
tree | 32be2bfec3ca062c65566c60ecf59b673d1f97e9 /storage/innobase/include/btr0btr.h | |
parent | 1a0c2153a036296785dcdfa7b5f4974515616e11 (diff) | |
parent | 94efc1c6b084ed531b513e70fb66e7b7a1186b56 (diff) | |
download | mariadb-git-b57e4dbd88671df86e2cf39aff5178976d710b64.tar.gz |
Creation of mysql-trunk = {summit + "Innodb plugin replacing the builtin"}:
bzr branch mysql-5.1-performance-version mysql-trunk # Summit
cd mysql-trunk
bzr merge mysql-5.1-innodb_plugin # which is 5.1 + Innodb plugin
bzr rm innobase # remove the builtin
Next step: build, test fixes.
Diffstat (limited to 'storage/innobase/include/btr0btr.h')
-rw-r--r-- | storage/innobase/include/btr0btr.h | 451 |
1 files changed, 0 insertions, 451 deletions
diff --git a/storage/innobase/include/btr0btr.h b/storage/innobase/include/btr0btr.h deleted file mode 100644 index 1573de7e818..00000000000 --- a/storage/innobase/include/btr0btr.h +++ /dev/null @@ -1,451 +0,0 @@ -/****************************************************** -The B-tree - -(c) 1994-1996 Innobase Oy - -Created 6/2/1994 Heikki Tuuri -*******************************************************/ - -#ifndef btr0btr_h -#define btr0btr_h - -#include "univ.i" - -#include "dict0dict.h" -#include "data0data.h" -#include "page0cur.h" -#include "rem0rec.h" -#include "mtr0mtr.h" -#include "btr0types.h" - -/* Maximum record size which can be stored on a page, without using the -special big record storage structure */ - -#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200) - -/* Maximum depth of a B-tree in InnoDB. Note that this isn't a maximum as -such; none of the tree operations avoid producing trees bigger than this. It -is instead a "max depth that other code must work with", useful for e.g. -fixed-size arrays that must store some information about each level in a -tree. In other words: if a B-tree with bigger depth than this is -encountered, it is not acceptable for it to lead to mysterious memory -corruption, but it is acceptable for the program to die with a clear assert -failure. */ -#define BTR_MAX_LEVELS 100 - -/* Latching modes for btr_cur_search_to_nth_level(). */ -#define BTR_SEARCH_LEAF RW_S_LATCH -#define BTR_MODIFY_LEAF RW_X_LATCH -#define BTR_NO_LATCHES RW_NO_LATCH -#define BTR_MODIFY_TREE 33 -#define BTR_CONT_MODIFY_TREE 34 -#define BTR_SEARCH_PREV 35 -#define BTR_MODIFY_PREV 36 - -/* If this is ORed to the latch mode, it means that the search tuple will be -inserted to the index, at the searched position */ -#define BTR_INSERT 512 - -/* This flag ORed to latch mode says that we do the search in query -optimization */ -#define BTR_ESTIMATE 1024 - -/* This flag ORed to latch mode says that we can ignore possible -UNIQUE definition on secondary indexes when we decide if we can use the -insert buffer to speed up inserts */ -#define BTR_IGNORE_SEC_UNIQUE 2048 - -/****************************************************************** -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 */ -/****************************************************************** -Gets a buffer page and declares its latching order level. */ -UNIV_INLINE -page_t* -btr_page_get( -/*=========*/ - ulint space, /* in: space id */ - ulint page_no, /* in: page number */ - ulint mode, /* in: latch mode */ - mtr_t* mtr); /* in: mtr */ -/****************************************************************** -Gets the index id field of a page. */ -UNIV_INLINE -dulint -btr_page_get_index_id( -/*==================*/ - /* out: index id */ - page_t* page); /* in: index page */ -/************************************************************ -Gets the node level field in an index page. */ -UNIV_INLINE -ulint -btr_page_get_level_low( -/*===================*/ - /* out: level, leaf level == 0 */ - page_t* page); /* in: index page */ -/************************************************************ -Gets the node level field in an index page. */ -UNIV_INLINE -ulint -btr_page_get_level( -/*===============*/ - /* out: level, leaf level == 0 */ - page_t* page, /* in: index page */ - mtr_t* mtr); /* in: mini-transaction handle */ -/************************************************************ -Gets the next index page number. */ -UNIV_INLINE -ulint -btr_page_get_next( -/*==============*/ - /* out: next page number */ - page_t* page, /* in: index page */ - mtr_t* mtr); /* in: mini-transaction handle */ -/************************************************************ -Gets the previous index page number. */ -UNIV_INLINE -ulint -btr_page_get_prev( -/*==============*/ - /* out: prev page number */ - page_t* page, /* in: index page */ - mtr_t* mtr); /* in: mini-transaction handle */ -/***************************************************************** -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 */ -/***************************************************************** -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 */ -/****************************************************************** -Releases the latch on a leaf page and bufferunfixes it. */ -UNIV_INLINE -void -btr_leaf_page_release( -/*==================*/ - page_t* page, /* in: page */ - ulint latch_mode, /* in: BTR_SEARCH_LEAF or BTR_MODIFY_LEAF */ - mtr_t* mtr); /* in: mtr */ -/****************************************************************** -Gets the child node file address in a node pointer. */ -UNIV_INLINE -ulint -btr_node_ptr_get_child_page_no( -/*===========================*/ - /* out: child node address */ - rec_t* rec, /* in: node pointer record */ - const ulint* offsets);/* in: array returned by rec_get_offsets() */ -/**************************************************************** -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 */ -/**************************************************************** -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 */ -/**************************************************************** -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 */ -/***************************************************************** -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 */ -/***************************************************************** -Reorganizes an index page. */ - -void -btr_page_reorganize( -/*================*/ - page_t* page, /* in: page to be reorganized */ - dict_index_t* index, /* in: record descriptor */ - mtr_t* mtr); /* in: mtr */ -/***************************************************************** -Decides if the page should be split at the convergence point of -inserts converging to 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 should be first */ -/***************************************************************** -Decides if the page should be split at the convergence point of -inserts converging to 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 should be first */ -/***************************************************************** -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 */ -/*********************************************************** -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_index_t* index, /* in: index */ - ulint level, /* in: level, must be > 0 */ - dtuple_t* tuple, /* in: the record to be inserted */ - mtr_t* mtr); /* in: mtr */ -/******************************************************************** -Sets a record as the predefined minimum record. */ - -void -btr_set_min_rec_mark( -/*=================*/ - rec_t* rec, /* in: record */ - ulint comp, /* in: nonzero=compact page format */ - mtr_t* mtr); /* in: mtr */ -/***************************************************************** -Deletes on the upper level the node pointer to a page. */ - -void -btr_node_ptr_delete( -/*================*/ - dict_index_t* index, /* in: index tree */ - page_t* page, /* in: page whose node pointer is deleted */ - mtr_t* mtr); /* in: mtr */ -#ifdef UNIV_DEBUG -/**************************************************************** -Checks that the node pointer to a page is appropriate. */ - -ibool -btr_check_node_ptr( -/*===============*/ - /* out: TRUE */ - dict_index_t* index, /* in: index tree */ - page_t* page, /* in: index page */ - mtr_t* mtr); /* in: mtr */ -#endif /* UNIV_DEBUG */ -/***************************************************************** -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 */ -/***************************************************************** -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 */ -/******************************************************************** -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 */ - ulint comp, /* in: nonzero=compact page format */ - page_t* page, /* in: page or NULL */ - mtr_t* mtr); /* in: mtr or NULL */ -/*************************************************************** -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 */ - dict_index_t* index, /* in: record descriptor */ - page_t* page, /* in: page or NULL */ - mtr_t* mtr); /* in: mtr or NULL */ -/****************************************************************** -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 */ -/****************************************************************** -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 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. 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 */ -/****************************************************************** -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 */ -#ifdef UNIV_BTR_PRINT -/***************************************************************** -Prints size info of a B-tree. */ - -void -btr_print_size( -/*===========*/ - dict_index_t* index); /* in: index tree */ -/****************************************************************** -Prints directories and other info of all nodes in the index. */ - -void -btr_print_index( -/*============*/ - dict_index_t* index, /* in: index */ - ulint width); /* in: print this many entries from start - and end */ -#endif /* UNIV_BTR_PRINT */ -/**************************************************************** -Checks the size and number of fields in a record based on the definition of -the index. */ - -ibool -btr_index_rec_validate( -/*===================*/ - /* out: TRUE if ok */ - rec_t* rec, /* in: index record */ - dict_index_t* index, /* in: index */ - ibool dump_on_error); /* in: TRUE if the function - should print hex dump of record - and page on error */ -/****************************************************************** -Checks the consistency of an index tree. */ - -ibool -btr_validate_index( -/*===============*/ - /* out: TRUE if ok */ - dict_index_t* index, /* in: index */ - trx_t* trx); /* in: transaction or NULL */ - -#define BTR_N_LEAF_PAGES 1 -#define BTR_TOTAL_SIZE 2 - -#ifndef UNIV_NONINL -#include "btr0btr.ic" -#endif - -#endif |