textures/base/pack/down_arrow.png

/*
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 "util/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))


AreaStore *AreaStore::getOptimalImplementation()
{
#if USE_SPATIAL
	return new SpatialAreaStore();
#else
	return new VectorAreaStore();
#endif
}

const Area *AreaStore::getArea(u32 id) const
{
	AreaMap::const_iterator it = areas_map.find(id);
	if (it == areas_map.end())
		return NULL;
	return &it->second;
}

void AreaStore::serialize(std::ostream &os) const
{
	writeU8(os, 0); // Serialisation version

	// TODO: Compression?
	writeU16(os, areas_map.size());
	for (AreaMap::const_iterator it = areas_map.begin();
			it != areas_map.end(); ++it) {
		const Area &a = it->second;
		writeV3S16(os, a.minedge);
		writeV3S16(os, a.maxedge);
		writeU16(os, a.data.size());
		os.write(a.data.data(), a.data.size());
	}
}

void AreaStore::deserialize(std::istream &is)
{
	u8 ver = readU8(is);
	if (ver != 0)
		throw SerializationError("Unknown AreaStore "
				"serialization version!");

	u16 num_areas = readU16(is);
	for (u32 i = 0; i < num_areas; ++i) {
		Area a;
		a.minedge = readV3S16(is);
		a.maxedge = readV3S16(is);
		u16 data_len = readU16(is);
		char *data = new char[data_len];
		is.read(data, data_len);
		a.data = std::string(data, data_len);
		insertArea(&a);
		delete [] data;
	}
}

void AreaStore::invalidateCache()
{
	if (m_cache_enabled) {
		m_res_cache.invalidate();
	}
}

void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
{
	m_cache_enabled = enabled;
	m_cacheblock_radius = MYMAX(block_radius, 16);
	m_res_cache.setLimit(MYMAX(limit, 20));
	invalidateCache();
}

void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<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 (m_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
////


bool VectorAreaStore::insertArea(Area *a)
{
	if (a->id == U32_MAX)
		a->id = getNextId();
	std::pair<AreaMap::iterator, bool> res =
			areas_map.insert(std::make_pair(a->id, *a));
	if (!res.second)
		// ID is not unique
		return false;
	m_areas.push_back(&res.first->second);
	invalidateCache();
	return true;
}

bool VectorAreaStore::removeArea(u32 id)
{
	AreaMap::iterator it = areas_map.find(id);
	if (it == areas_map.end())
		return false;
	Area *a = &it->second;
	for (std::vector<Area *>::iterator v_it = m_areas.begin();
			v_it != m_areas.end(); ++v_it) {
		if (*v_it == a) {
			m_areas.erase(v_it);
			break;
		}
	}
	areas_map.erase(it);
	invalidateCache();
	return true;
}
ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 00 80 00 00 00 80 02 03 00 00 00 be 50 89	.PNG........IHDR..............P.
0020	58 00 00 00 09 50 4c 54 45 00 00 00 ff ff ff ff ff ff 73 78 a5 63 00 00 00 02 74 52 4e 53 00 00	X....PLTE.........sx.c....tRNS..
0040	76 93 cd 38 00 00 01 19 49 44 41 54 78 5e ed d6 b1 8d 83 40 18 85 c1 15 c1 05 2e 65 4b a3 0a 4a	v..8....IDATx^.....@.......eK..J
0060	70 09 0e 61 ab 3c 61 9f f5 82 f9 e1 b2 93 75 e2 25 4e 3e d0 78 93 a5 7d cc be 46 b1 7b cb 7a 15	p..a.<a.......u.%N>.x..}..F.{.z.
0080	ac 2d 1b e5 12 4c 75 b0 84 b0 c7 2c 88 76 5b ab a0 3f 12 3c aa e0 f6 8f 82 2b b8 82 2b b8 82 2b	.-...Lu....,.v[..?.<.....+..+..+
00a0	98 c7 a8 83 31 b6 d7 75 73 1c 8c 25 bf ee fd 64 7f 5f 5f ec e7 e6 9b 03 90 b1 3f 9a f7 bb e9 19	....1..us..%...d.__.......?.....
00c0	84 e5 fe 2a b8 9f 7d 15 fc f6 37 f7 b3 ee db 71 30 af 7b 75 82 78 1e f5 14 84 84 e5 95 9d 9d 34	...*..}...7....q0.{u.x.........4
00e0	08 08 41 d4 04 10 10 12 96 04 10 10 40 40 00 21 21 a9 04 10 10 68 21 80 90 90 58 02 08 08 d4 10	..A.........@@.!!....h!...X.....
0100	40 40 20 87 10 04 04 7a 08 20 20 80 80 00 02 02 08 08 20 42 40 0d 01 04 04 10 10 40 40 00 01 01	@@.....z...........B@......@@...
0120	04 04 10 10 40 40 00 11 02 08 08 20 20 80 80 00 02 02 08 09 22 42 10 01 01 04 04 10 10 40 84 50	....@@.............."B.......@.P
0140	22 20 80 80 00 22 84 12 01 01 44 08 35 62 ed 21 94 88 31 42 a8 11 21 1c 20 42 a8 37 6f ed f3 f6	"...."....D.5b.!..1B..!..B.7o...
0160	0d 47 be 0d 6c 1a 34 fc c9 00 00 00 00 49 45 4e 44 ae 42 60 82	.G..l.4......IEND.B`.