Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(442)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: tests/GrRedBlackTreeTest.cpp

Issue 1226203013: Remove GrRedBlackTree (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: rebase Created 5 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « tests/GrOrderedSetTest.cpp ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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(GrRedBlackTree, 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
OLDNEW
« no previous file with comments | « tests/GrOrderedSetTest.cpp ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698