1 // Copyright 2006 Google LLC
2 //
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
5 // met:
6 //
7 // * Redistributions of source code must retain the above copyright
8 // notice, this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above
10 // copyright notice, this list of conditions and the following disclaimer
11 // in the documentation and/or other materials provided with the
12 // distribution.
13 // * Neither the name of Google LLC nor the names of its
14 // contributors may be used to endorse or promote products derived from
15 // this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 // address_map_unittest.cc: Unit tests for AddressMap.
30 //
31 // Author: Mark Mentovai
32
33 #ifdef HAVE_CONFIG_H
34 #include <config.h> // Must come first
35 #endif
36
37 #include <limits.h>
38 #include <stdio.h>
39
40 #include "processor/address_map-inl.h"
41 #include "processor/linked_ptr.h"
42 #include "processor/logging.h"
43
44 #define ASSERT_TRUE(condition) \
45 if (!(condition)) { \
46 fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \
47 return false; \
48 }
49
50 #define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition))
51
52 #define ASSERT_EQ(e1, e2) ASSERT_TRUE((e1) == (e2))
53
54 namespace {
55
56 using google_breakpad::AddressMap;
57 using google_breakpad::linked_ptr;
58
59 // A CountedObject holds an int. A global (not thread safe!) count of
60 // allocated CountedObjects is maintained to help test memory management.
61 class CountedObject {
62 public:
CountedObject(int id)63 explicit CountedObject(int id) : id_(id) { ++count_; }
~CountedObject()64 ~CountedObject() { --count_; }
65
count()66 static int count() { return count_; }
id() const67 int id() const { return id_; }
68
69 private:
70 static int count_;
71 int id_;
72 };
73
74 int CountedObject::count_;
75
76 typedef int AddressType;
77 typedef AddressMap< AddressType, linked_ptr<CountedObject> > TestMap;
78
DoAddressMapTest()79 static bool DoAddressMapTest() {
80 ASSERT_EQ(CountedObject::count(), 0);
81
82 TestMap test_map;
83 linked_ptr<CountedObject> entry;
84 AddressType address;
85
86 // Check that a new map is truly empty.
87 ASSERT_FALSE(test_map.Retrieve(0, &entry, &address));
88 ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address));
89 ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address));
90
91 // Check that Clear clears the map without leaking.
92 ASSERT_EQ(CountedObject::count(), 0);
93 ASSERT_TRUE(test_map.Store(1,
94 linked_ptr<CountedObject>(new CountedObject(0))));
95 ASSERT_TRUE(test_map.Retrieve(1, &entry, &address));
96 ASSERT_EQ(CountedObject::count(), 1);
97 test_map.Clear();
98 ASSERT_EQ(CountedObject::count(), 1); // still holding entry in this scope
99
100 // Check that a cleared map is truly empty.
101 ASSERT_FALSE(test_map.Retrieve(0, &entry, &address));
102 ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address));
103 ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address));
104
105 // Check a single-element map.
106 ASSERT_TRUE(test_map.Store(10,
107 linked_ptr<CountedObject>(new CountedObject(1))));
108 ASSERT_FALSE(test_map.Retrieve(9, &entry, &address));
109 ASSERT_TRUE(test_map.Retrieve(10, &entry, &address));
110 ASSERT_EQ(CountedObject::count(), 1);
111 ASSERT_EQ(entry->id(), 1);
112 ASSERT_EQ(address, 10);
113 ASSERT_TRUE(test_map.Retrieve(11, &entry, &address));
114 ASSERT_TRUE(test_map.Retrieve(11, &entry, NULL)); // NULL ok here
115
116 // Add some more elements.
117 ASSERT_TRUE(test_map.Store(5,
118 linked_ptr<CountedObject>(new CountedObject(2))));
119 ASSERT_EQ(CountedObject::count(), 2);
120 ASSERT_TRUE(test_map.Store(20,
121 linked_ptr<CountedObject>(new CountedObject(3))));
122 ASSERT_TRUE(test_map.Store(15,
123 linked_ptr<CountedObject>(new CountedObject(4))));
124 ASSERT_FALSE(test_map.Store(10,
125 linked_ptr<CountedObject>(new CountedObject(5)))); // already in map
126 ASSERT_TRUE(test_map.Store(16,
127 linked_ptr<CountedObject>(new CountedObject(6))));
128 ASSERT_TRUE(test_map.Store(14,
129 linked_ptr<CountedObject>(new CountedObject(7))));
130
131 // Nothing was stored with a key under 5. Don't use ASSERT inside loops
132 // because it won't show exactly which key/entry/address failed.
133 for (AddressType key = 0; key < 5; ++key) {
134 if (test_map.Retrieve(key, &entry, &address)) {
135 fprintf(stderr,
136 "FAIL: retrieve %d expected false observed true @ %s:%d\n",
137 key, __FILE__, __LINE__);
138 return false;
139 }
140 }
141
142 // Check everything that was stored.
143 const int id_verify[] = { 0, 0, 0, 0, 0, // unused
144 2, 2, 2, 2, 2, // 5 - 9
145 1, 1, 1, 1, 7, // 10 - 14
146 4, 6, 6, 6, 6, // 15 - 19
147 3, 3, 3, 3, 3, // 20 - 24
148 3, 3, 3, 3, 3 }; // 25 - 29
149 const AddressType address_verify[] = { 0, 0, 0, 0, 0, // unused
150 5, 5, 5, 5, 5, // 5 - 9
151 10, 10, 10, 10, 14, // 10 - 14
152 15, 16, 16, 16, 16, // 15 - 19
153 20, 20, 20, 20, 20, // 20 - 24
154 20, 20, 20, 20, 20 }; // 25 - 29
155
156 for (AddressType key = 5; key < 30; ++key) {
157 if (!test_map.Retrieve(key, &entry, &address)) {
158 fprintf(stderr,
159 "FAIL: retrieve %d expected true observed false @ %s:%d\n",
160 key, __FILE__, __LINE__);
161 return false;
162 }
163 if (entry->id() != id_verify[key]) {
164 fprintf(stderr,
165 "FAIL: retrieve %d expected entry %d observed %d @ %s:%d\n",
166 key, id_verify[key], entry->id(), __FILE__, __LINE__);
167 return false;
168 }
169 if (address != address_verify[key]) {
170 fprintf(stderr,
171 "FAIL: retrieve %d expected address %d observed %d @ %s:%d\n",
172 key, address_verify[key], address, __FILE__, __LINE__);
173 return false;
174 }
175 }
176
177 // The stored objects should still be in the map.
178 ASSERT_EQ(CountedObject::count(), 6);
179
180 return true;
181 }
182
RunTests()183 static bool RunTests() {
184 if (!DoAddressMapTest())
185 return false;
186
187 // Leak check.
188 ASSERT_EQ(CountedObject::count(), 0);
189
190 return true;
191 }
192
193 } // namespace
194
main(int argc,char ** argv)195 int main(int argc, char** argv) {
196 BPLOG_INIT(&argc, &argv);
197
198 return RunTests() ? 0 : 1;
199 }
200