All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
concurrentList.h
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 TRACE_CONCURRENT_LIST_H
26 #define 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 
37 PXR_NAMESPACE_OPEN_SCOPE
38 
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:
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 
71  pointer operator->() {
72  return _node ? &_node->value : nullptr;
73  }
74 
75  reference operator*() {
76  return _node->value;
77  }
78 
79  iterator& operator++() {
80  _node = _node->next;
81  return *this;
82  }
83 
84  iterator operator++(int) {
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 
105  TraceConcurrentList() : _head(nullptr) {}
106 
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;
121  TraceConcurrentList& operator=(const TraceConcurrentList&) = delete;
122 
125  iterator begin() { return iterator(_head.load(std::memory_order_acquire)); }
126  iterator end() { return iterator(); }
128 
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 
147 PXR_NAMESPACE_CLOSE_SCOPE
148 
149 #endif // TRACE_CONCURRENT_LIST_H
iterator Insert()
Inserts an item at the beginning of the list and returns an iterator to the newly created item...
~TraceConcurrentList()
Destructor.
This class supports thread safe insertion and iteration over a list of items.
This class provides forward iterator support to iterate over all the items.
TraceConcurrentList()
Constructor.