1/*****************************************************************************
2
3Copyright (c) 2014, 2019, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for 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 St, Fifth Floor, Boston, MA 02110-1301  USA
24
25*****************************************************************************/
26
27/** @file include gis0rtree.h
28 R-tree Inline code
29
30 Created 2013/03/27 Jimmy Yang and Allen Lai
31 ***********************************************************************/
32
33/** Sets the child node mbr in a node pointer. */
34UNIV_INLINE
35void rtr_page_cal_mbr(const dict_index_t *index, /*!< in: index */
36                      const buf_block_t *block,  /*!< in: buffer block */
37                      rtr_mbr_t *rtr_mbr, /*!< out: MBR encapsulates the page */
38                      mem_heap_t *heap)   /*!< in: heap for the memory
39                                          allocation */
40{
41  page_t *page;
42  rec_t *rec;
43  const byte *field;
44  ulint len;
45  ulint *offsets = nullptr;
46  double bmin, bmax;
47  double *amin;
48  double *amax;
49  ulint inc = 0;
50  double *mbr;
51
52  rtr_mbr->xmin = DBL_MAX;
53  rtr_mbr->ymin = DBL_MAX;
54  rtr_mbr->xmax = -DBL_MAX;
55  rtr_mbr->ymax = -DBL_MAX;
56
57  mbr = reinterpret_cast<double *>(rtr_mbr);
58
59  page = buf_block_get_frame(block);
60
61  rec = page_rec_get_next(page_get_infimum_rec(page));
62  offsets = rec_get_offsets(rec, index, offsets, 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 (int 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) *amin = bmin;
78      if (*amax < bmax) *amax = bmax;
79
80      inc += 2 * sizeof(double);
81    }
82
83    rec = page_rec_get_next(rec);
84
85    if (rec == nullptr) {
86      break;
87    }
88  } while (!page_rec_is_supremum(rec));
89}
90
91/** push a nonleaf index node to the search path */
92UNIV_INLINE
93void rtr_non_leaf_stack_push(rtr_node_path_t *path, /*!< in/out: search path */
94                             page_no_t pageno,      /*!< in: pageno to insert */
95                             node_seq_t seq_no,  /*!< in: Node sequence num */
96                             ulint level,        /*!< in: index page level */
97                             page_no_t child_no, /*!< in: child page no */
98                             btr_pcur_t *cursor, /*!< in: position cursor */
99                             double mbr_inc)     /*!< in: MBR needs to be
100                                                 enlarged */
101{
102  node_visit_t insert_val;
103
104  insert_val.page_no = pageno;
105  insert_val.seq_no = seq_no;
106  insert_val.level = level;
107  insert_val.child_no = child_no;
108  insert_val.cursor = cursor;
109  insert_val.mbr_inc = mbr_inc;
110
111  path->push_back(insert_val);
112
113#ifdef RTR_SEARCH_DIAGNOSTIC
114  fprintf(stderr,
115          "INNODB_RTR: Push page %d, level %d, seq %d"
116          " to search stack \n",
117          static_cast<int>(pageno), static_cast<int>(level),
118          static_cast<int>(seq_no));
119#endif /* RTR_SEARCH_DIAGNOSTIC */
120}
121
122/** Allocates a new Split Sequence Number.
123 @return new SSN id */
124UNIV_INLINE
125node_seq_t rtr_get_new_ssn_id(
126    dict_index_t *index) /*!< in/out: the index struct */
127{
128  node_seq_t ssn;
129
130  mutex_enter(&(index->rtr_ssn.mutex));
131  ssn = ++index->rtr_ssn.seq_no;
132  mutex_exit(&(index->rtr_ssn.mutex));
133
134  return (ssn);
135}
136/** Get the current Split Sequence Number.
137 @return current SSN id */
138UNIV_INLINE
139node_seq_t rtr_get_current_ssn_id(dict_index_t *index) /*!< in: index struct */
140{
141  node_seq_t ssn;
142
143  mutex_enter(&(index->rtr_ssn.mutex));
144  ssn = index->rtr_ssn.seq_no;
145  mutex_exit(&(index->rtr_ssn.mutex));
146
147  return (ssn);
148}
149
150/** Sets pointer to the data and length in a field. */
151UNIV_INLINE
152void rtr_write_mbr(byte *data,           /*!< out: data */
153                   const rtr_mbr_t *mbr) /*!< in: data */
154{
155  const double *my_mbr = reinterpret_cast<const double *>(mbr);
156
157  for (int i = 0; i < SPDIMS * 2; i++) {
158    mach_double_write(data + i * sizeof(double), my_mbr[i]);
159  }
160}
161
162/** Sets pointer to the data and length in a field. */
163UNIV_INLINE
164void rtr_read_mbr(const byte *data, /*!< in: data */
165                  rtr_mbr_t *mbr)   /*!< out: MBR */
166{
167  for (int i = 0; i < SPDIMS * 2; i++) {
168    (reinterpret_cast<double *>(mbr))[i] =
169        mach_double_read(data + i * sizeof(double));
170  }
171
172  ut_ad(mbr->xmin == DBL_MAX || mbr->xmax == -DBL_MAX ||
173        mbr->xmin <= mbr->xmax);
174  ut_ad(mbr->ymin == DBL_MAX || mbr->ymax == -DBL_MAX ||
175        mbr->ymin <= mbr->ymax);
176}
177
178/** Returns the R-Tree node stored in the parent search path
179 @return pointer to R-Tree cursor component in the parent path,
180 NULL if parent path is empty or index is larger than num of items contained */
181UNIV_INLINE
182node_visit_t *rtr_get_parent_node(
183    btr_cur_t *btr_cur, /*!< in: persistent cursor */
184    ulint level,        /*!< in: index level of buffer page */
185    ulint is_insert)    /*!< in: whether it is insert */
186{
187  ulint num;
188  ulint tree_height = btr_cur->tree_height;
189  node_visit_t *found_node = nullptr;
190
191  if (level >= tree_height) {
192    return (nullptr);
193  }
194
195  mutex_enter(&btr_cur->rtr_info->rtr_path_mutex);
196
197  num = btr_cur->rtr_info->parent_path->size();
198
199  if (!num) {
200    mutex_exit(&btr_cur->rtr_info->rtr_path_mutex);
201    return (nullptr);
202  }
203
204  if (is_insert) {
205    ulint idx = tree_height - level - 1;
206    ut_ad(idx < num);
207
208    found_node = &(*btr_cur->rtr_info->parent_path)[idx];
209  } else {
210    node_visit_t *node;
211
212    while (num > 0) {
213      node = &(*btr_cur->rtr_info->parent_path)[num - 1];
214
215      if (node->level == level) {
216        found_node = node;
217        break;
218      }
219      num--;
220    }
221  }
222
223  mutex_exit(&btr_cur->rtr_info->rtr_path_mutex);
224
225  return (found_node);
226}
227
228/** Returns the R-Tree cursor stored in the parent search path
229 @return pointer to R-Tree cursor component */
230UNIV_INLINE
231btr_pcur_t *rtr_get_parent_cursor(
232    btr_cur_t *btr_cur, /*!< in: persistent cursor */
233    ulint level,        /*!< in: index level of buffer page */
234    ulint is_insert)    /*!< in: whether insert operation */
235{
236  node_visit_t *found_node = rtr_get_parent_node(btr_cur, level, is_insert);
237
238  return ((found_node) ? found_node->cursor : nullptr);
239}
240
241/** Reinitialize a R-Tree search info in btr_cur_t */
242UNIV_INLINE
243void rtr_info_reinit_in_cursor(
244    /************************/
245    btr_cur_t *cursor,   /*!< in/out: tree cursor */
246    dict_index_t *index, /*!< in: index struct */
247    bool need_prdt)      /*!< in: Whether predicate lock is
248                         needed */
249{
250  rtr_clean_rtr_info(cursor->rtr_info, false);
251  rtr_init_rtr_info(cursor->rtr_info, need_prdt, cursor, index, true);
252}
253