[haiku-commits] haiku: hrev53793 - src/tests/system/kernel/util

  • From: waddlesplash <waddlesplash@xxxxxxxxx>
  • To: haiku-commits@xxxxxxxxxxxxx
  • Date: Wed, 29 Jan 2020 19:30:04 -0500 (EST)

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());


Other related posts:

  • » [haiku-commits] haiku: hrev53793 - src/tests/system/kernel/util - waddlesplash