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 
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_
Class to create a Trie object.
Definition: Trie.h:75
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:38
Trie() noexcept
Instantiates the object.
Definition: Trie.h:35
#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:163
void Match(const char *cstr, MatchCallback callback, void *user_obj=NULL) noexcept
Inspects the string to detect the target string registered in Trie.
Definition: Trie.h:46
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:227
Implements Trie using LOUDS.
Definition: Trie.h:33
#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:84
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:89
TrieBuilder() noexcept
Instantiates the object.
Definition: Trie.h:77
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:99
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:229
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:31
int errno_t
Indicates with an int-type typedef that a POSIX error value is returned as the return value...
Definition: NMalloc.h:37