nlib
Trie.h
Go to the documentation of this file.
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
4 #define INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
5 
6 #include <string.h>
7 
8 #include "nn/nlib/UniquePtr.h"
10 #include "nn/nlib/succinct/Sbv.h"
11 
12 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
13 #undef NLIB_VIS_PUBLIC
14 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
15 #endif
16 
17 NLIB_NAMESPACE_BEGIN
18 namespace succinct {
19 
21  public:
24  NLIB_MOVE_MEMBER_HELPER_3(Trie, m_Louds, m_IsTerminal, m_Labels);
25  void swap(Trie& rhs) NLIB_NOEXCEPT {
26  m_Louds.swap(rhs.m_Louds);
27  m_IsTerminal.swap(rhs.m_IsTerminal);
28  m_Labels.swap(rhs.m_Labels);
29  }
31  this->Reset();
32  return true;
33  }
34  typedef bool (*MatchCallback)(const char* first, const char* last, uint32_t nodeid,
35  void* user_obj);
36  void Match(const char* cstr, MatchCallback callback, void* user_obj = NULL) NLIB_NOEXCEPT {
37  this->Match(cstr, nlib_strlen(cstr), callback, user_obj);
38  }
39  NLIB_VIS_PUBLIC void Match(const void* data, size_t n, MatchCallback callback,
40  void* user_obj = NULL) NLIB_NOEXCEPT;
41  NLIB_VIS_PUBLIC void MatchBackward(const void* data, size_t n, MatchCallback callback,
42  void* user_obj = NULL) NLIB_NOEXCEPT;
43  NLIB_VIS_PUBLIC errno_t GetCommonPrefixWords(const void* prefix, size_t n,
44  ReallocCstringVec* vec) NLIB_NOEXCEPT;
45  void Reset() NLIB_NOEXCEPT {
46  m_Louds.Reset();
47  m_IsTerminal.Reset();
48  m_Labels.Reset();
49  }
50  NLIB_VIS_PUBLIC bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
52 
53  private:
54  NLIB_VIS_HIDDEN int Match_(const void* data, const unsigned char* p, uint32_t pos,
55  MatchCallback callback, void* user_obj, bool isfwd) NLIB_NOEXCEPT;
56 
57  private:
58  Louds m_Louds;
59  detail::BitVector32 m_IsTerminal;
60  detail::PlainArray32<unsigned char> m_Labels;
61  friend class TrieBuilder;
63 };
64 
66  public:
69  NLIB_VIS_PUBLIC bool Init() NLIB_NOEXCEPT;
70  NLIB_VIS_PUBLIC Trie* Build(ReallocVec<uint32_t>* keyids = NULL) NLIB_NOEXCEPT;
71  NLIB_VIS_PUBLIC bool AddWord(const char* str) NLIB_NOEXCEPT;
72  NLIB_VIS_PUBLIC bool AddPattern(const void* p, size_t n) NLIB_NOEXCEPT;
73  NLIB_VIS_PUBLIC bool AddWords(const char* str, size_t len) NLIB_NOEXCEPT;
74  bool AddWords(const char* str) NLIB_NOEXCEPT {
75  return AddWords(str, strlen(str));
76  }
77 
78  private:
79  ReallocCstringVec m_Words;
81 };
82 
83 } // namespace succinct
84 NLIB_NAMESPACE_END
85 
86 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
87 #undef NLIB_VIS_PUBLIC
88 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
89 #endif
90 
91 #endif // INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Platform.h:2151
Class to create a Trie object.
Definition: Trie.h:65
Defines the basic classes that form the basis to Rank and Select operations.
Defines the class for constructing and accessing a LOUDS succinct tree.
void swap(Trie &rhs) noexcept
Swaps the contents of an object.
Definition: Trie.h:25
Trie() noexcept
Instantiates the object.
Definition: Trie.h:22
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:126
void Match(const char *cstr, MatchCallback callback, void *user_obj=NULL) noexcept
Inspects the string to detect the target string registered in Trie.
Definition: Trie.h:36
~TrieBuilder() noexcept
Destructor.
Definition: Trie.h:68
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:214
#define NLIB_VIS_HIDDEN
Symbols for functions and classes are not made available outside of the library.
Definition: Platform_unix.h:50
Implements Trie using LOUDS.
Definition: Trie.h:20
Defines that class that is corresponding to std::unique_ptr.
bool Init() noexcept
Resets the contents of an object.
Definition: Trie.h:30
TrieBuilder() noexcept
Instantiates the object.
Definition: Trie.h:67
~Trie() noexcept
Destructor.
Definition: Trie.h:23
Provides a compact tree structure that can provide various operations in constant time...
Definition: Louds.h:17
size_t nlib_strlen(const char *s)
Internally calls strlen(). In some cases, it may operate as an independent implementation.
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:13
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:51
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:13
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:18
int errno_t
Indicates with an int-type typedef that a POSIX error value is returned as the return value...
Definition: NMalloc.h:24