src/areastore.h

   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 #ifndef AREASTORE_H_
  21 #define AREASTORE_H_
  22
  23 #include "irr_v3d.h"
  24 #include "noise.h" // for PcgRandom
  25 #include <map>
  26 #include <list>
  27 #include <vector>
  28 #include <istream>
  29 #include "util/container.h"
  30 #include "util/numeric.h"
  31 #ifndef ANDROID
  32         #include "cmake_config.h"
  33 #endif
  34 #if USE_SPATIAL
  35         #include <spatialindex/SpatialIndex.h>
  36         #include "util/serialize.h"
  37 #endif
  38
  39 #define AST_EXTREMIFY(min, max, pa, pb) \
  40         (min).X = MYMIN((pa).X, (pb).X);    \
  41         (min).Y = MYMIN((pa).Y, (pb).Y);    \
  42         (min).Z = MYMIN((pa).Z, (pb).Z);    \
  43         (max).X = MYMAX((pa).X, (pb).X);    \
  44         (max).Y = MYMAX((pa).Y, (pb).Y);    \
  45         (max).Z = MYMAX((pa).Z, (pb).Z);
  46
  47 #define AREA_ID_INVALID 0
  48
  49 struct Area {
  50         Area(const v3s16 &minedge, const v3s16 &maxedge)
  51         {
  52                 this->minedge = minedge;
  53                 this->maxedge = maxedge;
  54         }
  55
  56         Area() {}
  57
  58         void extremifyEdges()
  59         {
  60                 v3s16 nminedge;
  61                 v3s16 nmaxedge;
  62
  63                 AST_EXTREMIFY(nminedge, nmaxedge, minedge, maxedge)
  64
  65                 maxedge = nmaxedge;
  66                 minedge = nminedge;
  67         }
  68
  69         u32 id;
  70         v3s16 minedge;
  71         v3s16 maxedge;
  72         std::string data;
  73 };
  74
  75 std::vector<std::string> get_areastore_typenames();
  76
  77 class AreaStore {
  78 protected:
  79         // TODO change to unordered_map when we can
  80         std::map<u32, Area> areas_map;
  81         void invalidateCache();
  82         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos) = 0;
  83         bool cache_enabled; // don't write to this from subclasses, only read.
  84 public:
  85         virtual void insertArea(const Area &a) = 0;
  86         virtual void reserve(size_t count) {};
  87         virtual bool removeArea(u32 id) = 0;
  88         void getAreasForPos(std::vector<Area *> *result, v3s16 pos);
  89         virtual void getAreasInArea(std::vector<Area *> *result,
  90                 v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0;
  91
  92 #if 0
  93         // calls a passed function for every stored area, until the
  94         // callback returns true. If that happens, it returns true,
  95         // if the search is exhausted, it returns false
  96         virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const = 0;
  97 #endif
  98
  99         virtual ~AreaStore()
 100         {}
 101
 102         AreaStore() :
 103                 cache_enabled(true),
 104                 m_cacheblock_radius(64),
 105                 m_res_cache(1000, &cacheMiss, this),
 106                 m_highest_id(0)
 107         {
 108         }
 109
 110         void setCacheParams(bool enabled, u8 block_radius, size_t limit);
 111
 112         u32 getFreeId(v3s16 minedge, v3s16 maxedge);
 113         const Area *getArea(u32 id) const;
 114         u16 size() const;
 115 #if 0
 116         bool deserialize(std::istream &is);
 117         void serialize(std::ostream &is) const;
 118 #endif
 119 private:
 120         static void cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest);
 121         u8 m_cacheblock_radius; // if you modify this, call invalidateCache()
 122         LRUCache<v3s16, std::vector<Area *> > m_res_cache;
 123         u32 m_highest_id;
 124
 125 };
 126
 127
 128 class VectorAreaStore : public AreaStore {
 129 protected:
 130         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
 131 public:
 132         virtual void insertArea(const Area &a);
 133         virtual void reserve(size_t count);
 134         virtual bool removeArea(u32 id);
 135         virtual void getAreasInArea(std::vector<Area *> *result,
 136                 v3s16 minedge, v3s16 maxedge, bool accept_overlap);
 137         // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const;
 138 private:
 139         std::vector<Area *> m_areas;
 140 };
 141
 142 #if USE_SPATIAL
 143
 144 class SpatialAreaStore : public AreaStore {
 145 protected:
 146         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
 147 public:
 148         SpatialAreaStore();
 149         virtual void insertArea(const Area &a);
 150         virtual bool removeArea(u32 id);
 151         virtual void getAreasInArea(std::vector<Area *> *result,
 152                 v3s16 minedge, v3s16 maxedge, bool accept_overlap);
 153         // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const;
 154
 155         virtual ~SpatialAreaStore();
 156 private:
 157         SpatialIndex::ISpatialIndex *m_tree;
 158         SpatialIndex::IStorageManager *m_storagemanager;
 159
 160         class VectorResultVisitor : public SpatialIndex::IVisitor {
 161         private:
 162                 SpatialAreaStore *m_store;
 163                 std::vector<Area *> *m_result;
 164         public:
 165                 VectorResultVisitor(std::vector<Area *> *result, SpatialAreaStore *store)
 166                 {
 167                         m_store = store;
 168                         m_result = result;
 169                 }
 170
 171                 virtual void visitNode(const SpatialIndex::INode &in)
 172                 {
 173                 }
 174
 175                 virtual void visitData(const SpatialIndex::IData &in)
 176                 {
 177                         u32 id = in.getIdentifier();
 178
 179                         std::map<u32, Area>::iterator itr = m_store->areas_map.find(id);
 180                         assert(itr != m_store->areas_map.end());
 181                         m_result->push_back(&itr->second);
 182                 }
 183
 184                 virtual void visitData(std::vector<const SpatialIndex::IData *> &v)
 185                 {
 186                         for (size_t i = 0; i < v.size(); i++)
 187                                 visitData(*(v[i]));
 188                 }
 189
 190                 ~VectorResultVisitor() {}
 191         };
 192 };
 193
 194 #endif
 195
 196 #endif /* AREASTORE_H_ */