HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_HashTable.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_HashTable.h
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_HashTable_h__
12 #define __UT_HashTable_h__
13 
14 #include "UT_API.h"
15 #include <stdio.h>
16 #include <iosfwd>
17 #include <SYS/SYS_Deprecated.h>
18 #include <SYS/SYS_Types.h>
19 #include "UT_ThingList.h"
20 #include "UT_Hash.h"
21 
23 
25 {
26 public:
27  explicit UT_HashTable();
28  virtual ~UT_HashTable();
29 
30  // Set this to true before adding any items to the hash table if your
31  // hash function implements a proper strcmp() (returning -1 for <, 0 for =
32  // and 1 for >). This can shorten adds and queries to buckets with more
33  // than 1 entry.
34  void useOrderedLists(bool ordered);
35 
36  void addSymbol(const UT_Hash& symbol, const UT_Thing &data);
37  int findSymbol(const UT_Hash& symbol, UT_Thing *datap,
38  const UT_Hash **hash_symbol = 0) const;
39 
40  int contains(const UT_Hash &symbol) const
41  { UT_Thing value; return findSymbol(symbol, &value); }
42 
43  int count(const UT_Hash &symbol) const
44  { return contains(symbol) ? 1 : 0; }
45 
46  template <typename T>
47  T *findPointer(const UT_Hash &symbol) const
48  {
49  UT_Thing thing;
50  if (!findSymbol(symbol, &thing))
51  return NULL;
52  return thing.template asPointer<T>();
53  }
54 
55  int deleteSymbol(const UT_Hash& symbol);
56  int moveSymbol(const UT_Hash &oldsymbol,
57  const UT_Hash &newsymbol);
58  void clear();
59 
60  unsigned entries() const { return myNbrEntries; }
61  unsigned size() const { return myNbrEntries; }
62  bool empty() const { return !myNbrEntries; }
63 
64  // Retrieve an entry in the table, creating it if it doesn't already exist.
65  UT_Thing &operator[](const UT_Hash& symbol);
66 
67  // Call this method when you're adding entries to a table inside a loop
68  // and you know how many entries you'll be adding.
69  void reserveTableSize(int size);
70 
71  // The table will automatically rebuild itself to keep the load factor
72  // within the specified range. A minimum load factor of 0 means that
73  // the table will never shrink when elements are deleted from it.
74  float getMaxLoadFactor() const { return myMaxLoadFactor; }
75  void setMaxLoadFactor(float max_load_factor);
76  float getMinLoadFactor() const { return myMinLoadFactor; }
77  void setMinLoadFactor(float min_load_factor);
78 
79  // Merge the specified table with ourselves.
80  void mergeTable(const UT_HashTable &table);
81 
82  // "getHashReference" returns a pointer to the actual UT_Hash that
83  // is maintained in the hash table. This can be used to implement
84  // a shared hash symbol table.
85  const UT_Hash *getHashReference(const UT_Hash &hash);
86 
87  void outputStats(FILE *output) const;
88  void outputStats(std::ostream &os) const;
89  void dumpTable(FILE *output) const;
90 
91  int64 getMemoryUsage(bool inclusive) const;
92 
93  // "traverse" invokes the given function with every member of the
94  // hash table. The order of traversal is undefined. If the function
95  // returns a non-zero value the traversal continues. If it returns
96  // zero then traversal stops. The return value is zero if the traversal
97  // was interupted and one otherwise.
98  //
99  // Call traverseConst() if you will not be removing things from the table
100  // while traversing, and traverse() if you might be. If you call traverse()
101  // and add something to the table, you may or may not encounter it later
102  // in the traversal.
103  int traverseConst(
104  int (*function)(UT_Thing &, const UT_Hash&, void *),
105  void *data) const;
106  int traverse(int (*function)(UT_Thing &, const UT_Hash&, void *),
107  void *data);
108 
110  {
111  public:
113  : myCurrList(0), myEndList(0)
114  { }
116  { *this = src; }
118  { }
119 
120  UT_Thing &thing() const
121  { return myCurrEntry.thing(); }
122  UT_Hash *hash() const
123  { return myCurrEntry.hash(); }
124 
125  int operator==(const traverser &cmp) const
126  {
127  return ((!myCurrList && !cmp.myCurrList) ||
128  ((myCurrList == cmp.myCurrList) &&
129  (myCurrEntry == cmp.myCurrEntry)));
130  }
131  int operator!=(const traverser &cmp) const
132  { return !(*this == cmp); }
133 
134  bool atEnd() const
135  {
136  return !myCurrList;
137  }
138 
140  {
141  advance();
142  return *this;
143  }
145  {
146  advance();
147  return *this;
148  }
149 
151  {
152  myCurrList = src.myCurrList;
153  myEndList = src.myEndList;
154  myCurrEntry = src.myCurrEntry;
155  return *this;
156  }
157 
158  void advance()
159  {
160  if( ++myCurrEntry == myCurrList->end() )
161  {
162  ++myCurrList;
163  advanceToNextList();
164  }
165  }
166 
167  private:
168  traverser(const UT_ThingList *list, const UT_ThingList *endlist)
169  : myCurrList(list), myEndList(endlist)
170  { advanceToNextList(); }
171 
172  void advanceToNextList()
173  {
174  while( myCurrList != myEndList &&
175  myCurrList->begin() == myCurrList->end() )
176  ++myCurrList;
177  if( myCurrList == myEndList )
178  myCurrList = 0;
179  else
180  myCurrEntry = myCurrList->begin();
181  }
182 
183  const UT_ThingList *myCurrList;
184  const UT_ThingList *myEndList;
185  UT_ThingList::traverser myCurrEntry;
186 
187  friend class UT_HashTable;
188  };
189 
190  traverser begin() const
191  {
192  if( myTable )
193  return traverser(myTable, myTable + mySize);
194  return traverser(); // same as end()
195  }
196  traverser end() const
197  { return traverser(); }
198 
199 private:
200  enum UT_AdjustType { UT_ADJUST_INCREASE, UT_ADJUST_DECREASE };
201  void adjustTableSize(UT_AdjustType adjust_type);
202  void allocateTableOfNewSize(int size);
203 
204  // Data:
205  UT_ThingList *myTable;
206  int mySize;
207  unsigned int myNbrEntries;
208  fpreal myMaxLoadFactor;
209  fpreal myMinLoadFactor;
210  bool myUseOrdered;
211  bool myIsTraversing;
212 };
213 
215 
216 #endif
int contains(const UT_Hash &symbol) const
Definition: UT_HashTable.h:40
Unsorted map container.
Definition: UT_Map.h:83
unsigned size() const
Definition: UT_HashTable.h:61
#define SYS_DEPRECATED_PUSH_DISABLE()
#define SYS_DEPRECATED_POP_DISABLE()
float getMaxLoadFactor() const
Definition: UT_HashTable.h:74
int count(const UT_Hash &symbol) const
Definition: UT_HashTable.h:43
UT_Thing & thing() const
Definition: UT_HashTable.h:120
#define UT_API
Definition: UT_API.h:12
T * findPointer(const UT_Hash &symbol) const
Definition: UT_HashTable.h:47
traverser(const traverser &src)
Definition: UT_HashTable.h:115
traverser & operator++()
Definition: UT_HashTable.h:139
int operator!=(const traverser &cmp) const
Definition: UT_HashTable.h:131
GLsizeiptr size
Definition: glcorearb.h:663
#define SYS_DEPRECATED_REPLACE(__V__, __R__)
long long int64
Definition: SYS_Types.h:106
traverser & operator++(int)
Definition: UT_HashTable.h:144
UT_Hash * hash() const
Definition: UT_HashTable.h:122
GLboolean * data
Definition: glcorearb.h:130
virtual unsigned hash() const =0
int cmp(T a, T b)
Definition: ImathFun.h:119
GLsizei const GLfloat * value
Definition: glcorearb.h:823
double fpreal
Definition: SYS_Types.h:269
float getMinLoadFactor() const
Definition: UT_HashTable.h:76
traverser begin() const
Definition: UT_HashTable.h:190
traverser & operator=(const traverser &src)
Definition: UT_HashTable.h:150
traverser end() const
Definition: UT_HashTable.h:196
bool empty() const
Definition: UT_HashTable.h:62
int operator==(const traverser &cmp) const
Definition: UT_HashTable.h:125
unsigned entries() const
Definition: UT_HashTable.h:60
GLenum src
Definition: glcorearb.h:1792