shill/timeout_set.h

// Copyright 2020 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef SHILL_TIMEOUT_SET_H_
#define SHILL_TIMEOUT_SET_H_

#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <vector>

#include <base/cancelable_callback.h>
#include <base/threading/thread_task_runner_handle.h>
#include <base/time/time.h>

namespace shill {

// Class representing a set of elements, in which each element has its own
// lifetime. When the lifetime of an element has expired the element will be
// removed from the set. Users may also provide a callback in order to be
// informed if any element in the set has timed out.
//
// This class uses base::TimeTicks to represent times, resulting in a notion of
// time that never decreases, but may not increase in cases such as the computer
// being suspended. Thus elements cannot be expected to be removed exactly when
// their lifetime is expired, but they are guaranteed not to be removed prior to
// the expiration of their lifetime.
template <typename T>
class TimeoutSet {
 public:
  struct TimeElement {
    T element;
    base::TimeTicks deathtime;

    bool operator<(const TimeElement& rhs) const {
      // Since std::make_heap makes a max heap, define ordering such that the
      // greatest elements expire first.
      return deathtime >= rhs.deathtime;
    }
  };
  using const_iterator = typename std::vector<TimeElement>::const_iterator;

  virtual ~TimeoutSet() { Clear(); }

  // Set the callback used to inform clients that some elements have timed out.
  void SetInformCallback(base::Callback<void(std::vector<T>)> inform_callback) {
    inform_callback_ = std::move(inform_callback);
  }

  // Insert an element into the list with the specified lifetime. If the element
  // already exists, its lifetime will be updated. TimeDelta::Max() may be used
  // to indicate an infinite lifetime.
  //
  // This method currently runs in time linear to the number of elements in the
  // set, as duplicates are checked for prior to insertion.
  void Insert(T element, base::TimeDelta lifetime) {
    // Check for existing element.
    for (auto iter = elements_.begin(); iter != elements_.end(); ++iter) {
      if (iter->element == element) {
        elements_.erase(iter);
        std::make_heap(elements_.begin(), elements_.end());
        break;
      }
    }
    // Perform element insertion.
    base::TimeTicks deathtime =
        lifetime.is_max() ? base::TimeTicks::Max() : TimeNow() + lifetime;
    elements_.push_back({std::move(element), deathtime});
    std::push_heap(elements_.begin(), elements_.end());

    SetUpTimeoutTask();
  }

  // Remove all elements and cancel any pending timeout.
  void Clear() {
    elements_.clear();
    timeout_callback_.Cancel();
  }

  inline bool IsEmpty() const { return elements_.empty(); }

  // Call |apply_func| on each element that hasn't timed out.
  void Apply(base::Callback<void(const T& element)> apply_func) {
    for (const auto& elem : elements_) {
      apply_func.Run(elem.element);
    }
  }

  const_iterator begin() const { return elements_.cbegin(); }
  const_iterator end() const { return elements_.cend(); }
  const_iterator cbegin() const { return elements_.cbegin(); }
  const_iterator cend() const { return elements_.cend(); }

 private:
  template <typename U>
  friend class TimeoutSetTest;

  virtual base::TimeTicks TimeNow() const { return base::TimeTicks::Now(); }

  void OnTimeout() {
    std::vector<T> removed_elements;
    // Invalidate all elements that have timed out.
    while (!elements_.empty() && elements_[0].deathtime <= TimeNow()) {
      removed_elements.push_back(std::move(elements_[0].element));
      std::pop_heap(elements_.begin(), elements_.end());
      elements_.pop_back();
    }
    SetUpTimeoutTask();

    if (!inform_callback_.is_null()) {
      inform_callback_.Run(std::move(removed_elements));
    }
  }

  void SetUpTimeoutTask() {
    if (elements_.empty() || elements_[0].deathtime.is_max()) {
      return;
    }

    int64_t shortest_lifetime =
        (elements_[0].deathtime - TimeNow()).InMilliseconds();
    int64_t delay = std::max(shortest_lifetime, static_cast<int64_t>(0));
    timeout_callback_.Reset(
        base::Bind(&TimeoutSet::OnTimeout, base::Unretained(this)));
    base::ThreadTaskRunnerHandle::Get()->PostDelayedTask(
        FROM_HERE, timeout_callback_.callback(),
        base::TimeDelta::FromMilliseconds(delay));
  }

  std::vector<TimeElement> elements_;

  // Executes when an element times out. Calls OnTimeout.
  base::CancelableClosure timeout_callback_;
  // Called at the end of OnTimeout to inform user of timeout.
  base::Callback<void(std::vector<T>)> inform_callback_;
};

}  // namespace shill

#endif  // SHILL_TIMEOUT_SET_H_