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 u16 AreaStore::size() const
  48 {
  49         return areas_map.size();
  50 }
  51
  52 const Area *AreaStore::getArea(u32 id) const
  53 {
  54         const Area *res = NULL;
  55         std::map<u32, Area>::const_iterator itr = areas_map.find(id);
  56         if (itr != areas_map.end()) {
  57                 res = &itr->second;
  58         }
  59         return res;
  60 }
  61
  62 #if 0
  63 Currently, serialisation is commented out. This is because of multiple reasons:
  64 1. Why do we store the areastore into a file, why not into the database?
  65 2. We don't use libspatial's serialisation, but we should, or perhaps not, because
  66         it would remove the ability to switch. Perhaps write migration routines?
  67 3. Various things need fixing, e.g. the size is serialized as
  68         c++ implementation defined size_t
  69 bool AreaStore::deserialize(std::istream &is)
  70 {
  71         u8 ver = readU8(is);
  72         if (ver != 1)
  73                 return false;
  74         u16 count_areas = readU16(is);
  75         for (u16 i = 0; i < count_areas; i++) {
  76                 // deserialize an area
  77                 Area a;
  78                 a.id = readU32(is);
  79                 a.minedge = readV3S16(is);
  80                 a.maxedge = readV3S16(is);
  81                 a.datalen = readU16(is);
  82                 a.data = new char[a.datalen];
  83                 is.read((char *) a.data, a.datalen);
  84                 insertArea(a);
  85         }
  86         return true;
  87 }
  88
  89
  90 static bool serialize_area(void *ostr, Area *a)
  91 {
  92         std::ostream &os = *((std::ostream *) ostr);
  93         writeU32(os, a->id);
  94         writeV3S16(os, a->minedge);
  95         writeV3S16(os, a->maxedge);
  96         writeU16(os, a->datalen);
  97         os.write(a->data, a->datalen);
  98
  99         return false;
 100 }
 101
 102
 103 void AreaStore::serialize(std::ostream &os) const
 104 {
 105         // write initial data
 106         writeU8(os, 1); // serialisation version
 107         writeU16(os, areas_map.size()); //DANGER: not platform independent
 108         forEach(&serialize_area, &os);
 109 }
 110
 111 #endif
 112
 113 void AreaStore::invalidateCache()
 114 {
 115         if (m_cache_enabled) {
 116                 m_res_cache.invalidate();
 117         }
 118 }
 119
 120 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
 121 {
 122         m_cache_enabled = enabled;
 123         m_cacheblock_radius = MYMAX(block_radius, 16);
 124         m_res_cache.setLimit(MYMAX(limit, 20));
 125         invalidateCache();
 126 }
 127
 128 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
 129 {
 130         AreaStore *as = (AreaStore *)data;
 131         u8 r = as->m_cacheblock_radius;
 132
 133         // get the points at the edges of the mapblock
 134         v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
 135         v3s16 maxedge(
 136                 minedge.X + r - 1,
 137                 minedge.Y + r - 1,
 138                 minedge.Z + r - 1);
 139
 140         as->getAreasInArea(dest, minedge, maxedge, true);
 141
 142         /* infostream << "Cache miss with " << dest->size() << " areas, between ("
 143                         << minedge.X << ", " << minedge.Y << ", " << minedge.Z
 144                         << ") and ("
 145                         << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
 146                         << ")" << std::endl; // */
 147 }
 148
 149 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
 150 {
 151         if (m_cache_enabled) {
 152                 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
 153                 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
 154
 155                 size_t s_p_l = pre_list->size();
 156                 for (size_t i = 0; i < s_p_l; i++) {
 157                         Area *b = (*pre_list)[i];
 158                         if (AST_CONTAINS_PT(b, pos)) {
 159                                 result->push_back(b);
 160                         }
 161                 }
 162         } else {
 163                 return getAreasForPosImpl(result, pos);
 164         }
 165 }
 166
 167
 168 ////
 169 // VectorAreaStore
 170 ////
 171
 172
 173 bool VectorAreaStore::insertArea(Area *a)
 174 {
 175         a->id = getNextId();
 176         std::pair<std::map<u32, Area>::iterator, bool> res =
 177                         areas_map.insert(std::make_pair(a->id, *a));
 178         if (!res.second)
 179                 // ID is not unique
 180                 return false;
 181         m_areas.push_back(&res.first->second);
 182         invalidateCache();
 183         return true;
 184 }
 185
 186 void VectorAreaStore::reserve(size_t count)
 187 {
 188         m_areas.reserve(count);
 189 }
 190
 191 bool VectorAreaStore::removeArea(u32 id)
 192 {
 193         std::map<u32, Area>::iterator itr = areas_map.find(id);
 194         if (itr != areas_map.end()) {
 195                 size_t msiz = m_areas.size();
 196                 for (size_t i = 0; i < msiz; i++) {
 197                         Area * b = m_areas[i];
 198                         if (b->id == id) {
 199                                 areas_map.erase(itr);
 200                                 m_areas.erase(m_areas.begin() + i);
 201                                 invalidateCache();
 202                                 return true;
 203                         }
 204                 }
 205                 // we should never get here, it means we did find it in map,
 206                 // but not in the vector
 207         }
 208         return false;
 209 }
 210
 211 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 212 {
 213         size_t msiz = m_areas.size();
 214         for (size_t i = 0; i < msiz; i++) {
 215                 Area *b = m_areas[i];
 216                 if (AST_CONTAINS_PT(b, pos)) {
 217                         result->push_back(b);
 218                 }
 219         }
 220 }
 221
 222 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
 223                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 224 {
 225         size_t msiz = m_areas.size();
 226         for (size_t i = 0; i < msiz; i++) {
 227                 Area * b = m_areas[i];
 228                 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
 229                                 AST_CONTAINS_AREA(minedge, maxedge, b)) {
 230                         result->push_back(b);
 231                 }
 232         }
 233 }
 234
 235 #if 0
 236 bool VectorAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
 237 {
 238         size_t msiz = m_areas.size();
 239         for (size_t i = 0; i < msiz; i++) {
 240                 if (callback(args, m_areas[i])) {
 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