1/*****************************************************************************
2
3Copyright (c) 1996, 2015, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2015, 2018, 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, Suite 500, 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 last record on the same page. */
267UNIV_INLINE
268void
269btr_pcur_move_to_last_on_page(
270/*==========================*/
271 btr_pcur_t* cursor, /*!< in: persistent cursor */
272 mtr_t* mtr) /*!< in: mtr */
273{
274 UT_NOT_USED(mtr);
275 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
276
277 page_cur_set_after_last(btr_pcur_get_block(cursor),
278 btr_pcur_get_page_cur(cursor));
279
280 cursor->old_stored = false;
281}
282
283/*********************************************************//**
284Moves the persistent cursor to the next user record in the tree. If no user
285records are left, the cursor ends up 'after last in tree'.
286@return TRUE if the cursor moved forward, ending on a user record */
287UNIV_INLINE
288ibool
289btr_pcur_move_to_next_user_rec(
290/*===========================*/
291 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
292 function may release the page latch */
293 mtr_t* mtr) /*!< in: mtr */
294{
295 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
296 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
297 cursor->old_stored = false;
298loop:
299 if (btr_pcur_is_after_last_on_page(cursor)) {
300 if (btr_pcur_is_after_last_in_tree(cursor)) {
301 return(FALSE);
302 }
303
304 btr_pcur_move_to_next_page(cursor, mtr);
305 } else {
306 btr_pcur_move_to_next_on_page(cursor);
307 }
308
309 if (btr_pcur_is_on_user_rec(cursor)) {
310
311 return(TRUE);
312 }
313
314 goto loop;
315}
316
317/*********************************************************//**
318Moves the persistent cursor to the next record in the tree. If no records are
319left, the cursor stays 'after last in tree'.
320@return TRUE if the cursor was not after last in tree */
321UNIV_INLINE
322ibool
323btr_pcur_move_to_next(
324/*==================*/
325 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
326 function may release the page latch */
327 mtr_t* mtr) /*!< in: mtr */
328{
329 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
330 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
331
332 cursor->old_stored = false;
333
334 if (btr_pcur_is_after_last_on_page(cursor)) {
335 if (btr_pcur_is_after_last_in_tree(cursor)) {
336 return(FALSE);
337 }
338
339 btr_pcur_move_to_next_page(cursor, mtr);
340 return(TRUE);
341 }
342
343 btr_pcur_move_to_next_on_page(cursor);
344 return(TRUE);
345}
346
347/**************************************************************//**
348Commits the mtr and sets the pcur latch mode to BTR_NO_LATCHES,
349that is, the cursor becomes detached.
350Function btr_pcur_store_position should be used before calling this,
351if restoration of cursor is wanted later. */
352UNIV_INLINE
353void
354btr_pcur_commit_specify_mtr(
355/*========================*/
356 btr_pcur_t* pcur, /*!< in: persistent cursor */
357 mtr_t* mtr) /*!< in: mtr to commit */
358{
359 ut_ad(pcur->pos_state == BTR_PCUR_IS_POSITIONED);
360
361 pcur->latch_mode = BTR_NO_LATCHES;
362
363 mtr_commit(mtr);
364
365 pcur->pos_state = BTR_PCUR_WAS_POSITIONED;
366}
367
368/**************************************************************//**
369Sets the old_rec_buf field to NULL. */
370UNIV_INLINE
371void
372btr_pcur_init(
373/*==========*/
374 btr_pcur_t* pcur) /*!< in: persistent cursor */
375{
376 pcur->old_stored = false;
377 pcur->old_rec_buf = NULL;
378 pcur->old_rec = NULL;
379
380 pcur->btr_cur.rtr_info = NULL;
381}
382
383/** Free old_rec_buf.
384@param[in] pcur Persistent cursor holding old_rec to be freed. */
385UNIV_INLINE
386void
387btr_pcur_free(
388 btr_pcur_t* pcur)
389{
390 ut_free(pcur->old_rec_buf);
391}
392
393/**************************************************************//**
394Initializes and opens a persistent cursor to an index tree. It should be
395closed with btr_pcur_close. */
396UNIV_INLINE
397dberr_t
398btr_pcur_open_low(
399/*==============*/
400 dict_index_t* index, /*!< in: index */
401 ulint level, /*!< in: level in the btree */
402 const dtuple_t* tuple, /*!< in: tuple on which search done */
403 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...;
404 NOTE that if the search is made using a unique
405 prefix of a record, mode should be
406 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
407 may end up on the previous page from the
408 record! */
409 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ... */
410 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */
411 const char* file, /*!< in: file name */
412 unsigned line, /*!< in: line where called */
413 ib_uint64_t autoinc,/*!< in: PAGE_ROOT_AUTO_INC to be written
414 (0 if none) */
415 mtr_t* mtr) /*!< in: mtr */
416{
417 btr_cur_t* btr_cursor;
418 dberr_t err = DB_SUCCESS;
419
420 /* Initialize the cursor */
421
422 btr_pcur_init(cursor);
423
424 cursor->latch_mode = BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode);
425 cursor->search_mode = mode;
426
427 /* Search with the tree cursor */
428
429 btr_cursor = btr_pcur_get_btr_cur(cursor);
430
431 ut_ad(!dict_index_is_spatial(index));
432
433 err = btr_cur_search_to_nth_level_func(
434 index, level, tuple, mode, latch_mode, btr_cursor,
435#ifdef BTR_CUR_HASH_ADAPT
436 NULL,
437#endif /* BTR_CUR_HASH_ADAPT */
438 file, line, mtr, autoinc);
439
440 if (err != DB_SUCCESS) {
441 ib::warn() << " Error code: " << err
442 << " btr_pcur_open_low "
443 << " level: " << level
444 << " called from file: "
445 << file << " line: " << line
446 << " table: " << index->table->name
447 << " index: " << index->name;
448 }
449
450 cursor->pos_state = BTR_PCUR_IS_POSITIONED;
451
452 cursor->trx_if_known = NULL;
453
454 return(err);
455}
456
457/**************************************************************//**
458Opens an persistent cursor to an index tree without initializing the
459cursor. */
460UNIV_INLINE
461dberr_t
462btr_pcur_open_with_no_init_func(
463/*============================*/
464 dict_index_t* index, /*!< in: index */
465 const dtuple_t* tuple, /*!< in: tuple on which search done */
466 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...;
467 NOTE that if the search is made using a unique
468 prefix of a record, mode should be
469 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
470 may end up on the previous page of the
471 record! */
472 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ...;
473 NOTE that if ahi_latch then we might not
474 acquire a cursor page latch, but assume
475 that the ahi_latch protects the record! */
476 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */
477#ifdef BTR_CUR_HASH_ADAPT
478 rw_lock_t* ahi_latch,
479 /*!< in: adaptive hash index latch held
480 by the caller, or NULL if none */
481#endif /* BTR_CUR_HASH_ADAPT */
482 const char* file, /*!< in: file name */
483 unsigned line, /*!< in: line where called */
484 mtr_t* mtr) /*!< in: mtr */
485{
486 btr_cur_t* btr_cursor;
487 dberr_t err = DB_SUCCESS;
488
489 cursor->latch_mode = BTR_LATCH_MODE_WITHOUT_INTENTION(latch_mode);
490 cursor->search_mode = mode;
491
492 /* Search with the tree cursor */
493
494 btr_cursor = btr_pcur_get_btr_cur(cursor);
495
496 err = btr_cur_search_to_nth_level_func(
497 index, 0, tuple, mode, latch_mode, btr_cursor,
498#ifdef BTR_CUR_HASH_ADAPT
499 ahi_latch,
500#endif /* BTR_CUR_HASH_ADAPT */
501 file, line, mtr);
502
503 cursor->pos_state = BTR_PCUR_IS_POSITIONED;
504
505 cursor->old_stored = false;
506
507 cursor->trx_if_known = NULL;
508 return err;
509}
510
511/*****************************************************************//**
512Opens a persistent cursor at either end of an index. */
513UNIV_INLINE
514dberr_t
515btr_pcur_open_at_index_side(
516/*========================*/
517 bool from_left, /*!< in: true if open to the low end,
518 false if to the high end */
519 dict_index_t* index, /*!< in: index */
520 ulint latch_mode, /*!< in: latch mode */
521 btr_pcur_t* pcur, /*!< in/out: cursor */
522 bool init_pcur, /*!< in: whether to initialize pcur */
523 ulint level, /*!< in: level to search for
524 (0=leaf) */
525 mtr_t* mtr) /*!< in/out: mini-transaction */
526{
527 dberr_t err = DB_SUCCESS;
528
529 pcur->latch_mode = BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode);
530
531 pcur->search_mode = from_left ? PAGE_CUR_G : PAGE_CUR_L;
532
533 if (init_pcur) {
534 btr_pcur_init(pcur);
535 }
536
537 err = btr_cur_open_at_index_side(
538 from_left, index, latch_mode,
539 btr_pcur_get_btr_cur(pcur), level, mtr);
540 pcur->pos_state = BTR_PCUR_IS_POSITIONED;
541
542 pcur->old_stored = false;
543
544 pcur->trx_if_known = NULL;
545
546 return (err);
547}
548
549/**********************************************************************//**
550Positions a cursor at a randomly chosen position within a B-tree.
551@return true if the index is available and we have put the cursor, false
552if the index is unavailable */
553UNIV_INLINE
554bool
555btr_pcur_open_at_rnd_pos_func(
556/*==========================*/
557 dict_index_t* index, /*!< in: index */
558 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */
559 btr_pcur_t* cursor, /*!< in/out: B-tree pcur */
560 const char* file, /*!< in: file name */
561 unsigned line, /*!< in: line where called */
562 mtr_t* mtr) /*!< in: mtr */
563{
564 /* Initialize the cursor */
565
566 cursor->latch_mode = latch_mode;
567 cursor->search_mode = PAGE_CUR_G;
568
569 btr_pcur_init(cursor);
570
571 bool available;
572
573 available = btr_cur_open_at_rnd_pos_func(index, latch_mode,
574 btr_pcur_get_btr_cur(cursor),
575 file, line, mtr);
576 cursor->pos_state = BTR_PCUR_IS_POSITIONED;
577 cursor->old_stored = false;
578
579 cursor->trx_if_known = NULL;
580
581 return(available);
582}
583
584/**************************************************************//**
585Frees the possible memory heap of a persistent cursor and sets the latch
586mode of the persistent cursor to BTR_NO_LATCHES.
587WARNING: this function does not release the latch on the page where the
588cursor is currently positioned. The latch is acquired by the
589"move to next/previous" family of functions. Since recursive shared locks
590are not allowed, you must take care (if using the cursor in S-mode) to
591manually release the latch by either calling
592btr_leaf_page_release(btr_pcur_get_block(&pcur), pcur.latch_mode, mtr)
593or by committing the mini-transaction right after btr_pcur_close().
594A subsequent attempt to crawl the same page in the same mtr would cause
595an assertion failure. */
596UNIV_INLINE
597void
598btr_pcur_close(
599/*===========*/
600 btr_pcur_t* cursor) /*!< in: persistent cursor */
601{
602 ut_free(cursor->old_rec_buf);
603
604 if (cursor->btr_cur.rtr_info) {
605 rtr_clean_rtr_info(cursor->btr_cur.rtr_info, true);
606 cursor->btr_cur.rtr_info = NULL;
607 }
608
609 cursor->old_rec = NULL;
610 cursor->old_rec_buf = NULL;
611 cursor->btr_cur.page_cur.rec = NULL;
612 cursor->btr_cur.page_cur.block = NULL;
613
614 cursor->old_rec = NULL;
615 cursor->old_stored = false;
616
617 cursor->latch_mode = BTR_NO_LATCHES;
618 cursor->pos_state = BTR_PCUR_NOT_POSITIONED;
619
620 cursor->trx_if_known = NULL;
621}
622
623/*********************************************************//**
624Moves the persistent cursor to the infimum record on the same page. */
625UNIV_INLINE
626void
627btr_pcur_move_before_first_on_page(
628/*===============================*/
629 btr_pcur_t* cursor) /*!< in/out: persistent cursor */
630{
631 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
632
633 page_cur_set_before_first(btr_pcur_get_block(cursor),
634 btr_pcur_get_page_cur(cursor));
635
636 cursor->old_stored = false;
637}
638