susumu.yata
null+****@clear*****
Tue Jul 9 15:59:47 JST 2013
susumu.yata 2013-07-09 15:59:47 +0900 (Tue, 09 Jul 2013) New Revision: cf70a4c95a6cdf5159210846afe3377a6342c45e https://github.com/groonga/grnxx/commit/cf70a4c95a6cdf5159210846afe3377a6342c45e Message: Add an alpha version of Array implementations. Added files: lib/grnxx/array2.cpp lib/grnxx/array2.hpp lib/grnxx/array2_impl.cpp lib/grnxx/array2_impl.hpp Modified files: lib/grnxx/Makefile.am Modified: lib/grnxx/Makefile.am (+4 -0) =================================================================== --- lib/grnxx/Makefile.am 2013-07-09 15:57:26 +0900 (0909220) +++ lib/grnxx/Makefile.am 2013-07-09 15:59:47 +0900 (3a4356b) @@ -15,6 +15,8 @@ libgrnxx_la_LDFLAGS = @AM_LTLDFLAGS@ libgrnxx_la_SOURCES = \ array.cpp \ array_impl.cpp \ + array2.cpp \ + array2_impl.cpp \ backtrace.cpp \ broken_down_time.cpp \ charset.cpp \ @@ -41,6 +43,8 @@ libgrnxx_includedir = ${includedir}/grnxx libgrnxx_include_HEADERS = \ array.hpp \ array_impl.hpp \ + array2.hpp \ + array2_impl.hpp \ backtrace.hpp \ broken_down_time.hpp \ bytes.hpp \ Added: lib/grnxx/array2.cpp (+32 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array2.cpp 2013-07-09 15:59:47 +0900 (e6412a3) @@ -0,0 +1,32 @@ +/* + 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/array2.hpp" + +#include "grnxx/exception.hpp" +#include "grnxx/logger.hpp" + +namespace grnxx { +namespace alpha { + +void ArrayErrorHandler::throw_memory_error() { + GRNXX_ERROR() << "new grnxx::Array failed"; + throw MemoryError(); +} + +} // namespace alpha +} // namespace grnxx Added: lib/grnxx/array2.hpp (+124 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array2.hpp 2013-07-09 15:59:47 +0900 (02bf59c) @@ -0,0 +1,124 @@ +/* + 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_ARRAY2_HPP +#define GRNXX_ARRAY2_HPP + +#include "grnxx/features.hpp" + +#include <memory> +#include <new> + +#include "grnxx/array2_impl.hpp" +#include "grnxx/types.hpp" + +namespace grnxx { + +class Storage; + +namespace alpha { + +struct ArrayErrorHandler { + static void throw_memory_error(); +}; + +template <typename T, uint64_t PAGE_SIZE = 0, uint64_t TABLE_SIZE = 0> +class Array { + // Test template parameters. + static_assert((PAGE_SIZE != 0) || (TABLE_SIZE == 0), + "TABLE_SIZE must be zero if PAGE_SIZE is zero"); + static_assert((PAGE_SIZE & (PAGE_SIZE - 1)) == 0, + "PAGE_SIZE must be zero or a power of two"); + static_assert((TABLE_SIZE & (TABLE_SIZE - 1)) == 0, + "TABLE_SIZE must be zero or a power of two"); + + using Impl = ArrayImpl<T, PAGE_SIZE, TABLE_SIZE>; + + public: + using Value = typename Impl::Value; + using ValueArg = typename Impl::ValueArg; + + ~Array() {} + + // Create an array. + static Array *create(Storage *storage, uint32_t storage_node_id, + uint64_t size) { + std::unique_ptr<Array> array(create_instance()); + array->impl_.create(storage, storage_node_id, size); + return array.release(); + } + // Create an array with default value. + static Array *create(Storage *storage, uint32_t storage_node_id, + uint64_t size, ValueArg default_value) { + std::unique_ptr<Array> array(create_instance()); + array->impl_.create(storage, storage_node_id, size, default_value); + return array.release(); + } + + // Open an array. + static Array *open(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<Array> array(create_instance()); + array->impl_.open(storage, storage_node_id); + return array.release(); + } + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id) { + return Impl::unlink(storage, storage_node_id); + } + + // Return the storage node ID. + uint32_t storage_node_id() const { + return impl_.storage_node_id(); + } + // Return the number of values. + uint64_t size() const { + return impl_.size(); + } + + // Get a reference to a value. + Value &operator[](uint64_t value_id) { + return *impl_.get_value(value_id); + } + // Get a value. + Value get(uint64_t value_id) { + return *impl_.get_value(value_id); + } + // Set a value. + void set(uint64_t value_id, ValueArg value) { + *impl_.get_value(value_id) = value; + } + + private: + Impl impl_; + + Array() : impl_() {} + + // Create an instance or throw an exception on failure. + static Array *create_instance() { + Array * const array = new (std::nothrow) Array; + if (!array) { + ArrayErrorHandler::throw_memory_error(); + } + return array; + } +}; + +} // namespace alpha +} // namespace grnxx + +#endif // GRNXX_ARRAY2_HPP Added: lib/grnxx/array2_impl.cpp (+507 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array2_impl.cpp 2013-07-09 15:59:47 +0900 (8246f94) @@ -0,0 +1,507 @@ +/* + 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/array2_impl.hpp" + +#include <new> + +#include "grnxx/bytes.hpp" +#include "grnxx/common_header.hpp" +#include "grnxx/exception.hpp" +#include "grnxx/lock.hpp" +#include "grnxx/logger.hpp" +#include "grnxx/storage.hpp" + +namespace grnxx { +namespace alpha { +namespace { + +constexpr char FORMAT_STRING[] = "grnxx::Array"; + +} // namespace + +struct ArrayHeader { + CommonHeader common_header; + uint64_t value_size; + uint64_t page_size; + uint64_t table_size; + uint64_t secondary_table_size; + uint64_t size; + uint32_t has_default_value; + union { + uint32_t page_storage_node_id; + uint32_t table_storage_node_id; + uint32_t secondary_table_storage_node_id; + }; + Mutex page_mutex; + Mutex table_mutex; + + // Initialize the members except "common_header". + ArrayHeader(); + + // Return true iff the header seems to be correct. + explicit operator bool() const; +}; + +ArrayHeader::ArrayHeader() + : common_header(FORMAT_STRING), + value_size(0), + page_size(0), + table_size(0), + secondary_table_size(0), + size(0), + has_default_value(0), + page_storage_node_id(STORAGE_INVALID_NODE_ID), + page_mutex(), + table_mutex() {} + +ArrayHeader::operator bool() const { + return common_header.format() == FORMAT_STRING; +} + +Array1D::Array1D() + : page_(nullptr), + size_(0), + storage_node_id_(STORAGE_INVALID_NODE_ID) {} + +Array1D::~Array1D() {} + +void Array1D::create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t, + uint64_t, uint64_t size, + const void *default_value, ArrayFillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + throw LogicError(); + } + StorageNode storage_node = + storage->create_node(storage_node_id, sizeof(ArrayHeader)); + storage_node_id_ = storage_node.id(); + try { + ArrayHeader * const header = + static_cast<ArrayHeader *>(storage_node.body()); + *header = ArrayHeader(); + header->value_size = value_size; + header->page_size = size; + header->size = size; + // Create a page. + StorageNode page_node = + storage->create_node(storage_node_id_, value_size * size); + header->page_storage_node_id = page_node.id(); + page_ = page_node.body(); + if (default_value) { + header->has_default_value = 1; + fill_page(page_, size, default_value); + } + size_ = size; + } catch (...) { + storage->unlink_node(storage_node_id_); + throw; + } +} + +void Array1D::open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t, + uint64_t, ArrayFillPage) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + throw LogicError(); + } + StorageNode storage_node = storage->open_node(storage_node_id); + if (storage_node.size() < sizeof(ArrayHeader)) { + GRNXX_ERROR() << "too small header: size = " << storage_node.size(); + throw LogicError(); + } + storage_node_id_ = storage_node.id(); + const ArrayHeader * const header = + static_cast<ArrayHeader *>(storage_node.body()); + if (!*header) { + GRNXX_ERROR() << "wrong format: expected = " << FORMAT_STRING + << ", actual = " << header->common_header.format(); + throw LogicError(); + } + if (header->value_size != value_size) { + GRNXX_ERROR() << "wrong value_size: expected = " << value_size + << ", actual = " << header->value_size; + throw LogicError(); + } + StorageNode page_node = storage->open_node(header->page_storage_node_id); + page_ = page_node.body(); + size_ = header->size; +} + +bool Array1D::unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size) { + Array1D array; + array.open(storage, storage_node_id, + value_size, page_size, table_size, nullptr); + return storage->unlink_node(storage_node_id); +} + +Array2D::Array2D() + : pages_(), + size_(0), + storage_(nullptr), + storage_node_id_(STORAGE_INVALID_NODE_ID), + header_(nullptr), + fill_page_(nullptr), + table_(nullptr), + mutex_() {} + +Array2D::~Array2D() {} + +void Array2D::create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t, uint64_t size, + const void *default_value, ArrayFillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + throw LogicError(); + } + if ((size % page_size) != 0) { + const uint64_t adjusted_size = size + page_size - (size % page_size); + GRNXX_WARNING() << "size adjustment: before = " << size + << ", after = " << adjusted_size + << ", page_size = " << page_size; + size = adjusted_size; + } + storage_ = storage; + uint64_t storage_node_size = sizeof(ArrayHeader); + if (default_value) { + storage_node_size += value_size; + } + StorageNode storage_node = + storage->create_node(storage_node_id, storage_node_size); + storage_node_id_ = storage_node.id(); + try { + header_ = static_cast<ArrayHeader *>(storage_node.body()); + *header_ = ArrayHeader(); + header_->value_size = value_size; + header_->page_size = page_size; + header_->table_size = size / page_size; + header_->size = size; + if (default_value) { + header_->has_default_value = 1; + std::memcpy(header_ + 1, default_value, value_size); + fill_page_ = fill_page; + } + // Create a table. + StorageNode table_node = storage->create_node( + storage_node_id_, sizeof(uint32_t) * header_->table_size); + header_->table_storage_node_id = table_node.id(); + table_ = static_cast<uint32_t *>(table_node.body()); + for (uint64_t i = 0; i < header_->table_size; ++i) { + table_[i] = STORAGE_INVALID_NODE_ID; + } + reserve_pages(); + size_ = size; + } catch (...) { + storage->unlink_node(storage_node_id_); + throw; + } +} + +void Array2D::open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t , ArrayFillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + throw LogicError(); + } + storage_ = storage; + StorageNode storage_node = storage->open_node(storage_node_id); + if (storage_node.size() < sizeof(ArrayHeader)) { + GRNXX_ERROR() << "too small header: size = " << storage_node.size(); + throw LogicError(); + } + storage_node_id_ = storage_node.id(); + header_ = static_cast<ArrayHeader *>(storage_node.body()); + if (!*header_) { + GRNXX_ERROR() << "wrong format: expected = " << FORMAT_STRING + << ", actual = " << header_->common_header.format(); + throw LogicError(); + } + if (header_->value_size != value_size) { + GRNXX_ERROR() << "wrong value_size: expected = " << value_size + << ", actual = " << header_->value_size; + throw LogicError(); + } + if (header_->page_size != page_size) { + GRNXX_ERROR() << "wrong page_size: expected = " << page_size + << ", actual = " << header_->page_size; + throw LogicError(); + } + if (header_->has_default_value) { + fill_page_ = fill_page; + } + StorageNode table_node = storage->open_node(header_->table_storage_node_id); + table_ = static_cast<uint32_t *>(table_node.body()); + reserve_pages(); + size_ = header_->size; +} + +bool Array2D::unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size) { + Array2D array; + array.open(storage, storage_node_id, + value_size, page_size, table_size, nullptr); + return storage->unlink_node(storage_node_id); +} + +void Array2D::reserve_pages() { + pages_.reset(new (std::nothrow) void *[header_->table_size]); + if (!pages_) { + GRNXX_ERROR() << "new void *[] failed: size = " << header_->table_size; + throw MemoryError(); + } + for (uint64_t i = 0; i < header_->table_size; ++i) { + pages_[i] = invalid_page_address(); + } +} + +void Array2D::reserve_page(uint64_t page_id) { + Lock inter_thread_lock(&mutex_); + if (pages_[page_id] == invalid_page_address()) { + StorageNode page_node; + if (table_[page_id] == STORAGE_INVALID_NODE_ID) { + Lock inter_process_lock(&header_->table_mutex); + if (table_[page_id] == STORAGE_INVALID_NODE_ID) { + // Create a page. + page_node = + storage_->create_node(header_->table_storage_node_id, + header_->value_size * header_->page_size); + if (header_->has_default_value) { + fill_page_(page_node.body(), header_->page_size, header_ + 1); + } + table_[page_id] = page_node.id(); + } + } + if (!page_node) { + page_node = storage_->open_node(table_[page_id]); + } + pages_[page_id] = static_cast<char *>(page_node.body()) + - (header_->value_size * header_->page_size * page_id); + } +} + +Array3D::Array3D() + : tables_(), + size_(0), + storage_(nullptr), + storage_node_id_(STORAGE_INVALID_NODE_ID), + header_(nullptr), + fill_page_(nullptr), + secondary_table_(nullptr), + page_mutex_(), + table_mutex_() {} + +Array3D::~Array3D() { + if (tables_) { + for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { + if (tables_[i] != invalid_table_address()) { + delete [] (tables_[i] + (header_->table_size * i)); + } + } + } +} + +void Array3D::create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t size, + const void *default_value, ArrayFillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + throw LogicError(); + } + if ((size % (page_size * table_size)) != 0) { + const uint64_t adjusted_size = + size + (page_size * table_size) - (size % (page_size * table_size)); + GRNXX_WARNING() << "size adjustment: before = " << size + << ", after = " << adjusted_size + << ", page_size = " << page_size + << ", table_size = " << table_size; + size = adjusted_size; + } + storage_ = storage; + uint64_t storage_node_size = sizeof(ArrayHeader); + if (default_value) { + storage_node_size += value_size; + } + StorageNode storage_node = + storage->create_node(storage_node_id, storage_node_size); + storage_node_id_ = storage_node.id(); + try { + header_ = static_cast<ArrayHeader *>(storage_node.body()); + *header_ = ArrayHeader(); + header_->value_size = value_size; + header_->page_size = page_size; + header_->table_size = table_size; + header_->secondary_table_size = size / (page_size * table_size); + header_->size = size; + if (default_value) { + header_->has_default_value = 1; + std::memcpy(header_ + 1, default_value, value_size); + fill_page_ = fill_page; + } + // Create a secondary table. + StorageNode secondary_table_node = storage->create_node( + storage_node_id_, sizeof(uint32_t) * header_->secondary_table_size); + header_->secondary_table_storage_node_id = secondary_table_node.id(); + 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; + } + reserve_tables(); + size_ = size; + } catch (...) { + storage->unlink_node(storage_node_id_); + throw; + } +} + +void Array3D::open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, ArrayFillPage fill_page) { + if (!storage) { + GRNXX_ERROR() << "invalid argument: storage = nullptr"; + throw LogicError(); + } + storage_ = storage; + StorageNode storage_node = storage->open_node(storage_node_id); + if (storage_node.size() < sizeof(ArrayHeader)) { + GRNXX_ERROR() << "too small header: size = " << storage_node.size(); + throw LogicError(); + } + storage_node_id_ = storage_node.id(); + header_ = static_cast<ArrayHeader *>(storage_node.body()); + if (!*header_) { + GRNXX_ERROR() << "wrong format: expected = " << FORMAT_STRING + << ", actual = " << header_->common_header.format(); + throw LogicError(); + } + if (header_->value_size != value_size) { + GRNXX_ERROR() << "wrong value_size: expected = " << value_size + << ", actual = " << header_->value_size; + throw LogicError(); + } + if (header_->page_size != page_size) { + GRNXX_ERROR() << "wrong page_size: expected = " << page_size + << ", actual = " << header_->page_size; + throw LogicError(); + } + if (header_->table_size != table_size) { + GRNXX_ERROR() << "wrong table_size: expected = " << table_size + << ", actual = " << header_->table_size; + throw LogicError(); + } + if (header_->has_default_value) { + fill_page_ = fill_page; + } + StorageNode secondary_table_node = + storage->open_node(header_->secondary_table_storage_node_id); + secondary_table_ = static_cast<uint32_t *>(secondary_table_node.body()); + reserve_tables(); + size_ = header_->size; +} + +bool Array3D::unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size) { + Array3D array; + array.open(storage, storage_node_id, + value_size, page_size, table_size, nullptr); + return storage->unlink_node(storage_node_id); +} + +void Array3D::reserve_tables() { + tables_.reset(new (std::nothrow) void **[header_->secondary_table_size]); + if (!tables_) { + GRNXX_ERROR() << "new void **[] failed: size = " + << header_->secondary_table_size; + throw MemoryError(); + } + for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { + tables_[i] = invalid_table_address(); + } +} + +void Array3D::reserve_page(uint64_t page_id) { + const uint64_t table_id = page_id / header_->table_size; + if (tables_[table_id] == invalid_table_address()) { + reserve_table(table_id); + } + Lock inter_thread_lock(&page_mutex_); + if (tables_[table_id][page_id] == invalid_page_address()) { + StorageNode page_node; + StorageNode table_node = storage_->open_node(secondary_table_[table_id]); + uint32_t * const table = static_cast<uint32_t *>(table_node.body()) + - (header_->table_size * table_id); + if (table[page_id] == STORAGE_INVALID_NODE_ID) { + Lock inter_process_lock(&header_->page_mutex); + if (table[page_id] == STORAGE_INVALID_NODE_ID) { + // Create a page. + page_node = storage_->create_node( + secondary_table_[table_id], + header_->value_size * header_->page_size); + if (header_->has_default_value) { + fill_page_(page_node.body(), header_->page_size, header_ + 1); + } + table[page_id] = page_node.id(); + } + } + if (!page_node) { + page_node = storage_->open_node(table[page_id]); + } + tables_[table_id][page_id] = static_cast<char *>(page_node.body()) + - (header_->value_size * header_->page_size * page_id); + } +} + +void Array3D::reserve_table(uint64_t table_id) { + Lock inter_thread_lock(&table_mutex_); + if (tables_[table_id] == invalid_table_address()) { + 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) { + // Create a table. + StorageNode table_node = + storage_->create_node(header_->secondary_table_storage_node_id, + sizeof(uint32_t) * header_->table_size); + 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(); + } + } + // Create a table cache. + void ** const pages = new (std::nothrow) void *[header_->table_size]; + if (!pages) { + GRNXX_ERROR() << "new void *[] failed: size = " << header_->table_size; + throw MemoryError(); + } + for (uint64_t i = 0; i < header_->table_size; ++i) { + pages[i] = invalid_page_address(); + } + tables_[table_id] = pages - (header_->table_size * table_id); + } +} + +} // namespace alpha +} // namespace grnxx Added: lib/grnxx/array2_impl.hpp (+295 -0) 100644 =================================================================== --- /dev/null +++ lib/grnxx/array2_impl.hpp 2013-07-09 15:59:47 +0900 (9d11ff2) @@ -0,0 +1,295 @@ +/* + 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_ARRAY2_IMPL_HPP +#define GRNXX_ARRAY2_IMPL_HPP + +#include "grnxx/features.hpp" + +#include <memory> + +#include "grnxx/mutex.hpp" +#include "grnxx/traits.hpp" +#include "grnxx/types.hpp" + +namespace grnxx { + +class Storage; + +namespace alpha { + +struct ArrayHeader; + +// Fill "page" with "value". +using ArrayFillPage = void (*)(void *page, uint64_t page_size, + const void *value); + +class Array1D { + public: + Array1D(); + ~Array1D(); + + // Create an array. + void create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t size, + const void *default_value, ArrayFillPage fill_page); + // Open an array. + void open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, ArrayFillPage fill_page); + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size); + + // Return the storage node ID. + uint32_t storage_node_id() const { + return storage_node_id_; + } + // Return the number of values. + uint64_t size() const { + return size_; + } + + // Return a pointer to a value. + template <typename T, uint64_t, uint64_t> + T *get_value(uint64_t value_id) { + return &static_cast<T *>(page_)[value_id]; + } + + private: + void *page_; + uint64_t size_; + uint32_t storage_node_id_; +}; + +class Array2D { + public: + Array2D(); + ~Array2D(); + + // Create an array. + void create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t size, + const void *default_value, ArrayFillPage fill_page); + // Open an array. + void open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, ArrayFillPage fill_page); + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size); + + // Return the storage node ID. + uint32_t storage_node_id() const { + return storage_node_id_; + } + // Return the number of values. + uint64_t size() const { + return size_; + } + + // Return a pointer to a value. + template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> + T *get_value(uint64_t value_id) { + const uint64_t page_id = value_id / PAGE_SIZE; + if (pages_[page_id] == invalid_page_address()) { + reserve_page(page_id); + } + return &static_cast<T *>(pages_[page_id])[value_id]; + } + + private: + std::unique_ptr<void *[]> pages_; + uint64_t size_; + Storage *storage_; + uint32_t storage_node_id_; + ArrayHeader *header_; + ArrayFillPage fill_page_; + uint32_t *table_; + Mutex mutex_; + + void reserve_pages(); + void reserve_page(uint64_t page_id); + + static void *invalid_page_address() { + return static_cast<char *>(nullptr) - 1; + } +}; + +class Array3D { + using ArrayPageFiller = void (*)(void *page, const void *value); + + public: + Array3D(); + ~Array3D(); + + // Create an array. + void create(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, uint64_t size, + const void *default_value, ArrayFillPage fill_page); + // Open an array. + void open(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size, ArrayFillPage fill_page); + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id, + uint64_t value_size, uint64_t page_size, + uint64_t table_size); + + // Return the storage node ID. + uint32_t storage_node_id() const { + return storage_node_id_; + } + // Return the number of values. + uint64_t size() const { + return size_; + } + + // Return a pointer to a value. + template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> + T *get_value(uint64_t value_id) { + const uint64_t table_id = value_id / (PAGE_SIZE * TABLE_SIZE); + const uint64_t page_id = value_id / PAGE_SIZE; + if ((tables_[table_id] == invalid_page_address()) || + (tables_[table_id][page_id] == invalid_page_address())) { + reserve_page(page_id); + } + return &static_cast<T *>(tables_[table_id][page_id])[value_id]; + } + + private: + std::unique_ptr<void **[]> tables_; + uint64_t size_; + Storage *storage_; + uint32_t storage_node_id_; + ArrayHeader *header_; + ArrayFillPage fill_page_; + uint32_t *secondary_table_; + Mutex page_mutex_; + Mutex table_mutex_; + + void reserve_tables(); + void reserve_page(uint64_t page_id); + void reserve_table(uint64_t table_id); + + static void **invalid_table_address() { + return reinterpret_cast<void **>(static_cast<char *>(nullptr) + 1); + } + static void *invalid_page_address() { + return static_cast<char *>(nullptr) + 1; + } +}; + +template <uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> +struct ArrayImplSelector; + +// Use Array1D. +template <> +struct ArrayImplSelector<0, 0> { + using Type = Array1D; +}; + +// Use Array2D. +template <uint64_t PAGE_SIZE> +struct ArrayImplSelector<PAGE_SIZE, 0> { + using Type = Array2D; +}; + +// Use Array3D. +template <uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> +struct ArrayImplSelector { + using Type = Array3D; +}; + +template <typename T> +struct ArrayPageFiller { + // Fill "page" with "value". + // This function is used to initialize a page. + static void fill_page(void *page, uint64_t page_size, const void *value) { + for (uint64_t i = 0; i < page_size; ++i) { + static_cast<T *>(page)[i] = *static_cast<const T *>(value); + } + } +}; + +template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> +class ArrayImpl { + using Impl = typename ArrayImplSelector<PAGE_SIZE, TABLE_SIZE>::Type; + + public: + using Value = typename Traits<T>::Type; + using ValueArg = typename Traits<T>::ArgumentType; + + ArrayImpl() : impl_() {} + ~ArrayImpl() {} + + // Create an array. + void create(Storage *storage, uint32_t storage_node_id, uint64_t size) { + impl_.create(storage, storage_node_id, + sizeof(Value), PAGE_SIZE, TABLE_SIZE, size, + nullptr, ArrayPageFiller<Value>::fill_page); + } + // Create an array with the default value. + void create(Storage *storage, uint32_t storage_node_id, uint64_t size, + ValueArg default_value) { + impl_.create(storage, storage_node_id, + sizeof(Value), PAGE_SIZE, TABLE_SIZE, size, + &default_value, ArrayPageFiller<Value>::fill_page); + } + // Open an array. + void open(Storage *storage, uint32_t storage_node_id) { + impl_.open(storage, storage_node_id, + sizeof(Value), PAGE_SIZE, TABLE_SIZE, + ArrayPageFiller<Value>::fill_page); + } + + // Unlink an array. + static bool unlink(Storage *storage, uint32_t storage_node_id) { + return Impl::unlink(storage, storage_node_id, + sizeof(Value), PAGE_SIZE, TABLE_SIZE); + } + + // Return the storage node ID. + uint32_t storage_node_id() const { + return impl_.storage_node_id(); + } + // Return the number of values. + uint64_t size() const { + return impl_.size(); + } + + // Return a pointer to a value. + Value *get_value(uint64_t value_id) { + return impl_. template get_value<Value, PAGE_SIZE, TABLE_SIZE>(value_id); + } + + private: + Impl impl_; +}; + +} // namespace alpha +} // namespace grnxx + +#endif // GRNXX_ARRAY2_IMPL_HPP -------------- next part -------------- HTML����������������������������...Download