HashTableTest.cpp revision 5460a1f25d9ddecb5c70667267d66d51af177a99 
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_EQ(17, hashTable.numOfBuckets());
101  EXPECT_TRUE(hashTable.empty());
102  EXPECT_EQ(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 (unsigned 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_EQ(key, entry->key());
135    entry->setValue(key+10);
136  }
137
138  EXPECT_FALSE(hashTable->empty());
139  EXPECT_EQ(100, hashTable->numOfEntries());
140  EXPECT_EQ(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  int count;
183  HashTableTy::iterator iter;
184  for (unsigned int key=0; key<100; ++key) {
185    iter = hashTable->find(key);
186    EXPECT_TRUE(iter == hashTable->end());
187  }
188
189  EXPECT_TRUE(hashTable->empty());
190  delete hashTable;
191}
192
193TEST_F( HashTableTest, tombstone ) {
194  typedef HashEntry<int, int, IntCompare> HashEntryType;
195  typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > HashTableTy;
196  HashTableTy *hashTable = new HashTableTy();
197
198  bool exist;
199  HashTableTy::entry_type* entry = 0;
200  for (unsigned int key=0; key<100; ++key) {
201    entry = hashTable->insert(key, exist);
202  }
203  EXPECT_FALSE(hashTable->empty());
204
205  int count;
206  HashTableTy::iterator iter;
207  for (unsigned int key=0; key<20; ++key) {
208    count = hashTable->erase(key);
209    EXPECT_EQ(1, count);
210    iter = hashTable->find(key);
211    EXPECT_TRUE(iter == hashTable->end());
212  }
213  EXPECT_EQ(80, hashTable->numOfEntries());
214
215  for (unsigned int key=20; key<100; ++key) {
216    iter = hashTable->find(key);
217    EXPECT_TRUE(iter != hashTable->end());
218  }
219
220  for (unsigned int key=0; key<20; ++key) {
221    entry = hashTable->insert(key, exist);
222  }
223  EXPECT_EQ(100, hashTable->numOfEntries());
224  EXPECT_EQ(197, hashTable->numOfBuckets());
225
226  delete hashTable;
227}
228
229TEST_F( HashTableTest, rehash_test ) {
230  typedef HashEntry<int, int, IntCompare> HashEntryType;
231  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
232  HashTableTy *hashTable = new HashTableTy(0);
233
234  bool exist;
235  HashTableTy::entry_type* entry = 0;
236  for (unsigned int key=0; key<400000; ++key) {
237    entry = hashTable->insert(key, exist);
238    entry->setValue(key+10);
239  }
240
241  HashTableTy::iterator iter;
242  for (unsigned int key=0; key<400000; ++key) {
243    iter = hashTable->find(key);
244    EXPECT_EQ((key+10), iter.getEntry()->value());
245  }
246
247  delete hashTable;
248}
249
250TEST_F( HashTableTest, bucket_iterator ) {
251  typedef HashEntry<int, int, IntCompare> HashEntryType;
252  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
253  HashTableTy *hashTable = new HashTableTy(0);
254
255  bool exist;
256  HashTableTy::entry_type* entry = 0;
257  for (unsigned int key=0; key<400000; ++key) {
258    entry = hashTable->insert(key, exist);
259    entry->setValue(key+10);
260  }
261
262  HashTableTy::iterator iter, iEnd = hashTable->end();
263  unsigned int counter = 0;
264  for (iter = hashTable->begin(); iter != iEnd; ++iter) {
265    EXPECT_EQ(iter.getEntry()->key()+10, iter.getEntry()->value());
266    ++counter;
267  }
268  EXPECT_EQ(400000, counter);
269  delete hashTable;
270}
271
272
273TEST_F( HashTableTest, chain_iterator_single ) {
274  typedef HashEntry<int, int, IntCompare> HashEntryType;
275  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy;
276  HashTableTy *hashTable = new HashTableTy();
277
278  bool exist;
279  HashTableTy::entry_type* entry = 0;
280  for (unsigned int key=0; key<16; ++key) {
281    entry = hashTable->insert(key*37, exist);
282    entry->setValue(key+10);
283  }
284  for (unsigned int key=0; key<16; ++key) {
285    unsigned int counter = 0;
286    HashTableTy::chain_iterator iter, iEnd = hashTable->end(key*37);
287    for (iter = hashTable->begin(key*37); iter != iEnd; ++iter) {
288      EXPECT_EQ(key+10, iter.getEntry()->value());
289      ++counter;
290    }
291    EXPECT_EQ(1, counter);
292  }
293  delete hashTable;
294}
295
296struct FixHash
297{
298  size_t operator()(int pKey) const {
299    return 10;
300  }
301};
302
303
304TEST_F( HashTableTest, chain_iterator_list ) {
305  typedef HashEntry<int, int, IntCompare> HashEntryType;
306  typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > HashTableTy;
307  HashTableTy *hashTable = new HashTableTy();
308
309  bool exist;
310  HashTableTy::entry_type* entry = 0;
311  for (unsigned int key=0; key<16; ++key) {
312    entry = hashTable->insert(key, exist);
313    ASSERT_FALSE(exist);
314    entry->setValue(key);
315  }
316  ASSERT_EQ(16, hashTable->numOfEntries());
317  ASSERT_EQ(37, hashTable->numOfBuckets());
318
319  unsigned int key = 0;
320  unsigned int count = 0;
321  HashTableTy::chain_iterator iter, iEnd = hashTable->end(key);
322  for (iter = hashTable->begin(key); iter != iEnd; ++iter) {
323    count++;
324  }
325  ASSERT_EQ(16, count);
326  delete hashTable;
327}
328