HashTableTest.cpp revision 37b74a387bb3993387029859c2d9d051c41c724e 
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  HashTableTy::entry_type* entry = 0;
71
72  entry = hashTable->insert(pA, exist);
73
74  EXPECT_FALSE(hashTable->empty());
75
76  HashTableTy::iterator iter;
77  iter = hashTable->find(NULL);
78  EXPECT_TRUE(iter == hashTable->end());
79  delete hashTable;
80}
81
82TEST_F(HashTableTest, constructor) {
83  typedef HashEntry<int, int, IntCompare> HashEntryType;
84  HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > hashTable(16);
85  EXPECT_TRUE(17 == hashTable.numOfBuckets());
86  EXPECT_TRUE(hashTable.empty());
87  EXPECT_TRUE(0 == hashTable.numOfEntries());
88}
89
90TEST_F(HashTableTest, allocattion) {
91  typedef HashEntry<int, int, IntCompare> HashEntryType;
92  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
93      HashTableTy;
94  HashTableTy* hashTable = new HashTableTy(22);
95
96  bool exist;
97  int key = 100;
98  HashTableTy::entry_type* val = hashTable->insert(key, exist);
99  val->setValue(999);
100  EXPECT_FALSE(hashTable->empty());
101  EXPECT_FALSE(exist);
102  EXPECT_FALSE(NULL == val);
103  HashTableTy::iterator entry = hashTable->find(key);
104  EXPECT_EQ(999, entry.getEntry()->value());
105  delete hashTable;
106}
107
108TEST_F(HashTableTest, alloc100) {
109  typedef HashEntry<int, int, IntCompare> HashEntryType;
110  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
111      HashTableTy;
112  HashTableTy* hashTable = new HashTableTy(22);
113
114  bool exist;
115  HashTableTy::entry_type* entry = 0;
116  for (int key = 0; key < 100; ++key) {
117    entry = hashTable->insert(key, exist);
118    EXPECT_FALSE(hashTable->empty());
119    EXPECT_FALSE(exist);
120    EXPECT_FALSE(NULL == entry);
121    EXPECT_TRUE(key == entry->key());
122    entry->setValue(key + 10);
123  }
124
125  EXPECT_FALSE(hashTable->empty());
126  EXPECT_TRUE(100 == hashTable->numOfEntries());
127  EXPECT_TRUE(197 == hashTable->numOfBuckets());
128  delete hashTable;
129}
130
131TEST_F(HashTableTest, erase100) {
132  typedef HashEntry<int, int, IntCompare> HashEntryType;
133  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
134      HashTableTy;
135  HashTableTy* hashTable = new HashTableTy(0);
136
137  bool exist;
138  HashTableTy::entry_type* entry = 0;
139  for (unsigned int key = 0; key < 100; ++key)
140    entry = hashTable->insert(key, exist);
141
142  EXPECT_FALSE(hashTable->empty());
143
144  int count;
145  HashTableTy::iterator iter;
146  for (unsigned int key = 0; key < 100; ++key) {
147    count = hashTable->erase(key);
148    EXPECT_EQ(1, count);
149    iter = hashTable->find(key);
150    EXPECT_TRUE(iter == hashTable->end());
151  }
152
153  EXPECT_TRUE(hashTable->empty());
154  delete hashTable;
155}
156
157TEST_F(HashTableTest, clear) {
158  typedef HashEntry<int, int, IntCompare> HashEntryType;
159  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
160      HashTableTy;
161  HashTableTy* hashTable = new HashTableTy(22);
162
163  bool exist;
164  HashTableTy::entry_type* entry = 0;
165  for (unsigned int key = 0; key < 100; ++key) {
166    entry = hashTable->insert(key, exist);
167  }
168
169  hashTable->clear();
170
171  HashTableTy::iterator iter;
172  for (unsigned int key = 0; key < 100; ++key) {
173    iter = hashTable->find(key);
174    EXPECT_TRUE(iter == hashTable->end());
175  }
176
177  EXPECT_TRUE(hashTable->empty());
178  delete hashTable;
179}
180
181TEST_F(HashTableTest, tombstone) {
182  typedef HashEntry<int, int, IntCompare> HashEntryType;
183  typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> >
184      HashTableTy;
185  HashTableTy* hashTable = new HashTableTy();
186
187  bool exist;
188  HashTableTy::entry_type* entry = 0;
189  for (unsigned int key = 0; key < 100; ++key) {
190    entry = hashTable->insert(key, exist);
191  }
192  EXPECT_FALSE(hashTable->empty());
193
194  int count;
195  HashTableTy::iterator iter;
196  for (unsigned int key = 0; key < 20; ++key) {
197    count = hashTable->erase(key);
198    EXPECT_EQ(1, count);
199    iter = hashTable->find(key);
200    EXPECT_TRUE(iter == hashTable->end());
201  }
202  EXPECT_TRUE(80 == hashTable->numOfEntries());
203
204  for (unsigned int key = 20; key < 100; ++key) {
205    iter = hashTable->find(key);
206    EXPECT_TRUE(iter != hashTable->end());
207  }
208
209  for (unsigned int key = 0; key < 20; ++key) {
210    entry = hashTable->insert(key, exist);
211  }
212  EXPECT_TRUE(100 == hashTable->numOfEntries());
213  EXPECT_TRUE(197 == hashTable->numOfBuckets());
214
215  delete hashTable;
216}
217
218TEST_F(HashTableTest, rehash_test) {
219  typedef HashEntry<int, int, IntCompare> HashEntryType;
220  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
221      HashTableTy;
222  HashTableTy* hashTable = new HashTableTy(0);
223
224  bool exist;
225  HashTableTy::entry_type* entry = 0;
226  for (unsigned int key = 0; key < 400000; ++key) {
227    entry = hashTable->insert(key, exist);
228    entry->setValue(key + 10);
229  }
230
231  HashTableTy::iterator iter;
232  for (int key = 0; key < 400000; ++key) {
233    iter = hashTable->find(key);
234    EXPECT_EQ((key + 10), iter.getEntry()->value());
235  }
236
237  delete hashTable;
238}
239
240TEST_F(HashTableTest, bucket_iterator) {
241  typedef HashEntry<int, int, IntCompare> HashEntryType;
242  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
243      HashTableTy;
244  HashTableTy* hashTable = new HashTableTy(0);
245
246  bool exist;
247  HashTableTy::entry_type* entry = 0;
248  for (unsigned int key = 0; key < 400000; ++key) {
249    entry = hashTable->insert(key, exist);
250    entry->setValue(key + 10);
251  }
252
253  HashTableTy::iterator iter, iEnd = hashTable->end();
254  int counter = 0;
255  for (iter = hashTable->begin(); iter != iEnd; ++iter) {
256    EXPECT_EQ(iter.getEntry()->key() + 10, iter.getEntry()->value());
257    ++counter;
258  }
259  EXPECT_EQ(400000, counter);
260  delete hashTable;
261}
262
263TEST_F(HashTableTest, chain_iterator_single) {
264  typedef HashEntry<int, int, IntCompare> HashEntryType;
265  typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> >
266      HashTableTy;
267  HashTableTy* hashTable = new HashTableTy();
268
269  bool exist;
270  HashTableTy::entry_type* entry = 0;
271  for (int key = 0; key < 16; ++key) {
272    entry = hashTable->insert(key * 37, exist);
273    entry->setValue(key + 10);
274  }
275  for (int key = 0; key < 16; ++key) {
276    int counter = 0;
277    HashTableTy::chain_iterator iter, iEnd = hashTable->end(key * 37);
278    for (iter = hashTable->begin(key * 37); iter != iEnd; ++iter) {
279      EXPECT_EQ(key + 10, iter.getEntry()->value());
280      ++counter;
281    }
282    EXPECT_EQ(1, counter);
283  }
284  delete hashTable;
285}
286
287struct FixHash {
288  size_t operator()(int pKey) const { return 10; }
289};
290
291TEST_F(HashTableTest, chain_iterator_list) {
292  typedef HashEntry<int, int, IntCompare> HashEntryType;
293  typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> >
294      HashTableTy;
295  HashTableTy* hashTable = new HashTableTy();
296
297  bool exist;
298  HashTableTy::entry_type* entry = 0;
299  for (unsigned int key = 0; key < 16; ++key) {
300    entry = hashTable->insert(key, exist);
301    ASSERT_FALSE(exist);
302    entry->setValue(key);
303  }
304  ASSERT_TRUE(16 == hashTable->numOfEntries());
305  ASSERT_TRUE(37 == hashTable->numOfBuckets());
306
307  unsigned int key = 0;
308  int count = 0;
309  HashTableTy::chain_iterator iter, iEnd = hashTable->end(key);
310  for (iter = hashTable->begin(key); iter != iEnd; ++iter) {
311    count++;
312  }
313  ASSERT_EQ(16, count);
314  delete hashTable;
315}
316