aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.txt3
-rw-r--r--build/android/jni/Android.mk2
-rw-r--r--doc/lua_api.txt22
-rw-r--r--src/CMakeLists.txt22
-rw-r--r--src/areastore.cpp343
-rw-r--r--src/areastore.h196
-rw-r--r--src/cmake_config.h.in1
-rw-r--r--src/script/lua_api/CMakeLists.txt1
-rw-r--r--src/script/lua_api/l_areastore.cpp401
-rw-r--r--src/script/lua_api/l_areastore.h70
-rw-r--r--src/script/lua_api/l_util.cpp1
-rw-r--r--src/script/scripting_game.cpp2
-rw-r--r--src/unittest/CMakeLists.txt1
-rw-r--r--src/unittest/test_areastore.cpp129
-rw-r--r--src/util/container.h69
15 files changed, 1263 insertions, 0 deletions
diff --git a/README.txt b/README.txt
index 5a17b2a9d..ca15222e5 100644
--- a/README.txt
+++ b/README.txt
@@ -164,6 +164,7 @@ ENABLE_GETTEXT - Build with Gettext; Allows using translations
ENABLE_GLES - Search for Open GLES headers & libraries and use them
ENABLE_LEVELDB - Build with LevelDB; Enables use of LevelDB map backend (faster than SQLite3)
ENABLE_REDIS - Build with libhiredis; Enables use of Redis map backend
+ENABLE_SPATIAL - Build with LibSpatial; Speeds up AreaStores
ENABLE_SOUND - Build with OpenAL, libogg & libvorbis; in-game Sounds
ENABLE_LUAJIT - Build with LuaJIT (much faster than non-JIT Lua)
ENABLE_SYSTEM_GMP - Use GMP from system (much faster than bundled mini-gmp)
@@ -197,6 +198,8 @@ LEVELDB_LIBRARY - Only when building with LevelDB; path to lible
LEVELDB_DLL - Only when building with LevelDB on Windows; path to libleveldb.dll
REDIS_INCLUDE_DIR - Only when building with Redis support; directory that contains hiredis.h
REDIS_LIBRARY - Only when building with Redis support; path to libhiredis.a/libhiredis.so
+SPATIAL_INCLUDE_DIR - Only if you want to build with LibSpatial; directory that contains spatialindex/SpatialIndex.h
+SPATIAL_LIBRARY - Only if you want to build with LibSpatial; path to libspatialindex_c.so
LUA_INCLUDE_DIR - Only if you want to use LuaJIT; directory where luajit.h is located
LUA_LIBRARY - Only if you want to use LuaJIT; path to libluajit.a/libluajit.so
MINGWM10_DLL - Only if compiling with MinGW; path to mingwm10.dll
diff --git a/build/android/jni/Android.mk b/build/android/jni/Android.mk
index e606ccfc9..332677b84 100644
--- a/build/android/jni/Android.mk
+++ b/build/android/jni/Android.mk
@@ -112,6 +112,7 @@ LOCAL_C_INCLUDES := \
deps/sqlite/
LOCAL_SRC_FILES := \
+ jni/src/areastore.cpp \
jni/src/ban.cpp \
jni/src/camera.cpp \
jni/src/cavegen.cpp \
@@ -283,6 +284,7 @@ LOCAL_SRC_FILES += \
jni/src/script/cpp_api/s_player.cpp \
jni/src/script/cpp_api/s_security.cpp \
jni/src/script/cpp_api/s_server.cpp \
+ jni/src/script/lua_api/l_areastore.cpp \
jni/src/script/lua_api/l_base.cpp \
jni/src/script/lua_api/l_craft.cpp \
jni/src/script/lua_api/l_env.cpp \
diff --git a/doc/lua_api.txt b/doc/lua_api.txt
index 75bbbdb07..ab059e182 100644
--- a/doc/lua_api.txt
+++ b/doc/lua_api.txt
@@ -2602,6 +2602,28 @@ An `InvRef` is a reference to an inventory.
* `get_location()`: returns a location compatible to `minetest.get_inventory(location)`
* returns `{type="undefined"}` in case location is not known
+### `AreaStore`
+A fast access data structure to store areas, and find areas near a given position or area.
+Every area has a `data` string attribute to store additional information.
+You can create an empty `AreaStore` by calling `AreaStore()`, or `AreaStore(type_name)`.
+If you chose the parameter-less constructor, a fast implementation will be automatically chosen for you.
+
+#### Methods
+* `get_area(id, include_borders, include_data)`: returns the area with the id `id`. (optional) Boolean values `include_borders` and `include_data` control what's copied.
+* `get_areas_for_pos(pos, include_borders, include_data)`: returns all areas that contain the position `pos`. (optional) Boolean values `include_borders` and `include_data` control what's copied.
+* `get_areas_in_area(edge1, edge2, accept_overlap, include_borders, include_data)`: returns all areas that contain all nodes inside the area specified by `edge1` and `edge2` (inclusive). If `accept_overlap` is true, also areas are returned that have nodes in common with the specified area. (optional) Boolean values `include_borders` and `include_data` control what's copied.
+* `insert_area(edge1, edge2, data)`: inserts an area into the store. Returns the id if successful, nil otherwise. The (inclusive) positions `edge1` and `edge2` describe the area, `data`
+is a string stored with the area.
+* `reserve(count)`: reserves resources for at most `count` many contained areas. Only needed for efficiency, and only some implementations profit.
+* `remove_area(id)`: removes the area with the given id from the store, returns success.
+* `set_cache_params(params)`: sets params for the included prefiltering cache. Calling invalidates the cache, so that its elements have to be newly generated.
+ * `params`:
+ {
+ enabled = boolean, -- whether to enable, default true
+ block_radius = number, -- the radius (in nodes) of the areas the cache generates prefiltered lists for, minimum 16, default 64
+ limit = number, -- the cache's size, minimum 20, default 1000
+ }
+
### `ItemStack`
An `ItemStack` is a stack of items.
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-26 04:03:23 +0000