Adds PriorityQueue and PrioritizedDispatcher.

Adds PriorityQueue and PrioritizedDispatcher.
This will be used in HostResolverImpl to dispatch Jobs.

BUG=109426
TEST=./net_unittests --gtest_filter=PriorityQueue*:PrioritizedDispatcher*

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=116736

[szym, 2012-01-05 21:29:38]

Split this off from http://codereview.chromium.org/8965025/

I'll see if moving the Add/Cancel/OnJobFinished interface into Job works out.

Haven't decided if to allow copy and assign for PriorityQueue. If we do, we
should at least have a DCHECK that we're not using Pointers from another queue.

[cbentzel, 2012-01-06 16:03:05]

LGTM

Please enter a bug for this, if only for tracking in the future. 

Also, make sure to run try jobs on the rel bots in addition to debug due to the
differences in PriorityQueue between the builds.

http://codereview.chromium.org/9113022/diff/8/net/base/prioritized_dispatcher.h
File net/base/prioritized_dispatcher.h (right):

http://codereview.chromium.org/9113022/diff/8/net/base/prioritized_dispatcher...
net/base/prioritized_dispatcher.h:21: // All operations are O(1) time. The class
is fully reentrant: it is safe to
Aren't some O(p) where p is the number of levels.

http://codereview.chromium.org/9113022/diff/8/net/base/prioritized_dispatcher...
net/base/prioritized_dispatcher.h:23: // However, this class is NOT thread-safe.
Why not derive from NonThreadSafe here like the PriorityQueue?

http://codereview.chromium.org/9113022/diff/8/net/base/priority_queue.h
File net/base/priority_queue.h (right):

http://codereview.chromium.org/9113022/diff/8/net/base/priority_queue.h#newco...
net/base/priority_queue.h:35: // A pointer to a value stored in the queue. The
pointer becomes invalid
Nit: add a newline before this comment.

http://codereview.chromium.org/9113022/diff/8/net/base/priority_queue.h#newco...
net/base/priority_queue.h:59: // Note that we need iterator not const_iterator
to pass to List::erase.
Nit: add a newline before this comment.

http://codereview.chromium.org/9113022/diff/8/net/base/priority_queue.h#newco...
net/base/priority_queue.h:176: valid_ids_.clear();
valid_ids_ needs to be wrapped in NDEBUG conditional.

[szym, 2012-01-06 17:52:30]

http://codereview.chromium.org/9113022/diff/8/net/base/prioritized_dispatcher.h
File net/base/prioritized_dispatcher.h (right):

http://codereview.chromium.org/9113022/diff/8/net/base/prioritized_dispatcher...
net/base/prioritized_dispatcher.h:23: // However, this class is NOT thread-safe.
On 2012/01/06 16:03:05, cbentzel wrote:
> Why not derive from NonThreadSafe here like the PriorityQueue? 

The underlying PriorityQueue will enforce this. Added comment on that.

[mmenke, 2012-01-06 17:54:36]

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
File net/base/prioritized_dispatcher.cc (right):

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
net/base/prioritized_dispatcher.cc:1: // Copyright (c) 2011 The Chromium
Authors. All rights reserved.
nit:  Update year

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
File net/base/prioritized_dispatcher.h (right):

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
net/base/prioritized_dispatcher.h:61: // canceled, updated, or started.
nit:  I think "updated" is a little vague.  I'd say "canceled, evicted, started,
or has its priority explicitly changed".

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
net/base/prioritized_dispatcher.h:98: bool DispatchJob(const Handle& handle,
Priority priority);
nit:  Since this doesn't always dispatch a job, maybe rename to
MaybeDispatchJob?

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
net/base/prioritized_dispatcher.h:109: size_t max_queued_jobs_;
This doesn't seem to be initialized anywhere, isn't enforced, and only appears
in a DCHECK.

http://codereview.chromium.org/9113022/diff/11002/net/base/priority_queue.h
File net/base/priority_queue.h (right):

http://codereview.chromium.org/9113022/diff/11002/net/base/priority_queue.h#n...
net/base/priority_queue.h:37: // when the queue is destroyed or the value is
erased.
nit:  Or the queue is cleared.

[szym, 2012-01-06 17:56:42]

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
File net/base/prioritized_dispatcher.h (right):

http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
net/base/prioritized_dispatcher.h:109: size_t max_queued_jobs_;
On 2012/01/06 17:54:37, Matt Menke wrote:
> This doesn't seem to be initialized anywhere, isn't enforced, and only appears
> in a DCHECK.

Thanks for catching that, this is a left-over.

[mmenke, 2012-01-06 17:58:13]

No problem.  With that fixed, LGTM.

On 2012/01/06 17:56:42, szym wrote:
>
http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
> File net/base/prioritized_dispatcher.h (right):
> 
>
http://codereview.chromium.org/9113022/diff/11002/net/base/prioritized_dispat...
> net/base/prioritized_dispatcher.h:109: size_t max_queued_jobs_;
> On 2012/01/06 17:54:37, Matt Menke wrote:
> > This doesn't seem to be initialized anywhere, isn't enforced, and only
appears
> > in a DCHECK.
> 
> Thanks for catching that, this is a left-over.

[commit-bot: I haz the power, 2012-01-06 19:04:49]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/szym@chromium.org/9113022/20001

[commit-bot: I haz the power, 2012-01-06 19:45:23]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/szym@chromium.org/9113022/20001

[commit-bot: I haz the power, 2012-01-06 21:03:58]

Change committed as 116736