1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "src/anomaly/indexed_priority_queue.h" 18 19 #include <gtest/gtest.h> 20 21 using namespace android::os::statsd; 22 23 /** struct for template in indexed_priority_queue */ 24 struct AATest : public RefBase { 25 AATest(uint32_t val, std::string a, std::string b) : val(val), a(a), b(b) { 26 } 27 28 const int val; 29 const std::string a; 30 const std::string b; 31 32 struct Smaller { 33 bool operator()(const sp<const AATest> a, const sp<const AATest> b) const { 34 return (a->val < b->val); 35 } 36 }; 37 }; 38 39 #ifdef __ANDROID__ 40 TEST(indexed_priority_queue, empty_and_size) { 41 std::string emptyMetricId; 42 std::string emptyDimensionId; 43 indexed_priority_queue<AATest, AATest::Smaller> ipq; 44 sp<const AATest> aa4 = new AATest{4, emptyMetricId, emptyDimensionId}; 45 sp<const AATest> aa8 = new AATest{8, emptyMetricId, emptyDimensionId}; 46 47 EXPECT_EQ(0u, ipq.size()); 48 EXPECT_TRUE(ipq.empty()); 49 50 ipq.push(aa4); 51 EXPECT_EQ(1u, ipq.size()); 52 EXPECT_FALSE(ipq.empty()); 53 54 ipq.push(aa8); 55 EXPECT_EQ(2u, ipq.size()); 56 EXPECT_FALSE(ipq.empty()); 57 58 ipq.remove(aa4); 59 EXPECT_EQ(1u, ipq.size()); 60 EXPECT_FALSE(ipq.empty()); 61 62 ipq.remove(aa8); 63 EXPECT_EQ(0u, ipq.size()); 64 EXPECT_TRUE(ipq.empty()); 65 } 66 67 TEST(indexed_priority_queue, top) { 68 std::string emptyMetricId; 69 std::string emptyDimensionId; 70 indexed_priority_queue<AATest, AATest::Smaller> ipq; 71 sp<const AATest> aa2 = new AATest{2, emptyMetricId, emptyDimensionId}; 72 sp<const AATest> aa4 = new AATest{4, emptyMetricId, emptyDimensionId}; 73 sp<const AATest> aa8 = new AATest{8, emptyMetricId, emptyDimensionId}; 74 sp<const AATest> aa12 = new AATest{12, emptyMetricId, emptyDimensionId}; 75 sp<const AATest> aa16 = new AATest{16, emptyMetricId, emptyDimensionId}; 76 sp<const AATest> aa20 = new AATest{20, emptyMetricId, emptyDimensionId}; 77 78 EXPECT_EQ(ipq.top(), nullptr); 79 80 // add 8, 4, 12 81 ipq.push(aa8); 82 EXPECT_EQ(ipq.top(), aa8); 83 84 ipq.push(aa12); 85 EXPECT_EQ(ipq.top(), aa8); 86 87 ipq.push(aa4); 88 EXPECT_EQ(ipq.top(), aa4); 89 90 // remove 12, 4 91 ipq.remove(aa12); 92 EXPECT_EQ(ipq.top(), aa4); 93 94 ipq.remove(aa4); 95 EXPECT_EQ(ipq.top(), aa8); 96 97 // add 16, 2, 20 98 ipq.push(aa16); 99 EXPECT_EQ(ipq.top(), aa8); 100 101 ipq.push(aa2); 102 EXPECT_EQ(ipq.top(), aa2); 103 104 ipq.push(aa20); 105 EXPECT_EQ(ipq.top(), aa2); 106 107 // remove 2, 20, 16, 8 108 ipq.remove(aa2); 109 EXPECT_EQ(ipq.top(), aa8); 110 111 ipq.remove(aa20); 112 EXPECT_EQ(ipq.top(), aa8); 113 114 ipq.remove(aa16); 115 EXPECT_EQ(ipq.top(), aa8); 116 117 ipq.remove(aa8); 118 EXPECT_EQ(ipq.top(), nullptr); 119 } 120 121 TEST(indexed_priority_queue, push_same_aa) { 122 std::string emptyMetricId; 123 std::string emptyDimensionId; 124 indexed_priority_queue<AATest, AATest::Smaller> ipq; 125 sp<const AATest> aa4_a = new AATest{4, emptyMetricId, emptyDimensionId}; 126 sp<const AATest> aa4_b = new AATest{4, emptyMetricId, emptyDimensionId}; 127 128 ipq.push(aa4_a); 129 EXPECT_EQ(1u, ipq.size()); 130 EXPECT_TRUE(ipq.contains(aa4_a)); 131 EXPECT_FALSE(ipq.contains(aa4_b)); 132 133 ipq.push(aa4_a); 134 EXPECT_EQ(1u, ipq.size()); 135 EXPECT_TRUE(ipq.contains(aa4_a)); 136 EXPECT_FALSE(ipq.contains(aa4_b)); 137 138 ipq.push(aa4_b); 139 EXPECT_EQ(2u, ipq.size()); 140 EXPECT_TRUE(ipq.contains(aa4_a)); 141 EXPECT_TRUE(ipq.contains(aa4_b)); 142 } 143 144 TEST(indexed_priority_queue, remove_nonexistant) { 145 std::string emptyMetricId; 146 std::string emptyDimensionId; 147 indexed_priority_queue<AATest, AATest::Smaller> ipq; 148 sp<const AATest> aa4 = new AATest{4, emptyMetricId, emptyDimensionId}; 149 sp<const AATest> aa5 = new AATest{5, emptyMetricId, emptyDimensionId}; 150 151 ipq.push(aa4); 152 ipq.remove(aa5); 153 EXPECT_EQ(1u, ipq.size()); 154 EXPECT_TRUE(ipq.contains(aa4)); 155 EXPECT_FALSE(ipq.contains(aa5)); 156 } 157 158 TEST(indexed_priority_queue, remove_same_aa) { 159 indexed_priority_queue<AATest, AATest::Smaller> ipq; 160 std::string emptyMetricId; 161 std::string emptyDimensionId; 162 sp<const AATest> aa4_a = new AATest{4, emptyMetricId, emptyDimensionId}; 163 sp<const AATest> aa4_b = new AATest{4, emptyMetricId, emptyDimensionId}; 164 165 ipq.push(aa4_a); 166 ipq.push(aa4_b); 167 EXPECT_EQ(2u, ipq.size()); 168 EXPECT_TRUE(ipq.contains(aa4_a)); 169 EXPECT_TRUE(ipq.contains(aa4_b)); 170 171 ipq.remove(aa4_b); 172 EXPECT_EQ(1u, ipq.size()); 173 EXPECT_TRUE(ipq.contains(aa4_a)); 174 EXPECT_FALSE(ipq.contains(aa4_b)); 175 176 ipq.remove(aa4_a); 177 EXPECT_EQ(0u, ipq.size()); 178 EXPECT_FALSE(ipq.contains(aa4_a)); 179 EXPECT_FALSE(ipq.contains(aa4_b)); 180 } 181 182 TEST(indexed_priority_queue, nulls) { 183 indexed_priority_queue<AATest, AATest::Smaller> ipq; 184 185 EXPECT_TRUE(ipq.empty()); 186 EXPECT_FALSE(ipq.contains(nullptr)); 187 188 ipq.push(nullptr); 189 EXPECT_TRUE(ipq.empty()); 190 EXPECT_FALSE(ipq.contains(nullptr)); 191 192 ipq.remove(nullptr); 193 EXPECT_TRUE(ipq.empty()); 194 EXPECT_FALSE(ipq.contains(nullptr)); 195 } 196 197 TEST(indexed_priority_queue, pop) { 198 indexed_priority_queue<AATest, AATest::Smaller> ipq; 199 std::string emptyMetricId; 200 std::string emptyDimensionId; 201 sp<const AATest> a = new AATest{1, emptyMetricId, emptyDimensionId}; 202 sp<const AATest> b = new AATest{2, emptyMetricId, emptyDimensionId}; 203 sp<const AATest> c = new AATest{3, emptyMetricId, emptyDimensionId}; 204 205 ipq.push(c); 206 ipq.push(b); 207 ipq.push(a); 208 EXPECT_EQ(3u, ipq.size()); 209 210 ipq.pop(); 211 EXPECT_EQ(2u, ipq.size()); 212 EXPECT_FALSE(ipq.contains(a)); 213 EXPECT_TRUE(ipq.contains(b)); 214 EXPECT_TRUE(ipq.contains(c)); 215 216 ipq.pop(); 217 EXPECT_EQ(1u, ipq.size()); 218 EXPECT_FALSE(ipq.contains(a)); 219 EXPECT_FALSE(ipq.contains(b)); 220 EXPECT_TRUE(ipq.contains(c)); 221 222 ipq.pop(); 223 EXPECT_EQ(0u, ipq.size()); 224 EXPECT_FALSE(ipq.contains(a)); 225 EXPECT_FALSE(ipq.contains(b)); 226 EXPECT_FALSE(ipq.contains(c)); 227 EXPECT_TRUE(ipq.empty()); 228 229 ipq.pop(); // pop an empty queue 230 EXPECT_TRUE(ipq.empty()); 231 } 232 233 #else 234 GTEST_LOG_(INFO) << "This test does nothing.\n"; 235 #endif 236
