From 4f8fb9c70f814de796d61d7d85d4bf133afddafa Mon Sep 17 00:00:00 2001 From: Amlal El Mahrouss Date: Mon, 21 Apr 2025 17:47:16 +0200 Subject: dev, kernel: Made HeFS use a RB-Tree traversal algorithm. - ran format command. - a variation of a red-black tree traversal, with customized fallback mechanism. Signed-off-by: Amlal El Mahrouss --- dev/kernel/FSKit/HeFS.h | 6 +++--- dev/kernel/FirmwareKit/GPT.h | 4 ++-- dev/kernel/FirmwareKit/VEPM.h | 2 -- dev/kernel/GfxKit/FB.h | 24 ++++++++++++------------ dev/kernel/HALKit/AMD64/Storage/AHCI+Generic.cc | 2 +- dev/kernel/src/FS/HeFS.cc | 23 +++++++++++++++++------ dev/kernel/src/FS/NeFS.cc | 2 +- dev/kernel/src/UserProcessScheduler.cc | 2 +- dev/kernel/src/Utils.cc | 2 +- 9 files changed, 38 insertions(+), 29 deletions(-) (limited to 'dev/kernel') diff --git a/dev/kernel/FSKit/HeFS.h b/dev/kernel/FSKit/HeFS.h index d0311a38..4a50f438 100644 --- a/dev/kernel/FSKit/HeFS.h +++ b/dev/kernel/FSKit/HeFS.h @@ -163,8 +163,8 @@ struct PACKED HEFS_INDEX_NODE_DIRECTORY final Kernel::UInt64 fIndexNodeStart[kHeFSBlockCount]; /// @brief Start of the index node. Kernel::UInt64 fIndexNodeEnd[kHeFSBlockCount]; /// @brief End of the index node. - Kernel::UInt8 fColor; /// @brief Color of the node. (Red or Black). - Kernel::Lba fNext, fPrev, fChild, fParent; /// @brief Red-black tree pointers. + Kernel::UInt8 fColor; /// @brief Color of the node. (Red or Black). + Kernel::Lba fNext, fPrev, fChild, fParent; /// @brief Red-black tree pointers. }; namespace Kernel::Detail @@ -346,7 +346,7 @@ namespace Kernel class HeFileSystemParser final { public: - HeFileSystemParser() = default; + HeFileSystemParser() = default; ~HeFileSystemParser() = default; public: diff --git a/dev/kernel/FirmwareKit/GPT.h b/dev/kernel/FirmwareKit/GPT.h index dc2b5ce3..aab6b650 100644 --- a/dev/kernel/FirmwareKit/GPT.h +++ b/dev/kernel/FirmwareKit/GPT.h @@ -12,8 +12,8 @@ #define kSectorAlignGPT_PartTbl (420U) #define kSectorAlignGPT_PartEntry (72U) #define kMagicLenGPT (8U) -#define kMagicGPT ("EFI PART") // "EFI PART" -#define kGPTPartitionTableLBA (512U + sizeof(GPT_PARTITION_TABLE)) +#define kMagicGPT ("EFI PART") // "EFI PART" +#define kGPTPartitionTableLBA (512U + sizeof(GPT_PARTITION_TABLE)) namespace Kernel { diff --git a/dev/kernel/FirmwareKit/VEPM.h b/dev/kernel/FirmwareKit/VEPM.h index 742d5868..9d8fa4d4 100644 --- a/dev/kernel/FirmwareKit/VEPM.h +++ b/dev/kernel/FirmwareKit/VEPM.h @@ -11,6 +11,4 @@ /// @brief The Virtual Explicit Partition Map scheme extension. - - #endif // FIRMWAREKIT_VEPM_H \ No newline at end of file diff --git a/dev/kernel/GfxKit/FB.h b/dev/kernel/GfxKit/FB.h index ce5751dc..b01743ff 100644 --- a/dev/kernel/GfxKit/FB.h +++ b/dev/kernel/GfxKit/FB.h @@ -14,22 +14,22 @@ namespace Kernel class FBDeviceInterface; struct FBDevicePacket; - /// @brief Framebuffer device interface packet. - /// @details This structure is used to send and receive data from the framebuffer device. - /// @note The structure is packed to ensure that the data is aligned correctly for the device. + /// @brief Framebuffer device interface packet. + /// @details This structure is used to send and receive data from the framebuffer device. + /// @note The structure is packed to ensure that the data is aligned correctly for the device. struct PACKED FBDevicePacket final { - UInt32 fX; - UInt32 fY; - UInt32 fWidth; - UInt32 fHeight; - UInt32 fColor; - UInt32 fFlags; + UInt32 fX; + UInt32 fY; + UInt32 fWidth; + UInt32 fHeight; + UInt32 fColor; + UInt32 fFlags; }; - /// @brief Framebuffer device interface. - /// @details This class is used to send and receive data from the framebuffer device. - /// @note The class is derived from the IDeviceObject class. + /// @brief Framebuffer device interface. + /// @details This class is used to send and receive data from the framebuffer device. + /// @note The class is derived from the IDeviceObject class. class FBDeviceInterface NE_DEVICE { public: diff --git a/dev/kernel/HALKit/AMD64/Storage/AHCI+Generic.cc b/dev/kernel/HALKit/AMD64/Storage/AHCI+Generic.cc index 3955dd78..576c151b 100644 --- a/dev/kernel/HALKit/AMD64/Storage/AHCI+Generic.cc +++ b/dev/kernel/HALKit/AMD64/Storage/AHCI+Generic.cc @@ -286,7 +286,7 @@ STATIC Bool drv_std_init_ahci(UInt16& pi, BOOL& atapi) kSATADev.EnableMmio(); kSATADev.BecomeBusMaster(); - HbaMem* mem_ahci = (HbaMem*)kSATADev.Bar(kSATABar5); + HbaMem* mem_ahci = (HbaMem*)kSATADev.Bar(kSATABar5); HAL::mm_map_page((VoidPtr)mem_ahci, (VoidPtr)mem_ahci, HAL::kMMFlagsPresent | HAL::kMMFlagsWr | HAL::kMMFlagsPCD | HAL::kMMFlagsPwt); diff --git a/dev/kernel/src/FS/HeFS.cc b/dev/kernel/src/FS/HeFS.cc index 8d73b61e..2269896f 100644 --- a/dev/kernel/src/FS/HeFS.cc +++ b/dev/kernel/src/FS/HeFS.cc @@ -141,11 +141,22 @@ namespace Kernel start = dir->fNext; - if (start == 0) - start = dir->fChild; - - if (start == 0) - start = dir->fParent; + if (dir->fColor == kHeFSBlack) + { + if (dir->fParent != 0) + start = dir->fParent; + } + else + { + if (dir->fChild != 0) + start = dir->fChild; + else if (dir->fNext != 0) + start = dir->fNext; + else if (dir->fPrev != 0) + start = dir->fPrev; + else + start = dir->fParent; + } } delete dir; @@ -173,7 +184,7 @@ namespace Kernel NE_UNUSED(mnt); NE_UNUSED(parent_dir_name); NE_UNUSED(node); - + return NO; } } // namespace Detail diff --git a/dev/kernel/src/FS/NeFS.cc b/dev/kernel/src/FS/NeFS.cc index 115e4c82..e8e3804c 100644 --- a/dev/kernel/src/FS/NeFS.cc +++ b/dev/kernel/src/FS/NeFS.cc @@ -460,7 +460,7 @@ _Output Bool NeFileSystemParser::FormatGPT(_Input _Output DriveTrait* drive, _In NE_UNUSED(end_lba); NE_UNUSED(flags); NE_UNUSED(part_name); - + (void)(kout << "FormatGPT: Not implemented yet.\r"); return NO; diff --git a/dev/kernel/src/UserProcessScheduler.cc b/dev/kernel/src/UserProcessScheduler.cc index b45294b3..e96d2b27 100644 --- a/dev/kernel/src/UserProcessScheduler.cc +++ b/dev/kernel/src/UserProcessScheduler.cc @@ -428,7 +428,7 @@ namespace Kernel { return; } - + mTeam.mProcessList[process_id].Exit(0); } diff --git a/dev/kernel/src/Utils.cc b/dev/kernel/src/Utils.cc index 399be317..f5e61ddf 100644 --- a/dev/kernel/src/Utils.cc +++ b/dev/kernel/src/Utils.cc @@ -42,7 +42,7 @@ namespace Kernel return len; } - + Size rt_string_len(const Char* ptr) { SizeT cnt{0}; -- cgit v1.2.3