1 /* 2 * Copyright 2014 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 // This is a GPU-backend specific test 9 #if SK_SUPPORT_GPU 10 11 #include "GrRedBlackTree.h" 12 #include "SkRandom.h" 13 #include "Test.h" 14 15 typedef GrRedBlackTree<int> Tree; 16 17 DEF_TEST(GrRedBlackTreeTest, reporter) { 18 Tree tree; 19 20 SkRandom r; 21 22 int count[100] = {0}; 23 // add 10K ints 24 for (int i = 0; i < 10000; ++i) { 25 int x = r.nextU() % 100; 26 Tree::Iter xi = tree.insert(x); 27 REPORTER_ASSERT(reporter, *xi == x); 28 ++count[x]; 29 } 30 31 tree.insert(0); 32 ++count[0]; 33 tree.insert(99); 34 ++count[99]; 35 REPORTER_ASSERT(reporter, *tree.begin() == 0); 36 REPORTER_ASSERT(reporter, *tree.last() == 99); 37 REPORTER_ASSERT(reporter, --(++tree.begin()) == tree.begin()); 38 REPORTER_ASSERT(reporter, --tree.end() == tree.last()); 39 REPORTER_ASSERT(reporter, tree.count() == 10002); 40 41 int c = 0; 42 // check that we iterate through the correct number of 43 // elements and they are properly sorted. 44 for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) { 45 Tree::Iter b = a; 46 ++b; 47 ++c; 48 REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b); 49 } 50 REPORTER_ASSERT(reporter, c == tree.count()); 51 52 // check that the tree reports the correct number of each int 53 // and that we can iterate through them correctly both forward 54 // and backward. 55 for (int i = 0; i < 100; ++i) { 56 int c; 57 c = tree.countOf(i); 58 REPORTER_ASSERT(reporter, c == count[i]); 59 c = 0; 60 Tree::Iter iter = tree.findFirst(i); 61 while (iter != tree.end() && *iter == i) { 62 ++c; 63 ++iter; 64 } 65 REPORTER_ASSERT(reporter, count[i] == c); 66 c = 0; 67 iter = tree.findLast(i); 68 if (iter != tree.end()) { 69 do { 70 if (*iter == i) { 71 ++c; 72 } else { 73 break; 74 } 75 if (iter != tree.begin()) { 76 --iter; 77 } else { 78 break; 79 } 80 } while (true); 81 } 82 REPORTER_ASSERT(reporter, c == count[i]); 83 } 84 // remove all the ints between 25 and 74. Randomly chose to remove 85 // the first, last, or any entry for each. 86 for (int i = 25; i < 75; ++i) { 87 while (0 != tree.countOf(i)) { 88 --count[i]; 89 int x = r.nextU() % 3; 90 Tree::Iter iter; 91 switch (x) { 92 case 0: 93 iter = tree.findFirst(i); 94 break; 95 case 1: 96 iter = tree.findLast(i); 97 break; 98 case 2: 99 default: 100 iter = tree.find(i); 101 break; 102 } 103 tree.remove(iter); 104 } 105 REPORTER_ASSERT(reporter, 0 == count[i]); 106 REPORTER_ASSERT(reporter, tree.findFirst(i) == tree.end()); 107 REPORTER_ASSERT(reporter, tree.findLast(i) == tree.end()); 108 REPORTER_ASSERT(reporter, tree.find(i) == tree.end()); 109 } 110 // remove all of the 0 entries. (tests removing begin()) 111 REPORTER_ASSERT(reporter, *tree.begin() == 0); 112 REPORTER_ASSERT(reporter, *(--tree.end()) == 99); 113 while (0 != tree.countOf(0)) { 114 --count[0]; 115 tree.remove(tree.find(0)); 116 } 117 REPORTER_ASSERT(reporter, 0 == count[0]); 118 REPORTER_ASSERT(reporter, tree.findFirst(0) == tree.end()); 119 REPORTER_ASSERT(reporter, tree.findLast(0) == tree.end()); 120 REPORTER_ASSERT(reporter, tree.find(0) == tree.end()); 121 REPORTER_ASSERT(reporter, 0 < *tree.begin()); 122 123 // remove all the 99 entries (tests removing last()). 124 while (0 != tree.countOf(99)) { 125 --count[99]; 126 tree.remove(tree.find(99)); 127 } 128 REPORTER_ASSERT(reporter, 0 == count[99]); 129 REPORTER_ASSERT(reporter, tree.findFirst(99) == tree.end()); 130 REPORTER_ASSERT(reporter, tree.findLast(99) == tree.end()); 131 REPORTER_ASSERT(reporter, tree.find(99) == tree.end()); 132 REPORTER_ASSERT(reporter, 99 > *(--tree.end())); 133 REPORTER_ASSERT(reporter, tree.last() == --tree.end()); 134 135 // Make sure iteration still goes through correct number of entries 136 // and is still sorted correctly. 137 c = 0; 138 for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) { 139 Tree::Iter b = a; 140 ++b; 141 ++c; 142 REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b); 143 } 144 REPORTER_ASSERT(reporter, c == tree.count()); 145 146 // repeat check that correct number of each entry is in the tree 147 // and iterates correctly both forward and backward. 148 for (int i = 0; i < 100; ++i) { 149 REPORTER_ASSERT(reporter, tree.countOf(i) == count[i]); 150 int c = 0; 151 Tree::Iter iter = tree.findFirst(i); 152 while (iter != tree.end() && *iter == i) { 153 ++c; 154 ++iter; 155 } 156 REPORTER_ASSERT(reporter, count[i] == c); 157 c = 0; 158 iter = tree.findLast(i); 159 if (iter != tree.end()) { 160 do { 161 if (*iter == i) { 162 ++c; 163 } else { 164 break; 165 } 166 if (iter != tree.begin()) { 167 --iter; 168 } else { 169 break; 170 } 171 } while (true); 172 } 173 REPORTER_ASSERT(reporter, count[i] == c); 174 } 175 176 // remove all entries 177 while (!tree.empty()) { 178 tree.remove(tree.begin()); 179 } 180 181 // test reset on empty tree. 182 tree.reset(); 183 } 184 185 #endif 186
