src/util/areastore.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2015 est31 <mtest31@outlook.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "util/areastore.h"
  21 #include "util/serialize.h"
  22 #include "util/container.h"
  23
  24 #if USE_SPATIAL
  25         #include <spatialindex/SpatialIndex.h>
  26         #include <spatialindex/RTree.h>
  27         #include <spatialindex/Point.h>
  28 #endif
  29
  30 #define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z))
  31
  32 #define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \
  33         (!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d)))
  34
  35 #define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \
  36         AST_SMALLER_EQ_AS((p), (a)->maxedge))
  37
  38 #define AST_CONTAINS_AREA(amine, amaxe, b)         \
  39         (AST_SMALLER_EQ_AS((amine), (b)->minedge) \
  40         && AST_SMALLER_EQ_AS((b)->maxedge, (amaxe)))
  41
  42 #define AST_AREAS_OVERLAP(amine, amaxe, b)                \
  43         (AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), X) && \
  44         AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Y) &&  \
  45         AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Z))
  46
  47
  48 AreaStore *AreaStore::getOptimalImplementation()
  49 {
  50 #if USE_SPATIAL
  51         return new SpatialAreaStore();
  52 #else
  53         return new VectorAreaStore();
  54 #endif
  55 }
  56
  57 const Area *AreaStore::getArea(u32 id) const
  58 {
  59         AreaMap::const_iterator it = areas_map.find(id);
  60         if (it == areas_map.end())
  61                 return NULL;
  62         return &it->second;
  63 }
  64
  65 #if 0
  66 Currently, serialisation is commented out. This is because of multiple reasons:
  67 1. Why do we store the areastore into a file, why not into the database?
  68 2. We don't use libspatial's serialisation, but we should, or perhaps not, because
  69         it would remove the ability to switch. Perhaps write migration routines?
  70 3. Various things need fixing, e.g. the size is serialized as
  71         c++ implementation defined size_t
  72 bool AreaStore::deserialize(std::istream &is)
  73 {
  74         u8 ver = readU8(is);
  75         if (ver != 1)
  76                 return false;
  77         u16 count_areas = readU16(is);
  78         for (u16 i = 0; i < count_areas; i++) {
  79                 // deserialize an area
  80                 Area a;
  81                 a.id = readU32(is);
  82                 a.minedge = readV3S16(is);
  83                 a.maxedge = readV3S16(is);
  84                 a.datalen = readU16(is);
  85                 a.data = new char[a.datalen];
  86                 is.read((char *) a.data, a.datalen);
  87                 insertArea(a);
  88         }
  89         return true;
  90 }
  91
  92
  93 static bool serialize_area(void *ostr, Area *a)
  94 {
  95         std::ostream &os = *((std::ostream *) ostr);
  96         writeU32(os, a->id);
  97         writeV3S16(os, a->minedge);
  98         writeV3S16(os, a->maxedge);
  99         writeU16(os, a->datalen);
 100         os.write(a->data, a->datalen);
 101
 102         return false;
 103 }
 104
 105
 106 void AreaStore::serialize(std::ostream &os) const
 107 {
 108         // write initial data
 109         writeU8(os, 1); // serialisation version
 110         writeU16(os, areas_map.size()); //DANGER: not platform independent
 111         forEach(&serialize_area, &os);
 112 }
 113
 114 #endif
 115
 116 void AreaStore::invalidateCache()
 117 {
 118         if (m_cache_enabled) {
 119                 m_res_cache.invalidate();
 120         }
 121 }
 122
 123 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
 124 {
 125         m_cache_enabled = enabled;
 126         m_cacheblock_radius = MYMAX(block_radius, 16);
 127         m_res_cache.setLimit(MYMAX(limit, 20));
 128         invalidateCache();
 129 }
 130
 131 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
 132 {
 133         AreaStore *as = (AreaStore *)data;
 134         u8 r = as->m_cacheblock_radius;
 135
 136         // get the points at the edges of the mapblock
 137         v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
 138         v3s16 maxedge(
 139                 minedge.X + r - 1,
 140                 minedge.Y + r - 1,
 141                 minedge.Z + r - 1);
 142
 143         as->getAreasInArea(dest, minedge, maxedge, true);
 144
 145         /* infostream << "Cache miss with " << dest->size() << " areas, between ("
 146                         << minedge.X << ", " << minedge.Y << ", " << minedge.Z
 147                         << ") and ("
 148                         << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
 149                         << ")" << std::endl; // */
 150 }
 151
 152 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
 153 {
 154         if (m_cache_enabled) {
 155                 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
 156                 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
 157
 158                 size_t s_p_l = pre_list->size();
 159                 for (size_t i = 0; i < s_p_l; i++) {
 160                         Area *b = (*pre_list)[i];
 161                         if (AST_CONTAINS_PT(b, pos)) {
 162                                 result->push_back(b);
 163                         }
 164                 }
 165         } else {
 166                 return getAreasForPosImpl(result, pos);
 167         }
 168 }
 169
 170
 171 ////
 172 // VectorAreaStore
 173 ////
 174
 175
 176 bool VectorAreaStore::insertArea(Area *a)
 177 {
 178         a->id = getNextId();
 179         std::pair<AreaMap::iterator, bool> res =
 180                         areas_map.insert(std::make_pair(a->id, *a));
 181         if (!res.second)
 182                 // ID is not unique
 183                 return false;
 184         m_areas.push_back(&res.first->second);
 185         invalidateCache();
 186         return true;
 187 }
 188
 189 bool VectorAreaStore::removeArea(u32 id)
 190 {
 191         AreaMap::iterator it = areas_map.find(id);
 192         if (it == areas_map.end())
 193                 return false;
 194         Area *a = &it->second;
 195         for (std::vector<Area *>::iterator v_it = m_areas.begin();
 196                         v_it != m_areas.end(); ++v_it) {
 197                 if (*v_it == a) {
 198                         m_areas.erase(v_it);
 199                         break;
 200                 }
 201         }
 202         areas_map.erase(it);
 203         invalidateCache();
 204         return true;
 205 }
 206
 207 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 208 {
 209         for (size_t i = 0; i < m_areas.size(); ++i) {
 210                 Area *b = m_areas[i];
 211                 if (AST_CONTAINS_PT(b, pos)) {
 212                         result->push_back(b);
 213                 }
 214         }
 215 }
 216
 217 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
 218                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 219 {
 220         for (size_t i = 0; i < m_areas.size(); ++i) {
 221                 Area *b = m_areas[i];
 222                 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
 223                                 AST_CONTAINS_AREA(minedge, maxedge, b)) {
 224                         result->push_back(b);
 225                 }
 226         }
 227 }
 228
 229 #if 0
 230 bool SimpleAreaStore::forEach(ForEachCallback callback, void *arg) const
 231 {
 232         for (size_t i = 0; i < m_areas.size(); ++i) {
 233                 if (callback(m_areas[i], arg)) {
 234                         return true;
 235                 }
 236         }
 237         return false;
 238 }
 239 #endif
 240
 241 #if USE_SPATIAL
 242
 243 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
 244                 const v3s16 maxedge)
 245 {
 246         const double p_low[] = {(double)minedge.X,
 247                 (double)minedge.Y, (double)minedge.Z};
 248         const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
 249                 (double)maxedge.Z};
 250         return SpatialIndex::Region(p_low, p_high, 3);
 251 }
 252
 253 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
 254 {
 255         const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
 256         return SpatialIndex::Point(p, 3);
 257 }
 258
 259
 260 bool SpatialAreaStore::insertArea(Area *a)
 261 {
 262         a->id = getNextId();
 263         if (!areas_map.insert(std::make_pair(a->id, *a)).second)
 264                 // ID is not unique
 265                 return false;
 266         m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
 267         invalidateCache();
 268         return true;
 269 }
 270
 271 bool SpatialAreaStore::removeArea(u32 id)
 272 {
 273         std::map<u32, Area>::iterator itr = areas_map.find(id);
 274         if (itr != areas_map.end()) {
 275                 Area *a = &itr->second;
 276                 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
 277                         a->maxedge), id);
 278                 areas_map.erase(itr);
 279                 invalidateCache();
 280                 return result;
 281         } else {
 282                 return false;
 283         }
 284 }
 285
 286 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 287 {
 288         VectorResultVisitor visitor(result, this);
 289         m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
 290 }
 291
 292 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
 293                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 294 {
 295         VectorResultVisitor visitor(result, this);
 296         if (accept_overlap) {
 297                 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
 298                         visitor);
 299         } else {
 300                 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
 301         }
 302 }
 303
 304 #if 0
 305 bool SpatialAreaStore::forEach(ForEachCallback callback, void *arg) const
 306 {
 307         // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation)
 308         return false;
 309 }
 310 #endif
 311
 312 SpatialAreaStore::~SpatialAreaStore()
 313 {
 314         delete m_tree;
 315 }
 316
 317 SpatialAreaStore::SpatialAreaStore()
 318 {
 319         m_storagemanager =
 320                 SpatialIndex::StorageManager::createNewMemoryStorageManager();
 321         SpatialIndex::id_type id;
 322         m_tree = SpatialIndex::RTree::createNewRTree(
 323                 *m_storagemanager,
 324                 .7, // Fill factor
 325                 100, // Index capacity
 326                 100, // Leaf capacity
 327                 3, // dimension :)
 328                 SpatialIndex::RTree::RV_RSTAR,
 329                 id);
 330 }
 331
 332 #endif