susumu.yata
null+****@clear*****
Fri Mar 15 13:18:55 JST 2013
susumu.yata 2013-03-15 13:18:55 +0900 (Fri, 15 Mar 2013) New Revision: 03e43a8158d12ee4d4b00bc4b599b7c13c6959b8 https://github.com/groonga/grnxx/commit/03e43a8158d12ee4d4b00bc4b599b7c13c6959b8 Message: Implement grnxx::map::da::basic::IDCursor. Added files: lib/map/da/basic/Makefile.am lib/map/da/basic/id_cursor.cpp lib/map/da/basic/id_cursor.hpp lib/map/da/large/Makefile.am Modified files: configure.ac lib/map.cpp lib/map.hpp lib/map/da/Makefile.am lib/map/da/trie.cpp lib/map/da/trie.hpp lib/map/double_array.cpp lib/map/double_array.hpp Renamed files: lib/map/da/basic/trie.cpp (from lib/map/da/basic_trie.cpp) lib/map/da/basic/trie.hpp (from lib/map/da/basic_trie.hpp) lib/map/da/large/trie.cpp (from lib/map/da/large_trie.cpp) lib/map/da/large/trie.hpp (from lib/map/da/large_trie.hpp) Modified: configure.ac (+2 -0) =================================================================== --- configure.ac 2013-03-14 12:28:33 +0900 (054aa60) +++ configure.ac 2013-03-15 13:18:55 +0900 (6986ad4) @@ -65,6 +65,8 @@ AC_CONFIG_FILES([Makefile lib/io/Makefile lib/map/Makefile lib/map/da/Makefile + lib/map/da/basic/Makefile + lib/map/da/large/Makefile lib/time/Makefile src/Makefile test/Makefile]) Modified: lib/map.cpp (+1 -1) =================================================================== --- lib/map.cpp 2013-03-14 12:28:33 +0900 (c7e4a90) +++ lib/map.cpp 2013-03-15 13:18:55 +0900 (3788ef1) @@ -28,7 +28,7 @@ MapOptions::MapOptions() : type(MAP_UNKNOWN) {} MapHeader::MapHeader() : type(MAP_UNKNOWN) {} -MapCursor::MapCursor() : map_(nullptr), key_id_(-1), key_() {} +MapCursor::MapCursor() : key_id_(-1), key_() {} MapCursor::~MapCursor() {} MapScan::~MapScan() {} Modified: lib/map.hpp (+16 -23) =================================================================== --- lib/map.hpp 2013-03-14 12:28:33 +0900 (934ae29) +++ lib/map.hpp 2013-03-15 13:18:55 +0900 (d648211) @@ -133,9 +133,6 @@ class MapCursor { // Move the cursor to the next key and return true on success. virtual bool next() = 0; - // Remove the current key and return true on success. - virtual bool remove_key() = 0; - // Return the ID of the current key. int64_t key_id() const { return key_id_; @@ -146,7 +143,6 @@ class MapCursor { } protected: - Map *map_; int64_t key_id_; MapKey key_; }; @@ -154,20 +150,17 @@ class MapCursor { typedef FlagsImpl<MapCursor> MapCursorFlags; // Get keys in ascending order. -constexpr MapCursorFlags MAP_CURSOR_ASCENDING = +constexpr MapCursorFlags MAP_CURSOR_ASCENDING = MapCursorFlags::define(0x01); // Get keys in descending order. -constexpr MapCursorFlags MAP_CURSOR_DESCENDING = +constexpr MapCursorFlags MAP_CURSOR_DESCENDING = MapCursorFlags::define(0x02); -// Get keys except the begin. -constexpr MapCursorFlags MAP_CURSOR_EXCEPT_BEGIN = +// Get keys except "min". +constexpr MapCursorFlags MAP_CURSOR_EXCEPT_MIN = MapCursorFlags::define(0x10); -// Get keys except the end. -constexpr MapCursorFlags MAP_CURSOR_EXCEPT_END = +// Get keys except "max". +constexpr MapCursorFlags MAP_CURSOR_EXCEPT_MAX = MapCursorFlags::define(0x20); -// Get keys except the exact match. -constexpr MapCursorFlags MAP_CURSOR_EXCEPT_QUERY = - MapCursorFlags::define(0x40); class MapScan { public: @@ -264,27 +257,27 @@ class Map { // The object must be deleted after the scan. MapScan *open_scan(const Slice &query, const Charset *charset = nullptr); - // Find keys in an ID range ["begin", "end"] and return the keys in ID order. + // Find keys in an ID range ["min", "max"] and return the keys in ID order. // "flags" accepts MAP_CURSOR_ASCENDING, MAP_CURSOR_DESCENDING, - // MAP_CURSOR_EXCEPT_BEGIN, and MAP_CURSOR_EXCEPT_END. + // MAP_CURSOR_EXCEPT_MIN, and MAP_CURSOR_EXCEPT_MAX. virtual MapCursor *open_id_cursor(MapCursorFlags flags, - int64_t begin, int64_t end, + int64_t min, int64_t max, int64_t offset, int64_t limit) = 0; - // Find keys in a range ["begin", "end"] and return the keys in lexicographic + // Find keys in a range ["min", "max"] and return the keys in lexicographic // order. "flags" accepts MAP_CURSOR_ASCENDING, MAP_CURSOR_DESCENDING, - // MAP_CURSOR_EXCEPT_BEGIN, and MAP_CURSOR_EXCEPT_END. + // MAP_CURSOR_EXCEPT_MIN, and MAP_CURSOR_EXCEPT_MAX. virtual MapCursor *open_key_cursor(MapCursorFlags flags, - const Slice &begin, const Slice &end, + const Slice &min, const Slice &max, int64_t offset, int64_t limit) = 0; // Find keys in prefixes of "query". "flags" accepts MAP_CURSOR_ASCENDING, - // MAP_CURSOR_DESCENDING, and MAP_CURSOR_EXCEPT_QUERY. + // MAP_CURSOR_DESCENDING, and MAP_CURSOR_EXCEPT_MAX. virtual MapCursor *open_prefix_cursor(MapCursorFlags flags, - const Slice &query, + const Slice &max, int64_t offset, int64_t limit) = 0; // Find keys starting with "query". "flags" accepts MAP_CURSOR_ASCENDING, - // MAP_CURSOR_DESCENDING, and MAP_CURSOR_EXCEPT_QUERY. + // MAP_CURSOR_DESCENDING, and MAP_CURSOR_EXCEPT_MIN. virtual MapCursor *open_predictive_cursor(MapCursorFlags flags, - const Slice &query, + const Slice &min, int64_t offset, int64_t limit) = 0; }; Modified: lib/map/da/Makefile.am (+6 -4) =================================================================== --- lib/map/da/Makefile.am 2013-03-14 12:28:33 +0900 (7e5450a) +++ lib/map/da/Makefile.am 2013-03-15 13:18:55 +0900 (b1834ec) @@ -1,14 +1,16 @@ +SUBDIRS = basic large + noinst_LTLIBRARIES = libgrnxx_map_da.la +libgrnxx_map_da_la_LIBADD = \ + basic/libgrnxx_map_da_basic.la \ + large/libgrnxx_map_da_large.la + libgrnxx_map_da_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_map_da_la_SOURCES = \ - basic_trie.cpp \ - large_trie.cpp \ trie.cpp libgrnxx_map_da_includedir = ${includedir}/grnxx/map/da libgrnxx_map_da_include_HEADERS = \ - basic_trie.hpp \ - large_trie.hpp \ trie.hpp Added: lib/map/da/basic/Makefile.am (+12 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/Makefile.am 2013-03-15 13:18:55 +0900 (f81070d) @@ -0,0 +1,12 @@ +noinst_LTLIBRARIES = libgrnxx_map_da_basic.la + +libgrnxx_map_da_basic_la_LDFLAGS = @AM_LTLDFLAGS@ + +libgrnxx_map_da_basic_la_SOURCES = \ + id_cursor.cpp \ + trie.cpp + +libgrnxx_map_da_basic_includedir = ${includedir}/grnxx/map/da/basic +libgrnxx_map_da_basic_include_HEADERS = \ + id_cursor.hpp \ + trie.hpp Added: lib/map/da/basic/id_cursor.cpp (+90 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/id_cursor.cpp 2013-03-15 13:18:55 +0900 (076e3d1) @@ -0,0 +1,90 @@ +#include "map/da/basic/id_cursor.hpp" + +#include "exception.hpp" +#include "logger.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace basic { + +IDCursor::~IDCursor() {} + +IDCursor *IDCursor::open(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) { + std::unique_ptr<IDCursor> cursor(new (std::nothrow) IDCursor); + if (!cursor) { + GRNXX_ERROR() << "new grnxx::map::da::large::IDCursor failed"; + GRNXX_THROW(); + } + cursor->open_cursor(trie, flags, min, max, offset, limit); + return cursor.release(); +} + +bool IDCursor::next() { + if (limit_ <= 0) { + return false; + } + while (current_ != end_) { + const Entry entry = trie_->entries_[current_]; + if (entry) { + key_id_ = current_; + key_ = trie_->get_key(entry.key_pos()).slice(); + current_ += step_; + --limit_; + return true; + } + current_ += step_; + } + return false; +} + +IDCursor::IDCursor() + : MapCursor(), + trie_(), + current_(), + end_(), + step_(), + limit_() {} + +void IDCursor::open_cursor(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) { + trie_ = trie; + + if (min < 0) { + min = 0; + } else if (flags & MAP_CURSOR_EXCEPT_MIN) { + ++min; + } + + if ((max < 0) || (max > trie->header_->max_key_id)) { + max = trie->header_->max_key_id; + } else if (flags & MAP_CURSOR_EXCEPT_MAX) { + --max; + } + + if (flags & MAP_CURSOR_DESCENDING) { + current_ = max; + end_ = min - 1; + step_ = -1; + } else { + current_ = min; + end_ = max + 1; + step_ = 1; + } + + while ((current_ != end_) && (offset > 0)) { + if (trie->entries_[current_]) { + --offset; + } + current_ += step_; + } + limit_ = (limit >= 0) ? limit : std::numeric_limits<int64_t>::max(); +} + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx Added: lib/map/da/basic/id_cursor.hpp (+57 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/basic/id_cursor.hpp 2013-03-15 13:18:55 +0900 (212275f) @@ -0,0 +1,57 @@ +/* + Copyright (C) 2013 Brazil, Inc. + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + 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-1301 USA +*/ +#ifndef GRNXX_MAP_DA_BASIC_ID_CURSOR_HPP +#define GRNXX_MAP_DA_BASIC_ID_CURSOR_HPP + +#include "map/da/basic/trie.hpp" + +namespace grnxx { +namespace map { +namespace da { +namespace basic { + +class IDCursor : public MapCursor { + public: + ~IDCursor(); + + static IDCursor *open(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit); + + bool next(); + + private: + Trie *trie_; + int64_t current_; + int64_t end_; + int64_t step_; + int64_t limit_; + + IDCursor(); + + void open_cursor(Trie *trie, MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit); +}; + +} // namespace basic +} // namespace da +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DA_BASIC_ID_CURSOR_HPP Renamed: lib/map/da/basic/trie.cpp (+31 -2) 97% =================================================================== --- lib/map/da/basic_trie.cpp 2013-03-14 12:28:33 +0900 (15f0b63) +++ lib/map/da/basic/trie.cpp 2013-03-15 13:18:55 +0900 (d123c6b) @@ -1,8 +1,9 @@ -#include "map/da/basic_trie.hpp" +#include "map/da/basic/trie.hpp" #include "lock.hpp" #include "logger.hpp" -#include "map/da/large_trie.hpp" +#include "map/da/basic/id_cursor.hpp" +#include "map/da/large/trie.hpp" namespace grnxx { namespace map { @@ -337,6 +338,34 @@ bool Trie::update(const Slice &src_key, const Slice &dest_key, return false; } +MapCursor *Trie::open_id_cursor(MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + +MapCursor *Trie::open_key_cursor(MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + +MapCursor *Trie::open_prefix_cursor(MapCursorFlags flags, + const Slice &max, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + +MapCursor *Trie::open_predictive_cursor(MapCursorFlags flags, + const Slice &min, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + Trie::Trie() : pool_(), block_info_(nullptr), Renamed: lib/map/da/basic/trie.hpp (+13 -0) 95% =================================================================== --- lib/map/da/basic_trie.hpp 2013-03-14 12:28:33 +0900 (80e0a1a) +++ lib/map/da/basic/trie.hpp 2013-03-15 13:18:55 +0900 (f6a2a8c) @@ -86,6 +86,8 @@ constexpr uint32_t MAX_CHUNK_LEVEL = 5; // the linked list is empty and there exists no leader. constexpr uint32_t INVALID_LEADER = std::numeric_limits<uint32_t>::max(); +class IDCursor; + struct Header { TrieType type; uint32_t nodes_block_id; @@ -418,6 +420,7 @@ class Key { class Trie : public da::Trie { friend class large::Trie; + friend class IDCursor; public: ~Trie(); @@ -446,6 +449,16 @@ class Trie : public da::Trie { bool update(const Slice &src_key, const Slice &dest_key, int64_t *key_id = nullptr); + MapCursor *open_id_cursor(MapCursorFlags flags, int64_t min, int64_t max, + int64_t offset, int64_t limit); + MapCursor *open_key_cursor(MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit); + MapCursor *open_prefix_cursor(MapCursorFlags flags, const Slice &max, + int64_t offset, int64_t limit); + MapCursor *open_predictive_cursor(MapCursorFlags flags, const Slice &min, + int64_t offset, int64_t limit); + private: io::Pool pool_; const io::BlockInfo *block_info_; Added: lib/map/da/large/Makefile.am (+10 -0) 100644 =================================================================== --- /dev/null +++ lib/map/da/large/Makefile.am 2013-03-15 13:18:55 +0900 (c24fd63) @@ -0,0 +1,10 @@ +noinst_LTLIBRARIES = libgrnxx_map_da_large.la + +libgrnxx_map_da_large_la_LDFLAGS = @AM_LTLDFLAGS@ + +libgrnxx_map_da_large_la_SOURCES = \ + trie.cpp + +libgrnxx_map_da_large_includedir = ${includedir}/grnxx/map/da/large +libgrnxx_map_da_large_include_HEADERS = \ + trie.hpp Renamed: lib/map/da/large/trie.cpp (+29 -1) 97% =================================================================== --- lib/map/da/large_trie.cpp 2013-03-14 12:28:33 +0900 (a9a073d) +++ lib/map/da/large/trie.cpp 2013-03-15 13:18:55 +0900 (f062efe) @@ -1,4 +1,4 @@ -#include "map/da/large_trie.hpp" +#include "map/da/large/trie.hpp" #include "lock.hpp" #include "logger.hpp" @@ -349,6 +349,34 @@ bool Trie::update(const Slice &src_key, const Slice &dest_key, return false; } +MapCursor *Trie::open_id_cursor(MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + +MapCursor *Trie::open_key_cursor(MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + +MapCursor *Trie::open_prefix_cursor(MapCursorFlags flags, + const Slice &max, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + +MapCursor *Trie::open_predictive_cursor(MapCursorFlags flags, + const Slice &min, + int64_t offset, int64_t limit) { + // TODO + return nullptr; +} + Trie::Trie() : pool_(), block_info_(nullptr), Renamed: lib/map/da/large/trie.hpp (+11 -1) 96% =================================================================== --- lib/map/da/large_trie.hpp 2013-03-14 12:28:33 +0900 (e89d1b3) +++ lib/map/da/large/trie.hpp 2013-03-15 13:18:55 +0900 (06dc45d) @@ -18,7 +18,7 @@ #ifndef GRNXX_MAP_DA_LARGE_TRIE_HPP #define GRNXX_MAP_DA_LARGE_TRIE_HPP -#include "map/da/basic_trie.hpp" +#include "map/da/basic/trie.hpp" namespace grnxx { namespace map { @@ -441,6 +441,16 @@ class Trie : public da::Trie { bool update(const Slice &src_key, const Slice &dest_key, int64_t *key_id = nullptr); + MapCursor *open_id_cursor(MapCursorFlags flags, int64_t min, int64_t max, + int64_t offset, int64_t limit); + MapCursor *open_key_cursor(MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit); + MapCursor *open_prefix_cursor(MapCursorFlags flags, const Slice &max, + int64_t offset, int64_t limit); + MapCursor *open_predictive_cursor(MapCursorFlags flags, const Slice &min, + int64_t offset, int64_t limit); + private: io::Pool pool_; const io::BlockInfo *block_info_; Modified: lib/map/da/trie.cpp (+2 -2) =================================================================== --- lib/map/da/trie.cpp 2013-03-14 12:28:33 +0900 (09e84e5) +++ lib/map/da/trie.cpp 2013-03-15 13:18:55 +0900 (d907662) @@ -1,8 +1,8 @@ #include "map/da/trie.hpp" #include "logger.hpp" -#include "map/da/basic_trie.hpp" -#include "map/da/large_trie.hpp" +#include "map/da/basic/trie.hpp" +#include "map/da/large/trie.hpp" namespace grnxx { namespace map { Modified: lib/map/da/trie.hpp (+13 -0) =================================================================== --- lib/map/da/trie.hpp 2013-03-14 12:28:33 +0900 (95e7bed) +++ lib/map/da/trie.hpp 2013-03-15 13:18:55 +0900 (22ffc22) @@ -82,6 +82,19 @@ class Trie { virtual bool update(int64_t key_id, const Slice &dest_key) = 0; virtual bool update(const Slice &src_key, const Slice &dest_key, int64_t *key_id = nullptr) = 0; + + virtual MapCursor *open_id_cursor(MapCursorFlags flags, + int64_t min, int64_t max, + int64_t offset, int64_t limit) = 0; + virtual MapCursor *open_key_cursor(MapCursorFlags flags, + const Slice &min, const Slice &max, + int64_t offset, int64_t limit) = 0; + virtual MapCursor *open_prefix_cursor(MapCursorFlags flags, + const Slice &max, + int64_t offset, int64_t limit) = 0; + virtual MapCursor *open_predictive_cursor(MapCursorFlags flags, + const Slice &min, + int64_t offset, int64_t limit) = 0; }; } // namespace da Modified: lib/map/double_array.cpp (+28 -12) =================================================================== --- lib/map/double_array.cpp 2013-03-14 12:28:33 +0900 (b772820) +++ lib/map/double_array.cpp 2013-03-15 13:18:55 +0900 (ace2213) @@ -155,31 +155,47 @@ bool DoubleArray::update(const Slice &src_key, const Slice &dest_key, } MapCursor *DoubleArray::open_id_cursor(MapCursorFlags flags, - int64_t begin, int64_t end, + int64_t min, int64_t max, int64_t offset, int64_t limit) { - // TODO - return nullptr; + open_trie_if_needed(); + if (!front_) { + // TODO + return nullptr; + } + return front_->open_id_cursor(flags, min, max, offset, limit); } MapCursor *DoubleArray::open_key_cursor(MapCursorFlags flags, - const Slice &begin, const Slice &end, + const Slice &min, const Slice &max, int64_t offset, int64_t limit) { - // TODO - return nullptr; + open_trie_if_needed(); + if (!front_) { + // TODO + return nullptr; + } + return front_->open_key_cursor(flags, min, max, offset, limit); } MapCursor *DoubleArray::open_prefix_cursor(MapCursorFlags flags, - const Slice &query, + const Slice &max, int64_t offset, int64_t limit) { - // TODO - return nullptr; + open_trie_if_needed(); + if (!front_) { + // TODO + return nullptr; + } + return front_->open_prefix_cursor(flags, max, offset, limit); } MapCursor *DoubleArray::open_predictive_cursor(MapCursorFlags flags, - const Slice &query, + const Slice &min, int64_t offset, int64_t limit) { - // TODO - return nullptr; + open_trie_if_needed(); + if (!front_) { + // TODO + return nullptr; + } + return front_->open_predictive_cursor(flags, min, offset, limit); } DoubleArray::DoubleArray() Modified: lib/map/double_array.hpp (+4 -4) =================================================================== --- lib/map/double_array.hpp 2013-03-14 12:28:33 +0900 (fe3c837) +++ lib/map/double_array.hpp 2013-03-15 13:18:55 +0900 (e5e281f) @@ -58,14 +58,14 @@ class DoubleArray : public Map { bool update(const Slice &src_key, const Slice &dest_key, int64_t *key_id = nullptr); - MapCursor *open_id_cursor(MapCursorFlags flags, int64_t begin, int64_t end, + MapCursor *open_id_cursor(MapCursorFlags flags, int64_t min, int64_t max, int64_t offset, int64_t limit); MapCursor *open_key_cursor(MapCursorFlags flags, - const Slice &begin, const Slice &end, + const Slice &min, const Slice &max, int64_t offset, int64_t limit); - MapCursor *open_prefix_cursor(MapCursorFlags flags, const Slice &query, + MapCursor *open_prefix_cursor(MapCursorFlags flags, const Slice &max, int64_t offset, int64_t limit); - MapCursor *open_predictive_cursor(MapCursorFlags flags, const Slice &query, + MapCursor *open_predictive_cursor(MapCursorFlags flags, const Slice &min, int64_t offset, int64_t limit); private: -------------- next part -------------- HTML����������������������������...Download