/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

#include "precompiled.hpp"

#include "runtime/mutex.hpp"

#include "runtime/semaphore.hpp"

#include "runtime/thread.hpp"

#include "runtime/vmThread.hpp"

#include "runtime/vmOperations.hpp"

#include "utilities/concurrentHashTable.inline.hpp"

#include "utilities/concurrentHashTableTasks.inline.hpp"

#include "threadHelper.inline.hpp"

#include "unittest.hpp"

// NOTE: On win32 gtest asserts are not mt-safe.

// Amusingly as long as they do not assert they are mt-safe.

#define SIZE_32 5

struct Pointer;

typedef ConcurrentHashTable<uintptr_t, Pointer, mtInternal> SimpleTestTable;

typedef ConcurrentHashTable<uintptr_t, Pointer, mtInternal>::MultiGetHandle SimpleTestGetHandle;

// Simplest working CRPT implementation for the hash-table.

struct Pointer : public SimpleTestTable::BaseConfig {

  static uintx get_hash(const uintptr_t& value, bool* dead_hash) {

    return (uintx)value;

  }

  static void* allocate_node(size_t size, const uintptr_t& value) {

    return ::malloc(size);

  }

  static void free_node(void* memory, const uintptr_t& value) {

    ::free(memory);

  }

};

struct SimpleTestLookup {

  uintptr_t _val;

  SimpleTestLookup(uintptr_t val) : _val(val) {}

  uintx get_hash() {

    return Pointer::get_hash(_val, NULL);

  }

  bool equals(const uintptr_t* value, bool* is_dead) {

    return _val == *value;

  }

};

struct ValueGet {

  uintptr_t _return;

  ValueGet() : _return(0) {}

  void operator()(uintptr_t* value) {

    EXPECT_NE(value, (uintptr_t*)NULL) << "expected valid value";

    _return = *value;

  }

  uintptr_t get_value() const {

    return _return;

  }

};

}

}

static void cht_get_insert(Thread* thr) {

  uintptr_t val = 0x2;

  SimpleTestLookup stl(val);

  SimpleTestTable* cht = new SimpleTestTable();

  {

    SCOPED_TRACE("First");

  }

  EXPECT_TRUE(cht->remove(thr, stl)) << "Removing existing value failed.";

  {

    SCOPED_TRACE("Second");

  }

  delete cht;

}

static bool getinsert_bulkdelete_eval(uintptr_t* val) {

  EXPECT_TRUE(*val > 0 && *val < 4) << "Val wrong for this test.";

  return (*val & 0x1); // Delete all values ending with first bit set.

}

static void getinsert_bulkdelete_del(uintptr_t* val) {

  EXPECT_EQ(*val & 0x1, (uintptr_t)1) << "Deleting wrong value.";

}

static void cht_getinsert_bulkdelete_insert_verified(Thread* thr, SimpleTestTable* cht, uintptr_t val,

                                                     bool verify_expect_get, bool verify_expect_inserted) {

  SimpleTestLookup stl(val);

  if (verify_expect_inserted) {

  }

  if (verify_expect_get) {

  }

}

static void cht_getinsert_bulkdelete(Thread* thr) {

  uintptr_t val1 = 1;

  uintptr_t val2 = 2;

  uintptr_t val3 = 3;

  SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);

  SimpleTestTable* cht = new SimpleTestTable();

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true);

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true);

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true);

  EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value.";

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present

  // Removes all odd values.

  cht->bulk_delete(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del);

  EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist.";

  EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists.";

  delete cht;

}

static void cht_getinsert_bulkdelete_task(Thread* thr) {

  uintptr_t val1 = 1;

  uintptr_t val2 = 2;

  uintptr_t val3 = 3;

  SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);

  SimpleTestTable* cht = new SimpleTestTable();

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true);

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true);

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true);

  EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value.";

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted

  cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present

  // Removes all odd values.

  SimpleTestTable::BulkDeleteTask bdt(cht);

  if (bdt.prepare(thr)) {

    while(bdt.do_task(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del)) {

      bdt.pause(thr);

      bdt.cont(thr);

    }

    bdt.done(thr);

  }

  EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist.";

  EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists.";

  delete cht;

}

static void cht_scope(Thread* thr) {

  uintptr_t val = 0x2;

  SimpleTestLookup stl(val);

  SimpleTestTable* cht = new SimpleTestTable();

  EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";

  {

    SimpleTestGetHandle get_handle(thr, cht);

    EXPECT_EQ(*get_handle.get(stl), val) << "Getting a pre-existing value failed.";

  }

  // We do remove here to make sure the value-handle 'unlocked' the table when leaving the scope.

  EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed.";

  delete cht;

}

struct ChtScan {

  size_t _count;

  ChtScan() : _count(0) {}

  bool operator()(uintptr_t* val) {

    EXPECT_EQ(*val, (uintptr_t)0x2) << "Got an unknown value.";

    EXPECT_EQ(_count, 0u) << "Only one value should be in table.";

    _count++;

    return true; /* continue scan */

  }

};

static void cht_scan(Thread* thr) {

  uintptr_t val = 0x2;

  SimpleTestLookup stl(val);

  ChtScan scan;

  SimpleTestTable* cht = new SimpleTestTable();

  EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";

  EXPECT_EQ(cht->try_scan(thr, scan), true) << "Scanning an non-growing/shrinking table should work.";

  EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed.";

  delete cht;

}

struct ChtCountScan {

  size_t _count;

  ChtCountScan() : _count(0) {}

  bool operator()(uintptr_t* val) {

    _count++;

    return true; /* continue scan */

  }

};

static void cht_move_to(Thread* thr) {

  uintptr_t val1 = 0x2;

  uintptr_t val2 = 0xe0000002;

  uintptr_t val3 = 0x3;

  SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);

  SimpleTestTable* from_cht = new SimpleTestTable();

  EXPECT_TRUE(from_cht->insert(thr, stl1, val1)) << "Insert unique value failed.";

  EXPECT_TRUE(from_cht->insert(thr, stl2, val2)) << "Insert unique value failed.";

  EXPECT_TRUE(from_cht->insert(thr, stl3, val3)) << "Insert unique value failed.";

  SimpleTestTable* to_cht = new SimpleTestTable();

  EXPECT_TRUE(from_cht->try_move_nodes_to(thr, to_cht)) << "Moving nodes to new table failed";

  ChtCountScan scan_old;

  EXPECT_TRUE(from_cht->try_scan(thr, scan_old)) << "Scanning table should work.";

  EXPECT_EQ(scan_old._count, (size_t)0) << "All items should be moved";

  ChtCountScan scan_new;

  EXPECT_TRUE(to_cht->try_scan(thr, scan_new)) << "Scanning table should work.";

  EXPECT_EQ(scan_new._count, (size_t)3) << "All items should be moved";

}

static void cht_grow(Thread* thr) {

  uintptr_t val = 0x2;

  uintptr_t val2 = 0x22;

  uintptr_t val3 = 0x222;

  SimpleTestLookup stl(val), stl2(val2), stl3(val3);

  SimpleTestTable* cht = new SimpleTestTable();

  EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";

  EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";

  EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";

  EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";

  EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";

  EXPECT_TRUE(cht->grow(thr)) << "Growing uncontended should not fail.";

  EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";

  EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";

  EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";

  delete cht;

}

static void cht_task_grow(Thread* thr) {

  uintptr_t val = 0x2;

  uintptr_t val2 = 0x22;

  uintptr_t val3 = 0x222;

  SimpleTestLookup stl(val), stl2(val2), stl3(val3);

  SimpleTestTable* cht = new SimpleTestTable();

  EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";

  EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";

  EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";

  EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";

  EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";

  SimpleTestTable::GrowTask gt(cht);

  EXPECT_TRUE(gt.prepare(thr)) << "Growing uncontended should not fail.";

  while(gt.do_task(thr)) { /* grow */  }

  gt.done(thr);

  EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";

  EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";

  EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";

  delete cht;

}

TEST_VM(ConcurrentHashTable, basic_insert) {

  nomt_test_doer(cht_insert);

}

TEST_VM(ConcurrentHashTable, basic_get_insert) {

  nomt_test_doer(cht_get_insert);

}

TEST_VM(ConcurrentHashTable, basic_scope) {

  nomt_test_doer(cht_scope);

}

TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete) {

  nomt_test_doer(cht_getinsert_bulkdelete);

}

TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete_task) {

  nomt_test_doer(cht_getinsert_bulkdelete_task);

}

TEST_VM(ConcurrentHashTable, basic_scan) {

  nomt_test_doer(cht_scan);

}

TEST_VM(ConcurrentHashTable, basic_move_to) {

  nomt_test_doer(cht_move_to);

}

TEST_VM(ConcurrentHashTable, basic_grow) {

  nomt_test_doer(cht_grow);

}

TEST_VM(ConcurrentHashTable, task_grow) {

  nomt_test_doer(cht_task_grow);

}

//#############################################################################################

class TestInterface;

typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal> TestTable;

typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal>::MultiGetHandle TestGetHandle;

class TestInterface : public TestTable::BaseConfig {

public:

  static uintx get_hash(const uintptr_t& value, bool* dead_hash) {

    return (uintx)(value + 18446744073709551557ul) * 18446744073709551557ul;

  }

};

struct TestLookup {

  uintptr_t _val;

  TestLookup(uintptr_t val) : _val(val) {}

  uintx get_hash() {

    return TestInterface::get_hash(_val, NULL);

  }

  bool equals(const uintptr_t* value, bool* is_dead) {

    return _val == *value;

  }

};

class CHTTestThread : public JavaTestThread {

  public:

  uintptr_t _start;

  uintptr_t _stop;

  TestTable *_cht;

  jlong _stop_ms;

  CHTTestThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)

    : JavaTestThread(post), _start(start), _stop(stop), _cht(cht) {}

  virtual void premain() {}

  void main_run() {

    premain();

    _stop_ms = os::javaTimeMillis() + 2000; // 2 seconds max test time

    while (keep_looping() && test_loop()) { /* */ }

    postmain();

  }

  virtual void postmain() {}

  virtual bool keep_looping() {

    return _stop_ms > os::javaTimeMillis();

  };

  virtual bool test_loop() = 0;

  virtual ~CHTTestThread() {}

};

class ValueSaver {

  uintptr_t* _vals;

  size_t _it;

  size_t _size;

 public:

  ValueSaver() : _it(0), _size(1024) {

      _vals = NEW_C_HEAP_ARRAY(uintptr_t, _size, mtInternal);

  }

  bool operator()(uintptr_t* val) {

    _vals[_it++] = *val;

    if (_it == _size) {

      _size *= 2;

      _vals = REALLOC_RESOURCE_ARRAY(uintptr_t, _vals, _size/2, _size);

    }

    return true;

  }

  void check() {

    for (size_t i = 0; i < _it; i++) {

      size_t count = 0;

      for (size_t j = (i + 1u); j < _it; j++) {

        if (_vals[i] == _vals[j]) {

          count++;

        }

      }

      EXPECT_EQ(count, 0u);

    }

  }

};

static void integrity_check(Thread* thr, TestTable* cht)

{

  ValueSaver vs;

  cht->do_scan(thr, vs);

  vs.check();

}

//#############################################################################################

// All threads are working on different items

// This item should only be delete by this thread

// Thus get_unsafe is safe for this test.

class SimpleInserterThread : public CHTTestThread {

public:

  static volatile bool _exit;