null+****@clear*****
null+****@clear*****
2011年 6月 28日 (火) 15:15:15 JST
Susumu Yata 2011-06-28 06:15:15 +0000 (Tue, 28 Jun 2011)
New Revision: 8f7d538c5ef4f7b81923e3fb27aa081c7f72c791
Log:
fixed bugs of grn::dat::CommonPrefixSearchCursor.
Modified files:
lib/dat/common-prefix-search-cursor.cpp
lib/dat/common-prefix-search-cursor.hpp
lib/dat/dat.hpp
lib/dat/trie.cpp
Modified: lib/dat/common-prefix-search-cursor.cpp (+49 -44)
===================================================================
--- lib/dat/common-prefix-search-cursor.cpp 2011-06-27 11:16:42 +0000 (85bf069)
+++ lib/dat/common-prefix-search-cursor.cpp 2011-06-28 06:15:15 +0000 (5712dad)
@@ -12,7 +12,8 @@ CommonPrefixSearchCursor::CommonPrefixSearchCursor()
limit_(UINT32_MAX),
flags_(COMMON_PREFIX_CURSOR),
buf_(),
- count_(0) {}
+ cur_(0),
+ end_(0) {}
CommonPrefixSearchCursor::~CommonPrefixSearchCursor() {
close();
@@ -40,17 +41,18 @@ void CommonPrefixSearchCursor::close() {
limit_ = UINT32_MAX;
flags_ = COMMON_PREFIX_CURSOR;
buf_.clear();
- count_ = 0;
+ cur_ = 0;
+ end_ = 0;
}
bool CommonPrefixSearchCursor::next(Key *key) {
- if (count_ >= buf_.size()) {
+ if (cur_ == end_) {
return false;
}
if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) {
- trie_->ith_key(buf_[count_++], key);
+ trie_->ith_key(buf_[cur_++], key);
} else {
- trie_->ith_key(buf_[buf_.size() - ++count_], key);
+ trie_->ith_key(buf_[--cur_], key);
}
return true;
}
@@ -84,7 +86,8 @@ CommonPrefixSearchCursor::CommonPrefixSearchCursor(const Trie &trie,
limit_(limit),
flags_(flags),
buf_(),
- count_(0) {}
+ cur_(0),
+ end_(0) {}
void CommonPrefixSearchCursor::init(const UInt8 *ptr,
UInt32 min_length,
@@ -94,61 +97,62 @@ void CommonPrefixSearchCursor::init(const UInt8 *ptr,
}
UInt32 node_id = ROOT_NODE_ID;
- UInt32 skip_count = 0;
- for (UInt32 i = 0; i < max_length; ++i) {
+ UInt32 i;
+ for (i = 0; i < max_length; ++i) {
const Base base = trie_->ith_node(node_id).base();
if (base.is_terminal()) {
Key key;
trie_->ith_key(base.key_id(), &key);
if ((key.length() >= min_length) && (key.length() <= max_length) &&
- (std::memcmp(ptr + i, key.ptr() + i, key.length() - i) == 0)) {
- if (skip_count < offset_) {
- ++skip_count;
- } else {
- buf_.push_back(key.id());
- }
+ (std::memcmp(ptr + i, key.ptr() + i, key.length() - i) == 0) &&
+ ((key.length() < max_length) ||
+ ((flags_ & EXCEPT_EXACT_MATCH) != EXCEPT_EXACT_MATCH))) {
+ buf_.push_back(key.id());
}
- return;
+ break;
}
- if (trie_->ith_node(node_id).child() == TERMINAL_LABEL) {
- if (i >= min_length) {
- if (skip_count < offset_) {
- ++skip_count;
- } else {
- const UInt32 terminal = base.offset() ^ TERMINAL_LABEL;
- buf_.push_back(trie_->ith_node(terminal).key_id());
- if (buf_.size() >= limit_) {
- return;
- }
- }
- }
+ if ((i >= min_length) &&
+ (trie_->ith_node(node_id).child() == TERMINAL_LABEL)) {
+ const UInt32 terminal = base.offset() ^ TERMINAL_LABEL;
+ buf_.push_back(trie_->ith_node(terminal).key_id());
}
node_id = base.offset() ^ ptr[i];
if (trie_->ith_node(node_id).label() != ptr[i]) {
- return;
+ break;
}
}
- if (skip_count < offset_) {
+ if ((i == max_length) &&
+ (flags_ & EXCEPT_EXACT_MATCH) != EXCEPT_EXACT_MATCH) {
+ const Base base = trie_->ith_node(node_id).base();
+ if (base.is_terminal()) {
+ Key key;
+ trie_->ith_key(base.key_id(), &key);
+ if ((key.length() >= min_length) && (key.length() <= max_length)) {
+ buf_.push_back(key.id());
+ }
+ } else if (trie_->ith_node(node_id).child() == TERMINAL_LABEL) {
+ const UInt32 terminal = base.offset() ^ TERMINAL_LABEL;
+ Key key;
+ trie_->ith_key(trie_->ith_node(terminal).key_id(), &key);
+ if ((key.length() >= min_length) && (key.length() <= max_length)) {
+ buf_.push_back(key.id());
+ }
+ }
+ }
+
+ if (buf_.size() <= offset_) {
return;
}
- const Base base = trie_->ith_node(node_id).base();
- if (base.is_terminal()) {
- Key key;
- trie_->ith_key(base.key_id(), &key);
- if (key.length() <= max_length) {
- buf_.push_back(key.id());
- }
- } else if (trie_->ith_node(node_id).child() == TERMINAL_LABEL) {
- const UInt32 terminal = base.offset() ^ TERMINAL_LABEL;
- Key key;
- trie_->ith_key(trie_->ith_node(terminal).key_id(), &key);
- if ((key.length() >= min_length) && (key.length() <= max_length)) {
- buf_.push_back(key.id());
- }
+ 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;
}
}
@@ -158,7 +162,8 @@ void CommonPrefixSearchCursor::swap(CommonPrefixSearchCursor *cursor) {
std::swap(limit_, cursor->limit_);
std::swap(flags_, cursor->flags_);
buf_.swap(cursor->buf_);
- std::swap(count_, cursor->count_);
+ std::swap(cur_, cursor->cur_);
+ std::swap(end_, cursor->end_);
}
} // namespace grn
Modified: lib/dat/common-prefix-search-cursor.hpp (+2 -1)
===================================================================
--- lib/dat/common-prefix-search-cursor.hpp 2011-06-27 11:16:42 +0000 (2d0abf5)
+++ lib/dat/common-prefix-search-cursor.hpp 2011-06-28 06:15:15 +0000 (022d7aa)
@@ -43,7 +43,8 @@ class CommonPrefixSearchCursor : public Cursor {
UInt32 flags_;
std::vector<UInt32> buf_;
- UInt32 count_;
+ UInt32 cur_;
+ UInt32 end_;
UInt32 fix_flags(UInt32 flags) const;
CommonPrefixSearchCursor(const Trie &trie,
Modified: lib/dat/dat.hpp (+1 -1)
===================================================================
--- lib/dat/dat.hpp 2011-06-27 11:16:42 +0000 (c06d3dd)
+++ lib/dat/dat.hpp 2011-06-28 06:15:15 +0000 (d93680d)
@@ -95,7 +95,7 @@ const UInt32 ID_RANGE_CURSOR = 0x00001;
const UInt32 KEY_RANGE_CURSOR = 0x00002;
const UInt32 COMMON_PREFIX_CURSOR = 0x00004;
const UInt32 PREDICTIVE_CURSOR = 0x00008;
-const UInt32 CURSOR_TYPE_MASK = 0x000FF;
+const UInt32 CURSOR_TYPE_MASK = 0x000FF;
const UInt32 ASCENDING_CURSOR = 0x00100;
const UInt32 DESCENDING_CURSOR = 0x00200;
Modified: lib/dat/trie.cpp (+0 -1)
===================================================================
--- lib/dat/trie.cpp 2011-06-27 11:16:42 +0000 (3382df3)
+++ lib/dat/trie.cpp 2011-06-28 06:15:15 +0000 (d205f7e)
@@ -8,7 +8,6 @@
#include <algorithm>
#include <cstring>
-#include <new>
namespace grn {
namespace dat {