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