susumu.yata
null+****@clear*****
Sat Apr 27 20:59:27 JST 2013
susumu.yata 2013-04-27 20:59:27 +0900 (Sat, 27 Apr 2013) New Revision: 04bb3c2ed3bef8d60f8bfdc6bd87816ca35da01e https://github.com/groonga/grnxx/commit/04bb3c2ed3bef8d60f8bfdc6bd87816ca35da01e Message: Fix a bug of grnxx::alpha::map::DoubleArray. Modified files: lib/grnxx/alpha/geo_point.hpp lib/grnxx/alpha/map.hpp lib/grnxx/alpha/map/cursor.hpp lib/grnxx/alpha/map/double_array-slice.cpp lib/grnxx/alpha/map/double_array.cpp lib/grnxx/alpha/map/double_array.hpp test/test_alpha_map.cpp Modified: lib/grnxx/alpha/geo_point.hpp (+1 -1) =================================================================== --- lib/grnxx/alpha/geo_point.hpp 2013-04-26 22:35:21 +0900 (b52ec2a) +++ lib/grnxx/alpha/geo_point.hpp 2013-04-27 20:59:27 +0900 (eabd7a7) @@ -35,7 +35,7 @@ union GeoPoint { GeoPoint(const GeoPoint &x) : value_(x.value_) {} // Copy lat/long. GeoPoint(int32_t latitude, int32_t longitude) - : point_{ latitude, longitude } {} + : point_{ latitude, longitude } {} // Assign lat/long as uint64_t to force atomic assignment. GeoPoint &operator=(const GeoPoint &x) { Modified: lib/grnxx/alpha/map.hpp (+8 -11) =================================================================== --- lib/grnxx/alpha/map.hpp 2013-04-26 22:35:21 +0900 (4f96b11) +++ lib/grnxx/alpha/map.hpp 2013-04-27 20:59:27 +0900 (7799f63) @@ -43,7 +43,7 @@ struct MapOptions { }; struct MapCursorFlagsIdentifier; -typedef FlagsImpl<MapCursorFlagsIdentifier> MapCursorFlags; +using MapCursorFlags = FlagsImpl<MapCursorFlagsIdentifier>; // Use the default settings. constexpr MapCursorFlags MAP_CURSOR_DEFAULT = @@ -86,7 +86,6 @@ class MapCursor { // Move the cursor to the next key and return true on success. virtual bool next(); - // Remove the current key and return true on success. virtual bool remove(); @@ -107,8 +106,6 @@ class MapCursor { template <typename T> class Map { public: - using Cursor = MapCursor<T>; - Map(); virtual ~Map(); @@ -176,33 +173,33 @@ class Map { virtual bool truncate(); // Create a cursor for accessing all the keys. - virtual Cursor *open_basic_cursor( + virtual MapCursor<T> *open_basic_cursor( const MapCursorOptions &options = MapCursorOptions()); // Create a cursor for accessing keys in range [min, max]. - virtual Cursor *open_id_cursor( + virtual MapCursor<T> *open_id_cursor( int64_t min, int64_t max, const MapCursorOptions &options = MapCursorOptions()); // Create a cursor for accessing keys in range [min, max]. - virtual Cursor *open_key_cursor( + virtual MapCursor<T> *open_key_cursor( T min, T max, const MapCursorOptions &options = MapCursorOptions()); // Only for GeoPoint. // Create a cursor for accessing keys whose most significant "bit_size" bits // are same as the MSBs of "query". - virtual Cursor *open_bitwise_completion_cursor( + virtual MapCursor<T> *open_bitwise_completion_cursor( T query, size_t bit_size, const MapCursorOptions &options = MapCursorOptions()); // Only for Slice. // Create a cursor for accessing keys matching a prefix of "query". - virtual Cursor *open_prefix_cursor( + virtual MapCursor<T> *open_prefix_cursor( T query, size_t min_size, const MapCursorOptions &options = MapCursorOptions()); // Create a cursor for accessing keys starting with "query". - virtual Cursor *open_completion_cursor( + virtual MapCursor<T> *open_completion_cursor( T query, const MapCursorOptions &options = MapCursorOptions()); // Create a cursor for accessing keys ending with "query". - virtual Cursor *open_reverse_completion_cursor( + virtual MapCursor<T> *open_reverse_completion_cursor( T query, const MapCursorOptions &options = MapCursorOptions()); // Only for Slice. Modified: lib/grnxx/alpha/map/cursor.hpp (+4 -2) =================================================================== --- lib/grnxx/alpha/map/cursor.hpp 2013-04-26 22:35:21 +0900 (b91f813) +++ lib/grnxx/alpha/map/cursor.hpp 2013-04-27 20:59:27 +0900 (bc601fd) @@ -70,10 +70,12 @@ class ConditionalCursor : public MapCursor<T> { std::vector<std::pair<T, int64_t>> keys_; void init(); - void init_order_by_id(); - void init_order_by_key(); virtual bool is_valid(T key) const = 0; + + private: + void init_order_by_id(); + void init_order_by_key(); }; template <typename T> Modified: lib/grnxx/alpha/map/double_array-slice.cpp (+99 -126) =================================================================== --- lib/grnxx/alpha/map/double_array-slice.cpp 2013-04-26 22:35:21 +0900 (77f2ed8) +++ lib/grnxx/alpha/map/double_array-slice.cpp 2013-04-27 20:59:27 +0900 (e6132f0) @@ -76,7 +76,7 @@ constexpr uint32_t INVALID_LEADER = std::numeric_limits<uint32_t>::max(); } // namespace -struct DoubleArrayHeaderForSlice { +struct SliceDoubleArrayHeader { MapType map_type; uint32_t nodes_block_id; uint32_t chunks_block_id; @@ -97,37 +97,37 @@ struct DoubleArrayHeaderForSlice { uint32_t leaders[MAX_CHUNK_LEVEL + 1]; Mutex inter_process_mutex; - DoubleArrayHeaderForSlice(); + SliceDoubleArrayHeader(); }; -DoubleArrayHeaderForSlice::DoubleArrayHeaderForSlice() - : map_type(MAP_DOUBLE_ARRAY), - nodes_block_id(io::BLOCK_INVALID_ID), - chunks_block_id(io::BLOCK_INVALID_ID), - entries_block_id(io::BLOCK_INVALID_ID), - keys_block_id(io::BLOCK_INVALID_ID), - nodes_size(0), - chunks_size(0), - entries_size(0), - keys_size(0), - next_key_id(0), - next_key_pos(0), - max_key_id(-1), - total_key_length(0), - num_keys(0), - num_chunks(0), - num_phantoms(0), - num_zombies(0), - leaders(), - inter_process_mutex(MUTEX_UNLOCKED) { +SliceDoubleArrayHeader::SliceDoubleArrayHeader() + : map_type(MAP_DOUBLE_ARRAY), + nodes_block_id(io::BLOCK_INVALID_ID), + chunks_block_id(io::BLOCK_INVALID_ID), + entries_block_id(io::BLOCK_INVALID_ID), + keys_block_id(io::BLOCK_INVALID_ID), + nodes_size(0), + chunks_size(0), + entries_size(0), + keys_size(0), + next_key_id(0), + next_key_pos(0), + max_key_id(-1), + total_key_length(0), + num_keys(0), + num_chunks(0), + num_phantoms(0), + num_zombies(0), + leaders(), + inter_process_mutex(MUTEX_UNLOCKED) { for (uint32_t i = 0; i <= MAX_CHUNK_LEVEL; ++i) { leaders[i] = INVALID_LEADER; } } -class DoubleArrayNodeForSlice { +class SliceDoubleArrayNode { public: - DoubleArrayNodeForSlice() : qword_(IS_PHANTOM_FLAG) {} + SliceDoubleArrayNode() : qword_(IS_PHANTOM_FLAG) {} // Structure overview. // 0- 8 ( 9): next (is_phantom). @@ -272,9 +272,9 @@ class DoubleArrayNodeForSlice { static constexpr uint8_t CHILD_SHIFT = 50; }; -class DoubleArrayChunkForSlice { +class SliceDoubleArrayChunk { public: - DoubleArrayChunkForSlice() : next_(0), prev_(0), others_(0) {} + SliceDoubleArrayChunk() : next_(0), prev_(0), others_(0) {} // Chunks in the same level are doubly linked. uint32_t next() const { @@ -343,15 +343,15 @@ class DoubleArrayChunkForSlice { static constexpr uint32_t NUM_PHANTOMS_SHIFT = 20; }; -class DoubleArrayEntryForSlice { +class SliceDoubleArrayEntry { public: // Create a valid entry. - static DoubleArrayEntryForSlice valid_entry(uint32_t key_pos) { - return DoubleArrayEntryForSlice(IS_VALID_FLAG | key_pos); + static SliceDoubleArrayEntry valid_entry(uint32_t key_pos) { + return SliceDoubleArrayEntry(IS_VALID_FLAG | key_pos); } // Create an invalid entry. - static DoubleArrayEntryForSlice invalid_entry(uint32_t next) { - return DoubleArrayEntryForSlice(next); + static SliceDoubleArrayEntry invalid_entry(uint32_t next) { + return SliceDoubleArrayEntry(next); } // Return true iff "*this" is valid (associated with a key). @@ -376,15 +376,15 @@ class DoubleArrayEntryForSlice { static constexpr uint32_t IS_VALID_FLAG = uint32_t(1) << 31; - explicit DoubleArrayEntryForSlice(uint32_t x) : dword_(x) {} + explicit SliceDoubleArrayEntry(uint32_t x) : dword_(x) {} }; -class DoubleArrayKeyForSlice { +class SliceDoubleArrayKey { public: - DoubleArrayKeyForSlice(int32_t id, const Slice &key) - : id_(id), - size_(static_cast<uint16_t>(key.size())), - buf_{ '\0', '\0' } { + SliceDoubleArrayKey(int32_t id, const Slice &key) + : id_(id), + size_(static_cast<uint16_t>(key.size())), + buf_{ '\0', '\0' } { std::memcpy(buf_, key.ptr(), key.size()); } @@ -457,25 +457,22 @@ class DoubleArrayIDCursor<Slice> : public MapCursor<Slice> { DoubleArrayIDCursor<Slice>::DoubleArrayIDCursor( DoubleArray<Slice> *double_array, int64_t min, int64_t max, const MapCursorOptions &options) - : MapCursor<Slice>(), double_array_(double_array), cur_(), end_(), step_(), - count_(0), options_(options), keys_() { + : MapCursor<Slice>(), double_array_(double_array), cur_(), end_(), step_(), + count_(0), options_(options), keys_() { if (min < 0) { min = 0; } else if (options_.flags & MAP_CURSOR_EXCEPT_MIN) { ++min; } - if ((max < 0) || (max > double_array_->max_key_id())) { max = double_array_->max_key_id(); } else if (options_.flags & MAP_CURSOR_EXCEPT_MAX) { --max; } - if (min > max) { cur_ = end_ = 0; return; } - if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) || (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(min, max); @@ -516,7 +513,6 @@ bool DoubleArrayIDCursor<Slice>::remove() { void DoubleArrayIDCursor<Slice>::init_order_by_id(int64_t min, int64_t max) { options_.flags |= MAP_CURSOR_ORDER_BY_ID; options_.flags &= ~MAP_CURSOR_ORDER_BY_KEY; - if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { cur_ = min - 1; end_ = max; @@ -526,7 +522,6 @@ void DoubleArrayIDCursor<Slice>::init_order_by_id(int64_t min, int64_t max) { end_ = min; step_ = -1; } - uint64_t count = 0; while ((count < options_.offset) && (cur_ != end_)) { cur_ += step_; @@ -547,7 +542,6 @@ void DoubleArrayIDCursor<Slice>::init_order_by_key(int64_t min, int64_t max) { } } std::sort(keys_.begin(), keys_.end()); - if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { cur_ = -1; end_ = keys_.size() - 1; @@ -592,15 +586,19 @@ class DoubleArrayKeyCursor<Slice> : public MapCursor<Slice> { DoubleArrayKeyCursor<Slice>::DoubleArrayKeyCursor( DoubleArray<Slice> *double_array, Slice min, Slice max, const MapCursorOptions &options) - : MapCursor<Slice>(), double_array_(double_array), cur_(), count_(0), - min_(min), max_(max), options_(options), node_ids_(), keys_() { + : MapCursor<Slice>(), double_array_(double_array), cur_(), count_(0), + min_(min), max_(max), options_(options), node_ids_(), keys_() { if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(); - } else if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { - init_order_by_key(); } else { - init_reverse_order_by_key(); + options_.flags &= ~MAP_CURSOR_ORDER_BY_ID; + options_.flags |= MAP_CURSOR_ORDER_BY_KEY; + if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { + init_order_by_key(); + } else { + init_reverse_order_by_key(); + } } } @@ -610,8 +608,7 @@ bool DoubleArrayKeyCursor<Slice>::next() { if (count_ >= options_.limit) { return false; } - if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && - (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { + if (options_.flags & MAP_CURSOR_ORDER_BY_ID) { return next_order_by_id(); } else if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { return next_order_by_key(); @@ -626,18 +623,15 @@ bool DoubleArrayKeyCursor<Slice>::remove() { void DoubleArrayKeyCursor<Slice>::init_order_by_id() { init_order_by_key(); - while (!node_ids_.empty()) { const uint64_t node_id = node_ids_.back(); node_ids_.pop_back(); - - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.sibling() != INVALID_LABEL) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if (max_) { const int result = key.slice().compare(Slice(max_.ptr(), max_.size())); @@ -647,12 +641,10 @@ void DoubleArrayKeyCursor<Slice>::init_order_by_id() { } } keys_.push_back(std::make_pair(key.id(), key.slice())); - ++count_; } else if (node.child() != INVALID_LABEL) { node_ids_.push_back(node.offset() ^ node.child()); } } - std::sort(keys_.begin(), keys_.end()); if (options_.flags & MAP_CURSOR_REVERSE_ORDER) { std::reverse(keys_.begin(), keys_.end()); @@ -665,13 +657,12 @@ void DoubleArrayKeyCursor<Slice>::init_order_by_key() { node_ids_.push_back(ROOT_NODE_ID); return; } - uint64_t node_id = ROOT_NODE_ID; - DoubleArrayNodeForSlice node; + SliceDoubleArrayNode node; for (size_t i = 0; i < min_.size(); ++i) { node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); const int result = key.slice().compare(min_, i); if ((result > 0) || @@ -684,7 +675,6 @@ void DoubleArrayKeyCursor<Slice>::init_order_by_key() { } else if (node.sibling() != INVALID_LABEL) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - node_id = node.offset() ^ min_[i]; if (double_array_->nodes_[node_id].label() != min_[i]) { uint16_t label = node.child(); @@ -704,7 +694,7 @@ void DoubleArrayKeyCursor<Slice>::init_order_by_key() { node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = double_array_->get_key(node.key_pos()); + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if ((key.size() != min_.size()) || (~options_.flags & MAP_CURSOR_EXCEPT_MIN)) { node_ids_.push_back(node_id); @@ -730,12 +720,11 @@ void DoubleArrayKeyCursor<Slice>::init_reverse_order_by_key() { node_ids_.push_back(ROOT_NODE_ID); return; } - uint64_t node_id = ROOT_NODE_ID; for (size_t i = 0; i < max_.size(); ++i) { - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); const int result = key.slice().compare(max_, i); if ((result < 0) || @@ -744,7 +733,6 @@ void DoubleArrayKeyCursor<Slice>::init_reverse_order_by_key() { } return; } - uint16_t label = double_array_->nodes_[node_id].child(); if (label == TERMINAL_LABEL) { node_id = node.offset() ^ label; @@ -767,9 +755,9 @@ void DoubleArrayKeyCursor<Slice>::init_reverse_order_by_key() { } } - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = double_array_->get_key(node.key_pos()); + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if ((key.size() == max_.size()) && (~options_.flags & MAP_CURSOR_EXCEPT_MAX)) { node_ids_.push_back(node_id | POST_ORDER_FLAG); @@ -799,14 +787,12 @@ bool DoubleArrayKeyCursor<Slice>::next_order_by_key() { while (!node_ids_.empty()) { const uint64_t node_id = node_ids_.back(); node_ids_.pop_back(); - - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.sibling() != INVALID_LABEL) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if (max_) { const int result = key.slice().compare(Slice(max_.ptr(), max_.size())); @@ -835,12 +821,11 @@ bool DoubleArrayKeyCursor<Slice>::next_reverse_order_by_key() { while (!node_ids_.empty()) { const bool post_order = node_ids_.back() & POST_ORDER_FLAG; const uint64_t node_id = node_ids_.back() & ~POST_ORDER_FLAG; - - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (post_order) { node_ids_.pop_back(); if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if (min_) { const int result = @@ -897,15 +882,16 @@ class DoubleArrayPrefixCursor<Slice> : public MapCursor<Slice> { DoubleArrayPrefixCursor<Slice>::DoubleArrayPrefixCursor( DoubleArray<Slice> *double_array, Slice query, size_t min_size, const MapCursorOptions &options) - : MapCursor<Slice>(), double_array_(double_array), cur_(), - count_(0), options_(options), keys_() { - if ((~options_.flags & MAP_CURSOR_ORDER_BY_ID) || - (options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { - init_order_by_key(query, min_size); - } else { + : MapCursor<Slice>(), double_array_(double_array), cur_(), + count_(0), options_(options), keys_() { + if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && + (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(query, min_size); + } else { + options_.flags &= ~MAP_CURSOR_ORDER_BY_ID; + options_.flags |= MAP_CURSOR_ORDER_BY_KEY; + init_order_by_key(query, min_size); } - if (options_.flags & MAP_CURSOR_REVERSE_ORDER) { std::reverse(keys_.begin(), keys_.end()); } @@ -935,7 +921,6 @@ bool DoubleArrayPrefixCursor<Slice>::remove() { void DoubleArrayPrefixCursor<Slice>::init_order_by_id( Slice query, size_t min_size) { init_order_by_key(query, min_size); - std::sort(keys_.begin(), keys_.end()); } @@ -944,13 +929,12 @@ void DoubleArrayPrefixCursor<Slice>::init_order_by_key( if ((query.size() > 0) && (options_.flags & MAP_CURSOR_EXCEPT_QUERY)) { query.remove_suffix(1); } - uint64_t node_id = ROOT_NODE_ID; size_t i; for (i = 0; i < query.size(); ++i) { - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if ((key.size() >= min_size) && (key.size() <= query.size()) && key.equals_to(query.prefix(key.size()), i)) { @@ -958,18 +942,16 @@ void DoubleArrayPrefixCursor<Slice>::init_order_by_key( } break; } - if ((i >= min_size) && (double_array_->nodes_[node_id].child() == TERMINAL_LABEL)) { - const DoubleArrayNodeForSlice leaf_node = + const SliceDoubleArrayNode leaf_node = double_array_->nodes_[node.offset() ^ TERMINAL_LABEL]; if (leaf_node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(leaf_node.key_pos()); keys_.push_back(std::make_pair(key.id(), key.slice())); } } - node_id = node.offset() ^ query[i]; if (double_array_->nodes_[node_id].label() != query[i]) { break; @@ -977,18 +959,18 @@ void DoubleArrayPrefixCursor<Slice>::init_order_by_key( } if (i == query.size()) { - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if ((key.size() >= min_size) && (key.size() <= query.size())) { keys_.push_back(std::make_pair(key.id(), key.slice())); } } else if (double_array_->nodes_[node_id].child() == TERMINAL_LABEL) { - const DoubleArrayNodeForSlice leaf_node = + const SliceDoubleArrayNode leaf_node = double_array_->nodes_[node.offset() ^ TERMINAL_LABEL]; if (leaf_node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(leaf_node.key_pos()); keys_.push_back(std::make_pair(key.id(), key.slice())); } @@ -1028,12 +1010,14 @@ class DoubleArrayCompletionCursor<Slice> : public MapCursor<Slice> { DoubleArrayCompletionCursor<Slice>::DoubleArrayCompletionCursor( DoubleArray<Slice> *double_array, Slice query, const MapCursorOptions &options) - : MapCursor<Slice>(), double_array_(double_array), cur_(), count_(0), - query_(query), min_size_(), options_(options), node_ids_(), keys_() { + : MapCursor<Slice>(), double_array_(double_array), cur_(), count_(0), + query_(query), min_size_(), options_(options), node_ids_(), keys_() { if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(); } else { + options_.flags &= ~MAP_CURSOR_ORDER_BY_ID; + options_.flags |= MAP_CURSOR_ORDER_BY_KEY; init_order_by_key(); } } @@ -1044,8 +1028,7 @@ bool DoubleArrayCompletionCursor<Slice>::next() { if (count_ >= options_.limit) { return false; } - if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && - (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { + if (options_.flags & MAP_CURSOR_ORDER_BY_ID) { return next_order_by_id(); } else if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { return next_order_by_key(); @@ -1060,19 +1043,16 @@ bool DoubleArrayCompletionCursor<Slice>::remove() { void DoubleArrayCompletionCursor<Slice>::init_order_by_id() { init_order_by_key(); - while (!node_ids_.empty()) { const bool is_root = node_ids_.back() & IS_ROOT_FLAG; const uint64_t node_id = node_ids_.back() & ~IS_ROOT_FLAG; node_ids_.pop_back(); - - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (!is_root && (node.sibling() != INVALID_LABEL)) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if (key.size() >= min_size_) { keys_.push_back(std::make_pair(key.id(), key.slice())); @@ -1081,7 +1061,6 @@ void DoubleArrayCompletionCursor<Slice>::init_order_by_id() { node_ids_.push_back(node.offset() ^ node.child()); } } - std::sort(keys_.begin(), keys_.end()); if (options_.flags & MAP_CURSOR_REVERSE_ORDER) { std::reverse(keys_.begin(), keys_.end()); @@ -1094,12 +1073,11 @@ void DoubleArrayCompletionCursor<Slice>::init_order_by_key() { if (options_.flags & MAP_CURSOR_EXCEPT_QUERY) { ++min_size_; } - uint64_t node_id = ROOT_NODE_ID; for (size_t i = 0; i < query_.size(); ++i) { - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if ((key.size() >= min_size_) && (key.slice().subslice(i, query_.size() - i) == @@ -1111,13 +1089,11 @@ void DoubleArrayCompletionCursor<Slice>::init_order_by_key() { } return; } - node_id = node.offset() ^ query_[i]; if (double_array_->nodes_[node_id].label() != query_[i]) { return; } } - if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { node_id |= IS_ROOT_FLAG; } @@ -1140,14 +1116,12 @@ bool DoubleArrayCompletionCursor<Slice>::next_order_by_key() { const bool is_root = node_ids_.back() & IS_ROOT_FLAG; const uint64_t node_id = node_ids_.back() & ~IS_ROOT_FLAG; node_ids_.pop_back(); - - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (!is_root && (node.sibling() != INVALID_LABEL)) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if (key.size() >= min_size_) { if (options_.offset > 0) { @@ -1170,12 +1144,11 @@ bool DoubleArrayCompletionCursor<Slice>::next_reverse_order_by_key() { while (!node_ids_.empty()) { const bool post_order = node_ids_.back() & POST_ORDER_FLAG; const uint64_t node_id = node_ids_.back() & ~POST_ORDER_FLAG; - - const DoubleArrayNodeForSlice node = double_array_->nodes_[node_id]; + const SliceDoubleArrayNode node = double_array_->nodes_[node_id]; if (post_order) { node_ids_.pop_back(); if (node.is_leaf()) { - const DoubleArrayKeyForSlice &key = + const SliceDoubleArrayKey &key = double_array_->get_key(node.key_pos()); if (key.size() >= min_size_) { if (options_.offset > 0) { @@ -1577,14 +1550,14 @@ MapCursor<Slice> *DoubleArray<Slice>::open_completion_cursor( } DoubleArray<Slice>::DoubleArray() - : pool_(), - block_info_(nullptr), - header_(nullptr), - nodes_(nullptr), - chunks_(nullptr), - entries_(nullptr), - keys_(nullptr), - initialized_(false) {} + : pool_(), + block_info_(nullptr), + header_(nullptr), + nodes_(nullptr), + chunks_(nullptr), + entries_(nullptr), + keys_(nullptr), + initialized_(false) {} void DoubleArray<Slice>::create_double_array(io::Pool pool, const MapOptions &) { Modified: lib/grnxx/alpha/map/double_array.cpp (+70 -84) =================================================================== --- lib/grnxx/alpha/map/double_array.cpp 2013-04-26 22:35:21 +0900 (c63c21d) +++ lib/grnxx/alpha/map/double_array.cpp 2013-04-27 20:59:27 +0900 (1aa9bcb) @@ -193,7 +193,7 @@ void convert_key(GeoPoint key, uint8_t *key_buf) { } // namespace -struct DoubleArrayHeaderForOthers { +struct DoubleArrayHeader { MapType map_type; uint32_t nodes_block_id; uint32_t chunks_block_id; @@ -212,35 +212,35 @@ struct DoubleArrayHeaderForOthers { uint32_t leaders[MAX_CHUNK_LEVEL + 1]; Mutex inter_process_mutex; - DoubleArrayHeaderForOthers(); + DoubleArrayHeader(); }; -DoubleArrayHeaderForOthers::DoubleArrayHeaderForOthers() - : map_type(MAP_DOUBLE_ARRAY), - nodes_block_id(io::BLOCK_INVALID_ID), - chunks_block_id(io::BLOCK_INVALID_ID), - entries_block_id(io::BLOCK_INVALID_ID), - keys_block_id(io::BLOCK_INVALID_ID), - nodes_size(0), - chunks_size(0), - entries_size(0), - keys_size(0), - next_key_id(0), - max_key_id(-1), - num_keys(0), - num_chunks(0), - num_phantoms(0), - num_zombies(0), - leaders(), - inter_process_mutex(MUTEX_UNLOCKED) { +DoubleArrayHeader::DoubleArrayHeader() + : map_type(MAP_DOUBLE_ARRAY), + nodes_block_id(io::BLOCK_INVALID_ID), + chunks_block_id(io::BLOCK_INVALID_ID), + entries_block_id(io::BLOCK_INVALID_ID), + keys_block_id(io::BLOCK_INVALID_ID), + nodes_size(0), + chunks_size(0), + entries_size(0), + keys_size(0), + next_key_id(0), + max_key_id(-1), + num_keys(0), + num_chunks(0), + num_phantoms(0), + num_zombies(0), + leaders(), + inter_process_mutex(MUTEX_UNLOCKED) { for (uint32_t i = 0; i <= MAX_CHUNK_LEVEL; ++i) { leaders[i] = INVALID_LEADER; } } -class DoubleArrayNodeForOthers { +class DoubleArrayNode { public: - DoubleArrayNodeForOthers() : qword_(IS_PHANTOM_FLAG) {} + DoubleArrayNode() : qword_(IS_PHANTOM_FLAG) {} // Structure overview. // 0- 8 ( 9): next (is_phantom). @@ -385,9 +385,9 @@ class DoubleArrayNodeForOthers { static constexpr uint8_t CHILD_SHIFT = 50; }; -class DoubleArrayChunkForOthers { +class DoubleArrayChunk { public: - DoubleArrayChunkForOthers() : next_(0), prev_(0), others_(0) {} + DoubleArrayChunk() : next_(0), prev_(0), others_(0) {} // Chunks in the same level are doubly linked. uint32_t next() const { @@ -456,15 +456,15 @@ class DoubleArrayChunkForOthers { static constexpr uint32_t NUM_PHANTOMS_SHIFT = 20; }; -class DoubleArrayEntryForOthers { +class DoubleArrayEntry { public: // Create a valid entry. - static DoubleArrayEntryForOthers valid_entry() { - return DoubleArrayEntryForOthers(0); + static DoubleArrayEntry valid_entry() { + return DoubleArrayEntry(0); } // Create an invalid entry. - static DoubleArrayEntryForOthers invalid_entry(uint32_t next) { - return DoubleArrayEntryForOthers(next); + static DoubleArrayEntry invalid_entry(uint32_t next) { + return DoubleArrayEntry(next); } // Return true iff "*this" is valid (associated with a key). @@ -481,7 +481,7 @@ class DoubleArrayEntryForOthers { private: uint32_t dword_; - explicit DoubleArrayEntryForOthers(uint32_t x) : dword_(x) {} + explicit DoubleArrayEntry(uint32_t x) : dword_(x) {} }; template <typename T> @@ -515,25 +515,22 @@ template <typename T> DoubleArrayIDCursor<T>::DoubleArrayIDCursor( DoubleArray<T> *double_array, int64_t min, int64_t max, const MapCursorOptions &options) - : MapCursor<T>(), double_array_(double_array), cur_(), end_(), step_(), - count_(0), options_(options), keys_() { + : MapCursor<T>(), double_array_(double_array), cur_(), end_(), step_(), + count_(0), options_(options), keys_() { if (min < 0) { min = 0; } else if (options_.flags & MAP_CURSOR_EXCEPT_MIN) { ++min; } - if ((max < 0) || (max > double_array_->max_key_id())) { max = double_array_->max_key_id(); } else if (options_.flags & MAP_CURSOR_EXCEPT_MAX) { --max; } - if (min > max) { cur_ = end_ = 0; return; } - if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) || (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(min, max); @@ -578,7 +575,6 @@ template <typename T> void DoubleArrayIDCursor<T>::init_order_by_id(int64_t min, int64_t max) { options_.flags |= MAP_CURSOR_ORDER_BY_ID; options_.flags &= ~MAP_CURSOR_ORDER_BY_KEY; - if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { cur_ = min - 1; end_ = max; @@ -588,7 +584,6 @@ void DoubleArrayIDCursor<T>::init_order_by_id(int64_t min, int64_t max) { end_ = min; step_ = -1; } - uint64_t count = 0; while ((count < options_.offset) && (cur_ != end_)) { cur_ += step_; @@ -610,7 +605,6 @@ void DoubleArrayIDCursor<T>::init_order_by_key(int64_t min, int64_t max) { } } std::sort(keys_.begin(), keys_.end()); - if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { cur_ = -1; end_ = keys_.size() - 1; @@ -623,8 +617,10 @@ void DoubleArrayIDCursor<T>::init_order_by_key(int64_t min, int64_t max) { } template <> -void DoubleArrayIDCursor<GeoPoint>::init_order_by_key(int64_t, int64_t) { - // Not supported. +void DoubleArrayIDCursor<GeoPoint>::init_order_by_key(int64_t min, + int64_t max) { + // Ignore MAP_CURSOR_ORDER_BY_KEY. + init_order_by_id(min, max); } template <typename T> @@ -660,15 +656,19 @@ template <typename T> DoubleArrayKeyCursor<T>::DoubleArrayKeyCursor( DoubleArray<T> *double_array, T min, T max, const MapCursorOptions &options) - : MapCursor<T>(), double_array_(double_array), cur_(), count_(0), - min_(min), max_(max), options_(options), node_ids_(), keys_() { + : MapCursor<T>(), double_array_(double_array), cur_(), count_(0), + min_(min), max_(max), options_(options), node_ids_(), keys_() { if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(); - } else if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { - init_order_by_key(); } else { - init_reverse_order_by_key(); + options_.flags &= ~MAP_CURSOR_ORDER_BY_ID; + options_.flags |= MAP_CURSOR_ORDER_BY_KEY; + if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { + init_order_by_key(); + } else { + init_reverse_order_by_key(); + } } } @@ -680,8 +680,7 @@ bool DoubleArrayKeyCursor<T>::next() { if (count_ >= options_.limit) { return false; } - if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && - (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { + if (options_.flags & MAP_CURSOR_ORDER_BY_ID) { return next_order_by_id(); } else if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { return next_order_by_key(); @@ -698,16 +697,13 @@ bool DoubleArrayKeyCursor<T>::remove() { template <typename T> void DoubleArrayKeyCursor<T>::init_order_by_id() { init_order_by_key(); - while (!node_ids_.empty()) { const uint64_t node_id = node_ids_.back(); node_ids_.pop_back(); - - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (node.sibling() != INVALID_LABEL) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { const T key = double_array_->keys_[node.key_id()]; if ((key > max_) || @@ -715,12 +711,10 @@ void DoubleArrayKeyCursor<T>::init_order_by_id() { break; } keys_.push_back(std::make_pair(node.key_id(), key)); - ++count_; } else if (node.child() != INVALID_LABEL) { node_ids_.push_back(node.offset() ^ node.child()); } } - std::sort(keys_.begin(), keys_.end()); if (options_.flags & MAP_CURSOR_REVERSE_ORDER) { std::reverse(keys_.begin(), keys_.end()); @@ -734,7 +728,7 @@ void DoubleArrayKeyCursor<T>::init_order_by_key() { convert_key(min_, min_buf); uint64_t node_id = ROOT_NODE_ID; - DoubleArrayNodeForOthers node; + DoubleArrayNode node; for (size_t i = 0; i < sizeof(T); ++i) { node = double_array_->nodes_[node_id]; if (node.is_leaf()) { @@ -749,7 +743,6 @@ void DoubleArrayKeyCursor<T>::init_order_by_key() { } else if (node.sibling() != INVALID_LABEL) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - node_id = node.offset() ^ min_buf[i]; if (double_array_->nodes_[node_id].label() != min_buf[i]) { uint16_t label = node.child(); @@ -795,7 +788,7 @@ void DoubleArrayKeyCursor<T>::init_reverse_order_by_key() { uint64_t node_id = ROOT_NODE_ID; for (size_t i = 0; i < sizeof(T); ++i) { - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { const T key = double_array_->keys_[node.key_id()]; if ((key < max_) || @@ -804,7 +797,6 @@ void DoubleArrayKeyCursor<T>::init_reverse_order_by_key() { } return; } - uint16_t label = double_array_->nodes_[node_id].child(); if (label == TERMINAL_LABEL) { node_id = node.offset() ^ label; @@ -827,7 +819,7 @@ void DoubleArrayKeyCursor<T>::init_reverse_order_by_key() { } } - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { if (~options_.flags & MAP_CURSOR_EXCEPT_MAX) { node_ids_.push_back(node_id | POST_ORDER_FLAG); @@ -859,12 +851,10 @@ bool DoubleArrayKeyCursor<T>::next_order_by_key() { while (!node_ids_.empty()) { const uint64_t node_id = node_ids_.back(); node_ids_.pop_back(); - - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (node.sibling() != INVALID_LABEL) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { const T key = double_array_->keys_[node.key_id()]; if ((key > max_) || @@ -892,8 +882,7 @@ bool DoubleArrayKeyCursor<T>::next_reverse_order_by_key() { while (!node_ids_.empty()) { const bool post_order = node_ids_.back() & POST_ORDER_FLAG; const uint64_t node_id = node_ids_.back() & ~POST_ORDER_FLAG; - - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (post_order) { node_ids_.pop_back(); if (node.is_leaf()) { @@ -956,13 +945,15 @@ class DoubleArrayBitwiseCompletionCursor : public MapCursor<GeoPoint> { DoubleArrayBitwiseCompletionCursor::DoubleArrayBitwiseCompletionCursor( DoubleArray<GeoPoint> *double_array, GeoPoint query, size_t bit_size, const MapCursorOptions &options) - : MapCursor<GeoPoint>(), double_array_(double_array), cur_(), count_(0), - query_(query), bit_size_(bit_size), mask_(), options_(options), - node_ids_(), keys_() { + : MapCursor<GeoPoint>(), double_array_(double_array), cur_(), count_(0), + query_(query), bit_size_(bit_size), mask_(), options_(options), + node_ids_(), keys_() { if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { init_order_by_id(); } else { + options_.flags &= ~MAP_CURSOR_ORDER_BY_ID; + options_.flags |= MAP_CURSOR_ORDER_BY_KEY; init_order_by_key(); } } @@ -973,8 +964,7 @@ bool DoubleArrayBitwiseCompletionCursor::next() { if (count_ >= options_.limit) { return false; } - if ((options_.flags & MAP_CURSOR_ORDER_BY_ID) && - (~options_.flags & MAP_CURSOR_ORDER_BY_KEY)) { + if (options_.flags & MAP_CURSOR_ORDER_BY_ID) { return next_order_by_id(); } else if (~options_.flags & MAP_CURSOR_REVERSE_ORDER) { return next_order_by_key(); @@ -995,7 +985,7 @@ void DoubleArrayBitwiseCompletionCursor::init_order_by_id() { const uint64_t node_id = node_ids_.back() & ~IS_ROOT_FLAG; node_ids_.pop_back(); - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (!is_root && (node.sibling() != INVALID_LABEL)) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } @@ -1050,7 +1040,7 @@ void DoubleArrayBitwiseCompletionCursor::init_order_by_key() { uint64_t node_id = ROOT_NODE_ID; for (size_t i = 0; i < min_size; ++i) { - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (node.is_leaf()) { const GeoPoint key = double_array_->keys_[node.key_id()]; if (((key.value() ^ query_.value()) & mask_) == 0) { @@ -1061,7 +1051,6 @@ void DoubleArrayBitwiseCompletionCursor::init_order_by_key() { } return; } - node_id = node.offset() ^ query_buf[i]; if (double_array_->nodes_[node_id].label() != query_buf[i]) { return; @@ -1090,12 +1079,10 @@ bool DoubleArrayBitwiseCompletionCursor::next_order_by_key() { const bool is_root = node_ids_.back() & IS_ROOT_FLAG; const uint64_t node_id = node_ids_.back() & ~IS_ROOT_FLAG; node_ids_.pop_back(); - - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (!is_root && (node.sibling() != INVALID_LABEL)) { node_ids_.push_back(node_id ^ node.label() ^ node.sibling()); } - if (node.is_leaf()) { const GeoPoint key = double_array_->keys_[node.key_id()]; if (((key.value() ^ query_.value()) & mask_) == 0) { @@ -1119,8 +1106,7 @@ bool DoubleArrayBitwiseCompletionCursor::next_reverse_order_by_key() { while (!node_ids_.empty()) { const bool post_order = node_ids_.back() & POST_ORDER_FLAG; const uint64_t node_id = node_ids_.back() & ~POST_ORDER_FLAG; - - const DoubleArrayNodeForOthers node = double_array_->nodes_[node_id]; + const DoubleArrayNode node = double_array_->nodes_[node_id]; if (post_order) { node_ids_.pop_back(); if (node.is_leaf()) { @@ -1464,14 +1450,14 @@ MapCursor<GeoPoint> *DoubleArray<GeoPoint>::open_bitwise_completion_cursor( template <typename T> DoubleArray<T>::DoubleArray() - : pool_(), - block_info_(nullptr), - header_(nullptr), - nodes_(nullptr), - chunks_(nullptr), - entries_(nullptr), - keys_(nullptr), - initialized_(false) {} + : pool_(), + block_info_(nullptr), + header_(nullptr), + nodes_(nullptr), + chunks_(nullptr), + entries_(nullptr), + keys_(nullptr), + initialized_(false) {} template <typename T> void DoubleArray<T>::create_double_array(io::Pool pool, const MapOptions &) { Modified: lib/grnxx/alpha/map/double_array.hpp (+27 -27) =================================================================== --- lib/grnxx/alpha/map/double_array.hpp 2013-04-26 22:35:21 +0900 (5d11a6f) +++ lib/grnxx/alpha/map/double_array.hpp 2013-04-27 20:59:27 +0900 (a19f9f6) @@ -31,10 +31,16 @@ template <typename T> class DoubleArrayPrefixCursor; template <typename T> class DoubleArrayCompletionCursor; class DoubleArrayBitwiseCompletionCursor; -struct DoubleArrayHeaderForOthers; -class DoubleArrayNodeForOthers; -class DoubleArrayChunkForOthers; -class DoubleArrayEntryForOthers; +struct DoubleArrayHeader; +class DoubleArrayNode; +class DoubleArrayChunk; +class DoubleArrayEntry; + +struct SliceDoubleArrayHeader; +class SliceDoubleArrayNode; +class SliceDoubleArrayChunk; +class SliceDoubleArrayEntry; +class SliceDoubleArrayKey; class DoubleArrayException : Exception { public: @@ -51,12 +57,6 @@ class DoubleArrayException : Exception { } }; -struct DoubleArrayHeaderForSlice; -class DoubleArrayNodeForSlice; -class DoubleArrayChunkForSlice; -class DoubleArrayEntryForSlice; -class DoubleArrayKeyForSlice; - template <typename T> class DoubleArray : public Map<T> { friend class DoubleArrayIDCursor<T>; @@ -64,11 +64,6 @@ class DoubleArray : public Map<T> { friend class DoubleArrayBitwiseCompletionCursor; public: - typedef DoubleArrayHeaderForOthers DoubleArrayHeader; - typedef DoubleArrayNodeForOthers DoubleArrayNode; - typedef DoubleArrayChunkForOthers DoubleArrayChunk; - typedef DoubleArrayEntryForOthers DoubleArrayEntry; - ~DoubleArray(); static DoubleArray<T> *create(io::Pool pool, @@ -99,9 +94,11 @@ class DoubleArray : public Map<T> { MapCursor<T> *open_basic_cursor( const MapCursorOptions &options = MapCursorOptions()); - MapCursor<T> *open_id_cursor(int64_t min, int64_t max, + MapCursor<T> *open_id_cursor( + int64_t min, int64_t max, const MapCursorOptions &options = MapCursorOptions()); - MapCursor<T> *open_key_cursor(T min, T max, + MapCursor<T> *open_key_cursor( + T min, T max, const MapCursorOptions &options = MapCursorOptions()); MapCursor<T> *open_bitwise_completion_cursor( @@ -157,11 +154,11 @@ class DoubleArray<Slice> : public Map<Slice> { friend class DoubleArrayCompletionCursor<Slice>; public: - typedef DoubleArrayHeaderForSlice DoubleArrayHeader; - typedef DoubleArrayNodeForSlice DoubleArrayNode; - typedef DoubleArrayChunkForSlice DoubleArrayChunk; - typedef DoubleArrayEntryForSlice DoubleArrayEntry; - typedef DoubleArrayKeyForSlice DoubleArrayKey; + typedef SliceDoubleArrayHeader DoubleArrayHeader; + typedef SliceDoubleArrayNode DoubleArrayNode; + typedef SliceDoubleArrayChunk DoubleArrayChunk; + typedef SliceDoubleArrayEntry DoubleArrayEntry; + typedef SliceDoubleArrayKey DoubleArrayKey; ~DoubleArray(); @@ -196,15 +193,18 @@ class DoubleArray<Slice> : public Map<Slice> { MapCursor<Slice> *open_basic_cursor( const MapCursorOptions &options = MapCursorOptions()); - MapCursor<Slice> *open_id_cursor(int64_t min, int64_t max, + MapCursor<Slice> *open_id_cursor( + int64_t min, int64_t max, const MapCursorOptions &options = MapCursorOptions()); - MapCursor<Slice> *open_key_cursor(Slice min, Slice max, + MapCursor<Slice> *open_key_cursor( + Slice min, Slice max, const MapCursorOptions &options = MapCursorOptions()); - MapCursor<Slice> *open_prefix_cursor(Slice query, size_t min_size, - const MapCursorOptions &options = MapCursorOptions()); - MapCursor<Slice> *open_completion_cursor(Slice query, + MapCursor<Slice> *open_prefix_cursor( + Slice query, size_t min_size, const MapCursorOptions &options = MapCursorOptions()); + MapCursor<Slice> *open_completion_cursor( + Slice query, const MapCursorOptions &options = MapCursorOptions()); private: io::Pool pool_; Modified: test/test_alpha_map.cpp (+24 -4) =================================================================== --- test/test_alpha_map.cpp 2013-04-26 22:35:21 +0900 (b7dbaf0) +++ test/test_alpha_map.cpp 2013-04-27 20:59:27 +0900 (4f709dc) @@ -256,29 +256,47 @@ void test_key_cursor(const std::unique_ptr<Map<T>> &map) { std::swap(min_key, max_key); } - std::unique_ptr<MapCursor<T>> cursor( - map->open_key_cursor(min_key, max_key)); + std::unique_ptr<MapCursor<T>> cursor; + cursor.reset(map->open_key_cursor(min_key, max_key)); + size_t basic_count = 0; while (cursor->next()) { assert(cursor->key() >= min_key); assert(cursor->key() <= max_key); + ++basic_count; } assert(!cursor->next()); grnxx::alpha::MapCursorOptions options; - options.flags |= grnxx::alpha::MAP_CURSOR_EXCEPT_MIN | - grnxx::alpha::MAP_CURSOR_EXCEPT_MAX; + options.flags = grnxx::alpha::MAP_CURSOR_EXCEPT_MIN | + grnxx::alpha::MAP_CURSOR_EXCEPT_MAX; cursor.reset(map->open_key_cursor(min_key, max_key, options)); + size_t count = 0; while (cursor->next()) { assert(cursor->key() > min_key); assert(cursor->key() < max_key); + ++count; + } + assert(!cursor->next()); + assert(count <= basic_count); + + options.flags = grnxx::alpha::MAP_CURSOR_ORDER_BY_ID; + cursor.reset(map->open_key_cursor(min_key, max_key, options)); + count = 0; + while (cursor->next()) { + assert(cursor->key() >= min_key); + assert(cursor->key() <= max_key); + ++count; } assert(!cursor->next()); + assert(count == basic_count); options.flags = grnxx::alpha::MAP_CURSOR_ORDER_BY_KEY; cursor.reset(map->open_key_cursor(min_key, max_key, options)); + count = 0; if (cursor->next()) { assert(cursor->key() >= min_key); assert(cursor->key() <= max_key); + ++count; } T prev_key = cursor->key(); while (cursor->next()) { @@ -286,8 +304,10 @@ void test_key_cursor(const std::unique_ptr<Map<T>> &map) { assert(cursor->key() <= max_key); assert(prev_key < cursor->key()); prev_key = cursor->key(); + ++count; } assert(!cursor->next()); + assert(count == basic_count); } void test_key_cursor( -------------- next part -------------- HTML����������������������������...Download