susumu.yata
null+****@clear*****
Tue Jul 16 19:27:01 JST 2013
susumu.yata 2013-07-16 19:27:01 +0900 (Tue, 16 Jul 2013) New Revision: c87d8b275d70f986e59d13d1c09bb7f79d2034bd https://github.com/groonga/grnxx/commit/c87d8b275d70f986e59d13d1c09bb7f79d2034bd Message: Replace grnxx::Array with grnxx::alpha::Array. Removed 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 lib/grnxx/array.hpp lib/grnxx/array_impl.cpp lib/grnxx/array_impl.hpp lib/grnxx/map/array_map.cpp lib/grnxx/map/bytes_array.cpp lib/grnxx/map/bytes_array.hpp lib/grnxx/map/bytes_store.cpp lib/grnxx/map/bytes_store.hpp lib/grnxx/map/double_array.cpp lib/grnxx/map/double_array.hpp lib/grnxx/map/hash_table.cpp lib/grnxx/map/hash_table/key_id_array.hpp lib/grnxx/map/key_store.cpp lib/grnxx/map/key_store.hpp lib/grnxx/map/patricia.cpp lib/grnxx/map/patricia.hpp test/test_array.cpp test/test_map.cpp Modified: lib/grnxx/Makefile.am (+0 -4) =================================================================== --- lib/grnxx/Makefile.am 2013-07-16 15:25:57 +0900 (3a4356b) +++ lib/grnxx/Makefile.am 2013-07-16 19:27:01 +0900 (0909220) @@ -15,8 +15,6 @@ 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 \ @@ -43,8 +41,6 @@ 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 \ Modified: lib/grnxx/array.hpp (+30 -182) =================================================================== --- lib/grnxx/array.hpp 2013-07-16 15:25:57 +0900 (d92f31d) +++ lib/grnxx/array.hpp 2013-07-16 19:27:01 +0900 (424ccfc) @@ -24,53 +24,40 @@ #include <new> #include "grnxx/array_impl.hpp" -#include "grnxx/traits.hpp" #include "grnxx/types.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; - -class ArrayErrorHandler { - public: +struct ArrayErrorHandler { static void throw_memory_error(); }; -template <typename T, - uint64_t PAGE_SIZE = ARRAY_DEFAULT_PAGE_SIZE, - uint64_t TABLE_SIZE = ARRAY_DEFAULT_TABLE_SIZE, - uint64_t SECONDARY_TABLE_SIZE = ARRAY_DEFAULT_SECONDARY_TABLE_SIZE> +template <typename T, uint64_t PAGE_SIZE = 0, uint64_t TABLE_SIZE = 0> 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 Impl = ArrayImpl<T, PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE>; + using Impl = ArrayImpl<T, PAGE_SIZE, TABLE_SIZE>; public: - using Value = typename Impl::Value; + using Value = typename Impl::Value; using ValueArg = typename Impl::ValueArg; + using ValueRef = typename Impl::ValueRef; + using Unit = typename Impl::Unit; ~Array() {} // Create an array. - static Array *create(Storage *storage, uint32_t storage_node_id) { + 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); + array->impl_.create(storage, storage_node_id, size); return array.release(); } - - // Create an array with the default value. + // Create an array with default value. static Array *create(Storage *storage, uint32_t storage_node_id, - ValueArg default_value) { + uint64_t size, ValueArg default_value) { std::unique_ptr<Array> array(create_instance()); - array->impl_.create(storage, storage_node_id, default_value); + array->impl_.create(storage, storage_node_id, size, default_value); return array.release(); } @@ -86,178 +73,39 @@ class Array { Impl::unlink(storage, storage_node_id); } - // Return the number of values in each page. - static constexpr uint64_t page_size() { - return Impl::page_size(); - } - // Return the number of pages in each table. - static constexpr uint64_t table_size() { - return Impl::table_size(); - } - // Return the number of tables in each secondary table. - static constexpr uint64_t secondary_table_size() { - return Impl::secondary_table_size(); - } - // Return the number of values in Array. - static constexpr uint64_t size() { - return Impl::size(); - } - // Return the storage node ID. uint32_t storage_node_id() const { return impl_.storage_node_id(); } - - // Get a value and return true on success. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value) { - return impl_.get(value_id, value); - } - // Set a value and return true on success. - bool set(uint64_t value_id, ValueArg value) { - return impl_.set(value_id, value); - } - // Get a value and return its address on success. - Value *get_pointer(uint64_t value_id) { - return impl_.get_pointer(value_id); - } - // Get a page and return its starting address on success. - Value *get_page(uint64_t page_id) { - return impl_.get_page(page_id); - } - - private: - Impl impl_; - - Array() : impl_() {} - - static Array *create_instance() { - Array * const array = new (std::nothrow) Array; - if (!array) { - ArrayErrorHandler::throw_memory_error(); - } - return array; - } -}; - -// Bit array. -template <uint64_t PAGE_SIZE_IN_BITS, - uint64_t TABLE_SIZE, - uint64_t SECONDARY_TABLE_SIZE> -class Array<bool, PAGE_SIZE_IN_BITS, TABLE_SIZE, SECONDARY_TABLE_SIZE> { - public: - // Internal type to store bits. - using Unit = uint64_t; - - private: - static constexpr uint64_t UNIT_SIZE = sizeof(Unit) * 8; - static constexpr uint64_t PAGE_SIZE = PAGE_SIZE_IN_BITS / UNIT_SIZE; - - static_assert((PAGE_SIZE_IN_BITS % UNIT_SIZE) == 0, - "(PAGE_SIZE_IN_BITS % UNIT_SIZE) != 0"); - using UnitArray = ArrayImpl<Unit, PAGE_SIZE, TABLE_SIZE, - SECONDARY_TABLE_SIZE>; - - public: - using Value = typename Traits<bool>::Type; - using ValueArg = typename Traits<bool>::ArgumentType; - - ~Array() {} - - // Create an array. - static Array *create(Storage *storage, uint32_t storage_node_id) { - std::unique_ptr<Array> array(create_instance()); - array->units_.create(storage, storage_node_id); - 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(create_instance()); - array->units_.create(storage, storage_node_id, - default_value ? ~Unit(0) : Unit(0)); - return array.release(); - } - - // Open an array. - static Array *open(Storage *storage, uint32_t storage_node_id) { - std::unique_ptr<Array> array(create_instance()); - array->units_.open(storage, storage_node_id); - return array.release(); - } - - // Unlink an array. - static void unlink(Storage *storage, uint32_t storage_node_id) { - UnitArray::unlink(storage, storage_node_id); - } - - // Return the number of values in each unit. - static constexpr uint64_t unit_size() { - return UNIT_SIZE; - } - // Return the number of values in each page. - static constexpr uint64_t page_size() { - return PAGE_SIZE_IN_BITS; - } - // 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 number of values. + uint64_t size() const { + return impl_.size(); } - // Return the storage node ID. - uint32_t storage_node_id() const { - return units_.storage_node_id(); + // Get a value. + Value get(uint64_t value_id) { + return get_value(value_id); } - - // Get a value and return true on success. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value) { - const uint64_t unit_id = value_id / UNIT_SIZE; - const Unit * const page = get_page(unit_id / PAGE_SIZE); - if (value) { - *value = (page[unit_id % PAGE_SIZE] & - (Unit(1) << (value_id % UNIT_SIZE))) != 0; - } - return true; + // Set a value. + void set(uint64_t value_id, ValueArg value) { + get_value(value_id) = value; } - // Set a value and return true on success. - // Note that if bits in the same byte are set at the same time, the result is - // undefined. - bool set(uint64_t value_id, ValueArg value) { - const uint64_t unit_id = value_id / UNIT_SIZE; - Unit * const page = get_page(unit_id / PAGE_SIZE); - if (value) { - page[unit_id % PAGE_SIZE] |= Unit(1) << (value_id % UNIT_SIZE); - } else { - page[unit_id % PAGE_SIZE] &= ~(Unit(1) << (value_id % UNIT_SIZE)); - } - return true; + // Get a reference to a value. + ValueRef get_value(uint64_t value_id) { + return impl_.get_value(value_id); } - - // Get a unit and return its address on success. - Unit *get_unit(uint64_t unit_id) { - return units_.get_pointer(unit_id); - } - // Get a page and return its starting address on success. - Unit *get_page(uint64_t page_id) { - return units_.get_page(page_id); + // Get a reference to a unit. + Unit &get_unit(uint64_t unit_id) { + return impl_.get_unit(unit_id); } private: - UnitArray units_; + Impl impl_; - Array() : units_() {} + Array() : impl_() {} + // Create an instance or throw an exception on failure. static Array *create_instance() { Array * const array = new (std::nothrow) Array; if (!array) { Deleted: lib/grnxx/array2.cpp (+0 -32) 100644 =================================================================== --- lib/grnxx/array2.cpp 2013-07-16 15:25:57 +0900 (e6412a3) +++ /dev/null @@ -1,32 +0,0 @@ -/* - 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 Deleted: lib/grnxx/array2.hpp (+0 -123) 100644 =================================================================== --- lib/grnxx/array2.hpp 2013-07-16 15:25:57 +0900 (4254ef2) +++ /dev/null @@ -1,123 +0,0 @@ -/* - 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 { - using Impl = ArrayImpl<T, PAGE_SIZE, TABLE_SIZE>; - - public: - using Value = typename Impl::Value; - using ValueArg = typename Impl::ValueArg; - using ValueRef = typename Impl::ValueRef; - using Unit = typename Impl::Unit; - - ~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 void unlink(Storage *storage, uint32_t storage_node_id) { - 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 value. - Value get(uint64_t value_id) { - return get_value(value_id); - } - // Set a value. - void set(uint64_t value_id, ValueArg value) { - get_value(value_id) = value; - } - - // Get a reference to a value. - ValueRef get_value(uint64_t value_id) { - return impl_.get_value(value_id); - } - // Get a reference to a unit. - Unit &get_unit(uint64_t unit_id) { - return impl_.get_unit(unit_id); - } - - 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 Deleted: lib/grnxx/array2_impl.cpp (+0 -594) 100644 =================================================================== --- lib/grnxx/array2_impl.cpp 2013-07-16 15:25:57 +0900 (5d04d86) +++ /dev/null @@ -1,594 +0,0 @@ -/* - 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/intrinsic.hpp" -#include "grnxx/lock.hpp" -#include "grnxx/logger.hpp" -#include "grnxx/storage.hpp" - -namespace grnxx { -namespace alpha { -namespace { - -constexpr char FORMAT_STRING[] = "grnxx::Array"; - -struct DummyTable { - void **pages; - uint32_t reference_count; - Mutex mutex; - - DummyTable() : pages(nullptr), reference_count(0), mutex() {} -}; - -class DummyTableManager { - public: - // Get a singleton. - static DummyTableManager &get(); - - // Get a dummy table. - void **get_dummy_table(uint64_t table_size); - // Free a dummy table. - void free_dummy_table(uint64_t table_size); - - private: - DummyTable dummy_tables_[64]; - - DummyTableManager() : dummy_tables_() {} - - const DummyTableManager(const DummyTableManager &) = delete; - DummyTableManager &operator=(const DummyTableManager &) = delete; -}; - -DummyTableManager &DummyTableManager::get() { - static DummyTableManager singleton; - return singleton; -} - -void **DummyTableManager::get_dummy_table(uint64_t table_size) { - const uint64_t table_id = bit_scan_reverse(table_size); - DummyTable &dummy_table = dummy_tables_[table_id]; - Lock lock(&dummy_table.mutex); - if (dummy_table.reference_count == 0) { - if (dummy_table.pages) { - GRNXX_ERROR() << "already exists: table_size = " << table_size; - throw LogicError(); - } - // Create a dummy table. - dummy_table.pages = new (std::nothrow) void *[table_size]; - if (!dummy_table.pages) { - GRNXX_ERROR() << "new void *[] failed: size = " << table_size; - throw MemoryError(); - } - for (uint64_t i = 0; i < table_size; ++i) { - dummy_table.pages[i] = Array3D::invalid_page(); - } - } else if (!dummy_table.pages) { - GRNXX_ERROR() << "invalid pages: table_size = " << table_size; - throw LogicError(); - } - ++dummy_table.reference_count; - return dummy_table.pages; -} - -void DummyTableManager::free_dummy_table(uint64_t table_size) { - const uint64_t table_id = bit_scan_reverse(table_size); - DummyTable &dummy_table = dummy_tables_[table_id]; - Lock lock(&dummy_table.mutex); - if (!dummy_table.pages || (dummy_table.reference_count == 0)) { - GRNXX_ERROR() << "already freed: table_size = " << table_size; - throw LogicError(); - } - if (dummy_table.reference_count == 1) { - // Free a dummy table. - delete [] dummy_table.pages; - dummy_table.pages = nullptr; - } - --dummy_table.reference_count; -} - -} // 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; -} - -void 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); - 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; -} - -void 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); - storage->unlink_node(storage_node_id); -} - -void Array2D::reserve_pages() { - // Create a table cache. - 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(); - } -} - -void Array2D::reserve_page(uint64_t page_id) { - Lock inter_thread_lock(&mutex_); - if (pages_[page_id] == invalid_page()) { - 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), - dummy_table_(nullptr), - page_mutex_(), - table_mutex_() {} - -Array3D::~Array3D() { - if (tables_) { - uint64_t offset = 0; - for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { - if (tables_[i] != (dummy_table_ - offset)) { - delete [] (tables_[i] + offset); - } - offset += header_->table_size; - } - } - if (dummy_table_) { - DummyTableManager::get().free_dummy_table(header_->table_size); - } -} - -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; -} - -void 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); - storage->unlink_node(storage_node_id); -} - -void Array3D::reserve_tables() { - dummy_table_ = DummyTableManager::get().get_dummy_table(header_->table_size); - // Create a secondary table cache. - tables_.reset(new (std::nothrow) void **[header_->secondary_table_size]); - if (!tables_) { - GRNXX_ERROR() << "new void **[] failed: size = " - << header_->secondary_table_size; - throw MemoryError(); - } - // Fill the secondary table cache with the dummy table cache. - uint64_t offset = 0; - for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { - tables_[i] = dummy_table_ - offset; - offset += header_->table_size; - } -} - -void Array3D::reserve_page(uint64_t page_id) { - const uint64_t table_id = page_id / header_->table_size; - if (tables_[table_id] == (dummy_table_ - (header_->table_size * table_id))) { - reserve_table(table_id); - } - Lock inter_thread_lock(&page_mutex_); - if (tables_[table_id][page_id] == invalid_page()) { - 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] == (dummy_table_ - (header_->table_size * table_id))) { - 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(); - } - tables_[table_id] = pages - (header_->table_size * table_id); - } -} - -} // namespace alpha -} // namespace grnxx Deleted: lib/grnxx/array2_impl.hpp (+0 -431) 100644 =================================================================== --- lib/grnxx/array2_impl.hpp 2013-07-16 15:25:57 +0900 (1d8804d) +++ /dev/null @@ -1,431 +0,0 @@ -/* - 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 void 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 reference 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 void 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 reference 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()) { - 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_; - - // Initialize "pages_". - void reserve_pages(); - // Open or create a page. - void reserve_page(uint64_t page_id); - - // Return a pointer to an invalid page. - static void *invalid_page() { - 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 void 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 reference 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][page_id] == invalid_page()) { - reserve_page(page_id); - } - return static_cast<T *>(tables_[table_id][page_id])[value_id]; - } - - // Return a pointer to an invalid page. - static void *invalid_page() { - return static_cast<char *>(nullptr) + 1; - } - - 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_; - void **dummy_table_; - Mutex page_mutex_; - Mutex table_mutex_; - - // Initialize "tables_". - void reserve_tables(); - // Open or create a page. - void reserve_page(uint64_t page_id); - // Open or create a table. - void reserve_table(uint64_t table_id); -}; - -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 { - // 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 = typename ArrayImplSelector<PAGE_SIZE, TABLE_SIZE>::Type; - - public: - using Value = typename Traits<T>::Type; - using ValueArg = typename Traits<T>::ArgumentType; - using ValueRef = Value &; - using Unit = Value; - - 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 void unlink(Storage *storage, uint32_t storage_node_id) { - 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 reference to a value. - ValueRef get_value(uint64_t value_id) { - return impl_. template get_value<Value, PAGE_SIZE, TABLE_SIZE>(value_id); - } - // Return a reference to a unit. - Unit &get_unit(uint64_t unit_id) { - return get_value(unit_id); - } - - private: - Impl impl_; -}; - -// A reference to a bit. -class ArrayBitRef { - public: - using Unit = uint64_t; - - // Create a reference to a bit. - ArrayBitRef(Unit &unit, Unit mask) : unit_(unit), mask_(mask) {} - - // Get a bit. - operator bool() const { - return (unit_ & mask_) != 0; - } - - // Set a bit. - ArrayBitRef &operator=(bool value) { - if (value) { - unit_ |= mask_; - } else { - unit_ &= ~mask_; - } - return *this; - } - - // Copy a bit. - ArrayBitRef &operator=(const ArrayBitRef &rhs) { - return *this = bool(rhs); - } - - // Compare bits. - bool operator==(bool rhs) const { - return bool(*this) == rhs; - } - bool operator!=(bool rhs) const { - return bool(*this) != rhs; - } - - private: - Unit &unit_; - Unit mask_; -}; - -// An array of bits. -template <uint64_t PAGE_SIZE_IN_BITS, uint64_t TABLE_SIZE> -class ArrayImpl<bool, PAGE_SIZE_IN_BITS, TABLE_SIZE> { - static constexpr uint64_t UNIT_SIZE = sizeof(ArrayBitRef::Unit) * 8; - static constexpr uint64_t PAGE_SIZE = PAGE_SIZE_IN_BITS / UNIT_SIZE; - - // Test template parameters. - static_assert((PAGE_SIZE_IN_BITS % UNIT_SIZE) == 0, - "(PAGE_SIZE_IN_BITS % UNIT_SIZE) != 0"); - 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 = typename ArrayImplSelector<PAGE_SIZE, TABLE_SIZE>::Type; - - public: - using Value = typename Traits<bool>::Type; - using ValueArg = typename Traits<bool>::ArgumentType; - using ValueRef = ArrayBitRef; - using Unit = ArrayBitRef::Unit; - - 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(Unit), PAGE_SIZE, TABLE_SIZE, size / UNIT_SIZE, - nullptr, ArrayPageFiller<Unit>::fill_page); - } - // Create an array with the default value. - void create(Storage *storage, uint32_t storage_node_id, uint64_t size, - ValueArg default_value) { - const Unit default_unit = default_value ? ~(Unit)0 : (Unit)0; - impl_.create(storage, storage_node_id, - sizeof(Unit), PAGE_SIZE, TABLE_SIZE, size / UNIT_SIZE, - &default_unit, ArrayPageFiller<Unit>::fill_page); - } - // Open an array. - void open(Storage *storage, uint32_t storage_node_id) { - impl_.open(storage, storage_node_id, - sizeof(Unit), PAGE_SIZE, TABLE_SIZE, - ArrayPageFiller<Unit>::fill_page); - } - - // Unlink an array. - static void unlink(Storage *storage, uint32_t storage_node_id) { - Impl::unlink(storage, storage_node_id, - sizeof(Unit), 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() * UNIT_SIZE; - } - - // Return a reference to a value. - ValueRef get_value(uint64_t value_id) { - return ValueRef(get_unit(value_id / UNIT_SIZE), - Unit(1) << (value_id % UNIT_SIZE)); - } - // Return a reference to a unit. - Unit &get_unit(uint64_t unit_id) { - return impl_. template get_value<Unit, PAGE_SIZE, TABLE_SIZE>(unit_id); - } - - private: - Impl impl_; -}; - -} // namespace alpha -} // namespace grnxx - -#endif // GRNXX_ARRAY2_IMPL_HPP Modified: lib/grnxx/array_impl.cpp (+310 -186) =================================================================== --- lib/grnxx/array_impl.cpp 2013-07-16 15:25:57 +0900 (f2775a4) +++ lib/grnxx/array_impl.cpp 2013-07-16 19:27:01 +0900 (27b6c9d) @@ -19,54 +19,145 @@ #include <new> +#include "grnxx/bytes.hpp" +#include "grnxx/common_header.hpp" #include "grnxx/exception.hpp" +#include "grnxx/intrinsic.hpp" #include "grnxx/lock.hpp" #include "grnxx/logger.hpp" #include "grnxx/storage.hpp" namespace grnxx { +namespace { + +constexpr char FORMAT_STRING[] = "grnxx::Array"; + +struct DummyTable { + void **pages; + uint32_t reference_count; + Mutex mutex; + + DummyTable() : pages(nullptr), reference_count(0), mutex() {} +}; + +class DummyTableManager { + public: + // Get a singleton. + static DummyTableManager &get(); + + // Get a dummy table. + void **get_dummy_table(uint64_t table_size); + // Free a dummy table. + void free_dummy_table(uint64_t table_size); + + private: + DummyTable dummy_tables_[64]; + + DummyTableManager() : dummy_tables_() {} + + const DummyTableManager(const DummyTableManager &) = delete; + DummyTableManager &operator=(const DummyTableManager &) = delete; +}; + +DummyTableManager &DummyTableManager::get() { + static DummyTableManager singleton; + return singleton; +} + +void **DummyTableManager::get_dummy_table(uint64_t table_size) { + const uint64_t table_id = bit_scan_reverse(table_size); + DummyTable &dummy_table = dummy_tables_[table_id]; + Lock lock(&dummy_table.mutex); + if (dummy_table.reference_count == 0) { + if (dummy_table.pages) { + GRNXX_ERROR() << "already exists: table_size = " << table_size; + throw LogicError(); + } + // Create a dummy table. + dummy_table.pages = new (std::nothrow) void *[table_size]; + if (!dummy_table.pages) { + GRNXX_ERROR() << "new void *[] failed: size = " << table_size; + throw MemoryError(); + } + for (uint64_t i = 0; i < table_size; ++i) { + dummy_table.pages[i] = Array3D::invalid_page(); + } + } else if (!dummy_table.pages) { + GRNXX_ERROR() << "invalid pages: table_size = " << table_size; + throw LogicError(); + } + ++dummy_table.reference_count; + return dummy_table.pages; +} + +void DummyTableManager::free_dummy_table(uint64_t table_size) { + const uint64_t table_id = bit_scan_reverse(table_size); + DummyTable &dummy_table = dummy_tables_[table_id]; + Lock lock(&dummy_table.mutex); + if (!dummy_table.pages || (dummy_table.reference_count == 0)) { + GRNXX_ERROR() << "already freed: table_size = " << table_size; + throw LogicError(); + } + if (dummy_table.reference_count == 1) { + // Free a dummy table. + delete [] dummy_table.pages; + dummy_table.pages = nullptr; + } + --dummy_table.reference_count; +} + +} // 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; - uint32_t page_storage_node_id; - uint32_t table_storage_node_id; - uint32_t secondary_table_storage_node_id; - uint32_t reserved; + 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; - Mutex secondary_table_mutex; + // Initialize the members except "common_header". ArrayHeader(); + + // Return true iff the header seems to be correct. + explicit operator bool() const; }; ArrayHeader::ArrayHeader() - : value_size(1), - page_size(1), - table_size(1), - secondary_table_size(1), - has_default_value(false), + : 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), - table_storage_node_id(STORAGE_INVALID_NODE_ID), - secondary_table_storage_node_id(STORAGE_INVALID_NODE_ID), - reserved(0), page_mutex(), - table_mutex(), - secondary_table_mutex() {} + table_mutex() {} + +ArrayHeader::operator bool() const { + return common_header.format() == FORMAT_STRING; +} Array1D::Array1D() - : storage_node_id_(STORAGE_INVALID_NODE_ID), - header_(nullptr), - page_(nullptr) {} + : 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 page_size, - const void *default_value, FillPage fill_page) { + 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(); @@ -75,18 +166,22 @@ void Array1D::create(Storage *storage, uint32_t storage_node_id, storage->create_node(storage_node_id, sizeof(ArrayHeader)); 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; + 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 * page_size); - header_->page_storage_node_id = page_node.id(); + 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 = true; - fill_page(page_, default_value); + header->has_default_value = 1; + fill_page(page_, size, default_value); } + size_ = size; } catch (...) { storage->unlink_node(storage_node_id_); throw; @@ -94,60 +189,71 @@ void Array1D::create(Storage *storage, uint32_t storage_node_id, } void Array1D::open(Storage *storage, uint32_t storage_node_id, - uint64_t value_size, uint64_t page_size) { + 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() << "invalid format: node_size = " << storage_node.size() - << ", header_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_->value_size != value_size) { - GRNXX_ERROR() << "parameter conflict: value_size = " << value_size - << ", stored_value_size = " << header_->value_size; + 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_->page_size != page_size) { - GRNXX_ERROR() << "parameter conflict: page_size = " << page_size - << ", stored_page_size = " << header_->page_size; + 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); + StorageNode page_node = storage->open_node(header->page_storage_node_id); page_ = page_node.body(); + size_ = header->size; } void Array1D::unlink(Storage *storage, uint32_t storage_node_id, - uint64_t value_size, uint64_t page_size) { + uint64_t value_size, uint64_t page_size, + uint64_t table_size) { Array1D array; - array.open(storage, storage_node_id, value_size, page_size); + array.open(storage, storage_node_id, + value_size, page_size, table_size, nullptr); storage->unlink_node(storage_node_id); } Array2D::Array2D() - : storage_(nullptr), + : pages_(), + size_(0), + storage_(nullptr), storage_node_id_(STORAGE_INVALID_NODE_ID), header_(nullptr), - default_value_(nullptr), fill_page_(nullptr), table_(nullptr), - table_cache_(), mutex_() {} Array2D::~Array2D() {} void 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) { + 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) { @@ -161,28 +267,23 @@ void Array2D::create(Storage *storage, uint32_t storage_node_id, *header_ = ArrayHeader(); header_->value_size = value_size; header_->page_size = page_size; - header_->table_size = table_size; + header_->table_size = size / page_size; + header_->size = size; if (default_value) { - header_->has_default_value = true; - default_value_ = header_ + 1; - std::memcpy(default_value_, default_value, value_size); + header_->has_default_value = 1; + std::memcpy(header_ + 1, default_value, value_size); fill_page_ = fill_page; } - StorageNode table_node = - storage->create_node(storage_node_id_, sizeof(uint32_t) * table_size); + // 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 < table_size; ++i) { + for (uint64_t i = 0; i < header_->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; - throw MemoryError(); - } - for (uint64_t i = 0; i < table_size; ++i) { - table_cache_[i] = nullptr; - } + reserve_pages(); + size_ = size; } catch (...) { storage->unlink_node(storage_node_id_); throw; @@ -191,7 +292,7 @@ void Array2D::create(Storage *storage, uint32_t storage_node_id, void Array2D::open(Storage *storage, uint32_t storage_node_id, uint64_t value_size, uint64_t page_size, - uint64_t table_size, FillPage fill_page) { + uint64_t , ArrayFillPage fill_page) { if (!storage) { GRNXX_ERROR() << "invalid argument: storage = nullptr"; throw LogicError(); @@ -199,39 +300,33 @@ void Array2D::open(Storage *storage, uint32_t storage_node_id, storage_ = storage; StorageNode storage_node = storage->open_node(storage_node_id); if (storage_node.size() < sizeof(ArrayHeader)) { - GRNXX_ERROR() << "invalid format: node_size = " << storage_node.size() - << ", header_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() << "parameter conflict: value_size = " << value_size - << ", stored_value_size = " << header_->value_size; + GRNXX_ERROR() << "wrong value_size: expected = " << value_size + << ", actual = " << header_->value_size; throw LogicError(); } if (header_->page_size != page_size) { - GRNXX_ERROR() << "parameter conflict: page_size = " << page_size - << ", stored_page_size = " << header_->page_size; + GRNXX_ERROR() << "wrong page_size: expected = " << page_size + << ", actual = " << header_->page_size; throw LogicError(); } - if (header_->table_size != table_size) { - GRNXX_ERROR() << "parameter conflict: table_size = " << table_size - << ", stored_table_size = " << header_->table_size; - throw LogicError(); + if (header_->has_default_value) { + fill_page_ = fill_page; } - default_value_ = header_ + 1; - fill_page_ = fill_page; StorageNode table_node = storage->open_node(header_->table_storage_node_id); 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; - throw MemoryError(); - } - for (uint64_t i = 0; i < table_size; ++i) { - table_cache_[i] = nullptr; - } + reserve_pages(); + size_ = header_->size; } void Array2D::unlink(Storage *storage, uint32_t storage_node_id, @@ -243,51 +338,87 @@ void Array2D::unlink(Storage *storage, uint32_t storage_node_id, storage->unlink_node(storage_node_id); } -void Array2D::initialize_page(uint64_t page_id) { +void Array2D::reserve_pages() { + // Create a table cache. + 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(); + } +} + +void Array2D::reserve_page(uint64_t page_id) { Lock inter_thread_lock(&mutex_); - if (!table_cache_[page_id]) { + if (pages_[page_id] == invalid_page()) { 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 (default_value_) { - fill_page_(page_node.body(), default_value_); + if (header_->has_default_value) { + fill_page_(page_node.body(), header_->page_size, header_ + 1); } table_[page_id] = page_node.id(); - table_cache_[page_id] = page_node.body(); - return; } } - page_node = storage_->open_node(table_[page_id]); - table_cache_[page_id] = page_node.body(); + 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() - : storage_(nullptr), + : tables_(), + size_(0), + storage_(nullptr), storage_node_id_(STORAGE_INVALID_NODE_ID), header_(nullptr), - default_value_(nullptr), fill_page_(nullptr), secondary_table_(nullptr), - table_caches_(), + dummy_table_(nullptr), page_mutex_(), - table_mutex_(), - secondary_table_mutex_() {} + table_mutex_() {} -Array3D::~Array3D() {} +Array3D::~Array3D() { + if (tables_) { + uint64_t offset = 0; + for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { + if (tables_[i] != (dummy_table_ - offset)) { + delete [] (tables_[i] + offset); + } + offset += header_->table_size; + } + } + if (dummy_table_) { + DummyTableManager::get().free_dummy_table(header_->table_size); + } +} void 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) { + 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) { @@ -302,20 +433,23 @@ void Array3D::create(Storage *storage, uint32_t storage_node_id, header_->value_size = value_size; header_->page_size = page_size; header_->table_size = table_size; - header_->secondary_table_size = secondary_table_size; + header_->secondary_table_size = size / (page_size * table_size); + header_->size = size; if (default_value) { - header_->has_default_value = true; - default_value_ = header_ + 1; - std::memcpy(default_value_, default_value, value_size); + header_->has_default_value = 1; + std::memcpy(header_ + 1, 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; - throw MemoryError(); + // 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; @@ -324,8 +458,7 @@ void Array3D::create(Storage *storage, uint32_t storage_node_id, void 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) { + uint64_t table_size, ArrayFillPage fill_page) { if (!storage) { GRNXX_ERROR() << "invalid argument: storage = nullptr"; throw LogicError(); @@ -333,90 +466,106 @@ void Array3D::open(Storage *storage, uint32_t storage_node_id, storage_ = storage; StorageNode storage_node = storage->open_node(storage_node_id); if (storage_node.size() < sizeof(ArrayHeader)) { - GRNXX_ERROR() << "invalid format: node_size = " << storage_node.size() - << ", header_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_->value_size != value_size) { - GRNXX_ERROR() << "parameter conflict: value_size = " << value_size - << ", stored_value_size = " << header_->value_size; + if (!*header_) { + GRNXX_ERROR() << "wrong format: expected = " << FORMAT_STRING + << ", actual = " << header_->common_header.format(); throw LogicError(); } - if (header_->page_size != page_size) { - GRNXX_ERROR() << "parameter conflict: page_size = " << page_size - << ", stored_page_size = " << header_->page_size; + if (header_->value_size != value_size) { + GRNXX_ERROR() << "wrong value_size: expected = " << value_size + << ", actual = " << header_->value_size; throw LogicError(); } - if (header_->table_size != table_size) { - GRNXX_ERROR() << "parameter conflict: table_size = " << table_size - << ", stored_table_size = " << header_->table_size; + 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() << "parameter conflict: " - << "secondary_table_size = " << secondary_table_size - << ", stored_secondary_table_size = " - << header_->secondary_table_size; + GRNXX_ERROR() << "wrong table_size: expected = " << table_size + << ", actual = " << header_->table_size; throw LogicError(); } - 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; - throw MemoryError(); + 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; } void 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) { + uint64_t table_size) { Array3D array; - array.open(storage, storage_node_id, value_size, page_size, - table_size, secondary_table_size, nullptr); + array.open(storage, storage_node_id, + value_size, page_size, table_size, nullptr); storage->unlink_node(storage_node_id); } -void Array3D::initialize_page(uint64_t table_id, uint64_t page_id) { - if (!table_caches_[table_id]) { - initialize_table(table_id); +void Array3D::reserve_tables() { + dummy_table_ = DummyTableManager::get().get_dummy_table(header_->table_size); + // Create a secondary table cache. + tables_.reset(new (std::nothrow) void **[header_->secondary_table_size]); + if (!tables_) { + GRNXX_ERROR() << "new void **[] failed: size = " + << header_->secondary_table_size; + throw MemoryError(); + } + // Fill the secondary table cache with the dummy table cache. + uint64_t offset = 0; + for (uint64_t i = 0; i < header_->secondary_table_size; ++i) { + tables_[i] = dummy_table_ - offset; + offset += header_->table_size; + } +} + +void Array3D::reserve_page(uint64_t page_id) { + const uint64_t table_id = page_id / header_->table_size; + if (tables_[table_id] == (dummy_table_ - (header_->table_size * table_id))) { + reserve_table(table_id); } Lock inter_thread_lock(&page_mutex_); - if (!table_caches_[table_id][page_id]) { + if (tables_[table_id][page_id] == invalid_page()) { + StorageNode page_node; StorageNode table_node = storage_->open_node(secondary_table_[table_id]); - uint32_t * const table = static_cast<uint32_t *>(table_node.body()); + 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) { - StorageNode page_node = - storage_->create_node(secondary_table_[table_id], - header_->value_size * header_->page_size); - if (default_value_) { - fill_page_(page_node.body(), default_value_); + // 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(); - table_caches_[table_id][page_id] = page_node.body(); - return; } } - StorageNode page_node = storage_->open_node(table[page_id]); - table_caches_[table_id][page_id] = page_node.body(); + 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::initialize_table(uint64_t table_id) { +void Array3D::reserve_table(uint64_t table_id) { Lock inter_thread_lock(&table_mutex_); - if (!table_caches_[table_id]) { - if (!secondary_table_) { - initialize_secondary_table(); - } + if (tables_[table_id] == (dummy_table_ - (header_->table_size * table_id))) { 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); @@ -427,41 +576,16 @@ void Array3D::initialize_table(uint64_t table_id) { secondary_table_[table_id] = table_node.id(); } } - void ** const table_cache = new void *[header_->table_size]; - if (!table_cache) { + // 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) { - table_cache[i] = nullptr; - } - table_caches_[table_id].reset(table_cache); - } -} - -void 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); - 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; - } + pages[i] = invalid_page(); } - StorageNode secondary_table_node = - storage_->open_node(header_->secondary_table_storage_node_id); - secondary_table_ = static_cast<uint32_t *>(secondary_table_node.body()); + tables_[table_id] = pages - (header_->table_size * table_id); } } Modified: lib/grnxx/array_impl.hpp (+229 -290) =================================================================== --- lib/grnxx/array_impl.hpp 2013-07-16 15:25:57 +0900 (7929e6c) +++ lib/grnxx/array_impl.hpp 2013-07-16 19:27:01 +0900 (6ca91d2) @@ -20,7 +20,6 @@ #include "grnxx/features.hpp" -#include <cstring> #include <memory> #include "grnxx/mutex.hpp" @@ -33,455 +32,395 @@ class Storage; struct ArrayHeader; -class Array1D { - using FillPage = void (*)(void *page, const void *value); +// 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, - const void *default_value = nullptr, - FillPage fill_page = nullptr); + 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 value_size, uint64_t page_size, + uint64_t table_size, ArrayFillPage fill_page); + // Unlink an array. static void unlink(Storage *storage, uint32_t storage_node_id, - uint64_t value_size, uint64_t page_size); + 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_; + } - template <typename T> - T *get_page(uint64_t) { - return static_cast<T *>(page_); + // Return a reference 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: - uint32_t storage_node_id_; - ArrayHeader *header_; void *page_; + uint64_t size_; + uint32_t storage_node_id_; }; class Array2D { - using FillPage = void (*)(void *page, const void *value); - 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, - const void *default_value = nullptr, - FillPage fill_page = nullptr); + 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, FillPage fill_page); + uint64_t table_size, ArrayFillPage fill_page); + // Unlink an array. static void 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_; + } - template <typename T, uint64_t TABLE_SIZE> - T *get_page(uint64_t page_id) { - if (!table_cache_[page_id]) { - initialize_page(page_id); + // Return a reference 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()) { + reserve_page(page_id); } - return static_cast<T *>(table_cache_[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_; - void *default_value_; - FillPage fill_page_; + ArrayFillPage fill_page_; uint32_t *table_; - std::unique_ptr<void *[]> table_cache_; Mutex mutex_; - void initialize_page(uint64_t page_id); + // Initialize "pages_". + void reserve_pages(); + // Open or create a page. + void reserve_page(uint64_t page_id); + + // Return a pointer to an invalid page. + static void *invalid_page() { + return static_cast<char *>(nullptr) - 1; + } }; class Array3D { - using FillPage = void (*)(void *page, const void *value); + 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 secondary_table_size, - const void *default_value = nullptr, - FillPage fill_page = nullptr); - + 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, uint64_t secondary_table_size, - FillPage fill_page); + uint64_t table_size, ArrayFillPage fill_page); + // Unlink an array. static void 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); + 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_; + } - 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 a reference 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][page_id] == invalid_page()) { + reserve_page(page_id); } - return static_cast<T *>(table_caches_[table_id][page_id]); + return static_cast<T *>(tables_[table_id][page_id])[value_id]; + } + + // Return a pointer to an invalid page. + static void *invalid_page() { + return static_cast<char *>(nullptr) + 1; } private: + std::unique_ptr<void **[]> tables_; + uint64_t size_; Storage *storage_; uint32_t storage_node_id_; ArrayHeader *header_; - void *default_value_; - FillPage fill_page_; + ArrayFillPage fill_page_; uint32_t *secondary_table_; - std::unique_ptr<std::unique_ptr<void *[]>[]> table_caches_; + void **dummy_table_; Mutex page_mutex_; Mutex table_mutex_; - Mutex secondary_table_mutex_; - void initialize_page(uint64_t table_id, uint64_t page_id); - void initialize_table(uint64_t table_id); - void initialize_secondary_table(); + // Initialize "tables_". + void reserve_tables(); + // Open or create a page. + void reserve_page(uint64_t page_id); + // Open or create a table. + void reserve_table(uint64_t table_id); +}; + +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; }; -template <typename T, - uint64_t PAGE_SIZE, - uint64_t TABLE_SIZE, - uint64_t SECONDARY_TABLE_SIZE> -class ArrayImpl; +// 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 { + // 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"); -// 1D array. -template <typename T, uint64_t PAGE_SIZE> -class ArrayImpl<T, PAGE_SIZE, 1, 1> { - static_assert(PAGE_SIZE > 0, "PAGE_SIZE <= 0"); + using Impl = typename ArrayImplSelector<PAGE_SIZE, TABLE_SIZE>::Type; public: - using Value = typename Traits<T>::Type; + using Value = typename Traits<T>::Type; using ValueArg = typename Traits<T>::ArgumentType; + using ValueRef = Value &; + using Unit = Value; ArrayImpl() : impl_() {} ~ArrayImpl() {} - // Return true iff the array is valid. - explicit operator bool() const { - return static_cast<bool>(impl_); - } - // Create an array. - void create(Storage *storage, uint32_t storage_node_id) { - impl_.create(storage, storage_node_id, sizeof(Value), PAGE_SIZE); + 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, + 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, - &default_value, fill_page); + 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); + impl_.open(storage, storage_node_id, + sizeof(Value), PAGE_SIZE, TABLE_SIZE, + ArrayPageFiller<Value>::fill_page); } // Unlink an array. static void unlink(Storage *storage, uint32_t storage_node_id) { - 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(); + 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(); } - - // Get a value and return true. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value) { - const Value * const page = get_page(value_id / PAGE_SIZE); - if (value) { - *value = page[value_id]; -// *value = page[value_id % PAGE_SIZE]; - } - return true; + // Return the number of values. + uint64_t size() const { + return impl_.size(); } - // 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] = value; -// page[value_id % PAGE_SIZE] = value; - return true; + // Return a reference to a value. + ValueRef get_value(uint64_t value_id) { + return impl_. template get_value<Value, PAGE_SIZE, TABLE_SIZE>(value_id); } - - // Get a value and return its address. - Value *get_pointer(uint64_t value_id) { - Value * const page = get_page(value_id / PAGE_SIZE); - return &page[value_id]; -// return &page[value_id % PAGE_SIZE]; - } - - // Get a page and return its starting address. - Value *get_page(uint64_t page_id) { - return impl_.get_page<Value>(page_id); + // Return a reference to a unit. + Unit &get_unit(uint64_t unit_id) { + return get_value(unit_id); } private: - Array1D 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)); - } - } + Impl impl_; }; -// 2D array. -template <typename T, uint64_t PAGE_SIZE, uint64_t TABLE_SIZE> -class ArrayImpl<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"); - +// A reference to a bit. +class ArrayBitRef { public: - using Value = typename Traits<T>::Type; - using ValueArg = typename Traits<T>::ArgumentType; + using Unit = uint64_t; - ArrayImpl() : impl_() {} - ~ArrayImpl() {} + // Create a reference to a bit. + ArrayBitRef(Unit &unit, Unit mask) : unit_(unit), mask_(mask) {} - // Return true iff the array is valid. - explicit operator bool() const { - return static_cast<bool>(impl_); + // Get a bit. + operator bool() const { + return (unit_ & mask_) != 0; } - // Create an array. - void create(Storage *storage, uint32_t storage_node_id) { - impl_.create(storage, storage_node_id, sizeof(Value), PAGE_SIZE, - TABLE_SIZE); - } - // Create an array with the default value. - void create(Storage *storage, uint32_t storage_node_id, - ValueArg default_value) { - impl_.create(storage, storage_node_id, sizeof(Value), PAGE_SIZE, - TABLE_SIZE, &default_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, fill_page); - } - - // Unlink an array. - static void unlink(Storage *storage, uint32_t storage_node_id) { - 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 value and return true on success. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value) { - const Value * const page = get_page(value_id / PAGE_SIZE); + // Set a bit. + ArrayBitRef &operator=(bool value) { if (value) { - *value = page[value_id % PAGE_SIZE]; + unit_ |= mask_; + } else { + unit_ &= ~mask_; } - return true; + return *this; } - // 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); - page[value_id % PAGE_SIZE] = value; - return true; + // Copy a bit. + ArrayBitRef &operator=(const ArrayBitRef &rhs) { + return *this = bool(rhs); } - // Get a value and return its address on success. - Value *get_pointer(uint64_t value_id) { - Value * const page = get_page(value_id / PAGE_SIZE); - return &page[value_id % PAGE_SIZE]; + // Compare bits. + bool operator==(bool rhs) const { + return bool(*this) == rhs; } - - // Get a page and return its starting address on success. - Value *get_page(uint64_t page_id) { - return impl_.get_page<Value, TABLE_SIZE>(page_id); + bool operator!=(bool rhs) const { + return bool(*this) != rhs; } private: - Array2D 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)); - } - } + Unit &unit_; + Unit mask_; }; -// 3D array. -template <typename T, - uint64_t PAGE_SIZE, - uint64_t TABLE_SIZE, - uint64_t SECONDARY_TABLE_SIZE> -class ArrayImpl { - 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"); +// An array of bits. +template <uint64_t PAGE_SIZE_IN_BITS, uint64_t TABLE_SIZE> +class ArrayImpl<bool, PAGE_SIZE_IN_BITS, TABLE_SIZE> { + static constexpr uint64_t UNIT_SIZE = sizeof(ArrayBitRef::Unit) * 8; + static constexpr uint64_t PAGE_SIZE = PAGE_SIZE_IN_BITS / UNIT_SIZE; + + // Test template parameters. + static_assert((PAGE_SIZE_IN_BITS % UNIT_SIZE) == 0, + "(PAGE_SIZE_IN_BITS % UNIT_SIZE) != 0"); + 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 = typename ArrayImplSelector<PAGE_SIZE, TABLE_SIZE>::Type; public: - using Value = typename Traits<T>::Type; - using ValueArg = typename Traits<T>::ArgumentType; + using Value = typename Traits<bool>::Type; + using ValueArg = typename Traits<bool>::ArgumentType; + using ValueRef = ArrayBitRef; + using Unit = ArrayBitRef::Unit; ArrayImpl() : impl_() {} ~ArrayImpl() {} - // Return true iff the array is valid. - explicit operator bool() const { - return static_cast<bool>(impl_); - } - // Create an array. - void create(Storage *storage, uint32_t storage_node_id) { - impl_.create(storage, storage_node_id, sizeof(Value), PAGE_SIZE, - TABLE_SIZE, SECONDARY_TABLE_SIZE); + void create(Storage *storage, uint32_t storage_node_id, uint64_t size) { + impl_.create(storage, storage_node_id, + sizeof(Unit), PAGE_SIZE, TABLE_SIZE, size / UNIT_SIZE, + nullptr, ArrayPageFiller<Unit>::fill_page); } // Create an array with the default value. - void create(Storage *storage, uint32_t storage_node_id, + 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, SECONDARY_TABLE_SIZE, &default_value, fill_page); + const Unit default_unit = default_value ? ~(Unit)0 : (Unit)0; + impl_.create(storage, storage_node_id, + sizeof(Unit), PAGE_SIZE, TABLE_SIZE, size / UNIT_SIZE, + &default_unit, ArrayPageFiller<Unit>::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, SECONDARY_TABLE_SIZE, fill_page); + impl_.open(storage, storage_node_id, + sizeof(Unit), PAGE_SIZE, TABLE_SIZE, + ArrayPageFiller<Unit>::fill_page); } // Unlink an array. static void unlink(Storage *storage, uint32_t storage_node_id) { - 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(); + Impl::unlink(storage, storage_node_id, + sizeof(Unit), PAGE_SIZE, TABLE_SIZE); } // Return the storage node ID. uint32_t storage_node_id() const { return impl_.storage_node_id(); } - - // Get a value and return true on success. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value) { - const Value * const page = get_page(value_id / PAGE_SIZE); - if (value) { - *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); - page[value_id % PAGE_SIZE] = value; - return true; + // Return the number of values. + uint64_t size() const { + return impl_.size() * UNIT_SIZE; } - // Get a value and return its address on success. - Value *get_pointer(uint64_t value_id) { - Value * const page = get_page(value_id / PAGE_SIZE); - return &page[value_id % PAGE_SIZE]; + // Return a reference to a value. + ValueRef get_value(uint64_t value_id) { + return ValueRef(get_unit(value_id / UNIT_SIZE), + Unit(1) << (value_id % UNIT_SIZE)); } - - // Get a page and return its starting address on success. - Value *get_page(uint64_t page_id) { - return impl_.get_page<Value, TABLE_SIZE, SECONDARY_TABLE_SIZE>(page_id); + // Return a reference to a unit. + Unit &get_unit(uint64_t unit_id) { + return impl_. template get_value<Unit, PAGE_SIZE, TABLE_SIZE>(unit_id); } private: - Array3D 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)); - } - } + Impl impl_; }; } // namespace grnxx Modified: lib/grnxx/map/array_map.cpp (+15 -20) =================================================================== --- lib/grnxx/map/array_map.cpp 2013-07-16 15:25:57 +0900 (2ed6067) +++ lib/grnxx/map/array_map.cpp 2013-07-16 19:27:01 +0900 (c4baf94) @@ -89,13 +89,13 @@ bool ArrayMap<T>::get(int64_t key_id, Key *key) { // Out of range. return false; } - bool bit; - keys_->get_bit(key_id, &bit); - if (!bit) { + if (!keys_->get_bit(key_id)) { // Not found. return false; } - keys_->get_key(key_id, key); + if (key) { + *key = keys_->get_key(key_id); + } return true; } @@ -126,11 +126,8 @@ template <typename T> bool ArrayMap<T>::find(KeyArg key, int64_t *key_id) { const Key normalized_key = map::Helper<T>::normalize(key); for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id(); ++i) { - bool bit; - keys_->get_bit(i, &bit); - if (bit) { - Key stored_key; - keys_->get_key(i, &stored_key); + if (keys_->get_bit(i)) { + Key stored_key = keys_->get_key(i); if (Helper<T>::equal_to(normalized_key, stored_key)) { // Found. if (key_id) { @@ -147,11 +144,8 @@ template <typename T> bool ArrayMap<T>::add(KeyArg key, int64_t *key_id) { const Key normalized_key = Helper<T>::normalize(key); for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id(); ++i) { - bool bit; - keys_->get_bit(i, &bit); - if (bit) { - Key stored_key; - keys_->get_key(i, &stored_key); + if (keys_->get_bit(i)) { + Key stored_key = keys_->get_key(i); if (Helper<T>::equal_to(normalized_key, stored_key)) { // Found. if (key_id) { @@ -161,7 +155,11 @@ bool ArrayMap<T>::add(KeyArg key, int64_t *key_id) { } } } - keys_->add(normalized_key, key_id); + if (key_id) { + *key_id = keys_->add(normalized_key); + } else { + keys_->add(normalized_key); + } return true; } @@ -186,11 +184,8 @@ bool ArrayMap<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { const Key normalized_dest_key = Helper<T>::normalize(dest_key); int64_t src_key_id = MAP_INVALID_KEY_ID; for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id(); ++i) { - bool bit; - keys_->get_bit(i, &bit); - if (bit) { - Key stored_key; - keys_->get_key(i, &stored_key); + if (keys_->get_bit(i)) { + Key stored_key = keys_->get_key(i); if (Helper<T>::equal_to(normalized_src_key, stored_key)) { // Source key found. src_key_id = i; Modified: lib/grnxx/map/bytes_array.cpp (+14 -19) =================================================================== --- lib/grnxx/map/bytes_array.cpp 2013-07-16 15:25:57 +0900 (ce80438) +++ lib/grnxx/map/bytes_array.cpp 2013-07-16 19:27:01 +0900 (63c571a) @@ -43,12 +43,13 @@ BytesArrayHeader::BytesArrayHeader() BytesArray::~BytesArray() {} -BytesArray *BytesArray::create(Storage *storage, uint32_t storage_node_id) { - return create(storage, storage_node_id, ""); +BytesArray *BytesArray::create(Storage *storage, uint32_t storage_node_id, + uint64_t) { + return create(storage, storage_node_id, 0, ""); } BytesArray *BytesArray::create(Storage *storage, uint32_t storage_node_id, - ValueArg default_value) { + uint64_t, ValueArg default_value) { if (!storage) { GRNXX_ERROR() << "invalid argument: storage = nullptr"; throw LogicError(); @@ -81,23 +82,18 @@ void BytesArray::unlink(Storage *storage, uint32_t storage_node_id) { storage->unlink_node(storage_node_id); } -bool BytesArray::get(uint64_t value_id, Value *value) { - uint64_t bytes_id; - ids_->get(value_id, &bytes_id); - if (value) { - if (bytes_id == BYTES_STORE_INVALID_BYTES_ID) { - *value = default_value_; - } else { - store_->get(bytes_id, value); - } +auto BytesArray::get(uint64_t value_id) -> Value { + uint64_t bytes_id = ids_->get(value_id); + if (bytes_id == BYTES_STORE_INVALID_BYTES_ID) { + return default_value_; + } else { + return store_->get(bytes_id); } - return true; } -bool BytesArray::set(uint64_t value_id, ValueArg value) { - uint64_t *src_bytes_id = ids_->get_pointer(value_id); - uint64_t dest_bytes_id; - store_->add(value, &dest_bytes_id); +void BytesArray::set(uint64_t value_id, ValueArg value) { + uint64_t * const src_bytes_id = &ids_->get_value(value_id); + const uint64_t dest_bytes_id = store_->add(value); if (*src_bytes_id != BYTES_STORE_INVALID_BYTES_ID) { try { store_->unset(*src_bytes_id); @@ -107,7 +103,6 @@ bool BytesArray::set(uint64_t value_id, ValueArg value) { } } *src_bytes_id = dest_bytes_id; - return true; } bool BytesArray::sweep(Duration lifetime) { @@ -135,7 +130,7 @@ void BytesArray::create_array(Storage *storage, uint32_t storage_node_id, header_->default_value_size = default_value.size(); std::memcpy(header_ + 1, default_value.data(), default_value.size()); default_value_ = Value(header_ + 1, default_value.size()); - ids_.reset(IDArray::create(storage, storage_node_id_, + ids_.reset(IDArray::create(storage, storage_node_id_, ID_ARRAY_SIZE, BYTES_STORE_INVALID_BYTES_ID)); store_.reset(BytesStore::create(storage, storage_node_id_)); header_->ids_storage_node_id = ids_->storage_node_id(); Modified: lib/grnxx/map/bytes_array.hpp (+13 -23) =================================================================== --- lib/grnxx/map/bytes_array.hpp 2013-07-16 15:25:57 +0900 (2e19f0c) +++ lib/grnxx/map/bytes_array.hpp 2013-07-16 19:27:01 +0900 (26eb645) @@ -43,36 +43,27 @@ class BytesArray { using Value = typename Traits<Bytes>::Type; using ValueArg = typename Traits<Bytes>::ArgumentType; - using IDArray = Array<uint64_t>; + using IDArray = Array<uint64_t, 65536, 4096>; + + static constexpr uint64_t ID_ARRAY_SIZE = 1ULL << 40; ~BytesArray(); // Create an array. - static BytesArray *create(Storage *storage, uint32_t storage_node_id); - // Create an array with the default value. static BytesArray *create(Storage *storage, uint32_t storage_node_id, - ValueArg default_value); + uint64_t dummy); + // Create an array with default value. + static BytesArray *create(Storage *storage, uint32_t storage_node_id, + uint64_t dummy, ValueArg default_value); // Open an array. static BytesArray *open(Storage *storage, uint32_t storage_node_id); // Unlink an array. static void unlink(Storage *storage, uint32_t storage_node_id); - // Return the number of values in each page. - static constexpr uint64_t page_size() { - return IDArray::page_size(); - } - // Return the number of pages in each table. - static constexpr uint64_t table_size() { - return IDArray::table_size(); - } - // Return the number of tables in each secondary table. - static constexpr uint64_t secondary_table_size() { - return IDArray::secondary_table_size(); - } // Return the number of values in Array. - static constexpr uint64_t size() { - return IDArray::size(); + uint64_t size() const { + return ids_->size(); } // Return the storage node ID. @@ -80,11 +71,10 @@ class BytesArray { return storage_node_id_; } - // Get a value and return true on success. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value); - // Set a value and return true on success. - bool set(uint64_t value_id, ValueArg value); + // Get a value. + Value get(uint64_t value_id); + // Set a value. + void set(uint64_t value_id, ValueArg value); // Sweep empty pages whose modified time < (now - lifetime). bool sweep(Duration lifetime); Modified: lib/grnxx/map/bytes_store.cpp (+28 -47) =================================================================== --- lib/grnxx/map/bytes_store.cpp 2013-07-16 15:25:57 +0900 (398c747) +++ lib/grnxx/map/bytes_store.cpp 2013-07-16 19:27:01 +0900 (8bc1461) @@ -41,12 +41,12 @@ constexpr uint64_t BYTES_STORE_SIZE_MASK = static_assert(BYTES_STORE_MAX_SIZE <= BYTES_STORE_SIZE_MASK, "BYTES_STORE_MAX_SIZE > BYTES_STORE_SIZE_MASK"); +constexpr uint64_t BYTES_STORE_SIZE = 1ULL << 48; constexpr uint32_t BYTES_STORE_PAGE_SIZE = 1U << 20; constexpr uint32_t BYTES_STORE_TABLE_SIZE = 1U << 14; -constexpr uint32_t BYTES_STORE_SECONDARY_TABLE_SIZE = 1U << 14; constexpr uint32_t BYTES_STORE_MAX_PAGE_ID = - (BYTES_STORE_TABLE_SIZE * BYTES_STORE_SECONDARY_TABLE_SIZE) - 1; + (BYTES_STORE_SIZE / BYTES_STORE_PAGE_SIZE) - 1; constexpr uint32_t BYTES_STORE_INVALID_PAGE_ID = BYTES_STORE_MAX_PAGE_ID + 1; @@ -125,12 +125,8 @@ BytesStorePageHeader::BytesStorePageHeader() class BytesStoreImpl : public BytesStore { using BytesArray = Array<uint8_t, BYTES_STORE_PAGE_SIZE, - BYTES_STORE_TABLE_SIZE, - BYTES_STORE_SECONDARY_TABLE_SIZE>; - using PageHeaderArray = Array<BytesStorePageHeader, - BYTES_STORE_TABLE_SIZE, - BYTES_STORE_SECONDARY_TABLE_SIZE, - 1>; + BYTES_STORE_TABLE_SIZE>; + using PageHeaderArray = Array<BytesStorePageHeader, BYTES_STORE_TABLE_SIZE>; public: using Value = Bytes; @@ -144,9 +140,9 @@ class BytesStoreImpl : public BytesStore { uint32_t storage_node_id() const; - bool get(uint64_t bytes_id, Value *bytes); - bool unset(uint64_t bytes_id); - bool add(ValueArg bytes, uint64_t *bytes_id); + Value get(uint64_t bytes_id); + void unset(uint64_t bytes_id); + uint64_t add(ValueArg bytes); bool sweep(Duration lifetime); @@ -226,27 +222,13 @@ uint32_t BytesStoreImpl::storage_node_id() const { return storage_node_id_; } -bool BytesStoreImpl::get(uint64_t bytes_id, Value *bytes) { +auto BytesStoreImpl::get(uint64_t bytes_id) -> Value { const uint64_t offset = get_offset(bytes_id); const uint32_t size = get_size(bytes_id); - const uint32_t page_id = get_page_id(offset); - if ((size > BYTES_STORE_MAX_SIZE) || (page_id > header_->max_page_id)) { - GRNXX_ERROR() << "invalid argument: offset = " << offset - << ", size = " << size - << ", page_id = " << page_id - << ", max_size = " << BYTES_STORE_MAX_SIZE - << ", max_page_id = " << header_->max_page_id; - throw LogicError(); - } - const uint8_t * const page = pages_->get_page(page_id); - if (bytes) { - const uint32_t offset_in_page = get_offset_in_page(offset); - *bytes = Value(&page[offset_in_page], size); - } - return true; + return Value(&pages_->get_value(offset), size); } -bool BytesStoreImpl::unset(uint64_t bytes_id) { +void BytesStoreImpl::unset(uint64_t bytes_id) { const uint64_t offset = get_offset(bytes_id); const uint32_t size = get_size(bytes_id); const uint32_t page_id = get_page_id(offset); @@ -259,7 +241,7 @@ bool BytesStoreImpl::unset(uint64_t bytes_id) { throw LogicError(); } BytesStorePageHeader * const page_header = - page_headers_->get_pointer(page_id); + &page_headers_->get_value(page_id); if ((page_header->status != BYTES_STORE_PAGE_ACTIVE) && (page_header->status != BYTES_STORE_PAGE_IN_USE)) { GRNXX_ERROR() << "invalid argument: page_id = " << page_id @@ -279,10 +261,9 @@ bool BytesStoreImpl::unset(uint64_t bytes_id) { // This operation makes the page EMPTY. make_page_empty(page_id, page_header); } - return true; } -bool BytesStoreImpl::add(ValueArg bytes, uint64_t *bytes_id) { +uint64_t BytesStoreImpl::add(ValueArg bytes) { if (bytes.size() > BYTES_STORE_MAX_SIZE) { GRNXX_ERROR() << "invalid argument: size = " << bytes.size(); throw LogicError(); @@ -290,7 +271,7 @@ bool BytesStoreImpl::add(ValueArg bytes, uint64_t *bytes_id) { uint64_t offset = header_->next_offset; uint32_t size = static_cast<uint32_t>(bytes.size()); uint32_t page_id = get_page_id(offset); - BytesStorePageHeader *page_header = page_headers_->get_pointer(page_id); + BytesStorePageHeader *page_header = &page_headers_->get_value(page_id); uint32_t offset_in_page = get_offset_in_page(offset); const uint32_t size_left = BYTES_STORE_PAGE_SIZE - offset_in_page; if (size >= size_left) { @@ -308,26 +289,24 @@ bool BytesStoreImpl::add(ValueArg bytes, uint64_t *bytes_id) { page_header->modified_time = clock_.now(); } // Use the new ACTIVE page. - header_->next_offset = next_page_id * pages_->page_size(); + header_->next_offset = next_page_id * BYTES_STORE_PAGE_SIZE; offset = header_->next_offset; page_id = next_page_id; page_header = next_page_header; - offset_in_page = get_offset_in_page(offset); } else { // Use the previous ACTIVE page. page_header->status = BYTES_STORE_PAGE_IN_USE; page_header->modified_time = clock_.now(); - header_->next_offset = next_page_id * pages_->page_size(); + header_->next_offset = next_page_id * BYTES_STORE_PAGE_SIZE; } } - uint8_t * const page = pages_->get_page(page_id); - std::memcpy(page + offset_in_page, bytes.data(), size); - *bytes_id = get_bytes_id(offset, size); + uint8_t * const value = &pages_->get_value(offset); + std::memcpy(value, bytes.data(), size); page_header->size_in_use += size; if (offset == header_->next_offset) { header_->next_offset += size; } - return true; + return get_bytes_id(offset, size); } bool BytesStoreImpl::sweep(Duration lifetime) { @@ -336,13 +315,13 @@ bool BytesStoreImpl::sweep(Duration lifetime) { return true; } BytesStorePageHeader * const latest_empty_page_header = - page_headers_->get_pointer(header_->latest_empty_page_id); + &page_headers_->get_value(header_->latest_empty_page_id); const Time threshold = clock_.now() - lifetime; do { const uint32_t oldest_empty_page_id = latest_empty_page_header->next_page_id; BytesStorePageHeader * const oldest_empty_page_header = - page_headers_->get_pointer(oldest_empty_page_id); + &page_headers_->get_value(oldest_empty_page_id); if (oldest_empty_page_header->status != BYTES_STORE_PAGE_EMPTY) { GRNXX_ERROR() << "status conflict: status = " << oldest_empty_page_header->status; @@ -372,8 +351,10 @@ void BytesStoreImpl::create_store(Storage *storage, uint32_t storage_node_id) { try { header_ = static_cast<BytesStoreHeader *>(storage_node.body()); *header_ = BytesStoreHeader(); - pages_.reset(BytesArray::create(storage, storage_node_id_)); - page_headers_.reset(PageHeaderArray::create(storage, storage_node_id)); + pages_.reset(BytesArray::create(storage, storage_node_id_, + BYTES_STORE_SIZE)); + page_headers_.reset(PageHeaderArray::create(storage, storage_node_id, + BYTES_STORE_MAX_PAGE_ID + 1)); header_->pages_storage_node_id = pages_->storage_node_id(); header_->page_headers_storage_node_id = page_headers_->storage_node_id(); } catch (...) { @@ -399,7 +380,7 @@ void BytesStoreImpl::reserve_active_page(uint32_t *page_id, if (header_->latest_idle_page_id != BYTES_STORE_INVALID_PAGE_ID) { // Use the oldest IDLE page. latest_idle_page_header = - page_headers_->get_pointer(header_->latest_idle_page_id); + &page_headers_->get_value(header_->latest_idle_page_id); next_page_id = latest_idle_page_header->next_page_id; } else { // Create a new page. @@ -411,7 +392,7 @@ void BytesStoreImpl::reserve_active_page(uint32_t *page_id, } } BytesStorePageHeader * const next_page_header = - page_headers_->get_pointer(next_page_id); + &page_headers_->get_value(next_page_id); if (latest_idle_page_header) { if (next_page_id != header_->latest_idle_page_id) { latest_idle_page_header->next_page_id = next_page_header->next_page_id; @@ -432,7 +413,7 @@ void BytesStoreImpl::make_page_empty(uint32_t page_id, BytesStorePageHeader *latest_empty_page_header = nullptr; if (header_->latest_empty_page_id != BYTES_STORE_INVALID_PAGE_ID) { latest_empty_page_header = - page_headers_->get_pointer(header_->latest_empty_page_id); + &page_headers_->get_value(header_->latest_empty_page_id); } page_header->status = BYTES_STORE_PAGE_EMPTY; if (latest_empty_page_header) { @@ -450,7 +431,7 @@ void BytesStoreImpl::make_page_idle(uint32_t page_id, BytesStorePageHeader *latest_idle_page_header = nullptr; if (header_->latest_idle_page_id != BYTES_STORE_INVALID_PAGE_ID) { latest_idle_page_header = - page_headers_->get_pointer(header_->latest_idle_page_id); + &page_headers_->get_value(header_->latest_idle_page_id); } page_header->status = BYTES_STORE_PAGE_IDLE; if (latest_idle_page_header) { Modified: lib/grnxx/map/bytes_store.hpp (+4 -4) =================================================================== --- lib/grnxx/map/bytes_store.hpp 2013-07-16 15:25:57 +0900 (4e5e67a) +++ lib/grnxx/map/bytes_store.hpp 2013-07-16 19:27:01 +0900 (938a5f4) @@ -54,11 +54,11 @@ class BytesStore { virtual uint32_t storage_node_id() const = 0; // Get a stored byte sequence. - virtual bool get(uint64_t bytes_id, Value *bytes) = 0; + virtual Value get(uint64_t bytes_id) = 0; // Remove a stored byte sequence. - virtual bool unset(uint64_t bytes_id) = 0; - // Add a byte sequence. - virtual bool add(ValueArg bytes, uint64_t *bytes_id) = 0; + virtual void unset(uint64_t bytes_id) = 0; + // Add a byte sequence and return its ID. + virtual uint64_t add(ValueArg bytes) = 0; // Sweep empty pages whose modified time < (now - lifetime). virtual bool sweep(Duration lifetime) = 0; Modified: lib/grnxx/map/double_array.cpp (+58 -184) =================================================================== --- lib/grnxx/map/double_array.cpp 2013-07-16 15:25:57 +0900 (0e56a8c) +++ lib/grnxx/map/double_array.cpp 2013-07-16 19:27:01 +0900 (1b9d3a9) @@ -154,11 +154,7 @@ bool DoubleArray<Bytes>::reset(int64_t key_id, KeyArg dest_key) { bool DoubleArray<Bytes>::find(KeyArg key, int64_t *key_id) { uint64_t node_id = ROOT_NODE_ID; - Node node; - if (!nodes_->get(node_id, &node)) { - // Error. - return false; - } + Node node = nodes_->get(node_id); uint64_t key_pos; for (key_pos = 0; key_pos < key.size(); ++key_pos) { if (node.is_leaf()) { @@ -166,10 +162,7 @@ bool DoubleArray<Bytes>::find(KeyArg key, int64_t *key_id) { break; } node_id = node.offset() ^ key[key_pos]; - if (!nodes_->get(node_id, &node)) { - // Error. - return false; - } + node = nodes_->get(node_id); if (node.label() != key[key_pos]) { // Not found. return false; @@ -181,10 +174,7 @@ bool DoubleArray<Bytes>::find(KeyArg key, int64_t *key_id) { return false; } node_id = node.offset() ^ NODE_TERMINAL_LABEL; - if (!nodes_->get(node_id, &node)) { - // Error. - return false; - } + node = nodes_->get(node_id); if (!node.is_leaf()) { // Not found. return false; @@ -234,16 +224,8 @@ bool DoubleArray<Bytes>::add(KeyArg key, int64_t *key_id) { << ", max_key_id = " << MAP_MAX_KEY_ID; return false; } - Entry * const entry = entries_->get_pointer(next_key_id); - if (!entry) { - // Error. - return false; - } - uint64_t bytes_id; - if (!store_->add(key, &bytes_id)) { - // Error. - return false; - } + Entry * const entry = &entries_->get_value(next_key_id); + uint64_t bytes_id = store_->add(key); ++header_->num_keys; if (next_key_id > header_->max_key_id) { header_->max_key_id = next_key_id; @@ -266,20 +248,12 @@ bool DoubleArray<Bytes>::remove(KeyArg key) { // Not found or error. return false; } - Entry * const entry = entries_->get_pointer(node->key_id()); - if (!entry) { - // Error. - return false; - } + Entry * const entry = &entries_->get_value(node->key_id()); if (!*entry) { // Not found. return false; } - Key stored_key; - if (!store_->get(entry->bytes_id(), &stored_key)) { - // Error. - return false; - } + Key stored_key = store_->get(entry->bytes_id()); if (key.except_prefix(key_pos) != stored_key.except_prefix(key_pos)) { // Not found. return false; @@ -309,11 +283,7 @@ bool DoubleArray<Bytes>::replace(KeyArg src_key, KeyArg dest_key, } bool DoubleArray<Bytes>::truncate() { - Node * const node = nodes_->get_pointer(ROOT_NODE_ID); - if (!node) { - // Error. - return false; - } + Node * const node = &nodes_->get_value(ROOT_NODE_ID); node->set_child(NODE_INVALID_LABEL); node->set_offset(NODE_INVALID_OFFSET); header_->max_key_id = MAP_MIN_KEY_ID - 1; @@ -327,11 +297,7 @@ bool DoubleArray<Bytes>::find_longest_prefix_match(KeyArg query, Key *key) { bool found = false; uint64_t node_id = ROOT_NODE_ID; - Node node; - if (!nodes_->get(node_id, &node)) { - // Error. - return false; - } + Node node = nodes_->get(node_id); uint64_t query_pos; for (query_pos = 0; query_pos < query.size(); ++query_pos) { if (node.is_leaf()) { @@ -363,11 +329,7 @@ bool DoubleArray<Bytes>::find_longest_prefix_match(KeyArg query, } if (node.child() == NODE_TERMINAL_LABEL) { - Node leaf_node; - if (!nodes_->get(node.offset() ^ NODE_TERMINAL_LABEL, &leaf_node)) { - // Error. - return false; - } + Node leaf_node = nodes_->get(node.offset() ^ NODE_TERMINAL_LABEL); if (leaf_node.is_leaf()) { switch (get_key(leaf_node.key_id(), key)) { case DOUBLE_ARRAY_FOUND: { @@ -388,10 +350,7 @@ bool DoubleArray<Bytes>::find_longest_prefix_match(KeyArg query, } node_id = node.offset() ^ query[query_pos]; - if (!nodes_->get(node_id, &node)) { - // Error. - return false; - } + node = nodes_->get(node_id); if (node.label() != query[query_pos]) { return found; } @@ -420,21 +379,20 @@ bool DoubleArray<Bytes>::find_longest_prefix_match(KeyArg query, } } } else if (node.child() == NODE_TERMINAL_LABEL) { - if (nodes_->get(node.offset() ^ NODE_TERMINAL_LABEL, &node)) { - switch (get_key(node.key_id(), key)) { - case DOUBLE_ARRAY_FOUND: { - if (key_id) { - *key_id = node.key_id(); - } - found = true; - break; - } - case DOUBLE_ARRAY_NOT_FOUND: { - break; - } - default: { - return false; + node = nodes_->get(node.offset() ^ NODE_TERMINAL_LABEL); + switch (get_key(node.key_id(), key)) { + case DOUBLE_ARRAY_FOUND: { + if (key_id) { + *key_id = node.key_id(); } + found = true; + break; + } + case DOUBLE_ARRAY_NOT_FOUND: { + break; + } + default: { + return false; } } } @@ -468,10 +426,14 @@ void DoubleArray<Bytes>::create_map(Storage *storage, uint32_t storage_node_id, try { header_ = static_cast<Header *>(storage_node.body()); *header_ = Header(); - nodes_.reset(NodeArray::create(storage, storage_node_id_)); - siblings_.reset(SiblingArray::create(storage, storage_node_id_)); - blocks_.reset(BlockArray::create(storage, storage_node_id_)); - entries_.reset(EntryArray::create(storage, storage_node_id_)); + nodes_.reset(NodeArray::create(storage, storage_node_id_, + NODE_ARRAY_SIZE)); + siblings_.reset(SiblingArray::create(storage, storage_node_id_, + SIBLING_ARRAY_SIZE)); + blocks_.reset(BlockArray::create(storage, storage_node_id_, + BLOCK_ARRAY_SIZE)); + entries_.reset(EntryArray::create(storage, storage_node_id_, + ENTRY_ARRAY_SIZE)); store_.reset(BytesStore::create(storage, storage_node_id_)); header_->nodes_storage_node_id = nodes_->storage_node_id(); header_->siblings_storage_node_id = siblings_->storage_node_id(); @@ -510,15 +472,12 @@ void DoubleArray<Bytes>::open_map(Storage *storage, uint32_t storage_node_id) { } DoubleArrayResult DoubleArray<Bytes>::get_key(int64_t key_id, Key *key) { - Entry entry; - if (!entries_->get(key_id, &entry)) { - return DOUBLE_ARRAY_FAILED; - } + Entry entry = entries_->get(key_id); if (!entry) { return DOUBLE_ARRAY_NOT_FOUND; } - if (!store_->get(entry.bytes_id(), key)) { - return DOUBLE_ARRAY_FAILED; + if (key) { + *key = store_->get(entry.bytes_id()); } return DOUBLE_ARRAY_FOUND; } @@ -542,21 +501,13 @@ bool DoubleArray<Bytes>::replace_key(int64_t key_id, KeyArg src_key, return false; } } - Entry * const entry = entries_->get_pointer(key_id); - if (!entry) { - // Error. - return false; - } + Entry * const entry = &entries_->get_value(key_id); Node *src_node; if (find_leaf(src_key, &src_node, &key_pos) != DOUBLE_ARRAY_FOUND) { // Critical error. return false; } - uint64_t bytes_id; - if (!store_->add(dest_key, &bytes_id)) { - // Error. - return false; - } + uint64_t bytes_id = store_->add(dest_key); dest_node->set_key_id(key_id); *entry = Entry::valid_entry(bytes_id); src_node->set_offset(NODE_INVALID_OFFSET); @@ -565,10 +516,7 @@ bool DoubleArray<Bytes>::replace_key(int64_t key_id, KeyArg src_key, DoubleArrayResult DoubleArray<Bytes>::find_leaf(KeyArg key, Node **leaf_node, uint64_t *leaf_key_pos) { - Node *node = nodes_->get_pointer(ROOT_NODE_ID); - if (!node) { - return DOUBLE_ARRAY_FAILED; - } + Node *node = &nodes_->get_value(ROOT_NODE_ID); uint64_t key_pos; for (key_pos = 0; key_pos < key.size(); ++key_pos) { if (node->is_leaf()) { @@ -577,10 +525,7 @@ DoubleArrayResult DoubleArray<Bytes>::find_leaf(KeyArg key, Node **leaf_node, return DOUBLE_ARRAY_FOUND; } const uint64_t child_node_id = node->offset() ^ key[key_pos]; - Node * const child_node = nodes_->get_pointer(child_node_id); - if (!child_node) { - return DOUBLE_ARRAY_FAILED; - } + Node * const child_node = &nodes_->get_value(child_node_id); if (child_node->label() != key[key_pos]) { *leaf_node = node; *leaf_key_pos = key_pos; @@ -597,10 +542,7 @@ DoubleArrayResult DoubleArray<Bytes>::find_leaf(KeyArg key, Node **leaf_node, return DOUBLE_ARRAY_NOT_FOUND; } const uint64_t node_id = node->offset() ^ NODE_TERMINAL_LABEL; - node = nodes_->get_pointer(node_id); - if (!node) { - return DOUBLE_ARRAY_FAILED; - } + node = &nodes_->get_value(node_id); *leaf_node = node; return node->is_leaf() ? DOUBLE_ARRAY_FOUND : DOUBLE_ARRAY_NOT_FOUND; } @@ -665,11 +607,7 @@ bool DoubleArray<Bytes>::insert_node(Node *node, uint64_t label, } } const uint64_t next_node_id = offset ^ label; - uint8_t *next_sibling = siblings_->get_pointer(next_node_id); - if (!next_sibling) { - // Error. - return false; - } + uint8_t *next_sibling = &siblings_->get_value(next_node_id); Node * const next_node = reserve_node(next_node_id); if (!next_node) { // Error. @@ -736,11 +674,7 @@ bool DoubleArray<Bytes>::separate(Node *node, uint64_t labels[2], return false; } uint8_t * const sibling_block = - siblings_->get_pointer(offset & ~(BLOCK_SIZE - 1)); - if (!sibling_block) { - // Error. - return false; - } + &siblings_->get_value(offset & ~(BLOCK_SIZE - 1)); nodes[0]->set_label(labels[0]); nodes[0]->set_key_id(node->key_id()); nodes[1]->set_label(labels[1]); @@ -766,21 +700,13 @@ bool DoubleArray<Bytes>::resolve(Node *node, uint64_t label) { return true; } uint64_t dest_node_id = offset ^ label; - Node * const dest_node = nodes_->get_pointer(dest_node_id); - if (!dest_node) { - // Error. - return false; - } + Node * const dest_node = &nodes_->get_value(dest_node_id); if (dest_node->is_phantom()) { return true; } Node * const node_block = dest_node - (dest_node_id % BLOCK_SIZE); uint8_t * const sibling_block = - siblings_->get_pointer(dest_node_id & ~(BLOCK_SIZE - 1)); - if (!sibling_block) { - // Error. - return false; - } + &siblings_->get_value(dest_node_id & ~(BLOCK_SIZE - 1)); uint64_t labels[NODE_MAX_LABEL + 1]; uint64_t num_labels = 0; uint64_t child_label = node->child(); @@ -810,29 +736,13 @@ bool DoubleArray<Bytes>::migrate_nodes(Node *node, uint64_t dest_offset, uint64_t num_labels) { const uint64_t src_offset = node->offset(); Node * const src_node_block = - nodes_->get_pointer(src_offset & ~(BLOCK_SIZE - 1)); - if (!src_node_block) { - // Error. - return false; - } + &nodes_->get_value(src_offset & ~(BLOCK_SIZE - 1)); uint8_t * const src_sibling_block = - siblings_->get_pointer(src_offset & ~(BLOCK_SIZE - 1)); - if (!src_sibling_block) { - // Error. - return false; - } + &siblings_->get_value(src_offset & ~(BLOCK_SIZE - 1)); Node * const dest_node_block = - nodes_->get_pointer(dest_offset & ~(BLOCK_SIZE - 1)); - if (!dest_node_block) { - // Error. - return false; - } + &nodes_->get_value(dest_offset & ~(BLOCK_SIZE - 1)); uint8_t * const dest_sibling_block = - siblings_->get_pointer(dest_offset & ~(BLOCK_SIZE - 1)); - if (!dest_sibling_block) { - // Error. - return false; - } + &siblings_->get_value(dest_offset & ~(BLOCK_SIZE - 1)); for (uint64_t i = 0; i < num_labels; ++i) { const uint64_t src_node_id = src_offset ^ labels[i]; Node * const src_node = &src_node_block[src_node_id % BLOCK_SIZE]; @@ -872,16 +782,8 @@ bool DoubleArray<Bytes>::find_offset(const uint64_t *labels, } uint64_t block_id = latest_block_id; do { - Block * const block = blocks_->get_pointer(block_id); - if (!block) { - // Error. - return false; - } - Node * const node_block = nodes_->get_pointer(block_id * BLOCK_SIZE); - if (!node_block) { - // Error. - return false; - } + Block * const block = &blocks_->get_value(block_id); + Node * const node_block = &nodes_->get_value(block_id * BLOCK_SIZE); const uint64_t first_phantom_node_id = block->first_phantom(); uint64_t node_id = first_phantom_node_id; do { @@ -933,17 +835,13 @@ auto DoubleArray<Bytes>::reserve_node(uint64_t node_id) -> Node * { if (node_id >= (header_->num_blocks * BLOCK_SIZE)) { block = reserve_block(block_id); } else { - block = blocks_->get_pointer(block_id); + block = &blocks_->get_value(block_id); } if (!block) { // Error. return nullptr; } - Node * const node = nodes_->get_pointer(node_id); - if (!node) { - // Error. - return nullptr; - } + Node * const node = &nodes_->get_value(node_id); Node * const node_block = node - (node_id % BLOCK_SIZE); Node * const next_node = &node_block[node->next()]; Node * const prev_node = &node_block[node->prev()]; @@ -971,16 +869,8 @@ auto DoubleArray<Bytes>::reserve_block(uint64_t block_id) -> Block * { << ", blocks_size = " << blocks_->size(); return nullptr; } - Block * const block = blocks_->get_pointer(block_id); - if (!block) { - // Error. - return nullptr; - } - Node * const node = nodes_->get_pointer(block_id * BLOCK_SIZE); - if (!node) { - // Error. - return nullptr; - } + Block * const block = &blocks_->get_value(block_id); + Node * const node = &nodes_->get_value(block_id * BLOCK_SIZE); *block = Block::empty_block(); for (uint64_t i = 0; i < BLOCK_SIZE; ++i) { node[i] = Node::phantom_node(i + 1, i - 1); @@ -1013,17 +903,9 @@ bool DoubleArray<Bytes>::set_block_level(uint64_t block_id, Block *block, } else { // The block is appended to the level group. const uint64_t next_block_id = header_->latest_blocks[level]; - Block * const next_block = blocks_->get_pointer(next_block_id); - if (!next_block) { - // Error. - return false; - } + Block * const next_block = &blocks_->get_value(next_block_id); const uint64_t prev_block_id = next_block->prev(); - Block * const prev_block = blocks_->get_pointer(prev_block_id); - if (!prev_block) { - // Error. - return false; - } + Block * const prev_block = &blocks_->get_value(prev_block_id); block->set_next(next_block_id); block->set_prev(prev_block_id); prev_block->set_next(block_id); @@ -1042,16 +924,8 @@ bool DoubleArray<Bytes>::unset_block_level(uint64_t block_id, Block *block) { // The level group becomes empty. header_->latest_blocks[level] = BLOCK_INVALID_ID; } else { - Block * const next_block = blocks_->get_pointer(next_block_id); - if (!next_block) { - // Error. - return false; - } - Block * const prev_block = blocks_->get_pointer(prev_block_id); - if (!prev_block) { - // Error. - return false; - } + Block * const next_block = &blocks_->get_value(next_block_id); + Block * const prev_block = &blocks_->get_value(prev_block_id); prev_block->set_next(next_block_id); next_block->set_prev(prev_block_id); if (block_id == header_->latest_blocks[level]) { Modified: lib/grnxx/map/double_array.hpp (+9 -4) =================================================================== --- lib/grnxx/map/double_array.hpp 2013-07-16 15:25:57 +0900 (7984803) +++ lib/grnxx/map/double_array.hpp 2013-07-16 19:27:01 +0900 (8e8b2b9) @@ -67,10 +67,15 @@ class DoubleArray<Bytes> : public Map<Bytes> { using Block = double_array::Block; using Entry = double_array::Entry; - using NodeArray = Array<Node, 65536, 8192, 8192>; // 42-bit - using SiblingArray = Array<uint8_t, 262144, 4096, 4096>; // 42-bit - using BlockArray = Array<Block, 8192, 1024, 1024>; // 33-bit - using EntryArray = Array<Entry, 65536, 4096, 4096>; // 40-bit + using NodeArray = Array<Node, 65536, 8192>; // 42-bit + using SiblingArray = Array<uint8_t, 262144, 4096>; // 42-bit + using BlockArray = Array<Block, 8192, 1024>; // 33-bit + using EntryArray = Array<Entry, 65536, 4096>; // 40-bit + + static constexpr uint64_t NODE_ARRAY_SIZE = 1ULL << 42; + static constexpr uint64_t SIBLING_ARRAY_SIZE = 1ULL << 42; + static constexpr uint64_t BLOCK_ARRAY_SIZE = 1ULL << 33; + static constexpr uint64_t ENTRY_ARRAY_SIZE = 1ULL << 40; public: using Header = double_array::Header; Modified: lib/grnxx/map/hash_table.cpp (+8 -13) =================================================================== --- lib/grnxx/map/hash_table.cpp 2013-07-16 15:25:57 +0900 (6b00e96) +++ lib/grnxx/map/hash_table.cpp 2013-07-16 19:27:01 +0900 (008f8ef) @@ -101,13 +101,13 @@ bool HashTable<T>::get(int64_t key_id, Key *key) { // Out of range. return false; } - bool bit; - keys_->get_bit(key_id, &bit); - if (!bit) { + if (!keys_->get_bit(key_id)) { // Not found. return false; } - keys_->get_key(key_id, key); + if (key) { + *key = keys_->get_key(key_id); + } return true; } @@ -190,8 +190,7 @@ bool HashTable<T>::add(KeyArg key, int64_t *key_id) { // Error. return false; } - int64_t next_key_id; - keys_->add(normalized_key, &next_key_id); + int64_t next_key_id = keys_->add(normalized_key); if (*stored_key_id == MAP_INVALID_KEY_ID) { ++header_->num_key_ids; } @@ -354,8 +353,7 @@ bool HashTable<T>::find_key(KeyArg key, int64_t **stored_key_id) { *stored_key_id = key_id; } } else { - Key stored_key; - keys_->get_key(*key_id, &stored_key); + Key stored_key = keys_->get_key(*key_id); if (Helper<T>::equal_to(stored_key, key)) { // Found. *stored_key_id = key_id; @@ -392,13 +390,10 @@ void HashTable<T>::rebuild() { // Copy keys from the current hash table to the new one. int64_t key_id; for (key_id = MAP_MIN_KEY_ID; key_id <= max_key_id(); ++key_id) { - bool bit; - keys_->get_bit(key_id, &bit); - if (!bit) { + if (!keys_->get_bit(key_id)) { continue; } - Key stored_key; - keys_->get_key(key_id, &stored_key); + Key stored_key = keys_->get_key(key_id); const uint64_t first_hash = Hash<T>()(stored_key); int64_t *stored_key_id; for (uint64_t hash = first_hash; ; hash = rehash(hash)) { Modified: lib/grnxx/map/hash_table/key_id_array.hpp (+18 -30) =================================================================== --- lib/grnxx/map/hash_table/key_id_array.hpp 2013-07-16 15:25:57 +0900 (4323dfc) +++ lib/grnxx/map/hash_table/key_id_array.hpp 2013-07-16 19:27:01 +0900 (b80a1d8) @@ -39,25 +39,33 @@ struct KeyIDArrayHelper; // Map<T> has at most 2^40 different keys. template <typename T, size_t T_SIZE> struct KeyIDArrayHelper { - using ImplType = ArrayImpl<int64_t, 65536, 8192, 4096>; + using ImplType = ArrayImpl<int64_t, 65536, 8192>; + static constexpr uint64_t SIZE = 1ULL << 41; + static constexpr uint64_t PAGE_SIZE = 1ULL << 16; }; // Map<T> has at most 2^8 different keys. template <typename T> struct KeyIDArrayHelper<T, 1> { - using ImplType = ArrayImpl<int64_t, 512, 1, 1>; + using ImplType = ArrayImpl<int64_t, 0, 0>; + static constexpr uint64_t SIZE = 1ULL << 9; + static constexpr uint64_t PAGE_SIZE = SIZE; }; // Map<T> has at most 2^16 different keys. template <typename T> struct KeyIDArrayHelper<T, 2> { - using ImplType = ArrayImpl<int64_t, 512, 256, 1>; + using ImplType = ArrayImpl<int64_t, 512, 0>; + static constexpr uint64_t SIZE = 1ULL << 17; + static constexpr uint64_t PAGE_SIZE = 1ULL << 9; }; // Map<T> has at most 2^32 different keys. template <typename T> struct KeyIDArrayHelper<T, 4> { - using ImplType = ArrayImpl<int64_t, 65536, 512, 256>; + using ImplType = ArrayImpl<int64_t, 65536, 512>; + static constexpr uint64_t SIZE = 1ULL << 33; + static constexpr uint64_t PAGE_SIZE = 1ULL << 16; }; struct KeyIDArrayHeader { @@ -110,19 +118,11 @@ class KeyIDArray { // Return the number of values in each page. static constexpr uint64_t page_size() { - return ArrayImpl::page_size(); - } - // Return the number of pages in each table. - static constexpr uint64_t table_size() { - return ArrayImpl::table_size(); - } - // Return the number of tables in each secondary table. - static constexpr uint64_t secondary_table_size() { - return ArrayImpl::secondary_table_size(); + return KeyIDArrayHelper<T>::PAGE_SIZE; } // Return the number of values in Array. - static constexpr uint64_t size() { - return ArrayImpl::size(); + uint64_t size() const { + return impl_.size(); } // Return the storage node ID. @@ -134,22 +134,9 @@ class KeyIDArray { return mask_; } - // Get a value and return true on success. - // The value is assigned to "*value" iff "value" != nullptr. - bool get(uint64_t value_id, Value *value) { - return impl_.get(value_id & mask_, value); - } - // Set a value and return true on success. - bool set(uint64_t value_id, ValueArg value) { - return impl_.set(value_id & mask_, value); - } // Get a value and return its address on success. Value *get_pointer(uint64_t value_id) { - return impl_.get_pointer(value_id & mask_); - } - // Get a page and return its starting address on success. - Value *get_page(uint64_t page_id) { - return impl_.get_page(page_id & (mask_ / page_size())); + return &impl_.get_value(value_id & mask_); } private: @@ -177,7 +164,8 @@ class KeyIDArray { try { header_ = static_cast<KeyIDArrayHeader *>(storage_node.body()); *header_ = KeyIDArrayHeader(); - impl_.create(storage, storage_node_id_, MAP_INVALID_KEY_ID); + impl_.create(storage, storage_node_id_, KeyIDArrayHelper<T>::SIZE, + MAP_INVALID_KEY_ID); mask_ = mask; header_->impl_storage_node_id = impl_.storage_node_id(); header_->mask = mask_; Modified: lib/grnxx/map/key_store.cpp (+27 -21) =================================================================== --- lib/grnxx/map/key_store.cpp 2013-07-16 15:25:57 +0900 (0a03291) +++ lib/grnxx/map/key_store.cpp 2013-07-16 19:27:01 +0900 (6b24e0d) @@ -79,9 +79,9 @@ KeyStore<T> *KeyStore<T>::open(Storage *storage, uint32_t storage_node_id) { template <typename T> bool KeyStore<T>::unset(int64_t key_id) { // Prepare to update "bits_" and "links_". - const uint64_t unit_id = key_id / bits_->unit_size(); - const uint64_t unit_bit = 1ULL << (key_id % bits_->unit_size()); - BitArrayUnit * const unit = bits_->get_unit(unit_id); + const uint64_t unit_id = key_id / unit_size(); + const uint64_t unit_bit = 1ULL << (key_id % unit_size()); + BitArrayUnit * const unit = &bits_->get_unit(unit_id); if ((*unit & unit_bit) == 0) { // Not found. return false; @@ -89,7 +89,7 @@ bool KeyStore<T>::unset(int64_t key_id) { // Set "link" if this operation creates the first 0 bit in the unit. uint64_t *link = nullptr; if (*unit == ~BitArrayUnit(0)) { - link = links_->get_pointer(unit_id); + link = &links_->get_value(unit_id); } *unit &= ~unit_bit; if (link) { @@ -101,28 +101,34 @@ bool KeyStore<T>::unset(int64_t key_id) { } template <typename T> -bool KeyStore<T>::add(KeyArg key, int64_t *key_id) { +int64_t KeyStore<T>::add(KeyArg key) { // Find an unused key ID. const bool is_new_unit = (header_->latest_link == INVALID_LINK); uint64_t unit_id; if (is_new_unit) { - unit_id = (header_->max_key_id + 1) / bits_->unit_size(); + unit_id = (header_->max_key_id + 1) / unit_size(); } else { unit_id = header_->latest_link; } - BitArrayUnit * const unit = bits_->get_unit(unit_id); - const uint8_t unit_bit_id = bit_scan_forward(~*unit); - const uint64_t unit_bit = 1ULL << unit_bit_id; - const int64_t next_key_id = (unit_id * bits_->unit_size()) + unit_bit_id; + BitArrayUnit * const unit = &bits_->get_unit(unit_id); + uint8_t unit_bit_id; + uint64_t unit_bit; uint64_t *link = nullptr; if (is_new_unit) { links_->set(unit_id, INVALID_LINK); *unit = 0; - header_->latest_link = (header_->max_key_id + 1) / bits_->unit_size(); - } else if ((*unit | unit_bit) == ~BitArrayUnit(0)) { - // The unit will be removed from "links_" if it becomes full. - link = links_->get_pointer(header_->latest_link); + unit_bit_id = 0; + unit_bit = 1; + header_->latest_link = (header_->max_key_id + 1) / unit_size(); + } else { + unit_bit_id = bit_scan_forward(~*unit); + unit_bit = 1ULL << unit_bit_id; + if ((*unit | unit_bit) == ~BitArrayUnit(0)) { + // The unit will be removed from "links_" if it becomes full. + link = &links_->get_value(header_->latest_link); + } } + const int64_t next_key_id = (unit_id * unit_size()) + unit_bit_id; keys_->set(next_key_id, key); if (link) { header_->latest_link = *link; @@ -132,10 +138,7 @@ bool KeyStore<T>::add(KeyArg key, int64_t *key_id) { header_->max_key_id = next_key_id; } ++header_->num_keys; - if (key_id) { - *key_id = next_key_id; - } - return true; + return next_key_id; } template <typename T> @@ -155,9 +158,12 @@ void KeyStore<T>::create_store(Storage *storage, uint32_t storage_node_id) { try { header_ = static_cast<Header *>(storage_node.body()); *header_ = Header(); - keys_.reset(KeyArray::create(storage, storage_node_id_)); - bits_.reset(BitArray::create(storage, storage_node_id_)); - links_.reset(LinkArray::create(storage, storage_node_id_)); + keys_.reset(KeyArray::create(storage, storage_node_id_, + KeyStoreHelper<T>::KEY_ARRAY_SIZE)); + bits_.reset(BitArray::create(storage, storage_node_id_, + KeyStoreHelper<T>::BIT_ARRAY_SIZE)); + links_.reset(LinkArray::create(storage, storage_node_id_, + KeyStoreHelper<T>::LINK_ARRAY_SIZE)); header_->keys_storage_node_id = keys_->storage_node_id(); header_->bits_storage_node_id = bits_->storage_node_id(); header_->links_storage_node_id = links_->storage_node_id(); Modified: lib/grnxx/map/key_store.hpp (+45 -21) =================================================================== --- lib/grnxx/map/key_store.hpp 2013-07-16 15:25:57 +0900 (ddcf62c) +++ lib/grnxx/map/key_store.hpp 2013-07-16 19:27:01 +0900 (e52d9e5) @@ -53,41 +53,61 @@ struct KeyStoreHelper; // Map<T> has at most 2^40 different keys. template <typename T, size_t T_SIZE> struct KeyStoreHelper { - using KeyArray = Array<T, 65536, 4096, 4096>; - using BitArray = Array<bool, 65536, 4096, 4096>; - using LinkArray = Array<uint64_t, 16384, 1024, 1024>; + using KeyArray = Array<T, 65536, 4096>; + using BitArray = Array<bool, 65536, 4096>; + using LinkArray = Array<uint64_t, 16384, 1024>; + + static constexpr uint64_t KEY_ARRAY_SIZE = 1ULL << 40; + static constexpr uint64_t BIT_ARRAY_SIZE = 1ULL << 40; + static constexpr uint64_t LINK_ARRAY_SIZE = 1ULL << 34; }; // Map<T> has at most 2^8 different keys. template <typename T> struct KeyStoreHelper<T, 1> { - using KeyArray = Array<T, 256, 1, 1>; - using BitArray = Array<bool, 256, 1, 1>; - using LinkArray = Array<uint64_t, 4, 1, 1>; + using KeyArray = Array<T>; + using BitArray = Array<bool>; + using LinkArray = Array<uint64_t>; + + static constexpr uint64_t KEY_ARRAY_SIZE = 1ULL << 8; + static constexpr uint64_t BIT_ARRAY_SIZE = 1ULL << 8; + static constexpr uint64_t LINK_ARRAY_SIZE = 1ULL << 2; }; // Map<T> has at most 2^16 different keys. template <typename T> struct KeyStoreHelper<T, 2> { - using KeyArray = Array<T, 256, 256, 1>; - using BitArray = Array<bool, 256, 256, 1>; - using LinkArray = Array<uint64_t, 1024, 1, 1>; + using KeyArray = Array<T, 256>; + using BitArray = Array<bool, 256>; + using LinkArray = Array<uint64_t>; + + static constexpr uint64_t KEY_ARRAY_SIZE = 1ULL << 16; + static constexpr uint64_t BIT_ARRAY_SIZE = 1ULL << 16; + static constexpr uint64_t LINK_ARRAY_SIZE = 1ULL << 10; }; // Map<T> has at most 2^32 different keys. template <typename T> struct KeyStoreHelper<T, 4> { - using KeyArray = Array<T, 65536, 256, 256>; - using BitArray = Array<bool, 16384, 512, 512>; - using LinkArray = Array<uint64_t, 4096, 128, 128>; + using KeyArray = Array<T, 65536, 256>; + using BitArray = Array<bool, 16384, 512>; + using LinkArray = Array<uint64_t, 4096, 128>; + + static constexpr uint64_t KEY_ARRAY_SIZE = 1ULL << 32; + static constexpr uint64_t BIT_ARRAY_SIZE = 1ULL << 32; + static constexpr uint64_t LINK_ARRAY_SIZE = 1ULL << 26; }; // Map<T> has at most 2^40 different keys. template <> struct KeyStoreHelper<Bytes> { using KeyArray = BytesArray; - using BitArray = Array<bool, 65536, 4096, 4096>; - using LinkArray = Array<uint64_t, 16384, 1024, 1024>; + using BitArray = Array<bool, 65536, 4096>; + using LinkArray = Array<uint64_t, 16384, 1024>; + + static constexpr uint64_t KEY_ARRAY_SIZE = 1ULL << 40; + static constexpr uint64_t BIT_ARRAY_SIZE = 1ULL << 40; + static constexpr uint64_t LINK_ARRAY_SIZE = 1ULL << 34; }; template <typename T> @@ -119,18 +139,18 @@ class KeyStore { return header_->num_keys; } - bool get_key(int64_t key_id, Key *key = nullptr) { - return keys_->get(key_id, key); + Key get_key(int64_t key_id) { + return keys_->get(key_id); } - bool get_bit(int64_t key_id, bool *bit = nullptr) { - return bits_->get(key_id, bit); + bool get_bit(int64_t key_id) { + return bits_->get(key_id); } bool unset(int64_t key_id); - bool reset(int64_t key_id, KeyArg dest_key) { - return keys_->set(key_id, dest_key); + void reset(int64_t key_id, KeyArg dest_key) { + keys_->set(key_id, dest_key); } - bool add(KeyArg key, int64_t *key_id = nullptr); + int64_t add(KeyArg key); bool truncate(); @@ -144,6 +164,10 @@ class KeyStore { void create_store(Storage *storage, uint32_t storage_node_id); void open_store(Storage *storage, uint32_t storage_node_id); + + static constexpr uint64_t unit_size() { + return sizeof(typename BitArray::Unit) * 8; + } }; } // namespace map Modified: lib/grnxx/map/patricia.cpp (+82 -103) =================================================================== --- lib/grnxx/map/patricia.cpp 2013-07-16 15:25:57 +0900 (cd3d52b) +++ lib/grnxx/map/patricia.cpp 2013-07-16 19:27:01 +0900 (ebb77f6) @@ -105,13 +105,13 @@ bool Patricia<T>::get(int64_t key_id, Key *key) { // Out of range. return false; } - bool bit; - keys_->get_bit(key_id, &bit); - if (!bit) { + if (!keys_->get_bit(key_id)) { // Not found. return false; } - keys_->get_key(key_id, key); + if (key) { + *key = keys_->get_key(key_id); + } return true; } @@ -126,7 +126,7 @@ bool Patricia<T>::unset(int64_t key_id) { uint64_t node_id = ROOT_NODE_ID; Node *prev_node = nullptr; for ( ; ; ) { - Node * const node = nodes_->get_pointer(node_id); + Node * const node = &nodes_->get_value(node_id); if (node->status() == NODE_LEAF) { if (node->key_id() != key_id) { // Not found. @@ -160,7 +160,7 @@ bool Patricia<T>::reset(int64_t key_id, KeyArg dest_key) { Node *src_prev_node = nullptr; Node *src_sibling_node = nullptr; for ( ; ; ) { - src_node = nodes_->get_pointer(node_id); + src_node = &nodes_->get_value(node_id); if (src_node->status() == NODE_LEAF) { if (src_node->key_id() != key_id) { // Not found. @@ -180,7 +180,7 @@ bool Patricia<T>::reset(int64_t key_id, KeyArg dest_key) { Node *history[(sizeof(Key) * 8) + 1]; int depth = -1; for ( ; ; ) { - Node * const node = nodes_->get_pointer(node_id); + Node * const node = &nodes_->get_value(node_id); history[++depth] = node; if (node->status() == NODE_LEAF) { break; @@ -189,8 +189,7 @@ bool Patricia<T>::reset(int64_t key_id, KeyArg dest_key) { get_ith_bit(dest_normalized_key, node->bit_pos()); } // Count the number of the common prefix bits. - Key stored_key; - keys_->get_key(history[depth]->key_id(), &stored_key); + Key stored_key = keys_->get_key(history[depth]->key_id()); const uint64_t count = count_common_prefix_bits(dest_normalized_key, stored_key); if (count == (sizeof(Key) * 8)) { @@ -205,7 +204,7 @@ bool Patricia<T>::reset(int64_t key_id, KeyArg dest_key) { --depth; } Node * const dest_prev_node = history[depth]; - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); keys_->reset(key_id, dest_normalized_key); Node *dest_node; Node *dest_sibling_node; @@ -234,16 +233,14 @@ template <typename T> bool Patricia<T>::find(KeyArg key, int64_t *key_id) { const Key normalized_key = Helper<T>::normalize(key); uint64_t node_id = ROOT_NODE_ID; - Node node; - nodes_->get(node_id, &node); + Node node = nodes_->get(node_id); if (node.status() == NODE_DEAD) { // Not found. return false; } for ( ; ; ) { if (node.status() == NODE_LEAF) { - Key stored_key; - keys_->get_key(node.key_id(), &stored_key); + Key stored_key = keys_->get_key(node.key_id()); if (!Helper<T>::equal_to(normalized_key, stored_key)) { // Not found. return false; @@ -254,7 +251,7 @@ bool Patricia<T>::find(KeyArg key, int64_t *key_id) { return true; } node_id = node.offset() + get_ith_bit(normalized_key, node.bit_pos()); - nodes_->get(node_id, &node); + node = nodes_->get(node_id); } } @@ -262,11 +259,10 @@ template <typename T> bool Patricia<T>::add(KeyArg key, int64_t *key_id) { const Key normalized_key = Helper<T>::normalize(key); uint64_t node_id = ROOT_NODE_ID; - Node *node = nodes_->get_pointer(node_id); + Node *node = &nodes_->get_value(node_id); if (node->status() == NODE_DEAD) { // The patricia is empty. - int64_t next_key_id; - keys_->add(normalized_key, &next_key_id); + int64_t next_key_id = keys_->add(normalized_key); *node = Node::leaf_node(next_key_id); if (key_id) { *key_id = next_key_id; @@ -278,12 +274,11 @@ bool Patricia<T>::add(KeyArg key, int64_t *key_id) { history[0] = node; while (node->status() != NODE_LEAF) { node_id = node->offset() + get_ith_bit(normalized_key, node->bit_pos()); - node = nodes_->get_pointer(node_id); + node = &nodes_->get_value(node_id); history[++depth] = node; } // Count the number of the common prefix bits. - Key stored_key; - keys_->get_key(node->key_id(), &stored_key); + Key stored_key = keys_->get_key(node->key_id()); const uint64_t count = count_common_prefix_bits(normalized_key, stored_key); if (count == (sizeof(Key) * 8)) { // Found. @@ -300,9 +295,8 @@ bool Patricia<T>::add(KeyArg key, int64_t *key_id) { --depth; } node = history[depth]; - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); - int64_t next_key_id; - keys_->add(normalized_key, &next_key_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); + int64_t next_key_id = keys_->add(normalized_key); if (get_ith_bit(normalized_key, count)) { next_nodes[0] = *node; next_nodes[1] = Node::leaf_node(next_key_id); @@ -322,7 +316,7 @@ template <typename T> bool Patricia<T>::remove(KeyArg key) { const Key normalized_key = Helper<T>::normalize(key); uint64_t node_id = ROOT_NODE_ID; - Node *node = nodes_->get_pointer(node_id); + Node *node = &nodes_->get_value(node_id); if (node->status() == NODE_DEAD) { // Not found. return false; @@ -330,8 +324,7 @@ bool Patricia<T>::remove(KeyArg key) { Node *prev_node = nullptr; for ( ; ; ) { if (node->status() == NODE_LEAF) { - Key stored_key; - keys_->get_key(node->key_id(), &stored_key); + Key stored_key = keys_->get_key(node->key_id()); if (!Helper<T>::equal_to(normalized_key, stored_key)) { // Not found. return false; @@ -347,7 +340,7 @@ bool Patricia<T>::remove(KeyArg key) { } prev_node = node; node_id = node->offset() + get_ith_bit(normalized_key, node->bit_pos()); - node = nodes_->get_pointer(node_id); + node = &nodes_->get_value(node_id); } } @@ -355,7 +348,7 @@ template <typename T> bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { const Key src_normalized_key = Helper<T>::normalize(src_key); uint64_t node_id = ROOT_NODE_ID; - Node *src_node = nodes_->get_pointer(node_id); + Node *src_node = &nodes_->get_value(node_id); if (src_node->status() == NODE_DEAD) { // Not found. return false; @@ -366,8 +359,7 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { for ( ; ; ) { if (src_node->status() == NODE_LEAF) { src_key_id = src_node->key_id(); - Key stored_key; - keys_->get_key(src_key_id, &stored_key); + Key stored_key = keys_->get_key(src_key_id); if (!Helper<T>::equal_to(src_normalized_key, stored_key)) { // Not found. return false; @@ -380,7 +372,7 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { src_prev_node = src_node; node_id = src_node->offset() + get_ith_bit(src_normalized_key, src_node->bit_pos()); - src_node = nodes_->get_pointer(node_id); + src_node = &nodes_->get_value(node_id); } // Add the destination key. const Key dest_normalized_key = Helper<T>::normalize(dest_key); @@ -388,7 +380,7 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { Node *history[(sizeof(Key) * 8) + 1]; int depth = -1; for ( ; ; ) { - Node * const node = nodes_->get_pointer(node_id); + Node * const node = &nodes_->get_value(node_id); history[++depth] = node; if (node->status() == NODE_LEAF) { break; @@ -397,8 +389,7 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { get_ith_bit(dest_normalized_key, node->bit_pos()); } // Count the number of the common prefix bits. - Key stored_key; - keys_->get_key(history[depth]->key_id(), &stored_key); + Key stored_key = keys_->get_key(history[depth]->key_id()); const uint64_t count = count_common_prefix_bits(dest_normalized_key, stored_key); if (count == (sizeof(Key) * 8)) { @@ -413,7 +404,7 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { --depth; } Node * const dest_prev_node = history[depth]; - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); keys_->reset(src_key_id, dest_normalized_key); Node *dest_node; Node *dest_sibling_node; @@ -443,7 +434,7 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { template <typename T> bool Patricia<T>::truncate() { - Node * const root_node = nodes_->get_pointer(ROOT_NODE_ID); + Node * const root_node = &nodes_->get_value(ROOT_NODE_ID); if (!root_node) { return false; } @@ -464,11 +455,12 @@ void Patricia<T>::create_map(Storage *storage, uint32_t storage_node_id, try { header_ = static_cast<Header *>(storage_node.body()); *header_ = Header(); - nodes_.reset(NodeArray::create(storage, storage_node_id_)); + // TODO: Remove a magic number. + nodes_.reset(NodeArray::create(storage, storage_node_id_, 1ULL << 41)); keys_.reset(KeyStore<T>::create(storage, storage_node_id_)); header_->nodes_storage_node_id = nodes_->storage_node_id(); header_->keys_storage_node_id = keys_->storage_node_id(); - Node * const root_node = nodes_->get_pointer(ROOT_NODE_ID); + Node * const root_node = &nodes_->get_value(ROOT_NODE_ID); *root_node = Node::dead_node(); } catch (...) { storage->unlink_node(storage_node_id_); @@ -606,13 +598,13 @@ bool Patricia<Bytes>::get(int64_t key_id, Key *key) { // Out of range. return false; } - bool bit; - keys_->get_bit(key_id, &bit); - if (!bit) { + if (!keys_->get_bit(key_id)) { // Not found. return false; } - keys_->get_key(key_id, key); + if (key) { + *key = keys_->get_key(key_id); + } return true; } @@ -626,7 +618,7 @@ bool Patricia<Bytes>::unset(int64_t key_id) { uint64_t node_id = ROOT_NODE_ID; Node *prev_node = nullptr; for ( ; ; ) { - Node * const node = nodes_->get_pointer(node_id); + Node * const node = &nodes_->get_value(node_id); switch (node->status()) { case NODE_LEAF: { if (node->key_id() != key_id) { @@ -676,7 +668,7 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { Node *src_prev_node = nullptr; Node *src_sibling_node = nullptr; for ( ; ; ) { - src_node = nodes_->get_pointer(src_node_id); + src_node = &nodes_->get_value(src_node_id); if (src_node->status() == NODE_LEAF) { if (src_node->key_id() != key_id) { // Not found. @@ -710,7 +702,7 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { Node *history[HISTORY_SIZE]; int depth = -1; for ( ; ; ) { - Node *node = nodes_->get_pointer(dest_node_id); + Node *node = &nodes_->get_value(dest_node_id); history[++depth % HISTORY_SIZE] = node; if (node->status() == NODE_LEAF) { break; @@ -729,11 +721,10 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { // Find a leaf node. Node *leaf_node = history[depth % HISTORY_SIZE]; while (leaf_node->status() != NODE_LEAF) { - leaf_node = nodes_->get_pointer(leaf_node->offset()); + leaf_node = &nodes_->get_value(leaf_node->offset()); } // Count the number of the common prefix bits. - Key stored_key; - keys_->get_key(leaf_node->key_id(), &stored_key); + Key stored_key = keys_->get_key(leaf_node->key_id()); const uint64_t min_size = (dest_key.size() < stored_key.size()) ? dest_key.size() : stored_key.size(); uint64_t count; @@ -748,7 +739,7 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { return false; } Node * const dest_prev_node = history[depth % HISTORY_SIZE]; - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); keys_->reset(key_id, dest_key); Node *dest_node; Node *dest_sibling_node; @@ -796,7 +787,7 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { // Find the branching point with the naive method. dest_node_id = ROOT_NODE_ID; for ( ; ; ) { - dest_prev_node = nodes_->get_pointer(dest_node_id); + dest_prev_node = &nodes_->get_value(dest_node_id); if (dest_prev_node->status() == NODE_LEAF) { break; } else if (dest_prev_node->status() == NODE_BRANCH) { @@ -813,7 +804,7 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { } } } - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); keys_->reset(key_id, dest_key); Node *dest_node; Node *dest_sibling_node; @@ -841,8 +832,7 @@ bool Patricia<Bytes>::reset(int64_t key_id, KeyArg dest_key) { bool Patricia<Bytes>::find(KeyArg key, int64_t *key_id) { const uint64_t bit_size = key.size() * 8; uint64_t node_id = ROOT_NODE_ID; - Node node; - nodes_->get(node_id, &node); + Node node = nodes_->get(node_id); if (node.status() == NODE_DEAD) { // Not found. return false; @@ -850,8 +840,7 @@ bool Patricia<Bytes>::find(KeyArg key, int64_t *key_id) { for ( ; ; ) { switch (node.status()) { case NODE_LEAF: { - Key stored_key; - keys_->get_key(node.key_id(), &stored_key); + Key stored_key = keys_->get_key(node.key_id()); if (key != stored_key) { // Not found. return false; @@ -878,7 +867,7 @@ bool Patricia<Bytes>::find(KeyArg key, int64_t *key_id) { break; } } - nodes_->get(node_id, &node); + node = nodes_->get(node_id); } } @@ -886,12 +875,11 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { constexpr std::size_t HISTORY_SIZE = 8; int64_t * const cache = nullptr; // int64_t * const cache = -// cache_->get_pointer(hash_table::Hash<Key>()(key) % cache_->size()); +// &cache_->get_value(hash_table::Hash<Key>()(key) % cache_->size()); // if ((*cache >= 0) && (*cache < keys_->max_key_id())) { -// bool bit; -// if (keys_->get_bit(*cache, &bit) && bit) { -// Key cached_key; -// if (keys_->get_key(*cache, &cached_key) && (key == cached_key)) { +// if (keys_->get_bit(*cache)) { +// Key cached_key = keys_->get_key(*cache); +// if (key == cached_key) { // if (key_id) { // *key_id = *cache; // } @@ -900,11 +888,10 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { // } // } uint64_t node_id = ROOT_NODE_ID; - Node *node = nodes_->get_pointer(node_id); + Node *node = &nodes_->get_value(node_id); if (node->status() == NODE_DEAD) { // The patricia is empty. - int64_t next_key_id; - keys_->add(key, &next_key_id); + int64_t next_key_id = keys_->add(key); *node = Node::leaf_node(next_key_id); if (key_id) { *key_id = next_key_id; @@ -930,17 +917,16 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { } node_id = node->offset() + 1; } - node = nodes_->get_pointer(node_id); + node = &nodes_->get_value(node_id); history[++depth % HISTORY_SIZE] = node; } // Find a leaf node. while (node->status() != NODE_LEAF) { node_id = node->offset(); - node = nodes_->get_pointer(node_id); + node = &nodes_->get_value(node_id); } // Count the number of the common prefix bits. - Key stored_key; - keys_->get_key(node->key_id(), &stored_key); + Key stored_key = keys_->get_key(node->key_id()); const uint64_t min_size = (key.size() < stored_key.size()) ? key.size() : stored_key.size(); uint64_t count; @@ -961,9 +947,8 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { return false; } node = history[depth % HISTORY_SIZE]; - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); - int64_t next_key_id; - keys_->add(key, &next_key_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); + int64_t next_key_id = keys_->add(key); if (count == key.size()) { // "key" is a prefix of "stored_key". next_nodes[0] = Node::leaf_node(next_key_id); @@ -1004,7 +989,7 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { // Find the branching point with the naive method. node_id = ROOT_NODE_ID; for ( ; ; ) { - node = nodes_->get_pointer(node_id); + node = &nodes_->get_value(node_id); if (node->status() == NODE_LEAF) { break; } else if (node->status() == NODE_BRANCH) { @@ -1020,9 +1005,8 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { } } } - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); - int64_t next_key_id; - keys_->add(key, &next_key_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); + int64_t next_key_id = keys_->add(key); if (get_ith_bit(key, count)) { next_nodes[0] = *node; next_nodes[1] = Node::leaf_node(next_key_id); @@ -1044,7 +1028,7 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { bool Patricia<Bytes>::remove(KeyArg key) { const uint64_t bit_size = key.size() * 8; uint64_t node_id = ROOT_NODE_ID; - Node *node = nodes_->get_pointer(node_id); + Node *node = &nodes_->get_value(node_id); if (node->status() == NODE_DEAD) { // Not found. return false; @@ -1053,8 +1037,7 @@ bool Patricia<Bytes>::remove(KeyArg key) { for ( ; ; ) { switch (node->status()) { case NODE_LEAF: { - Key stored_key; - keys_->get_key(node->key_id(), &stored_key); + Key stored_key = keys_->get_key(node->key_id()); if (stored_key != key) { // Not found. return false; @@ -1086,7 +1069,7 @@ bool Patricia<Bytes>::remove(KeyArg key) { } } prev_node = node; - node = nodes_->get_pointer(node_id); + node = &nodes_->get_value(node_id); } } @@ -1096,7 +1079,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, const uint64_t src_bit_size = src_key.size() * 8; int64_t src_key_id; uint64_t src_node_id = ROOT_NODE_ID; - Node *src_node = nodes_->get_pointer(src_node_id); + Node *src_node = &nodes_->get_value(src_node_id); if (src_node->status() == NODE_DEAD) { // Not found. return false; @@ -1106,8 +1089,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, for ( ; ; ) { if (src_node->status() == NODE_LEAF) { src_key_id = src_node->key_id(); - Key stored_key; - keys_->get_key(src_key_id, &stored_key); + Key stored_key = keys_->get_key(src_key_id); if (stored_key != src_key) { // Not found. return false; @@ -1135,7 +1117,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, (src_node->bit_size() < src_bit_size); } src_prev_node = src_node; - src_node = nodes_->get_pointer(src_node_id); + src_node = &nodes_->get_value(src_node_id); } // Add the destination key. constexpr std::size_t HISTORY_SIZE = 8; @@ -1144,7 +1126,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, Node *history[HISTORY_SIZE]; int depth = -1; for ( ; ; ) { - Node *node = nodes_->get_pointer(dest_node_id); + Node *node = &nodes_->get_value(dest_node_id); history[++depth % HISTORY_SIZE] = node; if (node->status() == NODE_LEAF) { break; @@ -1163,11 +1145,10 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, // Find a leaf node. Node *leaf_node = history[depth % HISTORY_SIZE]; while (leaf_node->status() != NODE_LEAF) { - leaf_node = nodes_->get_pointer(leaf_node->offset()); + leaf_node = &nodes_->get_value(leaf_node->offset()); } // Count the number of the common prefix bits. - Key stored_key; - keys_->get_key(leaf_node->key_id(), &stored_key); + Key stored_key = keys_->get_key(leaf_node->key_id()); const uint64_t min_size = (dest_key.size() < stored_key.size()) ? dest_key.size() : stored_key.size(); uint64_t count; @@ -1182,7 +1163,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, return false; } Node * const dest_prev_node = history[depth % HISTORY_SIZE]; - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); keys_->reset(src_key_id, dest_key); Node *dest_node; Node *dest_sibling_node; @@ -1230,7 +1211,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, // Find the branching point with the naive method. dest_node_id = ROOT_NODE_ID; for ( ; ; ) { - dest_prev_node = nodes_->get_pointer(dest_node_id); + dest_prev_node = &nodes_->get_value(dest_node_id); if (dest_prev_node->status() == NODE_LEAF) { break; } else if (dest_prev_node->status() == NODE_BRANCH) { @@ -1247,7 +1228,7 @@ bool Patricia<Bytes>::replace(KeyArg src_key, KeyArg dest_key, } } } - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + Node * const next_nodes = &nodes_->get_value(header_->next_node_id); keys_->reset(src_key_id, dest_key); Node *dest_node; Node *dest_sibling_node; @@ -1278,16 +1259,14 @@ bool Patricia<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id, bool found = false; uint64_t node_id = ROOT_NODE_ID; for ( ; ; ) { - Node node; - nodes_->get(node_id, &node); + Node node = nodes_->get(node_id); switch (node.status()) { case NODE_DEAD: { // Not found. return found; } case NODE_LEAF: { - Key stored_key; - keys_->get_key(node.key_id(), &stored_key); + Key stored_key = keys_->get_key(node.key_id()); if (query.starts_with(stored_key)) { if (key_id) { *key_id = node.key_id(); @@ -1310,10 +1289,8 @@ bool Patricia<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id, if (node.bit_size() > bit_size) { return found; } else if (node.bit_size() < bit_size) { - Node leaf_node; - nodes_->get(node.offset(), &leaf_node); - Key stored_key; - keys_->get_key(leaf_node.key_id(), &stored_key); + Node leaf_node = nodes_->get(node.offset()); + Key stored_key = keys_->get_key(leaf_node.key_id()); if (query.starts_with(stored_key)) { if (key_id) { *key_id = leaf_node.key_id(); @@ -1332,7 +1309,7 @@ bool Patricia<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id, } bool Patricia<Bytes>::truncate() { - Node * const root_node = nodes_->get_pointer(ROOT_NODE_ID); + Node * const root_node = &nodes_->get_value(ROOT_NODE_ID); keys_->truncate(); *root_node = Node::dead_node(); return true; @@ -1347,13 +1324,15 @@ void Patricia<Bytes>::create_map(Storage *storage, uint32_t storage_node_id, try { header_ = static_cast<Header *>(storage_node.body()); *header_ = Header(); - nodes_.reset(NodeArray::create(storage, storage_node_id_)); + // TODO: Remove a magic number. + nodes_.reset(NodeArray::create(storage, storage_node_id_, 1ULL << 41)); keys_.reset(KeyStore<Bytes>::create(storage, storage_node_id_)); - cache_.reset(Cache::create(storage, storage_node_id_, -1)); + // TODO: Remove a magic number. + cache_.reset(Cache::create(storage, storage_node_id_, 1ULL << 20, -1)); header_->nodes_storage_node_id = nodes_->storage_node_id(); header_->keys_storage_node_id = keys_->storage_node_id(); header_->cache_storage_node_id = cache_->storage_node_id(); - Node * const root_node = nodes_->get_pointer(ROOT_NODE_ID); + Node * const root_node = &nodes_->get_value(ROOT_NODE_ID); *root_node = Node::dead_node(); } catch (...) { storage->unlink_node(storage_node_id_); Modified: lib/grnxx/map/patricia.hpp (+3 -3) =================================================================== --- lib/grnxx/map/patricia.hpp 2013-07-16 15:25:57 +0900 (30249ea) +++ lib/grnxx/map/patricia.hpp 2013-07-16 19:27:01 +0900 (c91e88b) @@ -43,7 +43,7 @@ struct Header; template <typename T> class Patricia : public Map<T> { using Node = patricia::Node; - using NodeArray = Array<Node>; + using NodeArray = Array<Node, 65536, 8192>; public: using Header = patricia::Header; @@ -93,8 +93,8 @@ class Patricia : public Map<T> { template <> class Patricia<Bytes> : public Map<Bytes> { using Node = patricia::Node; - using NodeArray = Array<Node>; - using Cache = Array<int64_t, 1 << 20, 1, 1>; + using NodeArray = Array<Node, 65536, 8192>; + using Cache = Array<int64_t>; public: using Header = patricia::Header; Modified: test/test_array.cpp (+74 -86) =================================================================== --- test/test_array.cpp 2013-07-16 15:25:57 +0900 (a14f285) +++ test/test_array.cpp 2013-07-16 19:27:01 +0900 (4378754) @@ -44,6 +44,10 @@ T generate_random_value() { const T *value = reinterpret_cast<const T *>(&random_value); return *value; } +template <> +bool generate_random_value<bool>() { + return bool(mersenne_twister() & 1); +} // Generate a random floating point number. template <> double generate_random_value<double>() { @@ -92,128 +96,112 @@ void generate_random_values(std::uint64_t num_values, std::vector<T> *values) { //} template <typename T, - std::uint64_t PAGE_SIZE, - std::uint64_t TABLE_SIZE, - std::uint64_t SECONDARY_TABLE_SIZE> -void test_array() { - using Array = grnxx::Array<T, PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE>; + std::uint64_t PAGE_SIZE = 0, + std::uint64_t TABLE_SIZE = 0> +void test_array(std::uint64_t size) { + using Array = grnxx::Array<T, PAGE_SIZE, TABLE_SIZE>; // Create an anonymous Storage. std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<Array> array; // Create an Array and test its member functions. - array.reset(array->create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID)); - assert(array->page_size() == PAGE_SIZE); - assert(array->table_size() == TABLE_SIZE); - assert(array->secondary_table_size() == SECONDARY_TABLE_SIZE); - assert(array->size() == (PAGE_SIZE * TABLE_SIZE * SECONDARY_TABLE_SIZE)); + array.reset(Array::create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, size)); + assert(array->size() == size); const std::uint32_t storage_node_id = array->storage_node_id(); // Generate random data. std::vector<T> values; - generate_random_values<T>(array->size(), &values); + generate_random_values<T>(size, &values); // Set and get values. - for (std::uint64_t i = 0; i < array->size(); ++i) { - assert(array->set(i, values[i])); + for (std::uint64_t i = 0; i < size; ++i) { + array->set(i, values[i]); + assert(array->get(i) == values[i]); } - for (std::uint64_t i = 0; i < array->size(); ++i) { - T value; - assert(array->get(i, &value)); - assert(value == values[i]); - } - for (std::uint64_t i = 0; i < (array->size() / array->page_size()); ++i) { - assert(array->get_page(i)); + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get(i) == values[i]); } // Open the Array and get values. assert(array->open(storage.get(), storage_node_id)); - for (std::uint64_t i = 0; i < array->size(); ++i) { - T value; - assert(array->get(i, &value)); - assert(value == values[i]); + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get(i) == values[i]); } // Create an Array with default value. array.reset(array->create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, - values[0])); - for (std::uint64_t i = 0; i < array->size(); ++i) { - T value; - assert(array->get(i, &value)); - assert(value == values[0]); - - T * const pointer = array->get_pointer(i); - assert(pointer); - assert(*pointer == values[0]); + size, values[0])); + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get(i) == values[0]); + } + + // Set and get values. + for (std::uint64_t i = 0; i < size; ++i) { + array->get_value(i) = values[i]; + assert(array->get_value(i) == values[i]); + } + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get_value(i) == values[i]); } } -template <std::uint64_t PAGE_SIZE, - std::uint64_t TABLE_SIZE, - std::uint64_t SECONDARY_TABLE_SIZE> -void test_bit_array() { - using Array = grnxx::Array<bool, PAGE_SIZE, TABLE_SIZE, SECONDARY_TABLE_SIZE>; +template <std::uint64_t PAGE_SIZE = 0, + std::uint64_t TABLE_SIZE = 0> +void test_bit_array(std::uint64_t size) { + using Array = grnxx::Array<bool, PAGE_SIZE, TABLE_SIZE>; using Unit = typename Array::Unit; + constexpr uint64_t UNIT_SIZE = sizeof(Unit) * 8; // Create an anonymous Storage. std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<Array> array; // Create an Array and test its member functions. - array.reset(array->create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID)); - assert(array->unit_size() == (sizeof(Unit) * 8)); - assert(array->page_size() == PAGE_SIZE); - assert(array->table_size() == TABLE_SIZE); - assert(array->secondary_table_size() == SECONDARY_TABLE_SIZE); - assert(array->size() == (PAGE_SIZE * TABLE_SIZE * SECONDARY_TABLE_SIZE)); + array.reset(Array::create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, size)); + assert(array->size() == size); const std::uint32_t storage_node_id = array->storage_node_id(); - // Generate an array of random units. - std::vector<Unit> units; - generate_random_values(array->size() / array->unit_size(), &units); + // Generate random data. + std::vector<bool> values; + generate_random_values<bool>(size, &values); // Set and get values. - for (std::uint64_t i = 0; i < array->size(); ++i) { - const bool bit = (units[i / 64] >> (i % 64)) & 1; - assert(array->set(i, bit)); - } - for (std::uint64_t i = 0; i < array->size(); ++i) { - const bool expected_bit = (units[i / 64] >> (i % 64)) & 1; - bool stored_bit; - assert(array->get(i, &stored_bit)); - assert(stored_bit == expected_bit); + for (std::uint64_t i = 0; i < size; ++i) { + array->set(i, values[i]); + assert(array->get(i) == values[i]); } - for (std::uint64_t i = 0; i < (array->size() / array->unit_size()); ++i) { - const Unit * const unit = array->get_unit(i); - assert(unit); - assert(*unit == units[i]); - } - for (std::uint64_t i = 0; i < (array->size() / array->page_size()); ++i) { - assert(array->get_page(i)); + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get(i) == values[i]); } // Open the Array and get values. - array.reset(array->open(storage.get(), storage_node_id)); - for (std::uint64_t i = 0; i < array->size(); ++i) { - const bool expected_bit = (units[i / 64] >> (i % 64)) & 1; - bool stored_bit; - assert(array->get(i, &stored_bit)); - assert(stored_bit == expected_bit); + assert(array->open(storage.get(), storage_node_id)); + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get(i) == values[i]); + } + + // Create an Array with default value. + array.reset(array->create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, + size, values[0])); + for (std::uint64_t i = 0; i < size; ++i) { + assert(array->get(i) == values[0]); } - // Create Arrays with default value. - array.reset(array->create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, false)); - for (std::uint64_t i = 0; i < array->size(); ++i) { - bool bit; - assert(array->get(i, &bit)); - assert(!bit); + // Generate random data. + std::vector<Unit> units; + generate_random_values<Unit>(size, &units); + + // Set and get units. + for (std::uint64_t i = 0; i < (size / UNIT_SIZE); ++i) { + array->get_unit(i) = units[i]; + assert(array->get_unit(i) == units[i]); } - array.reset(array->create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, true)); - for (std::uint64_t i = 0; i < array->size(); ++i) { - bool bit; - assert(array->get(i, &bit)); - assert(bit); + for (std::uint64_t i = 0; i < (size / UNIT_SIZE); ++i) { + assert(array->get_unit(i) == units[i]); + for (std::uint64_t j = 0; j < UNIT_SIZE; ++j) { + assert(array->get((i * UNIT_SIZE) + j) == ((units[i] >> j) & 1)); + } } } @@ -221,18 +209,18 @@ template <typename T> void test_array() { GRNXX_NOTICE() << __PRETTY_FUNCTION__; - test_array<T, 256, 1, 1>(); - test_array<T, 256, 64, 1>(); - test_array<T, 256, 64, 16>(); + test_array<T>(256); + test_array<T, 256>(256 * 64); + test_array<T, 256, 64>(256 * 64 * 16); } template <> void test_array<bool>() { GRNXX_NOTICE() << __PRETTY_FUNCTION__; - test_bit_array<256, 1, 1>(); - test_bit_array<256, 64, 1>(); - test_bit_array<256, 64, 16>(); + test_bit_array(256); + test_bit_array<256>(256 * 64); + test_bit_array<256, 64>(256 * 64 * 16); } } // namesapce Modified: test/test_map.cpp (+28 -30) =================================================================== --- test/test_map.cpp 2013-07-16 15:25:57 +0900 (e54e48e) +++ test/test_map.cpp 2013-07-16 19:27:01 +0900 (e6ba51f) @@ -188,16 +188,13 @@ void test_bytes_store_get() { generate_random_keys(BYTES_STORE_NUM_KEYS, &keys); for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - std::uint64_t key_id; - assert(store->add(keys[i], &key_id)); - grnxx::Bytes stored_key; - assert(store->get(key_id, &stored_key)); + std::uint64_t key_id = store->add(keys[i]); + grnxx::Bytes stored_key = store->get(key_id); assert(keys[i] == stored_key); key_ids.push_back(key_id); } for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - grnxx::Bytes stored_key; - assert(store->get(key_ids[i], &stored_key)); + grnxx::Bytes stored_key = store->get(key_ids[i]); assert(keys[i] == stored_key); } } @@ -212,17 +209,15 @@ void test_bytes_store_unset() { generate_random_keys(BYTES_STORE_NUM_KEYS, &keys); for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - std::uint64_t key_id; - assert(store->add(keys[i], &key_id)); - assert(store->unset(key_id)); + std::uint64_t key_id = store->add(keys[i]); + store->unset(key_id); } for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - std::uint64_t key_id; - assert(store->add(keys[i], &key_id)); + std::uint64_t key_id = store->add(keys[i]); key_ids.push_back(key_id); } for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - assert(store->unset(key_ids[i])); + store->unset(key_ids[i]); } } @@ -235,8 +230,7 @@ void test_bytes_store_add() { generate_random_keys(BYTES_STORE_NUM_KEYS, &keys); for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - std::uint64_t key_id; - assert(store->add(keys[i], &key_id)); + store->add(keys[i]); } } @@ -250,18 +244,16 @@ void test_bytes_store_sweep() { generate_random_keys(BYTES_STORE_NUM_KEYS, &keys); for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - std::uint64_t key_id; - assert(store->add(keys[i], &key_id)); - assert(store->unset(key_id)); + std::uint64_t key_id = store->add(keys[i]); + store->unset(key_id); } assert(store->sweep(grnxx::Duration(0))); for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - std::uint64_t key_id; - assert(store->add(keys[i], &key_id)); + std::uint64_t key_id = store->add(keys[i]); key_ids.push_back(key_id); } for (std::uint64_t i = 0; i < BYTES_STORE_NUM_KEYS; ++i) { - assert(store->unset(key_ids[i])); + store->unset(key_ids[i]); } assert(store->sweep(grnxx::Duration(0))); } @@ -270,7 +262,8 @@ void test_bytes_array_create() { std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), - grnxx::STORAGE_ROOT_NODE_ID)); + grnxx::STORAGE_ROOT_NODE_ID, + 0)); } void test_bytes_array_create_with_default_value() { @@ -278,6 +271,7 @@ void test_bytes_array_create_with_default_value() { std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), grnxx::STORAGE_ROOT_NODE_ID, + 0, "Default")); } @@ -285,7 +279,8 @@ void test_bytes_array_open() { std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), - grnxx::STORAGE_ROOT_NODE_ID)); + grnxx::STORAGE_ROOT_NODE_ID, + 0)); const std::uint32_t storage_node_id = array->storage_node_id(); array.reset(grnxx::map::BytesArray::open(storage.get(), storage_node_id)); } @@ -294,7 +289,8 @@ void test_bytes_array_unlink() { std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), - grnxx::STORAGE_ROOT_NODE_ID)); + grnxx::STORAGE_ROOT_NODE_ID, + 0)); grnxx::StorageNode storage_node = storage->open_node(array->storage_node_id()); grnxx::map::BytesArray::unlink(storage.get(), storage_node.id()); @@ -305,7 +301,8 @@ void test_bytes_array_storage_node_id() { std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), - grnxx::STORAGE_ROOT_NODE_ID)); + grnxx::STORAGE_ROOT_NODE_ID, + 0)); grnxx::StorageNode storage_node = storage->open_node(array->storage_node_id()); assert(storage_node.status() == grnxx::STORAGE_NODE_ACTIVE); @@ -315,15 +312,15 @@ void test_bytes_array_get() { std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), - grnxx::STORAGE_ROOT_NODE_ID)); + grnxx::STORAGE_ROOT_NODE_ID, + 0)); std::vector<grnxx::Bytes> keys; generate_random_keys(MAP_NUM_KEYS, &keys); for (std::uint64_t i = 0; i < MAP_NUM_KEYS; ++i) { - assert(array->set(i, keys[i])); + array->set(i, keys[i]); } for (std::uint64_t i = 0; i < MAP_NUM_KEYS; ++i) { - grnxx::Bytes stored_key; - assert(array->get(i, &stored_key)); + grnxx::Bytes stored_key = array->get(i); assert(stored_key == keys[i]); } } @@ -332,11 +329,12 @@ void test_bytes_array_set() { std::unique_ptr<grnxx::Storage> storage(grnxx::Storage::create(nullptr)); std::unique_ptr<grnxx::map::BytesArray> array( grnxx::map::BytesArray::create(storage.get(), - grnxx::STORAGE_ROOT_NODE_ID)); + grnxx::STORAGE_ROOT_NODE_ID, + 0)); std::vector<grnxx::Bytes> keys; generate_random_keys(MAP_NUM_KEYS, &keys); for (std::uint64_t i = 0; i < MAP_NUM_KEYS; ++i) { - assert(array->set(i, keys[i])); + array->set(i, keys[i]); } }
