1/***************************************************************************** 2 3Copyright (c) 1996, 2015, Oracle and/or its affiliates. All Rights Reserved. 4Copyright (c) 2015, 2020, MariaDB Corporation. 5 6This program is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free Software 8Foundation; version 2 of the License. 9 10This program is distributed in the hope that it will be useful, but WITHOUT 11ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 12FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 13 14You should have received a copy of the GNU General Public License along with 15this program; if not, write to the Free Software Foundation, Inc., 1651 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA 17 18*****************************************************************************/ 19 20/**************************************************//** 21@file include/btr0pcur.ic 22The index tree persistent cursor 23 24Created 2/23/1996 Heikki Tuuri 25*******************************************************/ 26 27 28/*********************************************************//** 29Gets the rel_pos field for a cursor whose position has been stored. 30@return BTR_PCUR_ON, ... */ 31UNIV_INLINE 32ulint 33btr_pcur_get_rel_pos( 34/*=================*/ 35 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 36{ 37 ut_ad(cursor); 38 ut_ad(cursor->old_rec); 39 ut_ad(cursor->old_stored); 40 ut_ad(cursor->pos_state == BTR_PCUR_WAS_POSITIONED 41 || cursor->pos_state == BTR_PCUR_IS_POSITIONED); 42 43 return(cursor->rel_pos); 44} 45 46#ifdef UNIV_DEBUG 47/*********************************************************//** 48Returns the btr cursor component of a persistent cursor. 49@return pointer to btr cursor component */ 50UNIV_INLINE 51btr_cur_t* 52btr_pcur_get_btr_cur( 53/*=================*/ 54 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 55{ 56 const btr_cur_t* btr_cur = &cursor->btr_cur; 57 return((btr_cur_t*) btr_cur); 58} 59 60/*********************************************************//** 61Returns the page cursor component of a persistent cursor. 62@return pointer to page cursor component */ 63UNIV_INLINE 64page_cur_t* 65btr_pcur_get_page_cur( 66/*==================*/ 67 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 68{ 69 return(btr_cur_get_page_cur(btr_pcur_get_btr_cur(cursor))); 70} 71 72/*********************************************************//** 73Returns the page of a persistent cursor. 74@return pointer to the page */ 75UNIV_INLINE 76page_t* 77btr_pcur_get_page( 78/*==============*/ 79 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 80{ 81 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 82 83 return(btr_cur_get_page(btr_pcur_get_btr_cur(cursor))); 84} 85 86/*********************************************************//** 87Returns the buffer block of a persistent cursor. 88@return pointer to the block */ 89UNIV_INLINE 90buf_block_t* 91btr_pcur_get_block( 92/*===============*/ 93 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 94{ 95 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 96 97 return(btr_cur_get_block(btr_pcur_get_btr_cur(cursor))); 98} 99 100/*********************************************************//** 101Returns the record of a persistent cursor. 102@return pointer to the record */ 103UNIV_INLINE 104rec_t* 105btr_pcur_get_rec( 106/*=============*/ 107 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 108{ 109 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 110 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 111 112 return(btr_cur_get_rec(btr_pcur_get_btr_cur(cursor))); 113} 114#endif /* UNIV_DEBUG */ 115 116/**************************************************************//** 117Gets the up_match value for a pcur after a search. 118@return number of matched fields at the cursor or to the right if 119search mode was PAGE_CUR_GE, otherwise undefined */ 120UNIV_INLINE 121ulint 122btr_pcur_get_up_match( 123/*==================*/ 124 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 125{ 126 const btr_cur_t* btr_cursor; 127 128 ut_ad((cursor->pos_state == BTR_PCUR_WAS_POSITIONED) 129 || (cursor->pos_state == BTR_PCUR_IS_POSITIONED)); 130 131 btr_cursor = btr_pcur_get_btr_cur(cursor); 132 133 ut_ad(btr_cursor->up_match != ULINT_UNDEFINED); 134 135 return(btr_cursor->up_match); 136} 137 138/**************************************************************//** 139Gets the low_match value for a pcur after a search. 140@return number of matched fields at the cursor or to the right if 141search mode was PAGE_CUR_LE, otherwise undefined */ 142UNIV_INLINE 143ulint 144btr_pcur_get_low_match( 145/*===================*/ 146 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 147{ 148 const btr_cur_t* btr_cursor; 149 150 ut_ad((cursor->pos_state == BTR_PCUR_WAS_POSITIONED) 151 || (cursor->pos_state == BTR_PCUR_IS_POSITIONED)); 152 153 btr_cursor = btr_pcur_get_btr_cur(cursor); 154 ut_ad(btr_cursor->low_match != ULINT_UNDEFINED); 155 156 return(btr_cursor->low_match); 157} 158 159/*********************************************************//** 160Checks if the persistent cursor is after the last user record on 161a page. */ 162UNIV_INLINE 163ibool 164btr_pcur_is_after_last_on_page( 165/*===========================*/ 166 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 167{ 168 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 169 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 170 171 return(page_cur_is_after_last(btr_pcur_get_page_cur(cursor))); 172} 173 174/*********************************************************//** 175Checks if the persistent cursor is before the first user record on 176a page. */ 177UNIV_INLINE 178ibool 179btr_pcur_is_before_first_on_page( 180/*=============================*/ 181 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 182{ 183 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 184 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 185 186 return(page_cur_is_before_first(btr_pcur_get_page_cur(cursor))); 187} 188 189/*********************************************************//** 190Checks if the persistent cursor is on a user record. */ 191UNIV_INLINE 192ibool 193btr_pcur_is_on_user_rec( 194/*====================*/ 195 const btr_pcur_t* cursor) /*!< in: persistent cursor */ 196{ 197 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 198 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 199 200 if (btr_pcur_is_before_first_on_page(cursor) 201 || btr_pcur_is_after_last_on_page(cursor)) { 202 203 return(FALSE); 204 } 205 206 return(TRUE); 207} 208 209/*********************************************************//** 210Checks if the persistent cursor is before the first user record in 211the index tree. */ 212static inline bool btr_pcur_is_before_first_in_tree(btr_pcur_t* cursor) 213{ 214 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 215 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 216 217 return !page_has_prev(btr_pcur_get_page(cursor)) 218 && page_cur_is_before_first(btr_pcur_get_page_cur(cursor)); 219} 220 221/*********************************************************//** 222Checks if the persistent cursor is after the last user record in 223the index tree. */ 224static inline bool btr_pcur_is_after_last_in_tree(btr_pcur_t* cursor) 225{ 226 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 227 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 228 229 return !page_has_next(btr_pcur_get_page(cursor)) 230 && page_cur_is_after_last(btr_pcur_get_page_cur(cursor)); 231} 232 233/*********************************************************//** 234Moves the persistent cursor to the next record on the same page. */ 235UNIV_INLINE 236void 237btr_pcur_move_to_next_on_page( 238/*==========================*/ 239 btr_pcur_t* cursor) /*!< in/out: persistent cursor */ 240{ 241 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 242 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 243 244 page_cur_move_to_next(btr_pcur_get_page_cur(cursor)); 245 246 cursor->old_stored = false; 247} 248 249/*********************************************************//** 250Moves the persistent cursor to the previous record on the same page. */ 251UNIV_INLINE 252void 253btr_pcur_move_to_prev_on_page( 254/*==========================*/ 255 btr_pcur_t* cursor) /*!< in/out: persistent cursor */ 256{ 257 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 258 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 259 260 page_cur_move_to_prev(btr_pcur_get_page_cur(cursor)); 261 262 cursor->old_stored = false; 263} 264 265/*********************************************************//** 266Moves the persistent cursor to the next user record in the tree. If no user 267records are left, the cursor ends up 'after last in tree'. 268@return TRUE if the cursor moved forward, ending on a user record */ 269UNIV_INLINE 270ibool 271btr_pcur_move_to_next_user_rec( 272/*===========================*/ 273 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the 274 function may release the page latch */ 275 mtr_t* mtr) /*!< in: mtr */ 276{ 277 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 278 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 279 cursor->old_stored = false; 280loop: 281 if (btr_pcur_is_after_last_on_page(cursor)) { 282 if (btr_pcur_is_after_last_in_tree(cursor)) { 283 return(FALSE); 284 } 285 286 btr_pcur_move_to_next_page(cursor, mtr); 287 } else { 288 btr_pcur_move_to_next_on_page(cursor); 289 } 290 291 if (btr_pcur_is_on_user_rec(cursor)) { 292 293 return(TRUE); 294 } 295 296 goto loop; 297} 298 299/*********************************************************//** 300Moves the persistent cursor to the next record in the tree. If no records are 301left, the cursor stays 'after last in tree'. 302@return TRUE if the cursor was not after last in tree */ 303UNIV_INLINE 304ibool 305btr_pcur_move_to_next( 306/*==================*/ 307 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the 308 function may release the page latch */ 309 mtr_t* mtr) /*!< in: mtr */ 310{ 311 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED); 312 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 313 314 cursor->old_stored = false; 315 316 if (btr_pcur_is_after_last_on_page(cursor)) { 317 if (btr_pcur_is_after_last_in_tree(cursor)) { 318 return(FALSE); 319 } 320 321 btr_pcur_move_to_next_page(cursor, mtr); 322 return(TRUE); 323 } 324 325 btr_pcur_move_to_next_on_page(cursor); 326 return(TRUE); 327} 328 329/**************************************************************//** 330Commits the mtr and sets the pcur latch mode to BTR_NO_LATCHES, 331that is, the cursor becomes detached. 332Function btr_pcur_store_position should be used before calling this, 333if restoration of cursor is wanted later. */ 334UNIV_INLINE 335void 336btr_pcur_commit_specify_mtr( 337/*========================*/ 338 btr_pcur_t* pcur, /*!< in: persistent cursor */ 339 mtr_t* mtr) /*!< in: mtr to commit */ 340{ 341 ut_ad(pcur->pos_state == BTR_PCUR_IS_POSITIONED); 342 343 pcur->latch_mode = BTR_NO_LATCHES; 344 345 mtr_commit(mtr); 346 347 pcur->pos_state = BTR_PCUR_WAS_POSITIONED; 348} 349 350/** Commits the mtr and sets the clustered index pcur and secondary index 351pcur latch mode to BTR_NO_LATCHES, that is, the cursor becomes detached. 352Function btr_pcur_store_position should be used for both cursor before 353calling this, if restoration of cursor is wanted later. 354@param[in] pcur persistent cursor 355@param[in] sec_pcur secondary index persistent cursor 356@param[in] mtr mtr to commit */ 357UNIV_INLINE 358void 359btr_pcurs_commit_specify_mtr( 360 btr_pcur_t* pcur, 361 btr_pcur_t* sec_pcur, 362 mtr_t* mtr) 363{ 364 ut_ad(pcur->pos_state == BTR_PCUR_IS_POSITIONED); 365 ut_ad(sec_pcur->pos_state == BTR_PCUR_IS_POSITIONED); 366 367 pcur->latch_mode = BTR_NO_LATCHES; 368 sec_pcur->latch_mode = BTR_NO_LATCHES; 369 370 mtr_commit(mtr); 371 372 pcur->pos_state = BTR_PCUR_WAS_POSITIONED; 373 sec_pcur->pos_state = BTR_PCUR_WAS_POSITIONED; 374} 375 376/**************************************************************//** 377Sets the old_rec_buf field to NULL. */ 378UNIV_INLINE 379void 380btr_pcur_init( 381/*==========*/ 382 btr_pcur_t* pcur) /*!< in: persistent cursor */ 383{ 384 pcur->old_stored = false; 385 pcur->old_rec_buf = NULL; 386 pcur->old_rec = NULL; 387 388 pcur->btr_cur.rtr_info = NULL; 389} 390 391/** Free old_rec_buf. 392@param[in] pcur Persistent cursor holding old_rec to be freed. */ 393UNIV_INLINE 394void 395btr_pcur_free( 396 btr_pcur_t* pcur) 397{ 398 ut_free(pcur->old_rec_buf); 399} 400 401/**************************************************************//** 402Initializes and opens a persistent cursor to an index tree. It should be 403closed with btr_pcur_close. */ 404UNIV_INLINE 405dberr_t 406btr_pcur_open_low( 407/*==============*/ 408 dict_index_t* index, /*!< in: index */ 409 ulint level, /*!< in: level in the btree */ 410 const dtuple_t* tuple, /*!< in: tuple on which search done */ 411 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...; 412 NOTE that if the search is made using a unique 413 prefix of a record, mode should be 414 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter 415 may end up on the previous page from the 416 record! */ 417 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ... */ 418 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */ 419 const char* file, /*!< in: file name */ 420 unsigned line, /*!< in: line where called */ 421 ib_uint64_t autoinc,/*!< in: PAGE_ROOT_AUTO_INC to be written 422 (0 if none) */ 423 mtr_t* mtr) /*!< in: mtr */ 424{ 425 btr_cur_t* btr_cursor; 426 dberr_t err = DB_SUCCESS; 427 428 /* Initialize the cursor */ 429 430 btr_pcur_init(cursor); 431 432 cursor->latch_mode = BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode); 433 cursor->search_mode = mode; 434 435 /* Search with the tree cursor */ 436 437 btr_cursor = btr_pcur_get_btr_cur(cursor); 438 439 ut_ad(!dict_index_is_spatial(index)); 440 441 err = btr_cur_search_to_nth_level_func( 442 index, level, tuple, mode, latch_mode, btr_cursor, 443#ifdef BTR_CUR_HASH_ADAPT 444 NULL, 445#endif /* BTR_CUR_HASH_ADAPT */ 446 file, line, mtr, autoinc); 447 448 if (UNIV_UNLIKELY(err != DB_SUCCESS)) { 449 ib::warn() << "btr_pcur_open_low" 450 << " level: " << level 451 << " called from file: " 452 << file << " line: " << line 453 << " table: " << index->table->name 454 << " index: " << index->name 455 << " error: " << err; 456 } 457 458 cursor->pos_state = BTR_PCUR_IS_POSITIONED; 459 460 cursor->trx_if_known = NULL; 461 462 return(err); 463} 464 465/**************************************************************//** 466Opens an persistent cursor to an index tree without initializing the 467cursor. */ 468UNIV_INLINE 469dberr_t 470btr_pcur_open_with_no_init_func( 471/*============================*/ 472 dict_index_t* index, /*!< in: index */ 473 const dtuple_t* tuple, /*!< in: tuple on which search done */ 474 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...; 475 NOTE that if the search is made using a unique 476 prefix of a record, mode should be 477 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter 478 may end up on the previous page of the 479 record! */ 480 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ...; 481 NOTE that if ahi_latch then we might not 482 acquire a cursor page latch, but assume 483 that the ahi_latch protects the record! */ 484 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */ 485#ifdef BTR_CUR_HASH_ADAPT 486 rw_lock_t* ahi_latch, 487 /*!< in: adaptive hash index latch held 488 by the caller, or NULL if none */ 489#endif /* BTR_CUR_HASH_ADAPT */ 490 const char* file, /*!< in: file name */ 491 unsigned line, /*!< in: line where called */ 492 mtr_t* mtr) /*!< in: mtr */ 493{ 494 btr_cur_t* btr_cursor; 495 dberr_t err = DB_SUCCESS; 496 497 cursor->latch_mode = BTR_LATCH_MODE_WITHOUT_INTENTION(latch_mode); 498 cursor->search_mode = mode; 499 500 /* Search with the tree cursor */ 501 502 btr_cursor = btr_pcur_get_btr_cur(cursor); 503 504 err = btr_cur_search_to_nth_level_func( 505 index, 0, tuple, mode, latch_mode, btr_cursor, 506#ifdef BTR_CUR_HASH_ADAPT 507 ahi_latch, 508#endif /* BTR_CUR_HASH_ADAPT */ 509 file, line, mtr); 510 511 cursor->pos_state = BTR_PCUR_IS_POSITIONED; 512 513 cursor->old_stored = false; 514 515 cursor->trx_if_known = NULL; 516 return err; 517} 518 519/*****************************************************************//** 520Opens a persistent cursor at either end of an index. */ 521UNIV_INLINE 522dberr_t 523btr_pcur_open_at_index_side( 524/*========================*/ 525 bool from_left, /*!< in: true if open to the low end, 526 false if to the high end */ 527 dict_index_t* index, /*!< in: index */ 528 ulint latch_mode, /*!< in: latch mode */ 529 btr_pcur_t* pcur, /*!< in/out: cursor */ 530 bool init_pcur, /*!< in: whether to initialize pcur */ 531 ulint level, /*!< in: level to search for 532 (0=leaf) */ 533 mtr_t* mtr) /*!< in/out: mini-transaction */ 534{ 535 dberr_t err = DB_SUCCESS; 536 537 pcur->latch_mode = BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode); 538 539 pcur->search_mode = from_left ? PAGE_CUR_G : PAGE_CUR_L; 540 541 if (init_pcur) { 542 btr_pcur_init(pcur); 543 } 544 545 err = btr_cur_open_at_index_side( 546 from_left, index, latch_mode, 547 btr_pcur_get_btr_cur(pcur), level, mtr); 548 pcur->pos_state = BTR_PCUR_IS_POSITIONED; 549 550 pcur->old_stored = false; 551 552 pcur->trx_if_known = NULL; 553 554 return (err); 555} 556 557/**********************************************************************//** 558Positions a cursor at a randomly chosen position within a B-tree. 559@return true if the index is available and we have put the cursor, false 560if the index is unavailable */ 561UNIV_INLINE 562bool 563btr_pcur_open_at_rnd_pos_func( 564/*==========================*/ 565 dict_index_t* index, /*!< in: index */ 566 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */ 567 btr_pcur_t* cursor, /*!< in/out: B-tree pcur */ 568 const char* file, /*!< in: file name */ 569 unsigned line, /*!< in: line where called */ 570 mtr_t* mtr) /*!< in: mtr */ 571{ 572 /* Initialize the cursor */ 573 574 cursor->latch_mode = latch_mode; 575 cursor->search_mode = PAGE_CUR_G; 576 577 btr_pcur_init(cursor); 578 579 bool available; 580 581 available = btr_cur_open_at_rnd_pos_func(index, latch_mode, 582 btr_pcur_get_btr_cur(cursor), 583 file, line, mtr); 584 cursor->pos_state = BTR_PCUR_IS_POSITIONED; 585 cursor->old_stored = false; 586 587 cursor->trx_if_known = NULL; 588 589 return(available); 590} 591 592/**************************************************************//** 593Frees the possible memory heap of a persistent cursor and sets the latch 594mode of the persistent cursor to BTR_NO_LATCHES. 595WARNING: this function does not release the latch on the page where the 596cursor is currently positioned. The latch is acquired by the 597"move to next/previous" family of functions. Since recursive shared locks 598are not allowed, you must take care (if using the cursor in S-mode) to 599manually release the latch by either calling 600btr_leaf_page_release(btr_pcur_get_block(&pcur), pcur.latch_mode, mtr) 601or by committing the mini-transaction right after btr_pcur_close(). 602A subsequent attempt to crawl the same page in the same mtr would cause 603an assertion failure. */ 604UNIV_INLINE 605void 606btr_pcur_close( 607/*===========*/ 608 btr_pcur_t* cursor) /*!< in: persistent cursor */ 609{ 610 ut_free(cursor->old_rec_buf); 611 612 if (cursor->btr_cur.rtr_info) { 613 rtr_clean_rtr_info(cursor->btr_cur.rtr_info, true); 614 cursor->btr_cur.rtr_info = NULL; 615 } 616 617 cursor->old_rec = NULL; 618 cursor->old_rec_buf = NULL; 619 cursor->btr_cur.page_cur.rec = NULL; 620 cursor->btr_cur.page_cur.block = NULL; 621 622 cursor->old_rec = NULL; 623 cursor->old_stored = false; 624 625 cursor->latch_mode = BTR_NO_LATCHES; 626 cursor->pos_state = BTR_PCUR_NOT_POSITIONED; 627 628 cursor->trx_if_known = NULL; 629} 630 631/*********************************************************//** 632Moves the persistent cursor to the infimum record on the same page. */ 633UNIV_INLINE 634void 635btr_pcur_move_before_first_on_page( 636/*===============================*/ 637 btr_pcur_t* cursor) /*!< in/out: persistent cursor */ 638{ 639 ut_ad(cursor->latch_mode != BTR_NO_LATCHES); 640 641 page_cur_set_before_first(btr_pcur_get_block(cursor), 642 btr_pcur_get_page_cur(cursor)); 643 644 cursor->old_stored = false; 645} 646