susumu.yata
null+****@clear*****
Thu Jun 27 10:50:35 JST 2013
susumu.yata 2013-06-27 10:50:35 +0900 (Thu, 27 Jun 2013) New Revision: d55c7ade5b00b7758dbb302fb14de22e4d8310ce https://github.com/groonga/grnxx/commit/d55c7ade5b00b7758dbb302fb14de22e4d8310ce Message: Add a cache mechanism to grnxx::map::Patricia (but commented out). Modified files: lib/grnxx/map/patricia.cpp lib/grnxx/map/patricia.hpp lib/grnxx/map/patricia/header.cpp lib/grnxx/map/patricia/header.hpp Modified: lib/grnxx/map/patricia.cpp (+39 -3) =================================================================== --- lib/grnxx/map/patricia.cpp 2013-06-26 09:58:41 +0900 (c440162) +++ lib/grnxx/map/patricia.cpp 2013-06-27 10:50:35 +0900 (4f614e3) @@ -22,6 +22,7 @@ #include "grnxx/bytes.hpp" #include "grnxx/geo_point.hpp" #include "grnxx/logger.hpp" +#include "grnxx/map/hash_table/hash.hpp" #include "grnxx/map/helper.hpp" #include "grnxx/map/patricia/header.hpp" #include "grnxx/storage.hpp" @@ -470,7 +471,8 @@ Patricia<Bytes>::Patricia() storage_node_id_(STORAGE_INVALID_NODE_ID), header_(nullptr), nodes_(), - keys_() {} + keys_(), + cache_() {} Patricia<Bytes>::~Patricia() {} @@ -648,6 +650,22 @@ bool Patricia<Bytes>::find(KeyArg key, int64_t *key_id) { } bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { +// int64_t * const cache = +// cache_->get_pointer(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 (key_id) { +// *key_id = *cache; +// } +// return false; +// } +// } +// } +// } uint64_t node_id = ROOT_NODE_ID; Node *node = nodes_->get_pointer(node_id); if (!node) { @@ -665,6 +683,9 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { if (key_id) { *key_id = next_key_id; } +// if (cache) { +// *cache = next_key_id; +// } return true; } const uint64_t bit_size = key.size() * 8; @@ -719,6 +740,9 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { if (key_id) { *key_id = node->key_id(); } +// if (cache) { +// *cache = node->key_id(); +// } return false; } node = history[depth % 8]; @@ -746,6 +770,9 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { if (key_id) { *key_id = next_key_id; } +// if (cache) { +// *cache = next_key_id; +// } return true; } count = (count * 8) + 7 - bit_scan_reverse(key[count] ^ stored_key[count]); @@ -785,6 +812,9 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { if (key_id) { *key_id = next_key_id; } +// if (cache) { +// *cache = next_key_id; +// } return true; } // Find the branching point with the naive method. @@ -832,6 +862,9 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { if (key_id) { *key_id = next_key_id; } +// if (cache) { +// *cache = next_key_id; +// } return true; } @@ -992,12 +1025,14 @@ bool Patricia<Bytes>::create_map(Storage *storage, uint32_t storage_node_id, *header_ = Header(); nodes_.reset(NodeArray::create(storage, storage_node_id_)); keys_.reset(KeyStore<Bytes>::create(storage, storage_node_id_)); - if (!nodes_ || !keys_) { + cache_.reset(Cache::create(storage, storage_node_id_, -1)); + if (!nodes_ || !keys_ || !cache_) { storage->unlink_node(storage_node_id_); return false; } 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); if (!root_node) { storage->unlink_node(storage_node_id_); @@ -1023,7 +1058,8 @@ bool Patricia<Bytes>::open_map(Storage *storage, uint32_t storage_node_id) { // TODO: Check the format. nodes_.reset(NodeArray::open(storage, header_->nodes_storage_node_id)); keys_.reset(KeyStore<Bytes>::open(storage, header_->keys_storage_node_id)); - if (!nodes_ || !keys_) { + cache_.reset(Cache::open(storage, header_->cache_storage_node_id)); + if (!nodes_ || !keys_ || !cache_) { return false; } return true; Modified: lib/grnxx/map/patricia.hpp (+2 -0) =================================================================== --- lib/grnxx/map/patricia.hpp 2013-06-26 09:58:41 +0900 (6f25ad1) +++ lib/grnxx/map/patricia.hpp 2013-06-27 10:50:35 +0900 (2ca3b16) @@ -94,6 +94,7 @@ template <> class Patricia<Bytes> : public Map<Bytes> { using Node = patricia::Node; using NodeArray = Array<Node>; + using Cache = Array<int64_t, 1 << 20, 1, 1>; public: using Header = patricia::Header; @@ -134,6 +135,7 @@ class Patricia<Bytes> : public Map<Bytes> { Header *header_; std::unique_ptr<NodeArray> nodes_; std::unique_ptr<KeyStore<Bytes>> keys_; + std::unique_ptr<Cache> cache_; bool create_map(Storage *storage, uint32_t storage_node_id, const MapOptions &options); Modified: lib/grnxx/map/patricia/header.cpp (+2 -1) =================================================================== --- lib/grnxx/map/patricia/header.cpp 2013-06-26 09:58:41 +0900 (abe4727) +++ lib/grnxx/map/patricia/header.cpp 2013-06-27 10:50:35 +0900 (4f6872f) @@ -27,7 +27,8 @@ Header::Header() : map_type(MAP_PATRICIA), next_node_id(2), nodes_storage_node_id(STORAGE_INVALID_NODE_ID), - keys_storage_node_id(STORAGE_INVALID_NODE_ID) {} + keys_storage_node_id(STORAGE_INVALID_NODE_ID), + cache_storage_node_id(STORAGE_INVALID_NODE_ID) {} } // namespace patricia } // namespace map Modified: lib/grnxx/map/patricia/header.hpp (+1 -0) =================================================================== --- lib/grnxx/map/patricia/header.hpp 2013-06-26 09:58:41 +0900 (05fa44c) +++ lib/grnxx/map/patricia/header.hpp 2013-06-27 10:50:35 +0900 (f355c16) @@ -32,6 +32,7 @@ struct Header { uint64_t next_node_id; uint32_t nodes_storage_node_id; uint32_t keys_storage_node_id; + uint32_t cache_storage_node_id; Header(); }; -------------- next part -------------- HTML����������������������������...Download