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