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 {
AATestAATest25     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 {
operator ()AATest::Smaller33         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__
TEST(indexed_priority_queue,empty_and_size)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 
TEST(indexed_priority_queue,top)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 
TEST(indexed_priority_queue,push_same_aa)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 
TEST(indexed_priority_queue,remove_nonexistant)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 
TEST(indexed_priority_queue,remove_same_aa)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 
TEST(indexed_priority_queue,nulls)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 
TEST(indexed_priority_queue,pop)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