diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/CMakeLists.txt | 22 | ||||
| -rw-r--r-- | src/areastore.cpp | 343 | ||||
| -rw-r--r-- | src/areastore.h | 196 | ||||
| -rw-r--r-- | src/cmake_config.h.in | 1 | ||||
| -rw-r--r-- | src/script/lua_api/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/script/lua_api/l_areastore.cpp | 401 | ||||
| -rw-r--r-- | src/script/lua_api/l_areastore.h | 70 | ||||
| -rw-r--r-- | src/script/lua_api/l_util.cpp | 1 | ||||
| -rw-r--r-- | src/script/scripting_game.cpp | 2 | ||||
| -rw-r--r-- | src/unittest/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/unittest/test_areastore.cpp | 129 | ||||
| -rw-r--r-- | src/util/container.h | 69 |
12 files changed, 1236 insertions, 0 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 0ed0b8015..614e81908 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -180,6 +180,21 @@ endif(ENABLE_REDIS) find_package(SQLite3 REQUIRED) find_package(Json REQUIRED) +OPTION(ENABLE_SPATIAL "Enable SpatialIndex AreaStore backend" TRUE) +set(USE_SPATIAL FALSE) + +if(ENABLE_SPATIAL) + find_library(SPATIAL_LIBRARY spatialindex) + find_path(SPATIAL_INCLUDE_DIR spatialindex/SpatialIndex.h) + if(SPATIAL_LIBRARY AND SPATIAL_INCLUDE_DIR) + set(USE_SPATIAL TRUE) + message(STATUS "SpatialIndex AreaStore backend enabled.") + include_directories(${SPATIAL_INCLUDE_DIR}) + else(SPATIAL_LIBRARY AND SPATIAL_INCLUDE_DIR) + message(STATUS "SpatialIndex not found!") + endif(SPATIAL_LIBRARY AND SPATIAL_INCLUDE_DIR) +endif(ENABLE_SPATIAL) + if(NOT MSVC) set(USE_GPROF FALSE CACHE BOOL "Use -pg flag for g++") @@ -289,6 +304,7 @@ add_subdirectory(unittest) add_subdirectory(util) set(common_SRCS + areastore.cpp ban.cpp cavegen.cpp clientiface.cpp @@ -532,6 +548,9 @@ if(BUILD_CLIENT) if (USE_REDIS) target_link_libraries(${PROJECT_NAME} ${REDIS_LIBRARY}) endif() + if (USE_SPATIAL) + target_link_libraries(${PROJECT_NAME} ${SPATIAL_LIBRARY}) + endif() endif(BUILD_CLIENT) @@ -556,6 +575,9 @@ if(BUILD_SERVER) if (USE_REDIS) target_link_libraries(${PROJECT_NAME}server ${REDIS_LIBRARY}) endif() + if (USE_SPATIAL) + target_link_libraries(${PROJECT_NAME}server ${SPATIAL_LIBRARY}) + endif() if(USE_CURL) target_link_libraries( ${PROJECT_NAME}server diff --git a/src/areastore.cpp b/src/areastore.cpp new file mode 100644 index 000000000..f9362c4a6 --- /dev/null +++ b/src/areastore.cpp @@ -0,0 +1,343 @@ +/* +Minetest +Copyright (C) 2015 est31 <mtest31@outlook.com> + +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 <spatialindex/SpatialIndex.h> + #include <spatialindex/RTree.h> + #include <spatialindex/Point.h> +#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(); +} + +u32 AreaStore::getFreeId(v3s16 minedge, v3s16 maxedge) +{ + int keep_on = 100; + while (keep_on--) { + m_highest_id++; + // Handle overflows, we dont want to return 0 + if (m_highest_id == AREA_ID_INVALID) + m_highest_id++; + if (areas_map.find(m_highest_id) == areas_map.end()) + return m_highest_id; + } + // search failed + return AREA_ID_INVALID; +} + +const Area *AreaStore::getArea(u32 id) const +{ + const Area *res = NULL; + std::map<u32, Area>::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 (cache_enabled) { + m_res_cache.invalidate(); + } +} + +void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit) +{ + 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<Area *> *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<Area *> *result, v3s16 pos) +{ + if (cache_enabled) { + v3s16 mblock = getContainerPos(pos, m_cacheblock_radius); + const std::vector<Area *> *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 +//// + + +void VectorAreaStore::insertArea(const Area &a) +{ + areas_map[a.id] = a; + m_areas.push_back(&(areas_map[a.id])); + invalidateCache(); +} + +void VectorAreaStore::reserve(size_t count) +{ + m_areas.reserve(count); +} + +bool VectorAreaStore::removeArea(u32 id) +{ + std::map<u32, Area>::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<Area *> *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<Area *> *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); +} + + +void SpatialAreaStore::insertArea(const Area &a) +{ + areas_map[a.id] = a; + m_tree->insertData(0, NULL, get_spatial_region(a.minedge, a.maxedge), a.id); + invalidateCache(); +} + +bool SpatialAreaStore::removeArea(u32 id) +{ + std::map<u32, Area>::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<Area *> *result, v3s16 pos) +{ + VectorResultVisitor visitor(result, this); + m_tree->pointLocationQuery(get_spatial_point(pos), visitor); +} + +void SpatialAreaStore::getAreasInArea(std::vector<Area *> *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 new file mode 100644 index 000000000..57d96450b --- /dev/null +++ b/src/areastore.h @@ -0,0 +1,196 @@ +/* +Minetest +Copyright (C) 2015 est31 <mtest31@outlook.com> + +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 <map> +#include <list> +#include <vector> +#include <istream> +#include "util/container.h" +#include "util/numeric.h" +#ifndef ANDROID + #include "cmake_config.h" +#endif +#if USE_SPATIAL + #include <spatialindex/SpatialIndex.h> + #include "util/serialize.h" +#endif + +#define AST_EXTREMIFY(min, max, pa, pb) \ + (min).X = MYMIN((pa).X, (pb).X); \ + (min).Y = MYMIN((pa).Y, (pb).Y); \ + (min).Z = MYMIN((pa).Z, (pb).Z); \ + (max).X = MYMAX((pa).X, (pb).X); \ + (max).Y = MYMAX((pa).Y, (pb).Y); \ + (max).Z = MYMAX((pa).Z, (pb).Z); + +#define AREA_ID_INVALID 0 + +struct Area { + Area(const v3s16 &minedge, const v3s16 &maxedge) + { + this->minedge = minedge; + this->maxedge = maxedge; + } + + Area() {} + + void extremifyEdges() + { + v3s16 nminedge; + v3s16 nmaxedge; + + AST_EXTREMIFY(nminedge, nmaxedge, minedge, maxedge) + + maxedge = nmaxedge; + minedge = nminedge; + } + + u32 id; + v3s16 minedge; + v3s16 maxedge; + std::string data; +}; + +std::vector<std::string> get_areastore_typenames(); + +class AreaStore { +protected: + // TODO change to unordered_map when we can + std::map<u32, Area> areas_map; + void invalidateCache(); + virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos) = 0; + bool cache_enabled; // don't write to this from subclasses, only read. +public: + virtual void insertArea(const Area &a) = 0; + virtual void reserve(size_t count) {}; + virtual bool removeArea(u32 id) = 0; + void getAreasForPos(std::vector<Area *> *result, v3s16 pos); + virtual void getAreasInArea(std::vector<Area *> *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() : + cache_enabled(true), + m_cacheblock_radius(64), + m_res_cache(1000, &cacheMiss, this), + m_highest_id(0) + { + } + + void setCacheParams(bool enabled, u8 block_radius, size_t limit); + + u32 getFreeId(v3s16 minedge, v3s16 maxedge); + 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<Area *> *dest); + u8 m_cacheblock_radius; // if you modify this, call invalidateCache() + LRUCache<v3s16, std::vector<Area *> > m_res_cache; + u32 m_highest_id; + +}; + + +class VectorAreaStore : public AreaStore { +protected: + virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos); +public: + virtual void insertArea(const Area &a); + virtual void reserve(size_t count); + virtual bool removeArea(u32 id); + virtual void getAreasInArea(std::vector<Area *> *result, + v3s16 minedge, v3s16 maxedge, bool accept_overlap); + // virtual bool forEach(bool (*callback)(void *args, Area *a), void *args) const; +private: + std::vector<Area *> m_areas; +}; + +#if USE_SPATIAL + +class SpatialAreaStore : public AreaStore { +protected: + virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos); +public: + SpatialAreaStore(); + virtual void insertArea(const Area &a); + virtual bool removeArea(u32 id); + virtual void getAreasInArea(std::vector<Area *> *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<Area *> *m_result; + public: + VectorResultVisitor(std::vector<Area *> *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<u32, Area>::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<const SpatialIndex::IData *> &v) + { + for (size_t i = 0; i < v.size(); i++) + visitData(*(v[i])); + } + + ~VectorResultVisitor() {} + }; +}; + +#endif + +#endif /* AREASTORE_H_ */ diff --git a/src/cmake_config.h.in b/src/cmake_config.h.in index c3ca1e864..04f368594 100644 --- a/src/cmake_config.h.in +++ b/src/cmake_config.h.in @@ -20,6 +20,7 @@ #cmakedefine01 USE_FREETYPE #cmakedefine01 USE_LEVELDB #cmakedefine01 USE_LUAJIT +#cmakedefine01 USE_SPATIAL #cmakedefine01 USE_SYSTEM_GMP #cmakedefine01 USE_REDIS #cmakedefine01 HAVE_ENDIAN_H diff --git a/src/script/lua_api/CMakeLists.txt b/src/script/lua_api/CMakeLists.txt index aaabc213e..2501ce6d6 100644 --- a/src/script/lua_api/CMakeLists.txt +++ b/src/script/lua_api/CMakeLists.txt @@ -1,4 +1,5 @@ set(common_SCRIPT_LUA_API_SRCS + ${CMAKE_CURRENT_SOURCE_DIR}/l_areastore.cpp ${CMAKE_CURRENT_SOURCE_DIR}/l_base.cpp ${CMAKE_CURRENT_SOURCE_DIR}/l_craft.cpp ${CMAKE_CURRENT_SOURCE_DIR}/l_env.cpp diff --git a/src/script/lua_api/l_areastore.cpp b/src/script/lua_api/l_areastore.cpp new file mode 100644 index 000000000..1e9075119 --- /dev/null +++ b/src/script/lua_api/l_areastore.cpp @@ -0,0 +1,401 @@ +/* +Minetest +Copyright (C) 2015 est31 <mtest31@outlook.com> + +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 "lua_api/l_areastore.h" +#include "lua_api/l_internal.h" +#include "common/c_converter.h" +#include "cpp_api/s_security.h" +#include "areastore.h" +#include "filesys.h" +#ifndef ANDROID + #include "cmake_config.h" +#endif +#include <fstream> + +static inline void get_data_and_border_flags(lua_State *L, u8 start_i, + bool *borders, bool *data) +{ + if (!lua_isboolean(L, start_i)) + return; + *borders = lua_toboolean(L, start_i); + if (!lua_isboolean(L, start_i + 1)) + return; + *data = lua_toboolean(L, start_i + 1); +} + +static void push_area(lua_State *L, const Area *a, + bool include_borders, bool include_data) +{ + if (!include_borders && !include_data) { + lua_pushboolean(L, true); + } + lua_newtable(L); + if (include_borders) { + push_v3s16(L, a->minedge); + lua_setfield(L, -2, "min"); + push_v3s16(L, a->maxedge); + lua_setfield(L, -2, "max"); + } + if (include_data) { + lua_pushlstring(L, a->data.c_str(), a->data.size()); + lua_setfield(L, -2, "data"); + } +} + +static inline void push_areas(lua_State *L, const std::vector<Area *> &areas, + bool borders, bool data) +{ + lua_newtable(L); + size_t cnt = areas.size(); + for (size_t i = 0; i < cnt; i++) { + lua_pushnumber(L, areas[i]->id); + push_area(L, areas[i], borders, data); + lua_settable(L, -3); + } +} + +// garbage collector +int LuaAreaStore::gc_object(lua_State *L) +{ + LuaAreaStore *o = *(LuaAreaStore **)(lua_touserdata(L, 1)); + delete o; + return 0; +} + +// get_area(id, include_borders, include_data) +int LuaAreaStore::l_get_area(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + u32 id = luaL_checknumber(L, 2); + + bool include_borders = true; + bool include_data = false; + get_data_and_border_flags(L, 3, &include_borders, &include_data); + + const Area *res; + + res = ast->getArea(id); + push_area(L, res, include_borders, include_data); + + return 1; +} + +// get_areas_for_pos(pos, include_borders, include_data) +int LuaAreaStore::l_get_areas_for_pos(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + v3s16 pos = check_v3s16(L, 2); + + bool include_borders = true; + bool include_data = false; + get_data_and_border_flags(L, 3, &include_borders, &include_data); + + std::vector<Area *> res; + + ast->getAreasForPos(&res, pos); + push_areas(L, res, include_borders, include_data); + + return 1; +} + +// get_areas_in_area(edge1, edge2, accept_overlap, include_borders, include_data) +int LuaAreaStore::l_get_areas_in_area(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + v3s16 minedge = check_v3s16(L, 2); + v3s16 maxedge = check_v3s16(L, 3); + + bool include_borders = true; + bool include_data = false; + bool accept_overlap = false; + if (lua_isboolean(L, 4)) { + accept_overlap = lua_toboolean(L, 4); + get_data_and_border_flags(L, 5, &include_borders, &include_data); + } + std::vector<Area *> res; + + ast->getAreasInArea(&res, minedge, maxedge, accept_overlap); + push_areas(L, res, include_borders, include_data); + + return 1; +} + +// insert_area(edge1, edge2, data) +int LuaAreaStore::l_insert_area(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + Area a; + + a.minedge = check_v3s16(L, 2); + a.maxedge = check_v3s16(L, 3); + + a.extremifyEdges(); + a.id = ast->getFreeId(a.minedge, a.maxedge); + + if (a.id == AREA_ID_INVALID) { + // couldn't get free id + lua_pushnil(L); + return 1; + } + + size_t d_len; + const char *data = luaL_checklstring(L, 4, &d_len); + + a.data = std::string(data, d_len); + + ast->insertArea(a); + + lua_pushnumber(L, a.id); + return 1; +} + +// reserve(count) +int LuaAreaStore::l_reserve(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + size_t count = luaL_checknumber(L, 2); + ast->reserve(count); + return 0; +} + +// remove_area(id) +int LuaAreaStore::l_remove_area(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + u32 id = luaL_checknumber(L, 2); + bool success = ast->removeArea(id); + + lua_pushboolean(L, success); + return 1; +} + +// set_cache_params(params) +int LuaAreaStore::l_set_cache_params(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + luaL_checktype(L, 2, LUA_TTABLE); + + bool enabled = getboolfield_default(L, 2, "enabled", true); + u8 block_radius = getintfield_default(L, 2, "block_radius", 64); + size_t limit = getintfield_default(L, 2, "block_radius", 1000); + + ast->setCacheParams(enabled, block_radius, limit); + + return 0; +} + +#if 0 +// to_string() +int LuaAreaStore::l_to_string(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + std::ostringstream os(std::ios_base::binary); + ast->serialize(os); + std::string str = os.str(); + + lua_pushlstring(L, str.c_str(), str.length()); + return 1; +} + +// to_file(filename) +int LuaAreaStore::l_to_file(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + const char *filename = luaL_checkstring(L, 2); + CHECK_SECURE_PATH_OPTIONAL(L, filename); + + std::ostringstream os(std::ios_base::binary); + ast->serialize(os); + + lua_pushboolean(L, fs::safeWriteToFile(filename, os.str())); + return 1; +} + +// from_string(str) +int LuaAreaStore::l_from_string(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + size_t len; + const char *str = luaL_checklstring(L, 2, &len); + + std::istringstream is(std::string(str, len), std::ios::binary); + bool success = ast->deserialize(is); + + lua_pushboolean(L, success); + return 1; +} + +// from_file(filename) +int LuaAreaStore::l_from_file(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = checkobject(L, 1); + AreaStore *ast = o->as; + + const char *filename = luaL_checkstring(L, 2); + CHECK_SECURE_PATH_OPTIONAL(L, filename); + + std::ifstream is(filename, std::ios::binary); + bool success = ast->deserialize(is); + + lua_pushboolean(L, success); + return 1; +} +#endif + +LuaAreaStore::LuaAreaStore() +{ +#if USE_SPATIAL + this->as = new SpatialAreaStore(); +#else + this->as = new VectorAreaStore(); +#endif +} + +LuaAreaStore::LuaAreaStore(const std::string &type) +{ +#if USE_SPATIAL + if (type == "LibSpatial") { + this->as = new SpatialAreaStore(); + } else +#endif + { + this->as = new VectorAreaStore(); + } +} + +LuaAreaStore::~LuaAreaStore() +{ + delete as; +} + +// LuaAreaStore() +// Creates an LuaAreaStore and leaves it on top of stack +int LuaAreaStore::create_object(lua_State *L) +{ + NO_MAP_LOCK_REQUIRED; + + LuaAreaStore *o = (lua_isstring(L, 1)) ? + new LuaAreaStore(lua_tostring(L, 1)) : + new LuaAreaStore(); + + *(void **)(lua_newuserdata(L, sizeof(void *))) = o; + luaL_getmetatable(L, className); + lua_setmetatable(L, -2); + return 1; +} + +LuaAreaStore *LuaAreaStore::checkobject(lua_State *L, int narg) +{ + NO_MAP_LOCK_REQUIRED; + + luaL_checktype(L, narg, LUA_TUSERDATA); + + void *ud = luaL_checkudata(L, narg, className); + if (!ud) + luaL_typerror(L, narg, className); + + return *(LuaAreaStore **)ud; // unbox pointer +} + +void LuaAreaStore::Register(lua_State *L) +{ + lua_newtable(L); + int methodtable = lua_gettop(L); + luaL_newmetatable(L, className); + int metatable = lua_gettop(L); + + lua_pushliteral(L, "__metatable"); + lua_pushvalue(L, methodtable); + lua_settable(L, metatable); // hide metatable from Lua getmetatable() + + lua_pushliteral(L, "__index"); + lua_pushvalue(L, methodtable); + lua_settable(L, metatable); + + lua_pushliteral(L, "__gc"); + lua_pushcfunction(L, gc_object); + lua_settable(L, metatable); + + lua_pop(L, 1); // drop metatable + + luaL_openlib(L, 0, methods, 0); // fill methodtable + lua_pop(L, 1); // drop methodtable + + // Can be created from Lua (AreaStore()) + lua_register(L, className, create_object); +} + +const char LuaAreaStore::className[] = "AreaStore"; +const luaL_reg LuaAreaStore::methods[] = { + luamethod(LuaAreaStore, get_area), + luamethod(LuaAreaStore, get_areas_for_pos), + luamethod(LuaAreaStore, get_areas_in_area), + luamethod(LuaAreaStore, insert_area), + luamethod(LuaAreaStore, reserve), + luamethod(LuaAreaStore, remove_area), + luamethod(LuaAreaStore, set_cache_params), + /* luamethod(LuaAreaStore, to_string), + luamethod(LuaAreaStore, to_file), + luamethod(LuaAreaStore, from_string), + luamethod(LuaAreaStore, from_file),*/ + {0,0} +}; diff --git a/src/script/lua_api/l_areastore.h b/src/script/lua_api/l_areastore.h new file mode 100644 index 000000000..a25529627 --- /dev/null +++ b/src/script/lua_api/l_areastore.h @@ -0,0 +1,70 @@ +/* +Minetest +Copyright (C) 2015 est31 <mtest31@outlook.com> + +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 L_AREASTORE_H_ +#define L_AREASTORE_H_ + +#include "lua_api/l_base.h" +#include "irr_v3d.h" +#include "areastore.h" + +/* + AreaStore + */ +class LuaAreaStore : public ModApiBase { +private: + + static const char className[]; + static const luaL_reg methods[]; + + static int gc_object(lua_State *L); + + static int l_get_area(lua_State *L); + + static int l_get_areas_for_pos(lua_State *L); + static int l_get_areas_in_area(lua_State *L); + static int l_insert_area(lua_State *L); + static int l_reserve(lua_State *L); + static int l_remove_area(lua_State *L); + + static int l_set_cache_params(lua_State *L); + + /* static int l_to_string(lua_State *L); + static int l_to_file(lua_State *L); + + static int l_from_string(lua_State *L); + static int l_from_file(lua_State *L); */ + +public: + AreaStore *as; + + LuaAreaStore(); + LuaAreaStore(const std::string &type); + ~LuaAreaStore(); + + // AreaStore() + // Creates a AreaStore and leaves it on top of stack + static int create_object(lua_State *L); + + static LuaAreaStore *checkobject(lua_State *L, int narg); + + static void Register(lua_State *L); +}; + +#endif /* L_AREASTORE_H_ */ diff --git a/src/script/lua_api/l_util.cpp b/src/script/lua_api/l_util.cpp index d97db2367..12146e80a 100644 --- a/src/script/lua_api/l_util.cpp +++ b/src/script/lua_api/l_util.cpp @@ -25,6 +25,7 @@ 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 "debug.h" #include "porting.h" #include "log.h" diff --git a/src/script/scripting_game.cpp b/src/script/scripting_game.cpp index 9321c38a9..8047c58cc 100644 --- a/src/script/scripting_game.cpp +++ b/src/script/scripting_game.cpp @@ -22,6 +22,7 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "log.h" #include "settings.h" #include "cpp_api/s_internal.h" +#include "lua_api/l_areastore.h" #include "lua_api/l_base.h" #include "lua_api/l_craft.h" #include "lua_api/l_env.h" @@ -91,6 +92,7 @@ void GameScripting::InitializeModApi(lua_State *L, int top) // Register reference classes (userdata) InvRef::Register(L); + LuaAreaStore::Register(L); LuaItemStack::Register(L); LuaPerlinNoise::Register(L); LuaPerlinNoiseMap::Register(L); diff --git a/src/unittest/CMakeLists.txt b/src/unittest/CMakeLists.txt index dcc68f9c8..bdff14f05 100644 --- a/src/unittest/CMakeLists.txt +++ b/src/unittest/CMakeLists.txt @@ -1,5 +1,6 @@ set (UNITTEST_SRCS ${CMAKE_CURRENT_SOURCE_DIR}/test.cpp + ${CMAKE_CURRENT_SOURCE_DIR}/test_areastore.cpp ${CMAKE_CURRENT_SOURCE_DIR}/test_collision.cpp ${CMAKE_CURRENT_SOURCE_DIR}/test_compression.cpp ${CMAKE_CURRENT_SOURCE_DIR}/test_connection.cpp diff --git a/src/unittest/test_areastore.cpp b/src/unittest/test_areastore.cpp new file mode 100644 index 000000000..a0dcada94 --- /dev/null +++ b/src/unittest/test_areastore.cpp @@ -0,0 +1,129 @@ +/* +Minetest +Copyright (C) 2015 est31, <MTest31@outlook.com> + +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 "test.h" + +#include "areastore.h" + +class TestAreaStore : public TestBase { +public: + TestAreaStore() { TestManager::registerTestModule(this); } + const char *getName() { return "TestAreaStore"; } + + void runTests(IGameDef *gamedef); + + void genericStoreTest(AreaStore *store); + void testVectorStore(); + void testSpatialStore(); +}; + +static TestAreaStore g_test_instance; + +void TestAreaStore::runTests(IGameDef *gamedef) +{ + TEST(testVectorStore); +#if USE_SPATIAL + TEST(testSpatialStore); +#endif +} + +//////////////////////////////////////////////////////////////////////////////// + +void TestAreaStore::testVectorStore() +{ + VectorAreaStore store; + genericStoreTest(&store); +} + +void TestAreaStore::testSpatialStore() +{ +#if USE_SPATIAL + SpatialAreaStore store; + genericStoreTest(&store); +#endif +} + +void TestAreaStore::genericStoreTest(AreaStore *store) +{ + Area a(v3s16(-10, -3, 5), v3s16(0, 29, 7)); + a.id = 1; + Area b(v3s16(-5, -2, 5), v3s16(0, 28, 6)); + b.id = 2; + Area c(v3s16(-7, -3, 6), v3s16(-1, 27, 7)); + c.id = 3; + std::vector<Area *> res; + + UASSERTEQ(size_t, store->size(), 0); + store->reserve(2); // sic + store->insertArea(a); + store->insertArea(b); + store->insertArea(c); + UASSERTEQ(size_t, store->size(), 3); + + store->getAreasForPos(&res, v3s16(-1, 0, 6)); + UASSERTEQ(size_t, res.size(), 3); + res.clear(); + store->getAreasForPos(&res, v3s16(0, 0, 7)); + UASSERTEQ(size_t, res.size(), 1); + UASSERTEQ(u32, res[0]->id, 1); + res.clear(); + + store->removeArea(1); + + store->getAreasForPos(&res, v3s16(0, 0, 7)); + UASSERTEQ(size_t, res.size(), 0); + res.clear(); + + store->insertArea(a); + + store->getAreasForPos(&res, v3s16(0, 0, 7)); + UASSERTEQ(size_t, res.size(), 1); + UASSERTEQ(u32, res[0]->id, 1); + res.clear(); + + store->getAreasInArea(&res, v3s16(-10, -3, 5), v3s16(0, 29, 7), false); + UASSERTEQ(size_t, res.size(), 3); + res.clear(); + + store->getAreasInArea(&res, v3s16(-100, 0, 6), v3s16(200, 0, 6), false); + UASSERTEQ(size_t, res.size(), 0); + res.clear(); + + store->getAreasInArea(&res, v3s16(-100, 0, 6), v3s16(200, 0, 6), true); + UASSERTEQ(size_t, res.size(), 3); + res.clear(); + + store->removeArea(1); + store->removeArea(2); + store->removeArea(3); + + Area d(v3s16(-100, -300, -200), v3s16(-50, -200, -100)); + d.id = 4; + d.data = "Hi!"; + store->insertArea(d); + + store->getAreasForPos(&res, v3s16(-75, -250, -150)); + UASSERTEQ(size_t, res.size(), 1); + UASSERTEQ(u32, res[0]->id, 4); + UASSERTEQ(u16, res[0]->data.size(), 3); + UASSERT(strncmp(res[0]->data.c_str(), "Hi!", 3) == 0); + res.clear(); + + store->removeArea(4); +} diff --git a/src/util/container.h b/src/util/container.h index 936c46d61..267d54c16 100644 --- a/src/util/container.h +++ b/src/util/container.h @@ -309,5 +309,74 @@ protected: JSemaphore m_size; }; +template<typename K, typename V> +class LRUCache +{ +public: + LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest), + void *data) + { + m_limit = limit; + m_cache_miss = cache_miss; + m_cache_miss_data = data; + } + + void setLimit(size_t limit) + { + m_limit = limit; + invalidate(); + } + + void invalidate() + { + m_map.clear(); + m_queue.clear(); + } + + const V *lookupCache(K key) + { + typename cache_type::iterator it = m_map.find(key); + V *ret; + if (it != m_map.end()) { + // found! + + cache_entry_t &entry = it->second; + + ret = &entry.second; + + // update the usage information + m_queue.erase(entry.first); + m_queue.push_front(key); + entry.first = m_queue.begin(); + } else { + // cache miss -- enter into cache + cache_entry_t &entry = + m_map[key]; + ret = &entry.second; + m_cache_miss(m_cache_miss_data, key, &entry.second); + + // delete old entries + if (m_queue.size() == m_limit) { + const K &id = m_queue.back(); + m_map.erase(id); + m_queue.pop_back(); + } + + m_queue.push_front(key); + entry.first = m_queue.begin(); + } + return ret; + } +private: + void (*m_cache_miss)(void *data, const K &key, V *dest); + void *m_cache_miss_data; + size_t m_limit; + typedef typename std::template pair<typename std::template list<K>::iterator, V> cache_entry_t; + typedef std::template map<K, cache_entry_t> cache_type; + cache_type m_map; + // we can't use std::deque here, because its iterators get invalidated + std::list<K> m_queue; +}; + #endif |