1// Copyright (c) 2010, 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// static_contained_range_map_unittest.cc: Unit tests for
31// StaticContainedRangeMap.
32//
33// Author: Siyang Xie (lambxsy@google.com)
34
35#include "breakpad_googletest_includes.h"
36#include "common/scoped_ptr.h"
37#include "processor/contained_range_map-inl.h"
38#include "processor/static_contained_range_map-inl.h"
39#include "processor/simple_serializer-inl.h"
40#include "processor/map_serializers-inl.h"
41#include "processor/logging.h"
42
43namespace {
44
45typedef google_breakpad::ContainedRangeMap<unsigned int, int> CRMMap;
46typedef google_breakpad::StaticContainedRangeMap<unsigned int, int> TestMap;
47
48// Each element in test_data contains the expected result when calling
49// RetrieveRange on an address.
50const int test_data[] = {
51  0,   // 0
52  0,   // 1
53  0,   // 2
54  0,   // 3
55  0,   // 4
56  0,   // 5
57  0,   // 6
58  0,   // 7
59  9,   // 8
60  7,   // 9
61  1,   // 10
62  5,   // 11
63  6,   // 12
64  6,   // 13
65  6,   // 14
66  6,   // 15
67  6,   // 16
68  6,   // 17
69  6,   // 18
70  5,   // 19
71  7,   // 20
72  8,   // 21
73  0,   // 22
74  0,   // 23
75  0,   // 24
76  0,   // 25
77  0,   // 26
78  0,   // 27
79  0,   // 28
80  0,   // 29
81  10,  // 30
82  10,  // 31
83  10,  // 32
84  11,  // 33
85  11,  // 34
86  11,  // 35
87  0,   // 36
88  0,   // 37
89  0,   // 38
90  0,   // 39
91  14,  // 40
92  14,  // 41
93  14,  // 42
94  14,  // 43
95  15,  // 44
96  15,  // 45
97  15,  // 46
98  15,  // 47
99  0,   // 48
100  0,   // 49
101  19,  // 50
102  18,  // 51
103  18,  // 52
104  18,  // 53
105  18,  // 54
106  18,  // 55
107  18,  // 56
108  18,  // 57
109  18,  // 58
110  20,  // 59
111  21,  // 60
112  25,  // 61
113  26,  // 62
114  26,  // 63
115  26,  // 64
116  26,  // 65
117  26,  // 66
118  26,  // 67
119  24,  // 68
120  22,  // 69
121  30,  // 70
122  30,  // 71
123  30,  // 72
124  30,  // 73
125  31,  // 74
126  31,  // 75
127  30,  // 76
128  32,  // 77
129  32,  // 78
130  30,  // 79
131  34,  // 80
132  35,  // 81
133  36,  // 82
134  39,  // 83
135  38,  // 84
136  37,  // 85
137  43,  // 86
138  44,  // 87
139  41,  // 88
140  45,  // 89
141  42,  // 90
142  0,   // 91
143  0,   // 92
144  0,   // 93
145  0,   // 94
146  0,   // 95
147  0,   // 96
148  0,   // 97
149  0,   // 98
150  0    // 99
151};
152
153}  // namespace
154
155namespace google_breakpad {
156
157class TestStaticCRMMap : public ::testing::Test {
158 protected:
159  void SetUp();
160
161  // A referrence map for testing StaticCRMMap.
162  google_breakpad::ContainedRangeMap<unsigned int, int> crm_map_;
163
164  // Static version of crm_map using serialized data of crm_map.
165  // The goal of testing is to make sure TestMap provides same results for
166  // lookup operation(s) as CRMMap does.
167  google_breakpad::StaticContainedRangeMap<unsigned int, int> test_map_;
168
169  google_breakpad::ContainedRangeMapSerializer<unsigned int, int> serializer_;
170
171  scoped_array<char> serialized_data_;
172};
173
174void TestStaticCRMMap::SetUp() {
175  // First, do the StoreRange tests.  This validates the containment
176  // rules.
177  // We confirm the referrence map correctly stores data during setup.
178  ASSERT_TRUE (crm_map_.StoreRange(10, 10,  1));
179  ASSERT_FALSE(crm_map_.StoreRange(10, 10,  2));  // exactly equal to 1
180  ASSERT_FALSE(crm_map_.StoreRange(11, 10,  3));  // begins inside 1 and extends up
181  ASSERT_FALSE(crm_map_.StoreRange( 9, 10,  4));  // begins below 1 and ends inside
182  ASSERT_TRUE (crm_map_.StoreRange(11,  9,  5));  // contained by existing
183  ASSERT_TRUE (crm_map_.StoreRange(12,  7,  6));
184  ASSERT_TRUE (crm_map_.StoreRange( 9, 12,  7));  // contains existing
185  ASSERT_TRUE (crm_map_.StoreRange( 9, 13,  8));
186  ASSERT_TRUE (crm_map_.StoreRange( 8, 14,  9));
187  ASSERT_TRUE (crm_map_.StoreRange(30,  3, 10));
188  ASSERT_TRUE (crm_map_.StoreRange(33,  3, 11));
189  ASSERT_TRUE (crm_map_.StoreRange(30,  6, 12));  // storable but totally masked
190  ASSERT_TRUE (crm_map_.StoreRange(40,  8, 13));  // will be totally masked
191  ASSERT_TRUE (crm_map_.StoreRange(40,  4, 14));
192  ASSERT_TRUE (crm_map_.StoreRange(44,  4, 15));
193  ASSERT_FALSE(crm_map_.StoreRange(32, 10, 16));  // begins in #10, ends in #14
194  ASSERT_FALSE(crm_map_.StoreRange(50,  0, 17));  // zero length
195  ASSERT_TRUE (crm_map_.StoreRange(50, 10, 18));
196  ASSERT_TRUE (crm_map_.StoreRange(50,  1, 19));
197  ASSERT_TRUE (crm_map_.StoreRange(59,  1, 20));
198  ASSERT_TRUE (crm_map_.StoreRange(60,  1, 21));
199  ASSERT_TRUE (crm_map_.StoreRange(69,  1, 22));
200  ASSERT_TRUE (crm_map_.StoreRange(60, 10, 23));
201  ASSERT_TRUE (crm_map_.StoreRange(68,  1, 24));
202  ASSERT_TRUE (crm_map_.StoreRange(61,  1, 25));
203  ASSERT_TRUE (crm_map_.StoreRange(61,  8, 26));
204  ASSERT_FALSE(crm_map_.StoreRange(59,  9, 27));
205  ASSERT_FALSE(crm_map_.StoreRange(59, 10, 28));
206  ASSERT_FALSE(crm_map_.StoreRange(59, 11, 29));
207  ASSERT_TRUE (crm_map_.StoreRange(70, 10, 30));
208  ASSERT_TRUE (crm_map_.StoreRange(74,  2, 31));
209  ASSERT_TRUE (crm_map_.StoreRange(77,  2, 32));
210  ASSERT_FALSE(crm_map_.StoreRange(72,  6, 33));
211  ASSERT_TRUE (crm_map_.StoreRange(80,  3, 34));
212  ASSERT_TRUE (crm_map_.StoreRange(81,  1, 35));
213  ASSERT_TRUE (crm_map_.StoreRange(82,  1, 36));
214  ASSERT_TRUE (crm_map_.StoreRange(83,  3, 37));
215  ASSERT_TRUE (crm_map_.StoreRange(84,  1, 38));
216  ASSERT_TRUE (crm_map_.StoreRange(83,  1, 39));
217  ASSERT_TRUE (crm_map_.StoreRange(86,  5, 40));
218  ASSERT_TRUE (crm_map_.StoreRange(88,  1, 41));
219  ASSERT_TRUE (crm_map_.StoreRange(90,  1, 42));
220  ASSERT_TRUE (crm_map_.StoreRange(86,  1, 43));
221  ASSERT_TRUE (crm_map_.StoreRange(87,  1, 44));
222  ASSERT_TRUE (crm_map_.StoreRange(89,  1, 45));
223  ASSERT_TRUE (crm_map_.StoreRange(87,  4, 46));
224  ASSERT_TRUE (crm_map_.StoreRange(87,  3, 47));
225  ASSERT_FALSE(crm_map_.StoreRange(86,  2, 48));
226
227  // Serialize crm_map to generate serialized data.
228  unsigned int size;
229  serialized_data_.reset(serializer_.Serialize(&crm_map_, &size));
230  BPLOG(INFO) << "Serialized data size: " << size << " Bytes.";
231
232  // Construct test_map_ from serialized data.
233  test_map_ = TestMap(serialized_data_.get());
234}
235
236TEST_F(TestStaticCRMMap, TestEmptyMap) {
237  CRMMap empty_crm_map;
238
239  unsigned int size;
240  scoped_array<char> serialized_data;
241  serialized_data.reset(serializer_.Serialize(&empty_crm_map, &size));
242  scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
243
244  const unsigned int kCorrectSizeForEmptyMap = 16;
245  ASSERT_EQ(kCorrectSizeForEmptyMap, size);
246
247  const int *entry_test;
248  ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test));
249  ASSERT_FALSE(test_map->RetrieveRange(0, entry_test));
250  ASSERT_FALSE(test_map->RetrieveRange(10, entry_test));
251}
252
253TEST_F(TestStaticCRMMap, TestSingleElementMap) {
254  CRMMap crm_map;
255  // Test on one element:
256  int entry = 1;
257  crm_map.StoreRange(10, 10,  entry);
258
259  unsigned int size;
260  scoped_array<char> serialized_data;
261  serialized_data.reset(serializer_.Serialize(&crm_map, &size));
262  scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get()));
263
264  const unsigned int kCorrectSizeForSingleElementMap = 40;
265  ASSERT_EQ(kCorrectSizeForSingleElementMap, size);
266
267  const int *entry_test;
268  ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test));
269  ASSERT_FALSE(test_map->RetrieveRange(0, entry_test));
270  ASSERT_TRUE(test_map->RetrieveRange(10, entry_test));
271  ASSERT_EQ(*entry_test, entry);
272  ASSERT_TRUE(test_map->RetrieveRange(13, entry_test));
273  ASSERT_EQ(*entry_test, entry);
274}
275
276TEST_F(TestStaticCRMMap, RunTestData) {
277  unsigned int test_high = sizeof(test_data) / sizeof(test_data[0]);
278
279  // Now, do the RetrieveRange tests.  This further validates that the
280  // objects were stored properly and that retrieval returns the correct
281  // object.
282  // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
283  // new test_data array will be printed.  Exercise caution when doing this.
284  // Be sure to verify the results manually!
285#ifdef GENERATE_TEST_DATA
286  printf("  const int test_data[] = {\n");
287#endif  // GENERATE_TEST_DATA
288
289  for (unsigned int address = 0; address < test_high; ++address) {
290    const int *entryptr;
291    int value = 0;
292    if (test_map_.RetrieveRange(address, entryptr))
293      value = *entryptr;
294
295#ifndef GENERATE_TEST_DATA
296    // Don't use ASSERT inside the loop because it won't show the failed
297    // |address|, and the line number will always be the same.  That makes
298    // it difficult to figure out which test failed.
299    EXPECT_EQ(value, test_data[address]) << "FAIL: retrieve address "
300                                         << address;
301#else  // !GENERATE_TEST_DATA
302    printf("    %d%c%s  // %d\n", value,
303                                  address == test_high - 1 ? ' ' : ',',
304                                  value < 10 ? " " : "",
305                                  address);
306#endif  // !GENERATE_TEST_DATA
307  }
308
309#ifdef GENERATE_TEST_DATA
310  printf("  };\n");
311#endif  // GENERATE_TEST_DATA
312}
313
314}  // namespace google_breakpad
315
316int main(int argc, char *argv[]) {
317  ::testing::InitGoogleTest(&argc, argv);
318
319  return RUN_ALL_TESTS();
320}
321