aboutsummaryrefslogtreecommitdiffhomepage
path: root/src
diff options
context:
space:
mode:
authorGravatar tfarina@chromium.org <tfarina@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81>2014-01-29 23:56:40 +0000
committerGravatar tfarina@chromium.org <tfarina@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81>2014-01-29 23:56:40 +0000
commit68f3a3e0b09fc544ebb20d46e37a95e01b83f74a (patch)
tree15f9c51d7b80858fb1c38282b657da9078de86ec /src
parent09dd1abc54ce92cef01e4cb85d147baf903d9d48 (diff)
Reland "Unwrap GrRedBlackTree unit test and use REPORTER_ASSERT()."
BUG=None TEST=tests R=robertphillips@google.com Review URL: https://codereview.chromium.org/137423009 git-svn-id: http://skia.googlecode.com/svn/trunk@13233 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'src')
-rw-r--r--src/gpu/GrRedBlackTree.h172
1 files changed, 1 insertions, 171 deletions
diff --git a/src/gpu/GrRedBlackTree.h b/src/gpu/GrRedBlackTree.h
index 1b2195c4f7..41a3dfb61e 100644
--- a/src/gpu/GrRedBlackTree.h
+++ b/src/gpu/GrRedBlackTree.h
@@ -8,6 +8,7 @@
#ifndef GrRedBlackTree_DEFINED
#define GrRedBlackTree_DEFINED
+#include "GrConfig.h"
#include "SkTypes.h"
template <typename T>
@@ -941,175 +942,4 @@ bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,
}
#endif
-#include "SkRandom.h"
-
-template <typename T, typename C>
-void GrRedBlackTree<T,C>::UnitTest() {
- GrRedBlackTree<int> tree;
-
- SkRandom r;
-
- int count[100] = {0};
- // add 10K ints
- for (int i = 0; i < 10000; ++i) {
- int x = r.nextU()%100;
- SkDEBUGCODE(Iter xi = ) tree.insert(x);
- SkASSERT(*xi == x);
- ++count[x];
- }
-
- tree.insert(0);
- ++count[0];
- tree.insert(99);
- ++count[99];
- SkASSERT(*tree.begin() == 0);
- SkASSERT(*tree.last() == 99);
- SkASSERT(--(++tree.begin()) == tree.begin());
- SkASSERT(--tree.end() == tree.last());
- SkASSERT(tree.count() == 10002);
-
- int c = 0;
- // check that we iterate through the correct number of
- // elements and they are properly sorted.
- for (Iter a = tree.begin(); tree.end() != a; ++a) {
- Iter b = a;
- ++b;
- ++c;
- SkASSERT(b == tree.end() || *a <= *b);
- }
- SkASSERT(c == tree.count());
-
- // check that the tree reports the correct number of each int
- // and that we can iterate through them correctly both forward
- // and backward.
- for (int i = 0; i < 100; ++i) {
- int c;
- c = tree.countOf(i);
- SkASSERT(c == count[i]);
- c = 0;
- Iter iter = tree.findFirst(i);
- while (iter != tree.end() && *iter == i) {
- ++c;
- ++iter;
- }
- SkASSERT(count[i] == c);
- c = 0;
- iter = tree.findLast(i);
- if (iter != tree.end()) {
- do {
- if (*iter == i) {
- ++c;
- } else {
- break;
- }
- if (iter != tree.begin()) {
- --iter;
- } else {
- break;
- }
- } while (true);
- }
- SkASSERT(c == count[i]);
- }
- // remove all the ints between 25 and 74. Randomly chose to remove
- // the first, last, or any entry for each.
- for (int i = 25; i < 75; ++i) {
- while (0 != tree.countOf(i)) {
- --count[i];
- int x = r.nextU() % 3;
- Iter iter;
- switch (x) {
- case 0:
- iter = tree.findFirst(i);
- break;
- case 1:
- iter = tree.findLast(i);
- break;
- case 2:
- default:
- iter = tree.find(i);
- break;
- }
- tree.remove(iter);
- }
- SkASSERT(0 == count[i]);
- SkASSERT(tree.findFirst(i) == tree.end());
- SkASSERT(tree.findLast(i) == tree.end());
- SkASSERT(tree.find(i) == tree.end());
- }
- // remove all of the 0 entries. (tests removing begin())
- SkASSERT(*tree.begin() == 0);
- SkASSERT(*(--tree.end()) == 99);
- while (0 != tree.countOf(0)) {
- --count[0];
- tree.remove(tree.find(0));
- }
- SkASSERT(0 == count[0]);
- SkASSERT(tree.findFirst(0) == tree.end());
- SkASSERT(tree.findLast(0) == tree.end());
- SkASSERT(tree.find(0) == tree.end());
- SkASSERT(0 < *tree.begin());
-
- // remove all the 99 entries (tests removing last()).
- while (0 != tree.countOf(99)) {
- --count[99];
- tree.remove(tree.find(99));
- }
- SkASSERT(0 == count[99]);
- SkASSERT(tree.findFirst(99) == tree.end());
- SkASSERT(tree.findLast(99) == tree.end());
- SkASSERT(tree.find(99) == tree.end());
- SkASSERT(99 > *(--tree.end()));
- SkASSERT(tree.last() == --tree.end());
-
- // Make sure iteration still goes through correct number of entries
- // and is still sorted correctly.
- c = 0;
- for (Iter a = tree.begin(); tree.end() != a; ++a) {
- Iter b = a;
- ++b;
- ++c;
- SkASSERT(b == tree.end() || *a <= *b);
- }
- SkASSERT(c == tree.count());
-
- // repeat check that correct number of each entry is in the tree
- // and iterates correctly both forward and backward.
- for (int i = 0; i < 100; ++i) {
- SkASSERT(tree.countOf(i) == count[i]);
- int c = 0;
- Iter iter = tree.findFirst(i);
- while (iter != tree.end() && *iter == i) {
- ++c;
- ++iter;
- }
- SkASSERT(count[i] == c);
- c = 0;
- iter = tree.findLast(i);
- if (iter != tree.end()) {
- do {
- if (*iter == i) {
- ++c;
- } else {
- break;
- }
- if (iter != tree.begin()) {
- --iter;
- } else {
- break;
- }
- } while (true);
- }
- SkASSERT(count[i] == c);
- }
-
- // remove all entries
- while (!tree.empty()) {
- tree.remove(tree.begin());
- }
-
- // test reset on empty tree.
- tree.reset();
-}
-
#endif