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 #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_
Class to create a Trie object.
Definition: Trie.h:83
Defines the basic classes that form the basis to Rank and Select operations.
Defines the class for constructing and accessing a LOUDS succinct tree.
constexpr Trie() noexcept
Instantiates the object with default parameters (default constructor). Requires initialization with I...
Definition: Trie.h:38
void Match(const char *cstr, MatchCallback callback) noexcept
A parameter omitted version of the above function which passes nullptr as a parameter.
Definition: Trie.h:47
#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:183
void Match(const void *data, size_t n, MatchCallback callback) noexcept
A parameter omitted version of the above function which passes nullptr as a parameter.
Definition: Trie.h:51
std::unique_ptr< Trie > Build2() noexcept
Creates the Trie object and return it with unique_ptr.
Definition: Trie.h:92
~TrieBuilder() noexcept
Destructor.
Definition: Trie.h:86
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:282
Implements Trie using LOUDS.
Definition: Trie.h:36
#define NLIB_VIS_HIDDEN
Symbols for functions and classes are not made available outside of the library.
Definition: Platform_unix.h:86
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:97
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:87
Defines the class that resembles std::vector but can store objects that cannot be copied...
constexpr TrieBuilder() noexcept
Instantiates the object with default parameters (default constructor). Requires initialization with I...
Definition: Trie.h:85
~Trie() noexcept
Destructor.
Definition: Trie.h:39
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:109
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:111
void MatchBackward(const void *data, size_t n, MatchCallback callback) noexcept
A parameter omitted version of the above function which passes nullptr as a parameter.
Definition: Trie.h:57
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:250
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:314
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