Add AreaStore data structure

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