123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171 |
- // -*- 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;
- }
|