HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_IndexedHashSetImpl.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_IndexedHashSetImpl.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #pragma once
12 
13 #ifndef __UT_IndexedHashSetImpl__
14 #define __UT_IndexedHashSetImpl__
15 
16 #include "UT_IndexedHashSet.h"
17 #include "UT_ArraySet.h" // Just for UT::DefaultClearer
18 #include "UT_Assert.h"
19 #include <vector>
20 
21 template<typename T>
22 void
24 {
25  myList.clear();
26  myHoles.clear();
27  myMap.clear();
28  myListSize.relaxedStore(0);
29 }
30 
31 template<typename T>
32 bool
34 {
35  return !UT::DefaultClearer<T>::isClear(key);
36 }
37 
38 template<typename T>
39 void
41 {
43 }
44 
45 template<typename T>
46 void
48 {
49  if (this == &src)
50  return;
51 
52  clear();
53 
54  // All of the IDs and reference counts need to be the same as in src.
55  // Just in case, the order of the holes should be the same, too.
56 
57  exint listsize = src.myList.size();
58  myList.resize(listsize);
59  myListSize.relaxedStore(listsize);
60  myMap.rehash(src.myMap.size());
61 
62  for (exint id = 0; id < listsize; ++id)
63  {
64  const T &srckey = src.myList[id];
65  if (!isValidKey(srckey))
66  {
67  invalidateKey(myList[id]);
68  continue;
69  }
70  myList[id] = srckey;
71 
72  exint refcount;
73  {
74  typename UT_IndexedHashSetTable::const_accessor a;
75  src.myMap.find(a, srckey);
76  refcount = a->second.getRef();
77  }
78  // There shouldn't be any conflicts, since we cleared above.
79  myMap.insert(std::pair<T,IdAndRefCount>(srckey, IdAndRefCount(id, refcount)));
80  }
81 
82  if (!src.myHoles.empty())
83  {
84  // Unfortunately, tbb::concurrent_queue::assign isn't accessible,
85  // so let's destruct and copy construct in-place.
86  myHoles.~UT_IndexedHashSetHoleQueue();
87  new (&myHoles) UT_IndexedHashSetHoleQueue(src.myHoles);
88  }
89 }
90 
91 template<typename T>
92 const T *
94  UT_IndexedHashSetItemId *id_store) const
95 {
96  if (myHoles.empty())
97  {
98  if (id_store)
99  *id_store = idx;
100  return get((UT_IndexedHashSetItemId)idx);
101  }
102  exint find = 0;
103  for (unsafe_listiterator it = beginList(); !it.atEnd(); ++it, ++find)
104  {
105  if (find == idx)
106  {
107  if (id_store)
108  *id_store = it.getItemId();
109  return &it.getKey();
110  }
111  }
112  return nullptr;
113 }
114 
115 template<typename T>
116 const T *
118 {
119  if (!isValidId(id))
120  return nullptr;
121 
122  // We need to "lock" this item since bumpRef() is not thread-safe
123  typename UT_IndexedHashSetTable::accessor a;
124  if (myMap.find(a, myList[id]))
125  {
126  // Check to see if this brought us to zero.
127  if (!a->second.bumpRef(inc))
128  {
129  // Last reference to the item
130 
131  // Clear the key
132  UT_IndexedHashSetItemId id = a->second.getId();
133  UT_ASSERT(isValidId(id));
134  invalidateKey(myList[id]);
135  myHoles.push(id); // Now safe to use
136 
137  // Erase from the map
138  myMap.erase(a);
139 
140  // We definitely don't want to return item now!
141  return nullptr;
142  }
143 
144  return &myList[id];
145  }
146 
147  // Looking up ID for clear key.
148  return nullptr;
149 }
150 
151 template<typename T>
152 exint
154 {
155  if (!isValidId(id))
156  return 0;
157 
158  // We need to "lock" this item since getRef() is not thread-safe
159  typename UT_IndexedHashSetTable::accessor a;
160  if (myMap.find(a, myList[id]))
161  {
162  return a->second.getRef();
163  }
164 
165  return 0;
166 }
167 
168 template<typename T>
169 exint
171 {
172  // We need to "lock" this item since getRef() is not thread-safe
173  typename UT_IndexedHashSetTable::accessor a;
174  if (myMap.find(a, key))
175  {
176  return a->second.getRef();
177  }
178 
179  return 0;
180 }
181 
182 template<typename T>
185 {
187  if (myHoles.try_pop(offset))
188  {
189  UT_ASSERT(offset >= 0 && offset < myList.size());
190  myList[offset] = key;
191  }
192  else
193  {
194  offset = myList.push_back(key) - myList.begin();
195  myListSize.maximum(offset+1);
196  }
197  return offset;
198 }
199 
200 template<typename T>
203 {
205  return UT_IndexedHashSetItemId(-1);
206  typename UT_IndexedHashSetTable::accessor a;
207  if (myMap.insert(a, key))
208  {
209  // Create an item and store it in the map.
210  // Use the key from the map, since it has the hash computed.
211  UT_IndexedHashSetItemId id = storeItemInList(a->first);
212  a->second.setId(id);
213  a->second.setRef(1);
214  }
215  else
216  {
217  // Increment the reference count on the container (not the item)
218  a->second.bumpRef(1);
219  }
220  return a->second.getId();
221 }
222 
223 template<typename T>
224 const T *
226  const T &key,
227  UT_IndexedHashSetItemId &id) const
228 {
229  typename UT_IndexedHashSetTable::const_accessor a;
230  if (myMap.find(a, key))
231  {
232  id = a->second.getId();
233  return &a->first;
234  }
235  return nullptr;
236 }
237 
238 template<typename T>
239 bool
241 {
242  typename UT_IndexedHashSetTable::accessor a;
243  if (myMap.find(a, key))
244  {
245  // We have write access to object
246  if (!a->second.bumpRef(-1))
247  {
248  // Last reference to the item
249 
250  // Clear the pointer
251  UT_IndexedHashSetItemId id = a->second.getId();
252  UT_ASSERT(isValidId(id));
253  invalidateKey(myList[id]);
254  myHoles.push(id); // Now safe to use
255 
256  // Erase from the map
257  myMap.erase(a);
258 
259  // true means removed
260  return true;
261  }
262  }
263  return false;
264 }
265 
266 template<typename T>
267 bool
269 {
270  if (!isValidId(id))
271  return false;
272 
273  const T &key = myList[id];
274  if (isValidKey(key))
275  {
276  return remove(key);
277  }
278  return false;
279 }
280 
281 template<typename T>
285  const T &key)
286 {
287  if (!isValidId(id) || !isValidKey(myList[id]))
288  return -1;
289 
290  typename UT_IndexedHashSetTable::accessor a;
291  // Find the item in the map so that we can replace it
292  const T &okey = myList[id];
293  if (!myMap.find(a, okey))
294  {
295  UT_ASSERT(0 && "Missing object that's in the map!");
296  return -1;
297  }
298 
299  // Get reference count of the current item
300  exint irefcount = a->second.getRef();
301 
302  // Assert the object is in the location we expect.
303  UT_ASSERT(a->second.getId() == id);
304 
305  // Remove the previous item from the list/map and delete it.
306  invalidateKey(myList[id]); // Clear out item from list
307  myMap.erase(a);
308 
310  {
311  // Since we've cleaned out the previous entry, and there isn't one
312  // for the clear value, just add the id to the hole list.
313  myHoles.push(id); // We can write into this list
314 
315  return UT_IndexedHashSetItemId(-1);
316  }
317 
318  // Now, insert the new item
319  if (myMap.insert(a, key))
320  {
321  // Store a new item in the map
322  a->second.setId(id);
323  a->second.setRef(irefcount);
324  // Use the key from the map, since it has the hash computed
325  myList[id] = a->first;
326  }
327  else
328  {
329  // Hey! There's already an item which matches the key
330 
331  // Since we've cleaned out the previous entry, we can now write to the
332  // object in the list, so add the id to the hole list.
333  myHoles.push(id); // We can write into this list
334 
335  // It's up to user to update references
336  a->second.bumpRef(irefcount);
337 
338  // Get the appropriate id
339  id = a->second.getId();
340  }
341  return id;
342 }
343 
344 template<typename T>
345 bool
347 {
348  if (myHoles.empty())
349  return false;
350  exint n = getListSize();
351 
352  remapping.prepare(n);
353  exint d = 0;
354  for (exint s = 0; s < n; ++s)
355  {
356  const T &skey = myList[s];
357  if (!isValidKey(skey))
358  continue;
359 
360  remapping.setId(s, d);
361  if (s != d)
362  {
363  {
364  typename UT_IndexedHashSetTable::accessor a;
365  UT_VERIFY_P(myMap.find(a, skey));
366  a->second.setId(d);
367  }
368  myList[d] = skey;
369  }
370  d++;
371  }
372  myList.resize(d); // Shrink to 'd' elements
373  myListSize.relaxedStore(myList.size());
374  myHoles.clear(); // No holes
375  return true;
376 }
377 
378 template<typename T>
379 template<typename P>
380 bool
382 {
383  if (!myHoles.empty())
384  return false;
385 
386  // There's no sort on concurrent list, so we need to throw the items into a
387  // normal list for sorting.
388  UT_ASSERT(myListSize.relaxedLoad() == myList.size());
389  exint nitems = myListSize.relaxedLoad();
390  std::vector<T> items;
391  items.reserve(nitems);
392  for (exint i = 0; i < nitems; ++i)
393  {
394  items.push_back(myList[i]);
395  }
396  std::stable_sort(items.begin(), items.end(), predicate);
397  // Now, throw back into my concurrent list
398  for (exint i = 0; i < nitems; ++i)
399  {
400  myList[i] = items[i];
401  myMap[items[i]].setId(i); // Set new location
402  }
403  return true;
404 }
405 
406 template<typename T>
407 template<typename ID_ARRAY, typename T_ARRAY>
408 exint
410  ID_ARRAY &ids,
411  T_ARRAY &items,
412  exint maxitems) const
413 {
414  if (maxitems == 0)
415  return 0;
416 
417  UT_ASSERT(myListSize.relaxedLoad() == myList.size());
418  exint nitems = myListSize.relaxedLoad();
419  for (exint i = 0; i < nitems; ++i)
420  {
421  if (isValidKey(myList[i]))
422  {
423  // NOTE: GA_ATIBlob::extractBlobs() and
424  // GA_ATIBlobArray::extractBlobs rely on ids
425  // being in ascending order. (See Question #71439.)
426  ids.append(i);
427  items.append(myList[i]);
428 
429  if (items.size() >= maxitems)
430  break;
431  }
432  }
433  return items.size();
434 }
435 
436 template<typename T>
437 template<typename ID_ARRAY, typename T_ARRAY>
438 exint
440  ID_ARRAY &ids,
441  T_ARRAY &items) const
442 {
443  UT_ASSERT(myListSize.relaxedLoad() == myList.size());
444  exint nitems = myListSize.relaxedLoad();
445  for (exint i = 0; i < nitems; ++i)
446  {
447  if (isValidKey(myList[i]))
448  {
449  // NOTE: GA_ATIBlob::extractBlobs() and
450  // GA_ATIBlobArray::extractBlobs rely on ids
451  // being in ascending order. (See Question #71439.)
452  ids.append(i);
453  items.append(myList[i]);
454  }
455  }
456  return items.size();
457 }
458 
459 template<typename T>
460 template<typename T_ARRAY>
461 exint
463  T_ARRAY &items) const
464 {
465  exint nitems = myListSize.relaxedLoad();
466  for (exint i = 0; i < nitems; ++i)
467  {
468  if (isValidKey(myList[i]))
469  items.append(myList[i]);
470  }
471  return items.size();
472 }
473 
474 template<typename T>
475 int64
477 {
478  int64 mem = inclusive ? sizeof(*this) : 0;
479 
480  UT_ASSERT(myListSize.relaxedLoad() == myList.size());
481  mem += UTgetMemoryUsage(myList, false);
482  mem += UTgetMemoryUsage(myMap, false);
483  mem += UTgetMemoryUsage(myHoles, false);
484  return mem;
485 }
486 
487 #endif
unsafe_listiterator beginList() const
bool sortItems(const P &predicate)
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
png_uint_32 i
Definition: png.h:2877
GLuint id
Definition: glcorearb.h:654
const T * findItemAndId(const T &key, UT_IndexedHashSetItemId &id) const
long long int64
Definition: SYS_Types.h:107
GLdouble n
Definition: glcorearb.h:2007
int64 exint
Definition: SYS_Types.h:116
void replace(const UT_IndexedHashSet &src)
int64 getMemoryUsage(bool inclusive) const
Return approximate memory usage (not including key or item storage)
GLintptr offset
Definition: glcorearb.h:664
exint getReferenceCount(UT_IndexedHashSetItemId id) const
int64 UTgetMemoryUsage(const UT_ConcurrentHashMap< K, V, H, A > &map, const bool inclusive)
exint extractItems(ID_ARRAY &ids, T_ARRAY &items, exint maxitems) const
bool remove(const T &key)
bool compactIds(IdRemapping &remapping)
UT_IndexedHashSetItemId replaceItem(UT_IndexedHashSetItemId id, const T &key)
#define UT_VERIFY_P(expr)
Definition: UT_Assert.h:180
UT_ConcurrentQueue< UT_IndexedHashSetItemId > UT_IndexedHashSetHoleQueue
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
const T * addReference(UT_IndexedHashSetItemId id, int inc)
GLenum src
Definition: glcorearb.h:1792