Loading...
Searching...
No Matches
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 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
37PXR_NAMESPACE_OPEN_SCOPE
38
44template <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
53public:
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
121 TraceConcurrentList& operator=(const TraceConcurrentList&) = delete;
122
125 iterator begin() { return iterator(_head.load(std::memory_order_acquire)); }
126 iterator end() { return iterator(); }
128
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
142private:
143 std::atomic<Node*> _head;
144 tbb::cache_aligned_allocator<Node> _alloc;
145};
146
147PXR_NAMESPACE_CLOSE_SCOPE
148
149#endif // PXR_BASE_TRACE_CONCURRENT_LIST_H
Provide architecture-specific memory-alignment information.
This class provides forward iterator support to iterate over all the items.
This class supports thread safe insertion and iteration over a list of items.
TraceConcurrentList()
Constructor.
iterator Insert()
Inserts an item at the beginning of the list and returns an iterator to the newly created item.
~TraceConcurrentList()
Destructor.