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