susumu.yata
null+****@clear*****
Mon Aug 19 18:28:21 JST 2013
susumu.yata 2013-08-19 18:28:21 +0900 (Mon, 19 Aug 2013) New Revision: 099d7263b5e29d19e2fd80c57988b550e45bbcd4 https://github.com/groonga/grnxx/commit/099d7263b5e29d19e2fd80c57988b550e45bbcd4 Message: Update grnxx::map::ArrayMap to use grnxx::map::Pool. Also, remove "const" from max_key_id() and num_keys(). Remove the argument of defrag(). Modified files: lib/grnxx/map.cpp lib/grnxx/map.hpp lib/grnxx/map/array_map.cpp lib/grnxx/map/array_map.hpp lib/grnxx/map/double_array.cpp lib/grnxx/map/double_array.hpp lib/grnxx/map/hash_table.cpp lib/grnxx/map/hash_table.hpp lib/grnxx/map/patricia.cpp lib/grnxx/map/patricia.hpp test/test_map.cpp Modified: lib/grnxx/map.cpp (+1 -1) =================================================================== --- lib/grnxx/map.cpp 2013-08-19 14:13:13 +0900 (c62e512) +++ lib/grnxx/map.cpp 2013-08-19 18:28:21 +0900 (8a2f65f) @@ -243,7 +243,7 @@ bool Map<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id, } template <typename T> -void Map<T>::defrag(double) { +void Map<T>::defrag() { GRNXX_ERROR() << "invalid operation"; throw LogicError(); } Modified: lib/grnxx/map.hpp (+3 -3) =================================================================== --- lib/grnxx/map.hpp 2013-08-19 14:13:13 +0900 (b96baeb) +++ lib/grnxx/map.hpp 2013-08-19 18:28:21 +0900 (36e6fa9) @@ -81,9 +81,9 @@ class Map { } // Return the maximum key ID ever used. // The return value can be a negative value iff the map is empty. - virtual int64_t max_key_id() const = 0; + virtual int64_t max_key_id() = 0; // Return the number of keys. - virtual uint64_t num_keys() const = 0; + virtual uint64_t num_keys() = 0; // Get a key associated with "key_id" and return true on success. // Assign the found key to "*key" iff "key" != nullptr. @@ -122,7 +122,7 @@ class Map { Key *key = nullptr); // Defrag components. - virtual void defrag(double usage_rate_threshold); + virtual void defrag(); // Remove all the keys in "*this" and return true on success. virtual void truncate(); Modified: lib/grnxx/map/array_map.cpp (+111 -17) =================================================================== --- lib/grnxx/map/array_map.cpp 2013-08-19 14:13:13 +0900 (dad9f7e) +++ lib/grnxx/map/array_map.cpp 2013-08-19 18:28:21 +0900 (b1b0f9d) @@ -22,10 +22,11 @@ #include "grnxx/bytes.hpp" #include "grnxx/exception.hpp" #include "grnxx/geo_point.hpp" +#include "grnxx/lock.hpp" #include "grnxx/logger.hpp" #include "grnxx/map/common_header.hpp" #include "grnxx/map/helper.hpp" -#include "grnxx/map/key_pool.hpp" +#include "grnxx/map/pool.hpp" #include "grnxx/storage.hpp" namespace grnxx { @@ -39,6 +40,8 @@ constexpr char FORMAT_STRING[] = "grnxx::map::ArrayMap"; struct ArrayMapHeader { CommonHeader common_header; uint32_t pool_storage_node_id; + uint64_t pool_id; + Mutex mutex; // Initialize the member variables. ArrayMapHeader(); @@ -49,7 +52,8 @@ struct ArrayMapHeader { ArrayMapHeader::ArrayMapHeader() : common_header(FORMAT_STRING, MAP_ARRAY), - pool_storage_node_id(STORAGE_INVALID_NODE_ID) {} + pool_storage_node_id(STORAGE_INVALID_NODE_ID), + pool_id(0) {} ArrayMapHeader::operator bool() const { return common_header.format() == FORMAT_STRING; @@ -60,7 +64,10 @@ ArrayMap<T>::ArrayMap() : storage_(nullptr), storage_node_id_(STORAGE_INVALID_NODE_ID), header_(nullptr), - pool_() {} + pool_(), + queue_(), + pool_id_(0), + clock_() {} template <typename T> ArrayMap<T>::~ArrayMap() {} @@ -99,27 +106,40 @@ MapType ArrayMap<T>::type() const { } template <typename T> -int64_t ArrayMap<T>::max_key_id() const { +int64_t ArrayMap<T>::max_key_id() { + refresh_if_possible(); return pool_->max_key_id(); } template <typename T> -uint64_t ArrayMap<T>::num_keys() const { +uint64_t ArrayMap<T>::num_keys() { + refresh_if_possible(); return pool_->num_keys(); } template <typename T> bool ArrayMap<T>::get(int64_t key_id, Key *key) { - if ((key_id < MAP_MIN_KEY_ID) || (key_id > max_key_id())) { + refresh_if_possible(); + Pool * const pool = pool_.get(); + if ((key_id < MAP_MIN_KEY_ID) || (key_id > pool->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 ArrayMap<T>::unset(int64_t key_id) { + refresh_if_possible(); + if ((key_id < MAP_MIN_KEY_ID) || (key_id > pool_->max_key_id())) { + // Out of range. + return false; + } if (!pool_->get_bit(key_id)) { + // Not found. return false; } pool_->unset(key_id); @@ -128,7 +148,12 @@ bool ArrayMap<T>::unset(int64_t key_id) { template <typename T> bool ArrayMap<T>::reset(int64_t key_id, KeyArg dest_key) { - if (!get(key_id)) { + refresh_if_possible(); + if ((key_id < MAP_MIN_KEY_ID) || (key_id > pool_->max_key_id())) { + // Out of range. + return false; + } + if (!pool_->get_bit(key_id)) { // Not found. return false; } @@ -142,10 +167,13 @@ bool ArrayMap<T>::reset(int64_t key_id, KeyArg dest_key) { template <typename T> bool ArrayMap<T>::find(KeyArg key, int64_t *key_id) { + refresh_if_possible(); + Pool * const pool = pool_.get(); const Key normalized_key = map::Helper<T>::normalize(key); - for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id(); ++i) { + const int64_t max_key_id = pool->max_key_id(); + for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id; ++i) { Key stored_key; - if (pool_->get(i, &stored_key)) { + if (pool->get(i, &stored_key)) { if (Helper<T>::equal_to(normalized_key, stored_key)) { // Found. if (key_id) { @@ -160,8 +188,10 @@ bool ArrayMap<T>::find(KeyArg key, int64_t *key_id) { template <typename T> bool ArrayMap<T>::add(KeyArg key, int64_t *key_id) { + refresh_if_possible(); const Key normalized_key = Helper<T>::normalize(key); - for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id(); ++i) { + const int64_t max_key_id = pool_->max_key_id(); + for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id; ++i) { Key stored_key; if (pool_->get(i, &stored_key)) { if (Helper<T>::equal_to(normalized_key, stored_key)) { @@ -183,6 +213,7 @@ bool ArrayMap<T>::add(KeyArg key, int64_t *key_id) { template <typename T> bool ArrayMap<T>::remove(KeyArg key) { + refresh_if_possible(); int64_t key_id; if (!find(key, &key_id)) { // Not found. @@ -194,10 +225,12 @@ bool ArrayMap<T>::remove(KeyArg key) { template <typename T> bool ArrayMap<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { + refresh_if_possible(); const Key normalized_src_key = Helper<T>::normalize(src_key); 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) { + const int64_t max_key_id = pool_->max_key_id(); + for (int64_t i = MAP_MIN_KEY_ID; i <= max_key_id; ++i) { Key stored_key; if (pool_->get(i, &stored_key)) { if (Helper<T>::equal_to(normalized_src_key, stored_key)) { @@ -222,13 +255,48 @@ bool ArrayMap<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { } template <typename T> -void ArrayMap<T>::defrag(double usage_rate_threshold) { - pool_->defrag(usage_rate_threshold); +void ArrayMap<T>::defrag() { + refresh_if_possible(); + pool_->defrag(); +} + +template <typename T> +void ArrayMap<T>::sweep(Duration lifetime) { + refresh_if_possible(); + const Time threshold = clock_.now() - lifetime; + while (!queue_.empty()) { + QueueEntry &queue_entry = queue_.front(); + if (queue_entry.time <= threshold) { + queue_.pop(); + } + } + pool_->sweep(lifetime); } template <typename T> void ArrayMap<T>::truncate() { - pool_->truncate(); + refresh_if_possible(); + if (pool_->max_key_id() == 0) { + // Nothing to do. + return; + } + std::unique_ptr<Pool> new_pool(Pool::create(storage_, storage_node_id_)); + const uint32_t old_pool_storage_node_id = pool_->storage_node_id(); + { + // Validate a new pool. + Lock lock(&header_->mutex); + header_->pool_storage_node_id = new_pool->storage_node_id(); + ++header_->pool_id; + pool_.swap(new_pool); + pool_id_ = header_->pool_id; + } + Pool::unlink(storage_, old_pool_storage_node_id); + try { + queue_.push(QueueEntry{ std::move(new_pool), clock_.now() }); + } catch (const std::exception &exception) { + GRNXX_ERROR() << "std::queue::push() failed"; + throw StandardError(exception); + } } template <typename T> @@ -241,7 +309,7 @@ void ArrayMap<T>::create_map(Storage *storage, uint32_t storage_node_id, try { header_ = static_cast<Header *>(storage_node.body()); *header_ = Header(); - pool_.reset(KeyPool<T>::create(storage, storage_node_id_)); + pool_.reset(Pool::create(storage, storage_node_id_)); header_->pool_storage_node_id = pool_->storage_node_id(); } catch (...) { storage->unlink_node(storage_node_id_); @@ -265,7 +333,33 @@ void ArrayMap<T>::open_map(Storage *storage, uint32_t storage_node_id) { << ", actual = " << header_->common_header.format(); throw LogicError(); } - pool_.reset(KeyPool<T>::open(storage, header_->pool_storage_node_id)); + Lock lock(&header_->mutex); + pool_.reset(Pool::open(storage, header_->pool_storage_node_id)); + pool_id_ = header_->pool_id; +} + +template <typename T> +void ArrayMap<T>::refresh_if_possible() { + if (pool_id_ != header_->pool_id) { + refresh(); + } +} + +template <typename T> +void ArrayMap<T>::refresh() { + Lock lock(&header_->mutex); + if (pool_id_ != header_->pool_id) { + 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), clock_.now() }); + } catch (const std::exception &exception) { + GRNXX_ERROR() << "std::queue::push() failed"; + throw StandardError(exception); + } + } } template class ArrayMap<int8_t>; Modified: lib/grnxx/map/array_map.hpp (+27 -7) =================================================================== --- lib/grnxx/map/array_map.hpp 2013-08-19 14:13:13 +0900 (5c6ef4a) +++ lib/grnxx/map/array_map.hpp 2013-08-19 18:28:21 +0900 (eeb9b3b) @@ -21,8 +21,13 @@ #include "grnxx/features.hpp" #include <memory> +#include <queue> +#include "grnxx/duration.hpp" #include "grnxx/map.hpp" +#include "grnxx/mutex.hpp" +#include "grnxx/periodic_clock.hpp" +#include "grnxx/time.hpp" #include "grnxx/types.hpp" namespace grnxx { @@ -31,16 +36,24 @@ class Storage; namespace map { -template <typename T> class KeyPool; +template <typename T> class Pool; struct ArrayMapHeader; template <typename T> +struct ArrayMapQueueEntry { + std::unique_ptr<Pool<T>> pool; + Time time; +}; + +template <typename T> class ArrayMap : public Map<T> { - using Header = ArrayMapHeader; + using Header = ArrayMapHeader; + using Pool = map::Pool<T>; + using QueueEntry = ArrayMapQueueEntry<T>; public: - using Key = typename Map<T>::Key; + using Key = typename Map<T>::Key; using KeyArg = typename Map<T>::KeyArg; using Cursor = typename Map<T>::Cursor; @@ -54,8 +67,8 @@ class ArrayMap : public Map<T> { uint32_t storage_node_id() const; MapType type() const; - int64_t max_key_id() const; - uint64_t num_keys() const; + int64_t max_key_id(); + uint64_t num_keys(); bool get(int64_t key_id, Key *key = nullptr); bool unset(int64_t key_id); @@ -66,7 +79,8 @@ class ArrayMap : public Map<T> { bool remove(KeyArg key); bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); - void defrag(double usage_rate_threshold); + void defrag(); + void sweep(Duration lifetime); void truncate(); @@ -74,11 +88,17 @@ class ArrayMap : public Map<T> { Storage *storage_; uint32_t storage_node_id_; Header *header_; - std::unique_ptr<KeyPool<T>> pool_; + std::unique_ptr<Pool> pool_; + std::queue<QueueEntry> queue_; + uint64_t pool_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); + + inline void refresh_if_possible(); + void refresh(); }; } // namespace map Modified: lib/grnxx/map/double_array.cpp (+6 -6) =================================================================== --- lib/grnxx/map/double_array.cpp 2013-08-19 14:13:13 +0900 (a73f307) +++ lib/grnxx/map/double_array.cpp 2013-08-19 18:28:21 +0900 (4e6824d) @@ -364,10 +364,10 @@ class DoubleArrayImpl { return storage_node_id_; } - int64_t max_key_id() const { + int64_t max_key_id() { return pool_->max_key_id(); } - uint64_t num_keys() const { + uint64_t num_keys() { return pool_->num_keys(); } @@ -1262,11 +1262,11 @@ MapType DoubleArray<Bytes>::type() const { return MAP_DOUBLE_ARRAY; } -int64_t DoubleArray<Bytes>::max_key_id() const { +int64_t DoubleArray<Bytes>::max_key_id() { return pool_->max_key_id(); } -uint64_t DoubleArray<Bytes>::num_keys() const { +uint64_t DoubleArray<Bytes>::num_keys() { return pool_->num_keys(); } @@ -1303,7 +1303,7 @@ bool DoubleArray<Bytes>::replace(KeyArg src_key, KeyArg dest_key, return impl_->replace(src_key, dest_key, key_id); } -void DoubleArray<Bytes>::defrag(double usage_rate_threshold) { +void DoubleArray<Bytes>::defrag() { refresh_impl(); if (max_key_id() == MAP_MIN_KEY_ID) { // Nothing to do. @@ -1322,7 +1322,7 @@ void DoubleArray<Bytes>::defrag(double usage_rate_threshold) { impl_id_ = header_->impl_id; } Impl::unlink(storage_, old_impl_->storage_node_id()); - pool_->defrag(usage_rate_threshold); + pool_->defrag(0.5); } void DoubleArray<Bytes>::truncate() { Modified: lib/grnxx/map/double_array.hpp (+3 -3) =================================================================== --- lib/grnxx/map/double_array.hpp 2013-08-19 14:13:13 +0900 (020ee8f) +++ lib/grnxx/map/double_array.hpp 2013-08-19 18:28:21 +0900 (e7569e8) @@ -68,8 +68,8 @@ class DoubleArray<Bytes> : public Map<Bytes> { uint32_t storage_node_id() const; MapType type() const; - int64_t max_key_id() const; - uint64_t num_keys() const; + int64_t max_key_id(); + uint64_t num_keys(); bool get(int64_t key_id, Key *key = nullptr); bool unset(int64_t key_id); @@ -80,7 +80,7 @@ class DoubleArray<Bytes> : public Map<Bytes> { bool remove(KeyArg key); bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); - void defrag(double usage_rate_threshold); + void defrag(); void truncate(); Modified: lib/grnxx/map/hash_table.cpp (+4 -4) =================================================================== --- lib/grnxx/map/hash_table.cpp 2013-08-19 14:13:13 +0900 (72d30d5) +++ lib/grnxx/map/hash_table.cpp 2013-08-19 18:28:21 +0900 (f00942b) @@ -160,12 +160,12 @@ MapType HashTable<T>::type() const { } template <typename T> -int64_t HashTable<T>::max_key_id() const { +int64_t HashTable<T>::max_key_id() { return pool_->max_key_id(); } template <typename T> -uint64_t HashTable<T>::num_keys() const { +uint64_t HashTable<T>::num_keys() { return pool_->num_keys(); } @@ -335,14 +335,14 @@ bool HashTable<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { } template <typename T> -void HashTable<T>::defrag(double usage_rate_threshold) { +void HashTable<T>::defrag() { refresh_table(); if (max_key_id() == MAP_MIN_KEY_ID) { // Nothing to do. return; } rebuild(); - pool_->defrag(usage_rate_threshold); + pool_->defrag(0.5); } template <typename T> Modified: lib/grnxx/map/hash_table.hpp (+3 -3) =================================================================== --- lib/grnxx/map/hash_table.hpp 2013-08-19 14:13:13 +0900 (2565423) +++ lib/grnxx/map/hash_table.hpp 2013-08-19 18:28:21 +0900 (ec6fd74) @@ -58,8 +58,8 @@ class HashTable : public Map<T> { uint32_t storage_node_id() const; MapType type() const; - int64_t max_key_id() const; - uint64_t num_keys() const; + int64_t max_key_id(); + uint64_t num_keys(); bool get(int64_t key_id, Key *key = nullptr); bool unset(int64_t key_id); @@ -70,7 +70,7 @@ class HashTable : public Map<T> { bool remove(KeyArg key); bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); - void defrag(double usage_rate_threshold); + void defrag(); void truncate(); Modified: lib/grnxx/map/patricia.cpp (+8 -8) =================================================================== --- lib/grnxx/map/patricia.cpp 2013-08-19 14:13:13 +0900 (12467a3) +++ lib/grnxx/map/patricia.cpp 2013-08-19 18:28:21 +0900 (815409c) @@ -254,12 +254,12 @@ MapType Patricia<T>::type() const { } template <typename T> -int64_t Patricia<T>::max_key_id() const { +int64_t Patricia<T>::max_key_id() { return pool_->max_key_id(); } template <typename T> -uint64_t Patricia<T>::num_keys() const { +uint64_t Patricia<T>::num_keys() { return pool_->num_keys(); } @@ -612,14 +612,14 @@ bool Patricia<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { } template <typename T> -void Patricia<T>::defrag(double usage_rate_threshold) { +void Patricia<T>::defrag() { refresh_nodes(); if (max_key_id() == MAP_MIN_KEY_ID) { // Nothing to do. return; } defrag_nodes(); - pool_->defrag(usage_rate_threshold); + pool_->defrag(0.5); } template <typename T> @@ -880,11 +880,11 @@ MapType Patricia<Bytes>::type() const { return MAP_PATRICIA; } -int64_t Patricia<Bytes>::max_key_id() const { +int64_t Patricia<Bytes>::max_key_id() { return pool_->max_key_id(); } -uint64_t Patricia<Bytes>::num_keys() const { +uint64_t Patricia<Bytes>::num_keys() { return pool_->num_keys(); } @@ -1604,14 +1604,14 @@ bool Patricia<Bytes>::find_longest_prefix_match(KeyArg query, int64_t *key_id, } } -void Patricia<Bytes>::defrag(double usage_rate_threshold) { +void Patricia<Bytes>::defrag() { refresh_nodes(); if (max_key_id() == MAP_MIN_KEY_ID) { // Nothing to do. return; } defrag_nodes(); - pool_->defrag(usage_rate_threshold); + pool_->defrag(0.5); } void Patricia<Bytes>::truncate() { Modified: lib/grnxx/map/patricia.hpp (+6 -6) =================================================================== --- lib/grnxx/map/patricia.hpp 2013-08-19 14:13:13 +0900 (1e6235c) +++ lib/grnxx/map/patricia.hpp 2013-08-19 18:28:21 +0900 (9e08d5a) @@ -62,8 +62,8 @@ class Patricia : public Map<T> { uint32_t storage_node_id() const; MapType type() const; - int64_t max_key_id() const; - uint64_t num_keys() const; + int64_t max_key_id(); + uint64_t num_keys(); bool get(int64_t key_id, Key *key = nullptr); bool unset(int64_t key_id); @@ -74,7 +74,7 @@ class Patricia : public Map<T> { bool remove(KeyArg key); bool replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id = nullptr); - void defrag(double usage_rate_threshold); + void defrag(); void truncate(); @@ -128,8 +128,8 @@ class Patricia<Bytes> : public Map<Bytes> { uint32_t storage_node_id() const; MapType type() const; - int64_t max_key_id() const; - uint64_t num_keys() const; + int64_t max_key_id(); + uint64_t num_keys(); bool get(int64_t key_id, Key *key = nullptr); bool unset(int64_t key_id); @@ -143,7 +143,7 @@ class Patricia<Bytes> : public Map<Bytes> { bool find_longest_prefix_match(KeyArg query, int64_t *key_id = nullptr, Key *key = nullptr); - void defrag(double usage_rate_threshold); + void defrag(); void truncate(); Modified: test/test_map.cpp (+1 -1) =================================================================== --- test/test_map.cpp 2013-08-19 14:13:13 +0900 (a961913) +++ test/test_map.cpp 2013-08-19 18:28:21 +0900 (fa5aede) @@ -566,7 +566,7 @@ void test_map_defrag(grnxx::MapType map_type) { for (std::uint64_t i = 0; i < MAP_NUM_KEYS; ++i) { assert(map->add(keys[i])); } - map->defrag(0.5); + map->defrag(); assert(map->max_key_id() == (MAP_NUM_KEYS - 1)); assert(map->num_keys() == (MAP_NUM_KEYS)); for (std::uint64_t i = 0; i < MAP_NUM_KEYS; ++i) { -------------- next part -------------- HTML����������������������������...Download