Refactoring of job dispatch in HostResolverImpl in preparation for DnsClient.

net/base/priority_queue.h

Index: net/base/priority_queue.h
diff --git a/net/base/priority_queue.h b/net/base/priority_queue.h
new file mode 100644
index 0000000000000000000000000000000000000000..763b5e50837e0c3691c12fe2728dc20e93a9056e
--- /dev/null
+++ b/net/base/priority_queue.h
@@ -0,0 +1,133 @@
+// Copyright (c) 2011 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 NET_BASE_PRIORITY_QUEUE_H_
+#define NET_BASE_PRIORITY_QUEUE_H_
+#pragma once
+
+#include <list>
+
+#include "base/basictypes.h"
+#include "net/base/net_export.h"
+#include "net/base/request_priority.h"
+
+namespace net {
+
+// A simple priority queue. The order of values is by RequestPriority and then
+// FIFO. The queue supports changing the priority of its elements.
+// All operations are O(1) time (assuming constant NUM_PRIORITIES).
+template<typename T>
+class PriorityQueue {
+ public:
+  typedef std::list<T> List;
+  typedef typename std::list<T>::iterator ListIterator;
+
+  // A pointer to a value stored in the queue. The pointer becomes invalid
+  // when the queue is destroyed, the value is erased, or moved.
+  class Pointer {
+   public:
+    // Constructs a null pointer.
+    Pointer() : priority_(NUM_PRIORITIES) {}
+
+    bool is_null() const { return priority_ == NUM_PRIORITIES; }
+    RequestPriority priority() const { return priority_; }
+
+    T& value() { return *iterator_; }
+    const T& value() const { return *iterator_; }
+
+    // Comparing to Pointer from a different PriorityQueue is undefined.
+    bool equals(const Pointer& other) const {
+      return (priority_ == other.priority_) && (iterator_ == other.iterator_);
+    }
+
+   protected:
+    friend class PriorityQueue;
+    Pointer(RequestPriority priority, const ListIterator& iterator)
+        : priority_(priority), iterator_(iterator) {}
+
+    RequestPriority priority_;
+    ListIterator iterator_;
+  };
+
+  PriorityQueue() : size_(0) {}
+
+  // Adds |value| with |priority| to the queue. Returns a pointer to the
+  // created element.
+  Pointer Insert(const T& value, RequestPriority priority) {
+    ++size_;
+    List& list = lists_[priority];
+    return Pointer(priority, list.insert(list.end(), value));
+  }
+
+  // Removes the value pointed by |pointer| from the queue. All pointers to this
+  // value including |pointer| become invalid.
+  void Erase(const Pointer& pointer) {
+    --size_;
+    lists_[pointer.priority_].erase(pointer.iterator_);
+  }
+
+  // Moves the value pointed by |pointer| to the end of all values with priority
+  // |priority| and returns a pointer to the moved value. All pointers to this
+  // value become invalid. No-op if priority is not changed.
+  Pointer Move(const Pointer& pointer, RequestPriority priority) {
+    if (pointer.priority_ == priority)
+      return pointer;
+    List& list = lists_[priority];
+    list.splice(list.end(), lists_[pointer.priority_], pointer.iterator_);
+    return Pointer(priority, --list.end());
+  }
+
+  // Returns a pointer to the first value in order or a null-pointer if empty.
+  Pointer First() {
+    for (size_t priority = 0; priority < NUM_PRIORITIES; ++priority) {
+      List& list = lists_[priority];
+      if (!list.empty())
+        return Pointer(static_cast<RequestPriority>(priority), list.begin());
+    }
+    return Pointer();
+  }
+
+  // Returns a pointer to the last value in order or a null-pointer if empty.
+  Pointer Last() {
+    for (size_t i = 0; i < NUM_PRIORITIES; ++i) {
+      size_t priority = NUM_PRIORITIES - i - 1;
+      List& list = lists_[priority];
+      if (!list.empty())
+        return Pointer(static_cast<RequestPriority>(priority), --list.end());
+    }
+    return Pointer();
+  }
+
+  // Returns a pointer to the oldest, lowest value or a null-pointer if empty.
+  Pointer OldestLowest() {
+    for (size_t i = 0; i < NUM_PRIORITIES; ++i) {
+      size_t priority = NUM_PRIORITIES - i - 1;
+      List& list = lists_[priority];
+      if (!list.empty())
+        return Pointer(static_cast<RequestPriority>(priority), list.begin());
+    }
+    return Pointer();
+  }
+
+  // Empties the queue. All pointers become invalid.
+  void Clear() {
+    for (size_t priority = 0; priority < NUM_PRIORITIES; ++priority)
+      lists_[priority].clear();
+    size_ = 0u;
+  }
+
+  // Returns number of queued values.
+  size_t size() const {
+    return size_;
+  }
+
+ private:
+  List lists_[NUM_PRIORITIES];
+  size_t size_;
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_PRIORITY_QUEUE_H_
+