HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_FSASymbolTable.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_FSASymbolTable.h ( UT Library, C++)
7  *
8  * COMMENTS: Insertion and deletion of symbols is incredibly expensive.
9  * Searching in the table is faster than other symbol tables (on
10  * most architectures).
11  *
12  */
13 
14 #ifndef __UT_FSASymbolTable__
15 #define __UT_FSASymbolTable__
16 
17 #include "UT_API.h"
18 #include "UT_Array.h"
19 #include "UT_DeepString.h"
20 #include "UT_FSA.h"
21 #include "UT_NonCopyable.h"
22 
23 template <typename ITEM_T>
25 {
26  struct SymbolStorage
27  {
28  SymbolStorage(const char *str, const ITEM_T &data)
29  : myThing(data)
30  , myString(str) {}
31 
32  ITEM_T myThing;
33  UT_DeepString myString;
34  };
35 
36 public:
37  UT_FSASymbolTable() : myDirty(true) {}
39 
41 
42  // Add a symbol to the table. Returns the string that would be returned
43  // by getStringReference() (this will be valid even after rebuid)
44  const char *addSymbol(const char *symbol, const ITEM_T &data)
45  {
46  myStorage.append(SymbolStorage(symbol, data));
47  myDirty = true;
48  return myStorage.last().myString;
49  }
50  int deleteSymbol(const char *symbol)
51  {
52  for (int i = 0; i < myStorage.entries(); i++)
53  {
54  if (myStorage(i).myString == symbol)
55  {
56  myStorage.removeIndex(i);
57  myDirty = true;
58  return 1;
59  }
60  }
61  return 0;
62  }
63  void clear()
64  {
65  myStorage.setCapacity(0);
66  myTable.clear();
67  myDirty = true;
68  }
69 
70  int findSymbol(const char *symbol, ITEM_T *datap) const
71  {
72  int idx;
73  if (myDirty) rebuild();
74  idx = myTable.findSymbol(symbol);
75  if (idx >= 0)
76  {
77  *datap = myStorage(idx).myThing;
78  return 1;
79  }
80  return 0;
81  }
82  int findSymbol(const UT_StringView &symbol, ITEM_T *datap) const
83  {
84  int idx;
85  if (myDirty) rebuild();
86  idx = myTable.findSymbol(symbol);
87  if (idx >= 0)
88  {
89  *datap = myStorage(idx).myThing;
90  return 1;
91  }
92  return 0;
93  }
94  int findSymbol(const UT_String &str, ITEM_T *datap) const
95  { return findSymbol(str.c_str(), datap); }
96  int findSymbol(const UT_StringRef &str, ITEM_T *datap) const
97  { return findSymbol(UT_StringView(str), datap); }
98 
99  unsigned entries() const { return myStorage.entries(); }
100  bool empty() const { return !myStorage.entries(); }
101 
102  bool contains(const char *symbol) const
103  { return myTable.contains(symbol); }
104  bool count(const char *symbol) const
105  { return myTable.count(symbol); }
106  void extractStrings(UT_StringArray &list) const
107  { myTable.extractStrings(list); }
108 
109  const char *getStringReference(const char *symbol)
110  {
111  int idx;
112  if (myDirty) rebuild();
113  idx = myTable.findSymbol(symbol);
114  return idx >= 0 ? myStorage(idx).myString : 0;
115  }
116 
117  int64 getMemoryUsage(bool inclusive) const
118  {
119  if (myDirty) rebuild();
120  int64 mem = inclusive ? sizeof(*this) : 0;
121  mem += myTable.getMemoryUsage(false);
122  mem += myStorage.getMemoryUsage(false);
123  return mem;
124  }
125 
127  int (*function)(const ITEM_T &, const char *, void *),
128  void *data) const
129  {
130  for (int i = 0; i < myStorage.entries(); i++)
131  {
132  if (!function(myStorage(i).myThing,
133  myStorage(i).myString, data))
134  return 0;
135  }
136  return 1;
137  }
138  int traverse(int (*function)(ITEM_T &, const char *, void *),
139  void *data)
140  {
141  for (int i = 0; i < myStorage.entries(); i++)
142  {
143  if (!function(myStorage(i).myThing,
144  myStorage(i).myString, data))
145  return 0;
146  }
147  return 1;
148  }
149 
150  void rebuild()
151  {
152  ut_FSA_Token *tokens;
153  int i;
154 
155  if (myDirty)
156  {
157  tokens = (ut_FSA_Token *)::malloc(
158  sizeof(ut_FSA_Token)*myStorage.entries());
159  for (i = 0; i < myStorage.entries(); i++)
160  tokens[i].set(i, myStorage(i).myString);
161 
162  myTable.build(myStorage.entries(), tokens, -1);
163  ::free(tokens);
164  myDirty = false;
165  }
166  }
167 
168 private:
169  void rebuild() const { (SYSconst_cast(this))->rebuild(); }
170 
171  UT_FSA myTable;
172  UT_Array<SymbolStorage> myStorage;
173  bool myDirty;
174 };
175 
176 #endif
T & last()
Definition: UT_Array.h:796
const char * getStringReference(const char *symbol)
int findSymbol(const char *symbol) const
unsigned entries() const
int traverseConst(int(*function)(const ITEM_T &, const char *, void *), void *data) const
int findSymbol(const char *symbol, ITEM_T *datap) const
int traverse(int(*function)(ITEM_T &, const char *, void *), void *data)
SYS_FORCE_INLINE T * SYSconst_cast(const T *foo)
Definition: SYS_Types.h:136
bool contains(const char *symbol) const
Definition: UT_FSA.h:89
void extractStrings(UT_StringArray &list) const
int deleteSymbol(const char *symbol)
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:657
exint removeIndex(exint index)
Definition: UT_Array.h:375
void setCapacity(exint new_capacity)
int count(const char *symbol) const
Definition: UT_FSA.h:91
const char * c_str() const
Definition: UT_String.h:508
int64 getMemoryUsage(bool inclusive) const
void extractStrings(UT_StringArray &list) const
A utility class to do read-only operations on a subset of an existing string.
Definition: UT_StringView.h:39
Definition: UT_FSA.h:54
void clear()
bool count(const char *symbol) const
#define UT_NON_COPYABLE(CLASS)
Define deleted copy constructor and assignment operator inside a class.
long long int64
Definition: SYS_Types.h:116
exint append()
Definition: UT_Array.h:142
int64 getMemoryUsage(bool inclusive) const
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:648
bool contains(const char *symbol) const
int findSymbol(const UT_StringRef &str, ITEM_T *datap) const
int findSymbol(const UT_String &str, ITEM_T *datap) const
bool build(const UT_StringArray &strings, const UT_IntArray &indices, int notfound_index=-1)
#define const
Definition: zconf.h:214
int findSymbol(const UT_StringView &symbol, ITEM_T *datap) const
Definition: format.h:895
const char * addSymbol(const char *symbol, const ITEM_T &data)