susumu.yata
null+****@clear*****
Fri Mar 22 13:08:07 JST 2013
susumu.yata 2013-03-22 13:08:07 +0900 (Fri, 22 Mar 2013) New Revision: 80167e071f8cf6fb1cbee68e68e2842209bfb8dd https://github.com/groonga/grnxx/commit/80167e071f8cf6fb1cbee68e68e2842209bfb8dd Message: Add cursor implementations for grnxx::map::da::large::Trie. Added files: lib/map/da/large/id_cursor.cpp lib/map/da/large/id_cursor.hpp lib/map/da/large/key_cursor.cpp lib/map/da/large/key_cursor.hpp lib/map/da/large/predictive_cursor.cpp lib/map/da/large/predictive_cursor.hpp lib/map/da/large/prefix_cursor.cpp lib/map/da/large/prefix_cursor.hpp Modified files: lib/map/da/large/Makefile.am lib/map/da/large/trie.cpp lib/map/da/large/trie.hpp test/test_map_da_large_trie.cpp Modified: lib/map/da/large/Makefile.am (+8 -0) =================================================================== --- lib/map/da/large/Makefile.am 2013-03-22 12:58:39 +0900 (c24fd63) +++ lib/map/da/large/Makefile.am 2013-03-22 13:08:07 +0900 (08de744) @@ -3,8 +3,16 @@ noinst_LTLIBRARIES = libgrnxx_map_da_large.la libgrnxx_map_da_large_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_map_da_large_la_SOURCES = \ + id_cursor.cpp \ + key_cursor.cpp \ + predictive_cursor.cpp \ + prefix_cursor.cpp \ trie.cpp libgrnxx_map_da_large_includedir = ${includedir}/grnxx/map/da/large libgrnxx_map_da_large_include_HEADERS = \ + id_cursor.hpp \ + key_cursor.hpp \ + predictive_cursor.hpp \ + prefix_cursor.hpp \ trie.hpp Added: lib/map/da/large/id_cursor.cpp (+90 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/id_cursor.cpp 2013-03-22 13:08:07 +0900 (f1c9e59) @@ -0,0 +1,90 @@ +#include "map/da/large/id_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace large { + +IDCursor::~IDCursor() {} + +IDCursor *IDCursor::open(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) { + std::unique_ptr<IDCursor> cursor(new (std::nothrow) IDCursor); + if (!cursor) { + GRNXX_ERROR() << "new grnxx::map::da::large::IDCursor failed"; + GRNXX_THROW(); + } + cursor->open_cursor(trie, flags, min, max, offset, limit); + return cursor.release(); +} + +bool IDCursor::next() { + if (limit_ <= 0) { + return false; + } + while (current_ != end_) { + const Entry entry = trie_->entries_[current_]; + if (entry) { + key_id_ = current_; + key_ = trie_->get_key(entry.key_pos()).slice(entry.key_size()); + current_ += step_; + --limit_; + return true; + } + current_ += step_; + } + return false; +} + +IDCursor::IDCursor() + : MapCursor(), + trie_(), + current_(), + end_(), + step_(), + limit_() {} + +void IDCursor::open_cursor(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) { + trie_ = trie; + + if (min < 0) { + min = 0; + } else if (flags & MAP_CURSOR_EXCEPT_MIN) { + ++min; + } + + if ((max < 0) || (max > trie->header_->max_key_id)) { + max = trie->header_->max_key_id; + } else if (flags & MAP_CURSOR_EXCEPT_MAX) { + --max; + } + + if (flags & MAP_CURSOR_DESCENDING) { + current_ = max; + end_ = min - 1; + step_ = -1; + } else { + current_ = min; + end_ = max + 1; + step_ = 1; + } + + while ((current_ != end_) && (offset > 0)) { + if (trie->entries_[current_]) { + --offset; + } + current_ += step_; + } + limit_ = (limit >= 0) ? limit : std::numeric_limits<int64_t>::max(); +} + +} // namespace large +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/large/id_cursor.hpp (+57 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/id_cursor.hpp 2013-03-22 13:08:07 +0900 (4354999) @@ -0,0 +1,57 @@ +/* + 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_LARGE_ID_CURSOR_HPP +#define GRNXX_MAP_DA_LARGE_ID_CURSOR_HPP + +#include "map/da/large/trie.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace large { + +class IDCursor : public MapCursor { + public: + ~IDCursor(); + + static IDCursor *open(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit); + + bool next(); + + private: + Trie *trie_; + int64_t current_; + int64_t end_; + int64_t step_; + int64_t limit_; + + IDCursor(); + + void open_cursor(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit); +}; + +} // namespace large +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_LARGE_ID_CURSOR_HPP Added: lib/map/da/large/key_cursor.cpp (+292 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/key_cursor.cpp 2013-03-22 13:08:07 +0900 (8395193) @@ -0,0 +1,292 @@ +#include "map/da/large/key_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace large { +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::large::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); + } +} + +// TODO: std::vector::push_back() may throw an exception. +void KeyCursor::ascending_init(const Slice &min, const Slice &max) { + if (max) { + has_end_ = true; + end_ = String(reinterpret_cast<const char *>(max.ptr()), max.size()); + } + + if (!min) { + 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(node.key_size()).compare(min, i); + if ((result > 0) || + ((result == 0) && (~flags_ & MAP_CURSOR_EXCEPT_MIN))) { + node_ids_.push_back(node_id); + } else if (node.has_sibling()) { + node_ids_.push_back(node_id ^ node.label() ^ + trie_->siblings_[node_id]); + } + return; + } else if (node.has_sibling()) { + node_ids_.push_back(node_id ^ node.label() ^ trie_->siblings_[node_id]); + } + + 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].has_sibling() ? + trie_->siblings_[node.offset() ^ label] : INVALID_LABEL; + } + while (label != INVALID_LABEL) { + if (label > min[i]) { + node_ids_.push_back(node.offset() ^ label); + break; + } + label = trie_->nodes_[node.offset() ^ label].has_sibling() ? + trie_->siblings_[node.offset() ^ label] : INVALID_LABEL; + } + return; + } + } + + node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + if ((node.key_size() != min.size()) || (~flags_ & MAP_CURSOR_EXCEPT_MIN)) { + node_ids_.push_back(node_id); + } else if (node.has_sibling()) { + node_ids_.push_back(node_id ^ node.label() ^ trie_->siblings_[node_id]); + } + return; + } else if (node.has_sibling()) { + node_ids_.push_back(node_id ^ node.label() ^ trie_->siblings_[node_id]); + } + + uint16_t label = node.child(); + if ((label == TERMINAL_LABEL) && (flags_ & MAP_CURSOR_EXCEPT_MIN)) { + label = trie_->nodes_[node.offset() ^ label].has_sibling() ? + trie_->siblings_[node.offset() ^ label] : INVALID_LABEL; + } + if (label != INVALID_LABEL) { + node_ids_.push_back(node.offset() ^ label); + } +} + +// TODO: std::vector::push_back() may throw an exception. +void KeyCursor::descending_init(const Slice &min, const Slice &max) { + if (min) { + has_end_ = true; + end_ = String(reinterpret_cast<const char *>(min.ptr()), min.size()); + } + + if (!max) { + 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(node.key_size()).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].has_sibling() ? + trie_->siblings_[node_id] : INVALID_LABEL; + } + 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].has_sibling() ? + trie_->siblings_[node_id] : INVALID_LABEL; + } + if (label == INVALID_LABEL) { + return; + } + } + + const Node node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + if ((node.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); + } +} + +// TODO: std::vector::push_back() may throw an exception. +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.has_sibling()) { + node_ids_.push_back(node_id ^ node.label() ^ trie_->siblings_[node_id]); + } + + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if (has_end_) { + const int result = key.slice(node.key_size()).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(node.key_size()); + --limit_; + return true; + } + } else if (node.child() != INVALID_LABEL) { + node_ids_.push_back(node.offset() ^ node.child()); + } + } + return false; +} + +// TODO: std::vector::push_back() may throw an exception. +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(node.key_size()).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(node.key_size()); + --limit_; + return true; + } + } + } else { + node_ids_.back() |= POST_ORDER_FLAG; + if (!node.is_leaf()) { + 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].has_sibling() ? + trie_->siblings_[node.offset() ^ label] : INVALID_LABEL; + } + } + } + } + return false; +} + +} // namespace large +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/large/key_cursor.hpp (+68 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/key_cursor.hpp 2013-03-22 13:08:07 +0900 (dedd5a5) @@ -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_LARGE_KEY_CURSOR_HPP +#define GRNXX_MAP_DA_LARGE_KEY_CURSOR_HPP + +#include "map/da/large/trie.hpp" +#include "string.hpp" + +#include <vector> + +namespace grnxx { +namespace map { +namespace da { +namespace large { + +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 large +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_LARGE_KEY_CURSOR_HPP Added: lib/map/da/large/predictive_cursor.cpp (+177 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/predictive_cursor.cpp 2013-03-22 13:08:07 +0900 (5202f76) @@ -0,0 +1,177 @@ +#include "map/da/large/predictive_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace large { +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::large::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 ((node.key_size() >= min_size_) && + (key.slice(node.key_size()).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.has_sibling())) { + node_ids_.push_back(node_id ^ node.label() ^ trie_->siblings_[node_id]); + } + + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if (node.key_size() >= min_size_) { + if (offset_ > 0) { + --offset_; + } else if (limit_ != 0) { + key_id_ = key.id(); + key_ = key.slice(node.key_size()); + --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 (node.key_size() >= min_size_) { + if (offset_ > 0) { + --offset_; + } else if (limit_ != 0) { + key_id_ = key.id(); + key_ = key.slice(node.key_size()); + --limit_; + return true; + } + } + } + } else { + node_ids_.back() |= POST_ORDER_FLAG; + if (!node.is_leaf()) { + 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].has_sibling() ? + trie_->siblings_[node.offset() ^ label] : INVALID_LABEL; + } + } + } + } + return false; +} catch (...) { + // TODO: Catch only std::vector's exception. + GRNXX_ERROR() << "std::vector::push_back() failed"; + GRNXX_THROW(); +} + +} // namespace large +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/large/predictive_cursor.hpp (+62 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/predictive_cursor.hpp 2013-03-22 13:08:07 +0900 (423f215) @@ -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_LARGE_PREDICTIVE_CURSOR_HPP +#define GRNXX_MAP_DA_LARGE_PREDICTIVE_CURSOR_HPP + +#include "map/da/large/trie.hpp" + +#include <vector> + +namespace grnxx { +namespace map { +namespace da { +namespace large { + +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 large +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_LARGE_PREDICTIVE_CURSOR_HPP Added: lib/map/da/large/prefix_cursor.cpp (+130 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/prefix_cursor.cpp 2013-03-22 13:08:07 +0900 (8a2e642) @@ -0,0 +1,130 @@ +#include "map/da/large/prefix_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace large { + +PrefixCursor::~PrefixCursor() {} + +PrefixCursor *PrefixCursor::open(Trie *trie, MapCursorFlags flags, + size_t min, const Slice &max, + int64_t offset, int64_t limit) { + std::unique_ptr<PrefixCursor> cursor(new (std::nothrow) PrefixCursor); + if (!cursor) { + GRNXX_ERROR() << "new grnxx::map::da::large::PrefixCursor failed"; + GRNXX_THROW(); + } + cursor->open_cursor(trie, flags, min, max, offset, limit); + return cursor.release(); +} + +bool PrefixCursor::next() { + if (current_ == end_) { + return false; + } + const Key &key = trie_->get_key(nodes_[current_].key_pos()); + key_id_ = key.id(); + key_ = key.slice(nodes_[current_].key_size()); + current_ += step_; + return true; +} + +PrefixCursor::PrefixCursor() + : MapCursor(), + trie_(), + nodes_(), + current_(), + end_(), + step_() {} + +void PrefixCursor::open_cursor(Trie *trie, MapCursorFlags flags, + size_t min, const Slice &max, + int64_t offset, int64_t limit) try { + trie_ = trie; + + if (flags & MAP_CURSOR_EXCEPT_MIN) { + ++min; + } + + Slice query = max; + if ((max.size() > 0) && (flags & MAP_CURSOR_EXCEPT_MAX)) { + query.remove_suffix(1); + } + + if (limit < 0) { + limit = std::numeric_limits<int64_t>::max(); + } + + uint64_t node_id = ROOT_NODE_ID; + size_t i; + for (i = 0; i < query.size(); ++i) { + const Node node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if ((node.key_size() >= min) && (node.key_size() <= query.size()) && + key.equals_to(query.prefix(node.key_size()), node.key_size(), i)) { + nodes_.push_back(node); + } + break; + } + + if ((i >= min) && + (trie_->nodes_[node_id].child() == TERMINAL_LABEL)) { + const Node leaf_node = trie_->nodes_[node.offset() ^ TERMINAL_LABEL]; + if (leaf_node.is_leaf()) { + nodes_.push_back(leaf_node); + } + } + + node_id = node.offset() ^ query[i]; + if (trie_->nodes_[node_id].label() != query[i]) { + break; + } + } + + if (i == query.size()) { + const Node node = trie_->nodes_[node_id]; + if (node.is_leaf()) { + const Key &key = trie_->get_key(node.key_pos()); + if ((node.key_size() >= min) && (node.key_size() <= query.size())) { + nodes_.push_back(node); + } + } else if (trie_->nodes_[node_id].child() == TERMINAL_LABEL) { + const Node leaf_node = trie_->nodes_[node.offset() ^ TERMINAL_LABEL]; + if (leaf_node.is_leaf()) { + nodes_.push_back(leaf_node); + } + } + } + + if (offset >= static_cast<int64_t>(nodes_.size())) { + current_ = end_ = 0; + } else if (flags & MAP_CURSOR_DESCENDING) { + current_ = nodes_.size() - offset - 1; + end_ = -1; + if (limit < (current_ - end_)) { + end_ = current_ - limit; + } + step_ = -1; + } else { + current_ = offset; + end_ = nodes_.size(); + if (limit < (end_ - current_)) { + end_ = current_ + limit; + } + step_ = 1; + } +} catch (...) { + // TODO: Catch only std::vector's exception. + GRNXX_ERROR() << "std::vector::push_back() failed"; + GRNXX_THROW(); +} + +} // namespace large +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/large/prefix_cursor.hpp (+59 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/prefix_cursor.hpp 2013-03-22 13:08:07 +0900 (02d7fbf) @@ -0,0 +1,59 @@ +/* + 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_LARGE_PREFIX_CURSOR_HPP +#define GRNXX_MAP_DA_LARGE_PREFIX_CURSOR_HPP + +#include "map/da/large/trie.hpp" + +#include <vector> + +namespace grnxx { +namespace map { +namespace da { +namespace large { + +class PrefixCursor : public MapCursor { + public: + ~PrefixCursor(); + + static PrefixCursor *open(Trie *trie, MapCursorFlags flags, + size_t min, const Slice &max, + int64_t offset, int64_t limit); + + bool next(); + + private: + Trie *trie_; + std::vector<Node> nodes_; + int64_t current_; + int64_t end_; + int64_t step_; + + PrefixCursor(); + + void open_cursor(Trie *trie, MapCursorFlags flags, + size_t min, const Slice &max, + int64_t offset, int64_t limit); +}; + +} // namespace large +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_LARGE_PREFIX_CURSOR_HPP Modified: lib/map/da/large/trie.cpp (+8 -8) =================================================================== --- lib/map/da/large/trie.cpp 2013-03-22 12:58:39 +0900 (c5d4ab1) +++ lib/map/da/large/trie.cpp 2013-03-22 13:08:07 +0900 (b9e61f8) @@ -2,6 +2,10 @@ #include "lock.hpp" #include "logger.hpp" +#include "map/da/large/id_cursor.hpp" +#include "map/da/large/key_cursor.hpp" +#include "map/da/large/predictive_cursor.hpp" +#include "map/da/large/prefix_cursor.hpp" namespace grnxx { namespace map { @@ -352,29 +356,25 @@ bool Trie::update(const Slice &src_key, const Slice &dest_key, MapCursor *Trie::open_id_cursor(MapCursorFlags flags, int64_t min, int64_t max, int64_t offset, int64_t limit) { - // TODO - return nullptr; + return IDCursor::open(this, flags, min, max, offset, limit); } 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, size_t min, const Slice &max, int64_t offset, int64_t limit) { - // TODO - return nullptr; + return PrefixCursor::open(this, flags, min, max, offset, limit); } 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/large/trie.hpp (+10 -0) =================================================================== --- lib/map/da/large/trie.hpp 2013-03-22 12:58:39 +0900 (896c1a8) +++ lib/map/da/large/trie.hpp 2013-03-22 13:08:07 +0900 (ce80699) @@ -410,7 +410,17 @@ class Key { uint8_t buf_[3]; }; +class IDCursor; +class KeyCursor; +class PredictiveCursor; +class PrefixCursor; + class Trie : public da::Trie { + friend class IDCursor; + friend class KeyCursor; + friend class PredictiveCursor; + friend class PrefixCursor; + public: ~Trie(); Modified: test/test_map_da_large_trie.cpp (+309 -0) =================================================================== --- test/test_map_da_large_trie.cpp 2013-03-22 12:58:39 +0900 (864e2b6) +++ test/test_map_da_large_trie.cpp 2013-03-22 13:08:07 +0900 (d7b1d44) @@ -395,6 +395,310 @@ void test_cross_defrag() { } } +void test_id_cursor() { + constexpr std::size_t NUM_KEYS = 1 << 12; + constexpr std::size_t MIN_SIZE = 1; + constexpr std::size_t MAX_SIZE = 10; + + grnxx::io::Pool pool; + pool.open(grnxx::io::POOL_TEMPORARY); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::large::Trie> trie( + grnxx::map::da::large::Trie::create(options, pool)); + + std::unordered_set<std::string> both_keys; + std::vector<grnxx::Slice> true_keys; + std::vector<grnxx::Slice> false_keys; + create_keys(NUM_KEYS, MIN_SIZE, MAX_SIZE, + &both_keys, &true_keys, &false_keys); + + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + std::int64_t key_id; + assert(trie->insert(true_keys[i], &key_id)); + assert(key_id == static_cast<std::int64_t>(i)); + } + + std::unique_ptr<grnxx::MapCursor> cursor( + trie->open_id_cursor(grnxx::MapCursorFlags(), 0, -1, 0, -1)); + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(cursor->next()); + assert(cursor->key_id() == static_cast<std::int64_t>(i)); + assert(cursor->key() == true_keys[i]); + } + assert(!cursor->next()); + + cursor.reset(trie->open_id_cursor( + grnxx::MapCursorFlags(), 0, -1, NUM_KEYS / 2, -1)); + for (std::size_t i = NUM_KEYS / 2; i < NUM_KEYS; ++i) { + assert(cursor->next()); + assert(cursor->key_id() == static_cast<std::int64_t>(i)); + assert(cursor->key() == true_keys[i]); + } + assert(!cursor->next()); + + cursor.reset(trie->open_id_cursor( + grnxx::MapCursorFlags(), 0, -1, 0, NUM_KEYS / 2)); + for (std::size_t i = 0; i < NUM_KEYS / 2; ++i) { + assert(cursor->next()); + assert(cursor->key_id() == static_cast<std::int64_t>(i)); + assert(cursor->key() == true_keys[i]); + } + assert(!cursor->next()); + + cursor.reset(trie->open_id_cursor( + grnxx::MAP_CURSOR_DESCENDING, 0, -1, 0, -1)); + for (std::size_t i = 0; i < NUM_KEYS; ++i) { + assert(cursor->next()); + assert(cursor->key_id() == static_cast<std::int64_t>(NUM_KEYS - i - 1)); + assert(cursor->key() == true_keys[NUM_KEYS - i - 1]); + } + assert(!cursor->next()); + + cursor.reset(trie->open_id_cursor( + grnxx::MAP_CURSOR_EXCEPT_MIN, 0, 1, 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 1); + assert(!cursor->next()); + + cursor.reset(trie->open_id_cursor( + grnxx::MAP_CURSOR_EXCEPT_MAX, 2, 3, 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 2); + 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::large::Trie> trie( + grnxx::map::da::large::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); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::large::Trie> trie( + grnxx::map::da::large::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); + + grnxx::map::da::TrieOptions options; + std::unique_ptr<grnxx::map::da::large::Trie> trie( + grnxx::map::da::large::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("01234"); + + 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_prefix_cursor(grnxx::MapCursorFlags(), 0, "01234", 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_prefix_cursor( + grnxx::MapCursorFlags(), 0, "01", 0, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 0); + assert(cursor->next()); + assert(cursor->key_id() == 1); + assert(!cursor->next()); + + cursor.reset(trie->open_prefix_cursor( + grnxx::MapCursorFlags(), 0, "01234", 3, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(cursor->next()); + assert(cursor->key_id() == 4); + assert(!cursor->next()); + + cursor.reset(trie->open_prefix_cursor( + grnxx::MapCursorFlags(), 0, "01234", 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_prefix_cursor( + grnxx::MAP_CURSOR_DESCENDING, 0, "01234", 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_prefix_cursor( + grnxx::MAP_CURSOR_EXCEPT_MIN, 1, "01234", 0, 2)); + assert(cursor->next()); + assert(cursor->key_id() == 1); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(!cursor->next()); + + cursor.reset(trie->open_prefix_cursor( + grnxx::MAP_CURSOR_EXCEPT_MAX, 0, "01234", 2, -1)); + assert(cursor->next()); + assert(cursor->key_id() == 2); + assert(cursor->next()); + assert(cursor->key_id() == 3); + assert(!cursor->next()); +} + int main() { grnxx::Logger::set_flags(grnxx::LOGGER_WITH_ALL | grnxx::LOGGER_ENABLE_COUT); @@ -410,5 +714,10 @@ int main() { test_defrag(); test_cross_defrag(); + test_id_cursor(); + test_key_cursor(); + test_predictive_cursor(); + test_prefix_cursor(); + return 0; } -------------- next part -------------- HTML����������������������������...Download