nlib
Trie.h
[詳解]
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
18 
19 #include <string.h>
20 #include <utility>
21 
22 #include "nn/nlib/succinct/Louds.h"
23 #include "nn/nlib/succinct/Sbv.h"
24 #include "nn/nlib/ReallocVec.h"
25 #include "nn/nlib/Swap.h"
26 #include "nn/nlib/Nlist.h"
27 
28 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
29 #undef NLIB_VIS_PUBLIC
30 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
31 #endif
32 
33 NLIB_NAMESPACE_BEGIN
34 namespace succinct {
35 
37  public:
38  NLIB_CEXPR Trie() NLIB_NOEXCEPT : prv_(nullptr) {}
39  ~Trie() NLIB_NOEXCEPT { Reset(); }
40  NLIB_DEFMOVE_PIMPL(Trie);
41  bool Init() NLIB_NOEXCEPT;
42  typedef bool (*MatchCallback)(const char* first, const char* last, uint32_t nodeid,
43  void* user_obj);
44  void Match(const char* cstr, MatchCallback callback, void* user_obj) NLIB_NOEXCEPT {
45  this->Match(cstr, nlib_strlen(cstr), callback, user_obj);
46  }
47  void Match(const char* cstr, MatchCallback callback) NLIB_NOEXCEPT {
48  this->Match(cstr, nlib_strlen(cstr), callback, nullptr);
49  }
50  void Match(const void* data, size_t n, MatchCallback callback, void* user_obj) NLIB_NOEXCEPT;
51  void Match(const void* data, size_t n, MatchCallback callback) NLIB_NOEXCEPT {
52  Match(data, n, callback, nullptr);
53  }
54 
55  void
56  MatchBackward(const void* data, size_t n, MatchCallback callback, void* user_obj) NLIB_NOEXCEPT;
57  void MatchBackward(const void* data, size_t n, MatchCallback callback) NLIB_NOEXCEPT {
58  MatchBackward(data, n, callback, nullptr);
59  }
60  errno_t
61  GetCommonPrefixWords(const void* prefix, size_t n, ReallocCstringVec* vec) NLIB_NOEXCEPT;
62 #ifdef __cpp_rvalue_references
63  std::pair<errno_t, Nlist<uint32_t> >
64  GetCommonPrefixWords(const void* prefix, size_t n) NLIB_NOEXCEPT;
65 #endif
66 
67  void Reset() NLIB_NOEXCEPT;
68  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
69  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
70  size_t MemSize() const NLIB_NOEXCEPT;
71 
72  private:
73  NLIB_VIS_HIDDEN int Match_(const nlib_byte_t* data, const unsigned char* p, uint32_t pos,
74  MatchCallback callback, void* user_obj, bool isfwd) NLIB_NOEXCEPT;
75 
76  private:
77  struct TriePrivate;
78  TriePrivate* prv_;
79  friend class TrieBuilder;
81 };
82 
84  public:
85  NLIB_CEXPR TrieBuilder() NLIB_NOEXCEPT : prv_(nullptr) {}
86  ~TrieBuilder() NLIB_NOEXCEPT { Reset(); }
87  NLIB_DEFMOVE_PIMPL(TrieBuilder);
88  void Reset() NLIB_NOEXCEPT;
89  bool Init() NLIB_NOEXCEPT;
90  Trie* Build(ReallocVec<uint32_t>* keyids = nullptr) NLIB_NOEXCEPT;
91 #ifdef __cpp_rvalue_references
92  std::unique_ptr<Trie> Build2() NLIB_NOEXCEPT { return decltype(Build2())(Build(nullptr)); }
93 #endif
94  bool AddWord(const char* str) NLIB_NOEXCEPT;
95  bool AddPattern(const void* p, size_t n) NLIB_NOEXCEPT;
96  bool AddWords(const char* str, size_t len) NLIB_NOEXCEPT;
97  bool AddWords(const char* str) NLIB_NOEXCEPT { return AddWords(str, strlen(str)); }
98 
99  private:
100  struct TrieBuilderPrivate;
101  TrieBuilderPrivate* prv_;
103 };
104 
105 } // namespace succinct
106 NLIB_NAMESPACE_END
107 
108 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Trie)
109 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::TrieBuilder)
110 
111 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
112 #undef NLIB_VIS_PUBLIC
113 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
114 #endif
115 
116 #endif // INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
Trieオブジェクトを作成するためのクラスです。
Definition: Trie.h:83
rank/select操作をベースとした基本的なクラスが定義されています。
LOUDSを構築したり、LOUDSにアクセスしたりするためのクラスが定義されています。
constexpr Trie() noexcept
デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
Definition: Trie.h:38
void Match(const char *cstr, MatchCallback callback) noexcept
上記関数の引数省略版で、nullptrを引数として渡します。
Definition: Trie.h:47
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:183
void Match(const void *data, size_t n, MatchCallback callback) noexcept
上記関数の引数省略版で、nullptrを引数として渡します。
Definition: Trie.h:51
std::unique_ptr< Trie > Build2() noexcept
Trieオブジェクトを作成してunique_ptrで返します。
Definition: Trie.h:92
~TrieBuilder() noexcept
デストラクタです。
Definition: Trie.h:86
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:282
LOUDSを利用したTrieの実装です。
Definition: Trie.h:36
#define NLIB_VIS_HIDDEN
関数やクラス等のシンボルをライブラリの外部に公開しません。
Definition: Platform_unix.h:86
bool AddWords(const char *str) noexcept
検出対象の文字列の集合が入った配列から文字列を追加します。文字列の区切りは改行(CRLFかLF)である必要が...
Definition: Trie.h:97
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:87
std::vectorに似ていますが、コピーできないオブジェクトを格納可能なクラスが定義されています。 ...
constexpr TrieBuilder() noexcept
デフォルトコンストラクタです。実行後Init()による初期化を必要とします。
Definition: Trie.h:85
~Trie() noexcept
デストラクタです。
Definition: Trie.h:39
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:111
void MatchBackward(const void *data, size_t n, MatchCallback callback) noexcept
上記関数の引数省略版で、nullptrを引数として渡します。
Definition: Trie.h:57
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:250
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
unsigned char nlib_byte_t
C++17以降でstd::byteにtypedefされる型です。
Definition: Platform.h:314
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:32
int errno_t
intのtypedefで、戻り値としてPOSIXのエラー値を返すことを示します。
Definition: NMalloc.h:37