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 
27 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
28 #undef NLIB_VIS_PUBLIC
29 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
30 #endif
31 
32 NLIB_NAMESPACE_BEGIN
33 namespace succinct {
34 
36  public:
37  NLIB_CEXPR Trie() NLIB_NOEXCEPT : prv_(nullptr) {}
38  ~Trie() NLIB_NOEXCEPT { Reset(); }
39  NLIB_DEFMOVE_PIMPL(Trie);
41  TriePrivate* tmp = rhs.prv_;
42  rhs.prv_ = this->prv_;
43  this->prv_ = tmp;
44  }
45  bool Init() NLIB_NOEXCEPT;
46  typedef bool (*MatchCallback)(const char* first, const char* last, uint32_t nodeid,
47  void* user_obj);
48  void Match(const char* cstr, MatchCallback callback, void* user_obj) NLIB_NOEXCEPT {
49  this->Match(cstr, nlib_strlen(cstr), callback, user_obj);
50  }
51  void Match(const char* cstr, MatchCallback callback) NLIB_NOEXCEPT {
52  this->Match(cstr, nlib_strlen(cstr), callback, nullptr);
53  }
54  void Match(const void* data, size_t n, MatchCallback callback,
55  void* user_obj) NLIB_NOEXCEPT;
56  void Match(const void* data, size_t n, MatchCallback callback) NLIB_NOEXCEPT {
57  Match(data, n, callback, nullptr);
58  }
59 
60  void MatchBackward(const void* data, size_t n, MatchCallback callback,
61  void* user_obj) NLIB_NOEXCEPT;
62  void MatchBackward(const void* data, size_t n, MatchCallback callback) NLIB_NOEXCEPT {
63  MatchBackward(data, n, callback, nullptr);
64  }
65  errno_t GetCommonPrefixWords(const void* prefix, size_t n,
67  void Reset() NLIB_NOEXCEPT;
68  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
69  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
70 
71  private:
72  NLIB_VIS_HIDDEN int Match_(const nlib_byte_t* data, const unsigned char* p, uint32_t pos,
73  MatchCallback callback, void* user_obj, bool isfwd) NLIB_NOEXCEPT;
74 
75  private:
76  struct TriePrivate;
77  TriePrivate* prv_;
78  friend class TrieBuilder;
80 };
81 
83  public:
84  NLIB_CEXPR TrieBuilder() NLIB_NOEXCEPT : prv_(nullptr) {}
85  ~TrieBuilder() NLIB_NOEXCEPT { Reset(); }
86  NLIB_DEFMOVE_PIMPL(TrieBuilder);
87  void Reset() NLIB_NOEXCEPT;
88  bool Init() NLIB_NOEXCEPT;
89  Trie* Build(ReallocVec<uint32_t>* keyids = nullptr) NLIB_NOEXCEPT;
90  bool AddWord(const char* str) NLIB_NOEXCEPT;
91  bool AddPattern(const void* p, size_t n) NLIB_NOEXCEPT;
92  bool AddWords(const char* str, size_t len) NLIB_NOEXCEPT;
93  bool AddWords(const char* str) NLIB_NOEXCEPT {
94  return AddWords(str, strlen(str));
95  }
96 
97  private:
98  struct TrieBuilderPrivate;
99  TrieBuilderPrivate* prv_;
101 };
102 
103 } // namespace succinct
104 NLIB_NAMESPACE_END
105 
106 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Trie)
107 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::TrieBuilder)
108 
109 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
110 #undef NLIB_VIS_PUBLIC
111 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
112 #endif
113 
114 #endif // INCLUDE_NN_NLIB_SUCCINCT_TRIE_H_
Trieオブジェクトを作成するためのクラスです。
Definition: Trie.h:82
rank/select操作をベースとした基本的なクラスが定義されています。
LOUDSを構築したり、LOUDSにアクセスしたりするためのクラスが定義されています。
void swap(Trie &rhs) noexcept
オブジェクトの内容をスワップします。
Definition: Trie.h:40
void Match(const char *cstr, MatchCallback callback, void *user_obj) noexcept
文字列を検査してTrieに登録されている文字列を検出します。
Definition: Trie.h:48
constexpr Trie() noexcept
コンストラクタです。
Definition: Trie.h:37
void Match(const char *cstr, MatchCallback callback) noexcept
Match(cstr, callback, NULL)を実行します。
Definition: Trie.h:51
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:179
void Match(const void *data, size_t n, MatchCallback callback) noexcept
Match(data, n, callback, NULL)を実行します。
Definition: Trie.h:56
~TrieBuilder() noexcept
デストラクタです。
Definition: Trie.h:85
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:290
LOUDSを利用したTrieの実装です。
Definition: Trie.h:35
#define NLIB_VIS_HIDDEN
関数やクラス等のシンボルをライブラリの外部に公開しません。
Definition: Platform_unix.h:88
bool AddWords(const char *str) noexcept
検出対象の文字列の集合が入った配列から文字列を追加します。文字列の区切りは改行(CRLFかLF)である必要が...
Definition: Trie.h:93
#define NLIB_DEPRECATED
関数等がdeprecatedになったことを示します。
Definition: Config.h:109
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:89
constexpr TrieBuilder() noexcept
コンストラクタです。
Definition: Trie.h:84
~Trie() noexcept
デストラクタです。
Definition: Trie.h:38
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:105
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:107
void MatchBackward(const void *data, size_t n, MatchCallback callback) noexcept
MatchBackward(data, n, callback, NULL)を実行します。
Definition: Trie.h:62
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
ストリーム(OutputStream)にバイナリを書き込むクラスです。
Definition: BinaryWriter.h:26
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:245
ストリーム(InputStream)からバイナリを読み込むクラスです。
Definition: BinaryReader.h:26
unsigned char nlib_byte_t
C++17以降でstd::byteにtypedefされる型です。
Definition: Platform.h:319
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:32
int errno_t
intのtypedefで、戻り値としてPOSIXのエラー値を返すことを示します。
Definition: NMalloc.h:37