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 "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))
47 u16 AreaStore::size() const
49 return areas_map.size();
52 const Area *AreaStore::getArea(u32 id) const
54 const Area *res = NULL;
55 std::map<u32, Area>::const_iterator itr = areas_map.find(id);
56 if (itr != areas_map.end()) {
63 Currently, serialisation is commented out. This is because of multiple reasons:
64 1. Why do we store the areastore into a file, why not into the database?
65 2. We don't use libspatial's serialisation, but we should, or perhaps not, because
66 it would remove the ability to switch. Perhaps write migration routines?
67 3. Various things need fixing, e.g. the size is serialized as
68 c++ implementation defined size_t
69 bool AreaStore::deserialize(std::istream &is)
74 u16 count_areas = readU16(is);
75 for (u16 i = 0; i < count_areas; i++) {
76 // deserialize an area
79 a.minedge = readV3S16(is);
80 a.maxedge = readV3S16(is);
81 a.datalen = readU16(is);
82 a.data = new char[a.datalen];
83 is.read((char *) a.data, a.datalen);
90 static bool serialize_area(void *ostr, Area *a)
92 std::ostream &os = *((std::ostream *) ostr);
94 writeV3S16(os, a->minedge);
95 writeV3S16(os, a->maxedge);
96 writeU16(os, a->datalen);
97 os.write(a->data, a->datalen);
103 void AreaStore::serialize(std::ostream &os) const
105 // write initial data
106 writeU8(os, 1); // serialisation version
107 writeU16(os, areas_map.size()); //DANGER: not platform independent
108 forEach(&serialize_area, &os);
113 void AreaStore::invalidateCache()
116 m_res_cache.invalidate();
120 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
122 cache_enabled = enabled;
123 m_cacheblock_radius = MYMAX(block_radius, 16);
124 m_res_cache.setLimit(MYMAX(limit, 20));
128 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
130 AreaStore *as = (AreaStore *)data;
131 u8 r = as->m_cacheblock_radius;
133 // get the points at the edges of the mapblock
134 v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
140 as->getAreasInArea(dest, minedge, maxedge, true);
142 /* infostream << "Cache miss with " << dest->size() << " areas, between ("
143 << minedge.X << ", " << minedge.Y << ", " << minedge.Z
145 << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
146 << ")" << std::endl; // */
149 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
152 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
153 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
155 size_t s_p_l = pre_list->size();
156 for (size_t i = 0; i < s_p_l; i++) {
157 Area *b = (*pre_list)[i];
158 if (AST_CONTAINS_PT(b, pos)) {
159 result->push_back(b);
163 return getAreasForPosImpl(result, pos);
173 bool VectorAreaStore::insertArea(Area *a)
176 std::pair<std::map<u32, Area>::iterator, bool> res =
177 areas_map.insert(std::make_pair(a->id, *a));
181 m_areas.push_back(&res.first->second);
186 void VectorAreaStore::reserve(size_t count)
188 m_areas.reserve(count);
191 bool VectorAreaStore::removeArea(u32 id)
193 std::map<u32, Area>::iterator itr = areas_map.find(id);
194 if (itr != areas_map.end()) {
195 size_t msiz = m_areas.size();
196 for (size_t i = 0; i < msiz; i++) {
197 Area * b = m_areas[i];
199 areas_map.erase(itr);
200 m_areas.erase(m_areas.begin() + i);
205 // we should never get here, it means we did find it in map,
206 // but not in the vector
211 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
213 size_t msiz = m_areas.size();
214 for (size_t i = 0; i < msiz; i++) {
215 Area *b = m_areas[i];
216 if (AST_CONTAINS_PT(b, pos)) {
217 result->push_back(b);
222 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
223 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
225 size_t msiz = m_areas.size();
226 for (size_t i = 0; i < msiz; i++) {
227 Area * b = m_areas[i];
228 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
229 AST_CONTAINS_AREA(minedge, maxedge, b)) {
230 result->push_back(b);
236 bool VectorAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
238 size_t msiz = m_areas.size();
239 for (size_t i = 0; i < msiz; i++) {
240 if (callback(args, m_areas[i])) {
250 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
253 const double p_low[] = {(double)minedge.X,
254 (double)minedge.Y, (double)minedge.Z};
255 const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
257 return SpatialIndex::Region(p_low, p_high, 3);
260 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
262 const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
263 return SpatialIndex::Point(p, 3);
267 bool SpatialAreaStore::insertArea(Area *a)
270 if (!areas_map.insert(std::make_pair(a->id, *a)).second)
273 m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
278 bool SpatialAreaStore::removeArea(u32 id)
280 std::map<u32, Area>::iterator itr = areas_map.find(id);
281 if (itr != areas_map.end()) {
282 Area *a = &itr->second;
283 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
292 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
294 VectorResultVisitor visitor(result, this);
295 m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
298 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
299 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
301 VectorResultVisitor visitor(result, this);
302 if (accept_overlap) {
303 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
306 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
311 bool SpatialAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
313 // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation)
318 SpatialAreaStore::~SpatialAreaStore()
323 SpatialAreaStore::SpatialAreaStore()
326 SpatialIndex::StorageManager::createNewMemoryStorageManager();
327 SpatialIndex::id_type id;
328 m_tree = SpatialIndex::RTree::createNewRTree(
331 100, // Index capacity
332 100, // Leaf capacity
334 SpatialIndex::RTree::RV_RSTAR,