Add a templated priority queue class.

Add a templated priority queue class.

Committed: https://skia.googlesource.com/skia/+/3555bd88a6513d219a084eabd41e9dff9e513605

[bsalomon, 2015-02-11 15:44:16]

bsalomon@google.com changed reviewers:
+ egdaniel@google.com, jvanverth@google.com

[bsalomon, 2015-02-11 15:44:17]

The idea is to use this to manage the LRU in the cache where only resources that
are purgeable are in the queue.

[egdaniel, 2015-02-11 18:58:28]

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h
File src/core/SkTDPQueue.h (right):

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h#ne...
src/core/SkTDPQueue.h:35: const T& peek() const { return fArray[0]; }
we assert the count > 0 on pop, but not here. Obviously there is an assert in
SkTDArray that will fire if you try to access array[0] when count is 0. Is there
a good reason to add an assert in one and not the other?

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h#ne...
src/core/SkTDPQueue.h:70: SkASSERT(index >= 0 && index < fArray.count());
should we assert the entry == fArray[index]? The owner of INDEX isn't forced to
return the index we set for it.

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h#ne...
src/core/SkTDPQueue.h:72: SkDEBUGCODE(if (INDEX) { *INDEX(fArray[index]) = -1;
})
We don't need to checkout INDEX here, since we assert above

https://codereview.chromium.org/914003004/diff/80001/tests/TDPQueueTest.cpp
File tests/TDPQueueTest.cpp (right):

https://codereview.chromium.org/914003004/diff/80001/tests/TDPQueueTest.cpp#n...
tests/TDPQueueTest.cpp:116: switch (action) {
Do you think it is fine to only do asserts when doing a pop? Given this is
random it is probably fine since we'll validate the state every ~3 actions. But
then again this doesn't pinpoint which action caused the problem. Just that
between two pop's there was some problem.

[bsalomon, 2015-02-11 19:14:52]

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h
File src/core/SkTDPQueue.h (right):

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h#ne...
src/core/SkTDPQueue.h:35: const T& peek() const { return fArray[0]; }
On 2015/02/11 18:58:27, egdaniel wrote:
> we assert the count > 0 on pop, but not here. Obviously there is an assert in
> SkTDArray that will fire if you try to access array[0] when count is 0. Is
there
> a good reason to add an assert in one and not the other?

nope, fair point. Will remove the redundant assert in pop.

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h#ne...
src/core/SkTDPQueue.h:70: SkASSERT(index >= 0 && index < fArray.count());
On 2015/02/11 18:58:27, egdaniel wrote:
> should we assert the entry == fArray[index]? The owner of INDEX isn't forced
to
> return the index we set for it.

validate() does that.

https://codereview.chromium.org/914003004/diff/80001/src/core/SkTDPQueue.h#ne...
src/core/SkTDPQueue.h:72: SkDEBUGCODE(if (INDEX) { *INDEX(fArray[index]) = -1;
})
On 2015/02/11 18:58:27, egdaniel wrote:
> We don't need to checkout INDEX here, since we assert above

Done.

https://codereview.chromium.org/914003004/diff/80001/tests/TDPQueueTest.cpp
File tests/TDPQueueTest.cpp (right):

https://codereview.chromium.org/914003004/diff/80001/tests/TDPQueueTest.cpp#n...
tests/TDPQueueTest.cpp:116: switch (action) {
On 2015/02/11 18:58:28, egdaniel wrote:
> Do you think it is fine to only do asserts when doing a pop? Given this is
> random it is probably fine since we'll validate the state every ~3 actions.
But
> then again this doesn't pinpoint which action caused the problem. Just that
> between two pop's there was some problem.

Done.

[egdaniel, 2015-02-11 19:49:09]

lgtm

[bsalomon, 2015-02-11 19:50:44]

The CQ bit was checked by bsalomon@google.com

[commit-bot: I haz the power, 2015-02-11 19:51:47]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/914003004/130001

[commit-bot: I haz the power, 2015-02-11 19:52:56]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-02-11 19:52:57]

Try jobs failed on following builders:
  Test-Ubuntu13.10-GCE-NoGPU-x86_64-Debug-Trybot on client.skia (JOB_FAILED,
http://build.chromium.org/p/client.skia/builders/Test-Ubuntu13.10-GCE-NoGPU-x...)
  Test-Ubuntu13.10-GCE-NoGPU-x86_64-Release-Shared-Trybot on client.skia
(JOB_FAILED,
http://build.chromium.org/p/client.skia/builders/Test-Ubuntu13.10-GCE-NoGPU-x...)

[bsalomon, 2015-02-13 18:48:56]

New patchsets have been uploaded after l-g-t-m from egdaniel@google.com

[bsalomon, 2015-02-13 18:49:02]

The CQ bit was checked by bsalomon@google.com

[commit-bot: I haz the power, 2015-02-13 18:49:35]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/914003004/150001

[commit-bot: I haz the power, 2015-02-13 18:51:26]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-02-13 18:51:27]

Try jobs failed on following builders:
  Test-Ubuntu13.10-GCE-NoGPU-x86_64-Release-Shared-Trybot on client.skia
(JOB_FAILED,
http://build.chromium.org/p/client.skia/builders/Test-Ubuntu13.10-GCE-NoGPU-x...)

[bsalomon, 2015-02-13 18:57:33]

The CQ bit was checked by bsalomon@google.com

[commit-bot: I haz the power, 2015-02-13 18:58:35]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/914003004/170001

[commit-bot: I haz the power, 2015-02-13 19:01:05]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-02-13 19:01:06]

Try jobs failed on following builders:
  Build-Ubuntu13.10-Clang-x86_64-Debug-Trybot on client.skia.compile
(JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu13.10-Cl...)

[bsalomon, 2015-02-13 19:02:12]

The CQ bit was checked by bsalomon@google.com

[commit-bot: I haz the power, 2015-02-13 19:02:35]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/914003004/190001

[commit-bot: I haz the power, 2015-02-13 19:08:27]

Committed patchset #11 (id:190001) as
https://skia.googlesource.com/skia/+/3555bd88a6513d219a084eabd41e9dff9e513605