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<std::map<u32, Area>::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 void VectorAreaStore::reserve(size_t count)
 197 {
 198         m_areas.reserve(count);
 199 }
 200
 201 bool VectorAreaStore::removeArea(u32 id)
 202 {
 203         std::map<u32, Area>::iterator itr = areas_map.find(id);
 204         if (itr != areas_map.end()) {
 205                 size_t msiz = m_areas.size();
 206                 for (size_t i = 0; i < msiz; i++) {
 207                         Area * b = m_areas[i];
 208                         if (b->id == id) {
 209                                 areas_map.erase(itr);
 210                                 m_areas.erase(m_areas.begin() + i);
 211                                 invalidateCache();
 212                                 return true;
 213                         }
 214                 }
 215                 // we should never get here, it means we did find it in map,
 216                 // but not in the vector
 217         }
 218         return false;
 219 }
 220
 221 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 222 {
 223         size_t msiz = m_areas.size();
 224         for (size_t i = 0; i < msiz; i++) {
 225                 Area *b = m_areas[i];
 226                 if (AST_CONTAINS_PT(b, pos)) {
 227                         result->push_back(b);
 228                 }
 229         }
 230 }
 231
 232 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
 233                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 234 {
 235         size_t msiz = m_areas.size();
 236         for (size_t i = 0; i < msiz; i++) {
 237                 Area * b = m_areas[i];
 238                 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
 239                                 AST_CONTAINS_AREA(minedge, maxedge, b)) {
 240                         result->push_back(b);
 241                 }
 242         }
 243 }
 244
 245 #if 0
 246 bool VectorAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
 247 {
 248         size_t msiz = m_areas.size();
 249         for (size_t i = 0; i < msiz; i++) {
 250                 if (callback(args, m_areas[i])) {
 251                         return true;
 252                 }
 253         }
 254         return false;
 255 }
 256 #endif
 257
 258 #if USE_SPATIAL
 259
 260 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
 261                 const v3s16 maxedge)
 262 {
 263         const double p_low[] = {(double)minedge.X,
 264                 (double)minedge.Y, (double)minedge.Z};
 265         const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
 266                 (double)maxedge.Z};
 267         return SpatialIndex::Region(p_low, p_high, 3);
 268 }
 269
 270 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
 271 {
 272         const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
 273         return SpatialIndex::Point(p, 3);
 274 }
 275
 276
 277 bool SpatialAreaStore::insertArea(Area *a)
 278 {
 279         a->id = getNextId();
 280         if (!areas_map.insert(std::make_pair(a->id, *a)).second)
 281                 // ID is not unique
 282                 return false;
 283         m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
 284         invalidateCache();
 285         return true;
 286 }
 287
 288 bool SpatialAreaStore::removeArea(u32 id)
 289 {
 290         std::map<u32, Area>::iterator itr = areas_map.find(id);
 291         if (itr != areas_map.end()) {
 292                 Area *a = &itr->second;
 293                 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
 294                         a->maxedge), id);
 295                 invalidateCache();
 296                 return result;
 297         } else {
 298                 return false;
 299         }
 300 }
 301
 302 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 303 {
 304         VectorResultVisitor visitor(result, this);
 305         m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
 306 }
 307
 308 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
 309                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 310 {
 311         VectorResultVisitor visitor(result, this);
 312         if (accept_overlap) {
 313                 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
 314                         visitor);
 315         } else {
 316                 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
 317         }
 318 }
 319
 320 #if 0
 321 bool SpatialAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
 322 {
 323         // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation)
 324         return false;
 325 }
 326 #endif
 327
 328 SpatialAreaStore::~SpatialAreaStore()
 329 {
 330         delete m_tree;
 331 }
 332
 333 SpatialAreaStore::SpatialAreaStore()
 334 {
 335         m_storagemanager =
 336                 SpatialIndex::StorageManager::createNewMemoryStorageManager();
 337         SpatialIndex::id_type id;
 338         m_tree = SpatialIndex::RTree::createNewRTree(
 339                 *m_storagemanager,
 340                 .7, // Fill factor
 341                 100, // Index capacity
 342                 100, // Leaf capacity
 343                 3, // dimension :)
 344                 SpatialIndex::RTree::RV_RSTAR,
 345                 id);
 346 }
 347
 348 #endif