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
50namespace {
51
52
53using google_breakpad::ContainedRangeMap;
54
55
56static 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
259int main(int argc, char **argv) {
260  BPLOG_INIT(&argc, &argv);
261
262  return RunTests() ? 0 : 1;
263}
264