hrev53793 adds 1 changeset to branch 'master'
old head: e53e22439c95a901967011ea890a43515a6207c4
new head: aa7ac127f80b67b3b4fa0efae312f39f782e00a2
overview:
https://git.haiku-os.org/haiku/log/?qt=range&q=aa7ac127f80b+%5Ee53e22439c95
----------------------------------------------------------------------------
aa7ac127f80b: tests/kernel: Add tests for BOpenHashTable
Linking libkernelutilstest.so with libbe to for use of BObjectList in
the tests.
Change-Id: I1abb991e240dd522821a71ef54d22a1ca7957283
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2165
Reviewed-by: Adrien Destugues <pulkomandy@xxxxxxxxx>
[ Kyle Ambroff-Kao <kyle@xxxxxxxxxxxxxx> ]
----------------------------------------------------------------------------
Revision: hrev53793
Commit: aa7ac127f80b67b3b4fa0efae312f39f782e00a2
URL: https://git.haiku-os.org/haiku/commit/?id=aa7ac127f80b
Author: Kyle Ambroff-Kao <kyle@xxxxxxxxxxxxxx>
Date: Sun Jan 26 10:11:49 2020 UTC
Committer: waddlesplash <waddlesplash@xxxxxxxxx>
Commit-Date: Thu Jan 30 00:30:00 2020 UTC
----------------------------------------------------------------------------
4 files changed, 353 insertions(+), 4 deletions(-)
.../system/kernel/util/BOpenHashTableTest.cpp | 324 +++++++++++++++++++
.../system/kernel/util/BOpenHashTableTest.h | 24 ++
src/tests/system/kernel/util/Jamfile | 5 +-
.../system/kernel/util/KernelUtilsTestAddon.cpp | 4 +-
----------------------------------------------------------------------------
diff --git a/src/tests/system/kernel/util/BOpenHashTableTest.cpp
b/src/tests/system/kernel/util/BOpenHashTableTest.cpp
new file mode 100644
index 0000000000..08922aab19
--- /dev/null
+++ b/src/tests/system/kernel/util/BOpenHashTableTest.cpp
@@ -0,0 +1,324 @@
+#include <cppunit/TestAssert.h>
+#include <cppunit/TestCaller.h>
+#include <cppunit/TestSuite.h>
+#include <TestShell.h>
+
+#include <os/support/ObjectList.h>
+#include <shared/AutoDeleter.h>
+#include <util/OpenHashTable.h>
+
+#include "BOpenHashTableTest.h"
+
+
+namespace {
+
+class Entry {
+public:
+ Entry(uint32_t value)
+ :
+ fValue(value),
+ fNext(NULL)
+ {
+ }
+
+ const uint32_t Value() const
+ {
+ return fValue;
+ }
+
+ Entry* Next() const
+ {
+ return fNext;
+ }
+
+private:
+ uint32_t fValue;
+ Entry *fNext;
+
+ friend class EntryDefinition;
+};
+
+
+class EntryDefinition {
+public:
+ typedef uint32_t KeyType;
+ typedef Entry ValueType;
+
+ size_t HashKey(const KeyType& key) const
+ {
+ return key;
+ }
+
+ size_t Hash(Entry* entry) const
+ {
+ return entry->fValue;
+ }
+
+ bool Compare(const KeyType& key, Entry* entry) const
+ {
+ return key == entry->fValue;
+ }
+
+ Entry*& GetLink(Entry* entry) const
+ {
+ return entry->fNext;
+ }
+};
+
+}
+
+
+CppUnit::Test* BOpenHashTableTest::Suite()
+{
+ CppUnit::TestSuite* suite = new CppUnit::TestSuite("BOpenHashTable");
+
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Insert test",
+ &BOpenHashTableTest::InsertTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Iterate and count
test",
+
&BOpenHashTableTest::IterateAndCountTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Lookup test",
+ &BOpenHashTableTest::LookupTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Resize test",
+ &BOpenHashTableTest::ResizeTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Remove test",
+ &BOpenHashTableTest::RemoveTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Duplicate insert
test",
+
&BOpenHashTableTest::DuplicateInsertTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Disable auto
expand",
+
&BOpenHashTableTest::DisableAutoExpandTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Init with zero
size",
+
&BOpenHashTableTest::InitWithZeroSizeTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Clear test",
+ &BOpenHashTableTest::ClearTest));
+ suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
+ "BOpenHashTable::Clear and return
test",
+
&BOpenHashTableTest::ClearAndReturnTest));
+
+ return suite;
+}
+
+
+BOpenHashTableTest::BOpenHashTableTest(std::string name)
+ : BTestCase(name)
+{
+}
+
+
+void BOpenHashTableTest::InsertTest()
+{
+ Entry entry(123);
+
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
+
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
+}
+
+
+void BOpenHashTableTest::IterateAndCountTest() {
+ const size_t kEntryCount = 20;
+
+ BObjectList<Entry> entries(20, true);
+
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(kEntryCount * 2), B_OK);
+
+ for (uint32_t i = 0; i < kEntryCount; ++i) {
+ Entry* entry = new Entry(i);
+ entries.AddItem(entry);
+ CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
+ }
+
+ // Verify that the table contains the expected values.
+ uint64_t map = 0;
+ BOpenHashTable<EntryDefinition>::Iterator iterator =
table.GetIterator();
+ while (iterator.HasNext()) {
+ Entry* entry = iterator.Next();
+ CPPUNIT_ASSERT_EQUAL(0, map & (1 << entry->Value()));
+ }
+
+ CPPUNIT_ASSERT_EQUAL(map, (1 << kEntryCount) - 1);
+ CPPUNIT_ASSERT_EQUAL(kEntryCount, table.CountElements());
+}
+
+
+void BOpenHashTableTest::ResizeTest()
+{
+ // This is the same as IterateAndCountTest, except that the table will
+ // be resized mid insertion.
+ const size_t kEntryCount = 20;
+ BObjectList<Entry> entries(20, true);
+ BOpenHashTable<EntryDefinition> table;
+
+ // Start off with capacity for 8 elements. This will mean that the table
+ // will be resized in the loop below since we are inserting 20 elements.
+ CPPUNIT_ASSERT_EQUAL(table.Init(8), B_OK);
+
+ for (uint32_t i = 0; i < kEntryCount; ++i) {
+ Entry* entry = new Entry(i);
+ entries.AddItem(entry);
+ CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
+ }
+
+ // Verify that after resize the expected elements are present within
+ // the table.
+ uint64_t map = 0;
+ BOpenHashTable<EntryDefinition>::Iterator iterator =
table.GetIterator();
+ while (iterator.HasNext()) {
+ Entry* entry = iterator.Next();
+ CPPUNIT_ASSERT_EQUAL(0, map & (1 << entry->Value()));
+ map |= (1 << entry->Value());
+ }
+
+ CPPUNIT_ASSERT_EQUAL(map, (1 << kEntryCount) - 1);
+ CPPUNIT_ASSERT_EQUAL(kEntryCount, table.CountElements());
+}
+
+
+void BOpenHashTableTest::LookupTest() {
+ Entry entry(123);
+
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
+
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+}
+
+
+void BOpenHashTableTest::RemoveTest() {
+ Entry entry(123);
+
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
+
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+
+ table.Remove(&entry);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), NULL);
+}
+
+
+void BOpenHashTableTest::DuplicateInsertTest()
+{
+ Entry entry(123);
+
+ BOpenHashTable<EntryDefinition, true, true> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
+
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+
+ CPPUNIT_ASSERT_DEBUGGER(table.Insert(&entry));
+
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+
+ // The item can basically never be removed now since there is a cycle,
+ // but we'll break into the debugger on remove when that happens as
well.
+ CPPUNIT_ASSERT_DEBUGGER(table.Remove(&entry));
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+
+ CPPUNIT_ASSERT_DEBUGGER(table.Remove(&entry));
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+}
+
+
+void BOpenHashTableTest::DisableAutoExpandTest()
+{
+ // Insert multiple items into a table with a fixed size of 1. This
+ // essentially turns this BOpenHashTable into a linked list, since
resize
+ // will never occur.
+ Entry entry1(123);
+ Entry entry2(456);
+
+ BOpenHashTable<EntryDefinition, false> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(1), B_OK);
+
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry1), B_OK);
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry2), B_OK);
+ CPPUNIT_ASSERT_EQUAL(table.CountElements(), 2);
+}
+
+
+void BOpenHashTableTest::InitWithZeroSizeTest()
+{
+ Entry entry(123);
+
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
+
+ CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
+}
+
+
+void BOpenHashTableTest::ClearTest()
+{
+ const size_t kEntryCount = 3;
+
+ BObjectList<Entry> entries(20, true);
+
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
+
+ for (uint32_t i = 0; i < kEntryCount; ++i) {
+ Entry* entry = new Entry(i);
+ entries.AddItem(entry);
+ CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
+ }
+
+ CPPUNIT_ASSERT_EQUAL(table.CountElements(), kEntryCount);
+ CPPUNIT_ASSERT(table.Lookup(2) != NULL);
+
+ CPPUNIT_ASSERT_EQUAL(table.Clear(false), NULL);
+ CPPUNIT_ASSERT_EQUAL(table.CountElements(), 0);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(2), NULL);
+ CPPUNIT_ASSERT_EQUAL(table.GetIterator().HasNext(), false);
+}
+
+
+void BOpenHashTableTest::ClearAndReturnTest()
+{
+ // Same as ClearTest(), except that Clear(true) is called, which tells
+ // the BOpenHashTable<T> to return a linked list of entries before
clearing
+ // the table.
+ const size_t kEntryCount = 3;
+ BOpenHashTable<EntryDefinition> table;
+ CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
+
+ for (uint32_t i = 0; i < kEntryCount; ++i) {
+ Entry* entry = new Entry(i);
+ CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
+ }
+
+ CPPUNIT_ASSERT_EQUAL(table.CountElements(), kEntryCount);
+ CPPUNIT_ASSERT(table.Lookup(2) != NULL);
+
+ Entry* head = table.Clear(true);
+ CPPUNIT_ASSERT(head != NULL);
+
+ CPPUNIT_ASSERT_EQUAL(table.CountElements(), 0);
+ CPPUNIT_ASSERT_EQUAL(table.Lookup(2), NULL);
+ CPPUNIT_ASSERT_EQUAL(table.GetIterator().HasNext(), false);
+
+ size_t items_returned = 0;
+ while (head != NULL) {
+ Entry* next = head->Next();
+ delete head;
+ head = next;
+
+ ++items_returned;
+ }
+
+ CPPUNIT_ASSERT_EQUAL(items_returned, kEntryCount);
+}
diff --git a/src/tests/system/kernel/util/BOpenHashTableTest.h
b/src/tests/system/kernel/util/BOpenHashTableTest.h
new file mode 100644
index 0000000000..a5500dcdfa
--- /dev/null
+++ b/src/tests/system/kernel/util/BOpenHashTableTest.h
@@ -0,0 +1,24 @@
+#ifndef BOPENHASHTABLE_TEST_H
+#define BOPENHASHTABLE_TEST_H
+
+#include <TestCase.h>
+
+class BOpenHashTableTest : public BTestCase {
+public:
+ BOpenHashTableTest(std::string name = "");
+
+ void InsertTest();
+ void IterateAndCountTest();
+ void ResizeTest();
+ void LookupTest();
+ void RemoveTest();
+ void DuplicateInsertTest();
+ void DisableAutoExpandTest();
+ void InitWithZeroSizeTest();
+ void ClearTest();
+ void ClearAndReturnTest();
+
+ static CppUnit::Test* Suite();
+};
+
+#endif // BOPENHASHTABLE_TEST_H
diff --git a/src/tests/system/kernel/util/Jamfile
b/src/tests/system/kernel/util/Jamfile
index 4001121d37..7b42652253 100644
--- a/src/tests/system/kernel/util/Jamfile
+++ b/src/tests/system/kernel/util/Jamfile
@@ -6,16 +6,15 @@ UsePrivateHeaders [ FDirName kernel util ] ;
UsePrivateHeaders [ FDirName kernel ] ;
UseHeaders [ FDirName $(HAIKU_TOP) src tests kits app ] ;
-# Two versions of the test lib are not really needed until
-# we start linking to Be libraries, but it doesn't hurt...
UnitTestLib libkernelutilstest.so
: KernelUtilsTestAddon.cpp
# AVLTreeMapTest.cpp
+ BOpenHashTableTest.cpp
SinglyLinkedListTest.cpp
DoublyLinkedListTest.cpp
VectorMapTest.cpp
VectorSetTest.cpp
VectorTest.cpp
- : [ TargetLibstdc++ ]
+ : [ TargetLibstdc++ ] be
;
diff --git a/src/tests/system/kernel/util/KernelUtilsTestAddon.cpp
b/src/tests/system/kernel/util/KernelUtilsTestAddon.cpp
index 945de0a6c2..ad43486ab6 100644
--- a/src/tests/system/kernel/util/KernelUtilsTestAddon.cpp
+++ b/src/tests/system/kernel/util/KernelUtilsTestAddon.cpp
@@ -2,8 +2,9 @@
#include <TestSuiteAddon.h>
//#include "AVLTreeMapTest.h"
-#include "SinglyLinkedListTest.h"
+#include "BOpenHashTableTest.h"
#include "DoublyLinkedListTest.h"
+#include "SinglyLinkedListTest.h"
#include "VectorMapTest.h"
#include "VectorSetTest.h"
#include "VectorTest.h"
@@ -12,6 +13,7 @@
BTestSuite* getTestSuite() {
BTestSuite *suite = new BTestSuite("KernelUtils");
// suite->addTest("AVLTreeMap", AVLTreeMapTest::Suite());
+ suite->addTest("BOpenHashTable", BOpenHashTableTest::Suite());
suite->addTest("SinglyLinkedList", SinglyLinkedListTest::Suite());
suite->addTest("DoublyLinkedList", DoublyLinkedListTest::Suite());
suite->addTest("VectorMap", VectorMapTest::Suite());
