Refactoring of job dispatch in HostResolverImpl in preparation for DnsClient.

net/base/priority_queue.h

+// 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.

[mmenke, 2011/12/21 16:22:58]

nit:  "when the queue is destroyed or the value is erased or moved"

[szym, 2011/12/28 01:24:10]

Done.

+  class Pointer {
+   public:
+    // Constructs a null pointer.
+    Pointer() : priority_(NUM_PRIORITIES) {}
+
+    bool is_null() const { return iterator_ == ListIterator(); }

[szym, 2011/12/20 16:48:39]

This is not allowed in MSVC. Working on fix.

+    RequestPriority priority() const { return priority_; }

[mmenke, 2011/12/21 16:22:58]

nit:  const

+
+    T& value() { return *iterator_; }
+    const T& value() const { return *iterator_; }
+
+    bool equals(const Pointer& other) const {
+      // list::iterator is unique.
+      return iterator_ == other.iterator_;

[szym, 2011/12/20 16:48:39]

Ditto, when the iterators are from different lists.

+    }
+
+   protected:
+    friend class PriorityQueue;

[mmenke, 2011/12/21 16:22:58]

nit:  Could you point a line break here?

[szym, 2011/12/28 01:24:10]

Done.

+    Pointer(RequestPriority priority, const ListIterator& iterator)
+        : priority_(priority), iterator_(iterator) {}
+
+    RequestPriority priority_;

[mmenke, 2011/12/21 16:22:58]

Currently, this can be const.  iterator_, too.  My other comments will change
that, but at least the iterator can be made kept const, I believe.

[szym, 2011/12/21 22:19:34]

If this is const, then the default operator= would not work.

+    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) {

[mmenke, 2011/12/21 16:22:58]

It's kinda odd to take a const reference, and then make it invalid.  I'd suggest
taking a non-const pointer instead, even though yes, you don't actually modify
it.  Same goes for Move().

Think that, for debugging purposes, it would also be a good idea to modify
|pointer| so we can have a DCHECK on re-use.  Setting its priority to
MAX_PRIORITY is probably the simplest way to do this.

[szym, 2011/12/21 22:19:34]

Agreed that invalidating |pointer| would make sense. However, an API that takes
Pointer* would forbid |queue.Erase(queue.Front())|

[mmenke, 2011/12/21 22:35:42]

I believe that |queue.Erase(&queue.Front())| should still work.

[szym, 2011/12/28 01:24:10]

Unfortunately, can't take address of a temporary. I left it unchanged.

+    --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) {

[mmenke, 2011/12/21 16:22:58]

I think "ChangePriority" or "Reprioritize" or "UpdatePriority" would be clearer
than "Move".

[szym, 2011/12/28 01:24:10]

Removed completely.

+    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() {

[mmenke, 2011/12/21 16:22:58]

Believe this and the next two functions can all be const.

[szym, 2011/12/28 01:24:10]

Unfortunately, then List would have be const and then we could only pass
const_iterator to Pointer. This would make Pointer useless for Erase.

This problem will go away in C++0x:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3092.pdf

Until then, I see two ways to resolve:
A) Create Pointer vs. ConstPointer and two different version of each
First/Last/OldestLowest.
B) Move to base/linked_list.h. Although that is exploiting the fact that
base::LinkedList can be const while other parts of it are modified.

For now, I left it as is.

+    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 priority = 0; priority < NUM_PRIORITIES; ++priority) {
+      List& list = lists_[NUM_PRIORITIES - priority - 1];
+      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 priority = 0; priority < NUM_PRIORITIES; ++priority) {
+      List& list = lists_[NUM_PRIORITIES - priority - 1];
+      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_
+