areastore.h 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197
  1. /*
  2. Minetest
  3. Copyright (C) 2015 est31 <mtest31@outlook.com>
  4. This program is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU Lesser General Public License as published by
  6. the Free Software Foundation; either version 2.1 of the License, or
  7. (at your option) any later version.
  8. This program is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11. GNU Lesser General Public License for more details.
  12. You should have received a copy of the GNU Lesser General Public License along
  13. with this program; if not, write to the Free Software Foundation, Inc.,
  14. 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  15. */
  16. #pragma once
  17. #include "irr_v3d.h"
  18. #include "noise.h" // for PcgRandom
  19. #include <map>
  20. #include <list>
  21. #include <vector>
  22. #include <istream>
  23. #include "util/container.h"
  24. #include "util/numeric.h"
  25. #ifndef ANDROID
  26. #include "cmake_config.h"
  27. #endif
  28. #if USE_SPATIAL
  29. #include <spatialindex/SpatialIndex.h>
  30. #include "util/serialize.h"
  31. #endif
  32. struct Area {
  33. Area(u32 area_id) : id(area_id) {}
  34. Area(const v3s16 &mine, const v3s16 &maxe, u32 area_id = U32_MAX) :
  35. id(area_id), minedge(mine), maxedge(maxe)
  36. {
  37. sortBoxVerticies(minedge, maxedge);
  38. }
  39. u32 id;
  40. v3s16 minedge, maxedge;
  41. std::string data;
  42. };
  43. class AreaStore {
  44. public:
  45. AreaStore() :
  46. m_res_cache(1000, &cacheMiss, this)
  47. {}
  48. virtual ~AreaStore() = default;
  49. static AreaStore *getOptimalImplementation();
  50. virtual void reserve(size_t count) {};
  51. size_t size() const { return areas_map.size(); }
  52. /// Add an area to the store.
  53. /// Updates the area's ID if it hasn't already been set.
  54. /// @return Whether the area insertion was successful.
  55. virtual bool insertArea(Area *a) = 0;
  56. /// Removes an area from the store by ID.
  57. /// @return Whether the area was in the store and removed.
  58. virtual bool removeArea(u32 id) = 0;
  59. /// Finds areas that the passed position is contained in.
  60. /// Stores output in passed vector.
  61. void getAreasForPos(std::vector<Area *> *result, v3s16 pos);
  62. /// Finds areas that are completely contained inside the area defined
  63. /// by the passed edges. If @p accept_overlap is true this finds any
  64. /// areas that intersect with the passed area at any point.
  65. virtual void getAreasInArea(std::vector<Area *> *result,
  66. v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0;
  67. /// Sets cache parameters.
  68. void setCacheParams(bool enabled, u8 block_radius, size_t limit);
  69. /// Returns a pointer to the area coresponding to the passed ID,
  70. /// or NULL if it doesn't exist.
  71. const Area *getArea(u32 id) const;
  72. /// Serializes the store's areas to a binary ostream.
  73. void serialize(std::ostream &is) const;
  74. /// Deserializes the Areas from a binary istream.
  75. /// This does not currently clear the AreaStore before adding the
  76. /// areas, making it possible to deserialize multiple serialized
  77. /// AreaStores.
  78. void deserialize(std::istream &is);
  79. protected:
  80. /// Invalidates the getAreasForPos cache.
  81. /// Call after adding or removing an area.
  82. void invalidateCache();
  83. /// Implementation of getAreasForPos.
  84. /// getAreasForPos calls this if the cache is disabled.
  85. virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos) = 0;
  86. /// Returns the next area ID and increments it.
  87. u32 getNextId() const;
  88. // Note: This can't be an unordered_map, since all
  89. // references would be invalidated on rehash.
  90. typedef std::map<u32, Area> AreaMap;
  91. AreaMap areas_map;
  92. private:
  93. /// Called by the cache when a value isn't found in the cache.
  94. static void cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest);
  95. bool m_cache_enabled = true;
  96. /// Range, in nodes, of the getAreasForPos cache.
  97. /// If you modify this, call invalidateCache()
  98. u8 m_cacheblock_radius = 64;
  99. LRUCache<v3s16, std::vector<Area *> > m_res_cache;
  100. };
  101. class VectorAreaStore : public AreaStore {
  102. public:
  103. virtual void reserve(size_t count) { m_areas.reserve(count); }
  104. virtual bool insertArea(Area *a);
  105. virtual bool removeArea(u32 id);
  106. virtual void getAreasInArea(std::vector<Area *> *result,
  107. v3s16 minedge, v3s16 maxedge, bool accept_overlap);
  108. protected:
  109. virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
  110. private:
  111. std::vector<Area *> m_areas;
  112. };
  113. #if USE_SPATIAL
  114. class SpatialAreaStore : public AreaStore {
  115. public:
  116. SpatialAreaStore();
  117. virtual ~SpatialAreaStore();
  118. virtual bool insertArea(Area *a);
  119. virtual bool removeArea(u32 id);
  120. virtual void getAreasInArea(std::vector<Area *> *result,
  121. v3s16 minedge, v3s16 maxedge, bool accept_overlap);
  122. protected:
  123. virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
  124. private:
  125. SpatialIndex::ISpatialIndex *m_tree = nullptr;
  126. SpatialIndex::IStorageManager *m_storagemanager = nullptr;
  127. class VectorResultVisitor : public SpatialIndex::IVisitor {
  128. public:
  129. VectorResultVisitor(std::vector<Area *> *result, SpatialAreaStore *store) :
  130. m_store(store),
  131. m_result(result)
  132. {}
  133. ~VectorResultVisitor() {}
  134. virtual void visitNode(const SpatialIndex::INode &in) {}
  135. virtual void visitData(const SpatialIndex::IData &in)
  136. {
  137. u32 id = in.getIdentifier();
  138. std::map<u32, Area>::iterator itr = m_store->areas_map.find(id);
  139. assert(itr != m_store->areas_map.end());
  140. m_result->push_back(&itr->second);
  141. }
  142. virtual void visitData(std::vector<const SpatialIndex::IData *> &v)
  143. {
  144. for (size_t i = 0; i < v.size(); i++)
  145. visitData(*(v[i]));
  146. }
  147. private:
  148. SpatialAreaStore *m_store = nullptr;
  149. std::vector<Area *> *m_result = nullptr;
  150. };
  151. };
  152. #endif // USE_SPATIAL