susumu.yata
null+****@clear*****
Fri Mar 22 10:50:45 JST 2013
susumu.yata 2013-03-22 10:50:45 +0900 (Fri, 22 Mar 2013) New Revision: 1d9ecfddabe167d74a84bbcd0707b5fa4567070e https://github.com/groonga/grnxx/commit/1d9ecfddabe167d74a84bbcd0707b5fa4567070e Message: Add grnxx::map::da::basic::KeyCursor. Added files: lib/map/da/basic/key_cursor.cpp lib/map/da/basic/key_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-22 10:41:25 +0900 (f146755) +++ lib/map/da/basic/Makefile.am 2013-03-22 10:50:45 +0900 (9a0680d) @@ -4,6 +4,7 @@ libgrnxx_map_da_basic_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_map_da_basic_la_SOURCES = \ id_cursor.cpp \ + key_cursor.cpp \ predictive_cursor.cpp \ prefix_cursor.cpp \ trie.cpp @@ -11,6 +12,7 @@ libgrnxx_map_da_basic_la_SOURCES = \ libgrnxx_map_da_basic_includedir = ${includedir}/grnxx/map/da/basic libgrnxx_map_da_basic_include_HEADERS = \ id_cursor.hpp \ + key_cursor.hpp \ predictive_cursor.hpp \ prefix_cursor.hpp \ trie.hpp Added: lib/map/da/basic/key_cursor.cpp (+281 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/key_cursor.cpp 2013-03-22 10:50:45 +0900 (2fec9fe) @@ -0,0 +1,281 @@ +#include "map/da/basic/key_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace basic { +namespace { + +constexpr uint64_t POST_ORDER_FLAG = uint64_t(1) << 63; + +} // namespace + +KeyCursor::~KeyCursor() {} + +KeyCursor *KeyCursor::open(Trie *trie, MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit) { + std::unique_ptr<KeyCursor> cursor(new (std::nothrow) KeyCursor); + if (!cursor) { + GRNXX_ERROR() << "new grnxx::map::da::basic::KeyCursor failed"; + GRNXX_THROW(); + } + cursor->open_cursor(trie, flags, min, max, offset, limit); + return cursor.release(); +} + +bool KeyCursor::next() { + if (limit_ == 0) { + return false; + } + + if (flags_ & MAP_CURSOR_DESCENDING) { + return descending_next(); + } else { + return ascending_next(); + } +} + + Trie *trie_; + std::vector<uint64_t> node_ids_; + int64_t offset_; + int64_t limit_; + MapCursorFlags flags_; + +KeyCursor::KeyCursor() + : MapCursor(), + trie_(), + node_ids_(), + offset_(), + limit_(), + flags_(), + has_end_(), + end_() {} + +void KeyCursor::open_cursor(Trie *trie, MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit) { + trie_ = trie; + offset_ = offset; + limit_ = (limit >= 0) ? limit : std::numeric_limits<int64_t>::max(); + flags_ = flags; + + if (flags & MAP_CURSOR_DESCENDING) { + descending_init(min, max); + } else { + ascending_init(min, max); + } +} + +void KeyCursor::ascending_init(const Slice &min, const Slice &max) { + if (max.ptr() && (max.size() != 0)) { + has_end_ = true; + end_ = String(reinterpret_cast<const char *>(max.ptr()), max.size()); + } + + if (!min.ptr() || (min.size() == 0)) { + node_ids_.push_back(ROOT_NODE_ID); + return; + } + + uint64_t node_id = ROOT_NODE_ID; + Node node; + for (size_t i = 0; i < min.size(); ++i) { + node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + const int result = key.slice().compare(min, i); + if ((result > 0) || + ((result == 0) && (~flags_ & MAP_CURSOR_EXCEPT_MIN))) { + node_ids_.push_back(node_id); + } else if (node.sibling() != INVALID_LABEL) { + node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); + } + return; + } else if (node.sibling() != INVALID_LABEL) { + node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); + } + + node_id = node.offset() ^ min[i]; + if (trie_->nodes_[node_id].label() != min[i]) { + uint16_t label = node.child(); + if (label == TERMINAL_LABEL) { + label = trie_->nodes_[node.offset() ^ label].sibling(); + } + while (label != INVALID_LABEL) { + if (label > min[i]) { + node_ids_.push_back(node.offset() ^ label); + break; + } + label = trie_->nodes_[node.offset() ^ label].sibling(); + } + return; + } + } + + node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if ((key.size() != min.size()) || (~flags_ & MAP_CURSOR_EXCEPT_MIN)) { + node_ids_.push_back(node_id); + } else if (node.sibling() != INVALID_LABEL) { + node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); + } + return; + } else if (node.sibling() != INVALID_LABEL) { + node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); + } + + uint16_t label = node.child(); + if ((label == TERMINAL_LABEL) && (flags_ & MAP_CURSOR_EXCEPT_MIN)) { + label = trie_->nodes_[node.offset() ^ label].sibling(); + } + if (label != INVALID_LABEL) { + node_ids_.push_back(node.offset() ^ label); + } +} + +void KeyCursor::descending_init(const Slice &min, const Slice &max) { + if (min.ptr() && (min.size() != 0)) { + has_end_ = true; + end_ = String(reinterpret_cast<const char *>(min.ptr()), min.size()); + } + + if (!max.ptr() || (max.size() == 0)) { + node_ids_.push_back(ROOT_NODE_ID); + return; + } + + uint64_t node_id = ROOT_NODE_ID; + for (size_t i = 0; i < max.size(); ++i) { + const Node node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + const int result = key.slice().compare(max, i); + if ((result < 0) || + ((result == 0) && (~flags_ & MAP_CURSOR_EXCEPT_MAX))) { + node_ids_.push_back(node_id | POST_ORDER_FLAG); + } + return; + } + + uint16_t label = trie_->nodes_[node_id].child(); + if (label == TERMINAL_LABEL) { + node_id = node.offset() ^ label; + node_ids_.push_back(node_id | POST_ORDER_FLAG); + label = trie_->nodes_[node_id].sibling(); + } + while (label != INVALID_LABEL) { + node_id = node.offset() ^ label; + if (label < max[i]) { + node_ids_.push_back(node_id); + } else if (label > max[i]) { + return; + } else { + break; + } + label = trie_->nodes_[node_id].sibling(); + } + if (label == INVALID_LABEL) { + return; + } + } + + const Node node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if ((key.size() == max.size()) && (~flags_ & MAP_CURSOR_EXCEPT_MAX)) { + node_ids_.push_back(node_id | POST_ORDER_FLAG); + } + return; + } + + uint16_t label = trie_->nodes_[node_id].child(); + if ((label == TERMINAL_LABEL) && (~flags_ & MAP_CURSOR_EXCEPT_MAX)) { + node_ids_.push_back((node.offset() ^ label) | POST_ORDER_FLAG); + } +} + +bool KeyCursor::ascending_next() { + while (!node_ids_.empty()) { + const uint64_t node_id = node_ids_.back(); + node_ids_.pop_back(); + + const Node node = trie_->nodes_[node_id]; + if (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 (has_end_) { + const int result = + key.slice().compare(Slice(end_.c_str(), end_.length())); + if ((result > 0) || + ((result == 0) && (flags_ & MAP_CURSOR_EXCEPT_MAX))) { + limit_ = 0; + return false; + } + } + 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; +} + +bool KeyCursor::descending_next() { + 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 (has_end_) { + const int result = + key.slice().compare(Slice(end_.c_str(), end_.length())); + if ((result < 0) || + ((result == 0) && (flags_ & MAP_CURSOR_EXCEPT_MIN))) { + limit_ = 0; + return false; + } + } + 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; + uint16_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; +} + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/basic/key_cursor.hpp (+68 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/key_cursor.hpp 2013-03-22 10:50:45 +0900 (8078a3d) @@ -0,0 +1,68 @@ +/* + 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_KEY_CURSOR_HPP +#define GRNXX_MAP_DA_BASIC_KEY_CURSOR_HPP + +#include "map/da/basic/trie.hpp" +#include "string.hpp" + +#include <vector> + +namespace grnxx { +namespace map { +namespace da { +namespace basic { + +class KeyCursor : public MapCursor { + public: + ~KeyCursor(); + + static KeyCursor *open(Trie *trie, MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit); + + bool next(); + + private: + Trie *trie_; + std::vector<uint64_t> node_ids_; + int64_t offset_; + int64_t limit_; + MapCursorFlags flags_; + bool has_end_; + String end_; + + KeyCursor(); + + void open_cursor(Trie *trie, MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit); + + void ascending_init(const Slice &min, const Slice &max); + void descending_init(const Slice &min, const Slice &max); + + bool ascending_next(); + bool descending_next(); +}; + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_BASIC_KEY_CURSOR_HPP Modified: lib/map/da/basic/trie.cpp (+2 -2) =================================================================== --- lib/map/da/basic/trie.cpp 2013-03-22 10:41:25 +0900 (6b521f9) +++ lib/map/da/basic/trie.cpp 2013-03-22 10:50:45 +0900 (fce8877) @@ -3,6 +3,7 @@ #include "lock.hpp" #include "logger.hpp" #include "map/da/basic/id_cursor.hpp" +#include "map/da/basic/key_cursor.hpp" #include "map/da/basic/predictive_cursor.hpp" #include "map/da/basic/prefix_cursor.hpp" #include "map/da/large/trie.hpp" @@ -349,8 +350,7 @@ MapCursor *Trie::open_id_cursor(MapCursorFlags flags, MapCursor *Trie::open_key_cursor(MapCursorFlags flags, const Slice &min, const Slice &max, int64_t offset, int64_t limit) { - // TODO - return nullptr; + return KeyCursor::open(this, flags, min, max, offset, limit); } MapCursor *Trie::open_prefix_cursor(MapCursorFlags flags, Modified: lib/map/da/basic/trie.hpp (+2 -0) =================================================================== --- lib/map/da/basic/trie.hpp 2013-03-22 10:41:25 +0900 (927dcdd) +++ lib/map/da/basic/trie.hpp 2013-03-22 10:50:45 +0900 (7c110bb) @@ -417,12 +417,14 @@ class Key { }; class IDCursor; +class KeyCursor; class PredictiveCursor; class PrefixCursor; class Trie : public da::Trie { friend class large::Trie; friend class IDCursor; + friend class KeyCursor; friend class PredictiveCursor; friend class PrefixCursor; Modified: test/test_map_da_basic_trie.cpp (+84 -0) =================================================================== --- test/test_map_da_basic_trie.cpp 2013-03-22 10:41:25 +0900 (614dd1f) +++ test/test_map_da_basic_trie.cpp 2013-03-22 10:50:45 +0900 (cf6ac1b) @@ -416,6 +416,89 @@ void test_id_cursor() { assert(!cursor->next()); } +void test_key_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("12"); + keys.push_back("123"); + keys.push_back("234"); + + 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_key_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_key_cursor( + grnxx::MapCursorFlags(), "01", "12", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 1); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(!cursor->next()); + + cursor.reset(trie->open_key_cursor( + grnxx::MapCursorFlags(), "00", "120", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 1); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(!cursor->next()); + + cursor.reset(trie->open_key_cursor( + grnxx::MapCursorFlags(), "01", "9", 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_key_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_key_cursor( + grnxx::MAP_CURSOR_DESCENDING, "01", "234", 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_key_cursor( + grnxx::MAP_CURSOR_EXCEPT_MIN, "12", "123", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(!cursor->next()); + + cursor.reset(trie->open_key_cursor( + grnxx::MAP_CURSOR_EXCEPT_MAX, "12", "123", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(!cursor->next()); +} + void test_predictive_cursor() { grnxx::io::Pool pool; pool.open(grnxx::io::POOL_TEMPORARY); @@ -579,6 +662,7 @@ int main() { test_defrag(); test_id_cursor(); + test_key_cursor(); test_predictive_cursor(); test_prefix_cursor(); -------------- next part -------------- HTML����������������������������...Download