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 u16 AreaStore::size() const
  58 {
  59         return areas_map.size();
  60 }
  61
  62 const Area *AreaStore::getArea(u32 id) const
  63 {
  64         const Area *res = NULL;
  65         std::map<u32, Area>::const_iterator itr = areas_map.find(id);
  66         if (itr != areas_map.end()) {
  67                 res = &itr->second;
  68         }
  69         return res;
  70 }
  71
  72 #if 0
  73 Currently, serialisation is commented out. This is because of multiple reasons:
  74 1. Why do we store the areastore into a file, why not into the database?
  75 2. We don't use libspatial's serialisation, but we should, or perhaps not, because
  76         it would remove the ability to switch. Perhaps write migration routines?
  77 3. Various things need fixing, e.g. the size is serialized as
  78         c++ implementation defined size_t
  79 bool AreaStore::deserialize(std::istream &is)
  80 {
  81         u8 ver = readU8(is);
  82         if (ver != 1)
  83                 return false;
  84         u16 count_areas = readU16(is);
  85         for (u16 i = 0; i < count_areas; i++) {
  86                 // deserialize an area
  87                 Area a;
  88                 a.id = readU32(is);
  89                 a.minedge = readV3S16(is);
  90                 a.maxedge = readV3S16(is);
  91                 a.datalen = readU16(is);
  92                 a.data = new char[a.datalen];
  93                 is.read((char *) a.data, a.datalen);
  94                 insertArea(a);
  95         }
  96         return true;
  97 }
  98
  99
 100 static bool serialize_area(void *ostr, Area *a)
 101 {
 102         std::ostream &os = *((std::ostream *) ostr);
 103         writeU32(os, a->id);
 104         writeV3S16(os, a->minedge);
 105         writeV3S16(os, a->maxedge);
 106         writeU16(os, a->datalen);
 107         os.write(a->data, a->datalen);
 108
 109         return false;
 110 }
 111
 112
 113 void AreaStore::serialize(std::ostream &os) const
 114 {
 115         // write initial data
 116         writeU8(os, 1); // serialisation version
 117         writeU16(os, areas_map.size()); //DANGER: not platform independent
 118         forEach(&serialize_area, &os);
 119 }
 120
 121 #endif
 122
 123 void AreaStore::invalidateCache()
 124 {
 125         if (m_cache_enabled) {
 126                 m_res_cache.invalidate();
 127         }
 128 }
 129
 130 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
 131 {
 132         m_cache_enabled = enabled;
 133         m_cacheblock_radius = MYMAX(block_radius, 16);
 134         m_res_cache.setLimit(MYMAX(limit, 20));
 135         invalidateCache();
 136 }
 137
 138 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
 139 {
 140         AreaStore *as = (AreaStore *)data;
 141         u8 r = as->m_cacheblock_radius;
 142
 143         // get the points at the edges of the mapblock
 144         v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
 145         v3s16 maxedge(
 146                 minedge.X + r - 1,
 147                 minedge.Y + r - 1,
 148                 minedge.Z + r - 1);
 149
 150         as->getAreasInArea(dest, minedge, maxedge, true);
 151
 152         /* infostream << "Cache miss with " << dest->size() << " areas, between ("
 153                         << minedge.X << ", " << minedge.Y << ", " << minedge.Z
 154                         << ") and ("
 155                         << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
 156                         << ")" << std::endl; // */
 157 }
 158
 159 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
 160 {
 161         if (m_cache_enabled) {
 162                 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
 163                 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
 164
 165                 size_t s_p_l = pre_list->size();
 166                 for (size_t i = 0; i < s_p_l; i++) {
 167                         Area *b = (*pre_list)[i];
 168                         if (AST_CONTAINS_PT(b, pos)) {
 169                                 result->push_back(b);
 170                         }
 171                 }
 172         } else {
 173                 return getAreasForPosImpl(result, pos);
 174         }
 175 }
 176
 177
 178 ////
 179 // VectorAreaStore
 180 ////
 181
 182
 183 bool VectorAreaStore::insertArea(Area *a)
 184 {
 185         a->id = getNextId();
 186         std::pair<AreaMap::iterator, bool> res =
 187                         areas_map.insert(std::make_pair(a->id, *a));
 188         if (!res.second)
 189                 // ID is not unique
 190                 return false;
 191         m_areas.push_back(&res.first->second);
 192         invalidateCache();
 193         return true;
 194 }
 195
 196 bool VectorAreaStore::removeArea(u32 id)
 197 {
 198         AreaMap::iterator it = areas_map.find(id);
 199         if (it == areas_map.end())
 200                 return false;
 201         Area *a = &it->second;
 202         for (std::vector<Area *>::iterator v_it = m_areas.begin();
 203                         v_it != m_areas.end(); ++v_it) {
 204                 if (*v_it == a) {
 205                         m_areas.erase(v_it);
 206                         break;
 207                 }
 208         }
 209         areas_map.erase(it);
 210         invalidateCache();
 211         return true;
 212 }
 213
 214 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 215 {
 216         for (size_t i = 0; i < m_areas.size(); ++i) {
 217                 Area *b = m_areas[i];
 218                 if (AST_CONTAINS_PT(b, pos)) {
 219                         result->push_back(b);
 220                 }
 221         }
 222 }
 223
 224 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
 225                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 226 {
 227         for (size_t i = 0; i < m_areas.size(); ++i) {
 228                 Area *b = m_areas[i];
 229                 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
 230                                 AST_CONTAINS_AREA(minedge, maxedge, b)) {
 231                         result->push_back(b);
 232                 }
 233         }
 234 }
 235
 236 #if 0
 237 bool SimpleAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
 238 {
 239         for (size_t i = 0; i < m_areas.size(); ++i) {
 240                 if (callback(m_areas[i], arg)) {
 241                         return true;
 242                 }
 243         }
 244         return false;
 245 }
 246 #endif
 247
 248 #if USE_SPATIAL
 249
 250 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
 251                 const v3s16 maxedge)
 252 {
 253         const double p_low[] = {(double)minedge.X,
 254                 (double)minedge.Y, (double)minedge.Z};
 255         const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
 256                 (double)maxedge.Z};
 257         return SpatialIndex::Region(p_low, p_high, 3);
 258 }
 259
 260 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
 261 {
 262         const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
 263         return SpatialIndex::Point(p, 3);
 264 }
 265
 266
 267 bool SpatialAreaStore::insertArea(Area *a)
 268 {
 269         a->id = getNextId();
 270         if (!areas_map.insert(std::make_pair(a->id, *a)).second)
 271                 // ID is not unique
 272                 return false;
 273         m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
 274         invalidateCache();
 275         return true;
 276 }
 277
 278 bool SpatialAreaStore::removeArea(u32 id)
 279 {
 280         std::map<u32, Area>::iterator itr = areas_map.find(id);
 281         if (itr != areas_map.end()) {
 282                 Area *a = &itr->second;
 283                 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
 284                         a->maxedge), id);
 285                 invalidateCache();
 286                 return result;
 287         } else {
 288                 return false;
 289         }
 290 }
 291
 292 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 293 {
 294         VectorResultVisitor visitor(result, this);
 295         m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
 296 }
 297
 298 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
 299                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 300 {
 301         VectorResultVisitor visitor(result, this);
 302         if (accept_overlap) {
 303                 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
 304                         visitor);
 305         } else {
 306                 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
 307         }
 308 }
 309
 310 #if 0
 311 bool SpatialAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
 312 {
 313         // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation)
 314         return false;
 315 }
 316 #endif
 317
 318 SpatialAreaStore::~SpatialAreaStore()
 319 {
 320         delete m_tree;
 321 }
 322
 323 SpatialAreaStore::SpatialAreaStore()
 324 {
 325         m_storagemanager =
 326                 SpatialIndex::StorageManager::createNewMemoryStorageManager();
 327         SpatialIndex::id_type id;
 328         m_tree = SpatialIndex::RTree::createNewRTree(
 329                 *m_storagemanager,
 330                 .7, // Fill factor
 331                 100, // Index capacity
 332                 100, // Leaf capacity
 333                 3, // dimension :)
 334                 SpatialIndex::RTree::RV_RSTAR,
 335                 id);
 336 }
 337
 338 #endif