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