1
/*****************************************************************************
3
Copyright (c) 1995, 2009, Innobase Oy. All Rights Reserved.
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.
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.
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., 51 Franklin
15
St, Fifth Floor, Boston, MA 02110-1301 USA
17
*****************************************************************************/
19
/******************************************************************//**
21
File-based list utilities
23
Created 11/28/1995 Heikki Tuuri
24
***********************************************************************/
33
#include "page0page.h"
35
/********************************************************************//**
36
Adds a node to an empty list. */
41
flst_base_node_t* base, /*!< in: pointer to base node of
43
flst_node_t* node, /*!< in: node to add */
44
mtr_t* mtr) /*!< in: mini-transaction handle */
50
ut_ad(mtr && base && node);
52
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
53
ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
54
len = flst_get_len(base, mtr);
57
buf_ptr_get_fsp_addr(node, &space, &node_addr);
59
/* Update first and last fields of base node */
60
flst_write_addr(base + FLST_FIRST, node_addr, mtr);
61
flst_write_addr(base + FLST_LAST, node_addr, mtr);
63
/* Set prev and next fields of node to add */
64
flst_write_addr(node + FLST_PREV, fil_addr_null, mtr);
65
flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr);
67
/* Update len of base node */
68
mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
71
/********************************************************************//**
72
Adds a node as the last node in a list. */
77
flst_base_node_t* base, /*!< in: pointer to base node of list */
78
flst_node_t* node, /*!< in: node to add */
79
mtr_t* mtr) /*!< in: mini-transaction handle */
85
flst_node_t* last_node;
87
ut_ad(mtr && base && node);
89
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
90
ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
91
len = flst_get_len(base, mtr);
92
last_addr = flst_get_last(base, mtr);
94
buf_ptr_get_fsp_addr(node, &space, &node_addr);
96
/* If the list is not empty, call flst_insert_after */
98
if (last_addr.page == node_addr.page) {
99
last_node = page_align(node) + last_addr.boffset;
101
ulint zip_size = fil_space_get_zip_size(space);
103
last_node = fut_get_ptr(space, zip_size, last_addr,
107
flst_insert_after(base, last_node, node, mtr);
109
/* else call flst_add_to_empty */
110
flst_add_to_empty(base, node, mtr);
114
/********************************************************************//**
115
Adds a node as the first node in a list. */
120
flst_base_node_t* base, /*!< in: pointer to base node of list */
121
flst_node_t* node, /*!< in: node to add */
122
mtr_t* mtr) /*!< in: mini-transaction handle */
125
fil_addr_t node_addr;
127
fil_addr_t first_addr;
128
flst_node_t* first_node;
130
ut_ad(mtr && base && node);
132
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
133
ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
134
len = flst_get_len(base, mtr);
135
first_addr = flst_get_first(base, mtr);
137
buf_ptr_get_fsp_addr(node, &space, &node_addr);
139
/* If the list is not empty, call flst_insert_before */
141
if (first_addr.page == node_addr.page) {
142
first_node = page_align(node) + first_addr.boffset;
144
ulint zip_size = fil_space_get_zip_size(space);
146
first_node = fut_get_ptr(space, zip_size, first_addr,
150
flst_insert_before(base, node, first_node, mtr);
152
/* else call flst_add_to_empty */
153
flst_add_to_empty(base, node, mtr);
157
/********************************************************************//**
158
Inserts a node after another in a list. */
163
flst_base_node_t* base, /*!< in: pointer to base node of list */
164
flst_node_t* node1, /*!< in: node to insert after */
165
flst_node_t* node2, /*!< in: node to add */
166
mtr_t* mtr) /*!< in: mini-transaction handle */
169
fil_addr_t node1_addr;
170
fil_addr_t node2_addr;
172
fil_addr_t node3_addr;
175
ut_ad(mtr && node1 && node2 && base);
176
ut_ad(base != node1);
177
ut_ad(base != node2);
178
ut_ad(node2 != node1);
179
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
180
ut_ad(mtr_memo_contains_page(mtr, node1, MTR_MEMO_PAGE_X_FIX));
181
ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
183
buf_ptr_get_fsp_addr(node1, &space, &node1_addr);
184
buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
186
node3_addr = flst_get_next_addr(node1, mtr);
188
/* Set prev and next fields of node2 */
189
flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
190
flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
192
if (!fil_addr_is_null(node3_addr)) {
193
/* Update prev field of node3 */
194
ulint zip_size = fil_space_get_zip_size(space);
196
node3 = fut_get_ptr(space, zip_size,
197
node3_addr, RW_X_LATCH, mtr);
198
flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
200
/* node1 was last in list: update last field in base */
201
flst_write_addr(base + FLST_LAST, node2_addr, mtr);
204
/* Set next field of node1 */
205
flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
207
/* Update len of base node */
208
len = flst_get_len(base, mtr);
209
mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
212
/********************************************************************//**
213
Inserts a node before another in a list. */
218
flst_base_node_t* base, /*!< in: pointer to base node of list */
219
flst_node_t* node2, /*!< in: node to insert */
220
flst_node_t* node3, /*!< in: node to insert before */
221
mtr_t* mtr) /*!< in: mini-transaction handle */
225
fil_addr_t node1_addr;
226
fil_addr_t node2_addr;
227
fil_addr_t node3_addr;
230
ut_ad(mtr && node2 && node3 && base);
231
ut_ad(base != node2);
232
ut_ad(base != node3);
233
ut_ad(node2 != node3);
234
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
235
ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
236
ut_ad(mtr_memo_contains_page(mtr, node3, MTR_MEMO_PAGE_X_FIX));
238
buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
239
buf_ptr_get_fsp_addr(node3, &space, &node3_addr);
241
node1_addr = flst_get_prev_addr(node3, mtr);
243
/* Set prev and next fields of node2 */
244
flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
245
flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
247
if (!fil_addr_is_null(node1_addr)) {
248
ulint zip_size = fil_space_get_zip_size(space);
249
/* Update next field of node1 */
250
node1 = fut_get_ptr(space, zip_size, node1_addr,
252
flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
254
/* node3 was first in list: update first field in base */
255
flst_write_addr(base + FLST_FIRST, node2_addr, mtr);
258
/* Set prev field of node3 */
259
flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
261
/* Update len of base node */
262
len = flst_get_len(base, mtr);
263
mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
266
/********************************************************************//**
272
flst_base_node_t* base, /*!< in: pointer to base node of list */
273
flst_node_t* node2, /*!< in: node to remove */
274
mtr_t* mtr) /*!< in: mini-transaction handle */
279
fil_addr_t node1_addr;
280
fil_addr_t node2_addr;
282
fil_addr_t node3_addr;
285
ut_ad(mtr && node2 && base);
286
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
287
ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
289
buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
290
zip_size = fil_space_get_zip_size(space);
292
node1_addr = flst_get_prev_addr(node2, mtr);
293
node3_addr = flst_get_next_addr(node2, mtr);
295
if (!fil_addr_is_null(node1_addr)) {
297
/* Update next field of node1 */
299
if (node1_addr.page == node2_addr.page) {
301
node1 = page_align(node2) + node1_addr.boffset;
303
node1 = fut_get_ptr(space, zip_size,
304
node1_addr, RW_X_LATCH, mtr);
307
ut_ad(node1 != node2);
309
flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr);
311
/* node2 was first in list: update first field in base */
312
flst_write_addr(base + FLST_FIRST, node3_addr, mtr);
315
if (!fil_addr_is_null(node3_addr)) {
316
/* Update prev field of node3 */
318
if (node3_addr.page == node2_addr.page) {
320
node3 = page_align(node2) + node3_addr.boffset;
322
node3 = fut_get_ptr(space, zip_size,
323
node3_addr, RW_X_LATCH, mtr);
326
ut_ad(node2 != node3);
328
flst_write_addr(node3 + FLST_PREV, node1_addr, mtr);
330
/* node2 was last in list: update last field in base */
331
flst_write_addr(base + FLST_LAST, node1_addr, mtr);
334
/* Update len of base node */
335
len = flst_get_len(base, mtr);
338
mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr);
341
/********************************************************************//**
342
Cuts off the tail of the list, including the node given. The number of
343
nodes which will be removed must be provided by the caller, as this function
344
does not measure the length of the tail. */
349
flst_base_node_t* base, /*!< in: pointer to base node of list */
350
flst_node_t* node2, /*!< in: first node to remove */
351
ulint n_nodes,/*!< in: number of nodes to remove,
353
mtr_t* mtr) /*!< in: mini-transaction handle */
357
fil_addr_t node1_addr;
358
fil_addr_t node2_addr;
361
ut_ad(mtr && node2 && base);
362
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
363
ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
366
buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
368
node1_addr = flst_get_prev_addr(node2, mtr);
370
if (!fil_addr_is_null(node1_addr)) {
372
/* Update next field of node1 */
374
if (node1_addr.page == node2_addr.page) {
376
node1 = page_align(node2) + node1_addr.boffset;
378
node1 = fut_get_ptr(space,
379
fil_space_get_zip_size(space),
380
node1_addr, RW_X_LATCH, mtr);
383
flst_write_addr(node1 + FLST_NEXT, fil_addr_null, mtr);
385
/* node2 was first in list: update the field in base */
386
flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr);
389
flst_write_addr(base + FLST_LAST, node1_addr, mtr);
391
/* Update len of base node */
392
len = flst_get_len(base, mtr);
393
ut_ad(len >= n_nodes);
395
mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
398
/********************************************************************//**
399
Cuts off the tail of the list, not including the given node. The number of
400
nodes which will be removed must be provided by the caller, as this function
401
does not measure the length of the tail. */
406
flst_base_node_t* base, /*!< in: pointer to base node of list */
407
flst_node_t* node2, /*!< in: first node not to remove */
408
ulint n_nodes,/*!< in: number of nodes to remove */
409
mtr_t* mtr) /*!< in: mini-transaction handle */
411
fil_addr_t node2_addr;
415
ut_ad(mtr && node2 && base);
416
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
417
ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
420
ut_ad(fil_addr_is_null(flst_get_next_addr(node2, mtr)));
425
buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
427
/* Update next field of node2 */
428
flst_write_addr(node2 + FLST_NEXT, fil_addr_null, mtr);
430
flst_write_addr(base + FLST_LAST, node2_addr, mtr);
432
/* Update len of base node */
433
len = flst_get_len(base, mtr);
434
ut_ad(len >= n_nodes);
436
mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
439
/********************************************************************//**
440
Validates a file-based list.
441
@return TRUE if ok */
446
const flst_base_node_t* base, /*!< in: pointer to base node of list */
447
mtr_t* mtr1) /*!< in: mtr */
451
const flst_node_t* node;
452
fil_addr_t node_addr;
453
fil_addr_t base_addr;
459
ut_ad(mtr_memo_contains_page(mtr1, base, MTR_MEMO_PAGE_X_FIX));
461
/* We use two mini-transaction handles: the first is used to
462
lock the base node, and prevent other threads from modifying the
463
list. The second is used to traverse the list. We cannot run the
464
second mtr without committing it at times, because if the list
465
is long, then the x-locked pages could fill the buffer resulting
468
/* Find out the space id */
469
buf_ptr_get_fsp_addr(base, &space, &base_addr);
470
zip_size = fil_space_get_zip_size(space);
472
len = flst_get_len(base, mtr1);
473
node_addr = flst_get_first(base, mtr1);
475
for (i = 0; i < len; i++) {
478
node = fut_get_ptr(space, zip_size,
479
node_addr, RW_X_LATCH, &mtr2);
480
node_addr = flst_get_next_addr(node, &mtr2);
482
mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
486
ut_a(fil_addr_is_null(node_addr));
488
node_addr = flst_get_last(base, mtr1);
490
for (i = 0; i < len; i++) {
493
node = fut_get_ptr(space, zip_size,
494
node_addr, RW_X_LATCH, &mtr2);
495
node_addr = flst_get_prev_addr(node, &mtr2);
497
mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
501
ut_a(fil_addr_is_null(node_addr));
506
/********************************************************************//**
507
Prints info of a file-based list. */
512
const flst_base_node_t* base, /*!< in: pointer to base node of list */
513
mtr_t* mtr) /*!< in: mtr */
515
const buf_frame_t* frame;
519
ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
520
frame = page_align((byte*) base);
522
len = flst_get_len(base, mtr);
526
"Base node in space %lu page %lu byte offset %lu; len %lu\n",
527
(ulong) page_get_space_id(frame),
528
(ulong) page_get_page_no(frame),
529
(ulong) page_offset(base), (ulong) len);