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 #pragma once
  21
  22 #include "irr_v3d.h"
  23 #include "noise.h" // for PcgRandom
  24 #include <map>
  25 #include <list>
  26 #include <vector>
  27 #include <istream>
  28 #include "util/container.h"
  29 #include "util/numeric.h"
  30 #ifndef ANDROID
  31         #include "cmake_config.h"
  32 #endif
  33 #if USE_SPATIAL
  34         #include <spatialindex/SpatialIndex.h>
  35         #include "util/serialize.h"
  36 #endif
  37
  38
  39 struct Area {
  40         Area() = default;
  41
  42         Area(const v3s16 &mine, const v3s16 &maxe) :
  43                 minedge(mine), maxedge(maxe)
  44         {
  45                 sortBoxVerticies(minedge, maxedge);
  46         }
  47
  48         u32 id = U32_MAX;
  49         v3s16 minedge, maxedge;
  50         std::string data;
  51 };
  52
  53
  54 class AreaStore {
  55 public:
  56         AreaStore() :
  57                 m_res_cache(1000, &cacheMiss, this)
  58         {}
  59
  60         virtual ~AreaStore() = default;
  61
  62         static AreaStore *getOptimalImplementation();
  63
  64         virtual void reserve(size_t count) {};
  65         size_t size() const { return areas_map.size(); }
  66
  67         /// Add an area to the store.
  68         /// Updates the area's ID if it hasn't already been set.
  69         /// @return Whether the area insertion was successful.
  70         virtual bool insertArea(Area *a) = 0;
  71
  72         /// Removes an area from the store by ID.
  73         /// @return Whether the area was in the store and removed.
  74         virtual bool removeArea(u32 id) = 0;
  75
  76         /// Finds areas that the passed position is contained in.
  77         /// Stores output in passed vector.
  78         void getAreasForPos(std::vector<Area *> *result, v3s16 pos);
  79
  80         /// Finds areas that are completely contained inside the area defined
  81         /// by the passed edges.  If @p accept_overlap is true this finds any
  82         /// areas that intersect with the passed area at any point.
  83         virtual void getAreasInArea(std::vector<Area *> *result,
  84                 v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0;
  85
  86         /// Sets cache parameters.
  87         void setCacheParams(bool enabled, u8 block_radius, size_t limit);
  88
  89         /// Returns a pointer to the area coresponding to the passed ID,
  90         /// or NULL if it doesn't exist.
  91         const Area *getArea(u32 id) const;
  92
  93         /// Serializes the store's areas to a binary ostream.
  94         void serialize(std::ostream &is) const;
  95
  96         /// Deserializes the Areas from a binary istream.
  97         /// This does not currently clear the AreaStore before adding the
  98         /// areas, making it possible to deserialize multiple serialized
  99         /// AreaStores.
 100         void deserialize(std::istream &is);
 101
 102 protected:
 103         /// Invalidates the getAreasForPos cache.
 104         /// Call after adding or removing an area.
 105         void invalidateCache();
 106
 107         /// Implementation of getAreasForPos.
 108         /// getAreasForPos calls this if the cache is disabled.
 109         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos) = 0;
 110
 111         /// Returns the next area ID and increments it.
 112         u32 getNextId() { return m_next_id++; }
 113
 114         // Note: This can't be an unordered_map, since all
 115         // references would be invalidated on rehash.
 116         typedef std::map<u32, Area> AreaMap;
 117         AreaMap areas_map;
 118
 119 private:
 120         /// Called by the cache when a value isn't found in the cache.
 121         static void cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest);
 122
 123         bool m_cache_enabled = true;
 124         /// Range, in nodes, of the getAreasForPos cache.
 125         /// If you modify this, call invalidateCache()
 126         u8 m_cacheblock_radius = 64;
 127         LRUCache<v3s16, std::vector<Area *> > m_res_cache;
 128
 129         u32 m_next_id = 0;
 130 };
 131
 132
 133 class VectorAreaStore : public AreaStore {
 134 public:
 135         virtual void reserve(size_t count) { m_areas.reserve(count); }
 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
 141 protected:
 142         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
 143
 144 private:
 145         std::vector<Area *> m_areas;
 146 };
 147
 148
 149 #if USE_SPATIAL
 150
 151 class SpatialAreaStore : public AreaStore {
 152 public:
 153         SpatialAreaStore();
 154         virtual ~SpatialAreaStore();
 155
 156         virtual bool insertArea(Area *a);
 157         virtual bool removeArea(u32 id);
 158         virtual void getAreasInArea(std::vector<Area *> *result,
 159                 v3s16 minedge, v3s16 maxedge, bool accept_overlap);
 160
 161 protected:
 162         virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
 163
 164 private:
 165         SpatialIndex::ISpatialIndex *m_tree = nullptr;
 166         SpatialIndex::IStorageManager *m_storagemanager = nullptr;
 167
 168         class VectorResultVisitor : public SpatialIndex::IVisitor {
 169         public:
 170                 VectorResultVisitor(std::vector<Area *> *result, SpatialAreaStore *store) :
 171                         m_store(store),
 172                         m_result(result)
 173                 {}
 174                 ~VectorResultVisitor() {}
 175
 176                 virtual void visitNode(const SpatialIndex::INode &in) {}
 177
 178                 virtual void visitData(const SpatialIndex::IData &in)
 179                 {
 180                         u32 id = in.getIdentifier();
 181
 182                         std::map<u32, Area>::iterator itr = m_store->areas_map.find(id);
 183                         assert(itr != m_store->areas_map.end());
 184                         m_result->push_back(&itr->second);
 185                 }
 186
 187                 virtual void visitData(std::vector<const SpatialIndex::IData *> &v)
 188                 {
 189                         for (size_t i = 0; i < v.size(); i++)
 190                                 visitData(*(v[i]));
 191                 }
 192
 193         private:
 194                 SpatialAreaStore *m_store = nullptr;
 195                 std::vector<Area *> *m_result = nullptr;
 196         };
 197 };
 198
 199 #endif // USE_SPATIAL