Adds PriorityQueue and PrioritizedDispatcher.

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 "base/threading/non_thread_safe.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, this implementation allows erasing elements
+// from the queue, and all operations are O(p) time for p priority 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 : public base::NonThreadSafe {
+ public:
+  typedef uint32 Priority;
+
+  // A pointer to a value stored in the queue. The pointer becomes invalid
+  // when the queue is destroyed or the value is erased.

[mmenke, 2012/01/06 17:54:37]

nit:  Or the queue is cleared.

+  class Pointer {
+   public:
+    // Constructs a null pointer.
+    Pointer() : priority_(kNullPriority) {}
+
+    bool is_null() const { return priority_ == kNullPriority; }
+
+    Priority priority() const { return priority_; }
+
+#if !defined(NDEBUG)
+    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.
+    typedef typename PriorityQueue::List::iterator ListIterator;
+
+    static const Priority kNullPriority = static_cast<Priority>(-1);
+
+    Pointer(Priority priority, const ListIterator& iterator)
+        : priority_(priority), iterator_(iterator) {
+#if !defined(NDEBUG)
+      id_ = iterator_->first;
+#endif
+    }
+
+    Priority priority_;
+    ListIterator iterator_;
+
+#if !defined(NDEBUG)
+    // Used by the queue to check if a Pointer is valid.
+    size_t id_;
+#endif
+  };
+
+  // Creates a new queue for |num_priorities|.
+  explicit PriorityQueue(Priority num_priorities)
+      : lists_(num_priorities), size_(0) {
+#if !defined(NDEBUG)
+    next_id_ = 0;
+#endif
+  }
+
+  // Adds |value| with |priority| to the queue. Returns a pointer to the
+  // created element.
+  Pointer Insert(const T& value, Priority priority) {
+    DCHECK(CalledOnValidThread());
+    DCHECK_LT(priority, lists_.size());
+    ++size_;
+    List& list = lists_[priority];
+#if !defined(NDEBUG)
+    size_t id = next_id_;
+    valid_ids_.insert(id);
+    ++next_id_;
+    return Pointer(priority, list.insert(list.end(),
+                                         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(CalledOnValidThread());
+    DCHECK_LT(pointer.priority_, lists_.size());
+    DCHECK_GT(size_, 0u);
+
+#if !defined(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() {
+    DCHECK(CalledOnValidThread());
+    for (size_t i = 0; i < lists_.size(); ++i) {
+      if (!lists_[i].empty())
+        return Pointer(i, lists_[i].begin());
+    }
+    return Pointer();
+  }
+
+  // Returns a pointer to the last value of minimum priority or a null-pointer
+  // if empty.
+  Pointer LastMin() {
+    DCHECK(CalledOnValidThread());
+    for (size_t i = 0; i < lists_.size(); ++i) {
+      if (!lists_[i].empty())
+        return Pointer(i, --lists_[i].end());
+    }
+    return Pointer();
+  }
+
+  // Returns a pointer to the first value of maximum priority or a null-pointer
+  // if empty.
+  Pointer FirstMax() {
+    DCHECK(CalledOnValidThread());
+    for (size_t i = lists_.size(); i > 0; --i) {
+      size_t index = i - 1;
+      if (!lists_[index].empty())
+        return Pointer(index, lists_[index].begin());
+    }
+    return Pointer();
+  }
+
+  // Returns a pointer to the last value of maximum priority or a null-pointer
+  // if empty.
+  Pointer LastMax() {
+    DCHECK(CalledOnValidThread());
+    for (size_t i = lists_.size(); i > 0; --i) {
+      size_t index = i - 1;
+      if (!lists_[index].empty())
+        return Pointer(index, --lists_[index].end());
+    }
+    return Pointer();
+  }
+
+  // Empties the queue. All pointers become invalid.
+  void Clear() {
+    DCHECK(CalledOnValidThread());
+    for (size_t i = 0; i < lists_.size(); ++i) {
+      lists_[i].clear();
+    }
+#if !defined(NDEBUG)
+    valid_ids_.clear();
+#endif
+    size_ = 0u;
+  }
+
+  // Returns number of queued values.
+  size_t size() const {
+    DCHECK(CalledOnValidThread());
+    return size_;
+  }
+
+ private:
+#if !defined(NDEBUG)
+  typedef std::list<std::pair<size_t, T> > List;
+#else
+  typedef std::list<T> List;
+#endif
+  typedef std::vector<List> ListVector;
+
+#if !defined(NDEBUG)
+  size_t next_id_;
+  base::hash_set<size_t> valid_ids_;
+#endif
+
+  ListVector lists_;
+  size_t size_;
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_PRIORITY_QUEUE_H_
+