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