susumu.yata
null+****@clear*****
Fri Mar 22 16:00:56 JST 2013
susumu.yata 2013-03-22 16:00:56 +0900 (Fri, 22 Mar 2013) New Revision: 5a7b4f4979b6c2f989bd08c35981bdbe55fdf508 https://github.com/groonga/groonga/commit/5a7b4f4979b6c2f989bd08c35981bdbe55fdf508 Message: Fix a bug of grn_dat_cursor. The old grn_dat_cursor returns wrong keys when used with GRN_CURSOR_BY_ID and (offset or limit) after deleting keys. Modified files: lib/dat/id-cursor.cpp lib/dat/id-cursor.hpp test/unit/core/dat/test-id-cursor.cpp Modified: lib/dat/id-cursor.cpp (+29 -21) =================================================================== --- lib/dat/id-cursor.cpp 2013-03-22 15:06:55 +0900 (24d82c7) +++ lib/dat/id-cursor.cpp 2013-03-22 16:00:56 +0900 (784175f) @@ -30,7 +30,8 @@ IdCursor::IdCursor() limit_(MAX_UINT32), flags_(ID_RANGE_CURSOR), cur_(INVALID_KEY_ID), - end_(INVALID_KEY_ID) {} + end_(INVALID_KEY_ID), + count_(0) {} IdCursor::~IdCursor() {} @@ -78,6 +79,9 @@ void IdCursor::close() { } const Key &IdCursor::next() { + if (count_ >= limit_) { + return Key::invalid_key(); + } while (cur_ != end_) { const Key &key = trie_->ith_key(cur_); if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) { @@ -86,6 +90,7 @@ const Key &IdCursor::next() { --cur_; } if (key.is_valid()) { + ++count_; return key; } } @@ -93,13 +98,16 @@ const Key &IdCursor::next() { } IdCursor::IdCursor(const Trie &trie, - UInt32 offset, UInt32 limit, UInt32 flags) + UInt32 offset, + UInt32 limit, + UInt32 flags) : trie_(&trie), offset_(offset), limit_(limit), flags_(flags), cur_(INVALID_KEY_ID), - end_(INVALID_KEY_ID) {} + end_(INVALID_KEY_ID), + count_(0) {} UInt32 IdCursor::fix_flags(UInt32 flags) const { const UInt32 cursor_type = flags & CURSOR_TYPE_MASK; @@ -135,30 +143,29 @@ void IdCursor::init(UInt32 min_id, UInt32 max_id) { --max_id; } - if (max_id < min_id) { - return; - } - - UInt32 diff = max_id - min_id; - if (diff < offset_) { + if ((max_id < min_id) || ((max_id - min_id) < offset_)) { return; } - diff -= offset_; - const UInt32 temp_limit = (limit_ > diff) ? (diff + 1) : limit_; if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) { - min_id += offset_; - max_id = min_id + temp_limit; - if (min_id < max_id) { - cur_ = min_id; - end_ = max_id; + cur_ = min_id; + end_ = max_id + 1; + for (UInt32 i = 0; (i < offset_) && (cur_ != end_); ++i) { + while (cur_ != end_) { + if (trie_->ith_key(cur_++).is_valid()) { + break; + } + } } } else { - max_id -= offset_; - min_id = max_id - temp_limit; - if (min_id < max_id) { - cur_ = max_id; - end_ = min_id; + cur_ = max_id; + end_ = min_id - 1; + for (UInt32 i = 0; (i < offset_) && (cur_ != end_); ++i) { + while (cur_ != end_) { + if (trie_->ith_key(cur_--).is_valid()) { + break; + } + } } } } @@ -170,6 +177,7 @@ void IdCursor::swap(IdCursor *cursor) { std::swap(flags_, cursor->flags_); std::swap(cur_, cursor->cur_); std::swap(end_, cursor->end_); + std::swap(count_, cursor->count_); } } // namespace dat Modified: lib/dat/id-cursor.hpp (+1 -0) =================================================================== --- lib/dat/id-cursor.hpp 2013-03-22 15:06:55 +0900 (9bcebbd) +++ lib/dat/id-cursor.hpp 2013-03-22 16:00:56 +0900 (aabd734) @@ -66,6 +66,7 @@ class GRN_DAT_API IdCursor : public Cursor { UInt32 cur_; UInt32 end_; + UInt32 count_; IdCursor(const Trie &trie, UInt32 offset, UInt32 limit, UInt32 flags); Modified: test/unit/core/dat/test-id-cursor.cpp (+60 -0) =================================================================== --- test/unit/core/dat/test-id-cursor.cpp 2013-03-22 15:06:55 +0900 (bc82890) +++ test/unit/core/dat/test-id-cursor.cpp 2013-03-22 16:00:56 +0900 (0d0c097) @@ -235,6 +235,34 @@ namespace test_dat_id_cursor cppcut_assert_equal(false, cursor.next().is_valid()); } + void test_offset_after_delete(void) { + grn::dat::Trie trie; + create_trie(&trie); + + for (grn::dat::UInt32 i = 1; i <= trie.max_key_id(); i += 2) { + trie.remove(i); + } + + grn::dat::IdCursor cursor; + + cursor.open(trie, 0, 0, 1); + for (grn::dat::UInt32 i = 4; i <= trie.max_key_id(); i += 2) { + const grn::dat::Key &key = cursor.next(); + cppcut_assert_equal(true, key.is_valid()); + } + cppcut_assert_equal(false, cursor.next().is_valid()); + + cursor.open(trie, 0, 0, 2); + for (grn::dat::UInt32 i = 6; i <= trie.max_key_id(); i += 2) { + const grn::dat::Key &key = cursor.next(); + cppcut_assert_equal(true, key.is_valid()); + } + cppcut_assert_equal(false, cursor.next().is_valid()); + + cursor.open(trie, 0, 0, trie.max_key_id() / 2); + cppcut_assert_equal(false, cursor.next().is_valid()); + } + void test_limit(void) { grn::dat::Trie trie; @@ -272,6 +300,38 @@ namespace test_dat_id_cursor cppcut_assert_equal(false, cursor.next().is_valid()); } + void test_limit_after_delete(void) { + grn::dat::Trie trie; + create_trie(&trie); + + for (grn::dat::UInt32 i = 1; i <= trie.max_key_id(); i += 2) { + trie.remove(i); + } + + grn::dat::IdCursor cursor; + + cursor.open(trie, 0, 0, 0, trie.max_key_id() / 2); + for (grn::dat::UInt32 i = 2; i <= trie.max_key_id(); i += 2) { + const grn::dat::Key &key = cursor.next(); + cppcut_assert_equal(true, key.is_valid()); + } + cppcut_assert_equal(false, cursor.next().is_valid()); + + cursor.open(trie, 0, 0, 0, 1); + for (grn::dat::UInt32 i = 2; i <= 2; i += 2) { + const grn::dat::Key &key = cursor.next(); + cppcut_assert_equal(true, key.is_valid()); + } + cppcut_assert_equal(false, cursor.next().is_valid()); + + cursor.open(trie, 0, 0, 0, 3); + for (grn::dat::UInt32 i = 2; i <= (2 + 4); i += 2) { + const grn::dat::Key &key = cursor.next(); + cppcut_assert_equal(true, key.is_valid()); + } + cppcut_assert_equal(false, cursor.next().is_valid()); + } + void test_ascending_cursor(void) { grn::dat::Trie trie; -------------- next part -------------- HTML����������������������������...Download