From 3555bd88a6513d219a084eabd41e9dff9e513605 Mon Sep 17 00:00:00 2001 From: bsalomon Date: Fri, 13 Feb 2015 11:08:21 -0800 Subject: [PATCH] Add a templated priority queue class. Review URL: https://codereview.chromium.org/914003004 --- gyp/core.gypi | 1 + gyp/tests.gypi | 1 + src/core/SkTDPQueue.h | 191 +++++++++++++++++++++++++++++++++++++++++ tests/TDPQueueTest.cpp | 156 +++++++++++++++++++++++++++++++++ 4 files changed, 349 insertions(+) create mode 100644 src/core/SkTDPQueue.h create mode 100644 tests/TDPQueueTest.cpp diff --git a/gyp/core.gypi b/gyp/core.gypi index 0e2f24f398..608014828e 100644 --- a/gyp/core.gypi +++ b/gyp/core.gypi @@ -203,6 +203,7 @@ '<(skia_src_path)/core/SkTextBlob.cpp', '<(skia_src_path)/core/SkTextFormatParams.h', '<(skia_src_path)/core/SkTextMapStateProc.h', + '<(skia_src_path)/core/SkTDPQueue.h', '<(skia_src_path)/core/SkTHashCache.h', '<(skia_src_path)/core/SkTLList.h', '<(skia_src_path)/core/SkTLS.cpp', diff --git a/gyp/tests.gypi b/gyp/tests.gypi index 25e1b7ae8c..625fa866f0 100644 --- a/gyp/tests.gypi +++ b/gyp/tests.gypi @@ -202,6 +202,7 @@ '../tests/StrokerTest.cpp', '../tests/SurfaceTest.cpp', '../tests/TArrayTest.cpp', + '../tests/TDPQueueTest.cpp', '../tests/THashCache.cpp', '../tests/Time.cpp', '../tests/TLSTest.cpp', diff --git a/src/core/SkTDPQueue.h b/src/core/SkTDPQueue.h new file mode 100644 index 0000000000..9efde01b66 --- /dev/null +++ b/src/core/SkTDPQueue.h @@ -0,0 +1,191 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkTDPQueue_DEFINED +#define SkTDPQueue_DEFINED + +#include "SkTDArray.h" + +/** + * This class implements a priority queue. T is the type of the elements in the queue. LESS is a + * function that compares two Ts and returns true if the first is higher priority than the second. + * + * Optionally objects may know their index into the priority queue. The queue will update the index + * as the objects move through the queue. This is enabled by using a non-NULL function for INDEX. + * When an INDEX function is provided random deletes from the queue are allowed using remove(). + * Additionally, the * priority is allowed to change as long as priorityDidChange() is called + * afterwards. In debug builds the index will be set to -1 before an element is removed from the + * queue. + */ +template +class SkTDPQueue : public SkNoncopyable { +public: + SkTDPQueue() {} + + /** Number of items in the queue. */ + int count() const { return fArray.count(); } + + /** Gets the next item in the queue without popping it. */ + const T& peek() const { return fArray[0]; } + T& peek() { return fArray[0]; } + + /** Removes the next item. */ + void pop() { + this->validate(); + SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; }) + if (1 == fArray.count()) { + fArray.pop(); + return; + } + + fArray[0] = fArray[fArray.count() - 1]; + this->setIndex(0); + fArray.pop(); + this->percolateDownIfNecessary(0); + + this->validate(); + } + + /** Inserts a new item in the queue based on its priority. */ + void insert(T entry) { + this->validate(); + int index = fArray.count(); + *fArray.append() = entry; + this->setIndex(fArray.count() - 1); + this->percolateUpIfNecessary(index); + this->validate(); + } + + /** Random access removal. This requires that the INDEX function is non-NULL. */ + void remove(T entry) { + SkASSERT(NULL != INDEX); + int index = *INDEX(entry); + SkASSERT(index >= 0 && index < fArray.count()); + this->validate(); + SkDEBUGCODE(*INDEX(fArray[index]) = -1;) + if (index == fArray.count() - 1) { + fArray.pop(); + return; + } + fArray[index] = fArray[fArray.count() - 1]; + fArray.pop(); + this->setIndex(index); + this->percolateUpOrDown(index); + this->validate(); + } + + /** Notification that the priority of an entry has changed. This must be called after an + item's priority is changed to maintain correct ordering. Changing the priority is only + allowed if an INDEX function is provided. */ + void priorityDidChange(T entry) { + SkASSERT(NULL != INDEX); + int index = *INDEX(entry); + SkASSERT(index >= 0 && index < fArray.count()); + this->validate(index); + this->percolateUpOrDown(index); + this->validate(); + } + +private: + static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; } + static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; } + + void percolateUpOrDown(int index) { + SkASSERT(index >= 0); + if (!percolateUpIfNecessary(index)) { + this->validate(index); + this->percolateDownIfNecessary(index); + } + } + + bool percolateUpIfNecessary(int index) { + SkASSERT(index >= 0); + bool percolated = false; + do { + if (0 == index) { + this->setIndex(index); + return percolated; + } + int p = ParentOf(index); + if (LESS(fArray[index], fArray[p])) { + SkTSwap(fArray[index], fArray[p]); + this->setIndex(index); + index = p; + percolated = true; + } else { + this->setIndex(index); + return percolated; + } + this->validate(index); + } while (true); + } + + void percolateDownIfNecessary(int index) { + SkASSERT(index >= 0); + do { + int child = LeftOf(index); + + if (child >= fArray.count()) { + // We're a leaf. + this->setIndex(index); + return; + } + + if (child + 1 >= fArray.count()) { + // We only have a left child. + if (LESS(fArray[child], fArray[index])) { + SkTSwap(fArray[child], fArray[index]); + this->setIndex(child); + this->setIndex(index); + return; + } + } else if (LESS(fArray[child + 1], fArray[child])) { + // The right child is the one we should swap with, if we swap. + child++; + } + + // Check if we need to swap. + if (LESS(fArray[child], fArray[index])) { + SkTSwap(fArray[child], fArray[index]); + this->setIndex(index); + index = child; + } else { + // We're less than both our children. + this->setIndex(index); + return; + } + this->validate(index); + } while (true); + } + + void setIndex(int index) { + SkASSERT(index < fArray.count()); + if (SkToBool(INDEX)) { + *INDEX(fArray[index]) = index; + } + } + + void validate(int excludedIndex = -1) const { +#ifdef SK_DEBUG + for (int i = 1; i < fArray.count(); ++i) { + int p = ParentOf(i); + if (excludedIndex != p && excludedIndex != i) { + SkASSERT(!(LESS(fArray[i], fArray[p]))); + SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i); + } + } +#endif + } + + SkTDArray fArray; + + typedef SkNoncopyable INHERITED; +}; + +#endif diff --git a/tests/TDPQueueTest.cpp b/tests/TDPQueueTest.cpp new file mode 100644 index 0000000000..70367a7b82 --- /dev/null +++ b/tests/TDPQueueTest.cpp @@ -0,0 +1,156 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "SkTDPQueue.h" +#include "SkRandom.h" +#include "Test.h" + +namespace { bool intless(const int& a, const int& b) { return a < b; } } + +static void simple_test(skiatest::Reporter* reporter) { + SkTDPQueue heap; + REPORTER_ASSERT(reporter, 0 == heap.count()); + + heap.insert(0); + REPORTER_ASSERT(reporter, 1 == heap.count()); + REPORTER_ASSERT(reporter, 0 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 0 == heap.count()); + + heap.insert(0); + heap.insert(1); + REPORTER_ASSERT(reporter, 2 == heap.count()); + REPORTER_ASSERT(reporter, 0 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 1 == heap.count()); + REPORTER_ASSERT(reporter, 1 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 0 == heap.count()); + + heap.insert(2); + heap.insert(1); + heap.insert(0); + REPORTER_ASSERT(reporter, 3 == heap.count()); + REPORTER_ASSERT(reporter, 0 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 2 == heap.count()); + REPORTER_ASSERT(reporter, 1 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 1 == heap.count()); + REPORTER_ASSERT(reporter, 2 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 0 == heap.count()); + + heap.insert(2); + heap.insert(3); + heap.insert(0); + heap.insert(1); + REPORTER_ASSERT(reporter, 4 == heap.count()); + REPORTER_ASSERT(reporter, 0 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 3 == heap.count()); + REPORTER_ASSERT(reporter, 1 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 2 == heap.count()); + REPORTER_ASSERT(reporter, 2 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 1 == heap.count()); + REPORTER_ASSERT(reporter, 3 == heap.peek()); + heap.pop(); + REPORTER_ASSERT(reporter, 0 == heap.count()); +} + +struct Dummy { + int fValue; + int fPriority; + mutable int fIndex; + + static bool LessP(Dummy* const& a, Dummy* const& b) { return a->fPriority < b->fPriority; } + static int* PQIndex(Dummy* const& dummy) { return &dummy->fIndex; } + + bool operator== (const Dummy& that) const { + return fValue == that.fValue && fPriority == that.fPriority; + } + bool operator!= (const Dummy& that) const { return !(*this == that); } +}; + +void random_test(skiatest::Reporter* reporter) { + SkRandom random; + static const Dummy kSentinel = {-1, -1, -1}; + + for (int i = 0; i < 100; ++i) { + // Create a random set of Dummy objects. + int count = random.nextULessThan(100); + SkTDArray array; + array.setReserve(count); + for (int j = 0; j < count; ++j) { + Dummy* dummy = array.append(); + dummy->fPriority = random.nextS(); + dummy->fValue = random.nextS(); + dummy->fIndex = -1; + if (*dummy == kSentinel) { + array.pop(); + --j; + } + } + + // Stick the dummy objects in the pqueue. + SkTDPQueue pq; + for (int j = 0; j < count; ++j) { + pq.insert(&array[j]); + } + REPORTER_ASSERT(reporter, pq.count() == array.count()); + for (int j = 0; j < count; ++j) { + // every item should have an entry in the queue. + REPORTER_ASSERT(reporter, -1 != array[j].fIndex); + } + + // Begin the test. + while (pq.count()) { + // Make sure the top of the queue is really the highest priority. + Dummy* top = pq.peek(); + for (int k = 0; k < count; ++k) { + REPORTER_ASSERT(reporter, kSentinel == array[k] || + array[k].fPriority >= top->fPriority); + } + // Do one of three random actions: + unsigned action = random.nextULessThan(3); + switch (action) { + case 0: { // pop the top, + Dummy* top = pq.peek(); + REPORTER_ASSERT(reporter, array.begin() <= top && top < array.end()); + pq.pop(); + *top = kSentinel; + break; + } + case 1: { // remove a random element, + int item; + do { + item = random.nextULessThan(count); + } while (array[item] == kSentinel); + pq.remove(&array[item]); + array[item] = kSentinel; + break; + } + case 2: { // or change an element's priority. + int item; + do { + item = random.nextULessThan(count); + } while (array[item] == kSentinel); + array[item].fPriority = random.nextS(); + pq.priorityDidChange(&array[item]); + break; + } + } + } + } +} + +DEF_TEST(TDPQueueTest, reporter) { + simple_test(reporter); + random_test(reporter); +} -- 2.34.1