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
116  class IdRemapping {
117  public:
120 
121  /// Find the number of entries in the map
122  exint entries() const { return myIdMap.entries(); }
123 
124  /// Query the new id associated with the previous id
126  {
127  if (prev >= 0 && prev < myIdMap.entries())
128  return myIdMap(prev);
129  return -1;
130  }
131 
132  /// @private Used by UT_IndexedHashMap::compactIds()
133  void prepare(exint size)
134  {
135  myIdMap.entries(size); // Grow to expected size
136  myIdMap.constant(-1); // Initialize to -1
137  }
138  /// @private Used by UT_IndexedHashMap::compactIds()
139  void setId(UT_IndexedHashMapItemId prev, UT_IndexedHashMapItemId curr)
140  {
141  UT_ASSERT(myIdMap(prev) == -1);
142  myIdMap(prev) = curr;
143  }
144  private:
145  UT_Array<exint> myIdMap;
146  };
147 
148  /// Compact the list. This fills out the integer map of old id's and their
149  /// new id's. If no compaction was done, the function returns false.
150  /// @note This is @b not thread-safe
151  /// @note This is a no-op if id's are not stored in the map
152  bool compactIds(IdRemapping &remapping);
153 
154  /// Sort the list of ids based on the comparator. This method only works
155  /// if the table has been compacted. Returns false if there are no ids or
156  /// the list is not compacted.
157  /// @note This is @b not thread-safe
158  /// @note This is a no-op if id's are not stored in the map
159  bool sortItems();
160 
161  exint getReferenceCount(UT_IndexedHashMapItemId id) const;
162 
163 protected:
164  // @{
165  // Internal implementation using internal types rather than exposed types.
166  // None of these methods use the template types and thus are only generated
167  // one time (outlined).
168  void _replace(const UT_IndexedHashMap &src);
169  InternalItemT *_add(const InternalKeyT *key,
170  InternalItemT *item=NULL,
171  UT_IndexedHashMapItemId *id=NULL);
172  InternalItemT *_addReference(UT_IndexedHashMapItemId id, int inc);
174  { return _addReference(id, 1); }
175 
176  InternalItemT *_find(const InternalKeyT *key) const
177  {
179  return _findItemAndId(key, id);
180  }
181  exint _findId(const InternalKeyT *key) const
182  {
184  if (!_findItemAndId(key, hid))
185  hid = -1;
186  return hid;
187  }
188  InternalItemT *_findItemAndId(const InternalKeyT *key,
189  UT_IndexedHashMapItemId &id) const;
190  InternalItemT *_get(UT_IndexedHashMapItemId id) const;
191  const InternalKeyT *_getKey(UT_IndexedHashMapItemId id) const;
192  InternalItemT *_getOrderedItem(exint index,
193  UT_IndexedHashMapItemId *id) const;
194  bool _remove(const InternalKeyT *key);
195  bool _remove(UT_IndexedHashMapItemId id);
197  const InternalKeyT *key,
198  InternalItemT *new_item=NULL);
199  exint _extractItems(
202  exint maxitems
203  ) const;
204  exint _extractItems(
207  ) const;
208  exint _extractItems(
210  ) const;
211  /// @}
212 
213 
214  // These classes need to be defined for the iterator
215  // Class to store reference counted items in the map
216  friend class itemContainer;
218  {
219  public:
221  InternalItemT *item,
222  exint id)
223  : myMap(map)
224  , myItem(item)
225  , myId(id)
226  , myRefCount(0)
227  {}
229  {
230  myMap.deleteItem(myItem);
231  }
232 
233  InternalItemT *getItem() const { return myItem; }
234  exint getId() const { return myId; }
235  void setId(exint id) { myId = id; }
236  exint getRef() const { return myRefCount; }
237  void setRef(int d) { myRefCount = d; }
238  int bumpRef(int d)
239  {
240  myRefCount += d;
241  return myRefCount;
242  }
243 
244  private:
245  const UT_IndexedHashMap &myMap;
246  InternalItemT *myItem;
247  exint myId;
248  int myRefCount;
249  };
250 
251  // Class to search for items in the map
252  friend class keyContainer;
254  {
255  public:
256  // Here, we just hold a reference to the key rather than duplicating
257  // the key.
258  explicit keyContainer(const UT_IndexedHashMap &map,
259  const InternalKeyT *key)
260  : myMap(map)
261  , myKey(key)
262  , myOwn(false)
263  {}
265  : myMap(src.myMap)
266  , myKey(src.myKey ? src.myMap.copyKey(src.myKey) : NULL)
267  , myOwn(true)
268  {}
270  {
271  if (myOwn)
272  myMap.deleteKey(const_cast<InternalKeyT *>(myKey));
273  }
275  {
276  UT_ASSERT(0);
277  if (myKey != src.myKey)
278  {
279  if (myOwn)
280  myMap.deleteKey(const_cast<InternalKeyT *>(myKey));
281  // Make a hard copy
282  myKey = src.myKey ?
283  src.myMap.copyKey(src.myKey) : NULL;
284  }
285  return *this;
286  }
287  const InternalKeyT *getKey() const
288  {
289  UT_ASSERT(myOwn);
290  return myKey;
291  }
292  uint hash() const
293  {
294  UT_ASSERT(myKey);
295  return myMap.hash(myKey);
296  }
297  bool isEqual(const keyContainer &b) const
298  {
299  UT_ASSERT(myKey && b.myKey);
300  return myMap.areKeysEqual(myKey, b.myKey);
301  }
302  private:
303  const UT_IndexedHashMap &myMap;
304  const InternalKeyT *myKey;
305  bool myOwn;
306  };
307 
308  // Class to store items in the indexed list
310  {
311  public:
313  : myItem(NULL)
314  , myKey(NULL)
315  {}
317  : myItem(i)
318  , myKey(k)
319  {}
321  : myItem(src.myItem)
322  , myKey(src.myKey)
323  {}
325  {
326  myItem = src.myItem;
327  myKey = src.myKey;
328  return *this;
329  }
330  bool isValid() const { return myItem; }
331 
333  {
334  return myItem ? myItem->getItem() : NULL;
335  }
336  const InternalKeyT *getKey() const { return myKey; }
337 
338  void setId(exint id) { myItem->setId(id); }
339  exint getId() const { return myItem->getId(); }
340  exint getRef() const
341  { return myItem ? myItem->getRef() : -1; }
342 
343  itemContainer *getItemContainer() { return myItem; }
344 
345  private:
346  itemContainer *myItem;
347  const InternalKeyT *myKey;
348  };
349 
350  // Comparison class for hash map
352  {
353  public:
354  static uint hash(const keyContainer &key)
355  {
356  return key.hash();
357  }
358  static bool equal(const keyContainer &a, const keyContainer &b)
359  {
360  return a.isEqual(b);
361  }
362  };
363 
364  // Class used to sort items
365  friend class itemCompare;
367  {
368  public:
370  : myMap(map)
371  {}
372  bool operator()(const listContainer &a, const listContainer &b) const
373  {
374  return myMap.isItemLessThan(a.getItem(), b.getItem());
375  }
376  private:
377  const UT_IndexedHashMap &myMap;
378  };
379 
380  typedef UT_ConcurrentHashMap<keyContainer, itemContainer *, keyCompare>
382  typedef UT_ConcurrentVector<listContainer> UT_IndexedHashMapVector;
383  typedef UT_ConcurrentQueue<UT_IndexedHashMapItemId>
385 
386 public:
387  /// Iterate over items in the list - this is in the order they are stored
388  /// in the map (i.e. by id).
390  {
392  : myMap(NULL)
393  , myIterator()
394  , mySize(0)
395  , myCurr(0)
396  { }
397  unsafe_listiterator(const unsafe_listiterator &src)
398  : myMap(src.myMap)
399  , myIterator(src.myIterator)
400  , mySize(src.mySize)
401  , myCurr(src.myCurr)
402  { }
403  ~unsafe_listiterator()
404  { }
405 
406  /// @{
407  /// Get information about the current item
408  const InternalKeyT *getKey() const
409  { return myIterator->getKey(); }
410  InternalItemT *getItem() const
411  { return myIterator->getItem(); }
412  UT_IndexedHashMapItemId getItemId() const
413  { return myIterator->getId(); }
414  exint getItemShareCount() const
415  { return myIterator->getRef(); }
416  template <typename T> const T *keyAs() const
417  { return static_cast<const T *>(getKey()); }
418  template <typename T> const T *itemAs() const
419  { return static_cast<const T *>(getItem()); }
420  /// @}
421 
422  /// @{
423  /// Implementation of iterator interface
424  bool atEnd() const { return myCurr >= mySize; }
425  void advance()
426  {
427  do
428  {
429  myCurr++;
430  myIterator++;
431  } while (myCurr < mySize && !myIterator->isValid());
432  }
433  unsafe_listiterator &operator++() { advance(); return *this; }
434  bool operator==(const unsafe_listiterator &it) const
435  {
436  if (atEnd() && it.atEnd())
437  return true;
438  return myMap == it.myMap &&
439  mySize == it.mySize &&
440  myCurr == it.myCurr;
441  }
442  bool operator!=(const unsafe_listiterator &it)
443  { return !(*this == it); }
444  /// @}
445  private:
446  unsafe_listiterator(const UT_IndexedHashMap &map)
447  : myMap(&map)
448  , myIterator(map.myList.begin())
449  , myCurr(0)
450  , mySize(map.entries())
451  {
452  }
453  const UT_IndexedHashMap *myMap;
454  UT_IndexedHashMapVector::const_iterator myIterator;
455  exint mySize, myCurr;
456  friend class UT_IndexedHashMap;
457  };
458  /// Iterate over items in the map - this is arbitrary order
460  {
461  public:
463  : myMap(NULL)
464  , myIterator()
465  , mySize(0)
466  , myCurr(0)
467  {}
469  : myMap(src.myMap)
470  , myIterator(src.myIterator)
471  , mySize(src.mySize)
472  , myCurr(src.myCurr)
473  {}
475 
477  {
478  myMap = src.myMap;
479  myIterator = src.myIterator;
480  mySize = src.mySize;
481  myCurr = src.myCurr;
482  return *this;
483  }
484 
485  /// @{
486  /// Get information about the current item
487  const InternalKeyT *getKey() const
488  { return myIterator->first.getKey(); }
490  { return myIterator->second->getItem(); }
492  { return myMap->_findId(getKey()); }
494  { return myIterator->second->getRef();}
495 
496  template <typename T> const T *keyAs() const
497  { return static_cast<const T *>(getKey()); }
498  template <typename T> const T *itemAs() const
499  { return static_cast<const T *>(getItem()); }
500  /// @}
501 
502  /// @{
503  /// Implementation of iterator interface
504  bool atEnd() const { return myCurr >= mySize; }
505  void advance()
506  {
507  ++myCurr; // Move my count
508  ++myIterator; // Move my iterator
509  // Assert that the iterator doesn't terminate early
510  UT_ASSERT(myCurr >= mySize ||
511  myIterator != myMap->myMap.end());
512  }
513  unsafe_iterator &operator++() { advance(); return *this; }
514  // No post increment as it is dangerous.
515  bool operator==(const unsafe_iterator &it) const
516  {
517  if (atEnd() && it.atEnd())
518  return true;
519  return myMap == it.myMap &&
520  mySize == it.mySize &&
521  myCurr == it.myCurr;
522  }
523  bool operator!=(const unsafe_iterator &it)
524  { return !(*this == it); }
525  /// @}
526  private:
528  : myMap(&map)
529  , myIterator(map.myMap.begin())
530  , myCurr(0)
531  , mySize(map.entries())
532  {
533  }
534  const UT_IndexedHashMap *myMap;
535  UT_IndexedHashMapTable::const_iterator myIterator;
536  exint mySize, myCurr;
537  friend class UT_IndexedHashMap;
538  };
540  { return unsafe_iterator(*this); }
542  { return unsafe_iterator(); }
544  { return unsafe_listiterator(*this); }
546  { return unsafe_listiterator(); }
547 
548 private:
549  UT_IndexedHashMapItemId storeItemInList(itemContainer *item,
550  const InternalKeyT *key);
551 
552  int getListSize() const
553  { return myListSize.relaxedLoad(); }
554  bool isValidId(UT_IndexedHashMapItemId id) const
555  { return id >= 0 && id < getListSize(); }
556 
560  SYS_AtomicInt32 myListSize;
561  bool myStoreIds;
562 };
563 
564 #endif
565 
bool operator()(const listContainer &a, const listContainer &b) const
#define SYSmax(a, b)
Definition: SYS_Math.h:1521
fpreal getOccupancy() const
bool empty() const
Return whether the map is empty.
GLuint id
Definition: glew.h:1679
GLsizeiptr size
Definition: glew.h:1681
GLenum src
Definition: glew.h:2410
UT_IndexedHashMapItemId getItemIdUpperBound() const
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
keyContainer(const keyContainer &src)
itemCompare(const UT_IndexedHashMap &map)
GLuint index
Definition: glew.h:1814
static bool equal(const keyContainer &a, const keyContainer &b)
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
keyContainer(const UT_IndexedHashMap &map, const InternalKeyT *key)
unsafe_iterator begin() const
int64 exint
Definition: SYS_Types.h:125
#define UT_API
Definition: UT_API.h:13
Iterate over items in the map - this is arbitrary order.
InternalItemT * getItem() const
unsafe_iterator end() const
unsafe_iterator & operator=(const unsafe_iterator &src)
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
exint entries() const
Find the number of entries in the map.
bool isEqual(const keyContainer &b) const
exint _findId(const InternalKeyT *key) const
unsafe_iterator(const unsafe_iterator &src)
virtual InternalKeyT * copyKey(const InternalKeyT *key) const =0
listContainer(const listContainer &src)
const InternalKeyT * getKey() const
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
const InternalKeyT * getKey() const
InternalItemT * _addReference(UT_IndexedHashMapItemId id)
UT_ConcurrentQueue< UT_IndexedHashMapItemId > UT_IndexedHashMapHoleQueue
fpreal64 fpreal
Definition: SYS_Types.h:277
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
const GLuint * ids
Definition: glew.h:1684
UT_ConcurrentVector< listContainer > UT_IndexedHashMapVector
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:135
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
int UT_IndexedHashMapItemId
Each item in the shared map is assigned a unique id.
InternalItemT * getItem() const