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