1 // Copyright (c) 2005, 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 // --- 31 // Author: Sanjay Ghemawat 32 33 #include <stdlib.h> // for rand() 34 #include <vector> 35 #include <set> 36 #include <algorithm> 37 #include <utility> 38 #include "addressmap-inl.h" 39 #include "base/logging.h" 40 #include "base/commandlineflags.h" 41 42 DEFINE_int32(iters, 20, "Number of test iterations"); 43 DEFINE_int32(N, 100000, "Number of elements to test per iteration"); 44 45 using std::pair; 46 using std::make_pair; 47 using std::vector; 48 using std::set; 49 using std::random_shuffle; 50 51 struct UniformRandomNumberGenerator { 52 size_t Uniform(size_t max_size) { 53 if (max_size == 0) 54 return 0; 55 return rand() % max_size; // not a great random-number fn, but portable 56 } 57 }; 58 static UniformRandomNumberGenerator rnd; 59 60 61 // pair of associated value and object size 62 typedef pair<int, size_t> ValueT; 63 64 struct PtrAndSize { 65 char* ptr; 66 size_t size; 67 PtrAndSize(char* p, size_t s) : ptr(p), size(s) {} 68 }; 69 70 size_t SizeFunc(const ValueT& v) { return v.second; } 71 72 static void SetCheckCallback(const void* ptr, ValueT* val, 73 set<pair<const void*, int> >* check_set) { 74 check_set->insert(make_pair(ptr, val->first)); 75 } 76 77 int main(int argc, char** argv) { 78 // Get a bunch of pointers 79 const int N = FLAGS_N; 80 static const int kMaxRealSize = 49; 81 // 100Mb to stress not finding previous object (AddressMap's cluster is 1Mb): 82 static const size_t kMaxSize = 100*1000*1000; 83 vector<PtrAndSize> ptrs_and_sizes; 84 for (int i = 0; i < N; ++i) { 85 size_t s = rnd.Uniform(kMaxRealSize); 86 ptrs_and_sizes.push_back(PtrAndSize(new char[s], s)); 87 } 88 89 for (int x = 0; x < FLAGS_iters; ++x) { 90 RAW_LOG(INFO, "Iteration %d/%d...\n", x, FLAGS_iters); 91 92 // Permute pointers to get rid of allocation order issues 93 random_shuffle(ptrs_and_sizes.begin(), ptrs_and_sizes.end()); 94 95 AddressMap<ValueT> map(malloc, free); 96 const ValueT* result; 97 const void* res_p; 98 99 // Insert a bunch of entries 100 for (int i = 0; i < N; ++i) { 101 char* p = ptrs_and_sizes[i].ptr; 102 CHECK(!map.Find(p)); 103 int offs = rnd.Uniform(ptrs_and_sizes[i].size); 104 CHECK(!map.FindInside(&SizeFunc, kMaxSize, p + offs, &res_p)); 105 map.Insert(p, make_pair(i, ptrs_and_sizes[i].size)); 106 CHECK(result = map.Find(p)); 107 CHECK_EQ(result->first, i); 108 CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); 109 CHECK_EQ(res_p, p); 110 CHECK_EQ(result->first, i); 111 map.Insert(p, make_pair(i + N, ptrs_and_sizes[i].size)); 112 CHECK(result = map.Find(p)); 113 CHECK_EQ(result->first, i + N); 114 } 115 116 // Delete the even entries 117 for (int i = 0; i < N; i += 2) { 118 void* p = ptrs_and_sizes[i].ptr; 119 ValueT removed; 120 CHECK(map.FindAndRemove(p, &removed)); 121 CHECK_EQ(removed.first, i + N); 122 } 123 124 // Lookup the odd entries and adjust them 125 for (int i = 1; i < N; i += 2) { 126 char* p = ptrs_and_sizes[i].ptr; 127 CHECK(result = map.Find(p)); 128 CHECK_EQ(result->first, i + N); 129 int offs = rnd.Uniform(ptrs_and_sizes[i].size); 130 CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); 131 CHECK_EQ(res_p, p); 132 CHECK_EQ(result->first, i + N); 133 map.Insert(p, make_pair(i + 2*N, ptrs_and_sizes[i].size)); 134 CHECK(result = map.Find(p)); 135 CHECK_EQ(result->first, i + 2*N); 136 } 137 138 // Insert even entries back 139 for (int i = 0; i < N; i += 2) { 140 char* p = ptrs_and_sizes[i].ptr; 141 int offs = rnd.Uniform(ptrs_and_sizes[i].size); 142 CHECK(!map.FindInside(&SizeFunc, kMaxSize, p + offs, &res_p)); 143 map.Insert(p, make_pair(i + 2*N, ptrs_and_sizes[i].size)); 144 CHECK(result = map.Find(p)); 145 CHECK_EQ(result->first, i + 2*N); 146 CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); 147 CHECK_EQ(res_p, p); 148 CHECK_EQ(result->first, i + 2*N); 149 } 150 151 // Check all entries 152 set<pair<const void*, int> > check_set; 153 map.Iterate(SetCheckCallback, &check_set); 154 CHECK_EQ(check_set.size(), N); 155 for (int i = 0; i < N; ++i) { 156 void* p = ptrs_and_sizes[i].ptr; 157 check_set.erase(make_pair(p, i + 2*N)); 158 CHECK(result = map.Find(p)); 159 CHECK_EQ(result->first, i + 2*N); 160 } 161 CHECK_EQ(check_set.size(), 0); 162 } 163 164 for (int i = 0; i < N; ++i) { 165 delete[] ptrs_and_sizes[i].ptr; 166 } 167 168 printf("PASS\n"); 169 return 0; 170 } 171
