null+****@clear*****
null+****@clear*****
2011年 12月 27日 (火) 13:27:07 JST
Susumu Yata 2011-12-27 13:27:07 +0900 (Tue, 27 Dec 2011)
New Revision: 45d5f1f7f0b6e692c464bcbebf3d2052917d4e5f
Log:
added grn::dat::Trie::lcp_search().
Modified files:
lib/dat/trie.cpp
lib/dat/trie.hpp
Modified: lib/dat/trie.cpp (+60 -0)
===================================================================
--- lib/dat/trie.cpp 2011-12-27 11:01:16 +0900 (eb9bb87)
+++ lib/dat/trie.cpp 2011-12-27 13:27:07 +0900 (4c64520)
@@ -370,6 +370,66 @@ bool Trie::search_linker(const UInt8 *ptr, UInt32 length,
return ith_node(next).is_linker();
}
+bool Trie::lcp_search_key(const UInt8 *ptr, UInt32 length,
+ UInt32 *key_pos) const {
+ GRN_DAT_DEBUG_THROW_IF((ptr == NULL) && (length != 0));
+
+ bool found = false;
+ UInt32 node_id = ROOT_NODE_ID;
+ UInt32 query_pos = 0;
+
+ for ( ; query_pos < length; ++query_pos) {
+ const Base base = ith_node(node_id).base();
+ if (base.is_linker()) {
+ const Key &key = get_key(base.key_pos());
+ if ((key.length() <= length) &&
+ key.equals_to(ptr, key.length(), query_pos)) {
+ if (key_pos != NULL) {
+ *key_pos = base.key_pos();
+ }
+ found = true;
+ }
+ return found;
+ }
+
+ if (ith_node(node_id).child() == TERMINAL_LABEL) {
+ const Base linker_base =
+ ith_node(base.offset() ^ TERMINAL_LABEL).base();
+ if (linker_base.is_linker()) {
+ if (key_pos != NULL) {
+ *key_pos = linker_base.key_pos();
+ }
+ found = true;
+ }
+ }
+
+ node_id = base.offset() ^ ptr[query_pos];
+ if (ith_node(node_id).label() != ptr[query_pos]) {
+ return found;
+ }
+ }
+
+ const Base base = ith_node(node_id).base();
+ if (base.is_linker()) {
+ const Key &key = get_key(base.key_pos());
+ if (key.length() <= length) {
+ if (key_pos != NULL) {
+ *key_pos = base.key_pos();
+ }
+ found = true;
+ }
+ } else if (ith_node(node_id).child() == TERMINAL_LABEL) {
+ const Base linker_base = ith_node(base.offset() ^ TERMINAL_LABEL).base();
+ if (linker_base.is_linker()) {
+ if (key_pos != NULL) {
+ *key_pos = linker_base.key_pos();
+ }
+ found = true;
+ }
+ }
+ return found;
+}
+
bool Trie::remove_key(const UInt8 *ptr, UInt32 length) {
GRN_DAT_DEBUG_THROW_IF((ptr == NULL) && (length != 0));
Modified: lib/dat/trie.hpp (+7 -0)
===================================================================
--- lib/dat/trie.hpp 2011-12-27 11:01:16 +0900 (f20fd0f)
+++ lib/dat/trie.hpp 2011-12-27 13:27:07 +0900 (ab866fd)
@@ -71,6 +71,11 @@ class Trie {
bool search(const void *ptr, UInt32 length, UInt32 *key_pos = NULL) const {
return search_key(static_cast<const UInt8 *>(ptr), length, key_pos);
}
+ // Longest prefix match search.
+ bool lcp_search(const void *ptr, UInt32 length,
+ UInt32 *key_pos = NULL) const {
+ return lcp_search_key(static_cast<const UInt8 *>(ptr), length, key_pos);
+ }
bool remove(UInt32 key_id) {
const Key &key = ith_key(key_id);
@@ -205,6 +210,8 @@ class Trie {
bool search_linker(const UInt8 *ptr, UInt32 length,
UInt32 &node_id, UInt32 &query_pos) const;
+ bool lcp_search_key(const UInt8 *ptr, UInt32 length, UInt32 *key_pos) const;
+
bool remove_key(const UInt8 *ptr, UInt32 length);
bool insert_key(const UInt8 *ptr, UInt32 length, UInt32 *key_pos);