HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
concurrentList.h
Go to the documentation of this file.
1 //
2 // Copyright 2018 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 
25 #ifndef PXR_BASE_TRACE_CONCURRENT_LIST_H
26 #define PXR_BASE_TRACE_CONCURRENT_LIST_H
27 
28 #include "pxr/pxr.h"
29 
30 #include "pxr/base/arch/align.h"
31 
32 #include <tbb/cache_aligned_allocator.h>
33 
34 #include <atomic>
35 #include <iterator>
36 
38 
39 ////////////////////////////////////////////////////////////////////////////////
40 /// \class TraceConcurrentList
41 ///
42 /// This class supports thread safe insertion and iteration over a list of items.
43 ///
44 template <typename T>
46 
47  // Linked list node that is cache line aligned to prevent false sharing.
48  struct alignas(ARCH_CACHE_LINE_SIZE*2) Node {
49  T value;
50  Node* next;
51  };
52 
53 public:
54  ////////////////////////////////////////////////////////////////////////////
55  /// \class iterator
56  ///
57  /// This class provides forward iterator support to iterate over all the
58  /// items.
59  ///
60  class iterator {
61  public:
62  // iterator types
63  using iterator_category = std::forward_iterator_tag;
64  using value = T;
65  using pointer = T*;
66  using reference = T&;
67  using difference_type = ptrdiff_t;
68 
69  iterator() : _node(nullptr) {}
70 
72  return _node ? &_node->value : nullptr;
73  }
74 
76  return _node->value;
77  }
78 
80  _node = _node->next;
81  return *this;
82  }
83 
85  iterator result(*this);
86  _node = _node->next;
87  return result;
88  }
89 
90  bool operator !=(const iterator& other) const {
91  return _node != other._node;
92  }
93 
94  bool operator ==(const iterator& other) const {
95  return _node == other._node;
96  }
97 
98  private:
99  explicit iterator(Node* node) : _node(node) {}
100  Node* _node;
101  friend class TraceConcurrentList;
102  };
103 
104  /// Constructor.
105  TraceConcurrentList() : _head(nullptr) {}
106 
107  /// Destructor.
109  // Delete all nodes in the list.
110  Node* curNode = _head.load(std::memory_order_acquire);
111  while (curNode) {
112  Node* nodeToDelete = curNode;
113  curNode = curNode->next;
114  _alloc.destroy(nodeToDelete);
115  _alloc.deallocate(nodeToDelete, 1);
116  }
117  }
118 
119  // No copies
120  TraceConcurrentList(const TraceConcurrentList&) = delete;
122 
123  /// \name Iterator support.
124  /// @{
125  iterator begin() { return iterator(_head.load(std::memory_order_acquire)); }
126  iterator end() { return iterator(); }
127  /// @}
128 
129  /// Inserts an item at the beginning of the list and returns an iterator to
130  /// the newly created item.
131  iterator Insert() {
132  Node* newNode = _alloc.allocate(1);
133  _alloc.construct(newNode);
134 
135  // Add the node to the linked list in an atomic manner.
136  do {
137  newNode->next = _head.load(std::memory_order_relaxed);
138  } while (!_head.compare_exchange_weak(newNode->next, newNode));
139  return iterator(newNode);
140  }
141 
142 private:
143  std::atomic<Node*> _head;
144  tbb::cache_aligned_allocator<Node> _alloc;
145 };
146 
148 
149 #endif // PXR_BASE_TRACE_CONCURRENT_LIST_H
std::forward_iterator_tag iterator_category
Definition: Node.h:52
GLsizei const GLfloat * value
Definition: glcorearb.h:824
**But if you need a result
Definition: thread.h:613
bool operator!=(const iterator &other) const
Node(ElementPtr parent, const string &name)
Definition: Node.h:55
TraceConcurrentList & operator=(const TraceConcurrentList &)=delete
TraceConcurrentList()
Constructor.
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1432
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
~TraceConcurrentList()
Destructor.
bool operator==(const iterator &other) const