1/*****************************************************************************
2
3Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2017, 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.h
22The index tree persistent cursor
23
24Created 2/23/1996 Heikki Tuuri
25*******************************************************/
26
27#ifndef btr0pcur_h
28#define btr0pcur_h
29
30#include "univ.i"
31#include "dict0dict.h"
32#include "data0data.h"
33#include "mtr0mtr.h"
34#include "page0cur.h"
35#include "btr0cur.h"
36#include "btr0btr.h"
37#include "btr0types.h"
38#include "gis0rtree.h"
39
40/* Relative positions for a stored cursor position */
41enum btr_pcur_pos_t {
42 BTR_PCUR_ON = 1,
43 BTR_PCUR_BEFORE = 2,
44 BTR_PCUR_AFTER = 3,
45/* Note that if the tree is not empty, btr_pcur_store_position does not
46use the following, but only uses the above three alternatives, where the
47position is stored relative to a specific record: this makes implementation
48of a scroll cursor easier */
49 BTR_PCUR_BEFORE_FIRST_IN_TREE = 4, /* in an empty tree */
50 BTR_PCUR_AFTER_LAST_IN_TREE = 5 /* in an empty tree */
51};
52
53/**************************************************************//**
54Allocates memory for a persistent cursor object and initializes the cursor.
55@return own: persistent cursor */
56btr_pcur_t*
57btr_pcur_create_for_mysql(void);
58/*============================*/
59
60/**************************************************************//**
61Resets a persistent cursor object, freeing ::old_rec_buf if it is
62allocated and resetting the other members to their initial values. */
63void
64btr_pcur_reset(
65/*===========*/
66 btr_pcur_t* cursor);/*!< in, out: persistent cursor */
67
68/**************************************************************//**
69Frees the memory for a persistent cursor object. */
70void
71btr_pcur_free_for_mysql(
72/*====================*/
73 btr_pcur_t* cursor); /*!< in, own: persistent cursor */
74/**************************************************************//**
75Copies the stored position of a pcur to another pcur. */
76void
77btr_pcur_copy_stored_position(
78/*==========================*/
79 btr_pcur_t* pcur_receive, /*!< in: pcur which will receive the
80 position info */
81 btr_pcur_t* pcur_donate); /*!< in: pcur from which the info is
82 copied */
83/**************************************************************//**
84Sets the old_rec_buf field to NULL. */
85UNIV_INLINE
86void
87btr_pcur_init(
88/*==========*/
89 btr_pcur_t* pcur); /*!< in: persistent cursor */
90
91/** Free old_rec_buf.
92@param[in] pcur Persistent cursor holding old_rec to be freed. */
93UNIV_INLINE
94void
95btr_pcur_free(
96 btr_pcur_t* pcur);
97
98/**************************************************************//**
99Initializes and opens a persistent cursor to an index tree. It should be
100closed with btr_pcur_close. */
101UNIV_INLINE
102dberr_t
103btr_pcur_open_low(
104/*==============*/
105 dict_index_t* index, /*!< in: index */
106 ulint level, /*!< in: level in the btree */
107 const dtuple_t* tuple, /*!< in: tuple on which search done */
108 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...;
109 NOTE that if the search is made using a unique
110 prefix of a record, mode should be
111 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
112 may end up on the previous page from the
113 record! */
114 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ... */
115 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */
116 const char* file, /*!< in: file name */
117 unsigned line, /*!< in: line where called */
118 ib_uint64_t autoinc,/*!< in: PAGE_ROOT_AUTO_INC to be written
119 (0 if none) */
120 mtr_t* mtr); /*!< in: mtr */
121#define btr_pcur_open(i,t,md,l,c,m) \
122 btr_pcur_open_low(i,0,t,md,l,c,__FILE__,__LINE__,0,m)
123/**************************************************************//**
124Opens an persistent cursor to an index tree without initializing the
125cursor. */
126UNIV_INLINE
127dberr_t
128btr_pcur_open_with_no_init_func(
129/*============================*/
130 dict_index_t* index, /*!< in: index */
131 const dtuple_t* tuple, /*!< in: tuple on which search done */
132 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...;
133 NOTE that if the search is made using a unique
134 prefix of a record, mode should be
135 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
136 may end up on the previous page of the
137 record! */
138 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ...;
139 NOTE that if ahi_latch then we might not
140 acquire a cursor page latch, but assume
141 that the ahi_latch protects the record! */
142 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */
143#ifdef BTR_CUR_HASH_ADAPT
144 rw_lock_t* ahi_latch,
145 /*!< in: adaptive hash index latch held
146 by the caller, or NULL if none */
147#endif /* BTR_CUR_HASH_ADAPT */
148 const char* file, /*!< in: file name */
149 unsigned line, /*!< in: line where called */
150 mtr_t* mtr); /*!< in: mtr */
151#ifdef BTR_CUR_HASH_ADAPT
152# define btr_pcur_open_with_no_init(ix,t,md,l,cur,ahi,m) \
153 btr_pcur_open_with_no_init_func(ix,t,md,l,cur,ahi,__FILE__,__LINE__,m)
154#else /* BTR_CUR_HASH_ADAPT */
155# define btr_pcur_open_with_no_init(ix,t,md,l,cur,ahi,m) \
156 btr_pcur_open_with_no_init_func(ix,t,md,l,cur,__FILE__,__LINE__,m)
157#endif /* BTR_CUR_HASH_ADAPT */
158
159/*****************************************************************//**
160Opens a persistent cursor at either end of an index. */
161UNIV_INLINE
162dberr_t
163btr_pcur_open_at_index_side(
164/*========================*/
165 bool from_left, /*!< in: true if open to the low end,
166 false if to the high end */
167 dict_index_t* index, /*!< in: index */
168 ulint latch_mode, /*!< in: latch mode */
169 btr_pcur_t* pcur, /*!< in/out: cursor */
170 bool init_pcur, /*!< in: whether to initialize pcur */
171 ulint level, /*!< in: level to search for
172 (0=leaf) */
173 mtr_t* mtr) /*!< in/out: mini-transaction */
174 MY_ATTRIBUTE((nonnull));
175/**************************************************************//**
176Gets the up_match value for a pcur after a search.
177@return number of matched fields at the cursor or to the right if
178search mode was PAGE_CUR_GE, otherwise undefined */
179UNIV_INLINE
180ulint
181btr_pcur_get_up_match(
182/*==================*/
183 const btr_pcur_t* cursor); /*!< in: persistent cursor */
184/**************************************************************//**
185Gets the low_match value for a pcur after a search.
186@return number of matched fields at the cursor or to the right if
187search mode was PAGE_CUR_LE, otherwise undefined */
188UNIV_INLINE
189ulint
190btr_pcur_get_low_match(
191/*===================*/
192 const btr_pcur_t* cursor); /*!< in: persistent cursor */
193/**************************************************************//**
194If mode is PAGE_CUR_G or PAGE_CUR_GE, opens a persistent cursor on the first
195user record satisfying the search condition, in the case PAGE_CUR_L or
196PAGE_CUR_LE, on the last user record. If no such user record exists, then
197in the first case sets the cursor after last in tree, and in the latter case
198before first in tree. The latching mode must be BTR_SEARCH_LEAF or
199BTR_MODIFY_LEAF. */
200void
201btr_pcur_open_on_user_rec_func(
202/*===========================*/
203 dict_index_t* index, /*!< in: index */
204 const dtuple_t* tuple, /*!< in: tuple on which search done */
205 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ... */
206 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF or
207 BTR_MODIFY_LEAF */
208 btr_pcur_t* cursor, /*!< in: memory buffer for persistent
209 cursor */
210 const char* file, /*!< in: file name */
211 unsigned line, /*!< in: line where called */
212 mtr_t* mtr); /*!< in: mtr */
213#define btr_pcur_open_on_user_rec(i,t,md,l,c,m) \
214 btr_pcur_open_on_user_rec_func(i,t,md,l,c,__FILE__,__LINE__,m)
215/**********************************************************************//**
216Positions a cursor at a randomly chosen position within a B-tree.
217@return true if the index is available and we have put the cursor, false
218if the index is unavailable */
219UNIV_INLINE
220bool
221btr_pcur_open_at_rnd_pos_func(
222/*==========================*/
223 dict_index_t* index, /*!< in: index */
224 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */
225 btr_pcur_t* cursor, /*!< in/out: B-tree pcur */
226 const char* file, /*!< in: file name */
227 unsigned line, /*!< in: line where called */
228 mtr_t* mtr); /*!< in: mtr */
229#define btr_pcur_open_at_rnd_pos(i,l,c,m) \
230 btr_pcur_open_at_rnd_pos_func(i,l,c,__FILE__,__LINE__,m)
231/**************************************************************//**
232Frees the possible memory heap of a persistent cursor and sets the latch
233mode of the persistent cursor to BTR_NO_LATCHES.
234WARNING: this function does not release the latch on the page where the
235cursor is currently positioned. The latch is acquired by the
236"move to next/previous" family of functions. Since recursive shared locks
237are not allowed, you must take care (if using the cursor in S-mode) to
238manually release the latch by either calling
239btr_leaf_page_release(btr_pcur_get_block(&pcur), pcur.latch_mode, mtr)
240or by committing the mini-transaction right after btr_pcur_close().
241A subsequent attempt to crawl the same page in the same mtr would cause
242an assertion failure. */
243UNIV_INLINE
244void
245btr_pcur_close(
246/*===========*/
247 btr_pcur_t* cursor); /*!< in: persistent cursor */
248/**************************************************************//**
249The position of the cursor is stored by taking an initial segment of the
250record the cursor is positioned on, before, or after, and copying it to the
251cursor data structure, or just setting a flag if the cursor id before the
252first in an EMPTY tree, or after the last in an EMPTY tree. NOTE that the
253page where the cursor is positioned must not be empty if the index tree is
254not totally empty! */
255void
256btr_pcur_store_position(
257/*====================*/
258 btr_pcur_t* cursor, /*!< in: persistent cursor */
259 mtr_t* mtr); /*!< in: mtr */
260/**************************************************************//**
261Restores the stored position of a persistent cursor bufferfixing the page and
262obtaining the specified latches. If the cursor position was saved when the
263(1) cursor was positioned on a user record: this function restores the position
264to the last record LESS OR EQUAL to the stored record;
265(2) cursor was positioned on a page infimum record: restores the position to
266the last record LESS than the user record which was the successor of the page
267infimum;
268(3) cursor was positioned on the page supremum: restores to the first record
269GREATER than the user record which was the predecessor of the supremum.
270(4) cursor was positioned before the first or after the last in an empty tree:
271restores to before first or after the last in the tree.
272@return TRUE if the cursor position was stored when it was on a user
273record and it can be restored on a user record whose ordering fields
274are identical to the ones of the original user record */
275ibool
276btr_pcur_restore_position_func(
277/*===========================*/
278 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */
279 btr_pcur_t* cursor, /*!< in: detached persistent cursor */
280 const char* file, /*!< in: file name */
281 unsigned line, /*!< in: line where called */
282 mtr_t* mtr); /*!< in: mtr */
283#define btr_pcur_restore_position(l,cur,mtr) \
284 btr_pcur_restore_position_func(l,cur,__FILE__,__LINE__,mtr)
285/*********************************************************//**
286Gets the rel_pos field for a cursor whose position has been stored.
287@return BTR_PCUR_ON, ... */
288UNIV_INLINE
289ulint
290btr_pcur_get_rel_pos(
291/*=================*/
292 const btr_pcur_t* cursor);/*!< in: persistent cursor */
293/**************************************************************//**
294Commits the mtr and sets the pcur latch mode to BTR_NO_LATCHES,
295that is, the cursor becomes detached.
296Function btr_pcur_store_position should be used before calling this,
297if restoration of cursor is wanted later. */
298UNIV_INLINE
299void
300btr_pcur_commit_specify_mtr(
301/*========================*/
302 btr_pcur_t* pcur, /*!< in: persistent cursor */
303 mtr_t* mtr); /*!< in: mtr to commit */
304/*********************************************************//**
305Moves the persistent cursor to the next record in the tree. If no records are
306left, the cursor stays 'after last in tree'.
307@return TRUE if the cursor was not after last in tree */
308UNIV_INLINE
309ibool
310btr_pcur_move_to_next(
311/*==================*/
312 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
313 function may release the page latch */
314 mtr_t* mtr); /*!< in: mtr */
315/*********************************************************//**
316Moves the persistent cursor to the previous record in the tree. If no records
317are left, the cursor stays 'before first in tree'.
318@return TRUE if the cursor was not before first in tree */
319ibool
320btr_pcur_move_to_prev(
321/*==================*/
322 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
323 function may release the page latch */
324 mtr_t* mtr); /*!< in: mtr */
325/*********************************************************//**
326Moves the persistent cursor to the last record on the same page. */
327UNIV_INLINE
328void
329btr_pcur_move_to_last_on_page(
330/*==========================*/
331 btr_pcur_t* cursor, /*!< in: persistent cursor */
332 mtr_t* mtr); /*!< in: mtr */
333/*********************************************************//**
334Moves the persistent cursor to the next user record in the tree. If no user
335records are left, the cursor ends up 'after last in tree'.
336@return TRUE if the cursor moved forward, ending on a user record */
337UNIV_INLINE
338ibool
339btr_pcur_move_to_next_user_rec(
340/*===========================*/
341 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
342 function may release the page latch */
343 mtr_t* mtr); /*!< in: mtr */
344/*********************************************************//**
345Moves the persistent cursor to the first record on the next page.
346Releases the latch on the current page, and bufferunfixes it.
347Note that there must not be modifications on the current page,
348as then the x-latch can be released only in mtr_commit. */
349void
350btr_pcur_move_to_next_page(
351/*=======================*/
352 btr_pcur_t* cursor, /*!< in: persistent cursor; must be on the
353 last record of the current page */
354 mtr_t* mtr); /*!< in: mtr */
355#ifdef UNIV_DEBUG
356/*********************************************************//**
357Returns the btr cursor component of a persistent cursor.
358@return pointer to btr cursor component */
359UNIV_INLINE
360btr_cur_t*
361btr_pcur_get_btr_cur(
362/*=================*/
363 const btr_pcur_t* cursor); /*!< in: persistent cursor */
364/*********************************************************//**
365Returns the page cursor component of a persistent cursor.
366@return pointer to page cursor component */
367UNIV_INLINE
368page_cur_t*
369btr_pcur_get_page_cur(
370/*==================*/
371 const btr_pcur_t* cursor); /*!< in: persistent cursor */
372/*********************************************************//**
373Returns the page of a persistent cursor.
374@return pointer to the page */
375UNIV_INLINE
376page_t*
377btr_pcur_get_page(
378/*==============*/
379 const btr_pcur_t* cursor);/*!< in: persistent cursor */
380/*********************************************************//**
381Returns the buffer block of a persistent cursor.
382@return pointer to the block */
383UNIV_INLINE
384buf_block_t*
385btr_pcur_get_block(
386/*===============*/
387 const btr_pcur_t* cursor);/*!< in: persistent cursor */
388/*********************************************************//**
389Returns the record of a persistent cursor.
390@return pointer to the record */
391UNIV_INLINE
392rec_t*
393btr_pcur_get_rec(
394/*=============*/
395 const btr_pcur_t* cursor);/*!< in: persistent cursor */
396#else /* UNIV_DEBUG */
397# define btr_pcur_get_btr_cur(cursor) (&(cursor)->btr_cur)
398# define btr_pcur_get_page_cur(cursor) (&(cursor)->btr_cur.page_cur)
399# define btr_pcur_get_page(cursor) ((cursor)->btr_cur.page_cur.block->frame)
400# define btr_pcur_get_block(cursor) ((cursor)->btr_cur.page_cur.block)
401# define btr_pcur_get_rec(cursor) ((cursor)->btr_cur.page_cur.rec)
402#endif /* UNIV_DEBUG */
403/*********************************************************//**
404Checks if the persistent cursor is on a user record. */
405UNIV_INLINE
406ibool
407btr_pcur_is_on_user_rec(
408/*====================*/
409 const btr_pcur_t* cursor);/*!< in: persistent cursor */
410/*********************************************************//**
411Checks if the persistent cursor is after the last user record on
412a page. */
413UNIV_INLINE
414ibool
415btr_pcur_is_after_last_on_page(
416/*===========================*/
417 const btr_pcur_t* cursor);/*!< in: persistent cursor */
418/*********************************************************//**
419Checks if the persistent cursor is before the first user record on
420a page. */
421UNIV_INLINE
422ibool
423btr_pcur_is_before_first_on_page(
424/*=============================*/
425 const btr_pcur_t* cursor);/*!< in: persistent cursor */
426/*********************************************************//**
427Checks if the persistent cursor is before the first user record in
428the index tree. */
429static inline bool btr_pcur_is_before_first_in_tree(btr_pcur_t* cursor);
430/*********************************************************//**
431Checks if the persistent cursor is after the last user record in
432the index tree. */
433static inline bool btr_pcur_is_after_last_in_tree(btr_pcur_t* cursor);
434/*********************************************************//**
435Moves the persistent cursor to the next record on the same page. */
436UNIV_INLINE
437void
438btr_pcur_move_to_next_on_page(
439/*==========================*/
440 btr_pcur_t* cursor);/*!< in/out: persistent cursor */
441/*********************************************************//**
442Moves the persistent cursor to the previous record on the same page. */
443UNIV_INLINE
444void
445btr_pcur_move_to_prev_on_page(
446/*==========================*/
447 btr_pcur_t* cursor);/*!< in/out: persistent cursor */
448/*********************************************************//**
449Moves the persistent cursor to the infimum record on the same page. */
450UNIV_INLINE
451void
452btr_pcur_move_before_first_on_page(
453/*===============================*/
454 btr_pcur_t* cursor); /*!< in/out: persistent cursor */
455
456/** Position state of persistent B-tree cursor. */
457enum pcur_pos_t {
458 /** The persistent cursor is not positioned. */
459 BTR_PCUR_NOT_POSITIONED = 0,
460 /** The persistent cursor was previously positioned.
461 TODO: currently, the state can be BTR_PCUR_IS_POSITIONED,
462 though it really should be BTR_PCUR_WAS_POSITIONED,
463 because we have no obligation to commit the cursor with
464 mtr; similarly latch_mode may be out of date. This can
465 lead to problems if btr_pcur is not used the right way;
466 all current code should be ok. */
467 BTR_PCUR_WAS_POSITIONED,
468 /** The persistent cursor is positioned by optimistic get to the same
469 record as it was positioned at. Not used for rel_pos == BTR_PCUR_ON.
470 It may need adjustment depending on previous/current search direction
471 and rel_pos. */
472 BTR_PCUR_IS_POSITIONED_OPTIMISTIC,
473 /** The persistent cursor is positioned by index search.
474 Or optimistic get for rel_pos == BTR_PCUR_ON. */
475 BTR_PCUR_IS_POSITIONED
476};
477
478/* The persistent B-tree cursor structure. This is used mainly for SQL
479selects, updates, and deletes. */
480
481struct btr_pcur_t{
482 /** a B-tree cursor */
483 btr_cur_t btr_cur;
484 /** see TODO note below!
485 BTR_SEARCH_LEAF, BTR_MODIFY_LEAF, BTR_MODIFY_TREE or BTR_NO_LATCHES,
486 depending on the latching state of the page and tree where the cursor
487 is positioned; BTR_NO_LATCHES means that the cursor is not currently
488 positioned:
489 we say then that the cursor is detached; it can be restored to
490 attached if the old position was stored in old_rec */
491 ulint latch_mode;
492 /** true if old_rec is stored */
493 bool old_stored;
494 /** if cursor position is stored, contains an initial segment of the
495 latest record cursor was positioned either on, before or after */
496 rec_t* old_rec;
497 /** number of fields in old_rec */
498 ulint old_n_fields;
499 /** BTR_PCUR_ON, BTR_PCUR_BEFORE, or BTR_PCUR_AFTER, depending on
500 whether cursor was on, before, or after the old_rec record */
501 enum btr_pcur_pos_t rel_pos;
502 /** buffer block when the position was stored */
503 buf_block_t* block_when_stored;
504 /** the modify clock value of the buffer block when the cursor position
505 was stored */
506 ib_uint64_t modify_clock;
507 /** the withdraw clock value of the buffer pool when the cursor
508 position was stored */
509 ulint withdraw_clock;
510 /** btr_pcur_store_position() and btr_pcur_restore_position() state. */
511 enum pcur_pos_t pos_state;
512 /** PAGE_CUR_G, ... */
513 page_cur_mode_t search_mode;
514 /** the transaction, if we know it; otherwise this field is not defined;
515 can ONLY BE USED in error prints in fatal assertion failures! */
516 trx_t* trx_if_known;
517 /*-----------------------------*/
518 /* NOTE that the following fields may possess dynamically allocated
519 memory which should be freed if not needed anymore! */
520
521 /** NULL, or a dynamically allocated buffer for old_rec */
522 byte* old_rec_buf;
523 /** old_rec_buf size if old_rec_buf is not NULL */
524 ulint buf_size;
525
526 /** Return the index of this persistent cursor */
527 dict_index_t* index() const { return(btr_cur.index); }
528};
529
530#include "btr0pcur.ic"
531
532#endif
533