1 /** 2 * @file rtree.h 3 * 4 * @section LICENSE 5 * 6 * The MIT License 7 * 8 * @copyright Copyright (c) 2017-2021 TileDB, Inc. 9 * 10 * Permission is hereby granted, free of charge, to any person obtaining a copy 11 * of this software and associated documentation files (the "Software"), to deal 12 * in the Software without restriction, including without limitation the rights 13 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 14 * copies of the Software, and to permit persons to whom the Software is 15 * furnished to do so, subject to the following conditions: 16 * 17 * The above copyright notice and this permission notice shall be included in 18 * all copies or substantial portions of the Software. 19 * 20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 25 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 26 * THE SOFTWARE. 27 * 28 * @section DESCRIPTION 29 * 30 * This file defines class RTree. 31 */ 32 33 #ifndef TILEDB_RTREE_H 34 #define TILEDB_RTREE_H 35 36 #include <vector> 37 38 #include "tiledb/common/status.h" 39 #include "tiledb/sm/array_schema/domain.h" 40 #include "tiledb/sm/misc/tile_overlap.h" 41 42 using namespace tiledb::common; 43 44 namespace tiledb { 45 namespace sm { 46 47 class Buffer; 48 class ConstBuffer; 49 50 enum class Datatype : uint8_t; 51 enum class Layout : uint8_t; 52 53 /** 54 * A simple RTree implementation. It supports storing only n-dimensional 55 * MBRs (not points). Also it only offers bottom-up bulk-loading 56 * (without incremental updates), and range and point queries. 57 */ 58 class RTree { 59 public: 60 /* ********************************* */ 61 /* CONSTRUCTORS & DESTRUCTORS */ 62 /* ********************************* */ 63 64 /** Constructor. */ 65 RTree(); 66 67 /** Constructor. */ 68 RTree(const Domain* domain, unsigned fanout); 69 70 /** Destructor. */ 71 ~RTree(); 72 73 /** Copy constructor. This performs a deep copy. */ 74 RTree(const RTree& rtree); 75 76 /** Move constructor. */ 77 RTree(RTree&& rtree) noexcept; 78 79 /** Copy-assign operator. This performs a deep copy. */ 80 RTree& operator=(const RTree& rtree); 81 82 /** Move-assign operator. */ 83 RTree& operator=(RTree&& rtree) noexcept; 84 85 /* ********************************* */ 86 /* API */ 87 /* ********************************* */ 88 89 /** Builds the RTree bottom-up on the current leaf level. */ 90 Status build_tree(); 91 92 /** Frees the memory associated with the rtree. */ 93 uint64_t free_memory(); 94 95 /** The number of dimensions of the R-tree. */ 96 unsigned dim_num() const; 97 98 /** Returns the domain. */ 99 const Domain* domain() const; 100 101 /** Returns the fanout. */ 102 unsigned fanout() const; 103 104 /** 105 * Returns the tile overlap of the input range with the MBRs stored 106 * in the RTree. 107 */ 108 TileOverlap get_tile_overlap(const NDRange& range) const; 109 110 /** 111 * Compute tile bitmap for the curent range. 112 */ 113 void compute_tile_bitmap( 114 const Range& range, unsigned d, std::vector<uint8_t>* tile_bitmap) const; 115 116 /** Returns the tree height. */ 117 unsigned height() const; 118 119 /** Returns the leaf MBR with the input index. */ 120 const NDRange& leaf(uint64_t leaf_idx) const; 121 122 /** Returns the leaves of the tree. */ 123 const std::vector<NDRange>& leaves() const; 124 125 /** 126 * Returns the number of leaves that are stored in a (full) subtree 127 * rooted at the input level. Note that the root is at level 0. 128 */ 129 uint64_t subtree_leaf_num(uint64_t level) const; 130 131 /** 132 * Serializes the contents of the object to the input buffer. 133 * Note that `domain_` is not serialized in the buffer. 134 */ 135 Status serialize(Buffer* buff) const; 136 137 /** 138 * Sets an MBR as a leaf in the tree. The function will error out 139 * if the number of levels in the tree is different from exactly 140 * 1 (the leaf level), and if `leaf_id` is out of bounds / invalid. 141 */ 142 Status set_leaf(uint64_t leaf_id, const NDRange& mbr); 143 144 /** 145 * Sets the input MBRs as leaves. This will destroy the existing 146 * RTree. 147 */ 148 Status set_leaves(const std::vector<NDRange>& mbrs); 149 150 /** 151 * Resizes the leaf level. It destroys the upper levels 152 * of the tree if they exist. 153 * It errors if `num` is smaller than the current number 154 * of leaves. 155 */ 156 Status set_leaf_num(uint64_t num); 157 158 /** 159 * Deserializes the contents of the object from the input buffer based 160 * on the format version. 161 * It also sets the input domain, as that is not serialized. 162 */ 163 Status deserialize( 164 ConstBuffer* cbuff, const Domain* domain, uint32_t version); 165 166 private: 167 /* ********************************* */ 168 /* PRIVATE TYPE DEFINITIONS */ 169 /* ********************************* */ 170 171 /** 172 * The RTree is composed of nodes and is constructed bottom up 173 * such that each node has exactly `fanout_` children. The 174 * construction algorithm attempts to create a full tree and, 175 * therefore, all nodes have `fanout_` children except for the 176 * "rightmost" nodes which may contain less. 177 * 178 * The nodes at the same height of the tree form a level of 179 * the tree. Also each node simply contains up to `fanout_` 180 * MBRs. 181 * 182 * A `Level` object serializes the contents of the nodes at 183 * the same tree level, that is it serializes all the MBRs 184 * of all those nodes. Since we know the `fanout_` and the 185 * number of levels, as well as the fact that the tree is from 186 * left-to-right complete, we can easily infer which MBRs 187 * in the `Level` object correspond to which node of that level. 188 * 189 * Note that the `Level` objects are stored in a simple vector 190 * `levels_`, where the first level is the root. This is how 191 * we can infer which tree level each `Level` object corresponds to. 192 */ 193 typedef std::vector<NDRange> Level; 194 195 /** 196 * Defines an R-Tree level entry, which corresponds to a node 197 * at a particular level. It stores the level the entry belongs 198 * to, as well as the starting index of the first MBR in the 199 * corresponding R-Tree node. 200 */ 201 struct Entry { 202 /** The level of the node the entry corresponds to. */ 203 uint64_t level_; 204 /** The index of the first MBR of the corresponding node. */ 205 uint64_t mbr_idx_; 206 }; 207 208 /* ********************************* */ 209 /* PRIVATE ATTRIBUTES */ 210 /* ********************************* */ 211 212 /** The domain. */ 213 const Domain* domain_; 214 215 /** The fanout of the tree. */ 216 unsigned fanout_; 217 218 /** 219 * The tree levels. The first level is the root. Note that the root 220 * always consists of a single MBR. 221 */ 222 std::vector<Level> levels_; 223 224 /** 225 * Stores the size of the buffer used to deserialize the data, used for 226 * memory tracking pusposes on reads. 227 */ 228 uint64_t deserialized_buffer_size_; 229 230 /* ********************************* */ 231 /* PRIVATE METHODS */ 232 /* ********************************* */ 233 234 /** Builds a single tree level on top of the input level. */ 235 Level build_level(const Level& level); 236 237 /** Returns a deep copy of this RTree. */ 238 RTree clone() const; 239 240 /** 241 * Deserializes the contents of the object from the input buffer based 242 * on the format version. 243 * It also sets the input domain, as that is not serialized. 244 * 245 * Applicable to versions 1-4 246 */ 247 Status deserialize_v1_v4(ConstBuffer* cbuff, const Domain* domain); 248 249 /** 250 * Deserializes the contents of the object from the input buffer based 251 * on the format version. 252 * It also sets the input domain, as that is not serialized. 253 * 254 * Applicable to versions >= 5 255 */ 256 Status deserialize_v5(ConstBuffer* cbuff, const Domain* domain); 257 258 /** 259 * Swaps the contents (all field values) of this RTree with the 260 * given ``rtree``. 261 */ 262 void swap(RTree& rtree); 263 }; 264 265 } // namespace sm 266 } // namespace tiledb 267 268 #endif // TILEDB_RTREE_H 269