susumu.yata
null+****@clear*****
Tue Apr 9 18:20:00 JST 2013
susumu.yata 2013-04-09 18:20:00 +0900 (Tue, 09 Apr 2013) New Revision: aa2a04a338e94129a5f5abd272fdb3fcc864f204 https://github.com/groonga/grnxx/commit/aa2a04a338e94129a5f5abd272fdb3fcc864f204 Message: Update grnxx::alpha::map::KeyCursor to support MAP_CURSOR_ORDER_BY_KEY. Modified files: lib/grnxx/alpha/map/cursor.cpp lib/grnxx/alpha/map/cursor.hpp test/test_alpha_map.cpp Modified: lib/grnxx/alpha/map/cursor.cpp (+75 -34) =================================================================== --- lib/grnxx/alpha/map/cursor.cpp 2013-04-09 17:55:37 +0900 (be2b598) +++ lib/grnxx/alpha/map/cursor.cpp 2013-04-09 18:20:00 +0900 (eeadd37) @@ -154,27 +154,69 @@ template class IDCursor<Slice>; template <typename T> KeyCursor<T>::KeyCursor(Map<T> *map, T min, T max, const MapCursorOptions &options) - : MapCursor<T>(), map_(map), min_(min), max_(max), end_(), step_(), - left_(options.limit), flags_(options.flags) { - if ((~options.flags & MAP_CURSOR_ORDER_BY_ID) && - (options.flags & MAP_CURSOR_ORDER_BY_KEY)) { - // TODO: Order by key. + : MapCursor<T>(), map_(map), min_(min), max_(max), cur_(), end_(), step_(), + count_(0), options_(options), keys_() { + if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) || + (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { + init_order_by_id(); + } else { + init_order_by_key(); } +} - uint64_t count = 0; - if (~flags_ & MAP_CURSOR_REVERSE_ORDER) { - this->key_id_ = -1; +template <typename T> +KeyCursor<T>::~KeyCursor() {} + +template <typename T> +bool KeyCursor<T>::next() { + if (count_ >= options_.limit) { + return false; + } + if (options_.flags & MAP_CURSOR_ORDER_BY_ID) { + while (cur_ != end_) { + cur_ += step_; + if (map_->get(cur_, &this->key_)) { + if (in_range(this->key_)) { + this->key_id_ = cur_; + ++count_; + return true; + } + } + } + } else if (cur_ != end_) { + cur_ += step_; + this->key_ = keys_[cur_].first; + this->key_id_ = keys_[cur_].second; + ++count_; + return true; + } + return false; +} + +template <typename T> +bool KeyCursor<T>::remove() { + return map_->unset(this->key_id_); +} + +template <typename T> +void KeyCursor<T>::init_order_by_id() { + options_.flags |= MAP_CURSOR_ORDER_BY_ID; + options_.flags &= ~MAP_CURSOR_ORDER_BY_KEY; + + if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { + cur_ = -1; end_ = map_->max_key_id(); step_ = 1; } else { - this->key_id_ = map_->max_key_id() + 1; + cur_ = map_->max_key_id() + 1; end_ = 0; step_ = -1; } - while ((count < options.offset) && (this->key_id_ != end_)) { - this->key_id_ += step_; - if (map_->get(this->key_id_, &this->key_)) { + uint64_t count = 0; + while ((count < options_.offset) && (cur_ != end_)) { + cur_ += step_; + if (map_->get(cur_, &this->key_)) { if (in_range(this->key_)) { ++count; } @@ -183,33 +225,32 @@ KeyCursor<T>::KeyCursor(Map<T> *map, T min, T max, } template <typename T> -KeyCursor<T>::~KeyCursor() {} - -template <typename T> -bool KeyCursor<T>::next() { - if (left_ == 0) { - return false; - } - while (this->key_id_ != end_) { - this->key_id_ += step_; - if (map_->get(this->key_id_, &this->key_)) { - if (in_range(this->key_)) { - --left_; - return true; +void KeyCursor<T>::init_order_by_key() { + std::int64_t max_key_id = map_->max_key_id(); + for (std::int64_t i = 0; i <= max_key_id; ++i) { + T key; + if (map_->get(i, &key)) { + if (in_range(key)) { + keys_.push_back(std::make_pair(key, i)); } } } - return false; -} + std::sort(keys_.begin(), keys_.end()); -template <typename T> -bool KeyCursor<T>::remove() { - return map_->unset(this->key_id_); + if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { + cur_ = -1; + end_ = keys_.size() - 1; + step_ = 1; + } else { + cur_ = keys_.size(); + end_ = 0; + step_ = -1; + } } template <typename T> bool KeyCursor<T>::in_range(T key) const { - if (flags_ & MAP_CURSOR_EXCEPT_MIN) { + if (options_.flags & MAP_CURSOR_EXCEPT_MIN) { if (key <= min_) { return false; } @@ -217,7 +258,7 @@ bool KeyCursor<T>::in_range(T key) const { return false; } - if (flags_ & MAP_CURSOR_EXCEPT_MAX) { + if (options_.flags & MAP_CURSOR_EXCEPT_MAX) { if (key >= max_) { return false; } @@ -230,7 +271,7 @@ bool KeyCursor<T>::in_range(T key) const { template <> bool KeyCursor<Slice>::in_range(Slice key) const { - if (flags_ & MAP_CURSOR_EXCEPT_MIN) { + if (options_.flags & MAP_CURSOR_EXCEPT_MIN) { if (key <= min_) { return false; } @@ -239,7 +280,7 @@ bool KeyCursor<Slice>::in_range(Slice key) const { } if (max_) { - if (flags_ & MAP_CURSOR_EXCEPT_MAX) { + if (options_.flags & MAP_CURSOR_EXCEPT_MAX) { if (key >= max_) { return false; } Modified: lib/grnxx/alpha/map/cursor.hpp (+7 -2) =================================================================== --- lib/grnxx/alpha/map/cursor.hpp 2013-04-09 17:55:37 +0900 (53e662c) +++ lib/grnxx/alpha/map/cursor.hpp 2013-04-09 18:20:00 +0900 (51bb4ec) @@ -63,10 +63,15 @@ class KeyCursor : public MapCursor<T> { Map<T> *map_; T min_; T max_; + int64_t cur_; int64_t end_; int64_t step_; - uint64_t left_; - MapCursorFlags flags_; + uint64_t count_; + MapCursorOptions options_; + std::vector<std::pair<T, int64_t>> keys_; + + void init_order_by_id(); + void init_order_by_key(); bool in_range(T key) const; }; Modified: test/test_alpha_map.cpp (+15 -0) =================================================================== --- test/test_alpha_map.cpp 2013-04-09 17:55:37 +0900 (e50ad3b) +++ test/test_alpha_map.cpp 2013-04-09 18:20:00 +0900 (13a9f51) @@ -272,6 +272,21 @@ void test_key_cursor(const std::unique_ptr<Map<T>> &map) { assert(cursor->key() < max_key); } assert(!cursor->next()); + + options.flags = grnxx::alpha::MAP_CURSOR_ORDER_BY_KEY; + cursor.reset(map->open_key_cursor(min_key, max_key, options)); + if (cursor->next()) { + assert(cursor->key() >= min_key); + assert(cursor->key() <= max_key); + } + T prev_key = cursor->key(); + while (cursor->next()) { + assert(cursor->key() >= min_key); + assert(cursor->key() <= max_key); + assert(prev_key < cursor->key()); + prev_key = cursor->key(); + } + assert(!cursor->next()); } void test_key_cursor( -------------- next part -------------- HTML����������������������������...Download