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// address_map_unittest.cc: Unit tests for AddressMap.
31//
32// Author: Mark Mentovai
33
34#include <limits.h>
35#include <stdio.h>
36
37#include "processor/address_map-inl.h"
38#include "processor/linked_ptr.h"
39#include "processor/logging.h"
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#define ASSERT_EQ(e1, e2) ASSERT_TRUE((e1) == (e2))
50
51namespace {
52
53using google_breakpad::AddressMap;
54using google_breakpad::linked_ptr;
55
56// A CountedObject holds an int.  A global (not thread safe!) count of
57// allocated CountedObjects is maintained to help test memory management.
58class CountedObject {
59 public:
60  explicit CountedObject(int id) : id_(id) { ++count_; }
61  ~CountedObject() { --count_; }
62
63  static int count() { return count_; }
64  int id() const { return id_; }
65
66 private:
67  static int count_;
68  int id_;
69};
70
71int CountedObject::count_;
72
73typedef int AddressType;
74typedef AddressMap< AddressType, linked_ptr<CountedObject> > TestMap;
75
76static bool DoAddressMapTest() {
77  ASSERT_EQ(CountedObject::count(), 0);
78
79  TestMap test_map;
80  linked_ptr<CountedObject> entry;
81  AddressType address;
82
83  // Check that a new map is truly empty.
84  ASSERT_FALSE(test_map.Retrieve(0, &entry, &address));
85  ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address));
86  ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address));
87
88  // Check that Clear clears the map without leaking.
89  ASSERT_EQ(CountedObject::count(), 0);
90  ASSERT_TRUE(test_map.Store(1,
91      linked_ptr<CountedObject>(new CountedObject(0))));
92  ASSERT_TRUE(test_map.Retrieve(1, &entry, &address));
93  ASSERT_EQ(CountedObject::count(), 1);
94  test_map.Clear();
95  ASSERT_EQ(CountedObject::count(), 1);  // still holding entry in this scope
96
97  // Check that a cleared map is truly empty.
98  ASSERT_FALSE(test_map.Retrieve(0, &entry, &address));
99  ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address));
100  ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address));
101
102  // Check a single-element map.
103  ASSERT_TRUE(test_map.Store(10,
104      linked_ptr<CountedObject>(new CountedObject(1))));
105  ASSERT_FALSE(test_map.Retrieve(9, &entry, &address));
106  ASSERT_TRUE(test_map.Retrieve(10, &entry, &address));
107  ASSERT_EQ(CountedObject::count(), 1);
108  ASSERT_EQ(entry->id(), 1);
109  ASSERT_EQ(address, 10);
110  ASSERT_TRUE(test_map.Retrieve(11, &entry, &address));
111  ASSERT_TRUE(test_map.Retrieve(11, &entry, NULL));     // NULL ok here
112
113  // Add some more elements.
114  ASSERT_TRUE(test_map.Store(5,
115      linked_ptr<CountedObject>(new CountedObject(2))));
116  ASSERT_EQ(CountedObject::count(), 2);
117  ASSERT_TRUE(test_map.Store(20,
118      linked_ptr<CountedObject>(new CountedObject(3))));
119  ASSERT_TRUE(test_map.Store(15,
120      linked_ptr<CountedObject>(new CountedObject(4))));
121  ASSERT_FALSE(test_map.Store(10,
122      linked_ptr<CountedObject>(new CountedObject(5))));  // already in map
123  ASSERT_TRUE(test_map.Store(16,
124      linked_ptr<CountedObject>(new CountedObject(6))));
125  ASSERT_TRUE(test_map.Store(14,
126      linked_ptr<CountedObject>(new CountedObject(7))));
127
128  // Nothing was stored with a key under 5.  Don't use ASSERT inside loops
129  // because it won't show exactly which key/entry/address failed.
130  for (AddressType key = 0; key < 5; ++key) {
131    if (test_map.Retrieve(key, &entry, &address)) {
132      fprintf(stderr,
133              "FAIL: retrieve %d expected false observed true @ %s:%d\n",
134              key, __FILE__, __LINE__);
135      return false;
136    }
137  }
138
139  // Check everything that was stored.
140  const int id_verify[] = { 0, 0, 0, 0, 0,    // unused
141                            2, 2, 2, 2, 2,    // 5 - 9
142                            1, 1, 1, 1, 7,    // 10 - 14
143                            4, 6, 6, 6, 6,    // 15 - 19
144                            3, 3, 3, 3, 3,    // 20 - 24
145                            3, 3, 3, 3, 3 };  // 25 - 29
146  const AddressType address_verify[] = {  0,  0,  0,  0,  0,    // unused
147                                          5,  5,  5,  5,  5,    // 5 - 9
148                                         10, 10, 10, 10, 14,    // 10 - 14
149                                         15, 16, 16, 16, 16,    // 15 - 19
150                                         20, 20, 20, 20, 20,    // 20 - 24
151                                         20, 20, 20, 20, 20 };  // 25 - 29
152
153  for (AddressType key = 5; key < 30; ++key) {
154    if (!test_map.Retrieve(key, &entry, &address)) {
155      fprintf(stderr,
156              "FAIL: retrieve %d expected true observed false @ %s:%d\n",
157              key, __FILE__, __LINE__);
158      return false;
159    }
160    if (entry->id() != id_verify[key]) {
161      fprintf(stderr,
162              "FAIL: retrieve %d expected entry %d observed %d @ %s:%d\n",
163              key, id_verify[key], entry->id(), __FILE__, __LINE__);
164      return false;
165    }
166    if (address != address_verify[key]) {
167      fprintf(stderr,
168              "FAIL: retrieve %d expected address %d observed %d @ %s:%d\n",
169              key, address_verify[key], address, __FILE__, __LINE__);
170      return false;
171    }
172  }
173
174  // The stored objects should still be in the map.
175  ASSERT_EQ(CountedObject::count(), 6);
176
177  return true;
178}
179
180static bool RunTests() {
181  if (!DoAddressMapTest())
182    return false;
183
184  // Leak check.
185  ASSERT_EQ(CountedObject::count(), 0);
186
187  return true;
188}
189
190}  // namespace
191
192int main(int argc, char **argv) {
193  BPLOG_INIT(&argc, &argv);
194
195  return RunTests() ? 0 : 1;
196}
197