third_party/tcmalloc/chromium/src/tests/addressmap_unittest.cc

   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 }