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 u32 AreaStore::getFreeId(v3s16 minedge, v3s16 maxedge)
57 // Handle overflows, we dont want to return 0
58 if (m_highest_id == AREA_ID_INVALID)
60 if (areas_map.find(m_highest_id) == areas_map.end())
64 return AREA_ID_INVALID;
67 const Area *AreaStore::getArea(u32 id) const
69 const Area *res = NULL;
70 std::map<u32, Area>::const_iterator itr = areas_map.find(id);
71 if (itr != areas_map.end()) {
78 Currently, serialisation is commented out. This is because of multiple reasons:
79 1. Why do we store the areastore into a file, why not into the database?
80 2. We don't use libspatial's serialisation, but we should, or perhaps not, because
81 it would remove the ability to switch. Perhaps write migration routines?
82 3. Various things need fixing, e.g. the size is serialized as
83 c++ implementation defined size_t
84 bool AreaStore::deserialize(std::istream &is)
89 u16 count_areas = readU16(is);
90 for (u16 i = 0; i < count_areas; i++) {
91 // deserialize an area
94 a.minedge = readV3S16(is);
95 a.maxedge = readV3S16(is);
96 a.datalen = readU16(is);
97 a.data = new char[a.datalen];
98 is.read((char *) a.data, a.datalen);
105 static bool serialize_area(void *ostr, Area *a)
107 std::ostream &os = *((std::ostream *) ostr);
109 writeV3S16(os, a->minedge);
110 writeV3S16(os, a->maxedge);
111 writeU16(os, a->datalen);
112 os.write(a->data, a->datalen);
118 void AreaStore::serialize(std::ostream &os) const
120 // write initial data
121 writeU8(os, 1); // serialisation version
122 writeU16(os, areas_map.size()); //DANGER: not platform independent
123 forEach(&serialize_area, &os);
128 void AreaStore::invalidateCache()
131 m_res_cache.invalidate();
135 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
137 cache_enabled = enabled;
138 m_cacheblock_radius = MYMAX(block_radius, 16);
139 m_res_cache.setLimit(MYMAX(limit, 20));
143 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
145 AreaStore *as = (AreaStore *)data;
146 u8 r = as->m_cacheblock_radius;
148 // get the points at the edges of the mapblock
149 v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
155 as->getAreasInArea(dest, minedge, maxedge, true);
157 /* infostream << "Cache miss with " << dest->size() << " areas, between ("
158 << minedge.X << ", " << minedge.Y << ", " << minedge.Z
160 << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
161 << ")" << std::endl; // */
164 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
167 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
168 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
170 size_t s_p_l = pre_list->size();
171 for (size_t i = 0; i < s_p_l; i++) {
172 Area *b = (*pre_list)[i];
173 if (AST_CONTAINS_PT(b, pos)) {
174 result->push_back(b);
178 return getAreasForPosImpl(result, pos);
188 void VectorAreaStore::insertArea(const Area &a)
191 m_areas.push_back(&(areas_map[a.id]));
195 void VectorAreaStore::reserve(size_t count)
197 m_areas.reserve(count);
200 bool VectorAreaStore::removeArea(u32 id)
202 std::map<u32, Area>::iterator itr = areas_map.find(id);
203 if (itr != areas_map.end()) {
204 size_t msiz = m_areas.size();
205 for (size_t i = 0; i < msiz; i++) {
206 Area * b = m_areas[i];
208 areas_map.erase(itr);
209 m_areas.erase(m_areas.begin() + i);
214 // we should never get here, it means we did find it in map,
215 // but not in the vector
220 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
222 size_t msiz = m_areas.size();
223 for (size_t i = 0; i < msiz; i++) {
224 Area *b = m_areas[i];
225 if (AST_CONTAINS_PT(b, pos)) {
226 result->push_back(b);
231 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
232 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
234 size_t msiz = m_areas.size();
235 for (size_t i = 0; i < msiz; i++) {
236 Area * b = m_areas[i];
237 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
238 AST_CONTAINS_AREA(minedge, maxedge, b)) {
239 result->push_back(b);
245 bool VectorAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
247 size_t msiz = m_areas.size();
248 for (size_t i = 0; i < msiz; i++) {
249 if (callback(args, m_areas[i])) {
259 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
262 const double p_low[] = {(double)minedge.X,
263 (double)minedge.Y, (double)minedge.Z};
264 const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
266 return SpatialIndex::Region(p_low, p_high, 3);
269 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
271 const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
272 return SpatialIndex::Point(p, 3);
276 void SpatialAreaStore::insertArea(const Area &a)
279 m_tree->insertData(0, NULL, get_spatial_region(a.minedge, a.maxedge), a.id);
283 bool SpatialAreaStore::removeArea(u32 id)
285 std::map<u32, Area>::iterator itr = areas_map.find(id);
286 if (itr != areas_map.end()) {
287 Area *a = &itr->second;
288 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
297 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
299 VectorResultVisitor visitor(result, this);
300 m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
303 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
304 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
306 VectorResultVisitor visitor(result, this);
307 if (accept_overlap) {
308 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
311 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
316 bool SpatialAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const
318 // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation)
323 SpatialAreaStore::~SpatialAreaStore()
328 SpatialAreaStore::SpatialAreaStore()
331 SpatialIndex::StorageManager::createNewMemoryStorageManager();
332 SpatialIndex::id_type id;
333 m_tree = SpatialIndex::RTree::createNewRTree(
336 100, // Index capacity
337 100, // Leaf capacity
339 SpatialIndex::RTree::RV_RSTAR,