diff options
Diffstat (limited to '')
-rw-r--r-- | storage/mroonga/vendor/groonga/lib/dat/prefix-cursor.cpp | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/storage/mroonga/vendor/groonga/lib/dat/prefix-cursor.cpp b/storage/mroonga/vendor/groonga/lib/dat/prefix-cursor.cpp new file mode 100644 index 00000000..83adeb37 --- /dev/null +++ b/storage/mroonga/vendor/groonga/lib/dat/prefix-cursor.cpp @@ -0,0 +1,175 @@ +/* -*- c-basic-offset: 2 -*- */ +/* Copyright(C) 2011 Brazil + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License version 2.1 as published by the Free Software Foundation. + + 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-1335 USA +*/ + +#include "prefix-cursor.hpp" + +#include <algorithm> + +#include "trie.hpp" + +namespace grn { +namespace dat { + +PrefixCursor::PrefixCursor() + : trie_(NULL), + offset_(0), + limit_(MAX_UINT32), + flags_(PREFIX_CURSOR), + buf_(), + cur_(0), + end_(0) {} + +PrefixCursor::~PrefixCursor() {} + +void PrefixCursor::open(const Trie &trie, + const String &str, + UInt32 min_length, + UInt32 offset, + UInt32 limit, + UInt32 flags) { + GRN_DAT_THROW_IF(PARAM_ERROR, (str.ptr() == NULL) && (str.length() != 0)); + GRN_DAT_THROW_IF(PARAM_ERROR, min_length > str.length()); + + flags = fix_flags(flags); + PrefixCursor new_cursor(trie, offset, limit, flags); + new_cursor.init(str, min_length); + new_cursor.swap(this); +} + +void PrefixCursor::close() { + PrefixCursor new_cursor; + new_cursor.swap(this); +} + +const Key &PrefixCursor::next() { + if (cur_ == end_) { + return Key::invalid_key(); + } + if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) { + return trie_->get_key(buf_[cur_++]); + } else { + return trie_->get_key(buf_[--cur_]); + } +} + +PrefixCursor::PrefixCursor(const Trie &trie, + UInt32 offset, UInt32 limit, UInt32 flags) + : trie_(&trie), + offset_(offset), + limit_(limit), + flags_(flags), + buf_(), + cur_(0), + end_(0) {} + +UInt32 PrefixCursor::fix_flags(UInt32 flags) const { + const UInt32 cursor_type = flags & CURSOR_TYPE_MASK; + GRN_DAT_THROW_IF(PARAM_ERROR, (cursor_type != 0) && + (cursor_type != PREFIX_CURSOR)); + flags |= PREFIX_CURSOR; + + const UInt32 cursor_order = flags & CURSOR_ORDER_MASK; + GRN_DAT_THROW_IF(PARAM_ERROR, (cursor_order != 0) && + (cursor_order != ASCENDING_CURSOR) && + (cursor_order != DESCENDING_CURSOR)); + if (cursor_order == 0) { + flags |= ASCENDING_CURSOR; + } + + const UInt32 cursor_options = flags & CURSOR_OPTIONS_MASK; + GRN_DAT_THROW_IF(PARAM_ERROR, cursor_options & ~EXCEPT_EXACT_MATCH); + + return flags; +} + +void PrefixCursor::init(const String &str, UInt32 min_length) { + if ((limit_ == 0) || (offset_ > (str.length() - min_length))) { + return; + } + + UInt32 node_id = ROOT_NODE_ID; + UInt32 i; + for (i = 0; i < str.length(); ++i) { + const Base base = trie_->ith_node(node_id).base(); + if (base.is_linker()) { + const Key &key = trie_->get_key(base.key_pos()); + if ((key.length() >= min_length) && (key.length() <= str.length()) && + (str.substr(0, key.length()).compare(key.str(), i) == 0) && + ((key.length() < str.length()) || + ((flags_ & EXCEPT_EXACT_MATCH) != EXCEPT_EXACT_MATCH))) { + buf_.push_back(base.key_pos()); + } + break; + } + + if ((i >= min_length) && + (trie_->ith_node(node_id).child() == TERMINAL_LABEL)) { + const Base linker_base = + trie_->ith_node(base.offset() ^ TERMINAL_LABEL).base(); + if (linker_base.is_linker()) { + buf_.push_back(linker_base.key_pos()); + } + } + + node_id = base.offset() ^ str[i]; + if (trie_->ith_node(node_id).label() != str[i]) { + break; + } + } + + if ((i == str.length()) && + ((flags_ & EXCEPT_EXACT_MATCH) != EXCEPT_EXACT_MATCH)) { + const Base base = trie_->ith_node(node_id).base(); + if (base.is_linker()) { + const Key &key = trie_->get_key(base.key_pos()); + if ((key.length() >= min_length) && (key.length() <= str.length())) { + buf_.push_back(base.key_pos()); + } + } else if (trie_->ith_node(node_id).child() == TERMINAL_LABEL) { + const Base linker_base = + trie_->ith_node(base.offset() ^ TERMINAL_LABEL).base(); + if (linker_base.is_linker()) { + buf_.push_back(linker_base.key_pos()); + } + } + } + + if (buf_.size() <= offset_) { + return; + } + + if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) { + cur_ = offset_; + end_ = (limit_ < (buf_.size() - cur_)) ? (cur_ + limit_) : buf_.size(); + } else { + cur_ = buf_.size() - offset_; + end_ = (limit_ < cur_) ? (cur_ - limit_) : 0; + } +} + +void PrefixCursor::swap(PrefixCursor *cursor) { + std::swap(trie_, cursor->trie_); + std::swap(offset_, cursor->offset_); + std::swap(limit_, cursor->limit_); + std::swap(flags_, cursor->flags_); + buf_.swap(&cursor->buf_); + std::swap(cur_, cursor->cur_); + std::swap(end_, cursor->end_); +} + +} // namespace dat +} // namespace grn |