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