nlib
Trie.h
Go to the documentation of this file.
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_
Class to create a Trie object.
Definition: Trie.h:82
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:40
void Match(const char *cstr, MatchCallback callback, void *user_obj) noexcept
Inspects the string to detect the target string registered in Trie.
Definition: Trie.h:48
constexpr Trie() noexcept
Instantiates the object.
Definition: Trie.h:37
void Match(const char *cstr, MatchCallback callback) noexcept
Runs Match(cstr, callback, NULL).
Definition: Trie.h:51
#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:179
void Match(const void *data, size_t n, MatchCallback callback) noexcept
Runs Match(data, n, callback, NULL).
Definition: Trie.h:56
~TrieBuilder() noexcept
Destructor.
Definition: Trie.h:85
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:290
Implements Trie using LOUDS.
Definition: Trie.h:35
#define NLIB_VIS_HIDDEN
Symbols for functions and classes are not made available outside of the library.
Definition: Platform_unix.h:88
bool AddWords(const char *str) noexcept
Adds a string from an array containing a set of target strings. The strings must be delimited by newl...
Definition: Trie.h:93
#define NLIB_DEPRECATED
Indicates that a function or something has been deprecated.
Definition: Config.h:109
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:89
constexpr TrieBuilder() noexcept
Instantiates the object.
Definition: Trie.h:84
~Trie() noexcept
Destructor.
Definition: Trie.h:38
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:105
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:107
void MatchBackward(const void *data, size_t n, MatchCallback callback) noexcept
Runs MatchBackward(data, n, callback, NULL).
Definition: Trie.h:62
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:26
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:245
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
unsigned char nlib_byte_t
This type will be defined as std::byte in a typedef of C++17 or later.
Definition: Platform.h:319
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:32
int errno_t
Indicates with an int-type typedef that a POSIX error value is returned as the return value...
Definition: NMalloc.h:37