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