3 Copyright (C) 2015 est31 <mtest31@outlook.com>
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.
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.
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.
20 #include "util/areastore.h"
21 #include "util/serialize.h"
22 #include "util/container.h"
25 #include <spatialindex/SpatialIndex.h>
26 #include <spatialindex/RTree.h>
27 #include <spatialindex/Point.h>
30 #define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z))
32 #define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \
33 (!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d)))
35 #define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \
36 AST_SMALLER_EQ_AS((p), (a)->maxedge))
38 #define AST_CONTAINS_AREA(amine, amaxe, b) \
39 (AST_SMALLER_EQ_AS((amine), (b)->minedge) \
40 && AST_SMALLER_EQ_AS((b)->maxedge, (amaxe)))
42 #define AST_AREAS_OVERLAP(amine, amaxe, b) \
43 (AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), X) && \
44 AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Y) && \
45 AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Z))
48 AreaStore *AreaStore::getOptimalImplementation()
51 return new SpatialAreaStore();
53 return new VectorAreaStore();
57 const Area *AreaStore::getArea(u32 id) const
59 AreaMap::const_iterator it = areas_map.find(id);
60 if (it == areas_map.end())
66 Currently, serialisation is commented out. This is because of multiple reasons:
67 1. Why do we store the areastore into a file, why not into the database?
68 2. We don't use libspatial's serialisation, but we should, or perhaps not, because
69 it would remove the ability to switch. Perhaps write migration routines?
70 3. Various things need fixing, e.g. the size is serialized as
71 c++ implementation defined size_t
72 bool AreaStore::deserialize(std::istream &is)
77 u16 count_areas = readU16(is);
78 for (u16 i = 0; i < count_areas; i++) {
79 // deserialize an area
82 a.minedge = readV3S16(is);
83 a.maxedge = readV3S16(is);
84 a.datalen = readU16(is);
85 a.data = new char[a.datalen];
86 is.read((char *) a.data, a.datalen);
93 static bool serialize_area(void *ostr, Area *a)
95 std::ostream &os = *((std::ostream *) ostr);
97 writeV3S16(os, a->minedge);
98 writeV3S16(os, a->maxedge);
99 writeU16(os, a->datalen);
100 os.write(a->data, a->datalen);
106 void AreaStore::serialize(std::ostream &os) const
108 // write initial data
109 writeU8(os, 1); // serialisation version
110 writeU16(os, areas_map.size()); //DANGER: not platform independent
111 forEach(&serialize_area, &os);
116 void AreaStore::invalidateCache()
118 if (m_cache_enabled) {
119 m_res_cache.invalidate();
123 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
125 m_cache_enabled = enabled;
126 m_cacheblock_radius = MYMAX(block_radius, 16);
127 m_res_cache.setLimit(MYMAX(limit, 20));
131 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
133 AreaStore *as = (AreaStore *)data;
134 u8 r = as->m_cacheblock_radius;
136 // get the points at the edges of the mapblock
137 v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
143 as->getAreasInArea(dest, minedge, maxedge, true);
145 /* infostream << "Cache miss with " << dest->size() << " areas, between ("
146 << minedge.X << ", " << minedge.Y << ", " << minedge.Z
148 << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
149 << ")" << std::endl; // */
152 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
154 if (m_cache_enabled) {
155 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
156 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
158 size_t s_p_l = pre_list->size();
159 for (size_t i = 0; i < s_p_l; i++) {
160 Area *b = (*pre_list)[i];
161 if (AST_CONTAINS_PT(b, pos)) {
162 result->push_back(b);
166 return getAreasForPosImpl(result, pos);
176 bool VectorAreaStore::insertArea(Area *a)
179 std::pair<AreaMap::iterator, bool> res =
180 areas_map.insert(std::make_pair(a->id, *a));
184 m_areas.push_back(&res.first->second);
189 bool VectorAreaStore::removeArea(u32 id)
191 AreaMap::iterator it = areas_map.find(id);
192 if (it == areas_map.end())
194 Area *a = &it->second;
195 for (std::vector<Area *>::iterator v_it = m_areas.begin();
196 v_it != m_areas.end(); ++v_it) {
207 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
209 for (size_t i = 0; i < m_areas.size(); ++i) {
210 Area *b = m_areas[i];
211 if (AST_CONTAINS_PT(b, pos)) {
212 result->push_back(b);
217 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
218 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
220 for (size_t i = 0; i < m_areas.size(); ++i) {
221 Area *b = m_areas[i];
222 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
223 AST_CONTAINS_AREA(minedge, maxedge, b)) {
224 result->push_back(b);
230 bool SimpleAreaStore::forEach(ForEachCallback callback, void *arg) const
232 for (size_t i = 0; i < m_areas.size(); ++i) {
233 if (callback(m_areas[i], arg)) {
243 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
246 const double p_low[] = {(double)minedge.X,
247 (double)minedge.Y, (double)minedge.Z};
248 const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
250 return SpatialIndex::Region(p_low, p_high, 3);
253 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
255 const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
256 return SpatialIndex::Point(p, 3);
260 bool SpatialAreaStore::insertArea(Area *a)
263 if (!areas_map.insert(std::make_pair(a->id, *a)).second)
266 m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
271 bool SpatialAreaStore::removeArea(u32 id)
273 std::map<u32, Area>::iterator itr = areas_map.find(id);
274 if (itr != areas_map.end()) {
275 Area *a = &itr->second;
276 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
285 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
287 VectorResultVisitor visitor(result, this);
288 m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
291 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
292 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
294 VectorResultVisitor visitor(result, this);
295 if (accept_overlap) {
296 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
299 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
304 bool SpatialAreaStore::forEach(ForEachCallback callback, void *arg) const
306 // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation)
311 SpatialAreaStore::~SpatialAreaStore()
316 SpatialAreaStore::SpatialAreaStore()
319 SpatialIndex::StorageManager::createNewMemoryStorageManager();
320 SpatialIndex::id_type id;
321 m_tree = SpatialIndex::RTree::createNewRTree(
324 100, // Index capacity
325 100, // Leaf capacity
327 SpatialIndex::RTree::RV_RSTAR,