15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2005, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Sanjay Ghemawat 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h> // for rand() 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set> 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <utility> 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "addressmap-inl.h" 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/commandlineflags.h" 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DEFINE_int32(iters, 20, "Number of test iterations"); 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DEFINE_int32(N, 100000, "Number of elements to test per iteration"); 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::pair; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::make_pair; 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::vector; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::set; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::random_shuffle; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct UniformRandomNumberGenerator { 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t Uniform(size_t max_size) { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (max_size == 0) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return rand() % max_size; // not a great random-number fn, but portable 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static UniformRandomNumberGenerator rnd; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pair of associated value and object size 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef pair<int, size_t> ValueT; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct PtrAndSize { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* ptr; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t size; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PtrAndSize(char* p, size_t s) : ptr(p), size(s) {} 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t SizeFunc(const ValueT& v) { return v.second; } 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void SetCheckCallback(const void* ptr, ValueT* val, 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) set<pair<const void*, int> >* check_set) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) check_set->insert(make_pair(ptr, val->first)); 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int main(int argc, char** argv) { 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get a bunch of pointers 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int N = FLAGS_N; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kMaxRealSize = 49; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 100Mb to stress not finding previous object (AddressMap's cluster is 1Mb): 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const size_t kMaxSize = 100*1000*1000; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<PtrAndSize> ptrs_and_sizes; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < N; ++i) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t s = rnd.Uniform(kMaxRealSize); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptrs_and_sizes.push_back(PtrAndSize(new char[s], s)); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int x = 0; x < FLAGS_iters; ++x) { 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_LOG(INFO, "Iteration %d/%d...\n", x, FLAGS_iters); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Permute pointers to get rid of allocation order issues 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) random_shuffle(ptrs_and_sizes.begin(), ptrs_and_sizes.end()); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddressMap<ValueT> map(malloc, free); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ValueT* result; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const void* res_p; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert a bunch of entries 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < N; ++i) { 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* p = ptrs_and_sizes[i].ptr; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(!map.Find(p)); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int offs = rnd.Uniform(ptrs_and_sizes[i].size); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(!map.FindInside(&SizeFunc, kMaxSize, p + offs, &res_p)); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map.Insert(p, make_pair(i, ptrs_and_sizes[i].size)); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.Find(p)); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(res_p, p); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map.Insert(p, make_pair(i + N, ptrs_and_sizes[i].size)); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.Find(p)); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + N); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Delete the even entries 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < N; i += 2) { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* p = ptrs_and_sizes[i].ptr; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ValueT removed; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(map.FindAndRemove(p, &removed)); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(removed.first, i + N); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Lookup the odd entries and adjust them 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i < N; i += 2) { 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* p = ptrs_and_sizes[i].ptr; 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.Find(p)); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + N); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int offs = rnd.Uniform(ptrs_and_sizes[i].size); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(res_p, p); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + N); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map.Insert(p, make_pair(i + 2*N, ptrs_and_sizes[i].size)); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.Find(p)); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + 2*N); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert even entries back 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < N; i += 2) { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* p = ptrs_and_sizes[i].ptr; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int offs = rnd.Uniform(ptrs_and_sizes[i].size); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(!map.FindInside(&SizeFunc, kMaxSize, p + offs, &res_p)); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map.Insert(p, make_pair(i + 2*N, ptrs_and_sizes[i].size)); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.Find(p)); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + 2*N); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(res_p, p); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + 2*N); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check all entries 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) set<pair<const void*, int> > check_set; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map.Iterate(SetCheckCallback, &check_set); 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(check_set.size(), N); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < N; ++i) { 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* p = ptrs_and_sizes[i].ptr; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) check_set.erase(make_pair(p, i + 2*N)); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(result = map.Find(p)); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(result->first, i + 2*N); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(check_set.size(), 0); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < N; ++i) { 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete[] ptrs_and_sizes[i].ptr; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("PASS\n"); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 171