| // -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- |
| // Copyright (c) 2005, Google Inc. |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following disclaimer |
| // in the documentation and/or other materials provided with the |
| // distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived from |
| // this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| // --- |
| // Author: Sanjay Ghemawat |
| |
| #include <stdlib.h> // for rand() |
| #include <vector> |
| #include <set> |
| #include <algorithm> |
| #include <utility> |
| #include "addressmap-inl.h" |
| #include "base/logging.h" |
| #include "base/commandlineflags.h" |
| |
| DEFINE_int32(iters, 20, "Number of test iterations"); |
| DEFINE_int32(N, 100000, "Number of elements to test per iteration"); |
| |
| using std::pair; |
| using std::make_pair; |
| using std::vector; |
| using std::set; |
| using std::random_shuffle; |
| |
| struct UniformRandomNumberGenerator { |
| size_t Uniform(size_t max_size) { |
| if (max_size == 0) |
| return 0; |
| return rand() % max_size; // not a great random-number fn, but portable |
| } |
| }; |
| static UniformRandomNumberGenerator rnd; |
| |
| |
| // pair of associated value and object size |
| typedef pair<int, size_t> ValueT; |
| |
| struct PtrAndSize { |
| char* ptr; |
| size_t size; |
| PtrAndSize(char* p, size_t s) : ptr(p), size(s) {} |
| }; |
| |
| size_t SizeFunc(const ValueT& v) { return v.second; } |
| |
| static void SetCheckCallback(const void* ptr, ValueT* val, |
| set<pair<const void*, int> >* check_set) { |
| check_set->insert(make_pair(ptr, val->first)); |
| } |
| |
| int main(int argc, char** argv) { |
| // Get a bunch of pointers |
| const int N = FLAGS_N; |
| static const int kMaxRealSize = 49; |
| // 100Mb to stress not finding previous object (AddressMap's cluster is 1Mb): |
| static const size_t kMaxSize = 100*1000*1000; |
| vector<PtrAndSize> ptrs_and_sizes; |
| for (int i = 0; i < N; ++i) { |
| size_t s = rnd.Uniform(kMaxRealSize); |
| ptrs_and_sizes.push_back(PtrAndSize(new char[s], s)); |
| } |
| |
| for (int x = 0; x < FLAGS_iters; ++x) { |
| RAW_LOG(INFO, "Iteration %d/%d...\n", x, FLAGS_iters); |
| |
| // Permute pointers to get rid of allocation order issues |
| random_shuffle(ptrs_and_sizes.begin(), ptrs_and_sizes.end()); |
| |
| AddressMap<ValueT> map(malloc, free); |
| const ValueT* result; |
| const void* res_p; |
| |
| // Insert a bunch of entries |
| for (int i = 0; i < N; ++i) { |
| char* p = ptrs_and_sizes[i].ptr; |
| CHECK(!map.Find(p)); |
| int offs = rnd.Uniform(ptrs_and_sizes[i].size); |
| CHECK(!map.FindInside(&SizeFunc, kMaxSize, p + offs, &res_p)); |
| map.Insert(p, make_pair(i, ptrs_and_sizes[i].size)); |
| CHECK(result = map.Find(p)); |
| CHECK_EQ(result->first, i); |
| CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); |
| CHECK_EQ(res_p, p); |
| CHECK_EQ(result->first, i); |
| map.Insert(p, make_pair(i + N, ptrs_and_sizes[i].size)); |
| CHECK(result = map.Find(p)); |
| CHECK_EQ(result->first, i + N); |
| } |
| |
| // Delete the even entries |
| for (int i = 0; i < N; i += 2) { |
| void* p = ptrs_and_sizes[i].ptr; |
| ValueT removed; |
| CHECK(map.FindAndRemove(p, &removed)); |
| CHECK_EQ(removed.first, i + N); |
| } |
| |
| // Lookup the odd entries and adjust them |
| for (int i = 1; i < N; i += 2) { |
| char* p = ptrs_and_sizes[i].ptr; |
| CHECK(result = map.Find(p)); |
| CHECK_EQ(result->first, i + N); |
| int offs = rnd.Uniform(ptrs_and_sizes[i].size); |
| CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); |
| CHECK_EQ(res_p, p); |
| CHECK_EQ(result->first, i + N); |
| map.Insert(p, make_pair(i + 2*N, ptrs_and_sizes[i].size)); |
| CHECK(result = map.Find(p)); |
| CHECK_EQ(result->first, i + 2*N); |
| } |
| |
| // Insert even entries back |
| for (int i = 0; i < N; i += 2) { |
| char* p = ptrs_and_sizes[i].ptr; |
| int offs = rnd.Uniform(ptrs_and_sizes[i].size); |
| CHECK(!map.FindInside(&SizeFunc, kMaxSize, p + offs, &res_p)); |
| map.Insert(p, make_pair(i + 2*N, ptrs_and_sizes[i].size)); |
| CHECK(result = map.Find(p)); |
| CHECK_EQ(result->first, i + 2*N); |
| CHECK(result = map.FindInside(&SizeFunc, kMaxRealSize, p + offs, &res_p)); |
| CHECK_EQ(res_p, p); |
| CHECK_EQ(result->first, i + 2*N); |
| } |
| |
| // Check all entries |
| set<pair<const void*, int> > check_set; |
| map.Iterate(SetCheckCallback, &check_set); |
| CHECK_EQ(check_set.size(), N); |
| for (int i = 0; i < N; ++i) { |
| void* p = ptrs_and_sizes[i].ptr; |
| check_set.erase(make_pair(p, i + 2*N)); |
| CHECK(result = map.Find(p)); |
| CHECK_EQ(result->first, i + 2*N); |
| } |
| CHECK_EQ(check_set.size(), 0); |
| } |
| |
| for (int i = 0; i < N; ++i) { |
| delete[] ptrs_and_sizes[i].ptr; |
| } |
| |
| printf("PASS\n"); |
| return 0; |
| } |