VTK  9.1.0
vtkSMPThreadLocalBackend.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkSMPThreadLocalBackend.h
5 
6  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7  All rights reserved.
8  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9 
10  This software is distributed WITHOUT ANY WARRANTY; without even
11  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12  PURPOSE. See the above copyright notice for more information.
13 
14 =========================================================================*/
15 
16 // Thread Specific Storage is implemented as a Hash Table, with the Thread Id
17 // as the key and a Pointer to the data as the value. The Hash Table implements
18 // Open Addressing with Linear Probing. A fixed-size array (HashTableArray) is
19 // used as the hash table. The size of this array is allocated to be large
20 // enough to store thread specific data for all the threads with a Load Factor
21 // of 0.5. In case the number of threads changes dynamically and the current
22 // array is not able to accommodate more entries, a new array is allocated that
23 // is twice the size of the current array. To avoid rehashing and blocking the
24 // threads, a rehash is not performed immediately. Instead, a linked list of
25 // hash table arrays is maintained with the current array at the root and older
26 // arrays along the list. All lookups are sequentially performed along the
27 // linked list. If the root array does not have an entry, it is created for
28 // faster lookup next time. The ThreadSpecific::GetStorage() function is thread
29 // safe and only blocks when a new array needs to be allocated, which should be
30 // rare.
31 
32 #ifndef OpenMPvtkSMPThreadLocalBackend_h
33 #define OpenMPvtkSMPThreadLocalBackend_h
34 
35 #include "vtkCommonCoreModule.h" // For export macro
36 #include "vtkSystemIncludes.h"
37 
38 #include <atomic>
39 #include <omp.h>
40 
41 namespace vtk
42 {
43 namespace detail
44 {
45 namespace smp
46 {
47 namespace OpenMP
48 {
49 
50 typedef void* ThreadIdType;
51 typedef vtkTypeUInt32 HashType;
52 typedef void* StoragePointerType;
53 
54 struct Slot
55 {
56  std::atomic<ThreadIdType> ThreadId;
57  omp_lock_t ModifyLock;
59 
60  Slot();
61  ~Slot();
62 
63 private:
64  // not copyable
65  Slot(const Slot&);
66  void operator=(const Slot&);
67 };
68 
70 {
71  size_t Size, SizeLg;
72  std::atomic<size_t> NumberOfEntries;
75 
76  explicit HashTableArray(size_t sizeLg);
78 
79 private:
80  // disallow copying
82  void operator=(const HashTableArray&);
83 };
84 
85 class VTKCOMMONCORE_EXPORT ThreadSpecific
86 {
87 public:
88  explicit ThreadSpecific(unsigned numThreads);
89  virtual ~ThreadSpecific() final;
90 
91  StoragePointerType& GetStorage();
92  size_t Size() const;
93 
94 private:
95  std::atomic<HashTableArray*> Root;
96  std::atomic<size_t> Count;
97 
99 };
100 
101 inline size_t ThreadSpecific::Size() const
102 {
103  return this->Count;
104 }
105 
107 {
108 public:
110  : ThreadSpecificStorage(nullptr)
111  , CurrentArray(nullptr)
112  , CurrentSlot(0)
113  {
114  }
115 
117  {
118  this->ThreadSpecificStorage = &threadSpecifc;
119  }
120 
121  void SetToBegin()
122  {
123  this->CurrentArray = this->ThreadSpecificStorage->Root;
124  this->CurrentSlot = 0;
125  if (!this->CurrentArray->Slots->Storage)
126  {
127  this->Forward();
128  }
129  }
130 
131  void SetToEnd()
132  {
133  this->CurrentArray = nullptr;
134  this->CurrentSlot = 0;
135  }
136 
137  bool GetInitialized() const { return this->ThreadSpecificStorage != nullptr; }
138 
139  bool GetAtEnd() const { return this->CurrentArray == nullptr; }
140 
141  void Forward()
142  {
143  for (;;)
144  {
145  if (++this->CurrentSlot >= this->CurrentArray->Size)
146  {
147  this->CurrentArray = this->CurrentArray->Prev;
148  this->CurrentSlot = 0;
149  if (!this->CurrentArray)
150  {
151  break;
152  }
153  }
154  Slot* slot = this->CurrentArray->Slots + this->CurrentSlot;
155  if (slot->Storage)
156  {
157  break;
158  }
159  }
160  }
161 
163  {
164  Slot* slot = this->CurrentArray->Slots + this->CurrentSlot;
165  return slot->Storage;
166  }
167 
169  {
170  return (this->ThreadSpecificStorage == it.ThreadSpecificStorage) &&
171  (this->CurrentArray == it.CurrentArray) && (this->CurrentSlot == it.CurrentSlot);
172  }
173 
174 private:
175  ThreadSpecific* ThreadSpecificStorage;
176  HashTableArray* CurrentArray;
177  size_t CurrentSlot;
178 };
179 
180 } // OpenMP;
181 } // namespace smp
182 } // namespace detail
183 } // namespace vtk
184 
185 #endif
bool operator==(const ThreadSpecificStorageIterator &it) const
Specialization of tuple ranges and iterators for vtkAOSDataArrayTemplate.
std::atomic< ThreadIdType > ThreadId