susumu.yata
null+****@clear*****
Mon May 13 17:57:42 JST 2013
susumu.yata 2013-05-13 17:57:42 +0900 (Mon, 13 May 2013) New Revision: 4b43b424030c56d1f3b59e8618772662c479cc5d https://github.com/groonga/grnxx/commit/4b43b424030c56d1f3b59e8618772662c479cc5d Message: Add grnxx::Array. Added files: lib/grnxx/array.hpp lib/grnxx/array/Makefile.am lib/grnxx/array/array_1d.cpp lib/grnxx/array/array_1d.hpp lib/grnxx/array/array_2d.cpp lib/grnxx/array/array_2d.hpp lib/grnxx/array/array_3d.cpp lib/grnxx/array/array_3d.hpp lib/grnxx/traits.hpp Modified files: configure.ac lib/grnxx/Makefile.am Modified: configure.ac (+1 -0) =================================================================== --- configure.ac 2013-05-11 13:47:43 +0900 (27d2a7d) +++ configure.ac 2013-05-13 17:57:42 +0900 (b480a79) @@ -62,6 +62,7 @@ AC_CONFIG_FILES([Makefile lib/grnxx/Makefile lib/grnxx/alpha/Makefile lib/grnxx/alpha/map/Makefile + lib/grnxx/array/Makefile lib/grnxx/charset/Makefile lib/grnxx/db/Makefile lib/grnxx/io/Makefile Modified: lib/grnxx/Makefile.am (+3 -0) =================================================================== --- lib/grnxx/Makefile.am 2013-05-11 13:47:43 +0900 (f7ee6ca) +++ lib/grnxx/Makefile.am 2013-05-13 17:57:42 +0900 (442f546) @@ -1,5 +1,6 @@ SUBDIRS = \ alpha \ + array \ charset \ db \ io \ @@ -11,6 +12,7 @@ lib_LTLIBRARIES = libgrnxx.la libgrnxx_la_LIBADD = \ alpha/libgrnxx_alpha.la \ + array/libgrnxx_array.la \ charset/libgrnxx_charset.la \ db/libgrnxx_db.la \ io/libgrnxx_io.la \ @@ -39,6 +41,7 @@ libgrnxx_la_SOURCES = \ libgrnxx_includedir = ${includedir}/grnxx libgrnxx_include_HEADERS = \ + array.hpp \ backtrace.hpp \ basic.hpp \ charset.hpp \ Added: lib/grnxx/array.hpp (+452 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array.hpp 2013-05-13 17:57:42 +0900 (4c49d4f) @@ -0,0 +1,452 @@ +/* + 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_ARRAY_HPP +#define GRNXX_ARRAY_HPP + +#include "grnxx/features.hpp" + +#include <cstring> +#include <memory> +#include <new> + +#include "grnxx/array/array_1d.hpp" +#include "grnxx/array/array_2d.hpp" +#include "grnxx/array/array_3d.hpp" +#include "grnxx/logger.hpp" +#include "grnxx/traits.hpp" + +namespace grnxx { + +class Storage; + +constexpr uint64_t ARRAY_DEFAULT_PAGE_SIZE = 1ULL << 16; +constexpr uint64_t ARRAY_DEFAULT_TABLE_SIZE = 1ULL << 12; +constexpr uint64_t ARRAY_DEFAULT_SECONDARY_TABLE_SIZE = 1ULL << 12; + +template <typename T, + uint64_t PAGE_SIZE = ARRAY_DEFAULT_PAGE_SIZE, + uint64_t TABLE_SIZE = 1, + uint64_t SECONDARY_TABLE_SIZE = 1> +class Array; + +// 1D array. +template <typename T, uint64_t PAGE_SIZE> +class Array<T, PAGE_SIZE, 1, 1> { + static_assert(PAGE_SIZE > 0, "PAGE_SIZE <= 0"); + + using Value = typename Traits<T>::Type; + using ValueArg = typename Traits<T>::ArgumentType; + + public: + ~Array() {} + + // Create an array. + static Array *create(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE; + return nullptr; + } + if (!array->impl_.create(storage, storage_node_id, sizeof(Value), + PAGE_SIZE)) { + return nullptr; + } + return array.release(); + } + + // Create an array with the default value. + static Array *create(Storage *storage, uint32_t storage_node_id, + ValueArg default_value) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE; + return nullptr; + } + if (!array->impl_.create(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, &default_value, fill_page)) { + return nullptr; + } + return array.release(); + } + + // Open an array. + static Array *open(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE; + return nullptr; + } + if (!array->impl_.open(storage, storage_node_id, sizeof(Value), + PAGE_SIZE)) { + return nullptr; + } + return array.release(); + } + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id) { + return Array1D::unlink(storage, storage_node_id, sizeof(Value), PAGE_SIZE); + } + + // Return the number of values in each page. + static constexpr uint64_t page_size() { + return PAGE_SIZE; + } + // Return the number of pages in each table. + static constexpr uint64_t table_size() { + return 1; + } + // Return the number of tables in each secondary table. + static constexpr uint64_t secondary_table_size() { + return 1; + } + // Return the number of values in Array. + static constexpr uint64_t size() { + return page_size() * table_size() * secondary_table_size(); + } + + // Return the storage node ID. + uint32_t storage_node_id() const { + return impl_.storage_node_id(); + } + + // Get a reference to a value. + Value &operator[](uint64_t value_id) { + Value * const page = get_page(value_id / PAGE_SIZE); + return page[value_id % PAGE_SIZE]; + } + + // Get a value and return true. + // The value is assigned to "*value". + bool get(uint64_t value_id, Value *value) { + const Value * const page = get_page(value_id / PAGE_SIZE); + *value = page[value_id % PAGE_SIZE]; + return true; + } + + // Set a value and return true. + bool set(uint64_t value_id, ValueArg value) { + Value * const page = get_page(value_id / PAGE_SIZE); + page[value_id % PAGE_SIZE] = value; + return true; + } + + // Get a page and return its starting address. + Value *get_page(uint64_t) { + return impl_.get_page<Value>(); + } + + private: + Array1D impl_; + + Array() : impl_() {} + + // This function is used to fill a new page with the default value. + static void fill_page(void *page, const void *value) { + Value *values = static_cast<Value *>(page); + for (uint64_t i = 0; i < PAGE_SIZE; ++i) { + std::memcpy(&values[i], value, sizeof(Value)); + } + } +}; + +// 2D array. +template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> +class Array<T, PAGE_SIZE, TABLE_SIZE, 1> { + static_assert((PAGE_SIZE > 0) && ((PAGE_SIZE & (PAGE_SIZE - 1)) == 0), + "PAGE_SIZE must be a power of two"); + static_assert(TABLE_SIZE > 0, "TABLE_SIZE <= 0"); + + using Value = typename Traits<T>::Type; + using ValueArg = typename Traits<T>::ArgumentType; + + public: + ~Array() {} + + // Create an array. + static Array *create(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE + << ", TABLE_SIZE = " << TABLE_SIZE; + return nullptr; + } + if (!array->impl_.create(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE)) { + return nullptr; + } + return array.release(); + } + + // Create an array with the default value. + static Array *create(Storage *storage, uint32_t storage_node_id, + ValueArg default_value) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE + << ", TABLE_SIZE = " << TABLE_SIZE; + return nullptr; + } + if (!array->impl_.create(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE, + &default_value, fill_page)) { + return nullptr; + } + return array.release(); + } + + // Open an array. + static Array *open(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE + << ", TABLE_SIZE = " << TABLE_SIZE; + return nullptr; + } + if (!array->impl_.open(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE)) { + return nullptr; + } + return array.release(); + } + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id) { + return Array2D::unlink(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE); + } + + // Return the number of values in each page. + static constexpr uint64_t page_size() { + return PAGE_SIZE; + } + // Return the number of pages in each table. + static constexpr uint64_t table_size() { + return TABLE_SIZE; + } + // Return the number of tables in each secondary table. + static constexpr uint64_t secondary_table_size() { + return 1; + } + // Return the number of values in Array. + static constexpr uint64_t size() { + return page_size() * table_size() * secondary_table_size(); + } + + // Return the storage node ID. + uint32_t storage_node_id() const { + return impl_.storage_node_id(); + } + + // Get a reference to a value. + // This function throws an exception on failure. + Value &operator[](uint64_t value_id) { + Value * const page = + impl_.get_page<Value, TABLE_SIZE>(value_id / PAGE_SIZE); + return page[value_id % PAGE_SIZE]; + } + + // Get a value and return true on success. + // The value is assigned to "*value". + bool get(uint64_t value_id, Value *value) { + const Value * const page = get_page(value_id / PAGE_SIZE); + if (!page) { + return false; + } + *value = page[value_id % PAGE_SIZE]; + return true; + } + + // Set a value and return true on success. + bool set(uint64_t value_id, ValueArg value) { + Value * const page = get_page(value_id / PAGE_SIZE); + if (!page) { + return false; + } + page[value_id % PAGE_SIZE] = value; + return true; + } + + // Get a page and return its starting address on success. + Value *get_page(uint64_t page_id) { + return impl_.get_page_nothrow<Value, TABLE_SIZE>(page_id); + } + + private: + Array2D impl_; + + Array() : impl_() {} + + // This function is used to fill a new page with the default value. + static void fill_page(void *page, const void *value) { + Value *values = static_cast<Value *>(page); + for (uint64_t i = 0; i < PAGE_SIZE; ++i) { + std::memcpy(&values[i], value, sizeof(Value)); + } + } +}; + +// 3D array. +template <typename T, + uint64_t PAGE_SIZE, + uint64_t TABLE_SIZE, + uint64_t SECONDARY_TABLE_SIZE> +class Array { + static_assert((PAGE_SIZE > 0) && ((PAGE_SIZE & (PAGE_SIZE - 1)) == 0), + "PAGE_SIZE must be a power of two"); + static_assert((TABLE_SIZE > 0) && ((TABLE_SIZE & (TABLE_SIZE - 1)) == 0), + "TABLE_SIZE must be a power of two"); + static_assert(SECONDARY_TABLE_SIZE > 0, "SECONDARY_TABLE_SIZE <= 0"); + + using Value = typename Traits<T>::Type; + using ValueArg = typename Traits<T>::ArgumentType; + + public: + ~Array() {} + + // Create an array. + static Array *create(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE + << ", TABLE_SIZE = " << TABLE_SIZE + << ", SECONDARY_TABLE_SIZE = " << SECONDARY_TABLE_SIZE; + return nullptr; + } + if (!array->impl_.create(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE)) { + return nullptr; + } + return array.release(); + } + + // Create an array with the default value. + static Array *create(Storage *storage, uint32_t storage_node_id, + ValueArg default_value) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE + << ", TABLE_SIZE = " << TABLE_SIZE + << ", SECONDARY_TABLE_SIZE = " << SECONDARY_TABLE_SIZE; + return nullptr; + } + if (!array->impl_.create(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE, + &default_value, fill_page)) { + return nullptr; + } + return array.release(); + } + + // Open an array. + static Array *open(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(new (std::nothrow) Array); + if (!array) { + GRNXX_ERROR() << "new grnxx::Array failed: PAGE_SIZE = " << PAGE_SIZE + << ", TABLE_SIZE = " << TABLE_SIZE + << ", SECONDARY_TABLE_SIZE = " << SECONDARY_TABLE_SIZE; + return nullptr; + } + if (!array->impl_.open(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE)) { + return nullptr; + } + return array.release(); + } + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id) { + return Array3D::unlink(storage, storage_node_id, sizeof(Value), + PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE); + } + + // Return the number of values in each page. + static constexpr uint64_t page_size() { + return PAGE_SIZE; + } + // Return the number of pages in each table. + static constexpr uint64_t table_size() { + return TABLE_SIZE; + } + // Return the number of tables in each secondary table. + static constexpr uint64_t secondary_table_size() { + return SECONDARY_TABLE_SIZE; + } + // Return the number of values in Array. + static constexpr uint64_t size() { + return page_size() * table_size() * secondary_table_size(); + } + + // Return the storage node ID. + uint32_t storage_node_id() const { + return impl_.storage_node_id(); + } + + // Get a reference to a value. + // This function throws an exception on failure. + Value &operator[](uint64_t value_id) { + Value * const page = + impl_.get_page<Value, TABLE_SIZE, + SECONDARY_TABLE_SIZE>(value_id / PAGE_SIZE); + return page[value_id % PAGE_SIZE]; + } + + // Get a value and return true on success. + // The value is assigned to "*value". + bool get(uint64_t value_id, Value *value) { + const Value * const page = get_page(value_id / PAGE_SIZE); + if (!page) { + return false; + } + *value = page[value_id % PAGE_SIZE]; + return true; + } + + // Set a value and return true on success. + bool set(uint64_t value_id, ValueArg value) { + Value * const page = get_page(value_id / PAGE_SIZE); + if (!page) { + return false; + } + page[value_id % PAGE_SIZE] = value; + return true; + } + + // Get a page and return its starting address on success. + Value *get_page(uint64_t page_id) { + return impl_.get_page_nothrow<Value, TABLE_SIZE, + SECONDARY_TABLE_SIZE>(page_id); + } + + private: + Array3D impl_; + + Array() : impl_() {} + + // This function is used to fill a new page with the default value. + static void fill_page(void *page, const void *value) { + Value *values = static_cast<Value *>(page); + for (uint64_t i = 0; i < PAGE_SIZE; ++i) { + std::memcpy(&values[i], value, sizeof(Value)); + } + } +}; + +} // namespace grnxx + +#endif // GRNXX_ARRAY_HPP Added: lib/grnxx/array/Makefile.am (+14 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/Makefile.am 2013-05-13 17:57:42 +0900 (ac0c4bd) @@ -0,0 +1,14 @@ +noinst_LTLIBRARIES = libgrnxx_array.la + +libgrnxx_array_la_LDFLAGS = @AM_LTLDFLAGS@ + +libgrnxx_array_la_SOURCES = \ + array_1d.cpp \ + array_2d.cpp \ + array_3d.cpp + +libgrnxx_array_includedir = ${includedir}/grnxx/array +libgrnxx_array_include_HEADERS = \ + array_1d.hpp \ + array_2d.hpp \ + array_3d.hpp Added: lib/grnxx/array/array_1d.cpp (+109 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/array_1d.cpp 2013-05-13 17:57:42 +0900 (44fb14c) @@ -0,0 +1,109 @@ +/* + 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/array/array_1d.hpp" + +#include "grnxx/logger.hpp" + +namespace grnxx { + +struct Array1DHeader { + uint64_t value_size; + uint64_t page_size; + uint32_t page_storage_node_id; + + Array1DHeader(uint64_t value_size, uint64_t page_size); +}; + +Array1DHeader::Array1DHeader(uint64_t value_size, uint64_t page_size) + : value_size(value_size), + page_size(page_size), + page_storage_node_id(STORAGE_INVALID_NODE_ID) {} + +Array1D::Array1D() + : storage_node_(), + header_(nullptr), + page_(nullptr) {} + +Array1D::~Array1D() {} + +bool Array1D::create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + const void *default_value, FillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + return nullptr; + } + storage_node_ = storage->create_node(storage_node_id, sizeof(Array1DHeader)); + if (!storage_node_.is_valid()) { + return false; + } + header_ = static_cast<Array1DHeader *>(storage_node_.body()); + *header_ = Array1DHeader(value_size, page_size); + StorageNode page_node = + storage->create_node(storage_node_.id(), value_size * page_size); + if (!page_node.is_valid()) { + storage->unlink_node(storage_node_.id()); + return false; + } + header_->page_storage_node_id = page_node.id(); + page_ = page_node.body(); + if (default_value) { + fill_page(page_, default_value); + } + return true; +} + +bool Array1D::open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + return nullptr; + } + storage_node_ = storage->open_node(storage_node_id); + if (!storage_node_.is_valid()) { + return false; + } + header_ = static_cast<Array1DHeader *>(storage_node_.body()); + if (header_->value_size != value_size) { + GRNXX_ERROR() << "parameter conflict: value_size = " << value_size + << ", stored_value_size = " << header_->value_size; + return false; + } + if (header_->page_size != page_size) { + GRNXX_ERROR() << "parameter conflict: page_size = " << page_size + << ", stored_page_size = " << header_->page_size; + return false; + } + StorageNode page_node = storage->open_node(header_->page_storage_node_id); + if (!page_node.is_valid()) { + return false; + } + page_ = page_node.body(); + return true; +} + +bool Array1D::unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size) { + Array1D array; + if (!array.open(storage, storage_node_id, value_size, page_size)) { + return false; + } + return storage->unlink_node(storage_node_id); +} + +} // namespace grnxx Added: lib/grnxx/array/array_1d.hpp (+62 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/array_1d.hpp 2013-05-13 17:57:42 +0900 (f4762c4) @@ -0,0 +1,62 @@ +/* + 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_ARRAY_ARRAY_1D_HPP +#define GRNXX_ARRAY_ARRAY_1D_HPP + +#include "grnxx/storage.hpp" +#include "grnxx/traits.hpp" + +namespace grnxx { + +struct Array1DHeader; + +class Array1D { + using FillPage = void (*)(void *page, const void *value); + + public: + Array1D(); + ~Array1D(); + + bool create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + const void *default_value = nullptr, + FillPage fill_page = nullptr); + bool open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size); + + static bool unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size); + + uint32_t storage_node_id() const { + return storage_node_.id(); + } + + template <typename T> + T *get_page() { + return static_cast<T *>(page_); + } + + private: + StorageNode storage_node_; + Array1DHeader *header_; + void *page_; +}; + +} // namespace grnxx + +#endif // GRNXX_ARRAY_ARRAY_1D_HPP Added: lib/grnxx/array/array_2d.cpp (+204 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/array_2d.cpp 2013-05-13 17:57:42 +0900 (47eddb1) @@ -0,0 +1,204 @@ +/* + 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/array/array_2d.hpp" + +#include <cstring> +#include <new> + +#include "grnxx/exception.hpp" +#include "grnxx/lock.hpp" +#include "grnxx/logger.hpp" +#include "grnxx/mutex.hpp" + +namespace grnxx { + +struct Array2DHeader { + uint64_t value_size; + uint64_t page_size; + uint64_t table_size; + uint32_t has_default_value; + uint32_t table_storage_node_id; + Mutex mutex; + + Array2DHeader(uint64_t value_size, uint64_t page_size, + uint64_t table_size, bool has_default_value); +}; + +Array2DHeader::Array2DHeader(uint64_t value_size, uint64_t page_size, + uint64_t table_size, bool has_default_value) + : value_size(value_size), + page_size(page_size), + table_size(table_size), + has_default_value(has_default_value ? 1 : 0), + table_storage_node_id(STORAGE_INVALID_NODE_ID), + mutex(MUTEX_UNLOCKED) {} + +Array2D::Array2D() + : storage_(nullptr), + storage_node_(), + header_(nullptr), + default_value_(nullptr), + fill_page_(nullptr), + table_(nullptr), + table_cache_(), + mutex_(MUTEX_UNLOCKED) {} + +Array2D::~Array2D() {} + +bool Array2D::create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, + const void *default_value, FillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + return nullptr; + } + storage_ = storage; + uint64_t storage_node_size = sizeof(Array2DHeader); + if (default_value) { + storage_node_size += value_size; + } + storage_node_ = storage->create_node(storage_node_id, storage_node_size); + if (!storage_node_.is_valid()) { + return false; + } + header_ = static_cast<Array2DHeader *>(storage_node_.body()); + *header_ = Array2DHeader(value_size, page_size, table_size, default_value); + if (default_value) { + default_value_ = header_ + 1; + std::memcpy(default_value_, default_value, value_size); + fill_page_ = fill_page; + } + StorageNode table_node = + storage->create_node(storage_node_.id(), sizeof(uint32_t) * table_size); + if (!table_node.is_valid()) { + storage->unlink_node(storage_node_.id()); + return false; + } + header_->table_storage_node_id = table_node.id(); + table_ = static_cast<uint32_t *>(table_node.body()); + for (uint64_t i = 0; i < table_size; ++i) { + table_[i] = STORAGE_INVALID_NODE_ID; + } + table_cache_.reset(new (std::nothrow) void *[table_size]); + if (!table_cache_) { + GRNXX_ERROR() << "new void *[] failed: size = " << table_size; + storage->unlink_node(storage_node_.id()); + return false; + } + for (uint64_t i = 0; i < table_size; ++i) { + table_cache_[i] = nullptr; + } + return true; +} + +bool Array2D::open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, FillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + return nullptr; + } + storage_ = storage; + storage_node_ = storage->open_node(storage_node_id); + if (!storage_node_.is_valid()) { + return false; + } + header_ = static_cast<Array2DHeader *>(storage_node_.body()); + if (header_->value_size != value_size) { + GRNXX_ERROR() << "parameter conflict: value_size = " << value_size + << ", stored_value_size = " << header_->value_size; + return false; + } + if (header_->page_size != page_size) { + GRNXX_ERROR() << "parameter conflict: page_size = " << page_size + << ", stored_page_size = " << header_->page_size; + return false; + } + if (header_->table_size != table_size) { + GRNXX_ERROR() << "parameter conflict: table_size = " << table_size + << ", stored_table_size = " << header_->table_size; + return false; + } + default_value_ = header_ + 1; + fill_page_ = fill_page; + StorageNode table_node = storage->open_node(header_->table_storage_node_id); + if (!table_node.is_valid()) { + return false; + } + table_ = static_cast<uint32_t *>(table_node.body()); + table_cache_.reset(new (std::nothrow) void *[table_size]); + if (!table_cache_) { + GRNXX_ERROR() << "new void *[] failed: size = " << table_size; + return false; + } + for (uint64_t i = 0; i < table_size; ++i) { + table_cache_[i] = nullptr; + } + return true; +} + +bool Array2D::unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size) { + Array2D array; + if (!array.open(storage, storage_node_id, + value_size, page_size, table_size, nullptr)) { + return false; + } + return storage->unlink_node(storage_node_id); +} + +void Array2D::initialize_page(uint64_t page_id) { + if (!initialize_page_nothrow(page_id)) { + GRNXX_ERROR() << "failed to initialize page: page_id = " << page_id; + GRNXX_THROW(); + } +} + +bool Array2D::initialize_page_nothrow(uint64_t page_id) { + Lock inter_thread_lock(&mutex_); + if (!table_cache_[page_id]) { + StorageNode page_node; + if (table_[page_id] == STORAGE_INVALID_NODE_ID) { + Lock inter_process_lock(&header_->mutex); + if (table_[page_id] == STORAGE_INVALID_NODE_ID) { + page_node = + storage_->create_node(header_->table_storage_node_id, + header_->value_size * header_->page_size); + if (!page_node.is_valid()) { + return false; + } + if (default_value_) { + fill_page_(page_node.body(), default_value_); + } + table_[page_id] = page_node.id(); + table_cache_[page_id] = page_node.body(); + return true; + } + } + page_node = storage_->open_node(table_[page_id]); + if (!page_node.is_valid()) { + return false; + } + table_cache_[page_id] = page_node.body(); + } + return true; +} + +} // namespace grnxx Added: lib/grnxx/array/array_2d.hpp (+86 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/array_2d.hpp 2013-05-13 17:57:42 +0900 (0cc8de8) @@ -0,0 +1,86 @@ +/* + 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_ARRAY_ARRAY_2D_HPP +#define GRNXX_ARRAY_ARRAY_2D_HPP + +#include "grnxx/mutex.hpp" +#include "grnxx/storage.hpp" +#include "grnxx/traits.hpp" + +namespace grnxx { + +struct Array2DHeader; + +class Array2D { + using FillPage = void (*)(void *page, const void *value); + + public: + Array2D(); + ~Array2D(); + + bool create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, uint64_t table_size, + const void *default_value = nullptr, + FillPage fill_page = nullptr); + bool open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, uint64_t table_size, + FillPage fill_page); + + static bool unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size); + + uint32_t storage_node_id() const { + return storage_node_.id(); + } + + template <typename T, uint64_t TABLE_SIZE> + T *get_page(uint64_t page_id) { + if (!table_cache_[page_id]) { + initialize_page(page_id); + } + return static_cast<T *>(table_cache_[page_id]); + } + + template <typename T, uint64_t TABLE_SIZE> + T *get_page_nothrow(uint64_t page_id) { + if (!table_cache_[page_id]) { + if (!initialize_page_nothrow(page_id)) { + return nullptr; + } + } + return static_cast<T *>(table_cache_[page_id]); + } + + private: + Storage *storage_; + StorageNode storage_node_; + Array2DHeader *header_; + void *default_value_; + FillPage fill_page_; + uint32_t *table_; + std::unique_ptr<void *[]> table_cache_; + Mutex mutex_; + + void initialize_page(uint64_t page_id); + bool initialize_page_nothrow(uint64_t page_id); +}; + +} // namespace grnxx + +#endif // GRNXX_ARRAY_ARRAY_2D_HPP Added: lib/grnxx/array/array_3d.cpp (+285 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/array_3d.cpp 2013-05-13 17:57:42 +0900 (e07115e) @@ -0,0 +1,285 @@ +/* + 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/array/array_3d.hpp" + +#include <cstring> +#include <new> + +#include "grnxx/exception.hpp" +#include "grnxx/lock.hpp" +#include "grnxx/logger.hpp" +#include "grnxx/mutex.hpp" + +namespace grnxx { + +struct Array3DHeader { + uint64_t value_size; + uint64_t page_size; + uint64_t table_size; + uint64_t secondary_table_size; + uint32_t has_default_value; + uint32_t secondary_table_storage_node_id; + Mutex page_mutex; + Mutex table_mutex; + Mutex secondary_table_mutex; + + Array3DHeader(uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size, + bool has_default_value); +}; + +Array3DHeader::Array3DHeader(uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size, + bool has_default_value) + : value_size(value_size), + page_size(page_size), + table_size(table_size), + secondary_table_size(secondary_table_size), + has_default_value(has_default_value ? 1 : 0), + secondary_table_storage_node_id(STORAGE_INVALID_NODE_ID), + page_mutex(MUTEX_UNLOCKED), + table_mutex(MUTEX_UNLOCKED), + secondary_table_mutex(MUTEX_UNLOCKED) {} + +Array3D::Array3D() + : storage_(nullptr), + storage_node_(), + header_(nullptr), + default_value_(nullptr), + fill_page_(nullptr), + secondary_table_(nullptr), + table_caches_(), + page_mutex_(MUTEX_UNLOCKED), + table_mutex_(MUTEX_UNLOCKED), + secondary_table_mutex_(MUTEX_UNLOCKED) {} + +Array3D::~Array3D() {} + +bool Array3D::create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size, + const void *default_value, FillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + return nullptr; + } + storage_ = storage; + uint64_t storage_node_size = sizeof(Array3DHeader); + if (default_value) { + storage_node_size += value_size; + } + storage_node_ = storage->create_node(storage_node_id, storage_node_size); + if (!storage_node_.is_valid()) { + return false; + } + header_ = static_cast<Array3DHeader *>(storage_node_.body()); + *header_ = Array3DHeader(value_size, page_size, table_size, + secondary_table_size, default_value); + if (default_value) { + default_value_ = header_ + 1; + std::memcpy(default_value_, default_value, value_size); + fill_page_ = fill_page; + } + table_caches_.reset( + new (std::nothrow) std::unique_ptr<void *[]>[secondary_table_size]); + if (!table_caches_) { + GRNXX_ERROR() << "new std::unique_ptr<void *[]>[] failed: size = " + << secondary_table_size; + storage->unlink_node(storage_node_.id()); + return false; + } + return true; +} + +bool Array3D::open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size, + FillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + return nullptr; + } + storage_ = storage; + storage_node_ = storage->open_node(storage_node_id); + if (!storage_node_.is_valid()) { + return false; + } + header_ = static_cast<Array3DHeader *>(storage_node_.body()); + if (header_->value_size != value_size) { + GRNXX_ERROR() << "parameter conflict: value_size = " << value_size + << ", stored_value_size = " << header_->value_size; + return false; + } + if (header_->page_size != page_size) { + GRNXX_ERROR() << "parameter conflict: page_size = " << page_size + << ", stored_page_size = " << header_->page_size; + return false; + } + if (header_->table_size != table_size) { + GRNXX_ERROR() << "parameter conflict: table_size = " << table_size + << ", stored_table_size = " << header_->table_size; + return false; + } + if (header_->table_size != table_size) { + GRNXX_ERROR() << "parameter conflict: " + << "secondary_table_size = " << secondary_table_size + << ", stored_secondary_table_size = " + << header_->secondary_table_size; + return false; + } + default_value_ = header_ + 1; + fill_page_ = fill_page; + table_caches_.reset( + new (std::nothrow) std::unique_ptr<void *[]>[secondary_table_size]); + if (!table_caches_) { + GRNXX_ERROR() << "new std::unique_ptr<void *[]>[] failed: size = " + << secondary_table_size; + return false; + } + return true; +} + +bool Array3D::unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size) { + Array3D array; + if (!array.open(storage, storage_node_id, value_size, page_size, + table_size, secondary_table_size, nullptr)) { + return false; + } + return storage->unlink_node(storage_node_id); +} + +void Array3D::initialize_page(uint64_t table_id, uint64_t page_id) { + if (!initialize_page_nothrow(table_id, page_id)) { + GRNXX_ERROR() << "failed to initialize page: table_id = " << table_id + << ", page_id = " << page_id; + GRNXX_THROW(); + } +} + +bool Array3D::initialize_page_nothrow(uint64_t table_id, uint64_t page_id) { + if (!table_caches_[table_id]) { + if (!initialize_table(table_id)) { + return false; + } + } + Lock inter_thread_lock(&page_mutex_); + if (!table_caches_[table_id][page_id]) { + StorageNode table_node = storage_->open_node(secondary_table_[table_id]); + if (!table_node.is_valid()) { + return false; + } + uint32_t * const table = static_cast<uint32_t *>(table_node.body()); + if (table[page_id] == STORAGE_INVALID_NODE_ID) { + Lock inter_process_lock(&header_->page_mutex); + if (table[page_id] == STORAGE_INVALID_NODE_ID) { + StorageNode page_node = + storage_->create_node(secondary_table_[table_id], + header_->value_size * header_->page_size); + if (!page_node.is_valid()) { + return false; + } + if (default_value_) { + fill_page_(page_node.body(), default_value_); + } + table[page_id] = page_node.id(); + table_caches_[table_id][page_id] = page_node.body(); + return true; + } + } + StorageNode page_node = storage_->open_node(table[page_id]); + if (!page_node.is_valid()) { + return false; + } + table_caches_[table_id][page_id] = page_node.body(); + } + return true; +} + +bool Array3D::initialize_table(uint64_t table_id) { + Lock inter_thread_lock(&table_mutex_); + if (!table_caches_[table_id]) { + if (!secondary_table_) { + if (!initialize_secondary_table()) { + return false; + } + } + if (secondary_table_[table_id] == STORAGE_INVALID_NODE_ID) { + Lock inter_process_lock(&header_->table_mutex); + if (secondary_table_[table_id] == STORAGE_INVALID_NODE_ID) { + StorageNode table_node = + storage_->create_node(header_->secondary_table_storage_node_id, + sizeof(uint32_t) * header_->table_size); + if (!table_node.is_valid()) { + return false; + } + uint32_t * const table = static_cast<uint32_t *>(table_node.body()); + for (uint64_t i = 0; i < header_->table_size; ++i) { + table[i] = STORAGE_INVALID_NODE_ID; + } + secondary_table_[table_id] = table_node.id(); + } + } + void ** const table_cache = new void *[header_->table_size]; + if (!table_cache) { + GRNXX_ERROR() << "new void *[] failed: size = " << header_->table_size; + return false; + } + for (uint64_t i = 0; i < header_->table_size; ++i) { + table_cache[i] = nullptr; + } + table_caches_[table_id].reset(table_cache); + } + return true; +} + +bool Array3D::initialize_secondary_table() { + Lock inter_thread_lock(&secondary_table_mutex_); + if (!secondary_table_) { + if (header_->secondary_table_storage_node_id == STORAGE_INVALID_NODE_ID) { + Lock inter_process_lock(&header_->secondary_table_mutex); + if (header_->secondary_table_storage_node_id == STORAGE_INVALID_NODE_ID) { + const uint64_t secondary_table_size = + sizeof(uint32_t) * header_->secondary_table_size; + StorageNode secondary_table_node = + storage_->create_node(storage_node_.id(), secondary_table_size); + if (!secondary_table_node.is_valid()) { + return false; + } + uint32_t * const secondary_table = + static_cast<uint32_t *>(secondary_table_node.body()); + for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { + secondary_table[i] = STORAGE_INVALID_NODE_ID; + } + header_->secondary_table_storage_node_id = secondary_table_node.id(); + secondary_table_ = secondary_table; + return true; + } + } + StorageNode secondary_table_node = + storage_->open_node(header_->secondary_table_storage_node_id); + if (!secondary_table_node.is_valid()) { + return false; + } + secondary_table_ = static_cast<uint32_t *>(secondary_table_node.body()); + } + return true; +} + +} // namespace grnxx Added: lib/grnxx/array/array_3d.hpp (+96 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array/array_3d.hpp 2013-05-13 17:57:42 +0900 (0464bfe) @@ -0,0 +1,96 @@ +/* + 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_ARRAY_ARRAY_3D_HPP +#define GRNXX_ARRAY_ARRAY_3D_HPP + +#include "grnxx/mutex.hpp" +#include "grnxx/storage.hpp" +#include "grnxx/traits.hpp" + +namespace grnxx { + +struct Array3DHeader; + +class Array3D { + using FillPage = void (*)(void *page, const void *value); + + public: + Array3D(); + ~Array3D(); + + bool create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size, + const void *default_value = nullptr, + FillPage fill_page = nullptr); + bool open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size, + FillPage fill_page); + + static bool unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t secondary_table_size); + + uint32_t storage_node_id() const { + return storage_node_.id(); + } + + template <typename T, uint64_t TABLE_SIZE, uint64_t SECONDARY_TABLE_SIZE> + T *get_page(uint64_t page_id) { + const uint64_t table_id = page_id / TABLE_SIZE; + page_id %= TABLE_SIZE; + if (!table_caches_[table_id] || !table_caches_[table_id][page_id]) { + initialize_page(table_id, page_id); + } + return static_cast<T *>(table_caches_[table_id][page_id]); + } + + template <typename T, uint64_t TABLE_SIZE, uint64_t SECONDARY_TABLE_SIZE> + T *get_page_nothrow(uint64_t page_id) { + const uint64_t table_id = page_id / TABLE_SIZE; + page_id %= TABLE_SIZE; + if (!table_caches_[table_id] || !table_caches_[table_id][page_id]) { + if (!initialize_page_nothrow(table_id, page_id)) { + return nullptr; + } + } + return static_cast<T *>(table_caches_[table_id][page_id]); + } + + private: + Storage *storage_; + StorageNode storage_node_; + Array3DHeader *header_; + void *default_value_; + FillPage fill_page_; + uint32_t *secondary_table_; + std::unique_ptr<std::unique_ptr<void *[]>[]> table_caches_; + Mutex page_mutex_; + Mutex table_mutex_; + Mutex secondary_table_mutex_; + + void initialize_page(uint64_t table_id, uint64_t page_id); + bool initialize_page_nothrow(uint64_t table_id, uint64_t page_id); + bool initialize_table(uint64_t table_id); + bool initialize_secondary_table(); +}; + +} // namespace grnxx + +#endif // GRNXX_ARRAY_ARRAY_3D_HPP Added: lib/grnxx/traits.hpp (+70 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/traits.hpp 2013-05-13 17:57:42 +0900 (f7cec8e) @@ -0,0 +1,70 @@ +/* + Copyright (C) 2012 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_TRAITS_HPP +#define GRNXX_TRAITS_HPP + +#include "grnxx/features.hpp" + +#include <type_traits> + +namespace grnxx { + +class GeoPoint; + +// A simple/complex type should use pass by value/reference. +template <typename T> +struct PreferredArgument { + using Type = typename std::conditional<std::is_scalar<T>::value, + T, const T &>::type; +}; +// GeoPoint is not a scalar type but a simple type. +template <> struct PreferredArgument<GeoPoint> { + using Type = GeoPoint; +}; + +// Check if operator<() is defined or not. +struct HasLessHelper { + template <typename T> + static auto check(T *p) -> decltype(p->operator<(), std::true_type()); + template <typename T> + static auto check(T *p) -> decltype(operator<(*p, *p), std::true_type()); + template <typename> + static auto check(...) -> decltype(std::false_type()); +}; +// Check if T has operator<() or not. +template <typename T> +struct HasLess { + static constexpr bool value() { + return std::conditional<std::is_scalar<T>::value, std::true_type, + decltype(HasLessHelper::check<T>(0))>::value; + } +}; + +// Type traits. +template <typename T> +struct Traits { + using Type = T; + using ArgumentType = typename PreferredArgument<T>::Type; + static constexpr bool hass_less() { + return HasLess<T>::value(); + } +}; + +} // namespace grnxx + +#endif // GRNXX_TRAITS_HPP -------------- next part -------------- HTML����������������������������... 下載