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