susumu.yata
null+****@clear*****
Mon Feb 18 14:44:22 JST 2013
susumu.yata 2013-02-18 14:44:22 +0900 (Mon, 18 Feb 2013) New Revision: a6583eac1ea4a8bfb85f7926949af114de168a01 https://github.com/groonga/grnxx/commit/a6583eac1ea4a8bfb85f7926949af114de168a01 Log: Add lcp_search(). Modified files: lib/map.hpp lib/map/da/basic_trie.cpp lib/map/da/basic_trie.hpp lib/map/da/trie.hpp lib/map/double_array.cpp lib/map/double_array.hpp Modified: lib/map.hpp (+3 -0) =================================================================== --- lib/map.hpp 2013-02-18 13:43:51 +0900 (81c2fdd) +++ lib/map.hpp 2013-02-18 14:44:22 +0900 (a326071) @@ -55,6 +55,9 @@ class Map { virtual bool search(int64_t key_id, Slice *key = nullptr) = 0; virtual bool search(const Slice &key, int64_t *key_id = nullptr) = 0; + virtual bool lcp_search(const Slice &query, int64_t *key_id = nullptr, + Slice *key = nullptr) = 0; + virtual bool insert(const Slice &key, int64_t *key_id = nullptr) = 0; virtual bool remove(int64_t key_id) = 0; Modified: lib/map/da/basic_trie.cpp (+74 -0) =================================================================== --- lib/map/da/basic_trie.cpp 2013-02-18 13:43:51 +0900 (52c654a) +++ lib/map/da/basic_trie.cpp 2013-02-18 14:44:22 +0900 (46aa092) @@ -131,6 +131,80 @@ bool Trie::search(const Slice &key, int64_t *key_id) { return false; } +bool Trie::lcp_search(const Slice &query, int64_t *key_id, Slice *key) { + bool found = false; + uint32_t node_id = ROOT_NODE_ID; + uint32_t query_pos = 0; + + for ( ; query_pos < query.size(); ++query_pos) { + const Node node = nodes_[node_id]; + if (node.is_leaf()) { + const Key &match = get_key(node.key_pos()); + if ((match.size() <= query.size()) && + match.equals_to(Slice(query.address(), match.size()), query_pos)) { + if (key_id) { + *key_id = match.id(); + } + if (key) { + *key = match.slice(); + } + found = true; + } + return found; + } + + if (nodes_[node_id].child() == TERMINAL_LABEL) { + const Node leaf_node = nodes_[node.offset() ^ TERMINAL_LABEL]; + if (leaf_node.is_leaf()) { + if (key_id || key) { + const Key &match = get_key(leaf_node.key_pos()); + if (key_id) { + *key_id = match.id(); + } + if (key) { + *key = match.slice(); + } + } + found = true; + } + } + + node_id = node.offset() ^ query[query_pos]; + if (nodes_[node_id].label() != query[query_pos]) { + return found; + } + } + + const Node node = nodes_[node_id]; + if (node.is_leaf()) { + const Key &match = get_key(node.key_pos()); + if (match.size() <= query.size()) { + if (key_id) { + *key_id = match.id(); + } + if (key) { + *key = match.slice(); + } + found = true; + } + } else if (nodes_[node_id].child() == TERMINAL_LABEL) { + const Node leaf_node = nodes_[node.offset() ^ TERMINAL_LABEL]; + if (leaf_node.is_leaf()) { + if (key_id || key) { + const Key &match = get_key(leaf_node.key_pos()); + if (key_id) { + *key_id = match.id(); + } + if (key) { + *key = match.slice(); + } + } + found = true; + } + } + return found; +} + bool Trie::insert(const Slice &key, int64_t *key_id) { if ((key.size() < MIN_KEY_SIZE) || (key.size() > MAX_KEY_SIZE)) { GRNXX_ERROR() << "invalid key: size = " << key.size(); Modified: lib/map/da/basic_trie.hpp (+3 -0) =================================================================== --- lib/map/da/basic_trie.hpp 2013-02-18 13:43:51 +0900 (aec0d00) +++ lib/map/da/basic_trie.hpp 2013-02-18 14:44:22 +0900 (0554b7b) @@ -423,6 +423,9 @@ class Trie : public da::Trie { bool search(int64_t key_id, Slice *key = nullptr); bool search(const Slice &key, int64_t *key_id = nullptr); + bool lcp_search(const Slice &query, int64_t *key_id = nullptr, + Slice *key = nullptr); + bool insert(const Slice &key, int64_t *key_id = nullptr); bool remove(int64_t key_id); Modified: lib/map/da/trie.hpp (+3 -0) =================================================================== --- lib/map/da/trie.hpp 2013-02-18 13:43:51 +0900 (68976c9) +++ lib/map/da/trie.hpp 2013-02-18 14:44:22 +0900 (2e1ba77) @@ -63,6 +63,9 @@ class Trie { virtual bool search(int64_t key_id, Slice *key = nullptr) = 0; virtual bool search(const Slice &key, int64_t *key_id = nullptr) = 0; + virtual bool lcp_search(const Slice &query, int64_t *key_id = nullptr, + Slice *key = nullptr) = 0; + virtual bool insert(const Slice &key, int64_t *key_id = nullptr) = 0; virtual bool remove(int64_t key_id) = 0; Modified: lib/map/double_array.cpp (+9 -0) =================================================================== --- lib/map/double_array.cpp 2013-02-18 13:43:51 +0900 (f371034) +++ lib/map/double_array.cpp 2013-02-18 14:44:22 +0900 (bb4e98c) @@ -65,6 +65,15 @@ bool DoubleArray::search(int64_t key_id, Slice *key) { return front_->search(key_id, key); } +bool DoubleArray::lcp_search(const Slice &query, int64_t *key_id, + Slice *key) { + open_trie_if_needed(); + if (!front_) { + return false; + } + return front_->lcp_search(query, key_id, key); +} + bool DoubleArray::search(const Slice &key, int64_t *key_id) { open_trie_if_needed(); if (!front_) { Modified: lib/map/double_array.hpp (+3 -0) =================================================================== --- lib/map/double_array.hpp 2013-02-18 13:43:51 +0900 (5f490c2) +++ lib/map/double_array.hpp 2013-02-18 14:44:22 +0900 (631a93d) @@ -44,6 +44,9 @@ class DoubleArray : public Map { bool search(int64_t key_id, Slice *key = nullptr); bool search(const Slice &key, int64_t *key_id = nullptr); + bool lcp_search(const Slice &query, int64_t *key_id = nullptr, + Slice *key = nullptr); + bool insert(const Slice &key, int64_t *key_id = nullptr); bool remove(int64_t key_id); -------------- next part -------------- HTML����������������������������...다운로드
