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