susumu.yata
null+****@clear*****
Tue Apr 9 11:17:38 JST 2013
susumu.yata 2013-04-09 11:17:38 +0900 (Tue, 09 Apr 2013) New Revision: 6e9594eab15290c247ec81eb03b6838413651a86 https://github.com/groonga/grnxx/commit/6e9594eab15290c247ec81eb03b6838413651a86 Message: Add cursors for grnxx::alpha::map::Array. Added files: lib/grnxx/alpha/map/cursor.cpp lib/grnxx/alpha/map/cursor.hpp Modified files: lib/grnxx/alpha/map.cpp lib/grnxx/alpha/map.hpp lib/grnxx/alpha/map/Makefile.am lib/grnxx/alpha/map/array.cpp lib/grnxx/alpha/map/array.hpp test/test_alpha_map.cpp Modified: lib/grnxx/alpha/map.cpp (+26 -0) =================================================================== --- lib/grnxx/alpha/map.cpp 2013-04-09 10:34:23 +0900 (263d9cf) +++ lib/grnxx/alpha/map.cpp 2013-04-09 11:17:38 +0900 (5c8e595) @@ -18,6 +18,7 @@ #include "grnxx/alpha/map.hpp" #include "grnxx/alpha/map/array.hpp" +#include "grnxx/alpha/map/cursor.hpp" #include "grnxx/slice.hpp" namespace grnxx { @@ -116,6 +117,12 @@ MapType Map<T>::type() const { } template <typename T> +int64_t Map<T>::max_key_id() const { + // Not supported. + return -1; +} + +template <typename T> bool Map<T>::get(int64_t, T *) { // Not supported. return false; @@ -162,6 +169,25 @@ void Map<T>::truncate() { // Not supported. } +template <typename T> +MapCursor<T> *Map<T>::open_basic_cursor(const MapCursorOptions &) { + // Not supported. + return nullptr; +} + +template <typename T> +MapCursor<T> *Map<T>::open_id_cursor(int64_t, int64_t, + const MapCursorOptions &) { + // Not supported. + return nullptr; +} + +template <typename T> +MapCursor<T> *Map<T>::open_key_cursor(T, T, const MapCursorOptions &) { + // Not supported. + return nullptr; +} + template class Map<int8_t>; template class Map<int16_t>; template class Map<int32_t>; Modified: lib/grnxx/alpha/map.hpp (+33 -2) =================================================================== --- lib/grnxx/alpha/map.hpp 2013-04-09 10:34:23 +0900 (f8b15ce) +++ lib/grnxx/alpha/map.hpp 2013-04-09 11:17:38 +0900 (211291c) @@ -78,7 +78,27 @@ struct MapHeader { MapType type; }; -// TODO: Not supported yet. +struct MapCursorFlagsIdentifier; +typedef FlagsImpl<MapCursorFlagsIdentifier> MapCursorFlags; + +// Sort keys by ID. +constexpr MapCursorFlags MAP_CURSOR_ORDER_BY_ID = + MapCursorFlags::define(0x01); +// Sort keys by key. +constexpr MapCursorFlags MAP_CURSOR_ORDER_BY_KEY = + MapCursorFlags::define(0x02); +// Access keys in reverse order. +constexpr MapCursorFlags MAP_CURSOR_REVERSE_ORDER = + MapCursorFlags::define(0x10); + +struct MapCursorOptions { + MapCursorFlags flags; + uint64_t offset; + uint64_t limit; + + constexpr MapCursorOptions() : flags(), offset(0), limit(-1) {} +}; + template <typename T> class MapCursor { public: @@ -100,7 +120,7 @@ class MapCursor { return key_; } - private: + protected: int64_t key_id_; T key_; }; @@ -125,6 +145,10 @@ class Map { // Return the type of "*this". virtual MapType type() const; + // Return the maximum key ID ever used. + // If the map is empty, the return value can be -1. + virtual int64_t max_key_id() const; + // Get a key associated with "key_id" and return true on success. // Assign the found key to "*key" iff "key" != nullptr. virtual bool get(int64_t key_id, T *key = nullptr); @@ -148,6 +172,13 @@ class Map { // Remove all the keys in "*this". virtual void truncate(); + + virtual MapCursor<T> *open_basic_cursor( + const MapCursorOptions &options = MapCursorOptions()); + virtual MapCursor<T> *open_id_cursor(int64_t min, int64_t max, + const MapCursorOptions &options = MapCursorOptions()); + virtual MapCursor<T> *open_key_cursor(T min, T max, + const MapCursorOptions &options = MapCursorOptions()); }; } // namespace alpha Modified: lib/grnxx/alpha/map/Makefile.am (+4 -2) =================================================================== --- lib/grnxx/alpha/map/Makefile.am 2013-04-09 10:34:23 +0900 (8586a95) +++ lib/grnxx/alpha/map/Makefile.am 2013-04-09 11:17:38 +0900 (3331d78) @@ -3,8 +3,10 @@ noinst_LTLIBRARIES = libgrnxx_alpha_map.la libgrnxx_alpha_map_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_alpha_map_la_SOURCES = \ - array.cpp + array.cpp \ + cursor.cpp libgrnxx_alpha_map_includedir = ${includedir}/grnxx/alpha/map libgrnxx_alpha_map_include_HEADERS = \ - array.hpp + array.hpp \ + cursor.hpp Modified: lib/grnxx/alpha/map/array.cpp (+51 -0) =================================================================== --- lib/grnxx/alpha/map/array.cpp 2013-04-09 10:34:23 +0900 (6533f2e) +++ lib/grnxx/alpha/map/array.cpp 2013-04-09 11:17:38 +0900 (c577779) @@ -20,6 +20,8 @@ #include <cmath> #include <string> +#include "grnxx/alpha/map/cursor.hpp" + namespace grnxx { namespace alpha { namespace map { @@ -116,6 +118,11 @@ MapType Array<T>::type() const { } template <typename T> +int64_t Array<T>::max_key_id() const { + return header_->max_key_id; +} + +template <typename T> bool Array<T>::get(int64_t key_id, T *key) { if ((key_id < 0) || (key_id > header_->max_key_id)) { return false; @@ -233,6 +240,30 @@ void Array<T>::truncate() { } template <typename T> +MapCursor<T> *Array<T>::open_basic_cursor(const MapCursorOptions &options) { + return new (std::nothrow) IDCursor<T>(this, 0, header_->max_key_id, options); +} + +template <typename T> +MapCursor<T> *Array<T>::open_id_cursor(int64_t min, int64_t max, + const MapCursorOptions &options) { + return new (std::nothrow) IDCursor<T>(this, min, max, options); +} + +template <typename T> +MapCursor<T> *Array<T>::open_key_cursor(T min, T max, + const MapCursorOptions &options) { + return new (std::nothrow) KeyCursor<T>(this, min, max, options); +} + +template <> +MapCursor<GeoPoint> *Array<GeoPoint>::open_key_cursor( + GeoPoint, GeoPoint, const MapCursorOptions &) { + // Not supported. + return nullptr; +} + +template <typename T> Array<T>::Array() : pool_(), block_info_(nullptr), @@ -290,6 +321,10 @@ MapType Array<Slice>::type() const { return MAP_ARRAY; } +int64_t Array<Slice>::max_key_id() const { + return header_->max_key_id; +} + bool Array<Slice>::get(int64_t key_id, Slice *key) { if ((key_id < 0) || (key_id > header_->max_key_id)) { return false; @@ -405,6 +440,22 @@ void Array<Slice>::truncate() { header_->max_key_id = -1; } +MapCursor<Slice> *Array<Slice>::open_basic_cursor( + const MapCursorOptions &options) { + return new (std::nothrow) IDCursor<Slice>( + this, 0, header_->max_key_id, options); +} + +MapCursor<Slice> *Array<Slice>::open_id_cursor( + int64_t min, int64_t max, const MapCursorOptions &options) { + return new (std::nothrow) IDCursor<Slice>(this, min, max, options); +} + +MapCursor<Slice> *Array<Slice>::open_key_cursor( + Slice min, Slice max, const MapCursorOptions &options) { + return new (std::nothrow) KeyCursor<Slice>(this, min, max, options); +} + Array<Slice>::Array() : pool_(), block_info_(nullptr), Modified: lib/grnxx/alpha/map/array.hpp (+18 -0) =================================================================== --- lib/grnxx/alpha/map/array.hpp 2013-04-09 10:34:23 +0900 (50e1f7f) +++ lib/grnxx/alpha/map/array.hpp 2013-04-09 11:17:38 +0900 (5307c8f) @@ -49,6 +49,8 @@ class Array : public grnxx::alpha::Map<T> { uint32_t block_id() const; MapType type() const; + int64_t max_key_id() const; + bool get(int64_t key_id, T *key = nullptr); bool unset(int64_t key_id); bool reset(int64_t key_id, T dest_key); @@ -60,6 +62,13 @@ class Array : public grnxx::alpha::Map<T> { void truncate(); + MapCursor<T> *open_basic_cursor( + const MapCursorOptions &options = MapCursorOptions()); + MapCursor<T> *open_id_cursor(int64_t min, int64_t max, + const MapCursorOptions &options = MapCursorOptions()); + MapCursor<T> *open_key_cursor(T min, T max, + const MapCursorOptions &options = MapCursorOptions()); + private: io::Pool pool_; const io::BlockInfo *block_info_; @@ -95,6 +104,8 @@ class Array<Slice> : public grnxx::alpha::Map<Slice> { uint32_t block_id() const; MapType type() const; + int64_t max_key_id() const; + bool get(int64_t key_id, Slice *key = nullptr); bool unset(int64_t key_id); bool reset(int64_t key_id, Slice dest_key); @@ -106,6 +117,13 @@ class Array<Slice> : public grnxx::alpha::Map<Slice> { void truncate(); + MapCursor<Slice> *open_basic_cursor( + const MapCursorOptions &options = MapCursorOptions()); + MapCursor<Slice> *open_id_cursor(int64_t min, int64_t max, + const MapCursorOptions &options = MapCursorOptions()); + MapCursor<Slice> *open_key_cursor(Slice min, Slice max, + const MapCursorOptions &options = MapCursorOptions()); + private: io::Pool pool_; const io::BlockInfo *block_info_; Added: lib/grnxx/alpha/map/cursor.cpp (+166 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map/cursor.cpp 2013-04-09 11:17:38 +0900 (dd1583b) @@ -0,0 +1,166 @@ +/* + 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 +*/ +#include "grnxx/alpha/map/cursor.hpp" + +namespace grnxx { +namespace alpha { +namespace map { + +template <typename T> +IDCursor<T>::IDCursor(Map<T> *map, int64_t min, int64_t max, + const MapCursorOptions &options) + : MapCursor<T>(), map_(map), end_(), step_(), left_(options.limit) { + // TODO? +// if (options.flags & MAP_CURSOR_ORDER_BY_ID) { +// } else if (options.flags & MAP_CURSOR_ORDER_BY_KEY) { +// } + + if (min < 0) { + min = 0; + } + // EXCEPT_MIN + + if (max > map_->max_key_id()) { + max = map_->max_key_id(); + } + // EXCEPT_MAX + + if (~options.flags & MAP_CURSOR_REVERSE_ORDER) { + this->key_id_ = min - 1; + end_ = max; + step_ = 1; + } else { + this->key_id_ = max + 1; + end_ = min; + step_ = -1; + } + + uint64_t count = 0; + while ((count < options.offset) && (this->key_id_ != end_)) { + this->key_id_ += step_; + if (map_->get(this->key_id_)) { + ++count; + } + } +} + +template <typename T> +IDCursor<T>::~IDCursor() {} + +template <typename T> +bool IDCursor<T>::next() { + if (left_ == 0) { + return false; + } + while (this->key_id_ != end_) { + this->key_id_ += step_; + if (map_->get(this->key_id_, &this->key_)) { + --left_; + return true; + } + } + return false; +} + +template <typename T> +bool IDCursor<T>::remove() { + return map_->unset(this->key_id_); +} + +template class IDCursor<int8_t>; +template class IDCursor<int16_t>; +template class IDCursor<int32_t>; +template class IDCursor<int64_t>; +template class IDCursor<uint8_t>; +template class IDCursor<uint16_t>; +template class IDCursor<uint32_t>; +template class IDCursor<uint64_t>; +template class IDCursor<double>; +template class IDCursor<GeoPoint>; +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) { + // TODO? +// if (options.flags & MAP_CURSOR_ORDER_BY_ID) { +// } else if (options.flags & MAP_CURSOR_ORDER_BY_KEY) { +// } + + uint64_t count = 0; + if (~flags_ & MAP_CURSOR_REVERSE_ORDER) { + this->key_id_ = -1; + end_ = map_->max_key_id(); + step_ = 1; + } else { + this->key_id_ = 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_)) { + if ((this->key_ >= min_) && (this->key_ <= max_)) { + ++count; + } + } + } +} + +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 ((this->key_ >= min_) && (this->key_ <= max_)) { + --left_; + return true; + } + } + } + return false; +} + +template <typename T> +bool KeyCursor<T>::remove() { + return map_->unset(this->key_id_); +} + +template class KeyCursor<int8_t>; +template class KeyCursor<int16_t>; +template class KeyCursor<int32_t>; +template class KeyCursor<int64_t>; +template class KeyCursor<uint8_t>; +template class KeyCursor<uint16_t>; +template class KeyCursor<uint32_t>; +template class KeyCursor<uint64_t>; +template class KeyCursor<double>; +template class KeyCursor<Slice>; + +} // namespace map +} // namespace alpha +} // namespace grnxx Added: lib/grnxx/alpha/map/cursor.hpp (+68 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/alpha/map/cursor.hpp 2013-04-09 11:17:38 +0900 (c2b3748) @@ -0,0 +1,68 @@ +/* + 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_ALPHA_MAP_CURSOR_HPP +#define GRNXX_ALPHA_MAP_CURSOR_HPP + +#include "grnxx/alpha/map.hpp" + +namespace grnxx { +namespace alpha { +namespace map { + +template <typename T> +class IDCursor : public MapCursor<T> { + public: + explicit IDCursor(Map<T> *map, int64_t min, int64_t max, + const MapCursorOptions &options); + ~IDCursor(); + + bool next(); + bool remove(); + + private: + Map<T> *map_; + int64_t end_; + int64_t step_; + uint64_t left_; +}; + +template <typename T> +class KeyCursor : public MapCursor<T> { + public: + explicit KeyCursor(Map<T> *map, T min, T max, + const MapCursorOptions &options); + ~KeyCursor(); + + bool next(); + bool remove(); + + private: + Map<T> *map_; + T min_; + T max_; + int64_t end_; + int64_t step_; + uint64_t left_; + MapCursorFlags flags_; +}; + +} // namespace map +} // namespace alpha +} // namespace grnxx + +#endif // GRNXX_ALPHA_MAP_CURSOR_HPP Modified: test/test_alpha_map.cpp (+58 -0) =================================================================== --- test/test_alpha_map.cpp 2013-04-09 10:34:23 +0900 (3003d8f) +++ test/test_alpha_map.cpp 2013-04-09 11:17:38 +0900 (042bea5) @@ -111,6 +111,60 @@ void compare_maps(const std::unique_ptr<grnxx::alpha::Map<T>> &map, } template <typename T> +void test_basic_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map, + std::size_t MAP_SIZE) { + std::unique_ptr<grnxx::alpha::MapCursor<T>> cursor( + map->open_basic_cursor()); + for (std::size_t i = 0; i < MAP_SIZE; ++i) { + assert(cursor->next()); + } + assert(!cursor->next()); +} + +template <typename T> +void test_id_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map, + std::size_t MAP_SIZE) { + const std::int64_t MIN_ID = MAP_SIZE / 4; + const std::int64_t MAX_ID = (MAP_SIZE * 3) / 4; + + grnxx::alpha::MapCursorOptions options; + options.flags |= grnxx::alpha::MAP_CURSOR_ORDER_BY_ID; + std::unique_ptr<grnxx::alpha::MapCursor<T>> cursor( + map->open_id_cursor(MIN_ID, MAX_ID, options)); + for (std::int64_t i = MIN_ID; i <= MAX_ID; ++i) { + assert(cursor->next()); + assert(cursor->key_id() == i); + T key; + assert(map->get(i, &key)); + assert(cursor->key() == key); + } + assert(!cursor->next()); +} + +template <typename T> +void test_key_cursor(const std::unique_ptr<grnxx::alpha::Map<T>> &map) { + T min_key, max_key; + generate_key(&min_key); + generate_key(&max_key); + if (min_key > max_key) { + std::swap(min_key, max_key); + } + + std::unique_ptr<grnxx::alpha::MapCursor<T>> cursor( + map->open_key_cursor(min_key, max_key)); + while (cursor->next()) { + assert(cursor->key() >= min_key); + assert(cursor->key() <= max_key); + } + assert(!cursor->next()); +} + +void test_key_cursor( + const std::unique_ptr<grnxx::alpha::Map<grnxx::alpha::GeoPoint>> &) { + // Not supported. +} + +template <typename T> void test_map() { GRNXX_NOTICE() << __PRETTY_FUNCTION__; @@ -145,6 +199,10 @@ void test_map() { compare_maps(map, hash_map); + test_basic_cursor(map, MAP_SIZE); + test_id_cursor(map, MAP_SIZE); + test_key_cursor(map); + std::uint32_t block_id = map->block_id(); map.reset(); map.reset(grnxx::alpha::Map<T>::open(pool, block_id)); -------------- next part -------------- HTML����������������������������...Download