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
21using namespace android::os::statsd;
22
23/** struct for template in indexed_priority_queue */
24struct 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__
40TEST(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
67TEST(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
121TEST(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
144TEST(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
158TEST(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
182TEST(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
197TEST(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
234GTEST_LOG_(INFO) << "This test does nothing.\n";
235#endif
236