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// Constructor can do set-up work for all test here.
20HashTableTest::HashTableTest() {
21}
22
23// Destructor can do clean-up work that doesn't throw exceptions here.
24HashTableTest::~HashTableTest() {
25}
26
27// SetUp() will be called immediately before each test.
28void HashTableTest::SetUp() {
29}
30
31// TearDown() will be called immediately after each test.
32void HashTableTest::TearDown() {
33}
34
35//==========================================================================//
36// Testcases
37//
38struct IntCompare {
39  bool operator()(int X, int Y) const { return (X == Y); }
40};
41
42struct PtrCompare {
43  bool operator()(const int* X, const int* Y) const { return (X == Y); }
44};
45
46struct PtrHash {
47  size_t operator()(const int* pKey) const {
48    return (unsigned((uintptr_t)pKey) >> 4) ^ (unsigned((uintptr_t)pKey) >> 9);
49  }
50};
51
52struct IntHash {
53  size_t operator()(int pKey) const { return pKey; }
54};
55
56struct IntMod3Hash {
57  size_t operator()(int pKey) const { return pKey % 3; }
58};
59
60TEST_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
80TEST_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
88TEST_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
106TEST_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
129TEST_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
154TEST_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
177TEST_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
213TEST_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
235TEST_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
258TEST_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
282struct FixHash {
283  size_t operator()(int pKey) const { return 10; }
284};
285
286TEST_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