susumu.yata
null+****@clear*****
Sun Mar 17 20:04:59 JST 2013
susumu.yata 2013-03-17 20:04:59 +0900 (Sun, 17 Mar 2013) New Revision: ea39f9d3c12ce34610a4d94ebb3260ee6e843a13 https://github.com/groonga/grnxx/commit/ea39f9d3c12ce34610a4d94ebb3260ee6e843a13 Message: Add grnxx::map::da::basic::PredictiveCursor. Added files: lib/map/da/basic/predictive_cursor.cpp lib/map/da/basic/predictive_cursor.hpp Modified files: lib/map/da/basic/Makefile.am lib/map/da/basic/trie.cpp lib/map/da/basic/trie.hpp test/test_map_da_basic_trie.cpp Modified: lib/map/da/basic/Makefile.am (+2 -0) =================================================================== --- lib/map/da/basic/Makefile.am 2013-03-16 21:28:04 +0900 (56ced41) +++ lib/map/da/basic/Makefile.am 2013-03-17 20:04:59 +0900 (f146755) @@ -4,11 +4,13 @@ libgrnxx_map_da_basic_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_map_da_basic_la_SOURCES = \ id_cursor.cpp \ + predictive_cursor.cpp \ prefix_cursor.cpp \ trie.cpp libgrnxx_map_da_basic_includedir = ${includedir}/grnxx/map/da/basic libgrnxx_map_da_basic_include_HEADERS = \ id_cursor.hpp \ + predictive_cursor.hpp \ prefix_cursor.hpp \ trie.hpp Added: lib/map/da/basic/predictive_cursor.cpp (+174 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/predictive_cursor.cpp 2013-03-17 20:04:59 +0900 (2341cff) @@ -0,0 +1,174 @@ +#include "map/da/basic/predictive_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace basic { +namespace { + +constexpr uint64_t IS_ROOT_FLAG = uint64_t(1) << 63; +constexpr uint64_t POST_ORDER_FLAG = uint64_t(1) << 63; + +} // namespace + +PredictiveCursor::~PredictiveCursor() {} + +PredictiveCursor *PredictiveCursor::open(Trie *trie, MapCursorFlags flags, + const Slice &min, + int64_t offset, int64_t limit) { + std::unique_ptr<PredictiveCursor> cursor(new (std::nothrow) PredictiveCursor); + if (!cursor) { + GRNXX_ERROR() << "new grnxx::map::da::basic::PredictiveCursor failed"; + GRNXX_THROW(); + } + cursor->open_cursor(trie, flags, min, offset, limit); + return cursor.release(); +} + +bool PredictiveCursor::next() { + if (limit_ == 0) { + return false; + } + + if (flags_ & MAP_CURSOR_DESCENDING) { + return descending_next(); + } else { + return ascending_next(); + } +} + +PredictiveCursor::PredictiveCursor() + : MapCursor(), + trie_(), + node_ids_(), + min_size_(), + offset_(), + limit_(), + flags_() {} + +void PredictiveCursor::open_cursor(Trie *trie, MapCursorFlags flags, + const Slice &min, + int64_t offset, int64_t limit) try { + trie_ = trie; + + min_size_ = min.size(); + if (flags & MAP_CURSOR_EXCEPT_MIN) { + ++min_size_; + } + + uint64_t node_id = ROOT_NODE_ID; + for (size_t i = 0; i < min.size(); ++i) { + const Node node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + if (offset == 0) { + const Key &key = trie_->get_key(node.key_pos()); + if ((key.size() >= min_size_) && + (key.slice().subslice(i, min.size() - i) == + min.subslice(i, min.size() - i))) { + if (~flags & MAP_CURSOR_DESCENDING) { + node_id |= IS_ROOT_FLAG; + } + node_ids_.push_back(node_id); + } + } + return; + } + + node_id = node.offset() ^ min[i]; + if (trie_->nodes_[node_id].label() != min[i]) { + return; + } + } + + if (~flags & MAP_CURSOR_DESCENDING) { + node_id |= IS_ROOT_FLAG; + } + node_ids_.push_back(node_id); + + offset_ = offset; + limit_ = (limit >= 0) ? limit : std::numeric_limits<int64_t>::max(); + flags_ = flags; +} catch (...) { + // TODO: Catch only std::vector's exception. + GRNXX_ERROR() << "std::vector::push_back() failed"; + GRNXX_THROW(); +} + +bool PredictiveCursor::ascending_next() try { + while (!node_ids_.empty()) { + const bool is_root = node_ids_.back() & IS_ROOT_FLAG; + const uint64_t node_id = node_ids_.back() & ~IS_ROOT_FLAG; + node_ids_.pop_back(); + + const Node node = trie_->nodes_[node_id]; + if (!is_root && (node.sibling() != INVALID_LABEL)) { + node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); + } + + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if (key.size() >= min_size_) { + if (offset_ != 0) { + --offset_; + } else if (limit_ != 0) { + key_id_ = key.id(); + key_ = key.slice(); + --limit_; + return true; + } + } + } else if (node.child() != INVALID_LABEL) { + node_ids_.push_back(node.offset() ^ node.child()); + } + } + return false; +} catch (...) { + // TODO: Catch only std::vector's exception. + GRNXX_ERROR() << "std::vector::push_back() failed"; + GRNXX_THROW(); +} + +bool PredictiveCursor::descending_next() try { + while (!node_ids_.empty()) { + const bool post_order = node_ids_.back() & POST_ORDER_FLAG; + const uint64_t node_id = node_ids_.back() & ~POST_ORDER_FLAG; + + const Node node = trie_->nodes_[node_id]; + if (post_order) { + node_ids_.pop_back(); + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if (key.size() >= min_size_) { + if (offset_ != 0) { + --offset_; + } else if (limit_ != 0) { + key_id_ = key.id(); + key_ = key.slice(); + --limit_; + return true; + } + } + } + } else { + node_ids_.back() |= POST_ORDER_FLAG; + uint64_t label = trie_->nodes_[node_id].child(); + while (label != INVALID_LABEL) { + node_ids_.push_back(node.offset() ^ label); + label = trie_->nodes_[node.offset() ^ label].sibling(); + } + } + } + return false; +} catch (...) { + // TODO: Catch only std::vector's exception. + GRNXX_ERROR() << "std::vector::push_back() failed"; + GRNXX_THROW(); +} + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/basic/predictive_cursor.hpp (+62 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/predictive_cursor.hpp 2013-03-17 20:04:59 +0900 (bc3710a) @@ -0,0 +1,62 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library 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 library 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 library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +*/ +#ifndef GRNXX_MAP_DA_BASIC_PREDICTIVE_CURSOR_HPP +#define GRNXX_MAP_DA_BASIC_PREDICTIVE_CURSOR_HPP + +#include "map/da/basic/trie.hpp" + +#include <vector> + +namespace grnxx { +namespace map { +namespace da { +namespace basic { + +class PredictiveCursor : public MapCursor { + public: + ~PredictiveCursor(); + + static PredictiveCursor *open(Trie *trie, MapCursorFlags flags, + const Slice &min, + int64_t offset, int64_t limit); + + bool next(); + + private: + Trie *trie_; + std::vector<uint64_t> node_ids_; + size_t min_size_; + int64_t offset_; + int64_t limit_; + MapCursorFlags flags_; + + PredictiveCursor(); + + void open_cursor(Trie *trie, MapCursorFlags flags, const Slice &min, + int64_t offset, int64_t limit); + + bool ascending_next(); + bool descending_next(); +}; + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_BASIC_PREDICTIVE_CURSOR_HPP Modified: lib/map/da/basic/trie.cpp (+2 -2) =================================================================== --- lib/map/da/basic/trie.cpp 2013-03-16 21:28:04 +0900 (9ca07a1) +++ lib/map/da/basic/trie.cpp 2013-03-17 20:04:59 +0900 (6b521f9) @@ -3,6 +3,7 @@ #include "lock.hpp" #include "logger.hpp" #include "map/da/basic/id_cursor.hpp" +#include "map/da/basic/predictive_cursor.hpp" #include "map/da/basic/prefix_cursor.hpp" #include "map/da/large/trie.hpp" @@ -361,8 +362,7 @@ MapCursor *Trie::open_prefix_cursor(MapCursorFlags flags, MapCursor *Trie::open_predictive_cursor(MapCursorFlags flags, const Slice &min, int64_t offset, int64_t limit) { - // TODO - return nullptr; + return PredictiveCursor::open(this, flags, min, offset, limit); } Trie::Trie() Modified: lib/map/da/basic/trie.hpp (+5 -3) =================================================================== --- lib/map/da/basic/trie.hpp 2013-03-16 21:28:04 +0900 (fb13876) +++ lib/map/da/basic/trie.hpp 2013-03-17 20:04:59 +0900 (927dcdd) @@ -86,9 +86,6 @@ constexpr uint32_t MAX_CHUNK_LEVEL = 5; // the linked list is empty and there exists no leader. constexpr uint32_t INVALID_LEADER = std::numeric_limits<uint32_t>::max(); -class IDCursor; -class PrefixCursor; - struct Header { TrieType type; uint32_t nodes_block_id; @@ -419,9 +416,14 @@ class Key { uint8_t buf_[2]; }; +class IDCursor; +class PredictiveCursor; +class PrefixCursor; + class Trie : public da::Trie { friend class large::Trie; friend class IDCursor; + friend class PredictiveCursor; friend class PrefixCursor; public: Modified: test/test_map_da_basic_trie.cpp (+70 -0) =================================================================== --- test/test_map_da_basic_trie.cpp 2013-03-16 21:28:04 +0900 (745ff1b) +++ test/test_map_da_basic_trie.cpp 2013-03-17 20:04:59 +0900 (614dd1f) @@ -416,6 +416,75 @@ void test_id_cursor() { assert(!cursor->next()); } +void test_predictive_cursor() { + grnxx::io::Pool pool; + pool.open(grnxx::io::POOL_TEMPORARY); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::basic::Trie> trie( + grnxx::map::da::basic::Trie::create(options, pool)); + + std::vector<grnxx::Slice> keys; + keys.push_back("0"); + keys.push_back("01"); + keys.push_back("012"); + keys.push_back("0123"); + keys.push_back("0145"); + + for (std::size_t i = 0; i < keys.size(); ++i) { + std::int64_t key_id; + assert(trie->insert(keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + } + + std::unique_ptr<grnxx::MapCursor> cursor( + trie->open_predictive_cursor(grnxx::MapCursorFlags(), "", 0, -1)); + for (std::size_t i = 0; i < keys.size(); ++i) { + assert(cursor->next()); + assert(cursor->key_id() == static_cast<std::int64_t>(i)); + assert(cursor->key() == keys[i]); + } + assert(!cursor->next()); + + cursor.reset(trie->open_predictive_cursor( + grnxx::MapCursorFlags(), "012", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(!cursor->next()); + + cursor.reset(trie->open_predictive_cursor( + grnxx::MapCursorFlags(), "01", 2, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(cursor->next()); + assert(cursor->key_id() == 4); + assert(!cursor->next()); + + cursor.reset(trie->open_predictive_cursor( + grnxx::MapCursorFlags(), "", 1, 2)); + assert(cursor->next()); + assert(cursor->key_id() == 1); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(!cursor->next()); + + cursor.reset(trie->open_predictive_cursor( + grnxx::MAP_CURSOR_DESCENDING, "01", 1, 2)); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(!cursor->next()); + + cursor.reset(trie->open_predictive_cursor( + grnxx::MAP_CURSOR_EXCEPT_MIN, "012", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(!cursor->next()); +} + void test_prefix_cursor() { grnxx::io::Pool pool; pool.open(grnxx::io::POOL_TEMPORARY); @@ -510,6 +579,7 @@ int main() { test_defrag(); test_id_cursor(); + test_predictive_cursor(); test_prefix_cursor(); return 0; -------------- next part -------------- HTML����������������������������...Download