14fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org/* 24fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Copyright 2014 Google Inc. 34fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * 44fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 54fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * found in the LICENSE file. 64fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 74fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 84fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#include "SkRandom.h" 94fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#include "Test.h" 104fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org// This is a GPU-backend specific test 114fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#if SK_SUPPORT_GPU 124fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#include "GrOrderedSet.h" 134fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 144fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypedef GrOrderedSet<int> Set; 154fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypedef GrOrderedSet<const char*, GrStrLess> Set2; 164fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 179ea53f93e79ba312c4b3943923450a8b4aa57c82tfarinaDEF_TEST(GrOrderedSet, reporter) { 184fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Set set; 194fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 204fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.empty()); 214fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 224fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org SkRandom r; 234fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 244fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org int count[1000] = {0}; 254fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // add 10K ints 264fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (int i = 0; i < 10000; ++i) { 274fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org int x = r.nextU() % 1000; 284fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Set::Iter xi = set.insert(x); 294fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, *xi == x); 304fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, !set.empty()); 314fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org count[x] = 1; 324fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 334fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.insert(0); 344fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org count[0] = 1; 354fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.insert(999); 364fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org count[999] = 1; 374fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org int totalCount = 0; 384fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (int i = 0; i < 1000; ++i) { 394fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org totalCount += count[i]; 404fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 414fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, *set.begin() == 0); 424fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, *set.last() == 999); 434fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, --(++set.begin()) == set.begin()); 444fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, --set.end() == set.last()); 454fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.count() == totalCount); 464fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 474fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org int c = 0; 484fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // check that we iterate through the correct number of 494fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // elements and they are properly sorted. 504fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (Set::Iter a = set.begin(); set.end() != a; ++a) { 514fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Set::Iter b = a; 524fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org ++b; 534fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org ++c; 544fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, b == set.end() || *a <= *b); 554fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 564fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, c == set.count()); 574fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 584fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // check that the set finds all ints and only ints added to set 594fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (int i = 0; i < 1000; ++i) { 604fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool existsFind = set.find(i) != set.end(); 614fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool existsCount = 0 != count[i]; 624fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, existsFind == existsCount); 634fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 644fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // remove all the ints between 100 and 200. 654fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (int i = 100; i < 200; ++i) { 664fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.remove(set.find(i)); 674fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org if (1 == count[i]) { 684fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org count[i] = 0; 694fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org --totalCount; 704fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 714fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.count() == totalCount); 724fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.find(i) == set.end()); 734fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 744fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // remove the 0 entry. (tests removing begin()) 754fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, *set.begin() == 0); 764fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, *(--set.end()) == 999); 774fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.remove(set.find(0)); 784fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org count[0] = 0; 794fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org --totalCount; 804fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.count() == totalCount); 814fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.find(0) == set.end()); 824fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, 0 < *set.begin()); 834fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 844fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // remove all the 999 entries (tests removing last()). 854fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.remove(set.find(999)); 864fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org count[999] = 0; 874fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org --totalCount; 884fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.count() == totalCount); 894fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.find(999) == set.end()); 904fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, 999 > *(--set.end())); 914fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.last() == --set.end()); 924fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 934fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // Make sure iteration still goes through correct number of entries 944fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // and is still sorted correctly. 954fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org c = 0; 964fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (Set::Iter a = set.begin(); set.end() != a; ++a) { 974fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Set::Iter b = a; 984fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org ++b; 994fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org ++c; 1004fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, b == set.end() || *a <= *b); 1014fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1024fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, c == set.count()); 1034fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1044fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // repeat check that the set finds all ints and only ints added to set 1054fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org for (int i = 0; i < 1000; ++i) { 1064fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool existsFind = set.find(i) != set.end(); 1074fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool existsCount = 0 != count[i]; 1084fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, existsFind == existsCount); 1094fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1104fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1114fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // remove all entries 1124fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org while (!set.empty()) { 1134fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.remove(set.begin()); 1144fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1154fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1164fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // test reset on empty set. 1174fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set.reset(); 1184fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set.empty()); 1194fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1204fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1214fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org // test using c strings 1224fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org const char* char1 = "dog"; 1234fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org const char* char2 = "cat"; 1244fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org const char* char3 = "dog"; 1254fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1264fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Set2 set2; 1274fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1284fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.insert("ape"); 1294fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.insert(char1); 1304fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.insert(char2); 1314fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.insert(char3); 1324fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.insert("ant"); 1334fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.insert("cat"); 1344fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1354fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.count() == 4); 1364fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.find("dog") == set2.last()); 1374fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.find("cat") != set2.end()); 1384fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.find("ant") == set2.begin()); 1394fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.find("bug") == set2.end()); 1404fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1414fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.remove(set2.find("ant")); 1424fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.find("ant") == set2.end()); 1434fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.count() == 3); 1444fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1454fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org set2.reset(); 1464fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org REPORTER_ASSERT(reporter, set2.empty()); 1474fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1484fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1494fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#endif 150