// Copyright (c) 2012 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_
#include <list>
#include <vector>
#include "base/basictypes.h"
#include "base/logging.h"
#include "base/threading/non_thread_safe.h"
#include "net/base/net_export.h"
#if !defined(NDEBUG)
#include "base/containers/hash_tables.h"
#endif
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 {
private:
// This section is up-front for Pointer only.
#if !defined(NDEBUG)
typedef std::list<std::pair<unsigned, T> > List;
#else
typedef std::list<T> List;
#endif
public:
typedef uint32 Priority;
// A pointer to a value stored in the queue. The pointer becomes invalid
// when the queue is destroyed or cleared, or the value is erased.
class Pointer {
public:
// Constructs a null pointer.
Pointer() : priority_(kNullPriority) {
#if !defined(NDEBUG)
id_ = static_cast<unsigned>(-1);
#endif
// TODO(syzm)
// An uninitialized iterator behaves like an uninitialized pointer as per
// the STL docs. The fix below is ugly and should possibly be replaced
// with a better approach.
iterator_ = dummy_empty_list_.end();
}
Pointer(const Pointer& p)
: priority_(p.priority_),
iterator_(p.iterator_) {
#if !defined(NDEBUG)
id_ = p.id_;
#endif
}
Pointer& operator=(const Pointer& p) {
// Self-assignment is benign.
priority_ = p.priority_;
iterator_ = p.iterator_;
#if !defined(NDEBUG)
id_ = p.id_;
#endif
return *this;
}
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_);
}
void Reset() {
*this = Pointer();
}
private:
friend class PriorityQueue;
// Note that we need iterator and not const_iterator to pass to
// List::erase. When C++11 is turned on for Chromium, this could
// be changed to const_iterator and the const_casts in the rest of
// the file can be removed.
typedef typename PriorityQueue::List::iterator ListIterator;
static const Priority kNullPriority = static_cast<Priority>(-1);
// It is guaranteed that Pointer will treat |iterator| as a
// const_iterator.
Pointer(Priority priority, const ListIterator& iterator)
: priority_(priority), iterator_(iterator) {
#if !defined(NDEBUG)
id_ = iterator_->first;
#endif
}
Priority priority_;
ListIterator iterator_;
// The STL iterators when uninitialized are like uninitialized pointers
// which cause crashes when assigned to other iterators. We need to
// initialize a NULL iterator to the end of a valid list.
List dummy_empty_list_;
#if !defined(NDEBUG)
// Used by the queue to check if a Pointer is valid.
unsigned 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)
unsigned 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
}
// Adds |value| with |priority| to the queue. Returns a pointer to the
// created element.
Pointer InsertAtFront(const T& value, Priority priority) {
DCHECK(CalledOnValidThread());
DCHECK_LT(priority, lists_.size());
++size_;
List& list = lists_[priority];
#if !defined(NDEBUG)
unsigned id = next_id_;
valid_ids_.insert(id);
++next_id_;
return Pointer(priority, list.insert(list.begin(),
std::make_pair(id, value)));
#else
return Pointer(priority, list.insert(list.begin(), 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() const {
DCHECK(CalledOnValidThread());
for (size_t i = 0; i < lists_.size(); ++i) {
List* list = const_cast<List*>(&lists_[i]);
if (!list->empty())
return Pointer(i, list->begin());
}
return Pointer();
}
// Returns a pointer to the last value of minimum priority or a null-pointer
// if empty.
Pointer LastMin() const {
DCHECK(CalledOnValidThread());
for (size_t i = 0; i < lists_.size(); ++i) {
List* list = const_cast<List*>(&lists_[i]);
if (!list->empty())
return Pointer(i, --list->end());
}
return Pointer();
}
// Returns a pointer to the first value of maximum priority or a null-pointer
// if empty.
Pointer FirstMax() const {
DCHECK(CalledOnValidThread());
for (size_t i = lists_.size(); i > 0; --i) {
size_t index = i - 1;
List* list = const_cast<List*>(&lists_[index]);
if (!list->empty())
return Pointer(index, list->begin());
}
return Pointer();
}
// Returns a pointer to the last value of maximum priority or a null-pointer
// if empty.
Pointer LastMax() const {
DCHECK(CalledOnValidThread());
for (size_t i = lists_.size(); i > 0; --i) {
size_t index = i - 1;
List* list = const_cast<List*>(&lists_[index]);
if (!list->empty())
return Pointer(index, --list->end());
}
return Pointer();
}
// Given an ordering of the values in this queue by decreasing
// priority and then FIFO, returns a pointer to the value following
// the value of the given pointer (which must be non-NULL).
//
// (One could also implement GetNextTowardsFirstMin() [decreasing
// priority, then reverse FIFO] as well as
// GetNextTowards{First,Last}Max() [increasing priority, then
// {,reverse} FIFO].)
Pointer GetNextTowardsLastMin(const Pointer& pointer) const {
DCHECK(CalledOnValidThread());
DCHECK(!pointer.is_null());
DCHECK_LT(pointer.priority_, lists_.size());
typename Pointer::ListIterator it = pointer.iterator_;
Priority priority = pointer.priority_;
DCHECK(it != lists_[priority].end());
++it;
while (it == lists_[priority].end()) {
if (priority == 0u)
return Pointer();
--priority;
it = const_cast<List*>(&lists_[priority])->begin();
}
return Pointer(priority, it);
}
// 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 the number of priorities the queue supports.
size_t num_priorities() const {
DCHECK(CalledOnValidThread());
return lists_.size();
}
bool empty() const {
DCHECK(CalledOnValidThread());
return size_ == 0;
}
// Returns number of queued values.
size_t size() const {
DCHECK(CalledOnValidThread());
return size_;
}
private:
typedef std::vector<List> ListVector;
#if !defined(NDEBUG)
unsigned next_id_;
base::hash_set<unsigned> valid_ids_;
#endif
ListVector lists_;
size_t size_;
DISALLOW_COPY_AND_ASSIGN(PriorityQueue);
};
} // namespace net
#endif // NET_BASE_PRIORITY_QUEUE_H_