1#include <cppunit/TestAssert.h>
2#include <cppunit/TestCaller.h>
3#include <cppunit/TestSuite.h>
4#include <TestShell.h>
5
6#include <os/support/ObjectList.h>
7#include <shared/AutoDeleter.h>
8#include <util/OpenHashTable.h>
9
10#include "BOpenHashTableTest.h"
11
12
13namespace {
14
15class Entry {
16public:
17	Entry(uint32_t value)
18		:
19		fValue(value),
20		fNext(NULL)
21	{
22	}
23
24	const uint32_t Value() const
25	{
26		return fValue;
27	}
28
29	Entry* Next() const
30	{
31		return fNext;
32	}
33
34private:
35	uint32_t	fValue;
36	Entry		*fNext;
37
38	friend class EntryDefinition;
39};
40
41
42class EntryDefinition {
43public:
44	typedef uint32_t KeyType;
45	typedef Entry ValueType;
46
47	size_t HashKey(const KeyType& key) const
48	{
49		return key;
50	}
51
52	size_t Hash(Entry* entry) const
53	{
54		return entry->fValue;
55	}
56
57	bool Compare(const KeyType& key, Entry* entry) const
58	{
59		return key == entry->fValue;
60	}
61
62	Entry*& GetLink(Entry* entry) const
63	{
64		return entry->fNext;
65	}
66};
67
68}
69
70
71CppUnit::Test* BOpenHashTableTest::Suite()
72{
73	CppUnit::TestSuite* suite = new CppUnit::TestSuite("BOpenHashTable");
74
75	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
76					   "BOpenHashTable::Insert test",
77					   &BOpenHashTableTest::InsertTest));
78	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
79					   "BOpenHashTable::Insert unchecked test",
80					   &BOpenHashTableTest::InsertUncheckedTest));
81	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
82					   "BOpenHashTable::Insert unchecked uninitialized test",
83					   &BOpenHashTableTest::InsertUncheckedUninitializedTest));
84	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
85					   "BOpenHashTable::Iterate and count test",
86					   &BOpenHashTableTest::IterateAndCountTest));
87	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
88					   "BOpenHashTable::Lookup test",
89					   &BOpenHashTableTest::LookupTest));
90	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
91					   "BOpenHashTable::Resize test",
92					   &BOpenHashTableTest::ResizeTest));
93	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
94					   "BOpenHashTable::Remove test",
95					   &BOpenHashTableTest::RemoveTest));
96	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
97					   "BOpenHashTable::Remove unchecked test",
98					   &BOpenHashTableTest::RemoveUncheckedTest));
99	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
100					   "BOpenHashTable::Remove when not present test",
101					   &BOpenHashTableTest::RemoveWhenNotPresentTest));
102	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
103					   "BOpenHashTable::Duplicate insert test",
104					   &BOpenHashTableTest::DuplicateInsertTest));
105	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
106					   "BOpenHashTable::Disable auto expand",
107					   &BOpenHashTableTest::DisableAutoExpandTest));
108	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
109					   "BOpenHashTable::Init with zero size",
110					   &BOpenHashTableTest::InitWithZeroSizeTest));
111	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
112					   "BOpenHashTable::Clear test",
113					   &BOpenHashTableTest::ClearTest));
114	suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
115					   "BOpenHashTable::Clear and return test",
116					   &BOpenHashTableTest::ClearAndReturnTest));
117
118	return suite;
119}
120
121
122BOpenHashTableTest::BOpenHashTableTest(std::string name)
123	: BTestCase(name)
124{
125}
126
127
128void BOpenHashTableTest::InsertTest()
129{
130	Entry entry(123);
131
132	BOpenHashTable<EntryDefinition> table;
133	CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
134
135	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
136}
137
138
139void BOpenHashTableTest::InsertUncheckedTest()
140{
141	Entry entry(123);
142
143	BOpenHashTable<EntryDefinition> table;
144	CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
145
146	table.InsertUnchecked(&entry);
147}
148
149
150void BOpenHashTableTest::InsertUncheckedUninitializedTest()
151{
152	Entry entry(123);
153
154	BOpenHashTable<EntryDefinition> table;
155	CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
156
157	table.InsertUnchecked(&entry);
158}
159
160
161void BOpenHashTableTest::IterateAndCountTest() {
162	const size_t kEntryCount = 20;
163
164	BObjectList<Entry> entries(20, true);
165
166	BOpenHashTable<EntryDefinition> table;
167	CPPUNIT_ASSERT_EQUAL(table.Init(kEntryCount * 2), B_OK);
168
169	for (uint32_t i = 0; i < kEntryCount; ++i) {
170		Entry* entry = new Entry(i);
171		entries.AddItem(entry);
172		CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
173	}
174
175	// Verify that the table contains the expected values.
176	uint64_t map = 0;
177	BOpenHashTable<EntryDefinition>::Iterator iterator = table.GetIterator();
178	while (iterator.HasNext()) {
179		Entry* entry = iterator.Next();
180		CPPUNIT_ASSERT_EQUAL(0, map & (1 << entry->Value()));
181		map |= (1 << entry->Value());
182	}
183
184	CPPUNIT_ASSERT_EQUAL(map, (1 << kEntryCount) - 1);
185	CPPUNIT_ASSERT_EQUAL(kEntryCount, table.CountElements());
186}
187
188
189void BOpenHashTableTest::ResizeTest()
190{
191	// This is the same as IterateAndCountTest, except that the table will
192	// be resized mid insertion.
193	const size_t kEntryCount = 20;
194	BObjectList<Entry> entries(20, true);
195	BOpenHashTable<EntryDefinition> table;
196
197	// Start off with capacity for 8 elements. This will mean that the table
198	// will be resized in the loop below since we are inserting 20 elements.
199	CPPUNIT_ASSERT_EQUAL(table.Init(8), B_OK);
200
201	for (uint32_t i = 0; i < kEntryCount; ++i) {
202		Entry* entry = new Entry(i);
203		entries.AddItem(entry);
204		CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
205	}
206
207	// Verify that after resize the expected elements are present within
208	// the table.
209	uint64_t map = 0;
210	BOpenHashTable<EntryDefinition>::Iterator iterator = table.GetIterator();
211	while (iterator.HasNext()) {
212		Entry* entry = iterator.Next();
213		CPPUNIT_ASSERT_EQUAL(0, map & (1 << entry->Value()));
214		map |= (1 << entry->Value());
215	}
216
217	CPPUNIT_ASSERT_EQUAL(map, (1 << kEntryCount) - 1);
218	CPPUNIT_ASSERT_EQUAL(kEntryCount, table.CountElements());
219}
220
221
222void BOpenHashTableTest::LookupTest() {
223	Entry entry(123);
224
225	BOpenHashTable<EntryDefinition> table;
226	CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
227
228	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
229	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
230}
231
232
233void BOpenHashTableTest::RemoveTest() {
234	Entry entry(123);
235
236	BOpenHashTable<EntryDefinition> table;
237	CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
238
239	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
240	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
241
242	table.Remove(&entry);
243	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), NULL);
244}
245
246
247void BOpenHashTableTest::RemoveUncheckedTest()
248{
249	Entry entry(123);
250
251	BOpenHashTable<EntryDefinition> table;
252	CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
253
254	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
255	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
256
257	table.RemoveUnchecked(&entry);
258	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), NULL);
259}
260
261
262void BOpenHashTableTest::RemoveWhenNotPresentTest()
263{
264	Entry entry1(123);
265	Entry entry2(456);
266	Entry entry3(789);
267
268	BOpenHashTable<EntryDefinition> table;
269	CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
270
271	// Only add the first two entries.
272	table.Insert(&entry1);
273	table.Insert(&entry2);
274
275	// entry3 is not in the table, but we'll remove it anyway.
276	table.Remove(&entry3);
277	table.RemoveUnchecked(&entry3);
278
279	// The original two entries should still be there.
280	CPPUNIT_ASSERT_EQUAL(table.CountElements(), 2);
281	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry1);
282	CPPUNIT_ASSERT_EQUAL(table.Lookup(456), &entry2);
283	CPPUNIT_ASSERT_EQUAL(table.Lookup(789), NULL);
284}
285
286
287void BOpenHashTableTest::DuplicateInsertTest()
288{
289	Entry entry(123);
290
291	BOpenHashTable<EntryDefinition, true, true> table;
292	CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
293
294	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
295	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
296
297	CPPUNIT_ASSERT_DEBUGGER(table.Insert(&entry));
298
299	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
300
301	// The item can basically never be removed now since there is a cycle,
302	// but we'll break into the debugger on remove when that happens as well.
303	CPPUNIT_ASSERT_DEBUGGER(table.Remove(&entry));
304	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
305
306	CPPUNIT_ASSERT_DEBUGGER(table.Remove(&entry));
307	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
308}
309
310
311void BOpenHashTableTest::DisableAutoExpandTest()
312{
313	// Insert multiple items into a table with a fixed size of 1. This
314	// essentially turns this BOpenHashTable into a linked list, since resize
315	// will never occur.
316	Entry entry1(123);
317	Entry entry2(456);
318
319	BOpenHashTable<EntryDefinition, false> table;
320	CPPUNIT_ASSERT_EQUAL(table.Init(1), B_OK);
321
322	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry1), B_OK);
323	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry2), B_OK);
324	CPPUNIT_ASSERT_EQUAL(table.CountElements(), 2);
325}
326
327
328void BOpenHashTableTest::InitWithZeroSizeTest()
329{
330	Entry entry(123);
331
332	BOpenHashTable<EntryDefinition> table;
333	CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
334
335	CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
336	CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
337}
338
339
340void BOpenHashTableTest::ClearTest()
341{
342	const size_t kEntryCount = 3;
343
344	BObjectList<Entry> entries(20, true);
345
346	BOpenHashTable<EntryDefinition> table;
347	CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
348
349	for (uint32_t i = 0; i < kEntryCount; ++i) {
350		Entry* entry = new Entry(i);
351		entries.AddItem(entry);
352		CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
353	}
354
355	CPPUNIT_ASSERT_EQUAL(table.CountElements(), kEntryCount);
356	CPPUNIT_ASSERT(table.Lookup(2) != NULL);
357
358	CPPUNIT_ASSERT_EQUAL(table.Clear(false), NULL);
359	CPPUNIT_ASSERT_EQUAL(table.CountElements(), 0);
360	CPPUNIT_ASSERT_EQUAL(table.Lookup(2), NULL);
361	CPPUNIT_ASSERT_EQUAL(table.GetIterator().HasNext(), false);
362}
363
364
365void BOpenHashTableTest::ClearAndReturnTest()
366{
367	// Same as ClearTest(), except that Clear(true) is called, which tells
368	// the BOpenHashTable<T> to return a linked list of entries before clearing
369	// the table.
370	const size_t kEntryCount = 3;
371	BOpenHashTable<EntryDefinition> table;
372	CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
373
374	for (uint32_t i = 0; i < kEntryCount; ++i) {
375		Entry* entry = new Entry(i);
376		CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
377	}
378
379	CPPUNIT_ASSERT_EQUAL(table.CountElements(), kEntryCount);
380	CPPUNIT_ASSERT(table.Lookup(2) != NULL);
381
382	Entry* head = table.Clear(true);
383	CPPUNIT_ASSERT(head != NULL);
384
385	CPPUNIT_ASSERT_EQUAL(table.CountElements(), 0);
386	CPPUNIT_ASSERT_EQUAL(table.Lookup(2), NULL);
387	CPPUNIT_ASSERT_EQUAL(table.GetIterator().HasNext(), false);
388
389	size_t items_returned = 0;
390	while (head != NULL) {
391		Entry* next = head->Next();
392		delete head;
393		head = next;
394
395		++items_returned;
396	}
397
398	CPPUNIT_ASSERT_EQUAL(items_returned, kEntryCount);
399}
400