Merge branch 'fmorgner/develop-BA-FS26/pit-device' into develop-BA-FS26

This changeset introduces a central device management system. The system
comprises the following components:

- kapi::devices::bus (type)

  A bus can be both a real (physically present inside the machine) or
  virtual (purely conceptual) bus. Busses form a hierarchy rooted in the
  virtual root_bus (accessible via `kapi::devices::get_root_bus`).
  Busses are derived from `kapi::devices::device`, and own devices. This
  means that a bus can be attached to another bus. This facilitates a
  uniform structure for device ownership. Each device needs to be
  attached to exactly one bus. Virtual devices, e.g. RAM disks, should
  be attached to the root root bus (via the `add_child` member
  function).

  Once a device, or bus, has been attached to a bus, it will be
  initialized (by means of a call to the `init` member function). Busses
  are responsible to initialize their children. If a bus has already
  been initialized, any newly attached children will automatically be
  initialized.

  During initialization, the `probe` member function of the bus under
  initialization weill be invoked. This allows a bus implementation to
  determine if the hardware, if any, is ready to be initialized and to
  also perform any required initialization steps.

  IMPORTANT: busses take ownership of their children in the form of a
  `unique_ptr`.

- kapi::devices (namespace)

  The functions `allocate_major_number`, `register_device`,
  `unregister_device`, and `find_device` form the device manager.

  The device manager is responsible for keeping a record of active
  devices, allowing O(log n) lookup of devices by major and minor, and
  O(n) lookup by name. Additionally, the device manager is responsible
  for handing out major numbers (via `allocate_major_number`) and
  keeping track of active devices. When a child is attached to a bus, it
  will also automatically be registered with the device manager.

  Lookup of devices via the device manager can be achieved by means of
  either overload of `find_device`.

  Devices should never ask the manager directly for a major number.
  Instead, a controller should be used, which requests a major number
  per device "class" (as in kind, not language class). For example, a
  RAM disk controller may request a single major number for all RAM
  disks it is going to create. When the controller creates a new device
  of a given "class", e.g. a RAM disk, it should then supply that major
  number to the new device instance.

  IMPORTANT: the device manager does not own the active devices. Rather
  it holds a `flat_map` indexed by `pair{major, minor}` and resolving to
  `kstd::observer_ptr<device>`.

- kstd::observer_ptr (type)

  An observer pointer is a simple vocabulary type to express the concept
  of having no ownership of the pointed-to object. In essence it is
  equivalent to a standard C-style pointer, but expresses semantics by
  virtue of being a separate type.

1 files changed, 359 insertions, 0 deletions

diff --git a/libs/kstd/tests/src/observer_ptr.cpp b/libs/kstd/tests/src/observer_ptr.cpp
new file mode 100644
index 0000000..006ebde
--- /dev/null
+++ b/libs/kstd/tests/src/observer_ptr.cpp
@@ -0,0 +1,359 @@
+#include <kstd/memory>
+#include <kstd/tests/os_panic.hpp>
+
+#include <catch2/catch_test_macros.hpp>
+
+#include <compare>
+#include <type_traits>
+#include <utility>
+
+namespace
+{
+  struct Base
+  {
+  };
+
+  struct Derived : Base
+  {
+  };
+
+  struct Element
+  {
+    int value{};
+
+    constexpr auto operator<=>(Element const &) const noexcept = default;
+  };
+}  // namespace
+
+SCENARIO("Observer Pointer initialization and construction", "[observer_ptr]")
+{
+  GIVEN("An empty context")
+  {
+    WHEN("constructing by default")
+    {
+      auto ptr = kstd::observer_ptr<int>{};
+
+      THEN("the observer pointer is null")
+      {
+        REQUIRE_FALSE(ptr);
+      }
+    }
+
+    WHEN("constructing from a nullptr")
+    {
+      auto ptr = kstd::observer_ptr<int>{nullptr};
+
+      THEN("the observer pointer is null")
+      {
+        REQUIRE_FALSE(ptr);
+      }
+    }
+
+    WHEN("constructing from a raw pointer")
+    {
+      auto value = 1;
+      auto ptr = kstd::observer_ptr{&value};
+
+      THEN("the observer pointer is not null")
+      {
+        REQUIRE(ptr);
+      }
+
+      THEN("the observer pointer points to the correct object")
+      {
+        REQUIRE(&*ptr == &value);
+      }
+    }
+
+    WHEN("copy constructing from an existing observer pointer")
+    {
+      auto value = 1;
+      auto ptr = kstd::observer_ptr{&value};
+      auto copy = ptr;
+
+      THEN("the new observer pointer points to the same object as the other observer pointer")
+      {
+        REQUIRE(&*copy == &value);
+      }
+    }
+
+    WHEN("copy constructing from an existing observer pointer with a compatible type")
+    {
+      auto value = Derived{};
+      auto ptr = kstd::observer_ptr<Derived>(&value);
+      kstd::observer_ptr<Base> copy = ptr;
+
+      THEN("the new observer pointer points to the same object as the other observer pointer")
+      {
+        REQUIRE(&*copy == &value);
+      }
+    }
+
+    WHEN("copy assigning from an existing observer pointer")
+    {
+      auto value = 1;
+      auto ptr = kstd::observer_ptr{&value};
+      auto copy = ptr;
+
+      THEN("the new observer pointer points to the same object as the other observer pointer")
+      {
+        REQUIRE(&*copy == &value);
+      }
+    }
+
+    WHEN("move constructing from an existing observer pointer")
+    {
+      auto value = 1;
+      auto ptr = kstd::observer_ptr{&value};
+      auto copy = std::move(ptr);
+
+      THEN("the new observer pointer points to the same object as the other observer pointer")
+      {
+        REQUIRE(&*copy == &value);
+      }
+    }
+
+    WHEN("move assigning from an existing observer pointer")
+    {
+      auto value = 1;
+      auto ptr = kstd::observer_ptr{&value};
+      auto copy = std::move(ptr);
+
+      THEN("the new observer pointer points to the same object as the other observer pointer")
+      {
+        REQUIRE(&*copy == &value);
+      }
+    }
+
+    WHEN("constructing an observer pointer using make_observer")
+    {
+      auto value = 1;
+      auto ptr = kstd::make_observer(&value);
+
+      THEN("the observer pointer points to the correct object")
+      {
+        REQUIRE(&*ptr == &value);
+      }
+
+      THEN("the observe pointer has the correct element type")
+      {
+        STATIC_REQUIRE(std::is_same_v<decltype(ptr), kstd::observer_ptr<int>>);
+      }
+    }
+  }
+}
+
+SCENARIO("Observer pointer modifiers", "[observer_ptr]")
+{
+  GIVEN("A non-null observer pointer")
+  {
+    auto value = 1;
+    auto ptr = kstd::observer_ptr{&value};
+
+    WHEN("releasing the observer pointer")
+    {
+      auto raw_ptr = ptr.release();
+
+      THEN("the observer pointer is null")
+      {
+        REQUIRE_FALSE(ptr);
+      }
+
+      THEN("the returned pointer points to the correct object")
+      {
+        REQUIRE(raw_ptr == &value);
+      }
+    }
+
+    WHEN("resetting the observer pointer to nullptr")
+    {
+      ptr.reset();
+
+      THEN("the observer pointer is null")
+      {
+        REQUIRE_FALSE(ptr);
+      }
+    }
+
+    WHEN("resetting the observer pointer to a new object")
+    {
+      auto other_value = 2;
+      ptr.reset(&other_value);
+
+      THEN("the observer pointer points to the new object")
+      {
+        REQUIRE(&*ptr == &other_value);
+      }
+    }
+
+    WHEN("swapping it with another observer pointer")
+    {
+      auto other_value = 2;
+      auto other_ptr = kstd::observer_ptr{&other_value};
+      ptr.swap(other_ptr);
+
+      THEN("the observer pointer points to the other object")
+      {
+        REQUIRE(&*ptr == &other_value);
+      }
+
+      THEN("the other observer pointer points to the original object")
+      {
+        REQUIRE(&*other_ptr == &value);
+      }
+    }
+
+    WHEN("using namespace-level swap to swap it with another observer pointer")
+    {
+      using std::swap;
+      auto other_value = 2;
+      auto other_ptr = kstd::observer_ptr{&other_value};
+      swap(ptr, other_ptr);
+
+      THEN("the observer pointer points to the other object")
+      {
+        REQUIRE(&*ptr == &other_value);
+      }
+
+      THEN("the other observer pointer points to the original object")
+      {
+        REQUIRE(&*other_ptr == &value);
+      }
+    }
+  }
+}
+
+SCENARIO("Observer pointer observers", "[observer_ptr]")
+{
+  GIVEN("A non-null observer pointer")
+  {
+    auto value = Element{1};
+    auto ptr = kstd::observer_ptr{&value};
+
+    WHEN("getting the raw pointer")
+    {
+      auto raw_ptr = ptr.get();
+
+      THEN("the raw pointer points to the correct object")
+      {
+        REQUIRE(raw_ptr == &value);
+      }
+    }
+
+    WHEN("dereferencing the observer pointer")
+    {
+      auto dereferenced = *ptr;
+
+      THEN("the dereferenced value is the correct value")
+      {
+        REQUIRE(dereferenced == value);
+      }
+    }
+
+    WHEN("writing through the observer pointer with the arrow operator")
+    {
+      ptr->value = 2;
+
+      THEN("the value is updated")
+      {
+        REQUIRE(value.value == 2);
+      }
+    }
+
+    WHEN("converting the observer pointer to a raw pointer")
+    {
+      auto raw_ptr = static_cast<Element *>(ptr);
+
+      THEN("the raw pointer points to the correct object")
+      {
+        REQUIRE(raw_ptr == &value);
+      }
+    }
+
+    WHEN("checking the observer pointer as a boolean")
+    {
+      THEN("it returns true")
+      {
+        REQUIRE(static_cast<bool>(ptr));
+      }
+    }
+  }
+
+  GIVEN("A null observer pointer")
+  {
+    auto ptr = kstd::observer_ptr<Element>{};
+
+    WHEN("checking the observer pointer as a boolean")
+    {
+      THEN("it returns false")
+      {
+        REQUIRE_FALSE(static_cast<bool>(ptr));
+      }
+    }
+
+    WHEN("dereferencing the observer pointer")
+    {
+      THEN("the observer pointer panics")
+      {
+        REQUIRE_THROWS_AS(*ptr, kstd::tests::os_panic);
+      }
+    }
+
+    WHEN("writing through the observer pointer with the arrow operator")
+    {
+      THEN("the observer pointer panics")
+      {
+        REQUIRE_THROWS_AS(ptr->value = 2, kstd::tests::os_panic);
+      }
+    }
+  }
+}
+
+SCENARIO("Observer pointer comparisons", "[observer_ptr]")
+{
+  GIVEN("Observer pointers to elements of an array")
+  {
+    int arr[] = {1, 2};
+    auto ptr1 = kstd::observer_ptr{&arr[0]};
+    auto ptr2 = kstd::observer_ptr{&arr[1]};
+
+    WHEN("comparing the same observer pointer")
+    {
+      THEN("they are equal")
+      {
+        REQUIRE(ptr1 == ptr1);
+        REQUIRE((ptr1 <=> ptr1) == std::strong_ordering::equal);
+      }
+    }
+
+    WHEN("comparing different observer pointers")
+    {
+      THEN("they are ordered correctly")
+      {
+        REQUIRE(ptr1 != ptr2);
+        REQUIRE(ptr1 < ptr2);
+        REQUIRE(ptr1 <= ptr2);
+        REQUIRE(ptr2 > ptr1);
+        REQUIRE(ptr2 >= ptr1);
+        REQUIRE((ptr1 <=> ptr2) == std::strong_ordering::less);
+        REQUIRE((ptr2 <=> ptr1) == std::strong_ordering::greater);
+      }
+    }
+  }
+
+  GIVEN("A null observer pointer")
+  {
+    auto ptr = kstd::observer_ptr<int>{};
+
+    WHEN("comparing with another null observer pointer")
+    {
+      auto other_ptr = kstd::observer_ptr<int>{};
+
+      THEN("they are equal")
+      {
+        REQUIRE(ptr == other_ptr);
+        REQUIRE((ptr <=> other_ptr) == std::strong_ordering::equal);
+      }
+    }
+  }
+}
\ No newline at end of file