HashTableTest.cpp revision 87f34658dec9097d987d254a990ea7f311bfc95f 
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
15using namespace std;
16using namespace mcld;
17using namespace mcldtest;
18
19
20// Constructor can do set-up work for all test here.
21HashTableTest::HashTableTest()
22{
23}
24
25// Destructor can do clean-up work that doesn't throw exceptions here.
26HashTableTest::~HashTableTest()
27{
28}
29
30// SetUp() will be called immediately before each test.
31void HashTableTest::SetUp()
32{
33}
34
35// TearDown() will be called immediately after each test.
36void HashTableTest::TearDown()
37{
38}
39
40//==========================================================================//
41// Testcases
42//
43struct IntCompare
44{
45  bool operator()(int X, int Y) const
46  { return (X==Y); }
47};
48
49struct PtrCompare
50{
51  bool operator()(const int* X, const int* Y) const
52  { return (X==Y); }
53};
54
55struct 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
64struct IntHash
65{
66  size_t operator()(int pKey) const
67  { return pKey; }
68};
69
70struct IntMod3Hash
71{
72  size_t operator()(int pKey) const
73  { return pKey % 3; }
74};
75
76TEST_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
97TEST_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
105TEST_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
122TEST_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
144TEST_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
169TEST_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
192TEST_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
228TEST_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
249TEST_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
272TEST_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
295struct FixHash
296{
297  size_t operator()(int pKey) const {
298    return 10;
299  }
300};
301
302
303TEST_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