susumu.yata
null+****@clear*****
Tue Aug 20 18:27:20 JST 2013
susumu.yata 2013-08-20 18:27:20 +0900 (Tue, 20 Aug 2013) New Revision: dc8b80757df2e527ace5b3d5f8b6f15c83218fb9 https://github.com/groonga/grnxx/commit/dc8b80757df2e527ace5b3d5f8b6f15c83218fb9 Message: Update grnxx::map::HashTable to use grnxx::map::Pool. Modified files: lib/grnxx/map/hash_table.cpp lib/grnxx/map/hash_table.hpp Modified: lib/grnxx/map/hash_table.cpp (+467 -211) =================================================================== --- lib/grnxx/map/hash_table.cpp 2013-08-20 15:52:37 +0900 (f00942b) +++ lib/grnxx/map/hash_table.cpp 2013-08-20 18:27:20 +0900 (c43b7d6) @@ -1,5 +1,5 @@ /* - Copyright (C) 2013 Brazil, Inc. + 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 @@ -28,7 +28,7 @@ #include "grnxx/map/common_header.hpp" #include "grnxx/map/hash.hpp" #include "grnxx/map/helper.hpp" -#include "grnxx/map/key_pool.hpp" +#include "grnxx/map/pool.hpp" #include "grnxx/mutex.hpp" #include "grnxx/storage.hpp" @@ -38,42 +38,29 @@ namespace { constexpr char FORMAT_STRING[] = "grnxx::map::HashTable"; -constexpr uint64_t MIN_TABLE_SIZE = 256; +constexpr uint64_t MIN_TABLE_SIZE = 64; -} // namespace - -struct HashTableHeader { - CommonHeader common_header; +struct ImplHeader { uint64_t num_entries; - uint64_t table_id; uint32_t table_storage_node_id; - uint32_t pool_storage_node_id; - Mutex mutex; - // Initialize the member variables. - HashTableHeader(); - - // Return true iff the header seems to be correct. - explicit operator bool() const; + ImplHeader(); }; -HashTableHeader::HashTableHeader() - : common_header(FORMAT_STRING, MAP_HASH_TABLE), - num_entries(0), - table_id(0), - table_storage_node_id(STORAGE_INVALID_NODE_ID), - pool_storage_node_id(STORAGE_INVALID_NODE_ID), - mutex() {} +ImplHeader::ImplHeader() + : num_entries(0), + table_storage_node_id(STORAGE_INVALID_NODE_ID) {} -HashTableHeader::operator bool() const { - return common_header.format() == FORMAT_STRING; -} +class TableEntry { + static constexpr uint64_t IS_UNUSED_FLAG = 1ULL << 40; + static constexpr uint64_t IS_REMOVED_FLAG = 1ULL << 41; + static constexpr uint8_t MEMO_SHIFT = 42; + static constexpr uint64_t KEY_ID_MASK = (1ULL << 40) - 1; -class HashTableEntry { public: // Create an unused entry. - static HashTableEntry unused_entry() { - return HashTableEntry(IS_UNUSED_FLAG); + static TableEntry unused_entry() { + return TableEntry(IS_UNUSED_FLAG); } // Return true iff this entry is not used. @@ -105,83 +92,146 @@ class HashTableEntry { private: uint64_t value_; - explicit HashTableEntry(uint64_t value) : value_(value) {} + explicit TableEntry(uint64_t value) : value_(value) {} +}; - static constexpr uint64_t IS_UNUSED_FLAG = 1ULL << 40; - static constexpr uint64_t IS_REMOVED_FLAG = 1ULL << 41; - static constexpr uint8_t MEMO_SHIFT = 42; - static constexpr uint64_t KEY_ID_MASK = (1ULL << 40) - 1; +struct TableSizeError {}; + +} // namespace + +template <typename T> +class HashTableImpl { + using Header = ImplHeader; + using Table = Array<TableEntry>; + using Pool = Pool<T>; + + public: + using Key = typename Map<T>::Key; + using KeyArg = typename Map<T>::KeyArg; + using Cursor = typename Map<T>::Cursor; + + HashTableImpl(); + ~HashTableImpl(); + + static HashTableImpl *create(Storage *storage, uint32_t storage_node_id, + Pool *pool); + static HashTableImpl *open(Storage *storage, uint32_t storage_node_id, + Pool *pool); + + static void unlink(Storage *storage, uint32_t storage_node_id) { + storage->unlink_node(storage_node_id); + } + + uint32_t storage_node_id() const { + return storage_node_id_; + } + + int64_t max_key_id() { + return pool_->max_key_id(); + } + uint64_t num_keys() { + return pool_->num_keys(); + } + + bool get(int64_t key_id, Key *key = nullptr); + bool unset(int64_t key_id); + bool reset(int64_t key_id, KeyArg dest_key); + + bool find(KeyArg key, int64_t *key_id = nullptr); + bool add(KeyArg key, int64_t *key_id = nullptr); + bool remove(KeyArg key); + bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); + + void defrag(); + + void truncate(); + + private: + Storage *storage_; + uint32_t storage_node_id_; + Header *header_; + Pool *pool_; + std::unique_ptr<Table> table_; + + void create_impl(Storage *storage, uint32_t storage_node_id, Pool *pool); + void open_impl(Storage *storage, uint32_t storage_node_id, Pool *pool); + + // Search a hash table for a key ID. + // On success, return a pointer to a matched entry. + // On failure, return nullptr. + TableEntry *find_key_id(int64_t key_id); + // Search a hash table for a key. + // On success, assign a pointer to a matched entry to "*entry" and return + // true. + // On failure, assign a pointer to the first unused or removed entry to + // "*entry" and return false. + bool find_key(KeyArg key, uint64_t hash_value, TableEntry **entry); + + // Build a hash table. + void build_table(); + + // Move to the next entry. + uint64_t rehash(uint64_t hash) const { + return hash + 1; + } }; template <typename T> -HashTable<T>::HashTable() +HashTableImpl<T>::HashTableImpl() : storage_(nullptr), storage_node_id_(STORAGE_INVALID_NODE_ID), header_(nullptr), - table_(), - old_table_(), - pool_(), - table_id_(0) {} + pool_(nullptr), + table_() {} template <typename T> -HashTable<T>::~HashTable() {} +HashTableImpl<T>::~HashTableImpl() {} template <typename T> -HashTable<T> *HashTable<T>::create(Storage *storage, uint32_t storage_node_id, - const MapOptions &options) { - std::unique_ptr<HashTable> map(new (std::nothrow) HashTable); +HashTableImpl<T> *HashTableImpl<T>::create(Storage *storage, + uint32_t storage_node_id, + Pool *pool) { + std::unique_ptr<HashTableImpl> map(new (std::nothrow) HashTableImpl); if (!map) { GRNXX_ERROR() << "new grnxx::map::HashTable failed"; throw MemoryError(); } - map->create_map(storage, storage_node_id, options); + map->create_impl(storage, storage_node_id, pool); return map.release(); } template <typename T> -HashTable<T> *HashTable<T>::open(Storage *storage, uint32_t storage_node_id) { - std::unique_ptr<HashTable> map(new (std::nothrow) HashTable); +HashTableImpl<T> *HashTableImpl<T>::open(Storage *storage, + uint32_t storage_node_id, + Pool *pool) { + std::unique_ptr<HashTableImpl> map(new (std::nothrow) HashTableImpl); if (!map) { GRNXX_ERROR() << "new grnxx::map::HashTable failed"; throw MemoryError(); } - map->open_map(storage, storage_node_id); + map->open_impl(storage, storage_node_id, pool); return map.release(); } template <typename T> -uint32_t HashTable<T>::storage_node_id() const { - return storage_node_id_; -} - -template <typename T> -MapType HashTable<T>::type() const { - return MAP_HASH_TABLE; -} - -template <typename T> -int64_t HashTable<T>::max_key_id() { - return pool_->max_key_id(); -} - -template <typename T> -uint64_t HashTable<T>::num_keys() { - return pool_->num_keys(); -} - -template <typename T> -bool HashTable<T>::get(int64_t key_id, Key *key) { +bool HashTableImpl<T>::get(int64_t key_id, Key *key) { if ((key_id < MAP_MIN_KEY_ID) || (key_id > max_key_id())) { // Out of range. return false; } - return pool_->get(key_id, key); + if (key) { + return pool_->get(key_id, key); + } + return pool_->get_bit(key_id); } template <typename T> -bool HashTable<T>::unset(int64_t key_id) { - refresh_table(); - Entry * const entry = find_key_id(key_id); +bool HashTableImpl<T>::unset(int64_t key_id) { + if ((key_id < MAP_MIN_KEY_ID) || (key_id > max_key_id())) { + // Out of range. + return false; + } + TableEntry * const entry = find_key_id(key_id); if (!entry) { // Not found. return false; @@ -192,25 +242,28 @@ bool HashTable<T>::unset(int64_t key_id) { } template <typename T> -bool HashTable<T>::reset(int64_t key_id, KeyArg dest_key) { - refresh_table(); - Entry * const src_entry = find_key_id(key_id); +bool HashTableImpl<T>::reset(int64_t key_id, KeyArg dest_key) { + if ((key_id < MAP_MIN_KEY_ID) || (key_id > max_key_id())) { + // Out of range. + return false; + } + TableEntry * const src_entry = find_key_id(key_id); if (!src_entry) { // Not found. return false; } const Key dest_normalized_key = Helper<T>::normalize(dest_key); const uint64_t dest_hash_value = Hash<T>()(dest_normalized_key); - Entry *dest_entry; + TableEntry *dest_entry; if (find_key(dest_normalized_key, dest_hash_value, &dest_entry)) { // Found. return false; } - // Create a new table if the filling rate of the current table is greater + // Throw an exception if the filling rate of the current table is greater // than 62.5%. const uint64_t table_size = table_->size(); if (header_->num_entries > ((table_size + (table_size / 4)) / 2)) { - rebuild(); + throw TableSizeError(); } pool_->reset(key_id, dest_normalized_key); if (dest_entry->is_unused()) { @@ -222,14 +275,12 @@ bool HashTable<T>::reset(int64_t key_id, KeyArg dest_key) { } template <typename T> -bool HashTable<T>::find(KeyArg key, int64_t *key_id) { - refresh_table(); +bool HashTableImpl<T>::find(KeyArg key, int64_t *key_id) { const Key normalized_key = Helper<T>::normalize(key); - Table * const table = table_.get(); - const uint64_t id_mask = table->size() - 1; + const uint64_t id_mask = table_->size() - 1; const uint64_t hash_value = Hash<T>()(normalized_key); for (uint64_t id = hash_value; ; ) { - Entry entry = table->get(id & id_mask); + TableEntry entry = table_->get(id & id_mask); if (entry.is_unused()) { // Not found. return false; @@ -255,17 +306,16 @@ bool HashTable<T>::find(KeyArg key, int64_t *key_id) { } template <typename T> -bool HashTable<T>::add(KeyArg key, int64_t *key_id) { - refresh_table(); - // Create a new table if the filling rate of the current table is greater +bool HashTableImpl<T>::add(KeyArg key, int64_t *key_id) { + // Throw an exception if the filling rate of the current table is greater // than 62.5%. const uint64_t table_size = table_->size(); if (header_->num_entries > ((table_size + (table_size / 4)) / 2)) { - rebuild(); + throw TableSizeError(); } const Key normalized_key = Helper<T>::normalize(key); const uint64_t hash_value = Hash<T>()(normalized_key); - Entry *entry; + TableEntry *entry; if (find_key(normalized_key, hash_value, &entry)) { // Found. if (key_id) { @@ -285,11 +335,10 @@ bool HashTable<T>::add(KeyArg key, int64_t *key_id) { } template <typename T> -bool HashTable<T>::remove(KeyArg key) { - refresh_table(); +bool HashTableImpl<T>::remove(KeyArg key) { const Key normalized_key = Helper<T>::normalize(key); const uint64_t hash_value = Hash<T>()(normalized_key); - Entry *entry; + TableEntry *entry; if (!find_key(normalized_key, hash_value, &entry)) { // Not found. return false; @@ -300,27 +349,27 @@ bool HashTable<T>::remove(KeyArg key) { } template <typename T> -bool HashTable<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { - refresh_table(); +bool HashTableImpl<T>::replace(KeyArg src_key, KeyArg dest_key, + int64_t *key_id) { const Key src_normalized_key = Helper<T>::normalize(src_key); const uint64_t src_hash_value = Hash<T>()(src_normalized_key); - Entry *src_entry; + TableEntry *src_entry; if (!find_key(src_normalized_key, src_hash_value, &src_entry)) { // Not found. return false; } const Key dest_normalized_key = Helper<T>::normalize(dest_key); const uint64_t dest_hash_value = Hash<T>()(dest_normalized_key); - Entry *dest_entry; + TableEntry *dest_entry; if (find_key(dest_normalized_key, dest_hash_value, &dest_entry)) { // Found. return false; } - // Create a new table if the filling rate of the current table is greater + // Throw an exception if the filling rate of the current table is greater // than 62.5%. const uint64_t table_size = table_->size(); if (header_->num_entries > ((table_size + (table_size / 4)) / 2)) { - rebuild(); + throw TableSizeError(); } pool_->reset(src_entry->key_id(), dest_normalized_key); if (dest_entry->is_unused()) { @@ -335,61 +384,17 @@ bool HashTable<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { } template <typename T> -void HashTable<T>::defrag() { - refresh_table(); - if (max_key_id() == MAP_MIN_KEY_ID) { - // Nothing to do. - return; - } - rebuild(); - pool_->defrag(0.5); -} - -template <typename T> -void HashTable<T>::truncate() { - refresh_table(); - if (max_key_id() == MAP_MIN_KEY_ID) { - // Nothing to do. - return; - } - // Create an empty table. - std::unique_ptr<Table> new_table( - Table::create(storage_, storage_node_id_, - MIN_TABLE_SIZE, Entry::unused_entry())); - try { - pool_->truncate(); - } catch (...) { - Table::unlink(storage_, new_table->storage_node_id()); - throw; - } - { - // Validate a new table. - Lock lock(&header_->mutex); - header_->table_storage_node_id = new_table->storage_node_id(); - header_->num_entries = 0; - ++header_->table_id; - old_table_.swap(new_table); - table_.swap(old_table_); - table_id_ = header_->table_id; - } - Table::unlink(storage_, old_table_->storage_node_id()); -} - -template <typename T> -void HashTable<T>::create_map(Storage *storage, uint32_t storage_node_id, - const MapOptions &) { +void HashTableImpl<T>::create_impl(Storage *storage, uint32_t storage_node_id, + Pool *pool) { storage_ = storage; - StorageNode storage_node = + StorageNode header_node = storage->create_node(storage_node_id, sizeof(Header)); - storage_node_id_ = storage_node.id(); + storage_node_id_ = header_node.id(); try { - header_ = static_cast<Header *>(storage_node.body()); + header_ = static_cast<Header *>(header_node.body()); *header_ = Header(); - table_.reset(Table::create(storage, storage_node_id_, - MIN_TABLE_SIZE, Entry::unused_entry())); - pool_.reset(KeyPool<T>::create(storage, storage_node_id_)); - header_->table_storage_node_id = table_->storage_node_id(); - header_->pool_storage_node_id = pool_->storage_node_id(); + pool_ = pool; + build_table(); } catch (...) { storage->unlink_node(storage_node_id_); throw; @@ -397,39 +402,32 @@ void HashTable<T>::create_map(Storage *storage, uint32_t storage_node_id, } template <typename T> -void HashTable<T>::open_map(Storage *storage, uint32_t storage_node_id) { +void HashTableImpl<T>::open_impl(Storage *storage, uint32_t storage_node_id, + Pool *pool) { storage_ = storage; - StorageNode storage_node = storage->open_node(storage_node_id); - if (storage_node.size() < sizeof(Header)) { - GRNXX_ERROR() << "invalid format: size = " << storage_node.size() + StorageNode header_node = storage->open_node(storage_node_id); + if (header_node.size() < sizeof(Header)) { + GRNXX_ERROR() << "invalid format: size = " << header_node.size() << ", header_size = " << sizeof(Header); throw LogicError(); } storage_node_id_ = storage_node_id; - header_ = static_cast<Header *>(storage_node.body()); - if (!*header_) { - GRNXX_ERROR() << "wrong format: expected = " << FORMAT_STRING - << ", actual = " << header_->common_header.format(); - throw LogicError(); - } - Lock lock(&header_->mutex); + header_ = static_cast<Header *>(header_node.body()); + pool_ = pool; table_.reset(Table::open(storage, header_->table_storage_node_id)); - pool_.reset(KeyPool<T>::open(storage, header_->pool_storage_node_id)); - table_id_ = header_->table_id; } template <typename T> -HashTableEntry *HashTable<T>::find_key_id(int64_t key_id) { - Table * const table = table_.get(); +TableEntry *HashTableImpl<T>::find_key_id(int64_t key_id) { Key stored_key; - if (!get(key_id, &stored_key)) { + if (!pool_->get(key_id, &stored_key)) { // Not found. return nullptr; } - const uint64_t id_mask = table->size() - 1; + const uint64_t id_mask = table_->size() - 1; const uint64_t hash_value = Hash<T>()(stored_key); for (uint64_t id = hash_value; ; ) { - Entry &entry = table->get_value(id & id_mask); + TableEntry &entry = table_->get_value(id & id_mask); if (entry.key_id() == key_id) { // Found. return &entry; @@ -444,12 +442,12 @@ HashTableEntry *HashTable<T>::find_key_id(int64_t key_id) { } template <typename T> -bool HashTable<T>::find_key(KeyArg key, uint64_t hash_value, Entry **entry) { - Table * const table = table_.get(); +bool HashTableImpl<T>::find_key(KeyArg key, uint64_t hash_value, + TableEntry **entry) { *entry = nullptr; - const uint64_t id_mask = table->size() - 1; + const uint64_t id_mask = table_->size() - 1; for (uint64_t id = hash_value; ; ) { - Entry &this_entry = table->get_value(id & id_mask); + TableEntry &this_entry = table_->get_value(id & id_mask); if (this_entry.is_unused()) { // Not found. if (!*entry) { @@ -479,67 +477,325 @@ bool HashTable<T>::find_key(KeyArg key, uint64_t hash_value, Entry **entry) { } template <typename T> -void HashTable<T>::rebuild() { +void HashTableImpl<T>::build_table() { // Create a new table. - uint64_t new_size = num_keys() * 2; + uint64_t new_size = pool_->num_keys() * 2; if (new_size < MIN_TABLE_SIZE) { new_size = MIN_TABLE_SIZE; } new_size = 2ULL << bit_scan_reverse(new_size - 1); - std::unique_ptr<Table> new_table( - Table::create(storage_, storage_node_id_, - new_size, Entry::unused_entry())); - try { - // Copy entries from the current table to the new table. - const uint64_t new_id_mask = new_size - 1; - int64_t key_id; - for (key_id = MAP_MIN_KEY_ID; key_id <= max_key_id(); ++key_id) { - Key stored_key; - if (!pool_->get(key_id, &stored_key)) { - continue; - } - const uint64_t hash_value = Hash<T>()(stored_key); - for (uint64_t id = hash_value; ; id = rehash(id)) { - Entry &entry = new_table->get_value(id & new_id_mask); - if (entry.is_unused()) { - entry.set(key_id, hash_value); - break; - } + table_.reset(Table::create(storage_, storage_node_id_, + new_size, TableEntry::unused_entry())); + // Add entries associated with keys in a pool. + const uint64_t new_id_mask = new_size - 1; + const int64_t max_key_id = pool_->max_key_id(); + for (int64_t key_id = MAP_MIN_KEY_ID; key_id <= max_key_id; ++key_id) { + Key stored_key; + if (!pool_->get(key_id, &stored_key)) { + continue; + } + const uint64_t hash_value = Hash<T>()(stored_key); + for (uint64_t id = hash_value; ; id = rehash(id)) { + TableEntry &entry = table_->get_value(id & new_id_mask); + if (entry.is_unused()) { + entry.set(key_id, hash_value); + break; } } + ++header_->num_entries; + } + header_->table_storage_node_id = table_->storage_node_id(); +} + +struct HashTableHeader { + CommonHeader common_header; + uint64_t pool_id; + uint64_t impl_id; + uint32_t pool_storage_node_id; + uint32_t impl_storage_node_id; + Mutex mutex; + + // Initialize the member variables. + HashTableHeader(); + + // Return true iff the header seems to be correct. + explicit operator bool() const; +}; + +HashTableHeader::HashTableHeader() + : common_header(FORMAT_STRING, MAP_HASH_TABLE), + pool_id(0), + impl_id(0), + pool_storage_node_id(STORAGE_INVALID_NODE_ID), + impl_storage_node_id(STORAGE_INVALID_NODE_ID), + mutex() {} + +HashTableHeader::operator bool() const { + return common_header.format() == FORMAT_STRING; +} + +template <typename T> +HashTable<T>::HashTable() + : storage_(nullptr), + storage_node_id_(STORAGE_INVALID_NODE_ID), + header_(nullptr), + pool_(), + impl_(), + queue_(), + pool_id_(0), + impl_id_(0), + clock_() {} + +template <typename T> +HashTable<T>::~HashTable() {} + +template <typename T> +HashTable<T> *HashTable<T>::create(Storage *storage, uint32_t storage_node_id, + const MapOptions &options) { + std::unique_ptr<HashTable> map(new (std::nothrow) HashTable); + if (!map) { + GRNXX_ERROR() << "new grnxx::map::HashTable failed"; + throw MemoryError(); + } + map->create_map(storage, storage_node_id, options); + return map.release(); +} + +template <typename T> +HashTable<T> *HashTable<T>::open(Storage *storage, uint32_t storage_node_id) { + std::unique_ptr<HashTable> map(new (std::nothrow) HashTable); + if (!map) { + GRNXX_ERROR() << "new grnxx::map::HashTable failed"; + throw MemoryError(); + } + map->open_map(storage, storage_node_id); + return map.release(); +} + +template <typename T> +uint32_t HashTable<T>::storage_node_id() const { + return storage_node_id_; +} + +template <typename T> +MapType HashTable<T>::type() const { + return MAP_HASH_TABLE; +} + +template <typename T> +int64_t HashTable<T>::max_key_id() { + refresh_if_possible(); + return impl_->max_key_id(); +} + +template <typename T> +uint64_t HashTable<T>::num_keys() { + refresh_if_possible(); + return impl_->num_keys(); +} + +template <typename T> +bool HashTable<T>::get(int64_t key_id, Key *key) { + refresh_if_possible(); + return impl_->get(key_id, key); +} + +template <typename T> +bool HashTable<T>::unset(int64_t key_id) { + refresh_if_possible(); + return impl_->unset(key_id); +} + +template <typename T> +bool HashTable<T>::reset(int64_t key_id, KeyArg dest_key) { + refresh_if_possible(); + try { + return impl_->reset(key_id, dest_key); + } catch (TableSizeError) { + rebuild_table(); + return impl_->reset(key_id, dest_key); + } +} + +template <typename T> +bool HashTable<T>::find(KeyArg key, int64_t *key_id) { + refresh_if_possible(); + return impl_->find(key, key_id); +} + +template <typename T> +bool HashTable<T>::add(KeyArg key, int64_t *key_id) { + refresh_if_possible(); + try { + return impl_->add(key, key_id); + } catch (TableSizeError) { + rebuild_table(); + return impl_->add(key, key_id); + } +} + +template <typename T> +bool HashTable<T>::remove(KeyArg key) { + refresh_if_possible(); + return impl_->remove(key); +} + +template <typename T> +bool HashTable<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { + refresh_if_possible(); + try { + return impl_->replace(src_key, dest_key, key_id); + } catch (TableSizeError) { + rebuild_table(); + return impl_->replace(src_key, dest_key, key_id); + } +} + +template <typename T> +void HashTable<T>::rebuild_table() { + std::unique_ptr<Impl> new_impl( + Impl::create(storage_, storage_node_id_, pool_.get())); + { + // Validate a new impl. + Lock lock(&header_->mutex); + header_->impl_storage_node_id = new_impl->storage_node_id(); + ++header_->impl_id; + impl_.swap(new_impl); + impl_id_ = header_->impl_id; + } + Impl::unlink(storage_, new_impl->storage_node_id()); + try { + queue_.push(QueueEntry{ nullptr, std::move(new_impl), clock_.now() }); + } catch (const std::exception &exception) { + GRNXX_ERROR() << "std::queue::push() failed"; + throw StandardError(exception); + } +} + +template <typename T> +void HashTable<T>::defrag() { + refresh_if_possible(); + pool_->defrag(); + rebuild_table(); +} + +template <typename T> +void HashTable<T>::truncate() { + refresh_if_possible(); + std::unique_ptr<Pool> new_pool(Pool::create(storage_, storage_node_id_)); + std::unique_ptr<Impl> new_impl; + try { + new_impl.reset(Impl::create(storage_, storage_node_id_, new_pool.get())); } catch (...) { - Table::unlink(storage_, new_table->storage_node_id()); + Pool::unlink(storage_, new_pool->storage_node_id()); throw; } { - // Validate a new table. + // Validate a new impl and a new pool. Lock lock(&header_->mutex); - header_->table_storage_node_id = new_table->storage_node_id(); - header_->num_entries = num_keys(); - ++header_->table_id; - old_table_.swap(new_table); - table_.swap(old_table_); - table_id_ = header_->table_id; + header_->pool_storage_node_id = new_pool->storage_node_id(); + header_->impl_storage_node_id = new_impl->storage_node_id(); + ++header_->pool_id; + ++header_->impl_id; + pool_.swap(new_pool); + impl_.swap(new_impl); + pool_id_ = header_->pool_id; + impl_id_ = header_->impl_id; + } + Pool::unlink(storage_, new_pool->storage_node_id()); + Impl::unlink(storage_, new_impl->storage_node_id()); + try { + queue_.push(QueueEntry{ std::move(new_pool), std::move(new_impl), + clock_.now() }); + } catch (const std::exception &exception) { + GRNXX_ERROR() << "std::queue::push() failed"; + throw StandardError(exception); + } +} + +template <typename T> +void HashTable<T>::create_map(Storage *storage, uint32_t storage_node_id, + const MapOptions &) { + storage_ = storage; + StorageNode storage_node = + storage->create_node(storage_node_id, sizeof(Header)); + storage_node_id_ = storage_node.id(); + try { + header_ = static_cast<Header *>(storage_node.body()); + *header_ = Header(); + pool_.reset(Pool::create(storage, storage_node_id_)); + impl_.reset(Impl::create(storage, storage_node_id_, pool_.get())); + header_->pool_storage_node_id = pool_->storage_node_id(); + header_->impl_storage_node_id = impl_->storage_node_id(); + pool_id_ = ++header_->pool_id; + impl_id_ = ++header_->impl_id; + } catch (...) { + storage->unlink_node(storage_node_id_); + throw; + } +} + +template <typename T> +void HashTable<T>::open_map(Storage *storage, uint32_t storage_node_id) { + storage_ = storage; + StorageNode storage_node = storage->open_node(storage_node_id); + if (storage_node.size() < sizeof(Header)) { + GRNXX_ERROR() << "invalid format: size = " << storage_node.size() + << ", header_size = " << sizeof(Header); + throw LogicError(); + } + storage_node_id_ = storage_node_id; + header_ = static_cast<Header *>(storage_node.body()); + if (!*header_) { + GRNXX_ERROR() << "wrong format: expected = " << FORMAT_STRING + << ", actual = " << header_->common_header.format(); + throw LogicError(); } - Table::unlink(storage_, old_table_->storage_node_id()); } template <typename T> -uint64_t HashTable<T>::rehash(uint64_t hash) const { - return hash + 1; +void HashTable<T>::refresh_if_possible() { + if (impl_id_ != header_->impl_id) { + refresh(); + } } template <typename T> -void HashTable<T>::refresh_table() { - if (table_id_ != header_->table_id) { - Lock lock(&header_->mutex); - if (table_id_ != header_->table_id) { - std::unique_ptr<Table> new_table( - Table::open(storage_, header_->table_storage_node_id)); - old_table_.swap(new_table); - table_.swap(old_table_); - table_id_ = header_->table_id; - } +void HashTable<T>::refresh() { + Lock lock(&header_->mutex); + if (pool_id_ != header_->pool_id) { + refresh_pool(); + } + if (impl_id_ != header_->impl_id) { + refresh_impl(); + } +} + +template <typename T> +void HashTable<T>::refresh_pool() { + std::unique_ptr<Pool> new_pool( + Pool::open(storage_, header_->pool_storage_node_id)); + pool_.swap(new_pool); + pool_id_ = header_->pool_id; + try { + queue_.push(QueueEntry{ std::move(new_pool), nullptr, clock_.now() }); + } catch (const std::exception &exception) { + GRNXX_ERROR() << "std::queue::push() failed"; + throw StandardError(exception); + } +} + +template <typename T> +void HashTable<T>::refresh_impl() { + std::unique_ptr<Impl> new_impl( + Impl::open(storage_, header_->impl_storage_node_id, pool_.get())); + impl_.swap(new_impl); + impl_id_ = header_->impl_id; + try { + queue_.push(QueueEntry{ nullptr, std::move(new_impl), clock_.now() }); + } catch (const std::exception &exception) { + GRNXX_ERROR() << "std::queue::push() failed"; + throw StandardError(exception); } } Modified: lib/grnxx/map/hash_table.hpp (+30 -28) =================================================================== --- lib/grnxx/map/hash_table.hpp 2013-08-20 15:52:37 +0900 (ec6fd74) +++ lib/grnxx/map/hash_table.hpp 2013-08-20 18:27:20 +0900 (ca388ba) @@ -1,5 +1,5 @@ /* - Copyright (C) 2013 Brazil, Inc. + 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 @@ -21,9 +21,12 @@ #include "grnxx/features.hpp" #include <memory> +#include <queue> #include "grnxx/array.hpp" #include "grnxx/map.hpp" +#include "grnxx/periodic_clock.hpp" +#include "grnxx/time.hpp" #include "grnxx/types.hpp" namespace grnxx { @@ -32,16 +35,25 @@ class Storage; namespace map { -template <typename T> class KeyPool; +template <typename T> class Pool; + +template <typename T> class HashTableImpl; struct HashTableHeader; -class HashTableEntry; + +template <typename T> +struct HashTableQueueEntry { + std::unique_ptr<Pool<T>> pool; + std::unique_ptr<HashTableImpl<T>> impl; + Time time; +}; template <typename T> class HashTable : public Map<T> { - using Header = HashTableHeader; - using Entry = HashTableEntry; - using Table = Array<Entry>; + using Header = HashTableHeader; + using Impl = HashTableImpl<T>; + using Pool = Pool<T>; + using QueueEntry = HashTableQueueEntry<T>; public: using Key = typename Map<T>::Key; @@ -78,33 +90,23 @@ class HashTable : public Map<T> { Storage *storage_; uint32_t storage_node_id_; Header *header_; - std::unique_ptr<Table> table_; - std::unique_ptr<Table> old_table_; - std::unique_ptr<KeyPool<T>> pool_; - uint64_t table_id_; + std::unique_ptr<Pool> pool_; + std::unique_ptr<Impl> impl_; + std::queue<QueueEntry> queue_; + uint64_t pool_id_; + uint64_t impl_id_; + PeriodicClock clock_; void create_map(Storage *storage, uint32_t storage_node_id, const MapOptions &options); void open_map(Storage *storage, uint32_t storage_node_id); - // Search a hash table for a key ID. - // On success, return a pointer to a matched entry. - // On failure, return nullptr. - Entry *find_key_id(int64_t key_id); - // Search a hash table for a key. - // On success, assign a pointer to a matched entry to "*entry" and return - // true. - // On failure, assign a pointer to the first unused or removed entry to - // "*entry" and return false. - bool find_key(KeyArg key, uint64_t hash_value, Entry **entry); - - // Rebuild the hash table. - void rebuild(); - // Move to the next entry. - uint64_t rehash(uint64_t hash) const; - - // Refresh "table_" if it is old. - void refresh_table(); + void rebuild_table(); + + inline void refresh_if_possible(); + void refresh(); + void refresh_pool(); + void refresh_impl(); }; } // namespace map -------------- next part -------------- HTML����������������������������...Download