susumu.yata
null+****@clear*****
Fri Mar 15 16:30:39 JST 2013
susumu.yata 2013-03-15 16:30:39 +0900 (Fri, 15 Mar 2013) New Revision: abe47d1f2646c3473f13571afbb4c107dcdcd9d3 https://github.com/groonga/grnxx/commit/abe47d1f2646c3473f13571afbb4c107dcdcd9d3 Message: Add grnxx::map::da::basic::PrefixCursor. Added files: lib/map/da/basic/prefix_cursor.cpp lib/map/da/basic/prefix_cursor.hpp Modified files: lib/map/da/basic/Makefile.am lib/map/da/basic/trie.cpp lib/map/da/basic/trie.hpp Modified: lib/map/da/basic/Makefile.am (+2 -0) =================================================================== --- lib/map/da/basic/Makefile.am 2013-03-15 15:34:06 +0900 (f81070d) +++ lib/map/da/basic/Makefile.am 2013-03-15 16:30:39 +0900 (56ced41) @@ -4,9 +4,11 @@ libgrnxx_map_da_basic_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_map_da_basic_la_SOURCES = \ id_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 \ + prefix_cursor.hpp \ trie.hpp Added: lib/map/da/basic/prefix_cursor.cpp (+129 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/prefix_cursor.cpp 2013-03-15 16:30:39 +0900 (be95186) @@ -0,0 +1,129 @@ +#include "map/da/basic/prefix_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace basic { + +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::basic::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(key_positions_[current_]); + key_id_ = key.id(); + key_ = key.slice(); + current_ += step_; + return true; +} + +PrefixCursor::PrefixCursor() + : MapCursor(), + trie_(), + key_positions_(), + 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 ((key.size() >= min) && (key.size() <= query.size()) && + key.equals_to(query.prefix(key.size()), i)) { + key_positions_.push_back(node.key_pos()); + } + 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()) { + key_positions_.push_back(leaf_node.key_pos()); + } + } + + 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 ((key.size() >= min) && (key.size() <= query.size())) { + key_positions_.push_back(node.key_pos()); + } + } else if (trie_->nodes_[node_id].child() == TERMINAL_LABEL) { + const Node leaf_node = trie_->nodes_[node.offset() ^ TERMINAL_LABEL]; + if (leaf_node.is_leaf()) { + key_positions_.push_back(leaf_node.key_pos()); + } + } + } + + if (offset >= static_cast<int64_t>(key_positions_.size())) { + current_ = end_ = 0; + } else if (flags & MAP_CURSOR_DESCENDING) { + current_ = key_positions_.size() - offset - 1; + end_ = -1; + if (limit < (current_ - end_)) { + end_ = current_ - limit; + } + step_ = -1; + } else { + current_ = offset; + end_ = key_positions_.size(); + if (limit < (end_ - current_)) { + end_ = current_ + limit; + } + step_ = 1; + } +} catch (...) { + GRNXX_ERROR() << "std::vector::push_back() failed"; + GRNXX_THROW(); +} + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/basic/prefix_cursor.hpp (+59 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/prefix_cursor.hpp 2013-03-15 16:30:39 +0900 (80f622f) @@ -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_BASIC_PREFIX_CURSOR_HPP +#define GRNXX_MAP_DA_BASIC_PREFIX_CURSOR_HPP + +#include "map/da/basic/trie.hpp" + +#include <vector> + +namespace grnxx { +namespace map { +namespace da { +namespace basic { + +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<uint64_t> key_positions_; + 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 basic +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_BASIC_PREFIX_CURSOR_HPP Modified: lib/map/da/basic/trie.cpp (+2 -2) =================================================================== --- lib/map/da/basic/trie.cpp 2013-03-15 15:34:06 +0900 (521cf5c) +++ lib/map/da/basic/trie.cpp 2013-03-15 16:30:39 +0900 (9ca07a1) @@ -3,6 +3,7 @@ #include "lock.hpp" #include "logger.hpp" #include "map/da/basic/id_cursor.hpp" +#include "map/da/basic/prefix_cursor.hpp" #include "map/da/large/trie.hpp" namespace grnxx { @@ -354,8 +355,7 @@ MapCursor *Trie::open_key_cursor(MapCursorFlags flags, 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, Modified: lib/map/da/basic/trie.hpp (+2 -0) =================================================================== --- lib/map/da/basic/trie.hpp 2013-03-15 15:34:06 +0900 (7acbc93) +++ lib/map/da/basic/trie.hpp 2013-03-15 16:30:39 +0900 (fb13876) @@ -87,6 +87,7 @@ constexpr uint32_t MAX_CHUNK_LEVEL = 5; constexpr uint32_t INVALID_LEADER = std::numeric_limits<uint32_t>::max(); class IDCursor; +class PrefixCursor; struct Header { TrieType type; @@ -421,6 +422,7 @@ class Key { class Trie : public da::Trie { friend class large::Trie; friend class IDCursor; + friend class PrefixCursor; public: ~Trie(); -------------- next part -------------- HTML����������������������������...Download