1/*****************************************************************************
2
3Copyright (c) 2014, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2017, 2021, 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 gis0rtree.h
22R-tree Inline code
23
24Created 2013/03/27 Jimmy Yang and Allen Lai
25***********************************************************************/
26
27/**************************************************************//**
28Sets the child node mbr in a node pointer. */
29UNIV_INLINE
30void
31rtr_page_cal_mbr(
32/*=============*/
33	const dict_index_t*	index,	/*!< in: index */
34	const buf_block_t*	block,	/*!< in: buffer block */
35	rtr_mbr_t*		rtr_mbr,/*!< out: MBR encapsulates the page */
36	mem_heap_t*		heap)	/*!< in: heap for the memory
37					allocation */
38{
39	page_t*		page;
40	rec_t*		rec;
41	const byte*	field;
42	ulint		len;
43	rec_offs*	offsets = NULL;
44	double		bmin, bmax;
45	double*		amin;
46	double*		amax;
47	ulint		inc = 0;
48	double*		mbr;
49
50	rtr_mbr->xmin = DBL_MAX;
51	rtr_mbr->ymin = DBL_MAX;
52	rtr_mbr->xmax = -DBL_MAX;
53	rtr_mbr->ymax = -DBL_MAX;
54
55	mbr = reinterpret_cast<double*>(rtr_mbr);
56
57	page = buf_block_get_frame(block);
58
59	rec = page_rec_get_next(page_get_infimum_rec(page));
60	offsets = rec_get_offsets(rec, index, offsets, page_is_leaf(page)
61				  ? index->n_fields : 0,
62				  ULINT_UNDEFINED, &heap);
63
64	do {
65		/* The mbr address is in the first field. */
66		field = rec_get_nth_field(rec, offsets, 0, &len);
67
68		ut_ad(len == DATA_MBR_LEN);
69		inc = 0;
70		for (unsigned i = 0; i < SPDIMS; i++) {
71			bmin = mach_double_read(field + inc);
72			bmax = mach_double_read(field + inc + sizeof(double));
73
74			amin = mbr + i * SPDIMS;
75			amax = mbr + i * SPDIMS + 1;
76
77			if (*amin > bmin)
78				*amin = bmin;
79			if (*amax < bmax)
80				*amax = bmax;
81
82			inc += 2 * sizeof(double);
83		}
84
85		rec = page_rec_get_next(rec);
86
87		if (rec == NULL) {
88			break;
89		}
90	} while (!page_rec_is_supremum(rec));
91}
92
93/**************************************************************//**
94push a nonleaf index node to the search path */
95UNIV_INLINE
96void
97rtr_non_leaf_stack_push(
98/*====================*/
99	rtr_node_path_t*	path,		/*!< in/out: search path */
100	ulint			pageno,		/*!< in: pageno to insert */
101	node_seq_t		seq_no,		/*!< in: Node sequence num */
102	ulint			level,		/*!< in: index page level */
103	ulint			child_no,	/*!< in: child page no */
104	btr_pcur_t*		cursor,		/*!< in: position cursor */
105	double			mbr_inc)	/*!< in: MBR needs to be
106						enlarged */
107{
108	node_visit_t	insert_val;
109
110	insert_val.page_no = pageno;
111	insert_val.seq_no = seq_no;
112	insert_val.level = level;
113	insert_val.child_no = child_no;
114	insert_val.cursor = cursor;
115	insert_val.mbr_inc = mbr_inc;
116
117	path->push_back(insert_val);
118
119#ifdef RTR_SEARCH_DIAGNOSTIC
120	fprintf(stderr, "INNODB_RTR: Push page %d, level %d, seq %d"
121			" to search stack \n",
122		static_cast<int>(pageno), static_cast<int>(level),
123		static_cast<int>(seq_no));
124#endif /* RTR_SEARCH_DIAGNOSTIC */
125}
126
127/*****************************************************************//**
128Allocates a new Split Sequence Number.
129@return new SSN id */
130UNIV_INLINE
131node_seq_t
132rtr_get_new_ssn_id(
133/*===============*/
134	dict_index_t*	index)	/*!< in/out: the index struct */
135{
136  node_seq_t ssn= my_atomic_add32_explicit(&index->rtr_ssn, 1,
137                                           MY_MEMORY_ORDER_RELAXED);
138  return ssn + 1;
139}
140/*****************************************************************//**
141Get the current Split Sequence Number.
142@return current SSN id */
143UNIV_INLINE
144node_seq_t
145rtr_get_current_ssn_id(
146/*===================*/
147	dict_index_t*	index)	/*!< in: index struct */
148{
149  return my_atomic_load32_explicit(&index->rtr_ssn, MY_MEMORY_ORDER_RELAXED);
150}
151
152/*********************************************************************//**
153Sets pointer to the data and length in a field. */
154UNIV_INLINE
155void
156rtr_write_mbr(
157/*==========*/
158	byte*			data,	/*!< out: data */
159	const rtr_mbr_t*	mbr)	/*!< in: data */
160{
161	const double* my_mbr = reinterpret_cast<const double*>(mbr);
162
163	for (unsigned i = 0; i < SPDIMS * 2; i++) {
164		mach_double_write(data + i * sizeof(double), my_mbr[i]);
165	}
166}
167
168/*********************************************************************//**
169Sets pointer to the data and length in a field. */
170UNIV_INLINE
171void
172rtr_read_mbr(
173/*==========*/
174	const byte*	data,	/*!< in: data */
175	rtr_mbr_t*	mbr)	/*!< out: MBR */
176{
177	for (unsigned i = 0; i < SPDIMS * 2; i++) {
178		(reinterpret_cast<double*>(mbr))[i] = mach_double_read(
179							data
180							+ i * sizeof(double));
181	}
182}
183
184/*********************************************************//**
185Returns the R-Tree node stored in the parent search path
186@return pointer to R-Tree cursor component in the parent path,
187NULL if parent path is empty or index is larger than num of items contained */
188UNIV_INLINE
189node_visit_t*
190rtr_get_parent_node(
191/*================*/
192	btr_cur_t*	btr_cur,	/*!< in: persistent cursor */
193	ulint		level,		/*!< in: index level of buffer page */
194	ulint		is_insert)	/*!< in: whether it is insert */
195{
196	ulint			num;
197	ulint			tree_height = btr_cur->tree_height;
198	node_visit_t*		found_node = NULL;
199
200	if (level >= tree_height) {
201		return(NULL);
202	}
203
204	mutex_enter(&btr_cur->rtr_info->rtr_path_mutex);
205
206	num = btr_cur->rtr_info->parent_path->size();
207
208	if (!num) {
209		mutex_exit(&btr_cur->rtr_info->rtr_path_mutex);
210		return(NULL);
211	}
212
213	if (is_insert) {
214		ulint	idx = tree_height - level - 1;
215		ut_ad(idx < num);
216
217		found_node = &(*btr_cur->rtr_info->parent_path)[idx];
218	} else {
219		node_visit_t*	node;
220
221		while (num > 0) {
222			node = &(*btr_cur->rtr_info->parent_path)[num - 1];
223
224			if (node->level == level) {
225				found_node = node;
226				break;
227			}
228			num--;
229		}
230	}
231
232	mutex_exit(&btr_cur->rtr_info->rtr_path_mutex);
233
234	return(found_node);
235}
236
237/*********************************************************//**
238Returns the R-Tree cursor stored in the parent search path
239@return pointer to R-Tree cursor component */
240UNIV_INLINE
241btr_pcur_t*
242rtr_get_parent_cursor(
243/*==================*/
244	btr_cur_t*	btr_cur,	/*!< in: persistent cursor */
245	ulint		level,		/*!< in: index level of buffer page */
246	ulint		is_insert)	/*!< in: whether insert operation */
247{
248	node_visit_t*   found_node = rtr_get_parent_node(
249					btr_cur, level, is_insert);
250
251	return((found_node) ? found_node->cursor : NULL);
252}
253
254/********************************************************************//**
255Reinitialize a R-Tree search info in btr_cur_t */
256UNIV_INLINE
257void
258rtr_info_reinit_in_cursor(
259/************************/
260	btr_cur_t*	cursor,		/*!< in/out: tree cursor */
261	dict_index_t*	index,		/*!< in: index struct */
262	bool		need_prdt)	/*!< in: Whether predicate lock is
263					needed */
264{
265	rtr_clean_rtr_info(cursor->rtr_info, false);
266	rtr_init_rtr_info(cursor->rtr_info, need_prdt, cursor, index, true);
267}
268