1 /***************************************************************************** 2 3 Copyright (c) 2014, Oracle and/or its affiliates. All Rights Reserved. 4 Copyright (c) 2018, 2020, MariaDB Corporation. 5 6 This program is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free Software 8 Foundation; version 2 of the License. 9 10 This program is distributed in the hope that it will be useful, but WITHOUT 11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 12 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License along with 15 this program; if not, write to the Free Software Foundation, Inc., 16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA 17 18 *****************************************************************************/ 19 20 /******************************************************************//** 21 @file include gis0type.h 22 R-tree header file 23 24 Created 2013/03/27 Jimmy Yang 25 ***********************************************************************/ 26 27 #ifndef gis0type_h 28 #define gis0type_h 29 30 #include "buf0buf.h" 31 #include "data0type.h" 32 #include "data0types.h" 33 #include "dict0types.h" 34 #include "ut0vec.h" 35 #include "gis0geo.h" 36 37 #include <vector> 38 #include <list> 39 40 /* Node Sequence Number. Only updated when page splits */ 41 typedef ib_uint32_t node_seq_t; 42 43 /* RTree internal non-leaf Nodes to be searched, from root to leaf */ 44 typedef struct node_visit { 45 ulint page_no; /*!< the page number */ 46 node_seq_t seq_no; /*!< the SSN (split sequence number */ 47 ulint level; /*!< the page's index level */ 48 ulint child_no; /*!< child page num if for parent 49 recording */ 50 btr_pcur_t* cursor; /*!< cursor structure if we positioned 51 FIXME: there is no need to use whole 52 btr_pcur_t, just the position related 53 members */ 54 double mbr_inc; /*!< whether this node needs to be 55 enlarged for insertion */ 56 } node_visit_t; 57 58 typedef std::vector<node_visit_t, ut_allocator<node_visit_t> > rtr_node_path_t; 59 60 typedef struct rtr_rec { 61 rec_t* r_rec; /*!< matched record */ 62 bool locked; /*!< whether the record locked */ 63 } rtr_rec_t; 64 65 typedef std::vector<rtr_rec_t, ut_allocator<rtr_rec_t> > rtr_rec_vector; 66 67 /* Structure for matched records on the leaf page */ 68 typedef struct matched_rec { 69 byte* bufp; /*!< aligned buffer point */ 70 byte rec_buf[UNIV_PAGE_SIZE_MAX * 2]; 71 /*!< buffer used to copy matching rec */ 72 buf_block_t block; /*!< the shadow buffer block */ 73 ulint used; /*!< memory used */ 74 rtr_rec_vector* matched_recs; /*!< vector holding the matching rec */ 75 ib_mutex_t rtr_match_mutex;/*!< mutex protect the match_recs 76 vector */ 77 bool valid; /*!< whether result in matched_recs 78 or this search is valid (page not 79 dropped) */ 80 bool locked; /*!< whether these recs locked */ 81 } matched_rec_t; 82 83 /* In memory representation of a minimum bounding rectangle */ 84 typedef struct rtr_mbr { 85 double xmin; /*!< minimum on x */ 86 double xmax; /*!< maximum on x */ 87 double ymin; /*!< minimum on y */ 88 double ymax; /*!< maximum on y */ 89 } rtr_mbr_t; 90 91 /* Maximum index level for R-Tree, this is consistent with BTR_MAX_LEVELS */ 92 #define RTR_MAX_LEVELS 100 93 94 /* Number of pages we latch at leaf level when there is possible Tree 95 modification (split, shrink), we always latch left, current 96 and right pages */ 97 #define RTR_LEAF_LATCH_NUM 3 98 99 /** Vectors holding the matching internal pages/nodes and leaf records */ 100 typedef struct rtr_info{ 101 rtr_node_path_t*path; /*!< vector holding matching pages */ 102 rtr_node_path_t*parent_path; 103 /*!< vector holding parent pages during 104 search */ 105 matched_rec_t* matches;/*!< struct holding matching leaf records */ 106 ib_mutex_t rtr_path_mutex; 107 /*!< mutex protect the "path" vector */ 108 buf_block_t* tree_blocks[RTR_MAX_LEVELS + RTR_LEAF_LATCH_NUM]; 109 /*!< tracking pages that would be locked 110 at leaf level, for future free */ 111 ulint tree_savepoints[RTR_MAX_LEVELS + RTR_LEAF_LATCH_NUM]; 112 /*!< savepoint used to release latches/blocks 113 on each level and leaf level */ 114 rtr_mbr_t mbr; /*!< the search MBR */ 115 que_thr_t* thr; /*!< the search thread */ 116 mem_heap_t* heap; /*!< memory heap */ 117 btr_cur_t* cursor; /*!< cursor used for search */ 118 dict_index_t* index; /*!< index it is searching */ 119 bool need_prdt_lock; 120 /*!< whether we will need predicate lock 121 the tree */ 122 bool need_page_lock; 123 /*!< whether we will need predicate page lock 124 the tree */ 125 bool allocated;/*!< whether this structure is allocate or 126 on stack */ 127 bool mbr_adj;/*!< whether mbr will need to be enlarged 128 for an insertion operation */ 129 bool fd_del; /*!< found deleted row */ 130 const dtuple_t* search_tuple; 131 /*!< search tuple being used */ 132 page_cur_mode_t search_mode; 133 /*!< current search mode */ 134 } rtr_info_t; 135 136 typedef std::list<rtr_info_t*, ut_allocator<rtr_info_t*> > rtr_info_active; 137 138 /* Tracking structure for all onoging search for an index */ 139 typedef struct rtr_info_track { 140 rtr_info_active* rtr_active; /*!< Active search info */ 141 ib_mutex_t rtr_active_mutex; 142 /*!< mutex to protect 143 rtr_active */ 144 } rtr_info_track_t; 145 146 /* This is to record the record movement between pages. Used for corresponding 147 lock movement */ 148 typedef struct rtr_rec_move { 149 rec_t* old_rec; /*!< record being moved in old page */ 150 rec_t* new_rec; /*!< new record location */ 151 bool moved; /*!< whether lock are moved too */ 152 } rtr_rec_move_t; 153 #endif /*!< gis0rtree.h */ 154