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..c4f14f09bfaaf4e4126ba34d6d2adca352114c43
--- /dev/null
+++ b/net/base/priority_queue.h
@@ -0,0 +1,125 @@
+// 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

[cbentzel, 2012/01/03 19:39:09]

It would be nice if this weren't coupled with RequestPriority/NUM_PRIORITIES so
it could be used in more situations.

Either make the number of priorities a constructor argument, or possibly a
non-type template parameter (although I am worried about code duplication in
that case). 

[szym, 2012/01/03 20:48:52]

Having NUM_PRIORITIES const allows the compiler to unroll some of the for loops,
but I doubt that it actually matters much. 

One caveat if we want decouple from RequestPriority/NUM_PRIORITIES: the callers
will need to explicitly cast Pointer/Handle::priority() from int to
RequestPriority.

+// FIFO. The queue supports changing the priority of its elements.

[cbentzel, 2012/01/03 19:39:09]

How do you change the priority of the elements? I can't see anything about that,
other than doing an Erase followed by an Insert as a caller. 

[szym, 2012/01/03 20:48:52]

There used to be Update/Move which essentially Erased then Inserted (with
slightly less work). Will update comment.

+// All operations are O(1) time (assuming constant NUM_PRIORITIES).

[cbentzel, 2012/01/03 19:39:09]

You should document why and where this is needed instead of the STL's
priority_queue.

+template<typename T>
+class PriorityQueue {

[cbentzel, 2012/01/03 19:39:09]

This should probably derive from NonThreadSafe or have some other assertions to
validate that it's always being accessed from the same thread. 

+ public:
+  typedef std::list<T> List;
+  // Note that we need iterator not const_iterator to pass to List::erase.
+  // When C++0x comes, this could be changed to const_iterator and const could
+  // be added to First, Last, and OldestLowest.
+  typedef typename std::list<T>::iterator ListIterator;

[cbentzel, 2012/01/03 19:39:09]

ListIterator could probably be typedef'd within Pointer instead of
PriorityQueue.

+
+  // A pointer to a value stored in the queue. The pointer becomes invalid
+  // when the queue is destroyed or 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_; }
+
+    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) {

[cbentzel, 2012/01/03 19:39:09]

Should this be a member on Pointer? 

Also, should this take a non-const Pointer since it will ultimately invalidate
the pointer?

[cbentzel, 2012/01/03 19:39:09]

It feels like this class could benefit with some debug invariant checks - like
making sure that size_ > 0 before doing this. 

[szym, 2012/01/03 20:48:52]

Since First returns a temporary, to allow queue.Erase(queue.First()) we need
either a const reference, or a value.

If we moved to LinkedList then there might be no need for a temporary in First,
although that would add some redundant storage to Job (priority, *queue). The
benefit would be that all "pointers" to the same element would be invalidated at
once.

+    --size_;
+    lists_[pointer.priority_].erase(pointer.iterator_);
+  }
+
+  // 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) {

[cbentzel, 2012/01/03 19:39:09]

Why not do a i = NUM_PRIORITIES; i > 0; --i?

Need to be more careful with unsigned, but this should be ok and more obvious.

+      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_
+