Skip to content

Commit

Permalink
Rewrite DB class to allow backends to fully optimize block fetches
Browse files Browse the repository at this point in the history
  • Loading branch information
@sfan5
sfan5 committed Mar 27, 2020
1 parent ecc2b31 commit 5b264fd
Show file tree
Hide file tree
Showing 11 changed files with 326 additions and 155 deletions.
85 changes: 45 additions & 40 deletions TileGenerator.cpp
View file
@@ -1,6 +1,7 @@
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cassert>
#include <fstream>
#include <iostream>
#include <sstream>
Expand Down Expand Up @@ -89,8 +90,8 @@ TileGenerator::TileGenerator():
m_xMax(INT_MIN),
m_zMin(INT_MAX),
m_zMax(INT_MIN),
m_yMin(-30000),
m_yMax(30000),
m_yMin(INT16_MIN),
m_yMax(INT16_MAX),
m_geomX(-2048),
m_geomY(-2048),
m_geomX2(2048),
Expand Down Expand Up @@ -184,6 +185,7 @@ void TileGenerator::setBackend(std::string backend)

void TileGenerator::setGeometry(int x, int y, int w, int h)
{
assert(w > 0 && h > 0);
m_geomX = round_multiple_nosign(x, 16) / 16;
m_geomY = round_multiple_nosign(y, 16) / 16;
m_geomX2 = round_multiple_nosign(x + w, 16) / 16;
Expand All @@ -193,11 +195,15 @@ void TileGenerator::setGeometry(int x, int y, int w, int h)
void TileGenerator::setMinY(int y)
{
m_yMin = y;
if (m_yMin > m_yMax)
std::swap(m_yMin, m_yMax);
}

void TileGenerator::setMaxY(int y)
{
m_yMax = y;
if (m_yMin > m_yMax)
std::swap(m_yMin, m_yMax);
}

void TileGenerator::parseColorsFile(const std::string &fileName)
Expand Down Expand Up @@ -244,7 +250,7 @@ void TileGenerator::generate(const std::string &input, const std::string &output
openDb(input_path);
loadBlocks();

if (m_dontWriteEmpty && ! m_positions.size())
if (m_dontWriteEmpty && m_positions.empty())
{
closeDatabase();
return;
Expand All @@ -268,7 +274,7 @@ void TileGenerator::generate(const std::string &input, const std::string &output

void TileGenerator::parseColorsStream(std::istream &in)
{
char line[128];
char line[512];
while (in.good()) {
in.getline(line, sizeof(line));

Expand All @@ -281,11 +287,11 @@ void TileGenerator::parseColorsStream(std::istream &in)
if(strlen(line) == 0)
continue;

char name[64 + 1] = {0};
char name[128 + 1] = {0};
unsigned int r, g, b, a, t;
a = 255;
t = 0;
int items = sscanf(line, "%64s %u %u %u %u %u", name, &r, &g, &b, &a, &t);
int items = sscanf(line, "%128s %u %u %u %u %u", name, &r, &g, &b, &a, &t);
if(items < 4) {
std::cerr << "Failed to parse color entry '" << line << "'" << std::endl;
continue;
Expand Down Expand Up @@ -333,15 +339,17 @@ void TileGenerator::closeDatabase()

void TileGenerator::loadBlocks()
{
std::vector<BlockPos> vec = m_db->getBlockPos();
for (std::vector<BlockPos>::iterator it = vec.begin(); it != vec.end(); ++it) {
BlockPos pos = *it;
// Check that it's in geometry (from --geometry option)
if (pos.x < m_geomX || pos.x >= m_geomX2 || pos.z < m_geomY || pos.z >= m_geomY2)
continue;
// Check that it's between --min-y and --max-y
if (pos.y * 16 < m_yMin || pos.y * 16 > m_yMax)
continue;
const int16_t yMax = m_yMax / 16 + 1;
std::vector<BlockPos> vec = m_db->getBlockPos(
BlockPos(m_geomX, m_yMin / 16, m_geomY),
BlockPos(m_geomX2, yMax, m_geomY2)
);

for (auto pos : vec) {
assert(pos.x >= m_geomX && pos.x < m_geomX2);
assert(pos.y >= m_yMin / 16 && pos.y < yMax);
assert(pos.z >= m_geomY && pos.z < m_geomY2);

// Adjust minimum and maximum positions to the nearest block
if (pos.x < m_xMin)
m_xMin = pos.x;
Expand All @@ -352,10 +360,17 @@ void TileGenerator::loadBlocks()
m_zMin = pos.z;
if (pos.z > m_zMax)
m_zMax = pos.z;
m_positions.push_back(std::make_pair(pos.x, pos.z));

m_positions[pos.z].emplace(pos.x);
}
m_positions.sort();
m_positions.unique();

#ifndef NDEBUG
int count = 0;
for (const auto &it : m_positions)
count += it.second.size();
std::cout << "Loaded " << count
<< " positions (across Z: " << m_positions.size() << ") for rendering" << std::endl;
#endif
}

void TileGenerator::createImage()
Expand Down Expand Up @@ -405,13 +420,12 @@ void TileGenerator::createImage()
void TileGenerator::renderMap()
{
BlockDecoder blk;
std::list<int16_t> zlist = getZValueList();
for (int16_t zPos : zlist) {
std::map<int16_t, BlockList> blocks;
m_db->getBlocksOnZ(blocks, zPos);
for (const auto position : m_positions) {
if (position.second != zPos)
continue;
const int16_t yMax = m_yMax / 16 + 1;

for (auto it = m_positions.rbegin(); it != m_positions.rend(); ++it) {
int16_t zPos = it->first;
for (auto it2 = it->second.rbegin(); it2 != it->second.rend(); ++it2) {
int16_t xPos = *it2;

m_readPixels.reset();
m_readInfo.reset();
Expand All @@ -423,11 +437,13 @@ void TileGenerator::renderMap()
}
}

int16_t xPos = position.first;
blocks[xPos].sort();
const BlockList &blockStack = blocks[xPos];
BlockList blockStack;
m_db->getBlocksOnXZ(blockStack, xPos, zPos, m_yMin / 16, yMax);
blockStack.sort();
for (const auto &it : blockStack) {
const BlockPos &pos = it.first;
const BlockPos pos = it.first;
assert(pos.x == xPos && pos.z == zPos);
assert(pos.y >= m_yMin / 16 && pos.y < yMax);

blk.reset();
blk.decode(it.second);
Expand Down Expand Up @@ -651,17 +667,6 @@ void TileGenerator::renderPlayers(const std::string &inputPath)
}
}

inline std::list<int16_t> TileGenerator::getZValueList() const
{
std::list<int16_t> zlist;
for (const auto position : m_positions)
zlist.push_back(position.second);
zlist.sort();
zlist.unique();
zlist.reverse();
return zlist;
}

void TileGenerator::writeImage(const std::string &output)
{
m_image->save(output);
Expand Down
48 changes: 36 additions & 12 deletions db-leveldb.cpp
View file
Expand Up @@ -11,14 +11,14 @@ static inline int64_t stoi64(const std::string &s)
return t;
}


static inline std::string i64tos(int64_t i)
{
std::ostringstream os;
os << i;
return os.str();
}


DBLevelDB::DBLevelDB(const std::string &mapdir)
{
leveldb::Options options;
Expand All @@ -28,6 +28,9 @@ DBLevelDB::DBLevelDB(const std::string &mapdir)
throw std::runtime_error(std::string("Failed to open Database: ") + status.ToString());
}

/* LevelDB is a dumb key-value store, so the only optimization we can do
* is to cache the block positions that exist in the db.
*/
loadPosCache();
}

Expand All @@ -38,9 +41,21 @@ DBLevelDB::~DBLevelDB()
}


std::vector<BlockPos> DBLevelDB::getBlockPos()
std::vector<BlockPos> DBLevelDB::getBlockPos(BlockPos min, BlockPos max)
{
return posCache;
std::vector<BlockPos> res;
for (const auto &it : posCache) {
if (it.first < min.z || it.first >= max.z)
continue;
for (auto pos2 : it.second) {
if (pos2.first < min.x || pos2.first >= max.x)
continue;
if (pos2.second < min.y || pos2.second >= max.y)
continue;
res.emplace_back(pos2.first, pos2.second, it.first);
}
}
return res;
}


Expand All @@ -49,26 +64,35 @@ void DBLevelDB::loadPosCache()
leveldb::Iterator * it = db->NewIterator(leveldb::ReadOptions());
for (it->SeekToFirst(); it->Valid(); it->Next()) {
int64_t posHash = stoi64(it->key().ToString());
posCache.push_back(decodeBlockPos(posHash));
BlockPos pos = decodeBlockPos(posHash);

posCache[pos.z].emplace_back(pos.x, pos.y);
}
delete it;
}


void DBLevelDB::getBlocksOnZ(std::map<int16_t, BlockList> &blocks, int16_t zPos)
void DBLevelDB::getBlocksOnXZ(BlockList &blocks, int16_t x, int16_t z,
int16_t min_y, int16_t max_y)
{
std::string datastr;
leveldb::Status status;

for (const auto &it : posCache) {
if (it.z != zPos) {
auto it = posCache.find(z);
if (it == posCache.cend())
return;
for (auto pos2 : it->second) {
if (pos2.first != x)
continue;
}
status = db->Get(leveldb::ReadOptions(), i64tos(encodeBlockPos(it)), &datastr);
if (pos2.second < min_y || pos2.second >= max_y)
continue;

BlockPos pos(x, pos2.second, z);
status = db->Get(leveldb::ReadOptions(), i64tos(encodeBlockPos(pos)), &datastr);
if (status.ok()) {
Block b(it, ustring((const unsigned char *) datastr.data(), datastr.size()));
blocks[b.first.x].push_back(b);
blocks.emplace_back(
pos, ustring((unsigned char *) datastr.data(), datastr.size())
);
}
}
}

0 comments on commit 5b264fd

Please sign in to comment.