HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_IndexedHashSet.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_IndexedHashSet.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #pragma once
12 
13 #ifndef __UT_IndexedHashSet__
14 #define __UT_IndexedHashSet__
15 
16 #include "UT_Assert.h"
17 #include "UT_Array.h"
18 #include "UT_ConcurrentHashMap.h"
19 #include "UT_ConcurrentVector.h"
20 #include "UT_ConcurrentQueue.h"
21 #include <SYS/SYS_AtomicInt.h>
22 #include <SYS/SYS_Inline.h>
23 #include <SYS/SYS_Types.h>
24 
25 /// Each item in the shared map is assigned a unique id
27 
28 /// @brief A thread-safe hash map which stores indexed shared items
29 ///
30 /// Each item in the hash map is reference counted. That is, if objects are
31 /// added multiple times, only a single object will be stored in the map.
32 ///
33 /// Removing an item from the hash map (by id or key) will decrement the
34 /// reference count on the item. When no longer referenced, the map will
35 /// delete the item.
36 ///
37 /// When the map stores 'ids', each item is assigned a unique id
38 /// (UT_IndexedHashSetItemId). The item can then be retrieved efficiently from
39 /// the map using the id (UT_IndexedHashSet::get())
40 ///
41 /// Many methods on the map are thread-safe. Some methods are not (and are
42 /// noted in the comments).
43 ///
44 /// The KEY template parameter needs to have: @code
45 /// KEY(const KEY &src); // The copy constructor
46 /// uint hash() const; // A hash method
47 /// bool isEqual(const KEY &src) const; // A comparison operator
48 /// @endcode
49 template<class T>
51 {
52 public:
53  /// Each item stored in the map will be given a unique id of type
54  /// UT_IndexedHashSetItemId. These id's can be used to perform efficient
55  /// lookup of items in the map.
57  : myListSize(0)
58  {}
60  {
61  UT_ASSERT(entries() == 0);
62  }
63 
64  /// Clear the map
65  /// @note This is @b not thread-safe
66  void clear();
67 
68  /// Return the number of entries in the map.
69  /// @note This is @b not thread-safe
70  exint entries() const { return myMap.size(); }
71 
72  /// Return whether the map is empty
73  bool empty() const { return myMap.empty(); }
74 
75  /// Return approximate memory usage (not including key or item storage)
76  int64 getMemoryUsage(bool inclusive) const;
77 
78  /// Return the maximum possible UT_IndexedHashSetItemId stored in the map.
79  /// This returns an upper bound and is not exact.
80  /// @note This is @b not thread-safe
81  /// @note Not supported if id's are not stored in the map
83  { return getListSize()-1; }
84 
85  /// Return the "occupancy" of the map.
86  /// @note This is @b not thread-safe
87  /// @note Not supported if id's are not stored in the map
89  {
90  exint lsize = getListSize();
91  exint hsize = myHoles.unsafe_size();
92  if (!lsize || !hsize)
93  return fpreal(1); // Fully occupied
94  UT_ASSERT(lsize > hsize);
95  return (fpreal)(lsize-hsize)/(fpreal)lsize;
96  }
97 
98  /// Class used by compacting to map from the previous id to the new id.
99  /// After compacting, this class stores a map of the old id's to the new
100  /// id's
101  class IdRemapping {
102  public:
103  /// Find the number of entries in the map
104  exint entries() const { return myIdMap.entries(); }
105 
106  /// Query the new id associated with the previous id
108  {
109  if (prev >= 0 && prev < myIdMap.entries())
110  return myIdMap(prev);
111  return -1;
112  }
113 
114  /// @private Used by UT_IndexedHashSet::compactIds()
115  void prepare(exint size)
116  {
117  myIdMap.setSizeNoInit(size);// Grow to expected size
118  myIdMap.constant(-1); // Initialize to -1
119  }
120  /// @private Used by UT_IndexedHashSet::compactIds()
121  void setId(UT_IndexedHashSetItemId prev, UT_IndexedHashSetItemId curr)
122  {
123  UT_ASSERT(myIdMap(prev) == -1);
124  myIdMap(prev) = curr;
125  }
126  private:
127  UT_Array<exint> myIdMap;
128  };
129 
130  /// Compact the list. This fills out the integer map of old id's and their
131  /// new id's. If no compaction was done, the function returns false.
132  /// @note This is @b not thread-safe
133  /// @note This is a no-op if id's are not stored in the map
134  bool compactIds(IdRemapping &remapping);
135 
136  /// Sort the list of ids based on the comparator. This method only works
137  /// if the table has been compacted. Returns false if there are no ids or
138  /// the list is not compacted.
139  /// @note This is @b not thread-safe
140  /// @note This is a no-op if id's are not stored in the map
141  template<typename P>
142  bool sortItems(const P &predicate);
143 
145  exint getReferenceCount(const T &key) const;
146 
147 public:
148  void replace(const UT_IndexedHashSet &src);
149  UT_IndexedHashSetItemId add(const T &key);
150  /// This may return null if inc is negative and the reference count
151  /// reaches zero, or if the ID is out of range.
152  const T *addReference(UT_IndexedHashSetItemId id, int inc);
155  { return addReference(id, 1); }
156 
157  UT_IndexedHashSetItemId findId(const T &key) const
158  {
160  if (!findItemAndId(key, id))
161  id = -1;
162  return id;
163  }
164  const T *findItemAndId(const T &key, UT_IndexedHashSetItemId &id) const;
166  const T *get(UT_IndexedHashSetItemId id) const
167  {
168  return isValidId(id) ? &myList[id] : nullptr;
169  }
170  const T *getOrderedItem(exint index, UT_IndexedHashSetItemId *id = nullptr) const;
171  bool remove(const T &key);
172  bool remove(UT_IndexedHashSetItemId id);
174  const T &key);
175 
176  template<typename ID_ARRAY, typename T_ARRAY>
177  exint extractItems(ID_ARRAY &ids,
178  T_ARRAY &items,
179  exint maxitems) const;
180  template<typename ID_ARRAY, typename T_ARRAY>
181  exint extractItems(ID_ARRAY &ids,
182  T_ARRAY &items) const;
183  template<typename T_ARRAY>
184  exint extractItems(T_ARRAY &items) const;
185 
186 
187  // Class to store item ID and reference count in the map
189  {
190  public:
191  /// WARNING: This initializes nothing; you must initialize separately
196  : myId(id)
197  , myRefCount(refcount)
198  {}
201  : myId(src.myId)
202  , myRefCount(src.myRefCount)
203  {}
206  : myId(src.myId)
207  , myRefCount(src.myRefCount)
208  {}
209 
211  UT_IndexedHashSetItemId getId() const { return myId; }
213  void setId(UT_IndexedHashSetItemId id) { myId = id; }
215  exint getRef() const { return myRefCount; }
217  void setRef(int d) { myRefCount = d; }
219  int bumpRef(int d)
220  {
221  myRefCount += d;
222  return myRefCount;
223  }
224 
225  private:
227  int myRefCount;
228  };
229 
230  // Comparison class for hash map
231  class keyHasher
232  {
233  public:
235  static uint hash(const T &key)
236  {
237  return hash_value(key);
238  }
240  static bool equal(const T &a, const T &b)
241  {
242  return a == b;
243  }
244  };
245 
246  typedef UT_ConcurrentHashMap<T, IdAndRefCount>
248  typedef UT_ConcurrentVector<T> UT_IndexedHashSetVector;
249  typedef UT_ConcurrentQueue<UT_IndexedHashSetItemId>
251 
252 public:
253  /// Iterate over items in the list - this is in the order they are stored
254  /// in the map (i.e. by id).
256  {
258  : myMap(nullptr)
259  , myIterator()
260  , mySize(0)
261  , myCurr(0)
262  { }
264  : myMap(src.myMap)
265  , myIterator(src.myIterator)
266  , mySize(src.mySize)
267  , myCurr(src.myCurr)
268  { }
270  { }
271 
272  /// @{
273  /// Get information about the current item
274  const T &getKey() const
275  { return *myIterator; }
276 
277  UT_IndexedHashSetItemId getItemId() const
278  { return UT_IndexedHashSetItemId(myCurr); }
279 
280  exint getItemShareCount() const
281  { return myMap->myMap[*myIterator].getRef(); }
282  /// @}
283 
284  /// @{
285  /// Implementation of iterator interface
286  bool atEnd() const { return myCurr >= mySize; }
287  void advance()
288  {
289  do
290  {
291  myCurr++;
292  myIterator++;
293  } while (myCurr < mySize && UT_IndexedHashSet::isValidKey(*myIterator));
294  }
295  unsafe_listiterator &operator++() { advance(); return *this; }
296  bool operator==(const unsafe_listiterator &it) const
297  {
298  if (atEnd() && it.atEnd())
299  return true;
300  return myMap == it.myMap &&
301  mySize == it.mySize &&
302  myCurr == it.myCurr;
303  }
304  bool operator!=(const unsafe_listiterator &it)
305  { return !(*this == it); }
306  /// @}
307  private:
309  : myMap(&map)
310  , myIterator(map.myList.begin())
311  , myCurr(0)
312  , mySize(map.entries())
313  {
314  }
315  const UT_IndexedHashSet *myMap;
316  typename UT_IndexedHashSetVector::const_iterator myIterator;
317  exint mySize, myCurr;
318  friend class UT_IndexedHashSet;
319  };
320  /// Iterate over items in the map - this is arbitrary order
322  {
323  public:
325  : myMap(NULL)
326  , myIterator()
327  , mySize(0)
328  , myCurr(0)
329  {}
331  : myMap(src.myMap)
332  , myIterator(src.myIterator)
333  , mySize(src.mySize)
334  , myCurr(src.myCurr)
335  {}
337 
338  /// @{
339  /// Get information about the current item
340  const T &getKey() const
341  { return myIterator->first; }
342 
344  { return myIterator->second.getId(); }
345 
347  { return myIterator->second.getRef();}
348  /// @}
349 
350  /// @{
351  /// Implementation of iterator interface
352  bool atEnd() const { return myCurr >= mySize; }
353  void advance()
354  {
355  ++myCurr; // Move my count
356  ++myIterator; // Move my iterator
357  // Assert that the iterator doesn't terminate early
358  UT_ASSERT_P(myCurr >= mySize || myIterator != myMap->myMap.end());
359  }
360  unsafe_iterator &operator++() { advance(); return *this; }
361  // No post increment as it is dangerous.
362  bool operator==(const unsafe_iterator &it) const
363  {
364  if (atEnd() && it.atEnd())
365  return true;
366  UT_ASSERT_P(mySize == it.mySize);
367  return myMap == it.myMap &&
368  myCurr == it.myCurr;
369  }
370  bool operator!=(const unsafe_iterator &it)
371  { return !(*this == it); }
372  /// @}
373  private:
375  : myMap(&map)
376  , myIterator(map.myMap.begin())
377  , myCurr(0)
378  , mySize(map.entries())
379  {
380  }
381  const UT_IndexedHashSet *myMap;
382  typename UT_IndexedHashSetTable::const_iterator myIterator;
383  exint mySize, myCurr;
384  friend class UT_IndexedHashSet;
385  };
386 
387  unsafe_iterator begin() const
388  { return unsafe_iterator(*this); }
389  unsafe_iterator end() const
390  { return unsafe_iterator(); }
391  unsafe_listiterator beginList() const
392  { return unsafe_listiterator(*this); }
393  unsafe_listiterator endList() const
394  { return unsafe_listiterator(); }
395 
396 private:
397  UT_IndexedHashSetItemId storeItemInList(const T &key);
398 
400  int getListSize() const
401  { return myListSize.relaxedLoad(); }
402 
404  bool isValidId(UT_IndexedHashSetItemId id) const
405  { return id >= 0 && id < getListSize(); }
406 
407  /// Return true if key is not the "clear" key value
409  static bool isValidKey(const T &key);
410 
411  /// Sets key to the "clear" key value
413  static void invalidateKey(T &key);
414 
418  SYS_AtomicCounter myListSize;
419 };
420 
421 #endif
422 
unsafe_listiterator beginList() const
exint entries() const
Find the number of entries in the map.
bool sortItems(const P &predicate)
unsafe_listiterator endList() const
UT_IndexedHashSetItemId findId(const T &key) const
UT_IndexedHashSetItemId getItemIdUpperBound() const
UT_ConcurrentVector< T > UT_IndexedHashSetVector
void setSizeNoInit(exint newsize)
Definition: UT_Array.h:492
SYS_FORCE_INLINE exint getRef() const
SYS_FORCE_INLINE void setId(UT_IndexedHashSetItemId id)
SYS_FORCE_INLINE UT_IndexedHashSetItemId getId() const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
UT_IndexedHashSetItemId add(const T &key)
exint UT_IndexedHashSetItemId
Each item in the shared map is assigned a unique id.
A thread-safe hash map which stores indexed shared items.
const T * getOrderedItem(exint index, UT_IndexedHashSetItemId *id=nullptr) const
GLuint * ids
Definition: glcorearb.h:651
GLsizeiptr size
Definition: glcorearb.h:663
unsafe_iterator begin() const
bool operator==(const unsafe_iterator &it) const
GLuint id
Definition: glcorearb.h:654
const T * findItemAndId(const T &key, UT_IndexedHashSetItemId &id) const
long long int64
Definition: SYS_Types.h:107
bool empty() const
Return whether the map is empty.
exint entries() const
static SYS_FORCE_INLINE bool equal(const T &a, const T &b)
int64 exint
Definition: SYS_Types.h:116
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
SYS_FORCE_INLINE IdAndRefCount(UT_IndexedHashSetItemId id, exint refcount)
void replace(const UT_IndexedHashSet &src)
SYS_FORCE_INLINE IdAndRefCount()
WARNING: This initializes nothing; you must initialize separately.
int64 getMemoryUsage(bool inclusive) const
Return approximate memory usage (not including key or item storage)
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
fpreal getOccupancy() const
bool operator!=(const unsafe_iterator &it)
unsafe_iterator end() const
exint getReferenceCount(UT_IndexedHashSetItemId id) const
UT_IndexedHashSetItemId getItemId() const
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
unsigned int uint
Definition: SYS_Types.h:40
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:453
UT_ConcurrentHashMap< T, IdAndRefCount > UT_IndexedHashSetTable
double fpreal
Definition: SYS_Types.h:270
exint extractItems(ID_ARRAY &ids, T_ARRAY &items, exint maxitems) const
bool compactIds(IdRemapping &remapping)
unsafe_iterator(const unsafe_iterator &src)
UT_IndexedHashSetItemId replaceItem(UT_IndexedHashSetItemId id, const T &key)
SYS_FORCE_INLINE IdAndRefCount(IdAndRefCount &&src)
GLuint index
Definition: glcorearb.h:785
Iterate over items in the map - this is arbitrary order.
SYS_FORCE_INLINE IdAndRefCount(const IdAndRefCount &src)
SYS_FORCE_INLINE const T * addReference(UT_IndexedHashSetItemId id)
void constant(const T &v)
Quickly set the array to a single value.
Definition: UT_ArrayImpl.h:668
UT_ConcurrentQueue< UT_IndexedHashSetItemId > UT_IndexedHashSetHoleQueue
SYS_FORCE_INLINE void setRef(int d)
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
UT_IndexedHashSetItemId newId(UT_IndexedHashSetItemId prev) const
Query the new id associated with the previous id.
const T * addReference(UT_IndexedHashSetItemId id, int inc)
size_t hash_value(const CH_ChannelRef &ref)
static SYS_FORCE_INLINE uint hash(const T &key)
SYS_FORCE_INLINE int bumpRef(int d)
SYS_FORCE_INLINE T relaxedLoad() const
Definition: SYS_AtomicInt.h:60
GLenum src
Definition: glcorearb.h:1792