unittests/HashTableTest.cpp

//===- HashTableTest.cpp --------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "HashTableTest.h"
#include "mcld/ADT/HashEntry.h"
#include "mcld/ADT/HashTable.h"
#include <cstdlib>

using namespace std;
using namespace mcld;
using namespace mcldtest;


// Constructor can do set-up work for all test here.
HashTableTest::HashTableTest()
{
}

// Destructor can do clean-up work that doesn't throw exceptions here.
HashTableTest::~HashTableTest()
{
}

// SetUp() will be called immediately before each test.
void HashTableTest::SetUp()
{
}

// TearDown() will be called immediately after each test.
void HashTableTest::TearDown()
{
}

//==========================================================================//
// Testcases
//
struct IntCompare
{
  bool operator()(int X, int Y) const
  { return (X==Y); }
};

struct PtrCompare
{
  bool operator()(const int* X, const int* Y) const
  { return (X==Y); }
};

struct PtrHash
{
  size_t operator()(const int* pKey) const
  {
    return (unsigned((uintptr_t)pKey) >> 4) ^
           (unsigned((uintptr_t)pKey) >> 9);
  }
};

struct IntHash
{
  size_t operator()(int pKey) const
  { return pKey; }
};

struct IntMod3Hash
{
  size_t operator()(int pKey) const
  { return pKey % 3; }
};

TEST_F( HashTableTest, ptr_entry ) {
  int A = 1;
  int* pA = &A;

  typedef HashEntry<int*, int, PtrCompare> HashEntryType;
  typedef HashTable<HashEntryType, PtrHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(0);

  bool exist;
  HashTableTy::entry_type* entry = 0;

  entry = hashTable->insert(pA, exist);

  EXPECT_FALSE(hashTable->empty());

  HashTableTy::iterator iter;
  iter = hashTable->find(NULL);
  EXPECT_TRUE(iter==hashTable->end());
  delete hashTable;
}

TEST_F( HashTableTest, constructor ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > hashTable(16);
  EXPECT_TRUE(17 == hashTable.numOfBuckets());
  EXPECT_TRUE(hashTable.empty());
  EXPECT_TRUE(0 == hashTable.numOfEntries());
}

TEST_F( HashTableTest, allocattion ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(22);

  bool exist;
  int key = 100;
  HashTableTy::entry_type* val = hashTable->insert(key, exist);
  val->setValue(999);
  EXPECT_FALSE(hashTable->empty());
  EXPECT_FALSE(exist);
  EXPECT_FALSE(NULL == val);
  HashTableTy::iterator entry = hashTable->find(key);
  EXPECT_EQ(999, entry.getEntry()->value());
  delete hashTable;
}

TEST_F( HashTableTest, alloc100 ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(22);

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (int key=0; key<100; ++key) {
    entry = hashTable->insert(key, exist);
    EXPECT_FALSE(hashTable->empty());
    EXPECT_FALSE(exist);
    EXPECT_FALSE(NULL == entry);
    EXPECT_TRUE(key == entry->key());
    entry->setValue(key+10);
  }

  EXPECT_FALSE(hashTable->empty());
  EXPECT_TRUE(100 == hashTable->numOfEntries());
  EXPECT_TRUE(197 == hashTable->numOfBuckets());
  delete hashTable;
}

TEST_F( HashTableTest, erase100 ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(0);

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (unsigned int key=0; key<100; ++key)
    entry = hashTable->insert(key, exist);

  EXPECT_FALSE(hashTable->empty());

  int count;
  HashTableTy::iterator iter;
  for (unsigned int key=0; key<100; ++key) {
    count = hashTable->erase(key);
    EXPECT_EQ(1, count);
    iter = hashTable->find(key);
    EXPECT_TRUE(iter == hashTable->end());
  }

  EXPECT_TRUE(hashTable->empty());
  delete hashTable;
}

TEST_F( HashTableTest, clear) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(22);

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (unsigned int key=0; key<100; ++key) {
    entry = hashTable->insert(key, exist);
  }

  hashTable->clear();

  HashTableTy::iterator iter;
  for (unsigned int key=0; key<100; ++key) {
    iter = hashTable->find(key);
    EXPECT_TRUE(iter == hashTable->end());
  }

  EXPECT_TRUE(hashTable->empty());
  delete hashTable;
}

TEST_F( HashTableTest, tombstone ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy();

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (unsigned int key=0; key<100; ++key) {
    entry = hashTable->insert(key, exist);
  }
  EXPECT_FALSE(hashTable->empty());

  int count;
  HashTableTy::iterator iter;
  for (unsigned int key=0; key<20; ++key) {
    count = hashTable->erase(key);
    EXPECT_EQ(1, count);
    iter = hashTable->find(key);
    EXPECT_TRUE(iter == hashTable->end());
  }
  EXPECT_TRUE(80 == hashTable->numOfEntries());

  for (unsigned int key=20; key<100; ++key) {
    iter = hashTable->find(key);
    EXPECT_TRUE(iter != hashTable->end());
  }

  for (unsigned int key=0; key<20; ++key) {
    entry = hashTable->insert(key, exist);
  }
  EXPECT_TRUE(100 == hashTable->numOfEntries());
  EXPECT_TRUE(197 == hashTable->numOfBuckets());

  delete hashTable;
}

TEST_F( HashTableTest, rehash_test ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(0);

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (unsigned int key=0; key<400000; ++key) {
    entry = hashTable->insert(key, exist);
    entry->setValue(key+10);
  }

  HashTableTy::iterator iter;
  for (int key=0; key<400000; ++key) {
    iter = hashTable->find(key);
    EXPECT_EQ((key+10), iter.getEntry()->value());
  }

  delete hashTable;
}

TEST_F( HashTableTest, bucket_iterator ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy(0);

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (unsigned int key=0; key<400000; ++key) {
    entry = hashTable->insert(key, exist);
    entry->setValue(key+10);
  }

  HashTableTy::iterator iter, iEnd = hashTable->end();
  int counter = 0;
  for (iter = hashTable->begin(); iter != iEnd; ++iter) {
    EXPECT_EQ(iter.getEntry()->key()+10, iter.getEntry()->value());
    ++counter;
  }
  EXPECT_EQ(400000, counter);
  delete hashTable;
}


TEST_F( HashTableTest, chain_iterator_single ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy();

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (int key=0; key<16; ++key) {
    entry = hashTable->insert(key*37, exist);
    entry->setValue(key+10);
  }
  for (int key=0; key<16; ++key) {
    int counter = 0;
    HashTableTy::chain_iterator iter, iEnd = hashTable->end(key*37);
    for (iter = hashTable->begin(key*37); iter != iEnd; ++iter) {
      EXPECT_EQ(key+10, iter.getEntry()->value());
      ++counter;
    }
    EXPECT_EQ(1, counter);
  }
  delete hashTable;
}

struct FixHash
{
  size_t operator()(int pKey) const {
    return 10;
  }
};


TEST_F( HashTableTest, chain_iterator_list ) {
  typedef HashEntry<int, int, IntCompare> HashEntryType;
  typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > HashTableTy;
  HashTableTy *hashTable = new HashTableTy();

  bool exist;
  HashTableTy::entry_type* entry = 0;
  for (unsigned int key=0; key<16; ++key) {
    entry = hashTable->insert(key, exist);
    ASSERT_FALSE(exist);
    entry->setValue(key);
  }
  ASSERT_TRUE(16 == hashTable->numOfEntries());
  ASSERT_TRUE(37 == hashTable->numOfBuckets());

  unsigned int key = 0;
  int count = 0;
  HashTableTy::chain_iterator iter, iEnd = hashTable->end(key);
  for (iter = hashTable->begin(key); iter != iEnd; ++iter) {
    count++;
  }
  ASSERT_EQ(16, count);
  delete hashTable;
}