From 0079887b645e0ee441bd2cfcd7874a1148fdd656 Mon Sep 17 00:00:00 2001 From: ShadowNinja Date: Thu, 29 Oct 2015 23:26:03 -0400 Subject: Move AreaStore to util --- src/CMakeLists.txt | 1 - src/areastore.cpp | 338 ------------------------------------- src/areastore.h | 177 ------------------- src/script/lua_api/l_areastore.cpp | 2 +- src/script/lua_api/l_areastore.h | 13 +- src/script/lua_api/l_util.cpp | 1 - src/unittest/test_areastore.cpp | 2 +- src/util/CMakeLists.txt | 1 + src/util/areastore.cpp | 338 +++++++++++++++++++++++++++++++++++++ src/util/areastore.h | 177 +++++++++++++++++++ 10 files changed, 524 insertions(+), 526 deletions(-) delete mode 100644 src/areastore.cpp delete mode 100644 src/areastore.h create mode 100644 src/util/areastore.cpp create mode 100644 src/util/areastore.h (limited to 'src') diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 0b84ff85a..feca199c1 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -348,7 +348,6 @@ add_subdirectory(unittest) add_subdirectory(util) set(common_SRCS - areastore.cpp ban.cpp cavegen.cpp chat.cpp diff --git a/src/areastore.cpp b/src/areastore.cpp deleted file mode 100644 index b1b5c0db4..000000000 --- a/src/areastore.cpp +++ /dev/null @@ -1,338 +0,0 @@ -/* -Minetest -Copyright (C) 2015 est31 - -This program is free software; you can redistribute it and/or modify -it under the terms of the GNU Lesser General Public License as published by -the Free Software Foundation; either version 2.1 of the License, or -(at your option) any later version. - -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU Lesser General Public License for more details. - -You should have received a copy of the GNU Lesser General Public License along -with this program; if not, write to the Free Software Foundation, Inc., -51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -*/ - -#include "areastore.h" -#include "util/serialize.h" -#include "util/container.h" - -#if USE_SPATIAL - #include - #include - #include -#endif - -#define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z)) - -#define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \ - (!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d))) - -#define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \ - AST_SMALLER_EQ_AS((p), (a)->maxedge)) - -#define AST_CONTAINS_AREA(amine, amaxe, b) \ - (AST_SMALLER_EQ_AS((amine), (b)->minedge) \ - && AST_SMALLER_EQ_AS((b)->maxedge, (amaxe))) - -#define AST_AREAS_OVERLAP(amine, amaxe, b) \ - (AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), X) && \ - AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Y) && \ - AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Z)) - -u16 AreaStore::size() const -{ - return areas_map.size(); -} - -const Area *AreaStore::getArea(u32 id) const -{ - const Area *res = NULL; - std::map::const_iterator itr = areas_map.find(id); - if (itr != areas_map.end()) { - res = &itr->second; - } - return res; -} - -#if 0 -Currently, serialisation is commented out. This is because of multiple reasons: -1. Why do we store the areastore into a file, why not into the database? -2. We don't use libspatial's serialisation, but we should, or perhaps not, because - it would remove the ability to switch. Perhaps write migration routines? -3. Various things need fixing, e.g. the size is serialized as - c++ implementation defined size_t -bool AreaStore::deserialize(std::istream &is) -{ - u8 ver = readU8(is); - if (ver != 1) - return false; - u16 count_areas = readU16(is); - for (u16 i = 0; i < count_areas; i++) { - // deserialize an area - Area a; - a.id = readU32(is); - a.minedge = readV3S16(is); - a.maxedge = readV3S16(is); - a.datalen = readU16(is); - a.data = new char[a.datalen]; - is.read((char *) a.data, a.datalen); - insertArea(a); - } - return true; -} - - -static bool serialize_area(void *ostr, Area *a) -{ - std::ostream &os = *((std::ostream *) ostr); - writeU32(os, a->id); - writeV3S16(os, a->minedge); - writeV3S16(os, a->maxedge); - writeU16(os, a->datalen); - os.write(a->data, a->datalen); - - return false; -} - - -void AreaStore::serialize(std::ostream &os) const -{ - // write initial data - writeU8(os, 1); // serialisation version - writeU16(os, areas_map.size()); //DANGER: not platform independent - forEach(&serialize_area, &os); -} - -#endif - -void AreaStore::invalidateCache() -{ - if (m_cache_enabled) { - m_res_cache.invalidate(); - } -} - -void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit) -{ - m_cache_enabled = enabled; - m_cacheblock_radius = MYMAX(block_radius, 16); - m_res_cache.setLimit(MYMAX(limit, 20)); - invalidateCache(); -} - -void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector *dest) -{ - AreaStore *as = (AreaStore *)data; - u8 r = as->m_cacheblock_radius; - - // get the points at the edges of the mapblock - v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r); - v3s16 maxedge( - minedge.X + r - 1, - minedge.Y + r - 1, - minedge.Z + r - 1); - - as->getAreasInArea(dest, minedge, maxedge, true); - - /* infostream << "Cache miss with " << dest->size() << " areas, between (" - << minedge.X << ", " << minedge.Y << ", " << minedge.Z - << ") and (" - << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z - << ")" << std::endl; // */ -} - -void AreaStore::getAreasForPos(std::vector *result, v3s16 pos) -{ - if (m_cache_enabled) { - v3s16 mblock = getContainerPos(pos, m_cacheblock_radius); - const std::vector *pre_list = m_res_cache.lookupCache(mblock); - - size_t s_p_l = pre_list->size(); - for (size_t i = 0; i < s_p_l; i++) { - Area *b = (*pre_list)[i]; - if (AST_CONTAINS_PT(b, pos)) { - result->push_back(b); - } - } - } else { - return getAreasForPosImpl(result, pos); - } -} - - -//// -// VectorAreaStore -//// - - -bool VectorAreaStore::insertArea(Area *a) -{ - a->id = getNextId(); - std::pair::iterator, bool> res = - areas_map.insert(std::make_pair(a->id, *a)); - if (!res.second) - // ID is not unique - return false; - m_areas.push_back(&res.first->second); - invalidateCache(); - return true; -} - -void VectorAreaStore::reserve(size_t count) -{ - m_areas.reserve(count); -} - -bool VectorAreaStore::removeArea(u32 id) -{ - std::map::iterator itr = areas_map.find(id); - if (itr != areas_map.end()) { - size_t msiz = m_areas.size(); - for (size_t i = 0; i < msiz; i++) { - Area * b = m_areas[i]; - if (b->id == id) { - areas_map.erase(itr); - m_areas.erase(m_areas.begin() + i); - invalidateCache(); - return true; - } - } - // we should never get here, it means we did find it in map, - // but not in the vector - } - return false; -} - -void VectorAreaStore::getAreasForPosImpl(std::vector *result, v3s16 pos) -{ - size_t msiz = m_areas.size(); - for (size_t i = 0; i < msiz; i++) { - Area *b = m_areas[i]; - if (AST_CONTAINS_PT(b, pos)) { - result->push_back(b); - } - } -} - -void VectorAreaStore::getAreasInArea(std::vector *result, - v3s16 minedge, v3s16 maxedge, bool accept_overlap) -{ - size_t msiz = m_areas.size(); - for (size_t i = 0; i < msiz; i++) { - Area * b = m_areas[i]; - if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) : - AST_CONTAINS_AREA(minedge, maxedge, b)) { - result->push_back(b); - } - } -} - -#if 0 -bool VectorAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const -{ - size_t msiz = m_areas.size(); - for (size_t i = 0; i < msiz; i++) { - if (callback(args, m_areas[i])) { - return true; - } - } - return false; -} -#endif - -#if USE_SPATIAL - -static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge, - const v3s16 maxedge) -{ - const double p_low[] = {(double)minedge.X, - (double)minedge.Y, (double)minedge.Z}; - const double p_high[] = {(double)maxedge.X, (double)maxedge.Y, - (double)maxedge.Z}; - return SpatialIndex::Region(p_low, p_high, 3); -} - -static inline SpatialIndex::Point get_spatial_point(const v3s16 pos) -{ - const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z}; - return SpatialIndex::Point(p, 3); -} - - -bool SpatialAreaStore::insertArea(Area *a) -{ - a->id = getNextId(); - if (!areas_map.insert(std::make_pair(a->id, *a)).second) - // ID is not unique - return false; - m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id); - invalidateCache(); - return true; -} - -bool SpatialAreaStore::removeArea(u32 id) -{ - std::map::iterator itr = areas_map.find(id); - if (itr != areas_map.end()) { - Area *a = &itr->second; - bool result = m_tree->deleteData(get_spatial_region(a->minedge, - a->maxedge), id); - invalidateCache(); - return result; - } else { - return false; - } -} - -void SpatialAreaStore::getAreasForPosImpl(std::vector *result, v3s16 pos) -{ - VectorResultVisitor visitor(result, this); - m_tree->pointLocationQuery(get_spatial_point(pos), visitor); -} - -void SpatialAreaStore::getAreasInArea(std::vector *result, - v3s16 minedge, v3s16 maxedge, bool accept_overlap) -{ - VectorResultVisitor visitor(result, this); - if (accept_overlap) { - m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge), - visitor); - } else { - m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor); - } -} - -#if 0 -bool SpatialAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const -{ - // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation) - return false; -} -#endif - -SpatialAreaStore::~SpatialAreaStore() -{ - delete m_tree; -} - -SpatialAreaStore::SpatialAreaStore() -{ - m_storagemanager = - SpatialIndex::StorageManager::createNewMemoryStorageManager(); - SpatialIndex::id_type id; - m_tree = SpatialIndex::RTree::createNewRTree( - *m_storagemanager, - .7, // Fill factor - 100, // Index capacity - 100, // Leaf capacity - 3, // dimension :) - SpatialIndex::RTree::RV_RSTAR, - id); -} - -#endif diff --git a/src/areastore.h b/src/areastore.h deleted file mode 100644 index 493b4fc25..000000000 --- a/src/areastore.h +++ /dev/null @@ -1,177 +0,0 @@ -/* -Minetest -Copyright (C) 2015 est31 - -This program is free software; you can redistribute it and/or modify -it under the terms of the GNU Lesser General Public License as published by -the Free Software Foundation; either version 2.1 of the License, or -(at your option) any later version. - -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU Lesser General Public License for more details. - -You should have received a copy of the GNU Lesser General Public License along -with this program; if not, write to the Free Software Foundation, Inc., -51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -*/ - -#ifndef AREASTORE_H_ -#define AREASTORE_H_ - -#include "irr_v3d.h" -#include "noise.h" // for PcgRandom -#include -#include -#include -#include -#include "util/container.h" -#include "util/numeric.h" -#ifndef ANDROID - #include "cmake_config.h" -#endif -#if USE_SPATIAL - #include - #include "util/serialize.h" -#endif - - -struct Area { - Area() {} - Area(const v3s16 &mine, const v3s16 &maxe) - { - minedge = mine; - maxedge = maxe; - sortBoxVerticies(minedge, maxedge); - } - - u32 id; - v3s16 minedge; - v3s16 maxedge; - std::string data; -}; - -std::vector get_areastore_typenames(); - -class AreaStore { -protected: - void invalidateCache(); - virtual void getAreasForPosImpl(std::vector *result, v3s16 pos) = 0; - u32 getNextId() { return m_next_id++; } - - // TODO change to unordered_map when we can - std::map areas_map; -public: - // Updates the area's ID - virtual bool insertArea(Area *a) = 0; - virtual void reserve(size_t count) {}; - virtual bool removeArea(u32 id) = 0; - void getAreasForPos(std::vector *result, v3s16 pos); - virtual void getAreasInArea(std::vector *result, - v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0; - -#if 0 - // calls a passed function for every stored area, until the - // callback returns true. If that happens, it returns true, - // if the search is exhausted, it returns false - virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const = 0; -#endif - - virtual ~AreaStore() - {} - - AreaStore() : - m_cacheblock_radius(64), - m_res_cache(1000, &cacheMiss, this), - m_next_id(0), - m_cache_enabled(true) - { - } - - void setCacheParams(bool enabled, u8 block_radius, size_t limit); - - const Area *getArea(u32 id) const; - u16 size() const; -#if 0 - bool deserialize(std::istream &is); - void serialize(std::ostream &is) const; -#endif -private: - static void cacheMiss(void *data, const v3s16 &mpos, std::vector *dest); - u8 m_cacheblock_radius; // if you modify this, call invalidateCache() - LRUCache > m_res_cache; - u32 m_next_id; - bool m_cache_enabled; -}; - - -class VectorAreaStore : public AreaStore { -protected: - virtual void getAreasForPosImpl(std::vector *result, v3s16 pos); -public: - virtual bool insertArea(Area *a); - virtual void reserve(size_t count); - virtual bool removeArea(u32 id); - virtual void getAreasInArea(std::vector *result, - v3s16 minedge, v3s16 maxedge, bool accept_overlap); - // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const; -private: - std::vector m_areas; -}; - -#if USE_SPATIAL - -class SpatialAreaStore : public AreaStore { -protected: - virtual void getAreasForPosImpl(std::vector *result, v3s16 pos); -public: - SpatialAreaStore(); - virtual bool insertArea(Area *a); - virtual bool removeArea(u32 id); - virtual void getAreasInArea(std::vector *result, - v3s16 minedge, v3s16 maxedge, bool accept_overlap); - // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const; - - virtual ~SpatialAreaStore(); -private: - SpatialIndex::ISpatialIndex *m_tree; - SpatialIndex::IStorageManager *m_storagemanager; - - class VectorResultVisitor : public SpatialIndex::IVisitor { - private: - SpatialAreaStore *m_store; - std::vector *m_result; - public: - VectorResultVisitor(std::vector *result, SpatialAreaStore *store) - { - m_store = store; - m_result = result; - } - - virtual void visitNode(const SpatialIndex::INode &in) - { - } - - virtual void visitData(const SpatialIndex::IData &in) - { - u32 id = in.getIdentifier(); - - std::map::iterator itr = m_store->areas_map.find(id); - assert(itr != m_store->areas_map.end()); - m_result->push_back(&itr->second); - } - - virtual void visitData(std::vector &v) - { - for (size_t i = 0; i < v.size(); i++) - visitData(*(v[i])); - } - - ~VectorResultVisitor() {} - }; -}; - -#endif - -#endif /* AREASTORE_H_ */ diff --git a/src/script/lua_api/l_areastore.cpp b/src/script/lua_api/l_areastore.cpp index ff6abbd9f..8b8b157d7 100644 --- a/src/script/lua_api/l_areastore.cpp +++ b/src/script/lua_api/l_areastore.cpp @@ -23,7 +23,7 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "common/c_converter.h" #include "cpp_api/s_security.h" #include "irr_v3d.h" -#include "areastore.h" +#include "util/areastore.h" #include "filesys.h" #ifndef ANDROID #include "cmake_config.h" diff --git a/src/script/lua_api/l_areastore.h b/src/script/lua_api/l_areastore.h index 543a2aa32..6321de6d1 100644 --- a/src/script/lua_api/l_areastore.h +++ b/src/script/lua_api/l_areastore.h @@ -17,15 +17,14 @@ with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ -#ifndef L_AREASTORE_H_ -#define L_AREASTORE_H_ +#ifndef L_AREA_STORE_H_ +#define L_AREA_STORE_H_ #include "lua_api/l_base.h" -#include "areastore.h" -/* - AreaStore - */ + +class AreaStore; + class LuaAreaStore : public ModApiBase { private: @@ -66,4 +65,4 @@ public: static void Register(lua_State *L); }; -#endif /* L_AREASTORE_H_ */ +#endif // L_AREA_STORE_H_ diff --git a/src/script/lua_api/l_util.cpp b/src/script/lua_api/l_util.cpp index 98f70d917..f990dacf9 100644 --- a/src/script/lua_api/l_util.cpp +++ b/src/script/lua_api/l_util.cpp @@ -25,7 +25,6 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "serialization.h" #include "json/json.h" #include "cpp_api/s_security.h" -#include "areastore.h" #include "porting.h" #include "debug.h" #include "log.h" diff --git a/src/unittest/test_areastore.cpp b/src/unittest/test_areastore.cpp index 9d70d0b70..cac9e0b58 100644 --- a/src/unittest/test_areastore.cpp +++ b/src/unittest/test_areastore.cpp @@ -19,7 +19,7 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "test.h" -#include "areastore.h" +#include "util/areastore.h" class TestAreaStore : public TestBase { public: diff --git a/src/util/CMakeLists.txt b/src/util/CMakeLists.txt index 33900a43a..0e7cbad07 100644 --- a/src/util/CMakeLists.txt +++ b/src/util/CMakeLists.txt @@ -1,4 +1,5 @@ set(UTIL_SRCS + ${CMAKE_CURRENT_SOURCE_DIR}/areastore.cpp ${CMAKE_CURRENT_SOURCE_DIR}/auth.cpp ${CMAKE_CURRENT_SOURCE_DIR}/base64.cpp ${CMAKE_CURRENT_SOURCE_DIR}/directiontables.cpp diff --git a/src/util/areastore.cpp b/src/util/areastore.cpp new file mode 100644 index 000000000..b0076faa3 --- /dev/null +++ b/src/util/areastore.cpp @@ -0,0 +1,338 @@ +/* +Minetest +Copyright (C) 2015 est31 + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public License along +with this program; if not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ + +#include "util/areastore.h" +#include "util/serialize.h" +#include "util/container.h" + +#if USE_SPATIAL + #include + #include + #include +#endif + +#define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z)) + +#define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \ + (!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d))) + +#define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \ + AST_SMALLER_EQ_AS((p), (a)->maxedge)) + +#define AST_CONTAINS_AREA(amine, amaxe, b) \ + (AST_SMALLER_EQ_AS((amine), (b)->minedge) \ + && AST_SMALLER_EQ_AS((b)->maxedge, (amaxe))) + +#define AST_AREAS_OVERLAP(amine, amaxe, b) \ + (AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), X) && \ + AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Y) && \ + AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Z)) + +u16 AreaStore::size() const +{ + return areas_map.size(); +} + +const Area *AreaStore::getArea(u32 id) const +{ + const Area *res = NULL; + std::map::const_iterator itr = areas_map.find(id); + if (itr != areas_map.end()) { + res = &itr->second; + } + return res; +} + +#if 0 +Currently, serialisation is commented out. This is because of multiple reasons: +1. Why do we store the areastore into a file, why not into the database? +2. We don't use libspatial's serialisation, but we should, or perhaps not, because + it would remove the ability to switch. Perhaps write migration routines? +3. Various things need fixing, e.g. the size is serialized as + c++ implementation defined size_t +bool AreaStore::deserialize(std::istream &is) +{ + u8 ver = readU8(is); + if (ver != 1) + return false; + u16 count_areas = readU16(is); + for (u16 i = 0; i < count_areas; i++) { + // deserialize an area + Area a; + a.id = readU32(is); + a.minedge = readV3S16(is); + a.maxedge = readV3S16(is); + a.datalen = readU16(is); + a.data = new char[a.datalen]; + is.read((char *) a.data, a.datalen); + insertArea(a); + } + return true; +} + + +static bool serialize_area(void *ostr, Area *a) +{ + std::ostream &os = *((std::ostream *) ostr); + writeU32(os, a->id); + writeV3S16(os, a->minedge); + writeV3S16(os, a->maxedge); + writeU16(os, a->datalen); + os.write(a->data, a->datalen); + + return false; +} + + +void AreaStore::serialize(std::ostream &os) const +{ + // write initial data + writeU8(os, 1); // serialisation version + writeU16(os, areas_map.size()); //DANGER: not platform independent + forEach(&serialize_area, &os); +} + +#endif + +void AreaStore::invalidateCache() +{ + if (m_cache_enabled) { + m_res_cache.invalidate(); + } +} + +void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit) +{ + m_cache_enabled = enabled; + m_cacheblock_radius = MYMAX(block_radius, 16); + m_res_cache.setLimit(MYMAX(limit, 20)); + invalidateCache(); +} + +void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector *dest) +{ + AreaStore *as = (AreaStore *)data; + u8 r = as->m_cacheblock_radius; + + // get the points at the edges of the mapblock + v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r); + v3s16 maxedge( + minedge.X + r - 1, + minedge.Y + r - 1, + minedge.Z + r - 1); + + as->getAreasInArea(dest, minedge, maxedge, true); + + /* infostream << "Cache miss with " << dest->size() << " areas, between (" + << minedge.X << ", " << minedge.Y << ", " << minedge.Z + << ") and (" + << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z + << ")" << std::endl; // */ +} + +void AreaStore::getAreasForPos(std::vector *result, v3s16 pos) +{ + if (m_cache_enabled) { + v3s16 mblock = getContainerPos(pos, m_cacheblock_radius); + const std::vector *pre_list = m_res_cache.lookupCache(mblock); + + size_t s_p_l = pre_list->size(); + for (size_t i = 0; i < s_p_l; i++) { + Area *b = (*pre_list)[i]; + if (AST_CONTAINS_PT(b, pos)) { + result->push_back(b); + } + } + } else { + return getAreasForPosImpl(result, pos); + } +} + + +//// +// VectorAreaStore +//// + + +bool VectorAreaStore::insertArea(Area *a) +{ + a->id = getNextId(); + std::pair::iterator, bool> res = + areas_map.insert(std::make_pair(a->id, *a)); + if (!res.second) + // ID is not unique + return false; + m_areas.push_back(&res.first->second); + invalidateCache(); + return true; +} + +void VectorAreaStore::reserve(size_t count) +{ + m_areas.reserve(count); +} + +bool VectorAreaStore::removeArea(u32 id) +{ + std::map::iterator itr = areas_map.find(id); + if (itr != areas_map.end()) { + size_t msiz = m_areas.size(); + for (size_t i = 0; i < msiz; i++) { + Area * b = m_areas[i]; + if (b->id == id) { + areas_map.erase(itr); + m_areas.erase(m_areas.begin() + i); + invalidateCache(); + return true; + } + } + // we should never get here, it means we did find it in map, + // but not in the vector + } + return false; +} + +void VectorAreaStore::getAreasForPosImpl(std::vector *result, v3s16 pos) +{ + size_t msiz = m_areas.size(); + for (size_t i = 0; i < msiz; i++) { + Area *b = m_areas[i]; + if (AST_CONTAINS_PT(b, pos)) { + result->push_back(b); + } + } +} + +void VectorAreaStore::getAreasInArea(std::vector *result, + v3s16 minedge, v3s16 maxedge, bool accept_overlap) +{ + size_t msiz = m_areas.size(); + for (size_t i = 0; i < msiz; i++) { + Area * b = m_areas[i]; + if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) : + AST_CONTAINS_AREA(minedge, maxedge, b)) { + result->push_back(b); + } + } +} + +#if 0 +bool VectorAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const +{ + size_t msiz = m_areas.size(); + for (size_t i = 0; i < msiz; i++) { + if (callback(args, m_areas[i])) { + return true; + } + } + return false; +} +#endif + +#if USE_SPATIAL + +static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge, + const v3s16 maxedge) +{ + const double p_low[] = {(double)minedge.X, + (double)minedge.Y, (double)minedge.Z}; + const double p_high[] = {(double)maxedge.X, (double)maxedge.Y, + (double)maxedge.Z}; + return SpatialIndex::Region(p_low, p_high, 3); +} + +static inline SpatialIndex::Point get_spatial_point(const v3s16 pos) +{ + const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z}; + return SpatialIndex::Point(p, 3); +} + + +bool SpatialAreaStore::insertArea(Area *a) +{ + a->id = getNextId(); + if (!areas_map.insert(std::make_pair(a->id, *a)).second) + // ID is not unique + return false; + m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id); + invalidateCache(); + return true; +} + +bool SpatialAreaStore::removeArea(u32 id) +{ + std::map::iterator itr = areas_map.find(id); + if (itr != areas_map.end()) { + Area *a = &itr->second; + bool result = m_tree->deleteData(get_spatial_region(a->minedge, + a->maxedge), id); + invalidateCache(); + return result; + } else { + return false; + } +} + +void SpatialAreaStore::getAreasForPosImpl(std::vector *result, v3s16 pos) +{ + VectorResultVisitor visitor(result, this); + m_tree->pointLocationQuery(get_spatial_point(pos), visitor); +} + +void SpatialAreaStore::getAreasInArea(std::vector *result, + v3s16 minedge, v3s16 maxedge, bool accept_overlap) +{ + VectorResultVisitor visitor(result, this); + if (accept_overlap) { + m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge), + visitor); + } else { + m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor); + } +} + +#if 0 +bool SpatialAreaStore::forEach(bool (*callback)(void *args, Area *a), void *args) const +{ + // TODO ?? (this is only needed for serialisation, but libspatial has its own serialisation) + return false; +} +#endif + +SpatialAreaStore::~SpatialAreaStore() +{ + delete m_tree; +} + +SpatialAreaStore::SpatialAreaStore() +{ + m_storagemanager = + SpatialIndex::StorageManager::createNewMemoryStorageManager(); + SpatialIndex::id_type id; + m_tree = SpatialIndex::RTree::createNewRTree( + *m_storagemanager, + .7, // Fill factor + 100, // Index capacity + 100, // Leaf capacity + 3, // dimension :) + SpatialIndex::RTree::RV_RSTAR, + id); +} + +#endif diff --git a/src/util/areastore.h b/src/util/areastore.h new file mode 100644 index 000000000..c36cbc389 --- /dev/null +++ b/src/util/areastore.h @@ -0,0 +1,177 @@ +/* +Minetest +Copyright (C) 2015 est31 + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public License along +with this program; if not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ + +#ifndef AREA_STORE_H_ +#define AREA_STORE_H_ + +#include "irr_v3d.h" +#include "noise.h" // for PcgRandom +#include +#include +#include +#include +#include "util/container.h" +#include "util/numeric.h" +#ifndef ANDROID + #include "cmake_config.h" +#endif +#if USE_SPATIAL + #include + #include "util/serialize.h" +#endif + + +struct Area { + Area() {} + Area(const v3s16 &mine, const v3s16 &maxe) + { + minedge = mine; + maxedge = maxe; + sortBoxVerticies(minedge, maxedge); + } + + u32 id; + v3s16 minedge; + v3s16 maxedge; + std::string data; +}; + +std::vector get_areastore_typenames(); + +class AreaStore { +protected: + void invalidateCache(); + virtual void getAreasForPosImpl(std::vector *result, v3s16 pos) = 0; + u32 getNextId() { return m_next_id++; } + + // TODO change to unordered_map when we can + std::map areas_map; +public: + // Updates the area's ID + virtual bool insertArea(Area *a) = 0; + virtual void reserve(size_t count) {}; + virtual bool removeArea(u32 id) = 0; + void getAreasForPos(std::vector *result, v3s16 pos); + virtual void getAreasInArea(std::vector *result, + v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0; + +#if 0 + // calls a passed function for every stored area, until the + // callback returns true. If that happens, it returns true, + // if the search is exhausted, it returns false + virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const = 0; +#endif + + virtual ~AreaStore() + {} + + AreaStore() : + m_cacheblock_radius(64), + m_res_cache(1000, &cacheMiss, this), + m_next_id(0), + m_cache_enabled(true) + { + } + + void setCacheParams(bool enabled, u8 block_radius, size_t limit); + + const Area *getArea(u32 id) const; + u16 size() const; +#if 0 + bool deserialize(std::istream &is); + void serialize(std::ostream &is) const; +#endif +private: + static void cacheMiss(void *data, const v3s16 &mpos, std::vector *dest); + u8 m_cacheblock_radius; // if you modify this, call invalidateCache() + LRUCache > m_res_cache; + u32 m_next_id; + bool m_cache_enabled; +}; + + +class VectorAreaStore : public AreaStore { +protected: + virtual void getAreasForPosImpl(std::vector *result, v3s16 pos); +public: + virtual bool insertArea(Area *a); + virtual void reserve(size_t count); + virtual bool removeArea(u32 id); + virtual void getAreasInArea(std::vector *result, + v3s16 minedge, v3s16 maxedge, bool accept_overlap); + // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const; +private: + std::vector m_areas; +}; + +#if USE_SPATIAL + +class SpatialAreaStore : public AreaStore { +protected: + virtual void getAreasForPosImpl(std::vector *result, v3s16 pos); +public: + SpatialAreaStore(); + virtual bool insertArea(Area *a); + virtual bool removeArea(u32 id); + virtual void getAreasInArea(std::vector *result, + v3s16 minedge, v3s16 maxedge, bool accept_overlap); + // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const; + + virtual ~SpatialAreaStore(); +private: + SpatialIndex::ISpatialIndex *m_tree; + SpatialIndex::IStorageManager *m_storagemanager; + + class VectorResultVisitor : public SpatialIndex::IVisitor { + private: + SpatialAreaStore *m_store; + std::vector *m_result; + public: + VectorResultVisitor(std::vector *result, SpatialAreaStore *store) + { + m_store = store; + m_result = result; + } + + virtual void visitNode(const SpatialIndex::INode &in) + { + } + + virtual void visitData(const SpatialIndex::IData &in) + { + u32 id = in.getIdentifier(); + + std::map::iterator itr = m_store->areas_map.find(id); + assert(itr != m_store->areas_map.end()); + m_result->push_back(&itr->second); + } + + virtual void visitData(std::vector &v) + { + for (size_t i = 0; i < v.size(); i++) + visitData(*(v[i])); + } + + ~VectorResultVisitor() {} + }; +}; + +#endif + +#endif // AREA_STORE_H_ -- cgit v1.2.3