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