susumu.yata
null+****@clear*****
Wed Jun 5 12:04:49 JST 2013
susumu.yata 2013-06-05 12:04:49 +0900 (Wed, 05 Jun 2013) New Revision: 10d9ce74c4d796a50e0361b4aeb682f71a683177 https://github.com/groonga/grnxx/commit/10d9ce74c4d796a50e0361b4aeb682f71a683177 Message: Add skeletons of Patricia and DoubleArray. Added files: lib/grnxx/map/double_array.cpp lib/grnxx/map/double_array.hpp lib/grnxx/map/patricia.cpp lib/grnxx/map/patricia.hpp Modified files: lib/grnxx/map.cpp lib/grnxx/map.hpp lib/grnxx/map/Makefile.am Modified: lib/grnxx/map.cpp (+6 -4) =================================================================== --- lib/grnxx/map.cpp 2013-06-05 10:48:50 +0900 (861a433) +++ lib/grnxx/map.cpp 2013-06-05 12:04:49 +0900 (d39b09a) @@ -26,9 +26,11 @@ #include "grnxx/string_builder.hpp" #include "grnxx/map/array_map.hpp" #include "grnxx/map/cursor_impl.hpp" +#include "grnxx/map/double_array.hpp" #include "grnxx/map/hash_table.hpp" #include "grnxx/map/header.hpp" #include "grnxx/map/helper.hpp" +#include "grnxx/map/patricia.hpp" #include "grnxx/map/scanner_impl.hpp" namespace grnxx { @@ -73,10 +75,10 @@ Map<T> *Map<T>::create(MapType type, Storage *storage, return map::ArrayMap<T>::create(storage, storage_node_id, options); } case MAP_DOUBLE_ARRAY: { - // TODO: Not supported yet. + return map::DoubleArray<T>::create(storage, storage_node_id, options); } case MAP_PATRICIA: { - // TODO: Not supported yet. + return map::Patricia<T>::create(storage, storage_node_id, options); } case MAP_HASH_TABLE: { return map::HashTable<T>::create(storage, storage_node_id, options); @@ -105,10 +107,10 @@ Map<T> *Map<T>::open(Storage *storage, uint32_t storage_node_id) { return map::ArrayMap<T>::open(storage, storage_node_id); } case MAP_DOUBLE_ARRAY: { - // TODO: Not supported yet. + return map::DoubleArray<T>::open(storage, storage_node_id); } case MAP_PATRICIA: { - // TODO: Not supported yet. + return map::Patricia<T>::open(storage, storage_node_id); } case MAP_HASH_TABLE: { return map::HashTable<T>::open(storage, storage_node_id); Modified: lib/grnxx/map.hpp (+2 -2) =================================================================== --- lib/grnxx/map.hpp 2013-06-05 10:48:50 +0900 (03c3f3f) +++ lib/grnxx/map.hpp 2013-06-05 12:04:49 +0900 (cf9cb45) @@ -38,9 +38,9 @@ constexpr int64_t MAP_INVALID_KEY_ID = MAP_MAX_KEY_ID + 1; enum MapType : uint32_t { MAP_ARRAY = 0, // Array-based implementation. - MAP_DOUBLE_ARRAY = 1, // TODO: DoubleArray-based implementation. + MAP_HASH_TABLE = 1, // HashTable-based implementation. MAP_PATRICIA = 2, // TODO: Patricia-based implementation. - MAP_HASH_TABLE = 3 // TODO: HashTable-based implementation. + MAP_DOUBLE_ARRAY = 3 // TODO: DoubleArray-based implementation. }; StringBuilder &operator<<(StringBuilder &builder, MapType type); Modified: lib/grnxx/map/Makefile.am (+4 -0) =================================================================== --- lib/grnxx/map/Makefile.am 2013-06-05 10:48:50 +0900 (4edca2e) +++ lib/grnxx/map/Makefile.am 2013-06-05 12:04:49 +0900 (fb287f2) @@ -15,7 +15,9 @@ libgrnxx_map_la_SOURCES = \ bytes_array.cpp \ bytes_store.cpp \ cursor_impl.cpp \ + double_array.cpp \ hash_table.cpp \ + patricia.cpp \ scanner_impl.cpp libgrnxx_map_includedir = ${includedir}/grnxx/map @@ -24,7 +26,9 @@ libgrnxx_map_include_HEADERS = \ bytes_array.hpp \ bytes_store.hpp \ cursor_impl.hpp \ + double_array.hpp \ hash_table.hpp \ header.hpp \ helper.hpp \ + patricia.hpp \ scanner_impl.hpp Added: lib/grnxx/map/double_array.cpp (+149 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/double_array.cpp 2013-06-05 12:04:49 +0900 (38cfa9b) @@ -0,0 +1,149 @@ +/* + Copyright (C) 2012-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/map/double_array.hpp" + +#include <new> + +#include "grnxx/bytes.hpp" +#include "grnxx/geo_point.hpp" +#include "grnxx/logger.hpp" +#include "grnxx/map/helper.hpp" +#include "grnxx/storage.hpp" + +namespace grnxx { +namespace map { + +struct DoubleArrayHeader { + // TODO + int64_t max_key_id; + uint64_t num_keys; + + DoubleArrayHeader(); +}; + +DoubleArrayHeader::DoubleArrayHeader() + : max_key_id(MAP_MIN_KEY_ID - 1), + num_keys(0) {} + +template <typename T> +Map<T> *DoubleArray<T>::create(Storage *, uint32_t, const MapOptions &) { + GRNXX_ERROR() << "invalid combination"; + return nullptr; +} + +template <typename T> +Map<T> *DoubleArray<T>::open(Storage *, uint32_t) { + GRNXX_ERROR() << "invalid combination"; + return nullptr; +} + +template class DoubleArray<int8_t>; +template class DoubleArray<uint8_t>; +template class DoubleArray<int16_t>; +template class DoubleArray<uint16_t>; +template class DoubleArray<int32_t>; +template class DoubleArray<uint32_t>; +template class DoubleArray<int64_t>; +template class DoubleArray<uint64_t>; +template class DoubleArray<double>; +template class DoubleArray<GeoPoint>; + +DoubleArray<Bytes>::DoubleArray() + : storage_(nullptr), + storage_node_id_(STORAGE_INVALID_NODE_ID), + header_(nullptr) {} + +DoubleArray<Bytes>::~DoubleArray() {} + +DoubleArray<Bytes> *DoubleArray<Bytes>::create(Storage *storage, + uint32_t storage_node_id, + const MapOptions &options) { + std::unique_ptr<DoubleArray> map(new (std::nothrow) DoubleArray); + if (!map) { + GRNXX_ERROR() << "new grnxx::map::DoubleArray failed"; + return nullptr; + } + if (!map->create_map(storage, storage_node_id, options)) { + return nullptr; + } + return map.release(); +} + +DoubleArray<Bytes> *DoubleArray<Bytes>::open(Storage *storage, + uint32_t storage_node_id) { + std::unique_ptr<DoubleArray> map(new (std::nothrow) DoubleArray); + if (!map) { + GRNXX_ERROR() << "new grnxx::map::DoubleArray failed"; + return nullptr; + } + if (!map->open_map(storage, storage_node_id)) { + return nullptr; + } + return map.release(); +} + +uint32_t DoubleArray<Bytes>::storage_node_id() const { + return storage_node_id_; +} + +MapType DoubleArray<Bytes>::type() const { + return MAP_DOUBLE_ARRAY; +} + +int64_t DoubleArray<Bytes>::max_key_id() const { + return header_->max_key_id; +} + +uint64_t DoubleArray<Bytes>::num_keys() const { + return header_->num_keys; +} + +bool DoubleArray<Bytes>::create_map(Storage *storage, uint32_t storage_node_id, + const MapOptions &) { + storage_ = storage; + StorageNode storage_node = + storage->create_node(storage_node_id, sizeof(DoubleArrayHeader)); + if (!storage_node) { + return false; + } + storage_node_id_ = storage_node.id(); + header_ = static_cast<DoubleArrayHeader *>(storage_node.body()); + *header_ = DoubleArrayHeader(); + // TODO + return false; +} + +bool DoubleArray<Bytes>::open_map(Storage *storage, uint32_t storage_node_id) { + storage_ = storage; + StorageNode storage_node = storage->open_node(storage_node_id); + if (!storage_node) { + return false; + } + if (storage_node.size() < sizeof(DoubleArrayHeader)) { + GRNXX_ERROR() << "invalid format: size = " << storage_node.size() + << ", header_size = " << sizeof(DoubleArrayHeader); + return false; + } + storage_node_id_ = storage_node_id; + header_ = static_cast<DoubleArrayHeader *>(storage_node.body()); + // TODO + return false; +} + +} // namespace map +} // namespace grnxx Added: lib/grnxx/map/double_array.hpp (+103 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/double_array.hpp 2013-06-05 12:04:49 +0900 (11cdcd2) @@ -0,0 +1,103 @@ +/* + Copyright (C) 2012-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_DOUBLE_ARRAY_HPP +#define GRNXX_MAP_DOUBLE_ARRAY_HPP + +#include "grnxx/features.hpp" + +#include <memory> + +#include "grnxx/bytes.hpp" +#include "grnxx/map.hpp" +#include "grnxx/map_cursor.hpp" +#include "grnxx/map_cursor_query.hpp" +#include "grnxx/types.hpp" + +namespace grnxx { +namespace map { + +struct DoubleArrayHeader; + +template <typename T> +class DoubleArray { + public: + static Map<T> *create(Storage *storage, uint32_t storage_node_id, + const MapOptions &options = MapOptions()); + static Map<T> *open(Storage *storage, uint32_t storage_node_id); +}; + +template <> +class DoubleArray<Bytes> : public Map<Bytes> { + public: + using Key = typename Map<Bytes>::Key; + using KeyArg = typename Map<Bytes>::KeyArg; + using Cursor = typename Map<Bytes>::Cursor; + + DoubleArray(); + ~DoubleArray(); + + static DoubleArray *create(Storage *storage, uint32_t storage_node_id, + const MapOptions &options = MapOptions()); + static DoubleArray *open(Storage *storage, uint32_t storage_node_id); + + uint32_t storage_node_id() const; + MapType type() const; + + int64_t max_key_id() const; + uint64_t num_keys() const; + + // TODO +// bool get(int64_t key_id, Key *key = nullptr); +// bool unset(int64_t key_id); +// bool reset(int64_t key_id, KeyArg dest_key); + +// bool find(KeyArg key, int64_t *key_id = nullptr); +// bool add(KeyArg key, int64_t *key_id = nullptr); +// bool remove(KeyArg key); +// bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); + +// bool truncate(); + +// bool find_longest_prefix_match(KeyArg query, +// int64_t *key_id = nullptr, +// Key *key = nullptr); + +// Cursor *create_cursor( +// MapCursorAllKeys<T> query, +// const MapCursorOptions &options = MapCursorOptions()); +// Cursor *create_cursor( +// const MapCursorKeyIDRange<T> &query, +// const MapCursorOptions &options = MapCursorOptions()); +// Cursor *create_cursor( +// const MapCursorKeyRange<T> &query, +// const MapCursorOptions &options = MapCursorOptions()); + + private: + Storage *storage_; + uint32_t storage_node_id_; + DoubleArrayHeader *header_; + + bool create_map(Storage *storage, uint32_t storage_node_id, + const MapOptions &options); + bool open_map(Storage *storage, uint32_t storage_node_id); +}; + +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_DOUBLE_ARRAY_HPP Added: lib/grnxx/map/patricia.cpp (+148 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/patricia.cpp 2013-06-05 12:04:49 +0900 (19edc88) @@ -0,0 +1,148 @@ +/* + Copyright (C) 2012-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/map/patricia.hpp" + +#include <new> + +#include "grnxx/bytes.hpp" +#include "grnxx/geo_point.hpp" +#include "grnxx/logger.hpp" +#include "grnxx/map/helper.hpp" +#include "grnxx/storage.hpp" + +namespace grnxx { +namespace map { + +struct PatriciaHeader { + // TODO + int64_t max_key_id; + uint64_t num_keys; + + PatriciaHeader(); +}; + +PatriciaHeader::PatriciaHeader() + : max_key_id(MAP_MIN_KEY_ID - 1), + num_keys(0) {} + +template <typename T> +Patricia<T>::Patricia() + : storage_(nullptr), + storage_node_id_(STORAGE_INVALID_NODE_ID), + header_(nullptr) {} + +template <typename T> +Patricia<T>::~Patricia() {} + +template <typename T> +Patricia<T> *Patricia<T>::create(Storage *storage, + uint32_t storage_node_id, + const MapOptions &options) { + std::unique_ptr<Patricia> map(new (std::nothrow) Patricia); + if (!map) { + GRNXX_ERROR() << "new grnxx::map::Patricia failed"; + return nullptr; + } + if (!map->create_map(storage, storage_node_id, options)) { + return nullptr; + } + return map.release(); +} + +template <typename T> +Patricia<T> *Patricia<T>::open(Storage *storage, + uint32_t storage_node_id) { + std::unique_ptr<Patricia> map(new (std::nothrow) Patricia); + if (!map) { + GRNXX_ERROR() << "new grnxx::map::Patricia failed"; + return nullptr; + } + if (!map->open_map(storage, storage_node_id)) { + return nullptr; + } + return map.release(); +} + +template <typename T> +uint32_t Patricia<T>::storage_node_id() const { + return storage_node_id_; +} + +template <typename T> +MapType Patricia<T>::type() const { + return MAP_DOUBLE_ARRAY; +} + +template <typename T> +int64_t Patricia<T>::max_key_id() const { + return header_->max_key_id; +} + +template <typename T> +uint64_t Patricia<T>::num_keys() const { + return header_->num_keys; +} + +template <typename T> +bool Patricia<T>::create_map(Storage *storage, uint32_t storage_node_id, + const MapOptions &) { + storage_ = storage; + StorageNode storage_node = + storage->create_node(storage_node_id, sizeof(PatriciaHeader)); + if (!storage_node) { + return false; + } + storage_node_id_ = storage_node.id(); + header_ = static_cast<PatriciaHeader *>(storage_node.body()); + *header_ = PatriciaHeader(); + // TODO + return false; +} + +template <typename T> +bool Patricia<T>::open_map(Storage *storage, uint32_t storage_node_id) { + storage_ = storage; + StorageNode storage_node = storage->open_node(storage_node_id); + if (!storage_node) { + return false; + } + if (storage_node.size() < sizeof(PatriciaHeader)) { + GRNXX_ERROR() << "invalid format: size = " << storage_node.size() + << ", header_size = " << sizeof(PatriciaHeader); + return false; + } + storage_node_id_ = storage_node_id; + header_ = static_cast<PatriciaHeader *>(storage_node.body()); + // TODO + return false; +} + +template class Patricia<int8_t>; +template class Patricia<uint8_t>; +template class Patricia<int16_t>; +template class Patricia<uint16_t>; +template class Patricia<int32_t>; +template class Patricia<uint32_t>; +template class Patricia<int64_t>; +template class Patricia<uint64_t>; +template class Patricia<double>; +template class Patricia<GeoPoint>; +template class Patricia<Bytes>; + +} // namespace map +} // namespace grnxx Added: lib/grnxx/map/patricia.hpp (+78 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/map/patricia.hpp 2013-06-05 12:04:49 +0900 (7ae45f4) @@ -0,0 +1,78 @@ +/* + Copyright (C) 2012-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_PATRICIA_HPP +#define GRNXX_MAP_PATRICIA_HPP + +#include "grnxx/features.hpp" + +#include <memory> + +#include "grnxx/map.hpp" +#include "grnxx/types.hpp" + +namespace grnxx { +namespace map { + +struct PatriciaHeader; + +template <typename T> +class Patricia : public Map<T> { + public: + using Key = typename Map<T>::Key; + using KeyArg = typename Map<T>::KeyArg; + using Cursor = typename Map<T>::Cursor; + + Patricia(); + ~Patricia(); + + static Patricia *create(Storage *storage, uint32_t storage_node_id, + const MapOptions &options = MapOptions()); + static Patricia *open(Storage *storage, uint32_t storage_node_id); + + uint32_t storage_node_id() const; + MapType type() const; + + int64_t max_key_id() const; + uint64_t num_keys() const; + + // TODO +// bool get(int64_t key_id, Key *key = nullptr); +// bool unset(int64_t key_id); +// bool reset(int64_t key_id, KeyArg dest_key); + +// bool find(KeyArg key, int64_t *key_id = nullptr); +// bool add(KeyArg key, int64_t *key_id = nullptr); +// bool remove(KeyArg key); +// bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); + +// bool truncate(); + + private: + Storage *storage_; + uint32_t storage_node_id_; + PatriciaHeader *header_; + + bool create_map(Storage *storage, uint32_t storage_node_id, + const MapOptions &options); + bool open_map(Storage *storage, uint32_t storage_node_id); +}; + +} // namespace map +} // namespace grnxx + +#endif // GRNXX_MAP_PATRICIA_HPP -------------- next part -------------- HTML����������������������������...Download