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 
398  /// @{
399  /// Get information about the current item
400  const InternalKeyT *getKey() const
401  { return myIterator->getKey(); }
402  InternalItemT *getItem() const
403  { return myIterator->getItem(); }
404  UT_IndexedHashMapItemId getItemId() const
405  { return myIterator->getId(); }
406  exint getItemShareCount() const
407  { return myIterator->getRef(); }
408  template <typename T> const T *keyAs() const
409  { return static_cast<const T *>(getKey()); }
410  template <typename T> const T *itemAs() const
411  { return static_cast<const T *>(getItem()); }
412  /// @}
413 
414  /// @{
415  /// Implementation of iterator interface
416  bool atEnd() const { return myCurr >= mySize; }
417  void advance()
418  {
419  do
420  {
421  myCurr++;
422  myIterator++;
423  } while (myCurr < mySize && !myIterator->isValid());
424  }
425  unsafe_listiterator &operator++() { advance(); return *this; }
426  bool operator==(const unsafe_listiterator &it) const
427  {
428  if (atEnd() && it.atEnd())
429  return true;
430  return myMap == it.myMap &&
431  mySize == it.mySize &&
432  myCurr == it.myCurr;
433  }
434  bool operator!=(const unsafe_listiterator &it)
435  { return !(*this == it); }
436  /// @}
437  private:
438  unsafe_listiterator(const UT_IndexedHashMap &map)
439  : myMap(&map)
440  , myIterator(map.myList.begin())
441  , myCurr(0)
442  , mySize(map.entries())
443  {
444  }
445  const UT_IndexedHashMap *myMap;
446  UT_IndexedHashMapVector::const_iterator myIterator;
447  exint mySize, myCurr;
448  friend class UT_IndexedHashMap;
449  };
450  /// Iterate over items in the map - this is arbitrary order
452  {
453  public:
455  : myMap(NULL)
456  , myIterator()
457  , mySize(0)
458  , myCurr(0)
459  {}
460 
461  /// @{
462  /// Get information about the current item
463  const InternalKeyT *getKey() const
464  { return myIterator->first.getKey(); }
466  { return myIterator->second->getItem(); }
468  { return myMap->_findId(getKey()); }
470  { return myIterator->second->getRef();}
471 
472  template <typename T> const T *keyAs() const
473  { return static_cast<const T *>(getKey()); }
474  template <typename T> const T *itemAs() const
475  { return static_cast<const T *>(getItem()); }
476  /// @}
477 
478  /// @{
479  /// Implementation of iterator interface
480  bool atEnd() const { return myCurr >= mySize; }
481  void advance()
482  {
483  ++myCurr; // Move my count
484  ++myIterator; // Move my iterator
485  // Assert that the iterator doesn't terminate early
486  UT_ASSERT(myCurr >= mySize ||
487  myIterator != myMap->myMap.end());
488  }
489  unsafe_iterator &operator++() { advance(); return *this; }
490  // No post increment as it is dangerous.
491  bool operator==(const unsafe_iterator &it) const
492  {
493  if (atEnd() && it.atEnd())
494  return true;
495  return myMap == it.myMap &&
496  mySize == it.mySize &&
497  myCurr == it.myCurr;
498  }
499  bool operator!=(const unsafe_iterator &it)
500  { return !(*this == it); }
501  /// @}
502  private:
504  : myMap(&map)
505  , myIterator(map.myMap.begin())
506  , myCurr(0)
507  , mySize(map.entries())
508  {
509  }
510  const UT_IndexedHashMap *myMap;
511  UT_IndexedHashMapTable::const_iterator myIterator;
512  exint mySize, myCurr;
513  friend class UT_IndexedHashMap;
514  };
516  { return unsafe_iterator(*this); }
518  { return unsafe_iterator(); }
520  { return unsafe_listiterator(*this); }
522  { return unsafe_listiterator(); }
523 
524 private:
525  UT_IndexedHashMapItemId storeItemInList(itemContainer *item,
526  const InternalKeyT *key);
527 
528  int getListSize() const
529  { return myListSize.relaxedLoad(); }
530  bool isValidId(UT_IndexedHashMapItemId id) const
531  { return id >= 0 && id < getListSize(); }
532 
536  SYS_AtomicInt32 myListSize;
537  bool myStoreIds;
538 };
539 
540 #endif
541 
bool operator()(const listContainer &a, const listContainer &b) const
#define SYSmax(a, b)
Definition: SYS_Math.h:1570
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.
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:277
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:558