HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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 
476  /// @{
477  /// Get information about the current item
478  const InternalKeyT *getKey() const
479  { return myIterator->first.getKey(); }
481  { return myIterator->second->getItem(); }
483  { return myMap->_findId(getKey()); }
485  { return myIterator->second->getRef();}
486 
487  template <typename T> const T *keyAs() const
488  { return static_cast<const T *>(getKey()); }
489  template <typename T> const T *itemAs() const
490  { return static_cast<const T *>(getItem()); }
491  /// @}
492 
493  /// @{
494  /// Implementation of iterator interface
495  bool atEnd() const { return myCurr >= mySize; }
496  void advance()
497  {
498  ++myCurr; // Move my count
499  ++myIterator; // Move my iterator
500  // Assert that the iterator doesn't terminate early
501  UT_ASSERT(myCurr >= mySize ||
502  myIterator != myMap->myMap.end());
503  }
504  unsafe_iterator &operator++() { advance(); return *this; }
505  // No post increment as it is dangerous.
506  bool operator==(const unsafe_iterator &it) const
507  {
508  if (atEnd() && it.atEnd())
509  return true;
510  return myMap == it.myMap &&
511  mySize == it.mySize &&
512  myCurr == it.myCurr;
513  }
514  bool operator!=(const unsafe_iterator &it)
515  { return !(*this == it); }
516  /// @}
517  private:
519  : myMap(&map)
520  , myIterator(map.myMap.begin())
521  , myCurr(0)
522  , mySize(map.entries())
523  {
524  }
525  const UT_IndexedHashMap *myMap;
526  UT_IndexedHashMapTable::const_iterator myIterator;
527  exint mySize, myCurr;
528  friend class UT_IndexedHashMap;
529  };
531  { return unsafe_iterator(*this); }
533  { return unsafe_iterator(); }
535  { return unsafe_listiterator(*this); }
537  { return unsafe_listiterator(); }
538 
539 private:
540  UT_IndexedHashMapItemId storeItemInList(itemContainer *item,
541  const InternalKeyT *key);
542 
543  int getListSize() const
544  { return myListSize; }
545  bool isValidId(UT_IndexedHashMapItemId id) const
546  { return id >= 0 && id < getListSize(); }
547 
551  SYS_AtomicInt32 myListSize;
552  bool myStoreIds;
553 };
554 
555 #endif
556 
bool operator()(const listContainer &a, const listContainer &b) const
#define SYSmax(a, b)
Definition: SYS_Math.h:1365
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
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:12
Iterate over items in the map - this is arbitrary order.
InternalItemT * getItem() const
GLuint * ids
Definition: glcorearb.h:651
unsafe_iterator end() const
png_uint_32 i
Definition: png.h:2877
bool operator==(const unsafe_iterator &it) const
GLsizeiptr size
Definition: glcorearb.h:663
exint entries() const
GLuint id
Definition: glcorearb.h:654
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
long long int64
Definition: SYS_Types.h:106
static uint hash(const keyContainer &key)
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
int64 exint
Definition: SYS_Types.h:115
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
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:1221
unsigned int uint
Definition: SYS_Types.h:39
unsafe_iterator(const unsafe_iterator &src)
virtual InternalKeyT * copyKey(const InternalKeyT *key) const =0
listContainer(const listContainer &src)
const InternalKeyT * getKey() const
const InternalKeyT * getKey() const
InternalItemT * _addReference(UT_IndexedHashMapItemId id)
double fpreal
Definition: SYS_Types.h:269
png_infop png_sPLT_tpp entries
Definition: png.h:2481
UT_ConcurrentQueue< UT_IndexedHashMapItemId > UT_IndexedHashMapHoleQueue
GLuint index
Definition: glcorearb.h:785
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
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
int UT_IndexedHashMapItemId
Each item in the shared map is assigned a unique id.
InternalItemT * getItem() const
GLenum src
Definition: glcorearb.h:1792