HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_IndexedHashMap.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_IndexedHashMap.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_IndexedHashMap__
12 #define __UT_IndexedHashMap__
13 
14 #include "UT_API.h"
15 #include <SYS/SYS_AtomicInt.h>
16 #include "UT_Assert.h"
17 #include "UT_Array.h"
18 #include "UT_VectorTypes.h"
19 #include "UT_ConcurrentHashMap.h"
20 #include "UT_ConcurrentVector.h"
21 #include "UT_ConcurrentQueue.h"
22 
23 /// Each item in the shared map is assigned a unique id
25 
26 /// @brief A thread-safe hash map which stores indexed shared items
27 ///
28 /// Each item in the hash map is reference counted. That is, if objects are
29 /// added multiple times, only a single object will be stored in the map.
30 ///
31 /// Removing an item from the hash map (by id or key) will decrement the
32 /// reference count on the item. When no longer referenced, the map will
33 /// delete the item.
34 ///
35 /// When the map stores 'ids', each item is assigned a unique id
36 /// (UT_IndexedHashMapItemId). The item can then be retrieved efficiently from
37 /// the map using the id (UT_IndexedHashMap::get())
38 ///
39 /// Many methods on the map are thread-safe. Some methods are not (and are
40 /// noted in the comments).
41 ///
42 /// The KEY template parameter needs to have: @code
43 /// KEY(const KEY &src); // The copy constructor
44 /// uint hash() const; // A hash method
45 /// bool isEqual(const KEY &src) const; // A comparison operator
46 /// @endcode
48 {
49 public:
50  typedef void InternalKeyT; // Internal key type
51  typedef void InternalItemT; // Internal item type
52 
53 protected:
54  virtual uint hash(const InternalKeyT *key) const = 0;
55  virtual bool areKeysEqual(const InternalKeyT *k1,
56  const InternalKeyT *k2) const = 0;
57  virtual InternalKeyT *copyKey(const InternalKeyT *key) const = 0;
58  virtual void deleteKey(InternalKeyT *key) const = 0;
59 
60  virtual InternalItemT *newItem(const InternalKeyT *key) const = 0;
61  virtual void deleteItem(InternalItemT *item) const = 0;
62  virtual bool isItemLessThan(const InternalItemT *a,
63  const InternalItemT *b) const = 0;
64 
65 public:
66  /// If @c store_ids is true, each item stored in the map will be given a
67  /// unique id of type UT_IndexedHashMapItemId. These id's can be used to
68  /// perform efficient lookup of items in the map.
69  ///
70  /// If the @c store_ids parameter is false, then elements in the shared map
71  /// will not store id's. The ids for the elements will always be -1
72  /// (invalid). The map won't store the structures required for indexed
73  /// lookup, saving some memory and allowing some operations to be slightly
74  /// more efficient. Operations which are invalid for maps that don't store
75  /// id's are noted in the comments).
76  UT_IndexedHashMap(bool store_ids);
77  virtual ~UT_IndexedHashMap();
78 
79  /// Clear the map
80  /// @note This is @b not thread-safe
81  void clear();
82 
83  /// Return the number of entries in the map.
84  /// @note This is @b not thread-safe
85  exint entries() const { return myMap.size(); }
86 
87  /// Return whether the map is empty
88  bool empty() const { return myMap.empty(); }
89 
90  /// Return approximate memory usage (not including key or item storage)
91  int64 getMemoryUsage(bool inclusive) const;
92 
93  /// Return the maximum possible UT_IndexedHashMapItemId stored in the map.
94  /// This returns an upper bound and is not exact.
95  /// @note This is @b not thread-safe
96  /// @note Not supported if id's are not stored in the map
98  { return SYSmax(1, getListSize())-1; }
99 
100  /// Return the "occupancy" of the map.
101  /// @note This is @b not thread-safe
102  /// @note Not supported if id's are not stored in the map
104  {
105  exint lsize = getListSize();
106  exint hsize = myHoles.unsafe_size();
107  if (!lsize || !hsize)
108  return 1; // Fully occupied
109  UT_ASSERT(lsize > hsize);
110  return (fpreal)(lsize-hsize)/(fpreal)lsize;
111  }
112 
113  /// Class used by compacting to map from the previous id to the new id.
114  /// After compacting, this class stores a map of the old id's to the new
115  /// id's
117  {
118  public:
121 
122  /// Find the number of entries in the map
123  exint entries() const { return myIdMap.entries(); }
124 
125  /// Query the new id associated with the previous id
127  {
128  if (prev >= 0 && prev < myIdMap.entries())
129  return myIdMap(prev);
130  return -1;
131  }
132 
133  /// @private Used by UT_IndexedHashMap::compactIds()
134  void prepare(exint size)
135  {
136  myIdMap.entries(size); // Grow to expected size
137  myIdMap.constant(-1); // Initialize to -1
138  }
139  /// @private Used by UT_IndexedHashMap::compactIds()
140  void setId(UT_IndexedHashMapItemId prev, UT_IndexedHashMapItemId curr)
141  {
142  UT_ASSERT(myIdMap(prev) == -1);
143  myIdMap(prev) = curr;
144  }
145  private:
146  UT_Array<exint> myIdMap;
147  };
148 
149  /// Compact the list. This fills out the integer map of old id's and their
150  /// new id's. If no compaction was done, the function returns false.
151  /// @note This is @b not thread-safe
152  /// @note This is a no-op if id's are not stored in the map
153  bool compactIds(IdRemapping &remapping);
154 
155  /// Sort the list of ids based on the comparator. This method only works
156  /// if the table has been compacted. Returns false if there are no ids or
157  /// the list is not compacted.
158  /// @note This is @b not thread-safe
159  /// @note This is a no-op if id's are not stored in the map
160  bool sortItems();
161 
162  exint getReferenceCount(UT_IndexedHashMapItemId id) const;
163 
164 protected:
165  /// @{
166  /// Internal implementation using internal types rather than exposed types.
167  /// None of these methods use the template types and thus are only generated
168  /// one time (outlined).
169  void _replace(const UT_IndexedHashMap &src);
170  InternalItemT *_add(const InternalKeyT *key,
171  InternalItemT *item=NULL,
172  UT_IndexedHashMapItemId *id=NULL);
173  InternalItemT *_addReference(UT_IndexedHashMapItemId id, int inc);
175  { return _addReference(id, 1); }
176 
177  InternalItemT *_find(const InternalKeyT *key) const
178  {
180  return _findItemAndId(key, id);
181  }
182  exint _findId(const InternalKeyT *key) const
183  {
185  if (!_findItemAndId(key, hid))
186  hid = -1;
187  return hid;
188  }
189  InternalItemT *_findItemAndId(const InternalKeyT *key,
190  UT_IndexedHashMapItemId &id) const;
191  InternalItemT *_get(UT_IndexedHashMapItemId id) const;
192  const InternalKeyT *_getKey(UT_IndexedHashMapItemId id) const;
193  InternalItemT *_getOrderedItem(exint index,
194  UT_IndexedHashMapItemId *id) const;
195  bool _remove(const InternalKeyT *key);
196  bool _remove(UT_IndexedHashMapItemId id);
198  const InternalKeyT *key,
199  InternalItemT *new_item=NULL);
200  exint _extractItems(
203  exint maxitems
204  ) const;
205  exint _extractItems(
208  ) const;
209  exint _extractItems(
211  ) const;
212  /// @}
213 
214 
215  // These classes need to be defined for the iterator
216  // Class to store reference counted items in the map
217  friend class itemContainer;
219  {
220  public:
222  InternalItemT *item,
223  exint id)
224  : myMap(map)
225  , myItem(item)
226  , myId(id)
227  , myRefCount(0)
228  {}
230  {
231  myMap.deleteItem(myItem);
232  }
233 
234  InternalItemT *getItem() const { return myItem; }
235  exint getId() const { return myId; }
236  void setId(exint id) { myId = id; }
237  exint getRef() const { return myRefCount; }
238  void setRef(int d) { myRefCount = d; }
239  int bumpRef(int d)
240  {
241  myRefCount += d;
242  return myRefCount;
243  }
244 
245  private:
246  const UT_IndexedHashMap &myMap;
247  InternalItemT *myItem;
248  exint myId;
249  int myRefCount;
250  };
251 
252  // Class to search for items in the map
253  friend class keyContainer;
255  {
256  public:
257  // Here, we just hold a reference to the key rather than duplicating
258  // the key.
259  explicit keyContainer(const UT_IndexedHashMap &map,
260  const InternalKeyT *key)
261  : myMap(map)
262  , myKey(key)
263  , myOwn(false)
264  {}
266  : myMap(src.myMap)
267  , myKey(src.myKey ? src.myMap.copyKey(src.myKey) : NULL)
268  , myOwn(true)
269  {}
271  {
272  if (myOwn)
273  myMap.deleteKey(const_cast<InternalKeyT *>(myKey));
274  }
276  {
277  UT_ASSERT(0);
278  if (myKey != src.myKey)
279  {
280  if (myOwn)
281  myMap.deleteKey(const_cast<InternalKeyT *>(myKey));
282  // Make a hard copy
283  myKey = src.myKey ?
284  src.myMap.copyKey(src.myKey) : NULL;
285  }
286  return *this;
287  }
288  const InternalKeyT *getKey() const
289  {
290  UT_ASSERT(myOwn);
291  return myKey;
292  }
293  uint hash() const
294  {
295  UT_ASSERT(myKey);
296  return myMap.hash(myKey);
297  }
298  bool isEqual(const keyContainer &b) const
299  {
300  UT_ASSERT(myKey && b.myKey);
301  return myMap.areKeysEqual(myKey, b.myKey);
302  }
303  private:
304  const UT_IndexedHashMap &myMap;
305  const InternalKeyT *myKey;
306  bool myOwn;
307  };
308 
309  // Class to store items in the indexed list
311  {
312  public:
314  : myItem(NULL)
315  , myKey(NULL)
316  {}
318  : myItem(i)
319  , myKey(k)
320  {}
322  : myItem(src.myItem)
323  , myKey(src.myKey)
324  {}
326  {
327  myItem = src.myItem;
328  myKey = src.myKey;
329  return *this;
330  }
331  bool isValid() const { return myItem; }
332 
334  {
335  return myItem ? myItem->getItem() : NULL;
336  }
337  const InternalKeyT *getKey() const { return myKey; }
338 
339  void setId(exint id) { myItem->setId(id); }
340  exint getId() const { return myItem->getId(); }
341  exint getRef() const
342  { return myItem ? myItem->getRef() : -1; }
343 
344  itemContainer *getItemContainer() { return myItem; }
345 
346  private:
347  itemContainer *myItem;
348  const InternalKeyT *myKey;
349  };
350 
351  // Comparison class for hash map
353  {
354  public:
355  static uint hash(const keyContainer &key)
356  {
357  return key.hash();
358  }
359  static bool equal(const keyContainer &a, const keyContainer &b)
360  {
361  return a.isEqual(b);
362  }
363  };
364 
365  // Class used to sort items
366  friend class itemCompare;
368  {
369  public:
371  : myMap(map)
372  {}
373  bool operator()(const listContainer &a, const listContainer &b) const
374  {
375  return myMap.isItemLessThan(a.getItem(), b.getItem());
376  }
377  private:
378  const UT_IndexedHashMap &myMap;
379  };
380 
383  typedef UT_ConcurrentVector<listContainer> UT_IndexedHashMapVector;
384  typedef UT_ConcurrentQueue<UT_IndexedHashMapItemId>
386 
387 public:
388  /// Iterate over items in the list - this is in the order they are stored
389  /// in the map (i.e. by id).
391  {
393  : myMap(NULL)
394  , myIterator()
395  , mySize(0)
396  , myCurr(0)
397  { }
398 
399  /// @{
400  /// Get information about the current item
401  const InternalKeyT *getKey() const
402  { return myIterator->getKey(); }
403  InternalItemT *getItem() const
404  { return myIterator->getItem(); }
405  UT_IndexedHashMapItemId getItemId() const
406  { return myIterator->getId(); }
407  exint getItemShareCount() const
408  { return myIterator->getRef(); }
409  template <typename T> const T *keyAs() const
410  { return static_cast<const T *>(getKey()); }
411  template <typename T> const T *itemAs() const
412  { return static_cast<const T *>(getItem()); }
413  /// @}
414 
415  /// @{
416  /// Implementation of iterator interface
417  bool atEnd() const { return myCurr >= mySize; }
418  void advance()
419  {
420  do
421  {
422  myCurr++;
423  myIterator++;
424  } while (myCurr < mySize && !myIterator->isValid());
425  }
426  unsafe_listiterator &operator++() { advance(); return *this; }
427  bool operator==(const unsafe_listiterator &it) const
428  {
429  if (atEnd() && it.atEnd())
430  return true;
431  return myMap == it.myMap &&
432  mySize == it.mySize &&
433  myCurr == it.myCurr;
434  }
435  bool operator!=(const unsafe_listiterator &it)
436  { return !(*this == it); }
437  /// @}
438  private:
439  unsafe_listiterator(const UT_IndexedHashMap &map)
440  : myMap(&map)
441  , myIterator(map.myList.begin())
442  , myCurr(0)
443  , mySize(map.entries())
444  {
445  }
446  const UT_IndexedHashMap *myMap;
447  UT_IndexedHashMapVector::const_iterator myIterator;
448  exint mySize, myCurr;
449  friend class UT_IndexedHashMap;
450  };
451  /// Iterate over items in the map - this is arbitrary order
453  {
454  public:
456  : myMap(NULL)
457  , myIterator()
458  , mySize(0)
459  , myCurr(0)
460  {}
461 
462  /// @{
463  /// Get information about the current item
464  const InternalKeyT *getKey() const
465  { return myIterator->first.getKey(); }
467  { return myIterator->second->getItem(); }
469  { return myMap->_findId(getKey()); }
471  { return myIterator->second->getRef();}
472 
473  template <typename T> const T *keyAs() const
474  { return static_cast<const T *>(getKey()); }
475  template <typename T> const T *itemAs() const
476  { return static_cast<const T *>(getItem()); }
477  /// @}
478 
479  /// @{
480  /// Implementation of iterator interface
481  bool atEnd() const { return myCurr >= mySize; }
482  void advance()
483  {
484  ++myCurr; // Move my count
485  ++myIterator; // Move my iterator
486  // Assert that the iterator doesn't terminate early
487  UT_ASSERT(myCurr >= mySize ||
488  myIterator != myMap->myMap.end());
489  }
490  unsafe_iterator &operator++() { advance(); return *this; }
491  // No post increment as it is dangerous.
492  bool operator==(const unsafe_iterator &it) const
493  {
494  if (atEnd() && it.atEnd())
495  return true;
496  return myMap == it.myMap &&
497  mySize == it.mySize &&
498  myCurr == it.myCurr;
499  }
500  bool operator!=(const unsafe_iterator &it)
501  { return !(*this == it); }
502  /// @}
503  private:
505  : myMap(&map)
506  , myIterator(map.myMap.begin())
507  , myCurr(0)
508  , mySize(map.entries())
509  {
510  }
511  const UT_IndexedHashMap *myMap;
512  UT_IndexedHashMapTable::const_iterator myIterator;
513  exint mySize, myCurr;
514  friend class UT_IndexedHashMap;
515  };
517  { return unsafe_iterator(*this); }
519  { return unsafe_iterator(); }
521  { return unsafe_listiterator(*this); }
523  { return unsafe_listiterator(); }
524 
525 private:
526  UT_IndexedHashMapItemId storeItemInList(itemContainer *item,
527  const InternalKeyT *key);
528 
529  int getListSize() const
530  { return myListSize.relaxedLoad(); }
531  bool isValidId(UT_IndexedHashMapItemId id) const
532  { return id >= 0 && id < getListSize(); }
533 
537  SYS_AtomicInt32 myListSize;
538  bool myStoreIds;
539 };
540 
541 #endif
542 
bool operator()(const listContainer &a, const listContainer &b) const
#define SYSmax(a, b)
Definition: SYS_Math.h:1582
fpreal getOccupancy() const
bool empty() const
Return whether the map is empty.
UT_IndexedHashMapItemId getItemIdUpperBound() const
keyContainer(const keyContainer &src)
itemCompare(const UT_IndexedHashMap &map)
static bool equal(const keyContainer &a, const keyContainer &b)
keyContainer(const UT_IndexedHashMap &map, const InternalKeyT *key)
unsafe_iterator begin() const
int64 exint
Definition: SYS_Types.h:125
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
#define UT_API
Definition: UT_API.h:14
Iterate over items in the map - this is arbitrary order.
InternalItemT * getItem() const
unsafe_iterator end() const
bool operator==(const unsafe_iterator &it) const
exint entries() const
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
static uint hash(const keyContainer &key)
UT_IndexedHashMapItemId newId(UT_IndexedHashMapItemId prev) const
Query the new id associated with the previous id.
itemContainer(const UT_IndexedHashMap &map, InternalItemT *item, exint id)
const InternalKeyT * getKey() const
long long int64
Definition: SYS_Types.h:116
GLuint id
Definition: glcorearb.h:655
exint entries() const
Find the number of entries in the map.
tbb::concurrent_hash_map< K, T, H, A > UT_ConcurrentHashMap
bool isEqual(const keyContainer &b) const
exint _findId(const InternalKeyT *key) const
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
virtual InternalKeyT * copyKey(const InternalKeyT *key) const =0
listContainer(const listContainer &src)
const InternalKeyT * getKey() const
const InternalKeyT * getKey() const
GLsizeiptr size
Definition: glcorearb.h:664
InternalItemT * _addReference(UT_IndexedHashMapItemId id)
UT_ConcurrentQueue< UT_IndexedHashMapItemId > UT_IndexedHashMapHoleQueue
fpreal64 fpreal
Definition: SYS_Types.h:278
GLuint index
Definition: glcorearb.h:786
listContainer & operator=(const listContainer &src)
bool operator!=(const unsafe_iterator &it)
unsafe_listiterator endList() const
A thread-safe hash map which stores indexed shared items.
friend class itemContainer
InternalItemT * getItem() const
unsafe_listiterator beginList() const
UT_ConcurrentVector< listContainer > UT_IndexedHashMapVector
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
keyContainer & operator=(const keyContainer &src)
listContainer(itemContainer *i, const InternalKeyT *k)
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:165
UT_IndexedHashMapItemId getItemId() const
InternalItemT * _find(const InternalKeyT *key) const
UT_ConcurrentHashMap< keyContainer, itemContainer *, keyCompare > UT_IndexedHashMapTable
unsigned int uint
Definition: SYS_Types.h:45
GLuint * ids
Definition: glcorearb.h:652
int UT_IndexedHashMapItemId
Each item in the shared map is assigned a unique id.
InternalItemT * getItem() const
GLenum src
Definition: glcorearb.h:1793
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:566