Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <atomic>
7 : #include <cstddef>
8 : #include <iterator>
9 : #include <limits>
10 : #include <memory>
11 : #include <mutex>
12 : #include <optional>
13 :
14 : /// \cond
15 : namespace PUP {
16 : class er;
17 : } // namespace PUP
18 : /// \endcond
19 :
20 0 : namespace domain::FunctionsOfTime::FunctionOfTimeHelpers {
21 : namespace ThreadsafeList_detail {
22 : template <typename T>
23 : struct Interval;
24 : } // namespace ThreadsafeList_detail
25 :
26 : /// A list of time intervals that allows safe access to existing
27 : /// elements even during modification.
28 : ///
29 : /// Concurrent modification is not supported. All non-modifying
30 : /// operations except for serialization can be safely performed in
31 : /// parallel with each other and with `insert` and will return a
32 : /// consistent state.
33 : template <typename T>
34 1 : class ThreadsafeList {
35 : private:
36 0 : using Interval = ThreadsafeList_detail::Interval<T>;
37 :
38 : public:
39 : /// No operations are valid on a default-initialized object except
40 : /// for assignment and deserialization.
41 1 : ThreadsafeList();
42 0 : ThreadsafeList(ThreadsafeList&& other);
43 0 : ThreadsafeList(const ThreadsafeList& other);
44 0 : ThreadsafeList& operator=(ThreadsafeList&& other);
45 0 : ThreadsafeList& operator=(const ThreadsafeList& other);
46 0 : ~ThreadsafeList();
47 :
48 0 : explicit ThreadsafeList(double initial_time);
49 :
50 : /// Insert data valid over the interval from \p update_time to \p
51 : /// expiration_time.
52 : ///
53 : /// The \p update_time must be the same as the old expiration time.
54 : /// It is passed as a check that the calling code is computing the
55 : /// other arguments with the correct value.
56 1 : void insert(double update_time, T data, double expiration_time);
57 :
58 0 : struct IntervalInfo {
59 0 : double update;
60 0 : const T& data;
61 0 : double expiration;
62 :
63 0 : friend bool operator==(const IntervalInfo& a, const IntervalInfo& b) {
64 : return a.update == b.update and a.data == b.data and
65 : a.expiration == b.expiration;
66 : }
67 0 : friend bool operator!=(const IntervalInfo& a, const IntervalInfo& b) {
68 : return not(a == b);
69 : }
70 : };
71 :
72 : /// Obtain the start time, data, and expiration time for the time
73 : /// interval containing \p time.
74 : ///
75 : /// If \p time is at an interval boundary, the earlier interval is
76 : /// returned, except for the initial time, which returns the first
77 : /// interval.
78 1 : IntervalInfo operator()(double time) const;
79 :
80 0 : double initial_time() const;
81 :
82 : /// The expiration time of the last data interval.
83 1 : double expiration_time() const;
84 :
85 : /// The first interval boundary after \p time. If \p time is an
86 : /// interval boundary, the one after it is returned.
87 1 : double expiration_after(double time) const;
88 :
89 : /// Remove the oldest data in the list, leaving at least \p length
90 : /// entries.
91 : ///
92 : /// If the list is truncated to zero length, the caller must ensure
93 : /// that no concurrent access or modification is performed. The
94 : /// list is guaranteed to be empty afterwards.
95 : ///
96 : /// Otherwise, it is the caller's responsibility to ensure that,
97 : /// during this call, no reader attempts to look up what will become
98 : /// the new oldest interval. Storing references to that interval's
99 : /// data is safe, and lookups of that interval are safe if they are
100 : /// sequenced after this call. Concurrent insertions are safe, and
101 : /// concurrent access to newer intervals is safe. Concurrent calls
102 : /// to truncate functions and serialization are protected by
103 : /// mutexes, but other concurrent calls are lock-free.
104 : ///
105 : /// If the list is initially shorter than \p length, it is left
106 : /// unchanged. Otherwise, if concurrent insertions occur, the
107 : /// amount of removed data is approximate, but will not leave the
108 : /// list shorter than the requested value. In the absence of
109 : /// concurrent modifications, the list will be left with exactly the
110 : /// requested length.
111 1 : void truncate_to_length(size_t length);
112 :
113 : /// Remove the oldest data in the list, retaining data needed to
114 : /// access at least as far back as \p time.
115 : ///
116 : /// If \p time is before `initial_time()`, the list is not modified.
117 : /// If \p time is after `expiration_time()`, the amount of removed
118 : /// data is unspecified.
119 : ///
120 : /// The amount of removed data is approximate. There may be
121 : /// slightly more data remaining after a call than requested.
122 : ///
123 : /// It is safe to insert and access data concurrently with
124 : /// truncation, as long as the accessed times are not before the
125 : /// truncation time. Concurrent calls to truncate functions and
126 : /// serialization are protected by mutexes, but other concurrent
127 : /// calls are lock-free.
128 1 : void truncate_at_time(double time);
129 :
130 : /// Empty the list. Equivalent to `truncate_to_length(0)`. See
131 : /// that method for details.
132 1 : void clear();
133 :
134 0 : void pup(PUP::er& p);
135 :
136 0 : class iterator {
137 : public:
138 0 : using iterator_category = std::input_iterator_tag;
139 0 : using value_type = IntervalInfo;
140 0 : using reference = value_type;
141 0 : using pointer = std::optional<value_type>;
142 0 : using difference_type = std::ptrdiff_t;
143 :
144 0 : iterator() = default;
145 0 : iterator& operator++();
146 0 : iterator operator++(int);
147 0 : reference operator*() const;
148 0 : pointer operator->() const;
149 :
150 0 : friend bool operator==(const iterator& a, const iterator& b) {
151 : return a.interval_ == b.interval_;
152 : }
153 0 : friend bool operator!=(const iterator& a, const iterator& b) {
154 : return not(a == b);
155 : }
156 :
157 : private:
158 0 : friend class ThreadsafeList;
159 :
160 0 : iterator(const ThreadsafeList* parent, const Interval* interval);
161 :
162 0 : const ThreadsafeList* parent_ = nullptr;
163 0 : const Interval* interval_ = nullptr;
164 : };
165 :
166 : /// Iterate over all the intervals in the list, in reverse order
167 : /// (i.e., most recent first).
168 : /// @{
169 1 : iterator begin() const;
170 1 : iterator end() const;
171 : /// @}
172 :
173 : private:
174 : // interval_after_boundary controls behavior at boundary points.
175 : // True -> later interval, false -> earlier. Initial time always
176 : // gives the first interval.
177 0 : const Interval& find_interval(double time,
178 : bool interval_after_boundary) const;
179 :
180 0 : alignas(64) std::atomic<double> initial_time_ =
181 : std::numeric_limits<double>::signaling_NaN();
182 : // Pad memory to avoid false-sharing when accessing initial_time_
183 : // NOLINTNEXTLINE(modernize-avoid-c-arrays)
184 0 : char unused_padding_initial_time_[64 - (sizeof(initial_time_) % 64)] = {};
185 0 : std::unique_ptr<Interval> interval_list_{};
186 0 : alignas(64) std::atomic<Interval*> most_recent_interval_{};
187 : // Pad memory to avoid false-sharing when accessing most_recent_interval_
188 : // NOLINTNEXTLINE(modernize-avoid-c-arrays)
189 : char
190 0 : unused_padding_most_recent_interval_[64 - (sizeof(most_recent_interval_) %
191 : 64)] = {};
192 : // Mutex protecting methods that access the tail of the list, i.e.,
193 : // truncation and serialization. Other methods are assumed to be
194 : // called with parameters that will not interact with truncation.
195 0 : std::mutex truncation_mutex_{};
196 : };
197 :
198 : template <typename T>
199 0 : bool operator==(const ThreadsafeList<T>& a, const ThreadsafeList<T>& b);
200 :
201 : template <typename T>
202 0 : bool operator!=(const ThreadsafeList<T>& a, const ThreadsafeList<T>& b);
203 : } // namespace domain::FunctionsOfTime::FunctionOfTimeHelpers
|
