susumu.yata
null+****@clear*****
Fri Jun 14 12:34:13 JST 2013
susumu.yata 2013-06-14 12:34:13 +0900 (Fri, 14 Jun 2013) New Revision: e3aba7cd0be490c99fdfd885a69733aa1ca87a86 https://github.com/groonga/grnxx/commit/e3aba7cd0be490c99fdfd885a69733aa1ca87a86 Message: Update grnxx::map::HashTable to use grnxx::map::KeyStore. Removed files: lib/grnxx/map/hash_table/bit_array.hpp lib/grnxx/map/hash_table/key_array.hpp lib/grnxx/map/hash_table/link_array.hpp Modified files: lib/grnxx/map/hash_table.cpp lib/grnxx/map/hash_table.hpp lib/grnxx/map/hash_table/Makefile.am lib/grnxx/map/hash_table/dummy.cpp lib/grnxx/map/hash_table/header.cpp lib/grnxx/map/hash_table/header.hpp lib/grnxx/map/hash_table/key_id_array.hpp Modified: lib/grnxx/map/hash_table.cpp (+23 -108) =================================================================== --- lib/grnxx/map/hash_table.cpp 2013-06-14 11:51:15 +0900 (0d42811) +++ lib/grnxx/map/hash_table.cpp 2013-06-14 12:34:13 +0900 (537e839) @@ -35,7 +35,6 @@ namespace map { template <typename T> using Hash = hash_table::Hash<T>; -using hash_table::INVALID_LINK; template <typename T> HashTable<T>::HashTable() @@ -44,9 +43,7 @@ HashTable<T>::HashTable() header_(nullptr), key_ids_(), old_key_ids_(), - keys_(), - bits_(), - links_() {} + keys_() {} template <typename T> HashTable<T>::~HashTable() {} @@ -90,22 +87,22 @@ MapType HashTable<T>::type() const { template <typename T> int64_t HashTable<T>::max_key_id() const { - return header_->max_key_id; + return keys_->max_key_id(); } template <typename T> uint64_t HashTable<T>::num_keys() const { - return header_->num_keys; + return keys_->num_keys(); } template <typename T> bool HashTable<T>::get(int64_t key_id, Key *key) { - if ((key_id < MAP_MIN_KEY_ID) || (key_id > header_->max_key_id)) { + if ((key_id < MAP_MIN_KEY_ID) || (key_id > max_key_id())) { // Out of range. return false; } bool bit; - if (!bits_->get(key_id, &bit)) { + if (!keys_->get_bit(key_id, &bit)) { // Error. return false; } @@ -113,7 +110,7 @@ bool HashTable<T>::get(int64_t key_id, Key *key) { // Not found. return false; } - return keys_->get(key_id, key); + return keys_->get_key(key_id, key); } template <typename T> @@ -127,30 +124,11 @@ bool HashTable<T>::unset(int64_t key_id) { // Not found or error. return false; } - // 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); - if (!unit) { + if (!keys_->unset(key_id)) { // Error. return false; } - // 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); - if (!link) { - // Error. - return false; - } - } - *unit &= ~unit_bit; *stored_key_id = -1; - if (link) { - *link = header_->latest_link; - header_->latest_link = *link; - } - --header_->num_keys; return true; } @@ -176,7 +154,7 @@ bool HashTable<T>::reset(int64_t key_id, KeyArg dest_key) { // Found or error. return false; } - if (!keys_->set(key_id, dest_normalized_key)) { + if (!keys_->reset(key_id, dest_normalized_key)) { // Error. return false; } @@ -232,54 +210,15 @@ bool HashTable<T>::add(KeyArg key, int64_t *key_id) { // Error. return false; } - // 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(); - } else { - unit_id = header_->latest_link; - } - BitArrayUnit * const unit = bits_->get_unit(unit_id); - if (!unit) { - // Error. - return false; - } - 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; - uint64_t *link = nullptr; - if (is_new_unit) { - if (!links_->set(unit_id, INVALID_LINK)) { - // Error. - return false; - } - *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); - if (!link) { - // Error. - return false; - } - } - if (!keys_->set(next_key_id, normalized_key)) { + int64_t next_key_id; + if (!keys_->add(normalized_key, &next_key_id)) { // Error. return false; } - if (link) { - header_->latest_link = *link; - } - *unit |= unit_bit; if (*stored_key_id == MAP_INVALID_KEY_ID) { ++header_->num_key_ids; } *stored_key_id = next_key_id; - if (next_key_id > header_->max_key_id) { - header_->max_key_id = next_key_id; - } - ++header_->num_keys; if (key_id) { *key_id = next_key_id; } @@ -298,30 +237,11 @@ bool HashTable<T>::remove(KeyArg key) { // Not found or error. return false; } - // Prepare to update "bits_" and "links_". - const uint64_t unit_id = *stored_key_id / bits_->unit_size(); - const uint64_t unit_bit = 1ULL << (*stored_key_id % bits_->unit_size()); - BitArrayUnit * const unit = bits_->get_unit(unit_id); - if (!unit) { + if (!keys_->unset(*stored_key_id)) { // Error. return false; } - // 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); - if (!link) { - // Error. - return false; - } - } - *unit &= ~unit_bit; *stored_key_id = -1; - if (link) { - *link = header_->latest_link; - header_->latest_link = *link; - } - --header_->num_keys; return true; } @@ -343,7 +263,7 @@ bool HashTable<T>::replace(KeyArg src_key, KeyArg dest_key, int64_t *key_id) { // Found or error. return false; } - if (!keys_->set(*src_key_id, dest_normalized_key)) { + if (!keys_->reset(*src_key_id, dest_normalized_key)) { // Error. return false; } @@ -363,7 +283,7 @@ bool HashTable<T>::truncate() { if (!refresh_key_ids()) { return false; } - if (header_->max_key_id == MAP_MIN_KEY_ID) { + if (max_key_id() == MAP_MIN_KEY_ID) { // Nothing to do. return true; } @@ -381,10 +301,11 @@ bool HashTable<T>::truncate() { return false; } } - header_->max_key_id = MAP_MIN_KEY_ID - 1; - header_->num_keys = 0; + if (!keys_->truncate()) { + // Error. + return false; + } header_->num_key_ids = 0; - header_->latest_link = INVALID_LINK; header_->old_key_ids_storage_node_id = header_->key_ids_storage_node_id; header_->key_ids_storage_node_id = new_key_ids->storage_node_id(); Lock lock(&header_->mutex); @@ -410,16 +331,12 @@ bool HashTable<T>::create_map(Storage *storage, uint32_t storage_node_id, key_ids_.reset(KeyIDArray::create(storage, storage_node_id_, KeyIDArray::page_size() - 1)); keys_.reset(KeyArray::create(storage, storage_node_id_)); - bits_.reset(BitArray::create(storage, storage_node_id_)); - links_.reset(LinkArray::create(storage, storage_node_id_)); - if (!key_ids_ || !keys_ || !bits_ || !links_) { + if (!key_ids_ || !keys_) { storage->unlink_node(storage_node_id_); return false; } header_->key_ids_storage_node_id = key_ids_->storage_node_id(); 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(); return true; } @@ -439,9 +356,7 @@ bool HashTable<T>::open_map(Storage *storage, uint32_t storage_node_id) { header_ = static_cast<Header *>(storage_node.body()); key_ids_.reset(KeyIDArray::open(storage, header_->key_ids_storage_node_id)); keys_.reset(KeyArray::open(storage, header_->keys_storage_node_id)); - bits_.reset(BitArray::open(storage, header_->bits_storage_node_id)); - links_.reset(LinkArray::open(storage, header_->links_storage_node_id)); - if (!key_ids_ || !keys_ || !bits_ || !links_) { + if (!key_ids_ || !keys_) { return false; } return true; @@ -499,7 +414,7 @@ bool HashTable<T>::find_key(KeyArg key, int64_t **stored_key_id) { } } else { Key stored_key; - if (!keys_->get(*key_id, &stored_key)) { + if (!keys_->get_key(*key_id, &stored_key)) { // Error. return false; } @@ -520,7 +435,7 @@ bool HashTable<T>::find_key(KeyArg key, int64_t **stored_key_id) { template <typename T> bool HashTable<T>::rebuild() { - uint64_t new_size = header_->num_keys * 2; + uint64_t new_size = num_keys() * 2; if (new_size < key_ids_->page_size()) { new_size = key_ids_->page_size(); } @@ -543,7 +458,7 @@ bool HashTable<T>::rebuild() { int64_t key_id; for (key_id = MAP_MIN_KEY_ID; key_id <= max_key_id(); ++key_id) { bool bit; - if (!bits_->get(key_id, &bit)) { + if (!keys_->get_bit(key_id, &bit)) { // Error. break; } @@ -551,7 +466,7 @@ bool HashTable<T>::rebuild() { continue; } Key stored_key; - if (!keys_->get(key_id, &stored_key)) { + if (!keys_->get_key(key_id, &stored_key)) { // Error. break; } Modified: lib/grnxx/map/hash_table.hpp (+5 -9) =================================================================== --- lib/grnxx/map/hash_table.hpp 2013-06-14 11:51:15 +0900 (79ca3b3) +++ lib/grnxx/map/hash_table.hpp 2013-06-14 12:34:13 +0900 (1b067c8) @@ -23,10 +23,11 @@ #include <memory> #include "grnxx/map.hpp" -#include "grnxx/map/hash_table/bit_array.hpp" -#include "grnxx/map/hash_table/key_array.hpp" +//#include "grnxx/map/hash_table/bit_array.hpp" +//#include "grnxx/map/hash_table/key_array.hpp" #include "grnxx/map/hash_table/key_id_array.hpp" -#include "grnxx/map/hash_table/link_array.hpp" +//#include "grnxx/map/hash_table/link_array.hpp" +#include "grnxx/map/key_store.hpp" #include "grnxx/types.hpp" namespace grnxx { @@ -44,10 +45,7 @@ template <typename T> class HashTable : public Map<T> { using Header = hash_table::Header; using KeyIDArray = typename hash_table::KeyIDArray<T>; - using KeyArray = typename hash_table::KeyArray<T>::Type; - using BitArray = typename hash_table::BitArray<T>::Type; - using BitArrayUnit = typename BitArray::Unit; - using LinkArray = typename hash_table::LinkArray<T>::Type; + using KeyArray = KeyStore<T>; public: using Key = typename Map<T>::Key; @@ -85,8 +83,6 @@ class HashTable : public Map<T> { std::unique_ptr<KeyIDArray> key_ids_; std::unique_ptr<KeyIDArray> old_key_ids_; std::unique_ptr<KeyArray> keys_; - std::unique_ptr<BitArray> bits_; - std::unique_ptr<LinkArray> links_; bool create_map(Storage *storage, uint32_t storage_node_id, const MapOptions &options); Modified: lib/grnxx/map/hash_table/Makefile.am (+1 -4) =================================================================== --- lib/grnxx/map/hash_table/Makefile.am 2013-06-14 11:51:15 +0900 (bf818f3) +++ lib/grnxx/map/hash_table/Makefile.am 2013-06-14 12:34:13 +0900 (28ad000) @@ -8,10 +8,7 @@ libgrnxx_map_hash_table_la_SOURCES = \ libgrnxx_map_hash_table_includedir = ${includedir}/grnxx/map/hash_table libgrnxx_map_hash_table_include_HEADERS = \ - bit_array.hpp \ dummy.hpp \ hash.hpp \ header.hpp \ - key_array.hpp \ - key_id_array.hpp \ - link_array.hpp + key_id_array.hpp Deleted: lib/grnxx/map/hash_table/bit_array.hpp (+0 -62) 100644 =================================================================== --- lib/grnxx/map/hash_table/bit_array.hpp 2013-06-14 11:51:15 +0900 (a21dd6a) +++ /dev/null @@ -1,62 +0,0 @@ -/* - Copyright (C) 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_MAP_HASH_TABLE_BIT_ARRAY_HPP -#define GRNXX_MAP_HASH_TABLE_BIT_ARRAY_HPP - -#include "grnxx/features.hpp" - -#include "grnxx/array.hpp" -#include "grnxx/types.hpp" - -namespace grnxx { -namespace map { -namespace hash_table { - -// Change the array size based on the size of "T". -template <typename T, size_t T_SIZE = sizeof(T)> -struct BitArray; - -// Map<T> has at most 2^40 different keys. -template <typename T, size_t T_SIZE> -struct BitArray { - using Type = Array<bool, 65536, 4096, 4096>; -}; - -// Map<T> has at most 2^8 different keys. -template <typename T> -struct BitArray<T, 1> { - using Type = Array<bool, 256, 1, 1>; -}; - -// Map<T> has at most 2^16 different keys. -template <typename T> -struct BitArray<T, 2> { - using Type = Array<bool, 256, 256, 1>; -}; - -// Map<T> has at most 2^32 different keys. -template <typename T> -struct BitArray<T, 4> { - using Type = Array<bool, 16384, 512, 512>; -}; - -} // namespace hash_table -} // namespace map -} // namespace grnxx - -#endif // GRNXX_MAP_HASH_TABLE_BIT_ARRAY_HPP Modified: lib/grnxx/map/hash_table/dummy.cpp (+0 -3) =================================================================== --- lib/grnxx/map/hash_table/dummy.cpp 2013-06-14 11:51:15 +0900 (8caebe3) +++ lib/grnxx/map/hash_table/dummy.cpp 2013-06-14 12:34:13 +0900 (de9cf16) @@ -17,11 +17,8 @@ */ #include "grnxx/map/hash_table/dummy.hpp" -#include "grnxx/map/hash_table/bit_array.hpp" #include "grnxx/map/hash_table/hash.hpp" -#include "grnxx/map/hash_table/key_array.hpp" #include "grnxx/map/hash_table/key_id_array.hpp" -#include "grnxx/map/hash_table/link_array.hpp" namespace grnxx { namespace map { Modified: lib/grnxx/map/hash_table/header.cpp (+0 -6) =================================================================== --- lib/grnxx/map/hash_table/header.cpp 2013-06-14 11:51:15 +0900 (f8981b2) +++ lib/grnxx/map/hash_table/header.cpp 2013-06-14 12:34:13 +0900 (e7b1404) @@ -17,7 +17,6 @@ */ #include "grnxx/map/hash_table/header.hpp" -#include "grnxx/map/hash_table/link_array.hpp" #include "grnxx/storage.hpp" namespace grnxx { @@ -29,12 +28,7 @@ Header::Header() key_ids_storage_node_id(STORAGE_INVALID_NODE_ID), old_key_ids_storage_node_id(STORAGE_INVALID_NODE_ID), keys_storage_node_id(STORAGE_INVALID_NODE_ID), - bits_storage_node_id(STORAGE_INVALID_NODE_ID), - links_storage_node_id(STORAGE_INVALID_NODE_ID), - max_key_id(MAP_MIN_KEY_ID - 1), - num_keys(0), num_key_ids(0), - latest_link(INVALID_LINK), mutex(MUTEX_UNLOCKED) {} } // namespace hash_table Modified: lib/grnxx/map/hash_table/header.hpp (+0 -5) =================================================================== --- lib/grnxx/map/hash_table/header.hpp 2013-06-14 11:51:15 +0900 (2266333) +++ lib/grnxx/map/hash_table/header.hpp 2013-06-14 12:34:13 +0900 (7118165) @@ -33,12 +33,7 @@ struct Header { uint32_t key_ids_storage_node_id; uint32_t old_key_ids_storage_node_id; uint32_t keys_storage_node_id; - uint32_t bits_storage_node_id; - uint32_t links_storage_node_id; - int64_t max_key_id; - uint64_t num_keys; uint64_t num_key_ids; - uint64_t latest_link; Mutex mutex; Header(); Deleted: lib/grnxx/map/hash_table/key_array.hpp (+0 -70) 100644 =================================================================== --- lib/grnxx/map/hash_table/key_array.hpp 2013-06-14 11:51:15 +0900 (bacec40) +++ /dev/null @@ -1,70 +0,0 @@ -/* - Copyright (C) 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_MAP_HASH_TABLE_KEY_ARRAY_HPP -#define GRNXX_MAP_HASH_TABLE_KEY_ARRAY_HPP - -#include "grnxx/features.hpp" - -#include "grnxx/array.hpp" -#include "grnxx/bytes.hpp" -#include "grnxx/map/bytes_array.hpp" -#include "grnxx/types.hpp" - -namespace grnxx { -namespace map { -namespace hash_table { - -// Change the array size based on "T". -template <typename T, size_t T_SIZE = sizeof(T)> -struct KeyArray; - -// Map<T> has at most 2^40 different keys. -template <typename T, size_t T_SIZE> -struct KeyArray { - using Type = Array<T, 65536, 4096, 4096>; -}; - -// Map<T> has at most 2^8 different keys. -template <typename T> -struct KeyArray<T, 1> { - using Type = Array<T, 256, 1, 1>; -}; - -// Map<T> has at most 2^16 different keys. -template <typename T> -struct KeyArray<T, 2> { - using Type = Array<T, 256, 256, 1>; -}; - -// Map<T> has at most 2^32 different keys. -template <typename T> -struct KeyArray<T, 4> { - using Type = Array<T, 65536, 256, 256>; -}; - -// Map<T> has at most 2^40 different keys. -template <> -struct KeyArray<Bytes> { - using Type = BytesArray; -}; - -} // namespace hash_table -} // namespace map -} // namespace grnxx - -#endif // GRNXX_MAP_HASH_TABLE_KEY_ARRAY_HPP Modified: lib/grnxx/map/hash_table/key_id_array.hpp (+1 -0) =================================================================== --- lib/grnxx/map/hash_table/key_id_array.hpp 2013-06-14 11:51:15 +0900 (76a0038) +++ lib/grnxx/map/hash_table/key_id_array.hpp 2013-06-14 12:34:13 +0900 (8e90c91) @@ -21,6 +21,7 @@ #include "grnxx/features.hpp" #include "grnxx/array_impl.hpp" +#include "grnxx/logger.hpp" #include "grnxx/map.hpp" #include "grnxx/storage.hpp" #include "grnxx/types.hpp" Deleted: lib/grnxx/map/hash_table/link_array.hpp (+0 -65) 100644 =================================================================== --- lib/grnxx/map/hash_table/link_array.hpp 2013-06-14 11:51:15 +0900 (9779e07) +++ /dev/null @@ -1,65 +0,0 @@ -/* - Copyright (C) 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_MAP_HASH_TABLE_LINK_ARRAY_HPP -#define GRNXX_MAP_HASH_TABLE_LINK_ARRAY_HPP - -#include "grnxx/features.hpp" - -#include "grnxx/array.hpp" -#include "grnxx/types.hpp" - -namespace grnxx { -namespace map { -namespace hash_table { - -constexpr uint64_t INVALID_LINK = uint64_t(-1); - -// Change the array size based on the size of "T". -// Note that the size of link array is N/64 where N is the size of BitArray. -template <typename T, size_t T_SIZE = sizeof(T)> -struct LinkArray; - -// Map<T> has at most 2^40 different keys. -template <typename T, size_t T_SIZE> -struct LinkArray { - using Type = Array<uint64_t, 16384, 1024, 1024>; -}; - -// Map<T> has at most 2^8 different keys. -template <typename T> -struct LinkArray<T, 1> { - using Type = Array<uint64_t, 4, 1, 1>; -}; - -// Map<T> has at most 2^16 different keys. -template <typename T> -struct LinkArray<T, 2> { - using Type = Array<uint64_t, 1024, 1, 1>; -}; - -// Map<T> has at most 2^32 different keys. -template <typename T> -struct LinkArray<T, 4> { - using Type = Array<uint64_t, 4096, 128, 128>; -}; - -} // namespace hash_table -} // namespace map -} // namespace grnxx - -#endif // GRNXX_MAP_HASH_TABLE_LINK_ARRAY_HPP -------------- next part -------------- HTML����������������������������...Download