168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org/* 268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org * Copyright 2014 Google Inc. 368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org * 468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org * Use of this source code is governed by a BSD-style license that can be 568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org * found in the LICENSE file. 668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org */ 768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 862c2ce84168aad10b91fbac7c9b1a9e1827bb77atfarina@chromium.org// This is a GPU-backend specific test 962c2ce84168aad10b91fbac7c9b1a9e1827bb77atfarina@chromium.org#if SK_SUPPORT_GPU 1062c2ce84168aad10b91fbac7c9b1a9e1827bb77atfarina@chromium.org 1168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org#include "GrRedBlackTree.h" 1268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org#include "SkRandom.h" 1368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org#include "Test.h" 1468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 1568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.orgtypedef GrRedBlackTree<int> Tree; 1668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 1768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.orgDEF_TEST(GrRedBlackTreeTest, reporter) { 1868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree tree; 1968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 2068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org SkRandom r; 2168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 2268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org int count[100] = {0}; 2368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // add 10K ints 2468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org for (int i = 0; i < 10000; ++i) { 2568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org int x = r.nextU() % 100; 2668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree::Iter xi = tree.insert(x); 2768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, *xi == x); 2868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++count[x]; 2968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 3068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 3168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.insert(0); 3268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++count[0]; 3368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.insert(99); 3468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++count[99]; 3568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, *tree.begin() == 0); 3668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, *tree.last() == 99); 3768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, --(++tree.begin()) == tree.begin()); 3868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, --tree.end() == tree.last()); 3968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.count() == 10002); 4068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 4168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org int c = 0; 4268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // check that we iterate through the correct number of 4368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // elements and they are properly sorted. 4468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) { 4568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree::Iter b = a; 4668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++b; 4768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++c; 4868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b); 4968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 5068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, c == tree.count()); 5168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 5268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // check that the tree reports the correct number of each int 5368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // and that we can iterate through them correctly both forward 5468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // and backward. 5568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org for (int i = 0; i < 100; ++i) { 5668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org int c; 5768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org c = tree.countOf(i); 5868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, c == count[i]); 5968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org c = 0; 6068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree::Iter iter = tree.findFirst(i); 6168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org while (iter != tree.end() && *iter == i) { 6268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++c; 6368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++iter; 6468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 6568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, count[i] == c); 6668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org c = 0; 6768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org iter = tree.findLast(i); 6868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org if (iter != tree.end()) { 6968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org do { 7068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org if (*iter == i) { 7168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++c; 7268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } else { 7368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 7468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 7568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org if (iter != tree.begin()) { 7668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org --iter; 7768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } else { 7868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 7968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 8068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } while (true); 8168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 8268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, c == count[i]); 8368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 8468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // remove all the ints between 25 and 74. Randomly chose to remove 8568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // the first, last, or any entry for each. 8668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org for (int i = 25; i < 75; ++i) { 8768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org while (0 != tree.countOf(i)) { 8868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org --count[i]; 8968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org int x = r.nextU() % 3; 9068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree::Iter iter; 9168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org switch (x) { 9268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org case 0: 9368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org iter = tree.findFirst(i); 9468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 9568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org case 1: 9668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org iter = tree.findLast(i); 9768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 9868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org case 2: 9968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org default: 10068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org iter = tree.find(i); 10168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 10268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 10368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.remove(iter); 10468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 10568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, 0 == count[i]); 10668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.findFirst(i) == tree.end()); 10768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.findLast(i) == tree.end()); 10868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.find(i) == tree.end()); 10968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 11068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // remove all of the 0 entries. (tests removing begin()) 11168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, *tree.begin() == 0); 11268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, *(--tree.end()) == 99); 11368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org while (0 != tree.countOf(0)) { 11468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org --count[0]; 11568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.remove(tree.find(0)); 11668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 11768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, 0 == count[0]); 11868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.findFirst(0) == tree.end()); 11968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.findLast(0) == tree.end()); 12068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.find(0) == tree.end()); 12168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, 0 < *tree.begin()); 12268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 12368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // remove all the 99 entries (tests removing last()). 12468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org while (0 != tree.countOf(99)) { 12568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org --count[99]; 12668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.remove(tree.find(99)); 12768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 12868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, 0 == count[99]); 12968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.findFirst(99) == tree.end()); 13068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.findLast(99) == tree.end()); 13168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.find(99) == tree.end()); 13268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, 99 > *(--tree.end())); 13368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.last() == --tree.end()); 13468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 13568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // Make sure iteration still goes through correct number of entries 13668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // and is still sorted correctly. 13768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org c = 0; 13868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) { 13968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree::Iter b = a; 14068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++b; 14168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++c; 14268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b); 14368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 14468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, c == tree.count()); 14568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 14668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // repeat check that correct number of each entry is in the tree 14768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // and iterates correctly both forward and backward. 14868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org for (int i = 0; i < 100; ++i) { 14968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, tree.countOf(i) == count[i]); 15068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org int c = 0; 15168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org Tree::Iter iter = tree.findFirst(i); 15268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org while (iter != tree.end() && *iter == i) { 15368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++c; 15468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++iter; 15568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 15668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, count[i] == c); 15768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org c = 0; 15868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org iter = tree.findLast(i); 15968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org if (iter != tree.end()) { 16068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org do { 16168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org if (*iter == i) { 16268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org ++c; 16368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } else { 16468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 16568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 16668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org if (iter != tree.begin()) { 16768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org --iter; 16868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } else { 16968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org break; 17068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 17168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } while (true); 17268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 17368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org REPORTER_ASSERT(reporter, count[i] == c); 17468f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 17568f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 17668f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // remove all entries 17768f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org while (!tree.empty()) { 17868f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.remove(tree.begin()); 17968f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org } 18068f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org 18168f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org // test reset on empty tree. 18268f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org tree.reset(); 18368f3a3e0b09fc544ebb20d46e37a95e01b83f74atfarina@chromium.org} 18462c2ce84168aad10b91fbac7c9b1a9e1827bb77atfarina@chromium.org 18562c2ce84168aad10b91fbac7c9b1a9e1827bb77atfarina@chromium.org#endif 186