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
42DEFINE_int32(iters, 20, "Number of test iterations");
43DEFINE_int32(N, 100000,  "Number of elements to test per iteration");
44
45using std::pair;
46using std::make_pair;
47using std::vector;
48using std::set;
49using std::random_shuffle;
50
51struct 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};
58static UniformRandomNumberGenerator rnd;
59
60
61// pair of associated value and object size
62typedef pair<int, size_t> ValueT;
63
64struct PtrAndSize {
65  char* ptr;
66  size_t size;
67  PtrAndSize(char* p, size_t s) : ptr(p), size(s) {}
68};
69
70size_t SizeFunc(const ValueT& v) { return v.second; }
71
72static 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
77int 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