susumu.yata
null+****@clear*****
Mon Feb 18 12:05:25 JST 2013
susumu.yata 2013-02-18 12:05:25 +0900 (Mon, 18 Feb 2013) New Revision: 576e0f02aee962007481cd0fe6d249aac0eeada0 https://github.com/groonga/grnxx/commit/576e0f02aee962007481cd0fe6d249aac0eeada0 Log: Implement grnxx::map::DoubleArray. DoubleArray uses grnxx::map::da::TrieException to detect size-errors. Modified files: lib/map/da/basic_trie.cpp lib/map/da/trie.hpp lib/map/double_array.cpp lib/map/double_array.hpp Modified: lib/map/da/basic_trie.cpp (+16 -17) =================================================================== --- lib/map/da/basic_trie.cpp 2013-02-18 12:02:38 +0900 (06ab83d) +++ lib/map/da/basic_trie.cpp 2013-02-18 12:05:25 +0900 (52c654a) @@ -1,6 +1,5 @@ #include "basic_trie.hpp" -#include "../../exception.hpp" #include "../../lock.hpp" #include "../../logger.hpp" @@ -552,9 +551,9 @@ bool Trie::insert_leaf(const Slice &key, uint32_t &node_id, size_t query_pos) { } if (header_->num_keys >= header_->entries_size) { - GRNXX_ERROR() << "too many keys: num_keys = " << header_->num_keys - << ", entries_size = " << header_->entries_size; - GRNXX_THROW(); + GRNXX_NOTICE() << "too many keys: num_keys = " << header_->num_keys + << ", entries_size = " << header_->entries_size; + throw TrieException(); } GRNXX_DEBUG_THROW_IF(static_cast<uint32_t>(header_->next_key_id) >= header_->entries_size); @@ -568,9 +567,9 @@ bool Trie::insert_leaf(const Slice &key, uint32_t &node_id, size_t query_pos) { return true; } else { if (header_->num_keys >= header_->entries_size) { - GRNXX_ERROR() << "too many keys: num_keys = " << header_->num_keys - << ", entries_size = " << header_->entries_size; - GRNXX_THROW(); + GRNXX_NOTICE() << "too many keys: num_keys = " << header_->num_keys + << ", entries_size = " << header_->entries_size; + throw TrieException(); } const uint16_t label = (query_pos < key.size()) ? @@ -644,19 +643,19 @@ uint32_t Trie::insert_node(uint32_t node_id, uint16_t label) { uint32_t Trie::append_key(const Slice &key, int32_t key_id) { if (static_cast<uint32_t>(key_id) >= header_->entries_size) { - GRNXX_ERROR() << "too many keys: key_id = " << key_id - << ", entries_size = " << header_->entries_size; - GRNXX_THROW(); + GRNXX_NOTICE() << "too many keys: key_id = " << key_id + << ", entries_size = " << header_->entries_size; + throw TrieException(); } const uint32_t key_pos = header_->next_key_pos; const uint32_t key_size = Key::estimate_size(key.size()); if (key_size > (header_->keys_size - key_pos)) { - GRNXX_ERROR() << "too many keys: key_size = " << key_size - << ", keys_size = " << header_->keys_size - << ", key_pos = " << key_pos; - GRNXX_THROW(); + GRNXX_NOTICE() << "too many keys: key_size = " << key_size + << ", keys_size = " << header_->keys_size + << ", key_pos = " << key_pos; + throw TrieException(); } new (&keys_[key_pos]) Key(key_id, key); @@ -887,9 +886,9 @@ void Trie::reserve_chunk(uint32_t chunk_id) { GRNXX_DEBUG_THROW_IF(chunk_id != header_->num_chunks); if (chunk_id >= header_->chunks_size) { - GRNXX_ERROR() << "too many chunks: chunk_id = " << chunk_id - << ", chunks_size = " << header_->chunks_size; - GRNXX_THROW(); + GRNXX_NOTICE() << "too many chunks: chunk_id = " << chunk_id + << ", chunks_size = " << header_->chunks_size; + throw TrieException(); } header_->num_chunks = chunk_id + 1; Modified: lib/map/da/trie.hpp (+15 -0) =================================================================== --- lib/map/da/trie.hpp 2013-02-18 12:02:38 +0900 (343d9e4) +++ lib/map/da/trie.hpp 2013-02-18 12:05:25 +0900 (68976c9) @@ -25,6 +25,21 @@ namespace grnxx { namespace map { namespace da { +class TrieException : Exception { + public: + TrieException() noexcept {} + virtual ~TrieException() noexcept {} + + TrieException(const TrieException &) noexcept {} + TrieException &operator=(const TrieException &) noexcept { + return *this; + } + + virtual const char *what() const noexcept { + return ""; + } +}; + struct TrieOptions { uint64_t nodes_size; uint64_t entries_size; Modified: lib/map/double_array.cpp (+135 -30) =================================================================== --- lib/map/double_array.cpp 2013-02-18 12:02:38 +0900 (58a1719) +++ lib/map/double_array.cpp 2013-02-18 12:05:25 +0900 (f371034) @@ -17,76 +17,181 @@ */ #include "double_array.hpp" -//#include "../exception.hpp" -//#include "../lock.hpp" -//#include "../logger.hpp" +#include "../exception.hpp" +#include "../lock.hpp" +#include "../logger.hpp" namespace grnxx { namespace map { DoubleArrayHeader::DoubleArrayHeader() : map_header(), - type(DOUBLE_ARRAY_UNKNOWN) { + front_block_id(io::BLOCK_INVALID_ID), + back_block_id(io::BLOCK_INVALID_ID) { map_header.type = MAP_DOUBLE_ARRAY; } -DoubleArray::~DoubleArray() { - // TODO -} +DoubleArray::~DoubleArray() {} -DoubleArray *DoubleArray::create(const MapOptions &, io::Pool pool) { - // TODO - return nullptr; +DoubleArray *DoubleArray::create(const MapOptions &options, io::Pool pool) { + std::unique_ptr<DoubleArray> da(new (std::nothrow) DoubleArray); + if (!da) { + GRNXX_ERROR() << "new grnxx::map::DoubleArray failed"; + GRNXX_THROW(); + } + da->create_double_array(options, pool); + return da.release(); } DoubleArray *DoubleArray::open(io::Pool pool, uint32_t block_id) { - // TODO - return nullptr; + std::unique_ptr<DoubleArray> da(new (std::nothrow) DoubleArray); + if (!da) { + GRNXX_ERROR() << "new grnxx::map::DoubleArray failed"; + GRNXX_THROW(); + } + da->open_double_array(pool, block_id); + return da.release(); } uint32_t DoubleArray::block_id() const { - // TODO - return 0; + return block_info_->id(); } bool DoubleArray::search(int64_t key_id, Slice *key) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + return false; + } + return front_->search(key_id, key); } bool DoubleArray::search(const Slice &key, int64_t *key_id) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + return false; + } + return front_->search(key, key_id); } bool DoubleArray::insert(const Slice &key, int64_t *key_id) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + // The first trie is created in the first insertion. + da::TrieOptions options; + std::unique_ptr<da::Trie> trie(da::Trie::create(options, pool_)); + trie.swap(front_); + front_block_id_ = header_->front_block_id = front_->block_id(); + } + try { + return front_->insert(key, key_id); + } catch (const da::TrieException &) { + defrag_trie(); + return front_->insert(key, key_id); + } } bool DoubleArray::remove(int64_t key_id) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + return false; + } + return front_->remove(key_id); } bool DoubleArray::remove(const Slice &key) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + return false; + } + return front_->remove(key); } bool DoubleArray::update(int64_t key_id, const Slice &dest_key) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + return false; + } + try { + return front_->update(key_id, dest_key); + } catch (const da::TrieException &) { + defrag_trie(); + return front_->update(key_id, dest_key); + } } bool DoubleArray::update(const Slice &src_key, const Slice &dest_key, int64_t *key_id) { - // TODO - return false; + open_trie_if_needed(); + if (!front_) { + return false; + } + try { + return front_->update(src_key, dest_key, key_id); + } catch (const da::TrieException &) { + defrag_trie(); + return front_->update(src_key, dest_key, key_id); + } } -DoubleArray::DoubleArray() { - // TODO +DoubleArray::DoubleArray() + : pool_(), + block_info_(nullptr), + header_(nullptr), + front_(nullptr), + back_(nullptr), + front_block_id_(io::BLOCK_INVALID_ID), + inter_thread_mutex_() {} + +void DoubleArray::create_double_array(const MapOptions &, io::Pool pool) { + pool_ = pool; + + block_info_ = pool_.create_block(sizeof(DoubleArrayHeader)); + + void * const block_address = pool_.get_block_address(*block_info_); + header_ = static_cast<DoubleArrayHeader *>(block_address); + *header_ = DoubleArrayHeader(); +} + +void DoubleArray::open_double_array(io::Pool pool, uint32_t block_id) { + pool_ = pool; + + block_info_ = pool_.get_block_info(block_id); + + void * const block_address = pool_.get_block_address(*block_info_); + header_ = static_cast<DoubleArrayHeader *>(block_address); + + // TODO: Check the format. +} + +bool DoubleArray::open_trie_if_needed() { + if (front_block_id_ == header_->front_block_id) { + return false; + } + Lock lock(&inter_thread_mutex_); + if (front_block_id_ == header_->front_block_id) { + return false; + } + + std::unique_ptr<da::Trie> trie( + da::Trie::open(pool_, header_->front_block_id)); + trie.swap(front_); + trie.swap(back_); + front_block_id_ = front_->block_id(); + + // TODO: Remove old tries. + + return true; +} + +void DoubleArray::defrag_trie() { + da::TrieOptions options; + std::unique_ptr<da::Trie> trie(front_->defrag(options)); + trie.swap(front_); + trie.swap(back_); + front_block_id_ = header_->front_block_id = front_->block_id(); + header_->back_block_id = back_->block_id(); + + // TODO: Remove old tries. } } // namespace map Modified: lib/map/double_array.hpp (+17 -7) =================================================================== --- lib/map/double_array.hpp 2013-02-18 12:02:38 +0900 (d71d07c) +++ lib/map/double_array.hpp 2013-02-18 12:05:25 +0900 (5f490c2) @@ -19,19 +19,15 @@ #define GRNXX_MAP_DOUBLE_ARRAY_HPP #include "../map.hpp" +#include "da/trie.hpp" namespace grnxx { namespace map { -enum DoubleArrayType : int32_t { - DOUBLE_ARRAY_UNKNOWN = 0, - DOUBLE_ARRAY_BASIC = 1, - DOUBLE_ARRAY_LARGE = 2 -}; - struct DoubleArrayHeader { MapHeader map_header; - DoubleArrayType type; + uint32_t front_block_id; + uint32_t back_block_id; DoubleArrayHeader(); }; @@ -58,7 +54,21 @@ class DoubleArray : public Map { int64_t *key_id = nullptr); private: + io::Pool pool_; + const io::BlockInfo *block_info_; + DoubleArrayHeader *header_; + std::unique_ptr<da::Trie> front_; + std::unique_ptr<da::Trie> back_; + uint32_t front_block_id_; + Mutex inter_thread_mutex_; + DoubleArray(); + + void create_double_array(const MapOptions &options, io::Pool pool); + void open_double_array(io::Pool pool, uint32_t block_id); + + bool open_trie_if_needed(); + void defrag_trie(); }; } // namespace map -------------- next part -------------- HTML����������������������������...Download