HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_FSA.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_FSA.h ( UT Library, C++)
7  *
8  * COMMENTS: Finite State Automata String Table
9  * This table takes a fixed set of strings and creates a FSA which is used
10  * for scanning the table. The integer value associated with each string
11  * can be found quite quickly. As well, a search for a string not in the
12  * table is especially efficient.
13  *
14  * The string table used to build the FSA can be destroyed after the table
15  * is constructed, unless, on the odd chance, you want to find out what
16  * strings are stored in the table.
17  */
18 
19 #ifndef __UT_FSA__
20 #define __UT_FSA__
21 
22 #include "UT_API.h"
23 #include <SYS/SYS_Types.h>
24 #include "UT_VectorTypes.h"
25 #include "UT_ValArray.h"
26 #include "UT_IntArray.h"
27 #include "UT_NonCopyable.h"
28 #include "UT_StringArray.h"
29 #include "UT_StringView.h"
30 
31 class UT_WorkBuffer;
32 
34 {
35 public:
36  ut_FSA_Token(int id=0, const char *token=0)
37  {
38  myId = id;
39  myToken = token;
40  }
42 
43  void set(int id, const char *token)
44  {
45  myToken = token;
46  myId = id;
47  }
48  int getId() const { return myId; }
49  const char *getToken() const { return myToken; }
50 private:
51  const char *myToken;
52  int myId;
53 };
54 
56 {
57 public:
58  UT_FSA();
59  ~UT_FSA();
60 
61  bool build(const UT_StringArray &strings, const UT_IntArray &indices,
62  int notfound_index = -1);
63  bool build(int ntokens, const ut_FSA_Token tokens[],
64  int notfound_index=-1);
65  void clear();
66 
67  /// Return the size of the symbol table
68  exint entries() const { return myEntries; }
69 
70  bool empty() const { return (myEntries == 0); }
71 
72  /// @{
73  /// Find a symbol in the map, returning the integer value associated with
74  /// the key.
75  int findSymbol(const char *symbol) const;
76  int findSymbol(const UT_StringView &symbol) const;
77  /// @}
78 
79  /// Return the integer associated with entries not in the map
80  int getNotFound() const { return myNotFound; }
81 
82  /// @{
83  /// Return whether a symbol exists
84  bool contains(const char *symbol) const
85  { return findSymbol(symbol) != myNotFound; }
86  bool count(const char *symbol) const
87  { return findSymbol(symbol) ? 1 : 0; }
88  /// @}
89 
90  int64 getMemoryUsage(bool inclusive) const;
91 
92  void dumpTables() const;
93 
94  // This method is used for validation. It is kind of expensive since it
95  // iterates over the entire space of the FSA for extraction.
96  void extractStrings(UT_StringArray &list) const;
97 
98  /// @private
99  /// Used internally
100  void resolveTree(const UT_IntArray &nexts,
101  const UT_IntArray &states,
102  const UT_IntArray &accepts,
103  const UT_ValArray<const char *> &remainders);
104 
105 private:
106  int *myAccept; // Acceptance states
107  int *myNexts; // Transition table
108  int *myValidate; // Verification states
109  char **myRemainder; // Remaining, unique text
110  int myNSize, myVSize, myASize, myRSize; // Sizes of arrays
111  int myEntries;
112  int myNotFound;
113 };
114 
115 #endif
const char * getToken() const
Definition: UT_FSA.h:49
GLsizei GLenum const void * indices
Definition: glcorearb.h:405
exint entries() const
Return the size of the symbol table.
Definition: UT_FSA.h:68
int getNotFound() const
Return the integer associated with entries not in the map.
Definition: UT_FSA.h:80
bool contains(const char *symbol) const
Definition: UT_FSA.h:84
#define UT_API
Definition: UT_API.h:13
ut_FSA_Token(int id=0, const char *token=0)
Definition: UT_FSA.h:36
GLuint id
Definition: glcorearb.h:654
long long int64
Definition: SYS_Types.h:107
A utility class to do read-only operations on a subset of an existing string.
Definition: UT_StringView.h:31
Definition: UT_FSA.h:55
int64 exint
Definition: SYS_Types.h:116
int getId() const
Definition: UT_FSA.h:48
void set(int id, const char *token)
Definition: UT_FSA.h:43
GLsizei const GLchar *const * strings
Definition: glcorearb.h:1932
bool empty() const
Definition: UT_FSA.h:70
bool count(const char *symbol) const
Definition: UT_FSA.h:86
~ut_FSA_Token()
Definition: UT_FSA.h:41