Move request_queue/_impl to //extensions

BUG=398671

Review URL: https://codereview.chromium.org/657693002

Cr-Commit-Position: refs/heads/master@{#299757}

2 files changed, 296 insertions, 0 deletions

diff --git a/extensions/browser/updater/request_queue.h b/extensions/browser/updater/request_queue.h
new file mode 100644
index 0000000..0e3d2eb
--- /dev/null
+++ b/extensions/browser/updater/request_queue.h
@@ -0,0 +1,142 @@
+// Copyright (c) 2012 The Chromium 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 EXTENSIONS_BROWSER_UPDATER_REQUEST_QUEUE_H_
+#define EXTENSIONS_BROWSER_UPDATER_REQUEST_QUEUE_H_
+
+#include <deque>
+#include <utility>
+
+#include "base/callback.h"
+#include "base/memory/linked_ptr.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/time/time.h"
+#include "base/timer/timer.h"
+#include "net/base/backoff_entry.h"
+
+namespace extensions {
+
+// This class keeps track of a queue of requests, and contains the logic to
+// retry requests with some backoff policy. Each request has a
+// net::BackoffEntry instance associated with it.
+//
+// The general flow when using this class would be something like this:
+//   - requests are queued up by calling ScheduleRequest.
+//   - when a request is ready to be executed, RequestQueue removes the
+//     request from the queue, assigns it as active request, and calls
+//     the callback that was passed to the constructor.
+//   - (optionally) when a request has completed unsuccessfully call
+//     RetryRequest to put the request back in the queue, using the
+//     backoff policy and minimum backoff delay to determine when to
+//     next schedule this request.
+//   - call reset_active_request() to indicate that the active request has
+//     been dealt with.
+//   - call StartNextRequest to schedule the next pending request (if any).
+template <typename T>
+class RequestQueue {
+ public:
+  class iterator;
+
+  RequestQueue(const net::BackoffEntry::Policy* backoff_policy,
+               const base::Closure& start_request_callback);
+  ~RequestQueue();
+
+  // Returns the request that is currently being processed.
+  T* active_request();
+
+  // Returns the number of times the current request has been retried already.
+  int active_request_failure_count();
+
+  // Signals RequestQueue that processing of the current request has completed.
+  scoped_ptr<T> reset_active_request();
+
+  // Add the given request to the queue, and starts the next request if no
+  // request is currently being processed.
+  void ScheduleRequest(scoped_ptr<T> request);
+
+  bool empty() const;
+  size_t size() const;
+
+  // Returns the earliest release time of all requests currently in the queue.
+  base::TimeTicks NextReleaseTime() const;
+
+  // Starts the next request, if no request is currently active. This will
+  // synchronously call the start_request_callback if the release time of the
+  // earliest available request is in the past, otherwise it will call that
+  // callback asynchronously after enough time has passed.
+  void StartNextRequest();
+
+  // Tell RequestQueue to put the current request back in the queue, after
+  // applying the backoff policy to determine when to next try this request.
+  // If the policy results in a backoff delay smaller than |min_backoff_delay|,
+  // that delay is used instead.
+  void RetryRequest(const base::TimeDelta& min_backoff_delay);
+
+  iterator begin();
+  iterator end();
+
+  // Change the backoff policy used by the queue.
+  void set_backoff_policy(const net::BackoffEntry::Policy* backoff_policy);
+
+ private:
+  struct Request {
+    Request(net::BackoffEntry* backoff_entry, T* request)
+        : backoff_entry(backoff_entry), request(request) {}
+    linked_ptr<net::BackoffEntry> backoff_entry;
+    linked_ptr<T> request;
+  };
+
+  // Compares the release time of two pending requests.
+  static bool CompareRequests(const Request& a, const Request& b);
+
+  // Pushes a request with a given backoff entry onto the queue.
+  void PushImpl(scoped_ptr<T> request,
+                scoped_ptr<net::BackoffEntry> backoff_entry);
+
+  // The backoff policy used to determine backoff delays.
+  const net::BackoffEntry::Policy* backoff_policy_;
+
+  // Callback to call when a new request has become the active request.
+  base::Closure start_request_callback_;
+
+  // Priority queue of pending requests. Not using std::priority_queue since
+  // the code needs to be able to iterate over all pending requests.
+  std::deque<Request> pending_requests_;
+
+  // Active request and its associated backoff entry.
+  scoped_ptr<T> active_request_;
+  scoped_ptr<net::BackoffEntry> active_backoff_entry_;
+
+  // Timer to schedule calls to StartNextRequest, if the first pending request
+  // hasn't passed its release time yet.
+  base::Timer timer_;
+};
+
+// Iterator class that wraps a std::deque<> iterator, only giving access to the
+// actual request part of each item.
+template <typename T>
+class RequestQueue<T>::iterator {
+ public:
+  iterator() {}
+
+  T* operator*() { return it_->request.get(); }
+  T* operator->() { return it_->request.get(); }
+  iterator& operator++() {
+    ++it_;
+    return *this;
+  }
+  bool operator!=(const iterator& b) const { return it_ != b.it_; }
+
+ private:
+  friend class RequestQueue<T>;
+  typedef std::deque<typename RequestQueue<T>::Request> Container;
+
+  explicit iterator(const typename Container::iterator& it) : it_(it) {}
+
+  typename Container::iterator it_;
+};
+
+}  // namespace extensions
+
+#endif  // EXTENSIONS_BROWSER_UPDATER_REQUEST_QUEUE_H_
diff --git a/extensions/browser/updater/request_queue_impl.h b/extensions/browser/updater/request_queue_impl.h
new file mode 100644
index 0000000..309dc82
--- /dev/null
+++ b/extensions/browser/updater/request_queue_impl.h
@@ -0,0 +1,154 @@
+// Copyright (c) 2012 The Chromium 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 EXTENSIONS_BROWSER_UPDATER_REQUEST_QUEUE_IMPL_H_
+#define EXTENSIONS_BROWSER_UPDATER_REQUEST_QUEUE_IMPL_H_
+
+#include <algorithm>
+
+#include "base/bind.h"
+#include "base/compiler_specific.h"
+#include "base/message_loop/message_loop.h"
+#include "base/stl_util.h"
+#include "extensions/browser/updater/request_queue.h"
+
+namespace extensions {
+
+template <typename T>
+RequestQueue<T>::RequestQueue(
+    const net::BackoffEntry::Policy* const backoff_policy,
+    const base::Closure& start_request_callback)
+    : backoff_policy_(backoff_policy),
+      start_request_callback_(start_request_callback),
+      timer_(false, false) {
+}
+
+template <typename T>
+RequestQueue<T>::~RequestQueue() {
+}
+
+template <typename T>
+T* RequestQueue<T>::active_request() {
+  return active_request_.get();
+}
+
+template <typename T>
+int RequestQueue<T>::active_request_failure_count() {
+  return active_backoff_entry_->failure_count();
+}
+
+template <typename T>
+scoped_ptr<T> RequestQueue<T>::reset_active_request() {
+  active_backoff_entry_.reset();
+  return active_request_.Pass();
+}
+
+template <typename T>
+void RequestQueue<T>::ScheduleRequest(scoped_ptr<T> request) {
+  PushImpl(
+      request.Pass(),
+      scoped_ptr<net::BackoffEntry>(new net::BackoffEntry(backoff_policy_)));
+  StartNextRequest();
+}
+
+template <typename T>
+void RequestQueue<T>::PushImpl(scoped_ptr<T> request,
+                               scoped_ptr<net::BackoffEntry> backoff_entry) {
+  pending_requests_.push_back(
+      Request(backoff_entry.release(), request.release()));
+  std::push_heap(
+      pending_requests_.begin(), pending_requests_.end(), CompareRequests);
+}
+
+template <typename T>
+bool RequestQueue<T>::empty() const {
+  return pending_requests_.empty();
+}
+
+template <typename T>
+size_t RequestQueue<T>::size() const {
+  return pending_requests_.size();
+}
+
+template <typename T>
+base::TimeTicks RequestQueue<T>::NextReleaseTime() const {
+  return pending_requests_.front().backoff_entry->GetReleaseTime();
+}
+
+template <typename T>
+void RequestQueue<T>::StartNextRequest() {
+  if (active_request_)
+    // Already running a request, assume this method will be called again when
+    // the request is done.
+    return;
+
+  if (empty())
+    // No requests in the queue, so we're done.
+    return;
+
+  base::TimeTicks next_release = NextReleaseTime();
+  base::TimeTicks now = base::TimeTicks::Now();
+  if (next_release > now) {
+    // Not ready for the next update check yet, call this method when it is
+    // time.
+    timer_.Start(
+        FROM_HERE,
+        next_release - now,
+        base::Bind(&RequestQueue<T>::StartNextRequest, base::Unretained(this)));
+    return;
+  }
+
+  // pop_heap swaps the first and last elements of pending_requests_, and after
+  // that assures that the rest of pending_requests_ (excluding the
+  // now last/formerly first element) forms a proper heap. After pop_heap
+  // [begin, end-1) is a valid heap, and *(end - 1) contains the element that
+  // used to be at the top of the heap. Since no elements are actually
+  // removed from the container it is safe to read the entry being removed after
+  // pop_heap is called (but before pop_back is called).
+  std::pop_heap(
+      pending_requests_.begin(), pending_requests_.end(), CompareRequests);
+
+  active_backoff_entry_.reset(pending_requests_.back().backoff_entry.release());
+  active_request_.reset(pending_requests_.back().request.release());
+
+  pending_requests_.pop_back();
+
+  start_request_callback_.Run();
+}
+
+template <typename T>
+void RequestQueue<T>::RetryRequest(const base::TimeDelta& min_backoff_delay) {
+  active_backoff_entry_->InformOfRequest(false);
+  if (active_backoff_entry_->GetTimeUntilRelease() < min_backoff_delay) {
+    active_backoff_entry_->SetCustomReleaseTime(base::TimeTicks::Now() +
+                                                min_backoff_delay);
+  }
+  PushImpl(active_request_.Pass(), active_backoff_entry_.Pass());
+}
+
+template <typename T>
+typename RequestQueue<T>::iterator RequestQueue<T>::begin() {
+  return iterator(pending_requests_.begin());
+}
+
+template <typename T>
+typename RequestQueue<T>::iterator RequestQueue<T>::end() {
+  return iterator(pending_requests_.end());
+}
+
+template <typename T>
+void RequestQueue<T>::set_backoff_policy(
+    const net::BackoffEntry::Policy* backoff_policy) {
+  backoff_policy_ = backoff_policy;
+}
+
+// static
+template <typename T>
+bool RequestQueue<T>::CompareRequests(const Request& a, const Request& b) {
+  return a.backoff_entry->GetReleaseTime() > b.backoff_entry->GetReleaseTime();
+}
+
+}  // namespace extensions
+
+#endif  // EXTENSIONS_BROWSER_UPDATER_REQUEST_QUEUE_IMPL_H_