可変長配列データベース
では、可変長配列データベースを作成します。ここでの「可変長」とは配列の各要素のサイズが可変であることを意味します。もちろん要素数も可変です。前にも書いたように可変長データを固定長データに分割して固定長データーベースに保存します。分割した固定長データをたどるためのポインタは圧縮して持ちます。可変長配列データベースを１から作成するのは結構大変ですが、既に可変長配列を構成する部品は揃っているので、純粋な可変長配列データベースの実装部分は結構少ないです。
class VariableArray { public: static const size_t headSize = 128; static const size_t bodySize = 256; // Format:|size(encoded)|body index(encoded)|data...| class Head { public: Head() { *record = 0; } unsigned char record[headSize]; }; // Format:|next index(encoded)|data...| class Body { public: unsigned char record[bodySize]; }; VariableArray(const std::string &f) { initialize(f); } void initialize(const std::string &f) { std::string str = f; str.append("_h"); head.initialize(str); str = f; str.append("_t"); body.initialize(str); } void set(size_t idx, std::vector<unsigned char> &val) { set(idx, &val[0], val.size()); } void set(size_t idx, unsigned char *val, size_t size) { erase(idx); if (idx >= head.getSize()) { head.resize(idx + 1); } unsigned char *ptr = (unsigned char*)&head.at(idx); int sizeSize = Codec::encode(size, ptr); size_t bodyIndexSize = 1; size_t totalSize = size + sizeSize + bodyIndexSize; ptr += sizeSize; size_t bodyIndex; int len; if (totalSize > headSize) { bodyIndex = body.insert(); bodyIndexSize = Codec::encode(bodyIndex, ptr); len = headSize - sizeSize - bodyIndexSize; } else { bodyIndex = 0; //bodyIndexSize = Codec::encode(bodyIndex, ptr); bodyIndexSize = 1; len = size; } ptr += bodyIndexSize; memcpy(ptr, val, len); while (bodyIndex != 0) { size -= len; val += len; bodyIndexSize = 1; totalSize = size + bodyIndexSize; if (totalSize > bodySize) { size_t ti = body.insert(); ptr = (unsigned char*)&body.at(bodyIndex); bodyIndex = ti; bodyIndexSize = Codec::encode(bodyIndex, ptr); len = bodySize - bodyIndexSize; } else { ptr = (unsigned char*)&body.at(bodyIndex); bodyIndex = 0; *ptr = 0; len = size; } ptr += bodyIndexSize; memcpy(ptr, val, len); } } unsigned char *get(size_t idx, size_t &size) { unsigned char *ptr = (unsigned char*)&head.at(idx); size_t sizeSize; size = Codec::decode(ptr, sizeSize); if (size == 0) { throw Exception("The specified element is empty"); } unsigned char *buf = new unsigned char[size]; unsigned char *bufptr = buf; ptr += sizeSize; size_t bodyIndexSize; size_t bodyIndex = Codec::decode(ptr, bodyIndexSize); ptr += bodyIndexSize; int len = headSize - sizeSize - bodyIndexSize; len = size > len ? len : size; memcpy(bufptr, ptr, len); while (bodyIndex != 0) { size -= len; assert(size > 0); bufptr += len; ptr = (unsigned char*)&body.at(bodyIndex); bodyIndex = Codec::decode(ptr, bodyIndexSize); ptr += bodyIndexSize; len = bodySize - bodyIndexSize; len = size > len ? len : size;; memcpy(bufptr, ptr, len); } return buf; } void erase(size_t idx) { if (idx >= head.getSize()) { return; } unsigned char *headPtr = (unsigned char*)&head.at(idx); unsigned char *ptr = headPtr; size_t sizeSize; size_t size = Codec::decode(ptr, sizeSize); if (size == 0) { // already cleared return; } ptr += sizeSize; size_t bodyIndexSize; size_t bodyIndex = Codec::decode(ptr, bodyIndexSize); headPtr[0] = 0; // size <- 0 headPtr[1] = 0; // index <- 0 invalid index while (bodyIndex != 0) { ptr = (unsigned char*)&body.at(bodyIndex); size_t nextIndex = Codec::decode(ptr, bodyIndexSize); body.remove(bodyIndex); bodyIndex = nextIndex; } return; } Array<Head> head; Pool<Body> body; };
ということで、ソースを書きなぐってきた感じですので、ちょっと使ってみたいと思っても、かなり使いにくい状態になっていますね。時間を見つけてライブラリにでもしないと。
