Home | History | Annotate | Download | only in unittests
      1 //===- HashTableTest.cpp --------------------------------------------------===//
      2 //
      3 //                     The MCLinker Project
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 
     10 #include "HashTableTest.h"
     11 #include "mcld/ADT/HashEntry.h"
     12 #include "mcld/ADT/HashTable.h"
     13 #include <cstdlib>
     14 
     15 using namespace std;
     16 using namespace mcld;
     17 using namespace mcldtest;
     18 
     19 
     20 // Constructor can do set-up work for all test here.
     21 HashTableTest::HashTableTest()
     22 {
     23 }
     24 
     25 // Destructor can do clean-up work that doesn't throw exceptions here.
     26 HashTableTest::~HashTableTest()
     27 {
     28 }
     29 
     30 // SetUp() will be called immediately before each test.
     31 void HashTableTest::SetUp()
     32 {
     33 }
     34 
     35 // TearDown() will be called immediately after each test.
     36 void HashTableTest::TearDown()
     37 {
     38 }
     39 
     40 //==========================================================================//
     41 // Testcases
     42 //
     43 struct IntCompare
     44 {
     45   bool operator()(int X, int Y) const
     46   { return (X==Y); }
     47 };
     48 
     49 struct PtrCompare
     50 {
     51   bool operator()(const int* X, const int* Y) const
     52   { return (X==Y); }
     53 };
     54 
     55 struct PtrHash
     56 {
     57   size_t operator()(const int* pKey) const
     58   {
     59     return (unsigned((uintptr_t)pKey) >> 4) ^
     60            (unsigned((uintptr_t)pKey) >> 9);
     61   }
     62 };
     63 
     64 struct IntHash
     65 {
     66   size_t operator()(int pKey) const
     67   { return pKey; }
     68 };
     69 
     70 struct IntMod3Hash
     71 {
     72   size_t operator()(int pKey) const
     73   { return pKey % 3; }
     74 };
     75 
     76 TEST_F( HashTableTest, ptr_entry ) {
     77   int A = 1;
     78   int* pA = &A;
     79 
     80   typedef HashEntry<int*, int, PtrCompare> HashEntryType;
     81   typedef HashTable<HashEntryType, PtrHash, EntryFactory<HashEntryType> > HashTableTy;
     82   HashTableTy *hashTable = new HashTableTy(0);
     83 
     84   bool exist;
     85   HashTableTy::entry_type* entry = 0;
     86 
     87   entry = hashTable->insert(pA, exist);
     88 
     89   EXPECT_FALSE(hashTable->empty());
     90 
     91   HashTableTy::iterator iter;
     92   iter = hashTable->find(NULL);
     93   EXPECT_TRUE(iter==hashTable->end());
     94   delete hashTable;
     95 }
     96 
     97 TEST_F( HashTableTest, constructor ) {
     98   typedef HashEntry<int, int, IntCompare> HashEntryType;
     99   HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > hashTable(16);
    100   EXPECT_TRUE(17 == hashTable.numOfBuckets());
    101   EXPECT_TRUE(hashTable.empty());
    102   EXPECT_TRUE(0 == hashTable.numOfEntries());
    103 }
    104 
    105 TEST_F( HashTableTest, allocattion ) {
    106   typedef HashEntry<int, int, IntCompare> HashEntryType;
    107   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    108   HashTableTy *hashTable = new HashTableTy(22);
    109 
    110   bool exist;
    111   int key = 100;
    112   HashTableTy::entry_type* val = hashTable->insert(key, exist);
    113   val->setValue(999);
    114   EXPECT_FALSE(hashTable->empty());
    115   EXPECT_FALSE(exist);
    116   EXPECT_FALSE(NULL == val);
    117   HashTableTy::iterator entry = hashTable->find(key);
    118   EXPECT_EQ(999, entry.getEntry()->value());
    119   delete hashTable;
    120 }
    121 
    122 TEST_F( HashTableTest, alloc100 ) {
    123   typedef HashEntry<int, int, IntCompare> HashEntryType;
    124   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    125   HashTableTy *hashTable = new HashTableTy(22);
    126 
    127   bool exist;
    128   HashTableTy::entry_type* entry = 0;
    129   for (int key=0; key<100; ++key) {
    130     entry = hashTable->insert(key, exist);
    131     EXPECT_FALSE(hashTable->empty());
    132     EXPECT_FALSE(exist);
    133     EXPECT_FALSE(NULL == entry);
    134     EXPECT_TRUE(key == entry->key());
    135     entry->setValue(key+10);
    136   }
    137 
    138   EXPECT_FALSE(hashTable->empty());
    139   EXPECT_TRUE(100 == hashTable->numOfEntries());
    140   EXPECT_TRUE(197 == hashTable->numOfBuckets());
    141   delete hashTable;
    142 }
    143 
    144 TEST_F( HashTableTest, erase100 ) {
    145   typedef HashEntry<int, int, IntCompare> HashEntryType;
    146   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    147   HashTableTy *hashTable = new HashTableTy(0);
    148 
    149   bool exist;
    150   HashTableTy::entry_type* entry = 0;
    151   for (unsigned int key=0; key<100; ++key)
    152     entry = hashTable->insert(key, exist);
    153 
    154   EXPECT_FALSE(hashTable->empty());
    155 
    156   int count;
    157   HashTableTy::iterator iter;
    158   for (unsigned int key=0; key<100; ++key) {
    159     count = hashTable->erase(key);
    160     EXPECT_EQ(1, count);
    161     iter = hashTable->find(key);
    162     EXPECT_TRUE(iter == hashTable->end());
    163   }
    164 
    165   EXPECT_TRUE(hashTable->empty());
    166   delete hashTable;
    167 }
    168 
    169 TEST_F( HashTableTest, clear) {
    170   typedef HashEntry<int, int, IntCompare> HashEntryType;
    171   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    172   HashTableTy *hashTable = new HashTableTy(22);
    173 
    174   bool exist;
    175   HashTableTy::entry_type* entry = 0;
    176   for (unsigned int key=0; key<100; ++key) {
    177     entry = hashTable->insert(key, exist);
    178   }
    179 
    180   hashTable->clear();
    181 
    182   HashTableTy::iterator iter;
    183   for (unsigned int key=0; key<100; ++key) {
    184     iter = hashTable->find(key);
    185     EXPECT_TRUE(iter == hashTable->end());
    186   }
    187 
    188   EXPECT_TRUE(hashTable->empty());
    189   delete hashTable;
    190 }
    191 
    192 TEST_F( HashTableTest, tombstone ) {
    193   typedef HashEntry<int, int, IntCompare> HashEntryType;
    194   typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > HashTableTy;
    195   HashTableTy *hashTable = new HashTableTy();
    196 
    197   bool exist;
    198   HashTableTy::entry_type* entry = 0;
    199   for (unsigned int key=0; key<100; ++key) {
    200     entry = hashTable->insert(key, exist);
    201   }
    202   EXPECT_FALSE(hashTable->empty());
    203 
    204   int count;
    205   HashTableTy::iterator iter;
    206   for (unsigned int key=0; key<20; ++key) {
    207     count = hashTable->erase(key);
    208     EXPECT_EQ(1, count);
    209     iter = hashTable->find(key);
    210     EXPECT_TRUE(iter == hashTable->end());
    211   }
    212   EXPECT_TRUE(80 == hashTable->numOfEntries());
    213 
    214   for (unsigned int key=20; key<100; ++key) {
    215     iter = hashTable->find(key);
    216     EXPECT_TRUE(iter != hashTable->end());
    217   }
    218 
    219   for (unsigned int key=0; key<20; ++key) {
    220     entry = hashTable->insert(key, exist);
    221   }
    222   EXPECT_TRUE(100 == hashTable->numOfEntries());
    223   EXPECT_TRUE(197 == hashTable->numOfBuckets());
    224 
    225   delete hashTable;
    226 }
    227 
    228 TEST_F( HashTableTest, rehash_test ) {
    229   typedef HashEntry<int, int, IntCompare> HashEntryType;
    230   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    231   HashTableTy *hashTable = new HashTableTy(0);
    232 
    233   bool exist;
    234   HashTableTy::entry_type* entry = 0;
    235   for (unsigned int key=0; key<400000; ++key) {
    236     entry = hashTable->insert(key, exist);
    237     entry->setValue(key+10);
    238   }
    239 
    240   HashTableTy::iterator iter;
    241   for (int key=0; key<400000; ++key) {
    242     iter = hashTable->find(key);
    243     EXPECT_EQ((key+10), iter.getEntry()->value());
    244   }
    245 
    246   delete hashTable;
    247 }
    248 
    249 TEST_F( HashTableTest, bucket_iterator ) {
    250   typedef HashEntry<int, int, IntCompare> HashEntryType;
    251   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    252   HashTableTy *hashTable = new HashTableTy(0);
    253 
    254   bool exist;
    255   HashTableTy::entry_type* entry = 0;
    256   for (unsigned int key=0; key<400000; ++key) {
    257     entry = hashTable->insert(key, exist);
    258     entry->setValue(key+10);
    259   }
    260 
    261   HashTableTy::iterator iter, iEnd = hashTable->end();
    262   int counter = 0;
    263   for (iter = hashTable->begin(); iter != iEnd; ++iter) {
    264     EXPECT_EQ(iter.getEntry()->key()+10, iter.getEntry()->value());
    265     ++counter;
    266   }
    267   EXPECT_EQ(400000, counter);
    268   delete hashTable;
    269 }
    270 
    271 
    272 TEST_F( HashTableTest, chain_iterator_single ) {
    273   typedef HashEntry<int, int, IntCompare> HashEntryType;
    274   typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
    275   HashTableTy *hashTable = new HashTableTy();
    276 
    277   bool exist;
    278   HashTableTy::entry_type* entry = 0;
    279   for (int key=0; key<16; ++key) {
    280     entry = hashTable->insert(key*37, exist);
    281     entry->setValue(key+10);
    282   }
    283   for (int key=0; key<16; ++key) {
    284     int counter = 0;
    285     HashTableTy::chain_iterator iter, iEnd = hashTable->end(key*37);
    286     for (iter = hashTable->begin(key*37); iter != iEnd; ++iter) {
    287       EXPECT_EQ(key+10, iter.getEntry()->value());
    288       ++counter;
    289     }
    290     EXPECT_EQ(1, counter);
    291   }
    292   delete hashTable;
    293 }
    294 
    295 struct FixHash
    296 {
    297   size_t operator()(int pKey) const {
    298     return 10;
    299   }
    300 };
    301 
    302 
    303 TEST_F( HashTableTest, chain_iterator_list ) {
    304   typedef HashEntry<int, int, IntCompare> HashEntryType;
    305   typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > HashTableTy;
    306   HashTableTy *hashTable = new HashTableTy();
    307 
    308   bool exist;
    309   HashTableTy::entry_type* entry = 0;
    310   for (unsigned int key=0; key<16; ++key) {
    311     entry = hashTable->insert(key, exist);
    312     ASSERT_FALSE(exist);
    313     entry->setValue(key);
    314   }
    315   ASSERT_TRUE(16 == hashTable->numOfEntries());
    316   ASSERT_TRUE(37 == hashTable->numOfBuckets());
    317 
    318   unsigned int key = 0;
    319   int count = 0;
    320   HashTableTy::chain_iterator iter, iEnd = hashTable->end(key);
    321   for (iter = hashTable->begin(key); iter != iEnd; ++iter) {
    322     count++;
    323   }
    324   ASSERT_EQ(16, count);
    325   delete hashTable;
    326 }
    327