HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_SymbolTable.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_SymbolTable.h
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_SymbolTable_h__
12 #define __UT_SymbolTable_h__
13 
14 #include "UT_API.h"
15 #include <stdio.h>
16 #include <SYS/SYS_Types.h>
17 #include "UT_ContainerPrinter.h"
18 #include "UT_IteratorRange.h"
19 #include "UT_StringMap.h"
20 
21 #include <iterator>
22 #include <iosfwd>
23 
24 /// A UT_SymbolMap contains a UT_Map but provides the interface
25 /// required by what was UT_SymbolTable. Strings are passed as <tt>const char
26 /// *</tt>.
27 template <typename ITEM_T>
28 class UT_SymbolMap
29 {
30 public:
33  typedef typename MapType::iterator map_iterator;
34  typedef ITEM_T value_type;
35 
36  /// Constructor
37  explicit UT_SymbolMap()
38  : myMap()
39  {
40  }
41  /// Destructor
43  {
44  clear();
45  }
46 
47  /// Add a symbol to the map
48  void addSymbol(const UT_StringHolder &symbol, const ITEM_T &data)
49  {
50  (*this)[symbol] = data;
51  }
52  /// Find a symbol in the map. If the symbol is found, the data pointer
53  /// passed in will be assigned to the ITEM_T in the map.
54  bool findSymbol(const UT_StringRef &symbol, ITEM_T *datap) const
55  {
56  const_map_iterator it = myMap.find(symbol);
57  if (it != myMap.end())
58  {
59  if (datap)
60  *datap = it->second;
61  return true;
62  }
63  return false;
64  }
65 
66  /// Find a symbol and return an iterator. Returns map_end() if the symbol
67  /// is not found in the map.
68  /// @{
70  {
71  return myMap.find(symbol);
72  }
73  const_map_iterator find(const UT_StringRef &symbol) const
74  {
75  return myMap.find(symbol);
76  }
77  /// @}
78 
79  /// Check if a symbol exists
80  bool contains(const UT_StringRef &symbol) const
81  { return myMap.count(symbol) > 0; }
82  /// Find out how many times a symbol exists (this will be either 0 or 1).
83  exint count(const UT_StringRef &symbol) const
84  { return myMap.count(symbol); }
85 
86  /// Erase a symbol from the map
87  bool deleteSymbol(const UT_StringRef &symbol)
88  {
89  myMap.erase(symbol);
90  return true;
91  }
92  /// @{
93  /// Erase a symbol from the map
94  exint erase(const UT_StringRef &symbol)
95  {
96  return myMap.erase(symbol);
97  }
99  {
100  return myMap.erase(it);
101  }
102  /// @}
103  /// Clear the map
104  void clear()
105  {
106  myMap.clear();
107  }
108 
109  /// Add a symbol and return the string reference
110  const char *addSymbolAndGetReference(const UT_StringHolder &symbol,
111  const ITEM_T &data)
112  {
113  addSymbol(symbol, data);
114 
115  UT_ASSERT_P(myMap.find(symbol) != myMap.end());
116  return myMap.find(symbol)->first.c_str();
117  }
118 
119 
120  /// @{
121  /// Query the number of elements in the map
122  exint entries() const { return myMap.size(); }
123  exint size() const { return myMap.size(); }
124  /// @}
125 
126  /// @{
127  /// Information about the buckets
128  exint bucket_count() const { return myMap.bucket_count(); }
129  exint capacity() const
130  { return exint(myMap.bucket_count()*myMap.max_load_factor()); }
131  /// @}
132 
133  /// Check if the map is empty
134  bool empty() const { return myMap.empty(); }
135 
136  /// Retrieve an entry in the table by name, creating it if it doesn't
137  /// already exist.
138  ITEM_T &operator[](const UT_StringHolder &symbol)
139  {
140  return myMap[symbol];
141  }
142  ITEM_T &insert(const UT_StringHolder &name, const ITEM_T &item)
143  {
144  // Assign and return the reference in the map
145  return ((*this)[name] = item);
146  }
147 
148  /// Call this method when you're adding entries to a table inside a loop
149  /// and you know how many entries you'll be adding. This will create at
150  /// least @c size buckets but also ensure the load factor is less than the
151  /// maximum load factor.
153  { myMap.rehash(size); }
154 
155  /// Get current load factor
156  float getLoadFactor() const
157  { return myMap.load_factor(); }
158 
159  /// @{
160  /// Adjust the maximum/minimum load factors
161  /// The table will automatically rebuild itself to keep the load factor
162  /// within the specified range. A minimum load factor of 0 means that
163  /// the table will never shrink when elements are deleted from it.
164  float getMaxLoadFactor() const
165  { return myMap.max_load_factor(); }
166  void setMaxLoadFactor(float f)
167  { myMap.max_load_factor(f); }
168  float getMinLoadFactor() const
169  { return 0.; }
170  void setMinLoadFactor(float) {}
171  /// @}
172 
173  /// Merge the specified table with ourselves.
174  void mergeTable(const UT_SymbolMap &table)
175  {
176  const_map_iterator it, last;
177  last = table.map_end();
178  for (it = table.map_begin(); it != last; ++it)
179  (*this)[it->first] = it->second;
180  }
181 
182  /// "getStringReference" returns a pointer to the actual string that
183  /// is maintained in the symbol table. This can be used to implement
184  /// a shared string symbol table.
185  const char *getStringReference(const UT_StringRef &symbol)
186  {
187  const_map_iterator it = myMap.find(symbol);
188  if (it == map_end())
189  {
190  // If we don't have an entry, we create one. Duh.
191  return addSymbolAndGetReference(symbol, ITEM_T());
192  }
193  return it->first.c_str();
194  }
195 
196  /// Returns a unique key based using the passed-in string as a prefix.
197  UT_StringHolder makeUniqueKey(const char *name) const
198  {
199  if (!UTisstring(name))
200  return UT_StringHolder();
201 
202  UT_String s(name);
203  while (myMap.find(s) != myMap.end())
205 
207  n.adoptFromString(s);
208  return n;
209  }
210 
211  /// Return an approximation of how much memory we use
212  int64 getMemoryUsage(bool inclusive) const
213  {
214  int64 mem = inclusive ? sizeof(*this) : 0;
215  mem += myMap.getMemoryUsage(false);
216  // The keys store copies of the strings if SAFE_STRINGS, so we need to count them
217  for (const_map_iterator it = myMap.begin(); it != myMap.end(); ++it)
218  mem += it->first.getMemoryUsage(false);
219  return mem;
220  }
221 
222  /// @{
223  /// "traverse" invokes the given function with every member of the symbol
224  /// table. The order of traversal is undefined. If the function returns a
225  /// non-zero value the traversal continues. If it returns zero then
226  /// traversal stops. The return value is zero if the traversal was
227  /// interupted and one otherwise.
228  ///
229  /// Call traverseConst() if you will not be removing things from the
230  /// table while traversing, and traverse() if you might be. It is only
231  /// safe to remove the current item when using traverse() -- not other
232  /// items. If you call traverse() and add something to the table, you
233  /// may or may not encounter it later in the traversal.
235  int (*function)(ITEM_T &, const char *, void *),
236  void *data) const
237  {
238  for (const_map_iterator it = map_begin(); it != map_end(); ++it)
239  {
240  if (!function(const_cast<ITEM_T &>(it->second),
241  it->first.c_str(), data))
242  {
243  return 0;
244  }
245  }
246  return 1;
247  }
248  int traverse(int (*function)(ITEM_T &, const char *, void *),
249  void *data)
250  {
251  for (map_iterator it = map_begin(); it != map_end(); )
252  {
253  // Increment before calling the functor to ensure
254  // that 'it' remains valid even if we delete the
255  // current element. It's still unsafe to delete
256  // the next element.
257  map_iterator curr = it++;
258  if (!function(curr->second, curr->first.c_str(), data))
259  {
260  return 0;
261  }
262  }
263  return 1;
264  }
265  /// @}
266 
267  /// Iterator conforming to Houdini's atEnd(), advance() interface
268  template<typename T, typename IT>
269  class base_iterator :
270  public std::iterator<std::forward_iterator_tag, T>
271  {
272  public:
273  typedef T& reference;
274  typedef T* pointer;
275 
277  : myIt()
278  , myEnd()
279  {}
280 
281  // Converting constructor to const_iterator
282  template<typename ET, typename EIT>
284  : myIt(src.myIt), myEnd(src.myEnd) {}
285 
286  reference value() const { return const_cast<T &>(myIt->second); }
287  reference operator*() const { return thing(); }
288  pointer operator->() const { return &thing(); }
289 
290  reference thing() const { return value(); }
291 
292  const UT_StringHolder &key() const
293  { return myIt->first; }
294  const char *name() const
295  { return key().c_str(); }
296 
298  {
299  return myIt == cmp.myIt;
300  }
302  { return !(*this == cmp); }
303 
304  bool atEnd() const
305  {
306  return myIt == myEnd;
307  }
308 
310  {
311  ++myIt;
312  return *this;
313  }
314 
316  {
317  myIt = src.myIt;
318  myEnd = src.myEnd;
319  return *this;
320  }
321 
322  private:
323  base_iterator(const IT &it,
324  const IT &end)
325  : myIt(it)
326  , myEnd(end)
327  {}
328 
329  IT myIt, myEnd;
330 
331  friend class UT_SymbolMap<ITEM_T>;
332  };
333 
334  typedef base_iterator<ITEM_T, map_iterator> iterator;
335  typedef base_iterator<const ITEM_T, const_map_iterator> const_iterator;
336 
338 
339  iterator begin() { return iterator(myMap.begin(), myMap.end()); }
340  iterator end() { return iterator(myMap.end(), myMap.end()); }
341  const_iterator begin() const { return const_iterator(myMap.begin(), myMap.end()); }
342  const_iterator end() const { return const_iterator(myMap.end(), myMap.end()); }
343 
344  const_map_iterator map_begin() const { return myMap.begin(); }
345  const_map_iterator map_end() const { return myMap.end(); }
346  map_iterator map_begin() { return myMap.begin(); }
347  map_iterator map_end() { return myMap.end(); }
348 
350  { return UTmakeRange(myMap.begin(), myMap.end()); }
352  { return UTmakeRange(myMap.begin(), myMap.end()); }
353 
354  /// Write out some statistics pertaining to the underlying map container to
355  /// the output stream given.
356  void outputStats(std::ostream &os) const;
357 protected:
358  template<typename OS, typename T>
359  friend OS &operator<<(OS &os, const UT_SymbolMap<T> &d);
360 
362 };
363 
364 template <typename T>
365 void
366 UT_SymbolMap<T>::outputStats(std::ostream &os) const
367 {
368  os << " Table Size: " << size() << "\n";
369  os << " Bucket Count: " << bucket_count() << "\n";
370  os << " Capacity: " << capacity() << "\n";
371  os << " Load Factor: " << getLoadFactor() << "\n";
372  os << "Max Load Factor: " << getMaxLoadFactor() << "\n";
373 }
374 
375 template<typename OS, typename T>
376 inline OS &
377 operator<<(OS &os, const UT_SymbolMap<T> &d)
378 {
379  os << d.myMap;
380  return os;
381 }
382 
383 
384 #endif
exint capacity() const
void adoptFromString(UT_String &str)
ITEM_T & operator[](const UT_StringHolder &symbol)
UT_IteratorRange< map_iterator > map_range()
ITEM_T value_type
exint entries() const
void incrementNumberedName()
iterator erase(const_iterator pos)
Definition: UT_StringMap.h:57
ITEM_T & insert(const UT_StringHolder &name, const ITEM_T &item)
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:133
void setMinLoadFactor(float)
UT_IteratorRange< IterT > UTmakeRange(IterT &&b, IterT &&e)
void setMaxLoadFactor(float f)
int64 getMemoryUsage(bool inclusive) const
Return an approximation of how much memory we use.
const_map_iterator find(const UT_StringRef &symbol) const
void outputStats(std::ostream &os) const
bool operator==(const base_iterator< T, IT > &cmp) const
base_iterator(const base_iterator< ET, EIT > &src)
GLsizeiptr size
Definition: glcorearb.h:663
int traverseConst(int(*function)(ITEM_T &, const char *, void *), void *data) const
MapType::const_iterator const_map_iterator
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
base_iterator< const ITEM_T, const_map_iterator > const_iterator
long long int64
Definition: SYS_Types.h:100
base_iterator< ITEM_T, map_iterator > iterator
const char * name() const
UT_StringHolder makeUniqueKey(const char *name) const
Returns a unique key based using the passed-in string as a prefix.
GLdouble n
Definition: glcorearb.h:2007
GLfloat f
Definition: glcorearb.h:1925
iterator end()
const_iterator traverser
int64 exint
Definition: SYS_Types.h:109
void reserveTableSize(exint size)
exint erase(const UT_StringRef &symbol)
GLuint GLuint end
Definition: glcorearb.h:474
~UT_SymbolMap()
Destructor.
base_iterator & operator++()
map_iterator find(const UT_StringRef &symbol)
base_iterator & operator=(const base_iterator< T, IT > &src)
SYS_FORCE_INLINE const char * c_str() const
iterator begin()
map_iterator map_begin()
GLboolean * data
Definition: glcorearb.h:130
GLuint const GLchar * name
Definition: glcorearb.h:785
Iterator conforming to Houdini's atEnd(), advance() interface.
UT_StringMap< ITEM_T > MapType
bool contains(const UT_StringRef &symbol) const
Check if a symbol exists.
int traverse(int(*function)(ITEM_T &, const char *, void *), void *data)
exint count(const UT_StringRef &symbol) const
Find out how many times a symbol exists (this will be either 0 or 1).
bool empty() const
Check if the map is empty.
map_iterator erase(const_map_iterator it)
void mergeTable(const UT_SymbolMap &table)
Merge the specified table with ourselves.
int cmp(T a, T b)
Definition: ImathFun.h:119
const_iterator end() const
const_map_iterator map_begin() const
UT_SymbolMap()
Constructor.
reference value() const
const_map_iterator map_end() const
const_iterator begin() const
exint size() const
SYS_FORCE_INLINE bool UTisstring(const char *s)
Definition: UT_String.h:58
const UT_StringHolder & key() const
const char * addSymbolAndGetReference(const UT_StringHolder &symbol, const ITEM_T &data)
Add a symbol and return the string reference.
map_iterator map_end()
bool findSymbol(const UT_StringRef &symbol, ITEM_T *datap) const
reference thing() const
bool operator!=(const base_iterator< T, IT > &cmp) const
UT_IteratorRange< const_map_iterator > map_range() const
bool deleteSymbol(const UT_StringRef &symbol)
Erase a symbol from the map.
const char * getStringReference(const UT_StringRef &symbol)
reference operator*() const
Parent::iterator iterator
Definition: UT_StringMap.h:51
float getMaxLoadFactor() const
MapType::iterator map_iterator
Parent::const_iterator const_iterator
Definition: UT_StringMap.h:50
float getLoadFactor() const
Get current load factor.
void addSymbol(const UT_StringHolder &symbol, const ITEM_T &data)
Add a symbol to the map.
GLenum src
Definition: glcorearb.h:1792
exint bucket_count() const
float getMinLoadFactor() const