12fc823f5794737391e231c1dce6c2b0793213e53mmentovai// Copyright (c) 2006, Google Inc. 22fc823f5794737391e231c1dce6c2b0793213e53mmentovai// All rights reserved. 32fc823f5794737391e231c1dce6c2b0793213e53mmentovai// 42fc823f5794737391e231c1dce6c2b0793213e53mmentovai// Redistribution and use in source and binary forms, with or without 52fc823f5794737391e231c1dce6c2b0793213e53mmentovai// modification, are permitted provided that the following conditions are 62fc823f5794737391e231c1dce6c2b0793213e53mmentovai// met: 72fc823f5794737391e231c1dce6c2b0793213e53mmentovai// 82fc823f5794737391e231c1dce6c2b0793213e53mmentovai// * Redistributions of source code must retain the above copyright 92fc823f5794737391e231c1dce6c2b0793213e53mmentovai// notice, this list of conditions and the following disclaimer. 102fc823f5794737391e231c1dce6c2b0793213e53mmentovai// * Redistributions in binary form must reproduce the above 112fc823f5794737391e231c1dce6c2b0793213e53mmentovai// copyright notice, this list of conditions and the following disclaimer 122fc823f5794737391e231c1dce6c2b0793213e53mmentovai// in the documentation and/or other materials provided with the 132fc823f5794737391e231c1dce6c2b0793213e53mmentovai// distribution. 142fc823f5794737391e231c1dce6c2b0793213e53mmentovai// * Neither the name of Google Inc. nor the names of its 152fc823f5794737391e231c1dce6c2b0793213e53mmentovai// contributors may be used to endorse or promote products derived from 162fc823f5794737391e231c1dce6c2b0793213e53mmentovai// this software without specific prior written permission. 172fc823f5794737391e231c1dce6c2b0793213e53mmentovai// 182fc823f5794737391e231c1dce6c2b0793213e53mmentovai// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 192fc823f5794737391e231c1dce6c2b0793213e53mmentovai// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 202fc823f5794737391e231c1dce6c2b0793213e53mmentovai// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 212fc823f5794737391e231c1dce6c2b0793213e53mmentovai// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 222fc823f5794737391e231c1dce6c2b0793213e53mmentovai// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 232fc823f5794737391e231c1dce6c2b0793213e53mmentovai// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 242fc823f5794737391e231c1dce6c2b0793213e53mmentovai// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 252fc823f5794737391e231c1dce6c2b0793213e53mmentovai// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 262fc823f5794737391e231c1dce6c2b0793213e53mmentovai// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 272fc823f5794737391e231c1dce6c2b0793213e53mmentovai// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 282fc823f5794737391e231c1dce6c2b0793213e53mmentovai// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 292fc823f5794737391e231c1dce6c2b0793213e53mmentovai 302fc823f5794737391e231c1dce6c2b0793213e53mmentovai// address_map_unittest.cc: Unit tests for AddressMap. 312fc823f5794737391e231c1dce6c2b0793213e53mmentovai// 322fc823f5794737391e231c1dce6c2b0793213e53mmentovai// Author: Mark Mentovai 332fc823f5794737391e231c1dce6c2b0793213e53mmentovai 34e1930985430ce289f4fe8525f51050e5d78cc44eted.mielczarek#include <limits.h> 35e1930985430ce289f4fe8525f51050e5d78cc44eted.mielczarek#include <stdio.h> 362fc823f5794737391e231c1dce6c2b0793213e53mmentovai 372fc823f5794737391e231c1dce6c2b0793213e53mmentovai#include "processor/address_map-inl.h" 382fc823f5794737391e231c1dce6c2b0793213e53mmentovai#include "processor/linked_ptr.h" 3932b802dba3d49880a0414d066e71cdc20ab09901mmentovai#include "processor/logging.h" 402fc823f5794737391e231c1dce6c2b0793213e53mmentovai 412fc823f5794737391e231c1dce6c2b0793213e53mmentovai#define ASSERT_TRUE(condition) \ 422fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (!(condition)) { \ 432fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \ 442fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; \ 452fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 462fc823f5794737391e231c1dce6c2b0793213e53mmentovai 472fc823f5794737391e231c1dce6c2b0793213e53mmentovai#define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition)) 482fc823f5794737391e231c1dce6c2b0793213e53mmentovai 492fc823f5794737391e231c1dce6c2b0793213e53mmentovai#define ASSERT_EQ(e1, e2) ASSERT_TRUE((e1) == (e2)) 502fc823f5794737391e231c1dce6c2b0793213e53mmentovai 518647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovainamespace { 528647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 53e5dc60822e5938fea2ae892ccddb906641ba174emmentovaiusing google_breakpad::AddressMap; 54e5dc60822e5938fea2ae892ccddb906641ba174emmentovaiusing google_breakpad::linked_ptr; 552fc823f5794737391e231c1dce6c2b0793213e53mmentovai 562fc823f5794737391e231c1dce6c2b0793213e53mmentovai// A CountedObject holds an int. A global (not thread safe!) count of 572fc823f5794737391e231c1dce6c2b0793213e53mmentovai// allocated CountedObjects is maintained to help test memory management. 582fc823f5794737391e231c1dce6c2b0793213e53mmentovaiclass CountedObject { 592fc823f5794737391e231c1dce6c2b0793213e53mmentovai public: 602fc823f5794737391e231c1dce6c2b0793213e53mmentovai explicit CountedObject(int id) : id_(id) { ++count_; } 612fc823f5794737391e231c1dce6c2b0793213e53mmentovai ~CountedObject() { --count_; } 622fc823f5794737391e231c1dce6c2b0793213e53mmentovai 632fc823f5794737391e231c1dce6c2b0793213e53mmentovai static int count() { return count_; } 642fc823f5794737391e231c1dce6c2b0793213e53mmentovai int id() const { return id_; } 652fc823f5794737391e231c1dce6c2b0793213e53mmentovai 662fc823f5794737391e231c1dce6c2b0793213e53mmentovai private: 672fc823f5794737391e231c1dce6c2b0793213e53mmentovai static int count_; 682fc823f5794737391e231c1dce6c2b0793213e53mmentovai int id_; 692fc823f5794737391e231c1dce6c2b0793213e53mmentovai}; 702fc823f5794737391e231c1dce6c2b0793213e53mmentovai 712fc823f5794737391e231c1dce6c2b0793213e53mmentovaiint CountedObject::count_; 722fc823f5794737391e231c1dce6c2b0793213e53mmentovai 732fc823f5794737391e231c1dce6c2b0793213e53mmentovaitypedef int AddressType; 742fc823f5794737391e231c1dce6c2b0793213e53mmentovaitypedef AddressMap< AddressType, linked_ptr<CountedObject> > TestMap; 752fc823f5794737391e231c1dce6c2b0793213e53mmentovai 762fc823f5794737391e231c1dce6c2b0793213e53mmentovaistatic bool DoAddressMapTest() { 772fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 0); 782fc823f5794737391e231c1dce6c2b0793213e53mmentovai 792fc823f5794737391e231c1dce6c2b0793213e53mmentovai TestMap test_map; 802fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject> entry; 812fc823f5794737391e231c1dce6c2b0793213e53mmentovai AddressType address; 822fc823f5794737391e231c1dce6c2b0793213e53mmentovai 832fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Check that a new map is truly empty. 842fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(0, &entry, &address)); 852fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address)); 862fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address)); 872fc823f5794737391e231c1dce6c2b0793213e53mmentovai 882fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Check that Clear clears the map without leaking. 892fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 0); 902fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(1, 912fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(0)))); 922fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Retrieve(1, &entry, &address)); 932fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 1); 942fc823f5794737391e231c1dce6c2b0793213e53mmentovai test_map.Clear(); 952fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 1); // still holding entry in this scope 962fc823f5794737391e231c1dce6c2b0793213e53mmentovai 972fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Check that a cleared map is truly empty. 982fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(0, &entry, &address)); 992fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address)); 1002fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address)); 1012fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1022fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Check a single-element map. 1032fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(10, 1042fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(1)))); 1052fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Retrieve(9, &entry, &address)); 1062fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Retrieve(10, &entry, &address)); 1072fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 1); 1082fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(entry->id(), 1); 1092fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(address, 10); 1102fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Retrieve(11, &entry, &address)); 1112fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Retrieve(11, &entry, NULL)); // NULL ok here 1122fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1132fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Add some more elements. 1142fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(5, 1152fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(2)))); 1162fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 2); 1172fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(20, 1182fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(3)))); 1192fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(15, 1202fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(4)))); 1212fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_FALSE(test_map.Store(10, 1222fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(5)))); // already in map 1232fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(16, 1242fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(6)))); 1252fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_TRUE(test_map.Store(14, 1262fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject>(new CountedObject(7)))); 1272fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1282fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Nothing was stored with a key under 5. Don't use ASSERT inside loops 1292fc823f5794737391e231c1dce6c2b0793213e53mmentovai // because it won't show exactly which key/entry/address failed. 1302fc823f5794737391e231c1dce6c2b0793213e53mmentovai for (AddressType key = 0; key < 5; ++key) { 1312fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (test_map.Retrieve(key, &entry, &address)) { 1322fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, 1332fc823f5794737391e231c1dce6c2b0793213e53mmentovai "FAIL: retrieve %d expected false observed true @ %s:%d\n", 1342fc823f5794737391e231c1dce6c2b0793213e53mmentovai key, __FILE__, __LINE__); 1352fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 1362fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 1372fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 1382fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1392fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Check everything that was stored. 1402fc823f5794737391e231c1dce6c2b0793213e53mmentovai const int id_verify[] = { 0, 0, 0, 0, 0, // unused 1412fc823f5794737391e231c1dce6c2b0793213e53mmentovai 2, 2, 2, 2, 2, // 5 - 9 1422fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1, 1, 1, 1, 7, // 10 - 14 1432fc823f5794737391e231c1dce6c2b0793213e53mmentovai 4, 6, 6, 6, 6, // 15 - 19 1442fc823f5794737391e231c1dce6c2b0793213e53mmentovai 3, 3, 3, 3, 3, // 20 - 24 1452fc823f5794737391e231c1dce6c2b0793213e53mmentovai 3, 3, 3, 3, 3 }; // 25 - 29 1462fc823f5794737391e231c1dce6c2b0793213e53mmentovai const AddressType address_verify[] = { 0, 0, 0, 0, 0, // unused 1472fc823f5794737391e231c1dce6c2b0793213e53mmentovai 5, 5, 5, 5, 5, // 5 - 9 1482fc823f5794737391e231c1dce6c2b0793213e53mmentovai 10, 10, 10, 10, 14, // 10 - 14 1492fc823f5794737391e231c1dce6c2b0793213e53mmentovai 15, 16, 16, 16, 16, // 15 - 19 1502fc823f5794737391e231c1dce6c2b0793213e53mmentovai 20, 20, 20, 20, 20, // 20 - 24 1512fc823f5794737391e231c1dce6c2b0793213e53mmentovai 20, 20, 20, 20, 20 }; // 25 - 29 1522fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1532fc823f5794737391e231c1dce6c2b0793213e53mmentovai for (AddressType key = 5; key < 30; ++key) { 1542fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (!test_map.Retrieve(key, &entry, &address)) { 1552fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, 1562fc823f5794737391e231c1dce6c2b0793213e53mmentovai "FAIL: retrieve %d expected true observed false @ %s:%d\n", 1572fc823f5794737391e231c1dce6c2b0793213e53mmentovai key, __FILE__, __LINE__); 1582fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 1592fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 1602fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (entry->id() != id_verify[key]) { 1612fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, 1622fc823f5794737391e231c1dce6c2b0793213e53mmentovai "FAIL: retrieve %d expected entry %d observed %d @ %s:%d\n", 1632fc823f5794737391e231c1dce6c2b0793213e53mmentovai key, id_verify[key], entry->id(), __FILE__, __LINE__); 1642fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 1652fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 1662fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (address != address_verify[key]) { 1672fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, 1682fc823f5794737391e231c1dce6c2b0793213e53mmentovai "FAIL: retrieve %d expected address %d observed %d @ %s:%d\n", 1692fc823f5794737391e231c1dce6c2b0793213e53mmentovai key, address_verify[key], address, __FILE__, __LINE__); 1702fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 1712fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 1722fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 1732fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1742fc823f5794737391e231c1dce6c2b0793213e53mmentovai // The stored objects should still be in the map. 1752fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 6); 1762fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1772fc823f5794737391e231c1dce6c2b0793213e53mmentovai return true; 1782fc823f5794737391e231c1dce6c2b0793213e53mmentovai} 1792fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1802fc823f5794737391e231c1dce6c2b0793213e53mmentovaistatic bool RunTests() { 1812fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (!DoAddressMapTest()) 1822fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 1832fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1842fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Leak check. 1852fc823f5794737391e231c1dce6c2b0793213e53mmentovai ASSERT_EQ(CountedObject::count(), 0); 1862fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1872fc823f5794737391e231c1dce6c2b0793213e53mmentovai return true; 1882fc823f5794737391e231c1dce6c2b0793213e53mmentovai} 1892fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1908647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai} // namespace 1918647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 1922fc823f5794737391e231c1dce6c2b0793213e53mmentovaiint main(int argc, char **argv) { 19332b802dba3d49880a0414d066e71cdc20ab09901mmentovai BPLOG_INIT(&argc, &argv); 19432b802dba3d49880a0414d066e71cdc20ab09901mmentovai 1952fc823f5794737391e231c1dce6c2b0793213e53mmentovai return RunTests() ? 0 : 1; 1962fc823f5794737391e231c1dce6c2b0793213e53mmentovai} 197