Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 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 | |
Joe Onorato | 9fc9edf | 2017-10-15 20:08:52 -0700 | [diff] [blame] | 17 | #include "src/anomaly/indexed_priority_queue.h" |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 18 | |
| 19 | #include <gtest/gtest.h> |
| 20 | |
Bookatz | b487b55 | 2017-09-18 11:26:01 -0700 | [diff] [blame] | 21 | using namespace android::os::statsd; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 22 | |
| 23 | /** struct for template in indexed_priority_queue */ |
| 24 | struct AATest : public RefBase { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 25 | AATest(uint32_t val, std::string a, std::string b) : val(val), a(a), b(b) { |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 26 | } |
| 27 | |
| 28 | const int val; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 29 | const std::string a; |
| 30 | const std::string b; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 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) { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 41 | std::string emptyMetricId; |
| 42 | std::string emptyDimensionId; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 43 | indexed_priority_queue<AATest, AATest::Smaller> ipq; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 44 | sp<const AATest> aa4 = new AATest{4, emptyMetricId, emptyDimensionId}; |
| 45 | sp<const AATest> aa8 = new AATest{8, emptyMetricId, emptyDimensionId}; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 46 | |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 47 | ASSERT_EQ(0u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 48 | EXPECT_TRUE(ipq.empty()); |
| 49 | |
| 50 | ipq.push(aa4); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 51 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 52 | EXPECT_FALSE(ipq.empty()); |
| 53 | |
| 54 | ipq.push(aa8); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 55 | ASSERT_EQ(2u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 56 | EXPECT_FALSE(ipq.empty()); |
| 57 | |
| 58 | ipq.remove(aa4); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 59 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 60 | EXPECT_FALSE(ipq.empty()); |
| 61 | |
| 62 | ipq.remove(aa8); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 63 | ASSERT_EQ(0u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 64 | EXPECT_TRUE(ipq.empty()); |
| 65 | } |
| 66 | |
| 67 | TEST(indexed_priority_queue, top) { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 68 | std::string emptyMetricId; |
| 69 | std::string emptyDimensionId; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 70 | indexed_priority_queue<AATest, AATest::Smaller> ipq; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 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}; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 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) { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 122 | std::string emptyMetricId; |
| 123 | std::string emptyDimensionId; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 124 | indexed_priority_queue<AATest, AATest::Smaller> ipq; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 125 | sp<const AATest> aa4_a = new AATest{4, emptyMetricId, emptyDimensionId}; |
| 126 | sp<const AATest> aa4_b = new AATest{4, emptyMetricId, emptyDimensionId}; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 127 | |
| 128 | ipq.push(aa4_a); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 129 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 130 | EXPECT_TRUE(ipq.contains(aa4_a)); |
| 131 | EXPECT_FALSE(ipq.contains(aa4_b)); |
| 132 | |
| 133 | ipq.push(aa4_a); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 134 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 135 | EXPECT_TRUE(ipq.contains(aa4_a)); |
| 136 | EXPECT_FALSE(ipq.contains(aa4_b)); |
| 137 | |
| 138 | ipq.push(aa4_b); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 139 | ASSERT_EQ(2u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 140 | EXPECT_TRUE(ipq.contains(aa4_a)); |
| 141 | EXPECT_TRUE(ipq.contains(aa4_b)); |
| 142 | } |
| 143 | |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 144 | TEST(indexed_priority_queue, remove_nonexistant) { |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 145 | std::string emptyMetricId; |
| 146 | std::string emptyDimensionId; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 147 | indexed_priority_queue<AATest, AATest::Smaller> ipq; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 148 | sp<const AATest> aa4 = new AATest{4, emptyMetricId, emptyDimensionId}; |
| 149 | sp<const AATest> aa5 = new AATest{5, emptyMetricId, emptyDimensionId}; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 150 | |
| 151 | ipq.push(aa4); |
| 152 | ipq.remove(aa5); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 153 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 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; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 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}; |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 164 | |
| 165 | ipq.push(aa4_a); |
| 166 | ipq.push(aa4_b); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 167 | ASSERT_EQ(2u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 168 | EXPECT_TRUE(ipq.contains(aa4_a)); |
| 169 | EXPECT_TRUE(ipq.contains(aa4_b)); |
| 170 | |
| 171 | ipq.remove(aa4_b); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 172 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 173 | EXPECT_TRUE(ipq.contains(aa4_a)); |
| 174 | EXPECT_FALSE(ipq.contains(aa4_b)); |
| 175 | |
| 176 | ipq.remove(aa4_a); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 177 | ASSERT_EQ(0u, ipq.size()); |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 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 | |
Bookatz | ece5f70 | 2017-10-09 14:59:38 -0700 | [diff] [blame] | 197 | TEST(indexed_priority_queue, pop) { |
| 198 | indexed_priority_queue<AATest, AATest::Smaller> ipq; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 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}; |
Bookatz | ece5f70 | 2017-10-09 14:59:38 -0700 | [diff] [blame] | 204 | |
| 205 | ipq.push(c); |
| 206 | ipq.push(b); |
| 207 | ipq.push(a); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 208 | ASSERT_EQ(3u, ipq.size()); |
Bookatz | ece5f70 | 2017-10-09 14:59:38 -0700 | [diff] [blame] | 209 | |
| 210 | ipq.pop(); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 211 | ASSERT_EQ(2u, ipq.size()); |
Bookatz | ece5f70 | 2017-10-09 14:59:38 -0700 | [diff] [blame] | 212 | EXPECT_FALSE(ipq.contains(a)); |
| 213 | EXPECT_TRUE(ipq.contains(b)); |
| 214 | EXPECT_TRUE(ipq.contains(c)); |
| 215 | |
| 216 | ipq.pop(); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 217 | ASSERT_EQ(1u, ipq.size()); |
Bookatz | ece5f70 | 2017-10-09 14:59:38 -0700 | [diff] [blame] | 218 | EXPECT_FALSE(ipq.contains(a)); |
| 219 | EXPECT_FALSE(ipq.contains(b)); |
| 220 | EXPECT_TRUE(ipq.contains(c)); |
| 221 | |
| 222 | ipq.pop(); |
Muhammad Qureshi | dff78d6 | 2020-05-11 13:37:43 -0700 | [diff] [blame] | 223 | ASSERT_EQ(0u, ipq.size()); |
Bookatz | ece5f70 | 2017-10-09 14:59:38 -0700 | [diff] [blame] | 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 | |
Bookatz | 0e95909 | 2017-09-07 17:39:37 -0700 | [diff] [blame] | 233 | #else |
| 234 | GTEST_LOG_(INFO) << "This test does nothing.\n"; |
| 235 | #endif |