13555bd88a6513d219a084eabd41e9dff9e513605bsalomon/* 23555bd88a6513d219a084eabd41e9dff9e513605bsalomon * Copyright 2015 Google Inc. 33555bd88a6513d219a084eabd41e9dff9e513605bsalomon * 43555bd88a6513d219a084eabd41e9dff9e513605bsalomon * Use of this source code is governed by a BSD-style license that can be 53555bd88a6513d219a084eabd41e9dff9e513605bsalomon * found in the LICENSE file. 63555bd88a6513d219a084eabd41e9dff9e513605bsalomon */ 73555bd88a6513d219a084eabd41e9dff9e513605bsalomon 83555bd88a6513d219a084eabd41e9dff9e513605bsalomon#include "SkTDPQueue.h" 93555bd88a6513d219a084eabd41e9dff9e513605bsalomon#include "SkRandom.h" 103555bd88a6513d219a084eabd41e9dff9e513605bsalomon#include "Test.h" 113555bd88a6513d219a084eabd41e9dff9e513605bsalomon 123555bd88a6513d219a084eabd41e9dff9e513605bsalomonnamespace { bool intless(const int& a, const int& b) { return a < b; } } 133555bd88a6513d219a084eabd41e9dff9e513605bsalomon 143555bd88a6513d219a084eabd41e9dff9e513605bsalomonstatic void simple_test(skiatest::Reporter* reporter) { 153555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTDPQueue<int, intless> heap; 163555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.count()); 173555bd88a6513d219a084eabd41e9dff9e513605bsalomon 183555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(0); 193555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.count()); 203555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.peek()); 213555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 223555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.count()); 233555bd88a6513d219a084eabd41e9dff9e513605bsalomon 243555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(0); 253555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(1); 263555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 2 == heap.count()); 273555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.peek()); 283555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 293555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.count()); 303555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.peek()); 313555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 323555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.count()); 333555bd88a6513d219a084eabd41e9dff9e513605bsalomon 343555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(2); 353555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(1); 363555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(0); 373555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 3 == heap.count()); 383555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.peek()); 393555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 403555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 2 == heap.count()); 413555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.peek()); 423555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 433555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.count()); 443555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 2 == heap.peek()); 453555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 463555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.count()); 473555bd88a6513d219a084eabd41e9dff9e513605bsalomon 483555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(2); 493555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(3); 503555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(0); 513555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.insert(1); 523555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 4 == heap.count()); 533555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.peek()); 543555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 553555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 3 == heap.count()); 563555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.peek()); 573555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 583555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 2 == heap.count()); 593555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 2 == heap.peek()); 603555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 613555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 1 == heap.count()); 623555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 3 == heap.peek()); 633555bd88a6513d219a084eabd41e9dff9e513605bsalomon heap.pop(); 643555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, 0 == heap.count()); 653555bd88a6513d219a084eabd41e9dff9e513605bsalomon} 663555bd88a6513d219a084eabd41e9dff9e513605bsalomon 673555bd88a6513d219a084eabd41e9dff9e513605bsalomonstruct Dummy { 683555bd88a6513d219a084eabd41e9dff9e513605bsalomon int fValue; 693555bd88a6513d219a084eabd41e9dff9e513605bsalomon int fPriority; 703555bd88a6513d219a084eabd41e9dff9e513605bsalomon mutable int fIndex; 713555bd88a6513d219a084eabd41e9dff9e513605bsalomon 723555bd88a6513d219a084eabd41e9dff9e513605bsalomon static bool LessP(Dummy* const& a, Dummy* const& b) { return a->fPriority < b->fPriority; } 733555bd88a6513d219a084eabd41e9dff9e513605bsalomon static int* PQIndex(Dummy* const& dummy) { return &dummy->fIndex; } 743555bd88a6513d219a084eabd41e9dff9e513605bsalomon 753555bd88a6513d219a084eabd41e9dff9e513605bsalomon bool operator== (const Dummy& that) const { 763555bd88a6513d219a084eabd41e9dff9e513605bsalomon return fValue == that.fValue && fPriority == that.fPriority; 773555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 783555bd88a6513d219a084eabd41e9dff9e513605bsalomon bool operator!= (const Dummy& that) const { return !(*this == that); } 793555bd88a6513d219a084eabd41e9dff9e513605bsalomon}; 803555bd88a6513d219a084eabd41e9dff9e513605bsalomon 813555bd88a6513d219a084eabd41e9dff9e513605bsalomonvoid random_test(skiatest::Reporter* reporter) { 823555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkRandom random; 833555bd88a6513d219a084eabd41e9dff9e513605bsalomon static const Dummy kSentinel = {-1, -1, -1}; 843555bd88a6513d219a084eabd41e9dff9e513605bsalomon 853555bd88a6513d219a084eabd41e9dff9e513605bsalomon for (int i = 0; i < 100; ++i) { 863555bd88a6513d219a084eabd41e9dff9e513605bsalomon // Create a random set of Dummy objects. 873555bd88a6513d219a084eabd41e9dff9e513605bsalomon int count = random.nextULessThan(100); 883555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTDArray<Dummy> array; 893555bd88a6513d219a084eabd41e9dff9e513605bsalomon array.setReserve(count); 903555bd88a6513d219a084eabd41e9dff9e513605bsalomon for (int j = 0; j < count; ++j) { 913555bd88a6513d219a084eabd41e9dff9e513605bsalomon Dummy* dummy = array.append(); 923555bd88a6513d219a084eabd41e9dff9e513605bsalomon dummy->fPriority = random.nextS(); 933555bd88a6513d219a084eabd41e9dff9e513605bsalomon dummy->fValue = random.nextS(); 943555bd88a6513d219a084eabd41e9dff9e513605bsalomon dummy->fIndex = -1; 953555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (*dummy == kSentinel) { 963555bd88a6513d219a084eabd41e9dff9e513605bsalomon array.pop(); 973555bd88a6513d219a084eabd41e9dff9e513605bsalomon --j; 983555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 993555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1003555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1013555bd88a6513d219a084eabd41e9dff9e513605bsalomon // Stick the dummy objects in the pqueue. 1023555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTDPQueue<Dummy*, Dummy::LessP, Dummy::PQIndex> pq; 1033555bd88a6513d219a084eabd41e9dff9e513605bsalomon for (int j = 0; j < count; ++j) { 1043555bd88a6513d219a084eabd41e9dff9e513605bsalomon pq.insert(&array[j]); 1053555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1063555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, pq.count() == array.count()); 1073555bd88a6513d219a084eabd41e9dff9e513605bsalomon for (int j = 0; j < count; ++j) { 1083555bd88a6513d219a084eabd41e9dff9e513605bsalomon // every item should have an entry in the queue. 1093555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, -1 != array[j].fIndex); 1103555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1113555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1123555bd88a6513d219a084eabd41e9dff9e513605bsalomon // Begin the test. 1133555bd88a6513d219a084eabd41e9dff9e513605bsalomon while (pq.count()) { 1143555bd88a6513d219a084eabd41e9dff9e513605bsalomon // Make sure the top of the queue is really the highest priority. 1153555bd88a6513d219a084eabd41e9dff9e513605bsalomon Dummy* top = pq.peek(); 1163555bd88a6513d219a084eabd41e9dff9e513605bsalomon for (int k = 0; k < count; ++k) { 1173555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, kSentinel == array[k] || 1183555bd88a6513d219a084eabd41e9dff9e513605bsalomon array[k].fPriority >= top->fPriority); 1193555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1203555bd88a6513d219a084eabd41e9dff9e513605bsalomon // Do one of three random actions: 1213555bd88a6513d219a084eabd41e9dff9e513605bsalomon unsigned action = random.nextULessThan(3); 1223555bd88a6513d219a084eabd41e9dff9e513605bsalomon switch (action) { 1233555bd88a6513d219a084eabd41e9dff9e513605bsalomon case 0: { // pop the top, 1243555bd88a6513d219a084eabd41e9dff9e513605bsalomon Dummy* top = pq.peek(); 1253555bd88a6513d219a084eabd41e9dff9e513605bsalomon REPORTER_ASSERT(reporter, array.begin() <= top && top < array.end()); 1263555bd88a6513d219a084eabd41e9dff9e513605bsalomon pq.pop(); 1273555bd88a6513d219a084eabd41e9dff9e513605bsalomon *top = kSentinel; 1283555bd88a6513d219a084eabd41e9dff9e513605bsalomon break; 1293555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1303555bd88a6513d219a084eabd41e9dff9e513605bsalomon case 1: { // remove a random element, 1313555bd88a6513d219a084eabd41e9dff9e513605bsalomon int item; 1323555bd88a6513d219a084eabd41e9dff9e513605bsalomon do { 1333555bd88a6513d219a084eabd41e9dff9e513605bsalomon item = random.nextULessThan(count); 1343555bd88a6513d219a084eabd41e9dff9e513605bsalomon } while (array[item] == kSentinel); 1353555bd88a6513d219a084eabd41e9dff9e513605bsalomon pq.remove(&array[item]); 1363555bd88a6513d219a084eabd41e9dff9e513605bsalomon array[item] = kSentinel; 1373555bd88a6513d219a084eabd41e9dff9e513605bsalomon break; 1383555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1393555bd88a6513d219a084eabd41e9dff9e513605bsalomon case 2: { // or change an element's priority. 1403555bd88a6513d219a084eabd41e9dff9e513605bsalomon int item; 1413555bd88a6513d219a084eabd41e9dff9e513605bsalomon do { 1423555bd88a6513d219a084eabd41e9dff9e513605bsalomon item = random.nextULessThan(count); 1433555bd88a6513d219a084eabd41e9dff9e513605bsalomon } while (array[item] == kSentinel); 1443555bd88a6513d219a084eabd41e9dff9e513605bsalomon array[item].fPriority = random.nextS(); 1453555bd88a6513d219a084eabd41e9dff9e513605bsalomon pq.priorityDidChange(&array[item]); 1463555bd88a6513d219a084eabd41e9dff9e513605bsalomon break; 1473555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1483555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1493555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1503555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1513555bd88a6513d219a084eabd41e9dff9e513605bsalomon} 1523555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1535480a18d8799511034d0da219c72932cd8f25274Derek Sollenbergervoid sort_test(skiatest::Reporter* reporter) { 1545480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger SkRandom random; 1555480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1565480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger SkTDPQueue<Dummy *, Dummy::LessP, Dummy::PQIndex> pqTest; 1575480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger SkTDPQueue<Dummy *, Dummy::LessP, Dummy::PQIndex> pqControl; 1585480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1595480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger // Create a random set of Dummy objects and populate the test queue. 1605480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger int count = random.nextULessThan(100); 1615480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger SkTDArray<Dummy> testArray; 1625480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger testArray.setReserve(count); 1635480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger for (int i = 0; i < count; i++) { 1645480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger Dummy *dummy = testArray.append(); 1655480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger dummy->fPriority = random.nextS(); 1665480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger dummy->fValue = random.nextS(); 1675480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger dummy->fIndex = -1; 1685480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger pqTest.insert(&testArray[i]); 1695480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1705480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1715480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger // Stick equivalent dummy objects into the control queue. 1725480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger SkTDArray<Dummy> controlArray; 1735480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger controlArray.setReserve(count); 1745480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger for (int i = 0; i < count; i++) { 1755480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger Dummy *dummy = controlArray.append(); 1765480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger dummy->fPriority = testArray[i].fPriority; 1775480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger dummy->fValue = testArray[i].fValue; 1785480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger dummy->fIndex = -1; 1795480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger pqControl.insert(&controlArray[i]); 1805480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1815480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1825480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger // Sort the queue 1835480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger pqTest.sort(); 1845480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1855480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger // Compare elements in the queue to ensure they are in sorted order 1865480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger int prevPriority = pqTest.peek()->fPriority; 1875480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger for (int i = 0; i < count; i++) { 1885480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger REPORTER_ASSERT(reporter, i <= pqTest.at(i)->fIndex); 1895480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger REPORTER_ASSERT(reporter, prevPriority <= pqTest.at(i)->fPriority); 1905480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger prevPriority = pqTest.at(i)->fPriority; 1915480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1925480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1935480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger // Verify that after sorting the queue still produces the same result as the control queue 1945480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger for (int i = 0; i < count; i++) { 1955480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger REPORTER_ASSERT(reporter, *pqControl.peek() == *pqTest.peek()); 1965480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger pqControl.pop(); 1975480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger pqTest.pop(); 1985480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1995480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger} 2005480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 2013555bd88a6513d219a084eabd41e9dff9e513605bsalomonDEF_TEST(TDPQueueTest, reporter) { 2023555bd88a6513d219a084eabd41e9dff9e513605bsalomon simple_test(reporter); 2033555bd88a6513d219a084eabd41e9dff9e513605bsalomon random_test(reporter); 2045480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger sort_test(reporter); 2053555bd88a6513d219a084eabd41e9dff9e513605bsalomon} 206