blob: 15bcec8550be99930b313a81a7c7b5a1ac00eccc [file] [log] [blame]
Tao Bao8f237572017-03-26 13:36:49 -07001/*
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 <signal.h>
18#include <sys/types.h>
19
20#include <vector>
21
22#include <gtest/gtest.h>
23
Tianjie Xu57dd9612017-08-17 17:50:56 -070024#include "rangeset.h"
Tao Bao8f237572017-03-26 13:36:49 -070025
26TEST(RangeSetTest, Parse_smoke) {
27 RangeSet rs = RangeSet::Parse("2,1,10");
Tao Baobf5b77d2017-03-30 16:57:29 -070028 ASSERT_EQ(static_cast<size_t>(1), rs.size());
29 ASSERT_EQ((Range{ 1, 10 }), rs[0]);
30 ASSERT_EQ(static_cast<size_t>(9), rs.blocks());
Tao Bao8f237572017-03-26 13:36:49 -070031
32 RangeSet rs2 = RangeSet::Parse("4,15,20,1,10");
Tao Baobf5b77d2017-03-30 16:57:29 -070033 ASSERT_EQ(static_cast<size_t>(2), rs2.size());
34 ASSERT_EQ((Range{ 15, 20 }), rs2[0]);
35 ASSERT_EQ((Range{ 1, 10 }), rs2[1]);
36 ASSERT_EQ(static_cast<size_t>(14), rs2.blocks());
Tao Bao8f237572017-03-26 13:36:49 -070037
38 // Leading zeros are fine. But android::base::ParseUint() doesn't like trailing zeros like "10 ".
39 ASSERT_EQ(rs, RangeSet::Parse(" 2, 1, 10"));
40 ASSERT_EXIT(RangeSet::Parse("2,1,10 "), ::testing::KilledBySignal(SIGABRT), "");
41}
42
43TEST(RangeSetTest, Parse_InvalidCases) {
44 // Insufficient number of tokens.
45 ASSERT_EXIT(RangeSet::Parse(""), ::testing::KilledBySignal(SIGABRT), "");
46 ASSERT_EXIT(RangeSet::Parse("2,1"), ::testing::KilledBySignal(SIGABRT), "");
47
48 // The first token (i.e. the number of following tokens) is invalid.
49 ASSERT_EXIT(RangeSet::Parse("a,1,1"), ::testing::KilledBySignal(SIGABRT), "");
50 ASSERT_EXIT(RangeSet::Parse("3,1,1"), ::testing::KilledBySignal(SIGABRT), "");
51 ASSERT_EXIT(RangeSet::Parse("-3,1,1"), ::testing::KilledBySignal(SIGABRT), "");
52 ASSERT_EXIT(RangeSet::Parse("2,1,2,3"), ::testing::KilledBySignal(SIGABRT), "");
53
54 // Invalid tokens.
55 ASSERT_EXIT(RangeSet::Parse("2,1,10a"), ::testing::KilledBySignal(SIGABRT), "");
56 ASSERT_EXIT(RangeSet::Parse("2,,10"), ::testing::KilledBySignal(SIGABRT), "");
57
58 // Empty or negative range.
59 ASSERT_EXIT(RangeSet::Parse("2,2,2"), ::testing::KilledBySignal(SIGABRT), "");
60 ASSERT_EXIT(RangeSet::Parse("2,2,1"), ::testing::KilledBySignal(SIGABRT), "");
61}
62
63TEST(RangeSetTest, Overlaps) {
64 RangeSet r1 = RangeSet::Parse("2,1,6");
65 RangeSet r2 = RangeSet::Parse("2,5,10");
66 ASSERT_TRUE(r1.Overlaps(r2));
67 ASSERT_TRUE(r2.Overlaps(r1));
68
69 r2 = RangeSet::Parse("2,6,10");
70 ASSERT_FALSE(r1.Overlaps(r2));
71 ASSERT_FALSE(r2.Overlaps(r1));
72
73 ASSERT_FALSE(RangeSet::Parse("2,3,5").Overlaps(RangeSet::Parse("2,5,7")));
74 ASSERT_FALSE(RangeSet::Parse("2,5,7").Overlaps(RangeSet::Parse("2,3,5")));
75}
76
77TEST(RangeSetTest, GetBlockNumber) {
78 RangeSet rs = RangeSet::Parse("2,1,10");
79 ASSERT_EQ(static_cast<size_t>(1), rs.GetBlockNumber(0));
80 ASSERT_EQ(static_cast<size_t>(6), rs.GetBlockNumber(5));
81 ASSERT_EQ(static_cast<size_t>(9), rs.GetBlockNumber(8));
82
83 // Out of bound.
84 ASSERT_EXIT(rs.GetBlockNumber(9), ::testing::KilledBySignal(SIGABRT), "");
85}
Tao Baobf5b77d2017-03-30 16:57:29 -070086
87TEST(RangeSetTest, equality) {
88 ASSERT_EQ(RangeSet::Parse("2,1,6"), RangeSet::Parse("2,1,6"));
89
90 ASSERT_NE(RangeSet::Parse("2,1,6"), RangeSet::Parse("2,1,7"));
91 ASSERT_NE(RangeSet::Parse("2,1,6"), RangeSet::Parse("2,2,7"));
92
93 // The orders of Range's matter. "4,1,5,8,10" != "4,8,10,1,5".
94 ASSERT_NE(RangeSet::Parse("4,1,5,8,10"), RangeSet::Parse("4,8,10,1,5"));
95}
96
97TEST(RangeSetTest, iterators) {
98 RangeSet rs = RangeSet::Parse("4,1,5,8,10");
99 std::vector<Range> ranges;
100 for (const auto& range : rs) {
101 ranges.push_back(range);
102 }
103 ASSERT_EQ((std::vector<Range>{ Range{ 1, 5 }, Range{ 8, 10 } }), ranges);
104
105 ranges.clear();
106
107 // Reverse iterators.
108 for (auto it = rs.crbegin(); it != rs.crend(); it++) {
109 ranges.push_back(*it);
110 }
111 ASSERT_EQ((std::vector<Range>{ Range{ 8, 10 }, Range{ 1, 5 } }), ranges);
112}
Tianjie Xub9e7fc72017-07-26 16:41:24 -0700113
114TEST(RangeSetTest, tostring) {
115 ASSERT_EQ("2,1,6", RangeSet::Parse("2,1,6").ToString());
116 ASSERT_EQ("4,1,5,8,10", RangeSet::Parse("4,1,5,8,10").ToString());
117 ASSERT_EQ("6,1,3,4,6,15,22", RangeSet::Parse("6,1,3,4,6,15,22").ToString());
118}
119
120TEST(SortedRangeSetTest, insertion) {
121 SortedRangeSet rs({ { 2, 3 }, { 4, 6 }, { 8, 14 } });
122 rs.Insert({ 1, 2 });
123 ASSERT_EQ(SortedRangeSet({ { 1, 3 }, { 4, 6 }, { 8, 14 } }), rs);
124 ASSERT_EQ(static_cast<size_t>(10), rs.blocks());
125 rs.Insert({ 3, 5 });
126 ASSERT_EQ(SortedRangeSet({ { 1, 6 }, { 8, 14 } }), rs);
127 ASSERT_EQ(static_cast<size_t>(11), rs.blocks());
128
129 SortedRangeSet r1({ { 20, 22 }, { 15, 18 } });
130 rs.Insert(r1);
131 ASSERT_EQ(SortedRangeSet({ { 1, 6 }, { 8, 14 }, { 15, 18 }, { 20, 22 } }), rs);
132 ASSERT_EQ(static_cast<size_t>(16), rs.blocks());
133
134 SortedRangeSet r2({ { 2, 7 }, { 15, 21 }, { 20, 25 } });
135 rs.Insert(r2);
136 ASSERT_EQ(SortedRangeSet({ { 1, 7 }, { 8, 14 }, { 15, 25 } }), rs);
137 ASSERT_EQ(static_cast<size_t>(22), rs.blocks());
138}
139
140TEST(SortedRangeSetTest, file_range) {
141 SortedRangeSet rs;
142 rs.Insert(4096, 4096);
143 ASSERT_EQ(SortedRangeSet({ { 1, 2 } }), rs);
144 // insert block 2-9
145 rs.Insert(4096 * 3 - 1, 4096 * 7);
146 ASSERT_EQ(SortedRangeSet({ { 1, 10 } }), rs);
147 // insert block 15-19
148 rs.Insert(4096 * 15 + 1, 4096 * 4);
149 ASSERT_EQ(SortedRangeSet({ { 1, 10 }, { 15, 20 } }), rs);
150
151 // rs overlaps block 2-2
152 ASSERT_TRUE(rs.Overlaps(4096 * 2 - 1, 10));
153 ASSERT_FALSE(rs.Overlaps(4096 * 10, 4096 * 5));
154
155 ASSERT_EQ(static_cast<size_t>(10), rs.GetOffsetInRangeSet(4106));
156 ASSERT_EQ(static_cast<size_t>(40970), rs.GetOffsetInRangeSet(4096 * 16 + 10));
157 // block#10 not in range.
158 ASSERT_EXIT(rs.GetOffsetInRangeSet(40970), ::testing::KilledBySignal(SIGABRT), "");
159}