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 <amlal@nekernel.org>

9 files changed, 38 insertions, 29 deletions

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<FBDevicePacket*>
 	{
 	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};