Skip to content

Commit

Permalink
Simplify AreaStore ID management
Browse files Browse the repository at this point in the history
  • Loading branch information
@ShadowNinja
ShadowNinja committed Mar 7, 2016
1 parent 725cb4e commit 095db16
Show file tree
Hide file tree
Showing 5 changed files with 45 additions and 86 deletions.
3 changes: 1 addition & 2 deletions doc/lua_api.txt
View file
Expand Up @@ -2727,8 +2727,7 @@ If you chose the parameter-less constructor, a fast implementation will be autom
* `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.
* `insert_area(edge1, edge2, data)`: inserts an area into the store. Returns the new area's ID, or nil if the insertion failed. 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.
Expand Down
37 changes: 16 additions & 21 deletions src/areastore.cpp
View file
Expand Up @@ -49,21 +49,6 @@ 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;
Expand Down Expand Up @@ -185,11 +170,17 @@ void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
////


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

void VectorAreaStore::reserve(size_t count)
Expand Down Expand Up @@ -273,11 +264,15 @@ static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
}


void SpatialAreaStore::insertArea(const Area &a)
bool SpatialAreaStore::insertArea(Area *a)
{
areas_map[a.id] = a;
m_tree->insertData(0, NULL, get_spatial_region(a.minedge, a.maxedge), a.id);
a->id = getNextId();
if (!areas_map.insert(std::make_pair(a->id, *a)).second)
// ID is not unique
return false;
m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
invalidateCache();
return true;
}

bool SpatialAreaStore::removeArea(u32 id)
Expand Down
46 changes: 14 additions & 32 deletions src/areastore.h
View file
Expand Up @@ -36,34 +36,14 @@ with this program; if not, write to the Free Software Foundation, Inc.,
#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()
Area(const v3s16 &mine, const v3s16 &maxe)
{
v3s16 nminedge;
v3s16 nmaxedge;

AST_EXTREMIFY(nminedge, nmaxedge, minedge, maxedge)

maxedge = nmaxedge;
minedge = nminedge;
minedge = mine;
maxedge = maxe;
sortBoxVerticies(minedge, maxedge);
}

u32 id;
Expand All @@ -76,13 +56,16 @@ 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;
u32 getNextId() { return m_next_id++; }

// TODO change to unordered_map when we can
std::map<u32, Area> areas_map;
bool cache_enabled; // don't write to this from subclasses, only read.
public:
virtual void insertArea(const Area &a) = 0;
// Updates the area's ID
virtual bool insertArea(Area *a) = 0;
virtual void reserve(size_t count) {};
virtual bool removeArea(u32 id) = 0;
void getAreasForPos(std::vector<Area *> *result, v3s16 pos);
Expand All @@ -103,13 +86,12 @@ class AreaStore {
cache_enabled(true),
m_cacheblock_radius(64),
m_res_cache(1000, &cacheMiss, this),
m_highest_id(0)
m_next_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
Expand All @@ -120,7 +102,7 @@ class AreaStore {
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;
u32 m_next_id;

};

Expand All @@ -129,7 +111,7 @@ class VectorAreaStore : public AreaStore {
protected:
virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
public:
virtual void insertArea(const Area &a);
virtual bool insertArea(Area *a);
virtual void reserve(size_t count);
virtual bool removeArea(u32 id);
virtual void getAreasInArea(std::vector<Area *> *result,
Expand All @@ -146,7 +128,7 @@ class SpatialAreaStore : public AreaStore {
virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);
public:
SpatialAreaStore();
virtual void insertArea(const Area &a);
virtual bool insertArea(Area *a);
virtual bool removeArea(u32 id);
virtual void getAreasInArea(std::vector<Area *> *result,
v3s16 minedge, v3s16 maxedge, bool accept_overlap);
Expand Down
17 changes: 3 additions & 14 deletions src/script/lua_api/l_areastore.cpp
View file
Expand Up @@ -159,26 +159,15 @@ int LuaAreaStore::l_insert_area(lua_State *L)
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;
}
Area a(check_v3s16(L, 2), check_v3s16(L, 3));

size_t d_len;
const char *data = luaL_checklstring(L, 4, &d_len);

a.data = std::string(data, d_len);

ast->insertArea(a);
if (!ast->insertArea(&a))
return 0;

lua_pushnumber(L, a.id);
return 1;
Expand Down
28 changes: 11 additions & 17 deletions src/unittest/test_areastore.cpp
View file
Expand Up @@ -62,39 +62,34 @@ void TestAreaStore::testSpatialStore()
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);
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->removeArea(a.id);

store->getAreasForPos(&res, v3s16(0, 0, 7));
UASSERTEQ(size_t, res.size(), 0);
res.clear();

store->insertArea(a);
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);
Expand All @@ -109,21 +104,20 @@ void TestAreaStore::genericStoreTest(AreaStore *store)
UASSERTEQ(size_t, res.size(), 3);
res.clear();

store->removeArea(1);
store->removeArea(2);
store->removeArea(3);
store->removeArea(a.id);
store->removeArea(b.id);
store->removeArea(c.id);

Area d(v3s16(-100, -300, -200), v3s16(-50, -200, -100));
d.id = 4;
d.data = "Hi!";
store->insertArea(d);
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);
store->removeArea(d.id);
}

0 comments on commit 095db16

Please sign in to comment.