HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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_FSA.h"
19 #include "UT_Array.h"
20 #include "UT_DeepString.h"
21 
22 template <typename ITEM_T>
24  struct SymbolStorage
25  {
26  SymbolStorage(const char *str, const ITEM_T &data)
27  : myThing(data)
28  , myString(str) {}
29 
30  ITEM_T myThing;
31  UT_DeepString myString;
32  };
33 
34 public:
35  UT_FSASymbolTable() : myDirty(true) {}
37 
38  // Add a symbol to the table. Returns the string that would be returned
39  // by getStringReference() (this will be valid even after rebuid)
40  const char *addSymbol(const char *symbol, const ITEM_T &data)
41  {
42  myStorage.append(SymbolStorage(symbol, data));
43  myDirty = true;
44  return myStorage.last().myString;
45  }
46  int deleteSymbol(const char *symbol)
47  {
48  for (int i = 0; i < myStorage.entries(); i++)
49  {
50  if (myStorage(i).myString == symbol)
51  {
52  myStorage.removeIndex(i);
53  myDirty = true;
54  return 1;
55  }
56  }
57  return 0;
58  }
59  void clear()
60  {
61  myStorage.setCapacity(0);
62  myTable.clear();
63  myDirty = true;
64  }
65 
66  int findSymbol(const char *symbol, ITEM_T *datap) const
67  {
68  int idx;
69  if (myDirty) rebuild();
70  idx = myTable.findSymbol(symbol);
71  if (idx >= 0)
72  {
73  *datap = myStorage(idx).myThing;
74  return 1;
75  }
76  return 0;
77  }
78  int findSymbol(const UT_StringView &symbol, ITEM_T *datap) const
79  {
80  int idx;
81  if (myDirty) rebuild();
82  idx = myTable.findSymbol(symbol);
83  if (idx >= 0)
84  {
85  *datap = myStorage(idx).myThing;
86  return 1;
87  }
88  return 0;
89  }
90 
91  unsigned entries() const { return myStorage.entries(); }
92  bool empty() const { return !myStorage.entries(); }
93 
94  bool contains(const char *symbol) const
95  { return myTable.contains(symbol); }
96  bool count(const char *symbol) const
97  { return myTable.count(symbol); }
98  void extractStrings(UT_StringArray &list) const
99  { myTable.extractStrings(list); }
100 
101  const char *getStringReference(const char *symbol)
102  {
103  int idx;
104  if (myDirty) rebuild();
105  idx = myTable.findSymbol(symbol);
106  return idx >= 0 ? myStorage(idx).myString : 0;
107  }
108 
109  int64 getMemoryUsage(bool inclusive) const
110  {
111  if (myDirty) rebuild();
112  int64 mem = inclusive ? sizeof(*this) : 0;
113  mem += myTable.getMemoryUsage(false);
114  mem += myStorage.getMemoryUsage(false);
115  return mem;
116  }
117 
119  int (*function)(const ITEM_T &, const char *, void *),
120  void *data) const
121  {
122  for (int i = 0; i < myStorage.entries(); i++)
123  {
124  if (!function(myStorage(i).myThing,
125  myStorage(i).myString, data))
126  return 0;
127  }
128  return 1;
129  }
130  int traverse(int (*function)(ITEM_T &, const char *, void *),
131  void *data)
132  {
133  for (int i = 0; i < myStorage.entries(); i++)
134  {
135  if (!function(myStorage(i).myThing,
136  myStorage(i).myString, data))
137  return 0;
138  }
139  return 1;
140  }
141 
142  void rebuild()
143  {
144  ut_FSA_Token *tokens;
145  int i;
146 
147  if (myDirty)
148  {
149  tokens = (ut_FSA_Token *)::malloc(
150  sizeof(ut_FSA_Token)*myStorage.entries());
151  for (i = 0; i < myStorage.entries(); i++)
152  tokens[i].set(i, myStorage(i).myString);
153 
154  myTable.build(myStorage.entries(), tokens, -1);
155  ::free(tokens);
156  myDirty = false;
157  }
158  }
159 
160 private:
161  void rebuild() const { (SYSconst_cast(this))->rebuild(); }
162 
163  UT_FSA myTable;
164  UT_Array<SymbolStorage> myStorage;
165  bool myDirty;
166 };
167 
168 #endif
T & last()
Definition: UT_Array.h:584
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
bool empty() 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:120
bool contains(const char *symbol) const
Definition: UT_FSA.h:84
void extractStrings(UT_StringArray &list) const
int deleteSymbol(const char *symbol)
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:455
exint removeIndex(exint index)
Definition: UT_Array.h:225
png_uint_32 i
Definition: png.h:2877
int64 getMemoryUsage(bool inclusive) const
void extractStrings(UT_StringArray &list) const
long long int64
Definition: SYS_Types.h:100
A utility class to do read-only operations on a subset of an existing string.
Definition: UT_StringView.h:30
void setCapacity(exint newcapacity)
Definition: UT_ArrayImpl.h:751
Definition: UT_FSA.h:55
void clear()
bool count(const char *symbol) const
GLboolean * data
Definition: glcorearb.h:130
int64 getMemoryUsage(bool inclusive) const
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:446
bool contains(const char *symbol) const
exint append(void)
Definition: UT_Array.h:95
bool build(const UT_StringArray &strings, const UT_IntArray &indices, int notfound_index=-1)
bool count(const char *symbol) const
Definition: UT_FSA.h:86
int findSymbol(const UT_StringView &symbol, ITEM_T *datap) const
const char * addSymbol(const char *symbol, const ITEM_T &data)