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 <vector>
+
+#include "base/basictypes.h"
+#ifndef NDEBUG
+#include "base/hash_tables.h"
+#endif
+#include "base/logging.h"
+#include "net/base/net_export.h"
+
+namespace net {
+
+// A simple priority queue. The order of values is by priority and then FIFO.
+// Unlike the std::priority_queue, all operations are O(p) time for p priority

[cbentzel, 2012/01/05 18:32:20]

This also allows erasing of elements in the queue, as well as getting the oldest
items.

+// levels. The queue is agnostic to priority ordering (whether 0 precedes 1).
+// If the highest priority is 0, FirstMin() returns the first in order.
+//
+// In debug-mode, the internal queues store (id, value) pairs where id is used
+// to validate Pointers.
+//
+template<typename T>
+class PriorityQueue {

[cbentzel, 2012/01/05 18:32:20]

I think this should derive from NonThreadSafe or have some other asserts to show
that it's always being accessed from the same thread.

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

[cbentzel, 2012/01/05 18:32:20]

Nit: remove "or moved". There is no direct support for moving an item in the
queue.

+  class Pointer {
+   public:
+    // Constructs a null pointer.
+    Pointer() : priority_(kNullPriority) {}
+
+    bool is_null() const { return priority_ == kNullPriority; }
+
+    size_t priority() const { return priority_; }

[cbentzel, 2012/01/05 18:32:20]

I'd argue for just using uint32 rather than a size_t, as it has nothing to do
with sizeof() or byte count, etc.

It would probably be reasonable to also add a 

typedef uint32 Level;

or something similar to prevent repetition of the size_t/uint32 throughout.

+
+#ifndef NDEBUG

[cbentzel, 2012/01/05 18:32:20]

Nit: #if !defined(NDEBUG)

is preferred over #ifndef

See http://dev.chromium.org/developers/coding-style

+    const T& value() const { return iterator_->second; }
+#else
+    const T& value() const { return *iterator_; }
+#endif
+
+    // Comparing to Pointer from a different PriorityQueue is undefined.
+    bool Equals(const Pointer& other) const {
+      return (priority_ == other.priority_) && (iterator_ == other.iterator_);
+    }
+
+   private:
+    friend class PriorityQueue;
+    // 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.
+#ifndef NDEBUG
+    typedef typename std::list<std::pair<size_t, T> >::iterator ListIterator;

[cbentzel, 2012/01/05 18:32:20]

Could be PriorityQueue::List::iterator to prevent needing to duplicate the
debug/non-debug version (I think).

+#else
+    typedef typename std::list<T>::iterator ListIterator;
+#endif
+
+    static const size_t kNullPriority = static_cast<size_t>(-1);
+
+    Pointer(size_t priority, const ListIterator& iterator)
+        : priority_(priority), iterator_(iterator) {
+#ifndef NDEBUG
+      id_ = iterator_->first;
+#endif
+    }
+
+    size_t priority_;
+    ListIterator iterator_;
+
+#ifndef NDEBUG
+    // Used by the queue to check if a Pointer is valid.
+    size_t id_;
+#endif
+  };
+
+  // Creates a new queue for |num_priorities|.
+  PriorityQueue(size_t num_priorities)

[cbentzel, 2012/01/05 18:32:20]

explicit constructor needed.

+      : lists_(num_priorities), size_(0) {
+#ifndef NDEBUG
+    next_id_ = 0;
+#endif
+  }
+
+  // Adds |value| with |priority| to the queue. Returns a pointer to the
+  // created element.
+  Pointer Insert(const T& value, size_t priority) {
+    DCHECK_LT(priority, lists_.size());
+    ++size_;
+    List& list = lists_[priority];
+#ifndef NDEBUG
+    size_t id = next_id_;
+    valid_ids_.insert(id);
+    ++next_id_;
+    return Pointer(priority, list.insert(list.end(),

[cbentzel, 2012/01/05 18:32:20]

Nit: list.push_back would be clearer than list.insert(list.end()

[szym, 2012/01/05 19:00:29]

list.push_back returns void.

+                                         std::make_pair(id, value)));
+#else
+    return Pointer(priority, list.insert(list.end(), value));
+#endif
+  }
+
+  // Removes the value pointed by |pointer| from the queue. All pointers to this
+  // value including |pointer| become invalid.
+  void Erase(const Pointer& pointer) {
+    DCHECK_LT(pointer.priority_, lists_.size());
+    DCHECK_GT(size_, 0u);
+
+#ifndef NDEBUG
+    DCHECK_EQ(1u, valid_ids_.erase(pointer.id_));
+    DCHECK_EQ(pointer.iterator_->first, pointer.id_);
+#endif
+
+    --size_;
+    lists_[pointer.priority_].erase(pointer.iterator_);
+  }
+
+  // Returns a pointer to the first value of minimum priority or a null-pointer
+  // if empty.
+  Pointer FirstMin() {
+    if (!size()) return Pointer();

[cbentzel, 2012/01/05 18:32:20]

It would be clearer to just remove this line and the NOTREACHED statement below
- I'm not too worried about perf here. Ditto for the rest of this file.

+    for (size_t i = 0; i < lists_.size(); ++i)

[cbentzel, 2012/01/05 18:32:20]

Please use braces in this for loop. 

+      if (!lists_[i].empty())
+        return Pointer(i, lists_[i].begin());
+    NOTREACHED();
+    return Pointer();
+  }
+
+  // Returns a pointer to the last value of minimum priority or a null-pointer
+  // if empty.
+  Pointer LastMin() {
+    if (!size()) return Pointer();
+    for (size_t i = 0; i < lists_.size(); ++i)
+      if (!lists_[i].empty())
+        return Pointer(i, --lists_[i].end());
+    NOTREACHED();
+    return Pointer();
+  }
+
+  // Returns a pointer to the first value of maximum priority or a null-pointer
+  // if empty.
+  Pointer FirstMax() {
+    if (!size()) return Pointer();
+    for (size_t i = lists_.size(); i > 0; --i)
+      if (!lists_[i - 1].empty())
+        return Pointer(i - 1, lists_[i - 1].begin());
+    NOTREACHED();
+    return Pointer();
+  }
+
+  // Returns a pointer to the last value of maximum priority or a null-pointer
+  // if empty.
+  Pointer LastMax() {
+    if (!size()) return Pointer();
+    for (size_t i = lists_.size(); i > 0; --i)

[cbentzel, 2012/01/05 18:32:20]

To be pedantic, this should be ListVector::size_type, but the assumption that
it's size_t is done throughout the code base.

+      if (!lists_[i - 1].empty())

[cbentzel, 2012/01/05 18:32:20]

Nit: probably clearer to have a local variable index = i - 1;

+        return Pointer(i - 1, --lists_[i - 1].end());
+    NOTREACHED();
+    return Pointer();
+  }
+
+  // Empties the queue. All pointers become invalid.
+  void Clear() {
+    for (size_t i = 0; i < lists_.size(); ++i)

[cbentzel, 2012/01/05 18:32:20]

BUG: valid_ids_ needs to be cleared here as well.

+      lists_[i].clear();
+    size_ = 0u;
+  }
+
+  // Returns number of queued values.
+  size_t size() const {
+    return size_;
+  }
+
+ private:
+#ifndef NDEBUG
+  typedef std::list<std::pair<size_t, T> > List;
+#else
+  typedef std::list<T> List;
+#endif
+  typedef std::vector<List> ListVector;
+
+#ifndef NDEBUG
+  size_t next_id_;
+  base::hash_set<size_t> valid_ids_;
+#endif
+
+  ListVector lists_;
+  size_t size_;

[cbentzel, 2012/01/05 18:32:20]

Nit: extra new line.

+

[cbentzel, 2012/01/05 18:32:20]

Should copy-and-assignment be disallowed? I don't think so, and it looks like it
will work even in the presence of valid_ids_. 

[szym, 2012/01/05 19:00:29]

It can be allowed. But for safety Pointers need to have a reference to the queue
(ifndef NDEBUG).

+};
+
+}  // namespace net
+
+#endif  // NET_BASE_PRIORITY_QUEUE_H_
+