src/util/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 AREA_STORE_H_
  21 #define AREA_STORE_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
  40 struct Area {
  41         Area() {}
  42         Area(const v3s16 &mine, const v3s16 &maxe) :
  43                 minedge(mine), maxedge(maxe)
  44         {
  45                 sortBoxVerticies(minedge, maxedge);
  46         }
  47
  48         u32 id;
  49         v3s16 minedge, maxedge;
  50         std::string data;
  51 };
  52
  53
  54 class AreaStore {
  55 public:
  56         AreaStore() :
  57                 m_cache_enabled(true),
  58                 m_cacheblock_radius(64),
  59                 m_res_cache(1000, &cacheMiss, this),
  60                 m_next_id(0)
  61         {}
  62
  63         virtual ~AreaStore() {}
  64
  65         static AreaStore *getOptimalImplementation();
  66
  67         virtual void reserve(size_t count) {};
  68         size_t size() const { return areas_map.size(); }
  69
  70         // Updates the area's ID
  71         virtual bool insertArea(Area *a) = 0;
  72         virtual bool removeArea(u32 id) = 0;
  73         void getAreasForPos(std::vector<Area *> *result, v3s16 pos);
  74         virtual void getAreasInArea(std::vector<Area *> *result,
  75                 v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0;
  76         void setCacheParams(bool enabled, u8 block_radius, size_t limit);
  77
  78         const Area *getArea(u32 id) const;
  79
  80 #if 0
  81         typedef bool (*ForEachCallback)(const Area *a, void *arg);
  82         // Calls a passed function for every stored area, until the
  83         // callback returns true.  If that happens, it returns true,
  84         // if the search is exhausted, it returns false.
  85         virtual bool forEach(ForEachCallback, void *arg=NULL) const = 0;
  86
  87         void serialize(std::ostream &is) const;
  88         bool deserialize(std::istream &is);
  89 #endif
  90
  91 protected:
  92         void invalidateCache();
  93         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos) = 0;
  94         u32 getNextId() { return m_next_id++; }
  95
  96         // Note: This can't be an unordered_map, since all
  97         // references would be invalidated on rehash.
  98         typedef std::map<u32, Area> AreaMap;
  99         AreaMap areas_map;
 100
 101 private:
 102         static void cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest);
 103
 104         bool m_cache_enabled;
 105         u8 m_cacheblock_radius; // if you modify this, call invalidateCache()
 106         LRUCache<v3s16, std::vector<Area *> > m_res_cache;
 107
 108         u32 m_next_id;
 109 };
 110
 111
 112 class VectorAreaStore : public AreaStore {
 113 public:
 114         virtual void reserve(size_t count) { m_areas.reserve(count); }
 115         virtual bool insertArea(Area *a);
 116         virtual bool removeArea(u32 id);
 117         virtual void getAreasInArea(std::vector<Area *> *result,
 118                 v3s16 minedge, v3s16 maxedge, bool accept_overlap);
 119         //virtual bool forEach(ForEachCallback, void *arg) const;
 120
 121 protected:
 122         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
 123
 124 private:
 125         std::vector<Area *> m_areas;
 126 };
 127
 128
 129 #if USE_SPATIAL
 130
 131 class SpatialAreaStore : public AreaStore {
 132 public:
 133         SpatialAreaStore();
 134         virtual ~SpatialAreaStore();
 135
 136         virtual bool insertArea(Area *a);
 137         virtual bool removeArea(u32 id);
 138         virtual void getAreasInArea(std::vector<Area *> *result,
 139                 v3s16 minedge, v3s16 maxedge, bool accept_overlap);
 140         //virtual bool forEach(ForEachCallback, void *arg) const;
 141
 142 protected:
 143         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
 144
 145 private:
 146         SpatialIndex::ISpatialIndex *m_tree;
 147         SpatialIndex::IStorageManager *m_storagemanager;
 148
 149         class VectorResultVisitor : public SpatialIndex::IVisitor {
 150         public:
 151                 VectorResultVisitor(std::vector<Area *> *result, SpatialAreaStore *store) :
 152                         m_store(store),
 153                         m_result(result)
 154                 {}
 155                 ~VectorResultVisitor() {}
 156
 157                 virtual void visitNode(const SpatialIndex::INode &in) {}
 158
 159                 virtual void visitData(const SpatialIndex::IData &in)
 160                 {
 161                         u32 id = in.getIdentifier();
 162
 163                         std::map<u32, Area>::iterator itr = m_store->areas_map.find(id);
 164                         assert(itr != m_store->areas_map.end());
 165                         m_result->push_back(&itr->second);
 166                 }
 167
 168                 virtual void visitData(std::vector<const SpatialIndex::IData *> &v)
 169                 {
 170                         for (size_t i = 0; i < v.size(); i++)
 171                                 visitData(*(v[i]));
 172                 }
 173
 174         private:
 175                 SpatialAreaStore *m_store;
 176                 std::vector<Area *> *m_result;
 177         };
 178 };
 179
 180 #endif // USE_SPATIAL
 181
 182 #endif // AREA_STORE_H_