1 // Copyright (c) 2006, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 // contained_range_map_unittest.cc: Unit tests for ContainedRangeMap
31 //
32 // Author: Mark Mentovai
33
34 #include <stdio.h>
35
36 #include "processor/contained_range_map-inl.h"
37
38 #include "processor/logging.h"
39
40
41 #define ASSERT_TRUE(condition) \
42 if (!(condition)) { \
43 fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \
44 return false; \
45 }
46
47 #define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition))
48
49
50 namespace {
51
52
53 using google_breakpad::ContainedRangeMap;
54
55
RunTests()56 static bool RunTests() {
57 ContainedRangeMap<unsigned int, int> crm;
58
59 // First, do the StoreRange tests. This validates the containment
60 // rules.
61 ASSERT_TRUE (crm.StoreRange(10, 10, 1));
62 ASSERT_FALSE(crm.StoreRange(10, 10, 2)); // exactly equal to 1
63 ASSERT_FALSE(crm.StoreRange(11, 10, 3)); // begins inside 1 and extends up
64 ASSERT_FALSE(crm.StoreRange( 9, 10, 4)); // begins below 1 and ends inside
65 ASSERT_TRUE (crm.StoreRange(11, 9, 5)); // contained by existing
66 ASSERT_TRUE (crm.StoreRange(12, 7, 6));
67 ASSERT_TRUE (crm.StoreRange( 9, 12, 7)); // contains existing
68 ASSERT_TRUE (crm.StoreRange( 9, 13, 8));
69 ASSERT_TRUE (crm.StoreRange( 8, 14, 9));
70 ASSERT_TRUE (crm.StoreRange(30, 3, 10));
71 ASSERT_TRUE (crm.StoreRange(33, 3, 11));
72 ASSERT_TRUE (crm.StoreRange(30, 6, 12)); // storable but totally masked
73 ASSERT_TRUE (crm.StoreRange(40, 8, 13)); // will be totally masked
74 ASSERT_TRUE (crm.StoreRange(40, 4, 14));
75 ASSERT_TRUE (crm.StoreRange(44, 4, 15));
76 ASSERT_FALSE(crm.StoreRange(32, 10, 16)); // begins in #10, ends in #14
77 ASSERT_FALSE(crm.StoreRange(50, 0, 17)); // zero length
78 ASSERT_TRUE (crm.StoreRange(50, 10, 18));
79 ASSERT_TRUE (crm.StoreRange(50, 1, 19));
80 ASSERT_TRUE (crm.StoreRange(59, 1, 20));
81 ASSERT_TRUE (crm.StoreRange(60, 1, 21));
82 ASSERT_TRUE (crm.StoreRange(69, 1, 22));
83 ASSERT_TRUE (crm.StoreRange(60, 10, 23));
84 ASSERT_TRUE (crm.StoreRange(68, 1, 24));
85 ASSERT_TRUE (crm.StoreRange(61, 1, 25));
86 ASSERT_TRUE (crm.StoreRange(61, 8, 26));
87 ASSERT_FALSE(crm.StoreRange(59, 9, 27));
88 ASSERT_FALSE(crm.StoreRange(59, 10, 28));
89 ASSERT_FALSE(crm.StoreRange(59, 11, 29));
90 ASSERT_TRUE (crm.StoreRange(70, 10, 30));
91 ASSERT_TRUE (crm.StoreRange(74, 2, 31));
92 ASSERT_TRUE (crm.StoreRange(77, 2, 32));
93 ASSERT_FALSE(crm.StoreRange(72, 6, 33));
94 ASSERT_TRUE (crm.StoreRange(80, 3, 34));
95 ASSERT_TRUE (crm.StoreRange(81, 1, 35));
96 ASSERT_TRUE (crm.StoreRange(82, 1, 36));
97 ASSERT_TRUE (crm.StoreRange(83, 3, 37));
98 ASSERT_TRUE (crm.StoreRange(84, 1, 38));
99 ASSERT_TRUE (crm.StoreRange(83, 1, 39));
100 ASSERT_TRUE (crm.StoreRange(86, 5, 40));
101 ASSERT_TRUE (crm.StoreRange(88, 1, 41));
102 ASSERT_TRUE (crm.StoreRange(90, 1, 42));
103 ASSERT_TRUE (crm.StoreRange(86, 1, 43));
104 ASSERT_TRUE (crm.StoreRange(87, 1, 44));
105 ASSERT_TRUE (crm.StoreRange(89, 1, 45));
106 ASSERT_TRUE (crm.StoreRange(87, 4, 46));
107 ASSERT_TRUE (crm.StoreRange(87, 3, 47));
108 ASSERT_FALSE(crm.StoreRange(86, 2, 48));
109
110 // Each element in test_data contains the expected result when calling
111 // RetrieveRange on an address.
112 const int test_data[] = {
113 0, // 0
114 0, // 1
115 0, // 2
116 0, // 3
117 0, // 4
118 0, // 5
119 0, // 6
120 0, // 7
121 9, // 8
122 7, // 9
123 1, // 10
124 5, // 11
125 6, // 12
126 6, // 13
127 6, // 14
128 6, // 15
129 6, // 16
130 6, // 17
131 6, // 18
132 5, // 19
133 7, // 20
134 8, // 21
135 0, // 22
136 0, // 23
137 0, // 24
138 0, // 25
139 0, // 26
140 0, // 27
141 0, // 28
142 0, // 29
143 10, // 30
144 10, // 31
145 10, // 32
146 11, // 33
147 11, // 34
148 11, // 35
149 0, // 36
150 0, // 37
151 0, // 38
152 0, // 39
153 14, // 40
154 14, // 41
155 14, // 42
156 14, // 43
157 15, // 44
158 15, // 45
159 15, // 46
160 15, // 47
161 0, // 48
162 0, // 49
163 19, // 50
164 18, // 51
165 18, // 52
166 18, // 53
167 18, // 54
168 18, // 55
169 18, // 56
170 18, // 57
171 18, // 58
172 20, // 59
173 21, // 60
174 25, // 61
175 26, // 62
176 26, // 63
177 26, // 64
178 26, // 65
179 26, // 66
180 26, // 67
181 24, // 68
182 22, // 69
183 30, // 70
184 30, // 71
185 30, // 72
186 30, // 73
187 31, // 74
188 31, // 75
189 30, // 76
190 32, // 77
191 32, // 78
192 30, // 79
193 34, // 80
194 35, // 81
195 36, // 82
196 39, // 83
197 38, // 84
198 37, // 85
199 43, // 86
200 44, // 87
201 41, // 88
202 45, // 89
203 42, // 90
204 0, // 91
205 0, // 92
206 0, // 93
207 0, // 94
208 0, // 95
209 0, // 96
210 0, // 97
211 0, // 98
212 0 // 99
213 };
214 unsigned int test_high = sizeof(test_data) / sizeof(int);
215
216 // Now, do the RetrieveRange tests. This further validates that the
217 // objects were stored properly and that retrieval returns the correct
218 // object.
219 // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
220 // new test_data array will be printed. Exercise caution when doing this.
221 // Be sure to verify the results manually!
222 #ifdef GENERATE_TEST_DATA
223 printf(" const int test_data[] = {\n");
224 #endif // GENERATE_TEST_DATA
225
226 for (unsigned int address = 0; address < test_high; ++address) {
227 int value;
228 if (!crm.RetrieveRange(address, &value))
229 value = 0;
230
231 #ifndef GENERATE_TEST_DATA
232 // Don't use ASSERT inside the loop because it won't show the failed
233 // |address|, and the line number will always be the same. That makes
234 // it difficult to figure out which test failed.
235 if (value != test_data[address]) {
236 fprintf(stderr, "FAIL: retrieve %d expected %d observed %d @ %s:%d\n",
237 address, test_data[address], value, __FILE__, __LINE__);
238 return false;
239 }
240 #else // !GENERATE_TEST_DATA
241 printf(" %d%c%s // %d\n", value,
242 address == test_high - 1 ? ' ' : ',',
243 value < 10 ? " " : "",
244 address);
245 #endif // !GENERATE_TEST_DATA
246 }
247
248 #ifdef GENERATE_TEST_DATA
249 printf(" };\n");
250 #endif // GENERATE_TEST_DATA
251
252 return true;
253 }
254
255
256 } // namespace
257
258
main(int argc,char ** argv)259 int main(int argc, char **argv) {
260 BPLOG_INIT(&argc, &argv);
261
262 return RunTests() ? 0 : 1;
263 }
264