← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/include/btr0btr.h

  • Committer: Brian Aker
  • Date: 2009-01-24 09:43:35 UTC
  • Revision ID: brian@gir-3.local-20090124094335-6qdtvc35gl5fvivz
Adding in an example singe thread scheduler

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/include/btr0btr.h
1
 
/*****************************************************************************
2
 
 
3
 
Copyright (c) 1994, 2009, Innobase Oy. All Rights Reserved.
4
 
 
5
 
This program is free software; you can redistribute it and/or modify it under
6
 
the terms of the GNU General Public License as published by the Free Software
7
 
Foundation; version 2 of the License.
8
 
 
9
 
This program is distributed in the hope that it will be useful, but WITHOUT
10
 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
 
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
 
 
13
 
You should have received a copy of the GNU General Public License along with
14
 
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
15
 
Place, Suite 330, Boston, MA 02111-1307 USA
16
 
 
17
 
*****************************************************************************/
18
 
 
19
 
/**************************************************//**
20
 
@file include/btr0btr.h
 
1
/******************************************************
21
2
The B-tree
22
3
 
 
4
(c) 1994-1996 Innobase Oy
 
5
 
23
6
Created 6/2/1994 Heikki Tuuri
24
7
*******************************************************/
25
8
 
31
14
#include "dict0dict.h"
32
15
#include "data0data.h"
33
16
#include "page0cur.h"
 
17
#include "rem0rec.h"
34
18
#include "mtr0mtr.h"
35
19
#include "btr0types.h"
36
20
 
37
 
#ifndef UNIV_HOTBACKUP
38
 
/** Maximum record size which can be stored on a page, without using the
 
21
/* Maximum record size which can be stored on a page, without using the
39
22
special big record storage structure */
 
23
 
40
24
#define BTR_PAGE_MAX_REC_SIZE   (UNIV_PAGE_SIZE / 2 - 200)
41
25
 
42
 
/** @brief Maximum depth of a B-tree in InnoDB.
43
 
 
44
 
Note that this isn't a maximum as such; none of the tree operations
45
 
avoid producing trees bigger than this. It is instead a "max depth
46
 
that other code must work with", useful for e.g.  fixed-size arrays
47
 
that must store some information about each level in a tree. In other
48
 
words: if a B-tree with bigger depth than this is encountered, it is
49
 
not acceptable for it to lead to mysterious memory corruption, but it
50
 
is acceptable for the program to die with a clear assert failure. */
 
26
/* Maximum depth of a B-tree in InnoDB. Note that this isn't a maximum as
 
27
such; none of the tree operations avoid producing trees bigger than this. It
 
28
is instead a "max depth that other code must work with", useful for e.g.
 
29
fixed-size arrays that must store some information about each level in a
 
30
tree. In other words: if a B-tree with bigger depth than this is
 
31
encountered, it is not acceptable for it to lead to mysterious memory
 
32
corruption, but it is acceptable for the program to die with a clear assert
 
33
failure. */
51
34
#define BTR_MAX_LEVELS          100
52
35
 
53
 
/** Latching modes for btr_cur_search_to_nth_level(). */
54
 
enum btr_latch_mode {
55
 
        /** Search a record on a leaf page and S-latch it. */
56
 
        BTR_SEARCH_LEAF = RW_S_LATCH,
57
 
        /** (Prepare to) modify a record on a leaf page and X-latch it. */
58
 
        BTR_MODIFY_LEAF = RW_X_LATCH,
59
 
        /** Obtain no latches. */
60
 
        BTR_NO_LATCHES = RW_NO_LATCH,
61
 
        /** Start modifying the entire B-tree. */
62
 
        BTR_MODIFY_TREE = 33,
63
 
        /** Continue modifying the entire B-tree. */
64
 
        BTR_CONT_MODIFY_TREE = 34,
65
 
        /** Search the previous record. */
66
 
        BTR_SEARCH_PREV = 35,
67
 
        /** Modify the previous record. */
68
 
        BTR_MODIFY_PREV = 36
69
 
};
 
36
/* Latching modes for btr_cur_search_to_nth_level(). */
 
37
#define BTR_SEARCH_LEAF         RW_S_LATCH
 
38
#define BTR_MODIFY_LEAF         RW_X_LATCH
 
39
#define BTR_NO_LATCHES          RW_NO_LATCH
 
40
#define BTR_MODIFY_TREE         33
 
41
#define BTR_CONT_MODIFY_TREE    34
 
42
#define BTR_SEARCH_PREV         35
 
43
#define BTR_MODIFY_PREV         36
70
44
 
71
 
/** If this is ORed to btr_latch_mode, it means that the search tuple
72
 
will be inserted to the index, at the searched position */
 
45
/* If this is ORed to the latch mode, it means that the search tuple will be
 
46
inserted to the index, at the searched position */
73
47
#define BTR_INSERT              512
74
48
 
75
 
/** This flag ORed to btr_latch_mode says that we do the search in query
 
49
/* This flag ORed to latch mode says that we do the search in query
76
50
optimization */
77
51
#define BTR_ESTIMATE            1024
78
52
 
79
 
/** This flag ORed to btr_latch_mode says that we can ignore possible
80
 
UNIQUE definition on secondary indexes when we decide if we can use
81
 
the insert buffer to speed up inserts */
 
53
/* This flag ORed to latch mode says that we can ignore possible
 
54
UNIQUE definition on secondary indexes when we decide if we can use the
 
55
insert buffer to speed up inserts */
82
56
#define BTR_IGNORE_SEC_UNIQUE   2048
83
57
 
84
 
/**************************************************************//**
85
 
Gets the root node of a tree and x-latches it.
86
 
@return root page, x-latched */
 
58
/******************************************************************
 
59
Gets the root node of a tree and x-latches it. */
87
60
UNIV_INTERN
88
61
page_t*
89
62
btr_root_get(
90
63
/*=========*/
91
 
        dict_index_t*   index,  /*!< in: index tree */
92
 
        mtr_t*          mtr);   /*!< in: mtr */
93
 
/**************************************************************//**
 
64
                                /* out: root page, x-latched */
 
65
        dict_index_t*   index,  /* in: index tree */
 
66
        mtr_t*          mtr);   /* in: mtr */
 
67
/******************************************************************
94
68
Gets a buffer page and declares its latching order level. */
95
69
UNIV_INLINE
96
70
buf_block_t*
97
71
btr_block_get(
98
72
/*==========*/
99
 
        ulint   space,          /*!< in: space id */
100
 
        ulint   zip_size,       /*!< in: compressed page size in bytes
 
73
        ulint   space,          /* in: space id */
 
74
        ulint   zip_size,       /* in: compressed page size in bytes
101
75
                                or 0 for uncompressed pages */
102
 
        ulint   page_no,        /*!< in: page number */
103
 
        ulint   mode,           /*!< in: latch mode */
104
 
        mtr_t*  mtr);           /*!< in: mtr */
105
 
/**************************************************************//**
 
76
        ulint   page_no,        /* in: page number */
 
77
        ulint   mode,           /* in: latch mode */
 
78
        mtr_t*  mtr);           /* in: mtr */
 
79
/******************************************************************
106
80
Gets a buffer page and declares its latching order level. */
107
81
UNIV_INLINE
108
82
page_t*
109
83
btr_page_get(
110
84
/*=========*/
111
 
        ulint   space,          /*!< in: space id */
112
 
        ulint   zip_size,       /*!< in: compressed page size in bytes
 
85
        ulint   space,          /* in: space id */
 
86
        ulint   zip_size,       /* in: compressed page size in bytes
113
87
                                or 0 for uncompressed pages */
114
 
        ulint   page_no,        /*!< in: page number */
115
 
        ulint   mode,           /*!< in: latch mode */
116
 
        mtr_t*  mtr);           /*!< in: mtr */
117
 
#endif /* !UNIV_HOTBACKUP */
118
 
/**************************************************************//**
119
 
Gets the index id field of a page.
120
 
@return index id */
 
88
        ulint   page_no,        /* in: page number */
 
89
        ulint   mode,           /* in: latch mode */
 
90
        mtr_t*  mtr);           /* in: mtr */
 
91
/******************************************************************
 
92
Gets the index id field of a page. */
121
93
UNIV_INLINE
122
94
dulint
123
95
btr_page_get_index_id(
124
96
/*==================*/
125
 
        const page_t*   page);  /*!< in: index page */
126
 
#ifndef UNIV_HOTBACKUP
127
 
/********************************************************//**
128
 
Gets the node level field in an index page.
129
 
@return level, leaf level == 0 */
 
97
                                /* out: index id */
 
98
        const page_t*   page);  /* in: index page */
 
99
/************************************************************
 
100
Gets the node level field in an index page. */
130
101
UNIV_INLINE
131
102
ulint
132
103
btr_page_get_level_low(
133
104
/*===================*/
134
 
        const page_t*   page);  /*!< in: index page */
135
 
/********************************************************//**
136
 
Gets the node level field in an index page.
137
 
@return level, leaf level == 0 */
 
105
                                /* out: level, leaf level == 0 */
 
106
        const page_t*   page);  /* in: index page */
 
107
/************************************************************
 
108
Gets the node level field in an index page. */
138
109
UNIV_INLINE
139
110
ulint
140
111
btr_page_get_level(
141
112
/*===============*/
142
 
        const page_t*   page,   /*!< in: index page */
143
 
        mtr_t*          mtr);   /*!< in: mini-transaction handle */
144
 
/********************************************************//**
145
 
Gets the next index page number.
146
 
@return next page number */
 
113
                                /* out: level, leaf level == 0 */
 
114
        const page_t*   page,   /* in: index page */
 
115
        mtr_t*          mtr);   /* in: mini-transaction handle */
 
116
/************************************************************
 
117
Gets the next index page number. */
147
118
UNIV_INLINE
148
119
ulint
149
120
btr_page_get_next(
150
121
/*==============*/
151
 
        const page_t*   page,   /*!< in: index page */
152
 
        mtr_t*          mtr);   /*!< in: mini-transaction handle */
153
 
/********************************************************//**
154
 
Gets the previous index page number.
155
 
@return prev page number */
 
122
                                /* out: next page number */
 
123
        const page_t*   page,   /* in: index page */
 
124
        mtr_t*          mtr);   /* in: mini-transaction handle */
 
125
/************************************************************
 
126
Gets the previous index page number. */
156
127
UNIV_INLINE
157
128
ulint
158
129
btr_page_get_prev(
159
130
/*==============*/
160
 
        const page_t*   page,   /*!< in: index page */
161
 
        mtr_t*          mtr);   /*!< in: mini-transaction handle */
162
 
/*************************************************************//**
 
131
                                /* out: prev page number */
 
132
        const page_t*   page,   /* in: index page */
 
133
        mtr_t*          mtr);   /* in: mini-transaction handle */
 
134
/*****************************************************************
163
135
Gets pointer to the previous user record in the tree. It is assumed
164
 
that the caller has appropriate latches on the page and its neighbor.
165
 
@return previous user record, NULL if there is none */
 
136
that the caller has appropriate latches on the page and its neighbor. */
166
137
UNIV_INTERN
167
138
rec_t*
168
139
btr_get_prev_user_rec(
169
140
/*==================*/
170
 
        rec_t*  rec,    /*!< in: record on leaf level */
171
 
        mtr_t*  mtr);   /*!< in: mtr holding a latch on the page, and if
 
141
                        /* out: previous user record, NULL if there is none */
 
142
        rec_t*  rec,    /* in: record on leaf level */
 
143
        mtr_t*  mtr);   /* in: mtr holding a latch on the page, and if
172
144
                        needed, also to the previous page */
173
 
/*************************************************************//**
 
145
/*****************************************************************
174
146
Gets pointer to the next user record in the tree. It is assumed
175
 
that the caller has appropriate latches on the page and its neighbor.
176
 
@return next user record, NULL if there is none */
 
147
that the caller has appropriate latches on the page and its neighbor. */
177
148
UNIV_INTERN
178
149
rec_t*
179
150
btr_get_next_user_rec(
180
151
/*==================*/
181
 
        rec_t*  rec,    /*!< in: record on leaf level */
182
 
        mtr_t*  mtr);   /*!< in: mtr holding a latch on the page, and if
 
152
                        /* out: next user record, NULL if there is none */
 
153
        rec_t*  rec,    /* in: record on leaf level */
 
154
        mtr_t*  mtr);   /* in: mtr holding a latch on the page, and if
183
155
                        needed, also to the next page */
184
 
/**************************************************************//**
 
156
/******************************************************************
185
157
Releases the latch on a leaf page and bufferunfixes it. */
186
158
UNIV_INLINE
187
159
void
188
160
btr_leaf_page_release(
189
161
/*==================*/
190
 
        buf_block_t*    block,          /*!< in: buffer block */
191
 
        ulint           latch_mode,     /*!< in: BTR_SEARCH_LEAF or
 
162
        buf_block_t*    block,          /* in: buffer block */
 
163
        ulint           latch_mode,     /* in: BTR_SEARCH_LEAF or
192
164
                                        BTR_MODIFY_LEAF */
193
 
        mtr_t*          mtr);           /*!< in: mtr */
194
 
/**************************************************************//**
195
 
Gets the child node file address in a node pointer.
196
 
@return child node address */
 
165
        mtr_t*          mtr);           /* in: mtr */
 
166
/******************************************************************
 
167
Gets the child node file address in a node pointer. */
197
168
UNIV_INLINE
198
169
ulint
199
170
btr_node_ptr_get_child_page_no(
200
171
/*===========================*/
201
 
        const rec_t*    rec,    /*!< in: node pointer record */
202
 
        const ulint*    offsets);/*!< in: array returned by rec_get_offsets() */
203
 
/************************************************************//**
204
 
Creates the root node for a new index tree.
205
 
@return page number of the created root, FIL_NULL if did not succeed */
 
172
                                /* out: child node address */
 
173
        const rec_t*    rec,    /* in: node pointer record */
 
174
        const ulint*    offsets);/* in: array returned by rec_get_offsets() */
 
175
/****************************************************************
 
176
Creates the root node for a new index tree. */
206
177
UNIV_INTERN
207
178
ulint
208
179
btr_create(
209
180
/*=======*/
210
 
        ulint           type,   /*!< in: type of the index */
211
 
        ulint           space,  /*!< in: space where created */
212
 
        ulint           zip_size,/*!< in: compressed page size in bytes
 
181
                                /* out: page number of the created root,
 
182
                                FIL_NULL if did not succeed */
 
183
        ulint           type,   /* in: type of the index */
 
184
        ulint           space,  /* in: space where created */
 
185
        ulint           zip_size,/* in: compressed page size in bytes
213
186
                                or 0 for uncompressed pages */
214
 
        dulint          index_id,/*!< in: index id */
215
 
        dict_index_t*   index,  /*!< in: index */
216
 
        mtr_t*          mtr);   /*!< in: mini-transaction handle */
217
 
/************************************************************//**
 
187
        dulint          index_id,/* in: index id */
 
188
        dict_index_t*   index,  /* in: index */
 
189
        mtr_t*          mtr);   /* in: mini-transaction handle */
 
190
/****************************************************************
218
191
Frees a B-tree except the root page, which MUST be freed after this
219
192
by calling btr_free_root. */
220
193
UNIV_INTERN
221
194
void
222
195
btr_free_but_not_root(
223
196
/*==================*/
224
 
        ulint   space,          /*!< in: space where created */
225
 
        ulint   zip_size,       /*!< in: compressed page size in bytes
 
197
        ulint   space,          /* in: space where created */
 
198
        ulint   zip_size,       /* in: compressed page size in bytes
226
199
                                or 0 for uncompressed pages */
227
 
        ulint   root_page_no);  /*!< in: root page number */
228
 
/************************************************************//**
 
200
        ulint   root_page_no);  /* in: root page number */
 
201
/****************************************************************
229
202
Frees the B-tree root page. Other tree MUST already have been freed. */
230
203
UNIV_INTERN
231
204
void
232
205
btr_free_root(
233
206
/*==========*/
234
 
        ulint   space,          /*!< in: space where created */
235
 
        ulint   zip_size,       /*!< in: compressed page size in bytes
 
207
        ulint   space,          /* in: space where created */
 
208
        ulint   zip_size,       /* in: compressed page size in bytes
236
209
                                or 0 for uncompressed pages */
237
 
        ulint   root_page_no,   /*!< in: root page number */
238
 
        mtr_t*  mtr);           /*!< in: a mini-transaction which has already
 
210
        ulint   root_page_no,   /* in: root page number */
 
211
        mtr_t*  mtr);           /* in: a mini-transaction which has already
239
212
                                been started */
240
 
/*************************************************************//**
 
213
/*****************************************************************
241
214
Makes tree one level higher by splitting the root, and inserts
242
215
the tuple. It is assumed that mtr contains an x-latch on the tree.
243
216
NOTE that the operation of this function must always succeed,
244
217
we cannot reverse it: therefore enough free disk space must be
245
 
guaranteed to be available before this function is called.
246
 
@return inserted record */
 
218
guaranteed to be available before this function is called. */
247
219
UNIV_INTERN
248
220
rec_t*
249
221
btr_root_raise_and_insert(
250
222
/*======================*/
251
 
        btr_cur_t*      cursor, /*!< in: cursor at which to insert: must be
 
223
                                /* out: inserted record */
 
224
        btr_cur_t*      cursor, /* in: cursor at which to insert: must be
252
225
                                on the root page; when the function returns,
253
226
                                the cursor is positioned on the predecessor
254
227
                                of the inserted record */
255
 
        const dtuple_t* tuple,  /*!< in: tuple to insert */
256
 
        ulint           n_ext,  /*!< in: number of externally stored columns */
257
 
        mtr_t*          mtr);   /*!< in: mtr */
258
 
/*************************************************************//**
 
228
        const dtuple_t* tuple,  /* in: tuple to insert */
 
229
        ulint           n_ext,  /* in: number of externally stored columns */
 
230
        mtr_t*          mtr);   /* in: mtr */
 
231
/*****************************************************************
259
232
Reorganizes an index page.
260
233
IMPORTANT: if btr_page_reorganize() is invoked on a compressed leaf
261
234
page of a non-clustered index, the caller must update the insert
262
235
buffer free bits in the same mini-transaction in such a way that the
263
 
modification will be redo-logged.
264
 
@return TRUE on success, FALSE on failure */
 
236
modification will be redo-logged. */
265
237
UNIV_INTERN
266
238
ibool
267
239
btr_page_reorganize(
268
240
/*================*/
269
 
        buf_block_t*    block,  /*!< in: page to be reorganized */
270
 
        dict_index_t*   index,  /*!< in: record descriptor */
271
 
        mtr_t*          mtr);   /*!< in: mtr */
272
 
/*************************************************************//**
 
241
                                /* out: TRUE on success, FALSE on failure */
 
242
        buf_block_t*    block,  /* in: page to be reorganized */
 
243
        dict_index_t*   index,  /* in: record descriptor */
 
244
        mtr_t*          mtr);   /* in: mtr */
 
245
/*****************************************************************
273
246
Decides if the page should be split at the convergence point of
274
 
inserts converging to left.
275
 
@return TRUE if split recommended */
 
247
inserts converging to left. */
276
248
UNIV_INTERN
277
249
ibool
278
250
btr_page_get_split_rec_to_left(
279
251
/*===========================*/
280
 
        btr_cur_t*      cursor, /*!< in: cursor at which to insert */
281
 
        rec_t**         split_rec);/*!< out: if split recommended,
 
252
                                /* out: TRUE if split recommended */
 
253
        btr_cur_t*      cursor, /* in: cursor at which to insert */
 
254
        rec_t**         split_rec);/* out: if split recommended,
282
255
                                the first record on upper half page,
283
256
                                or NULL if tuple should be first */
284
 
/*************************************************************//**
 
257
/*****************************************************************
285
258
Decides if the page should be split at the convergence point of
286
 
inserts converging to right.
287
 
@return TRUE if split recommended */
 
259
inserts converging to right. */
288
260
UNIV_INTERN
289
261
ibool
290
262
btr_page_get_split_rec_to_right(
291
263
/*============================*/
292
 
        btr_cur_t*      cursor, /*!< in: cursor at which to insert */
293
 
        rec_t**         split_rec);/*!< out: if split recommended,
 
264
                                /* out: TRUE if split recommended */
 
265
        btr_cur_t*      cursor, /* in: cursor at which to insert */
 
266
        rec_t**         split_rec);/* out: if split recommended,
294
267
                                the first record on upper half page,
295
268
                                or NULL if tuple should be first */
296
 
/*************************************************************//**
 
269
/*****************************************************************
297
270
Splits an index page to halves and inserts the tuple. It is assumed
298
 
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
299
 
released within this function! NOTE that the operation of this
300
 
function must always succeed, we cannot reverse it: therefore enough
301
 
free disk space (2 pages) must be guaranteed to be available before
302
 
this function is called.
303
 
 
304
 
@return inserted record */
 
271
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
 
272
is released within this function! NOTE that the operation of this
 
273
function must always succeed, we cannot reverse it: therefore
 
274
enough free disk space must be guaranteed to be available before
 
275
this function is called. */
305
276
UNIV_INTERN
306
277
rec_t*
307
278
btr_page_split_and_insert(
308
279
/*======================*/
309
 
        btr_cur_t*      cursor, /*!< in: cursor at which to insert; when the
 
280
                                /* out: inserted record; NOTE: the tree
 
281
                                x-latch is released! NOTE: 2 free disk
 
282
                                pages must be available! */
 
283
        btr_cur_t*      cursor, /* in: cursor at which to insert; when the
310
284
                                function returns, the cursor is positioned
311
285
                                on the predecessor of the inserted record */
312
 
        const dtuple_t* tuple,  /*!< in: tuple to insert */
313
 
        ulint           n_ext,  /*!< in: number of externally stored columns */
314
 
        mtr_t*          mtr);   /*!< in: mtr */
315
 
/*******************************************************//**
 
286
        const dtuple_t* tuple,  /* in: tuple to insert */
 
287
        ulint           n_ext,  /* in: number of externally stored columns */
 
288
        mtr_t*          mtr);   /* in: mtr */
 
289
/***********************************************************
316
290
Inserts a data tuple to a tree on a non-leaf level. It is assumed
317
291
that mtr holds an x-latch on the tree. */
318
292
UNIV_INTERN
319
293
void
320
294
btr_insert_on_non_leaf_level(
321
295
/*=========================*/
322
 
        dict_index_t*   index,  /*!< in: index */
323
 
        ulint           level,  /*!< in: level, must be > 0 */
324
 
        dtuple_t*       tuple,  /*!< in: the record to be inserted */
325
 
        mtr_t*          mtr);   /*!< in: mtr */
326
 
#endif /* !UNIV_HOTBACKUP */
327
 
/****************************************************************//**
 
296
        dict_index_t*   index,  /* in: index */
 
297
        ulint           level,  /* in: level, must be > 0 */
 
298
        dtuple_t*       tuple,  /* in: the record to be inserted */
 
299
        mtr_t*          mtr);   /* in: mtr */
 
300
/********************************************************************
328
301
Sets a record as the predefined minimum record. */
329
302
UNIV_INTERN
330
303
void
331
304
btr_set_min_rec_mark(
332
305
/*=================*/
333
 
        rec_t*  rec,    /*!< in/out: record */
334
 
        mtr_t*  mtr);   /*!< in: mtr */
335
 
#ifndef UNIV_HOTBACKUP
336
 
/*************************************************************//**
 
306
        rec_t*  rec,    /* in/out: record */
 
307
        mtr_t*  mtr);   /* in: mtr */
 
308
/*****************************************************************
337
309
Deletes on the upper level the node pointer to a page. */
338
310
UNIV_INTERN
339
311
void
340
312
btr_node_ptr_delete(
341
313
/*================*/
342
 
        dict_index_t*   index,  /*!< in: index tree */
343
 
        buf_block_t*    block,  /*!< in: page whose node pointer is deleted */
344
 
        mtr_t*          mtr);   /*!< in: mtr */
 
314
        dict_index_t*   index,  /* in: index tree */
 
315
        buf_block_t*    block,  /* in: page whose node pointer is deleted */
 
316
        mtr_t*          mtr);   /* in: mtr */
345
317
#ifdef UNIV_DEBUG
346
 
/************************************************************//**
347
 
Checks that the node pointer to a page is appropriate.
348
 
@return TRUE */
 
318
/****************************************************************
 
319
Checks that the node pointer to a page is appropriate. */
349
320
UNIV_INTERN
350
321
ibool
351
322
btr_check_node_ptr(
352
323
/*===============*/
353
 
        dict_index_t*   index,  /*!< in: index tree */
354
 
        buf_block_t*    block,  /*!< in: index page */
355
 
        mtr_t*          mtr);   /*!< in: mtr */
 
324
                                /* out: TRUE */
 
325
        dict_index_t*   index,  /* in: index tree */
 
326
        buf_block_t*    block,  /* in: index page */
 
327
        mtr_t*          mtr);   /* in: mtr */
356
328
#endif /* UNIV_DEBUG */
357
 
/*************************************************************//**
 
329
/*****************************************************************
358
330
Tries to merge the page first to the left immediate brother if such a
359
331
brother exists, and the node pointers to the current page and to the
360
332
brother reside on the same page. If the left brother does not satisfy these
362
334
level lifts the records of the page to the father page, thus reducing the
363
335
tree height. It is assumed that mtr holds an x-latch on the tree and on the
364
336
page. If cursor is on the leaf level, mtr must also hold x-latches to
365
 
the brothers, if they exist.
366
 
@return TRUE on success */
 
337
the brothers, if they exist. */
367
338
UNIV_INTERN
368
339
ibool
369
340
btr_compress(
370
341
/*=========*/
371
 
        btr_cur_t*      cursor, /*!< in: cursor on the page to merge or lift;
 
342
                                /* out: TRUE on success */
 
343
        btr_cur_t*      cursor, /* in: cursor on the page to merge or lift;
372
344
                                the page must not be empty: in record delete
373
345
                                use btr_discard_page if the page would become
374
346
                                empty */
375
 
        mtr_t*          mtr);   /*!< in: mtr */
376
 
/*************************************************************//**
 
347
        mtr_t*          mtr);   /* in: mtr */
 
348
/*****************************************************************
377
349
Discards a page from a B-tree. This is used to remove the last record from
378
350
a B-tree page: the whole page must be removed at the same time. This cannot
379
351
be used for the root page, which is allowed to be empty. */
381
353
void
382
354
btr_discard_page(
383
355
/*=============*/
384
 
        btr_cur_t*      cursor, /*!< in: cursor on the page to discard: not on
 
356
        btr_cur_t*      cursor, /* in: cursor on the page to discard: not on
385
357
                                the root page */
386
 
        mtr_t*          mtr);   /*!< in: mtr */
387
 
#endif /* !UNIV_HOTBACKUP */
388
 
/****************************************************************//**
 
358
        mtr_t*          mtr);   /* in: mtr */
 
359
/********************************************************************
389
360
Parses the redo log record for setting an index record as the predefined
390
 
minimum record.
391
 
@return end of log record or NULL */
 
361
minimum record. */
392
362
UNIV_INTERN
393
363
byte*
394
364
btr_parse_set_min_rec_mark(
395
365
/*=======================*/
396
 
        byte*   ptr,    /*!< in: buffer */
397
 
        byte*   end_ptr,/*!< in: buffer end */
398
 
        ulint   comp,   /*!< in: nonzero=compact page format */
399
 
        page_t* page,   /*!< in: page or NULL */
400
 
        mtr_t*  mtr);   /*!< in: mtr or NULL */
401
 
/***********************************************************//**
402
 
Parses a redo log record of reorganizing a page.
403
 
@return end of log record or NULL */
 
366
                        /* out: end of log record or NULL */
 
367
        byte*   ptr,    /* in: buffer */
 
368
        byte*   end_ptr,/* in: buffer end */
 
369
        ulint   comp,   /* in: nonzero=compact page format */
 
370
        page_t* page,   /* in: page or NULL */
 
371
        mtr_t*  mtr);   /* in: mtr or NULL */
 
372
/***************************************************************
 
373
Parses a redo log record of reorganizing a page. */
404
374
UNIV_INTERN
405
375
byte*
406
376
btr_parse_page_reorganize(
407
377
/*======================*/
408
 
        byte*           ptr,    /*!< in: buffer */
409
 
        byte*           end_ptr,/*!< in: buffer end */
410
 
        dict_index_t*   index,  /*!< in: record descriptor */
411
 
        buf_block_t*    block,  /*!< in: page to be reorganized, or NULL */
412
 
        mtr_t*          mtr);   /*!< in: mtr or NULL */
413
 
#ifndef UNIV_HOTBACKUP
414
 
/**************************************************************//**
415
 
Gets the number of pages in a B-tree.
416
 
@return number of pages */
 
378
                                /* out: end of log record or NULL */
 
379
        byte*           ptr,    /* in: buffer */
 
380
        byte*           end_ptr,/* in: buffer end */
 
381
        dict_index_t*   index,  /* in: record descriptor */
 
382
        buf_block_t*    block,  /* in: page to be reorganized, or NULL */
 
383
        mtr_t*          mtr);   /* in: mtr or NULL */
 
384
/******************************************************************
 
385
Gets the number of pages in a B-tree. */
417
386
UNIV_INTERN
418
387
ulint
419
388
btr_get_size(
420
389
/*=========*/
421
 
        dict_index_t*   index,  /*!< in: index */
422
 
        ulint           flag);  /*!< in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
423
 
/**************************************************************//**
 
390
                                /* out: number of pages */
 
391
        dict_index_t*   index,  /* in: index */
 
392
        ulint           flag);  /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
 
393
/******************************************************************
424
394
Allocates a new file page to be used in an index tree. NOTE: we assume
425
 
that the caller has made the reservation for free extents!
426
 
@return new allocated block, x-latched; NULL if out of space */
 
395
that the caller has made the reservation for free extents! */
427
396
UNIV_INTERN
428
397
buf_block_t*
429
398
btr_page_alloc(
430
399
/*===========*/
431
 
        dict_index_t*   index,          /*!< in: index tree */
432
 
        ulint           hint_page_no,   /*!< in: hint of a good page */
433
 
        byte            file_direction, /*!< in: direction where a possible
 
400
                                        /* out: new allocated block, x-latched;
 
401
                                        NULL if out of space */
 
402
        dict_index_t*   index,          /* in: index tree */
 
403
        ulint           hint_page_no,   /* in: hint of a good page */
 
404
        byte            file_direction, /* in: direction where a possible
434
405
                                        page split is made */
435
 
        ulint           level,          /*!< in: level where the page is placed
 
406
        ulint           level,          /* in: level where the page is placed
436
407
                                        in the tree */
437
 
        mtr_t*          mtr);           /*!< in: mtr */
438
 
/**************************************************************//**
 
408
        mtr_t*          mtr);           /* in: mtr */
 
409
/******************************************************************
439
410
Frees a file page used in an index tree. NOTE: cannot free field external
440
411
storage pages because the page must contain info on its level. */
441
412
UNIV_INTERN
442
413
void
443
414
btr_page_free(
444
415
/*==========*/
445
 
        dict_index_t*   index,  /*!< in: index tree */
446
 
        buf_block_t*    block,  /*!< in: block to be freed, x-latched */
447
 
        mtr_t*          mtr);   /*!< in: mtr */
448
 
/**************************************************************//**
 
416
        dict_index_t*   index,  /* in: index tree */
 
417
        buf_block_t*    block,  /* in: block to be freed, x-latched */
 
418
        mtr_t*          mtr);   /* in: mtr */
 
419
/******************************************************************
449
420
Frees a file page used in an index tree. Can be used also to BLOB
450
421
external storage pages, because the page level 0 can be given as an
451
422
argument. */
453
424
void
454
425
btr_page_free_low(
455
426
/*==============*/
456
 
        dict_index_t*   index,  /*!< in: index tree */
457
 
        buf_block_t*    block,  /*!< in: block to be freed, x-latched */
458
 
        ulint           level,  /*!< in: page level */
459
 
        mtr_t*          mtr);   /*!< in: mtr */
 
427
        dict_index_t*   index,  /* in: index tree */
 
428
        buf_block_t*    block,  /* in: block to be freed, x-latched */
 
429
        ulint           level,  /* in: page level */
 
430
        mtr_t*          mtr);   /* in: mtr */
460
431
#ifdef UNIV_BTR_PRINT
461
 
/*************************************************************//**
 
432
/*****************************************************************
462
433
Prints size info of a B-tree. */
463
434
UNIV_INTERN
464
435
void
465
436
btr_print_size(
466
437
/*===========*/
467
 
        dict_index_t*   index); /*!< in: index tree */
468
 
/**************************************************************//**
 
438
        dict_index_t*   index); /* in: index tree */
 
439
/******************************************************************
469
440
Prints directories and other info of all nodes in the index. */
470
441
UNIV_INTERN
471
442
void
472
443
btr_print_index(
473
444
/*============*/
474
 
        dict_index_t*   index,  /*!< in: index */
475
 
        ulint           width); /*!< in: print this many entries from start
 
445
        dict_index_t*   index,  /* in: index */
 
446
        ulint           width); /* in: print this many entries from start
476
447
                                and end */
477
448
#endif /* UNIV_BTR_PRINT */
478
 
/************************************************************//**
 
449
/****************************************************************
479
450
Checks the size and number of fields in a record based on the definition of
480
 
the index.
481
 
@return TRUE if ok */
 
451
the index. */
482
452
UNIV_INTERN
483
453
ibool
484
454
btr_index_rec_validate(
485
455
/*===================*/
486
 
        const rec_t*            rec,            /*!< in: index record */
487
 
        const dict_index_t*     index,          /*!< in: index */
488
 
        ibool                   dump_on_error); /*!< in: TRUE if the function
 
456
                                                /* out: TRUE if ok */
 
457
        const rec_t*            rec,            /* in: index record */
 
458
        const dict_index_t*     index,          /* in: index */
 
459
        ibool                   dump_on_error); /* in: TRUE if the function
489
460
                                                should print hex dump of record
490
461
                                                and page on error */
491
 
/**************************************************************//**
492
 
Checks the consistency of an index tree.
493
 
@return TRUE if ok */
 
462
/******************************************************************
 
463
Checks the consistency of an index tree. */
494
464
UNIV_INTERN
495
465
ibool
496
466
btr_validate_index(
497
467
/*===============*/
498
 
        dict_index_t*   index,  /*!< in: index */
499
 
        trx_t*          trx);   /*!< in: transaction or NULL */
 
468
                                /* out: TRUE if ok */
 
469
        dict_index_t*   index,  /* in: index */
 
470
        trx_t*          trx);   /* in: transaction or NULL */
500
471
 
501
472
#define BTR_N_LEAF_PAGES        1
502
473
#define BTR_TOTAL_SIZE          2
503
 
#endif /* !UNIV_HOTBACKUP */
504
474
 
505
475
#ifndef UNIV_NONINL
506
476
#include "btr0btr.ic"