From: Alex Ionescu <aionescu@gmail.com>
Date: Mon, 7 Nov 2005 22:05:46 +0000 (+0000)
Subject: - Finished implementing RtlInsertUnicodePrefix: handle greater and less than insertions.
X-Git-Tag: backups/ros-branch-0_2_9@19949~852
X-Git-Url: https://git.reactos.org/?p=reactos.git;a=commitdiff_plain;h=9810da1c6af9cc70e14f4ed62f7021f13671a985;hp=de2ccc1c5138fd78a7a30df233ecc4f38c930d7c;ds=sidebyside

- Finished implementing RtlInsertUnicodePrefix: handle greater and less than insertions.

svn path=/trunk/; revision=19046
---

diff --git a/reactos/include/ndk/rtlfuncs.h b/reactos/include/ndk/rtlfuncs.h
index 7c2dd688013..0a5ddd4720b 100644
--- a/reactos/include/ndk/rtlfuncs.h
+++ b/reactos/include/ndk/rtlfuncs.h
@@ -36,13 +36,29 @@
 #define RtlParent(Links) \
     (PRTL_SPLAY_LINKS)(Links)->Parent
 
-#define RtlInitializeSplayLinks(Links)       \
-    PRTL_SPLAY_LINKS _SplayLinks;            \
-    _SplayLinks = (PRTL_SPLAY_LINKS)(Links); \
-    _SplayLinks->Parent = _SplayLinks;       \
-    _SplayLinks->LeftChild = NULL;           \
+#define RtlInitializeSplayLinks(Links)                  \
+    PRTL_SPLAY_LINKS _SplayLinks;                       \
+    _SplayLinks = (PRTL_SPLAY_LINKS)(Links);            \
+    _SplayLinks->Parent = _SplayLinks;                  \
+    _SplayLinks->LeftChild = NULL;                      \
     _SplayLinks->RightChild = NULL;
 
+#define RtlInsertAsLeftChild(ParentLinks,ChildLinks)    \
+    PRTL_SPLAY_LINKS _SplayParent;                      \
+    PRTL_SPLAY_LINKS _SplayChild;                       \
+    _SplayParent = (PRTL_SPLAY_LINKS)(ParentLinks);     \
+    _SplayChild = (PRTL_SPLAY_LINKS)(ChildLinks);       \
+    _SplayParent->LeftChild = _SplayChild;              \
+    _SplayChild->Parent = _SplayParent;
+
+#define RtlInsertAsRightChild(ParentLinks,ChildLinks)   \
+    PRTL_SPLAY_LINKS _SplayParent;                      \
+    PRTL_SPLAY_LINKS _SplayChild;                       \
+    _SplayParent = (PRTL_SPLAY_LINKS)(ParentLinks);     \
+    _SplayChild = (PRTL_SPLAY_LINKS)(ChildLinks);       \
+    _SplayParent->RightChild = _SplayChild;             \
+    _SplayChild->Parent = _SplayParent;
+
 /* PROTOTYPES ****************************************************************/
 
 /*
diff --git a/reactos/lib/rtl/unicodeprefix.c b/reactos/lib/rtl/unicodeprefix.c
index 4d8a15c6b1a..4607514e1d2 100644
--- a/reactos/lib/rtl/unicodeprefix.c
+++ b/reactos/lib/rtl/unicodeprefix.c
@@ -139,7 +139,7 @@ RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
 }
 
 /*
- * @unimplemented
+ * @implemented
  */
 BOOLEAN
 NTAPI
@@ -147,17 +147,6 @@ RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
                        PUNICODE_STRING Prefix,
                        PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
 {
-    /*
-     * implementation notes:
-     * - get name length (number of names) DONE
-     * - init splay links DONE
-     * - find a matching tree DONE
-     * - if !found, insert a new NTC_ROOT entry and return TRUE; DONE
-     * - if found, loop tree and compare strings: DONE
-     *   if equal, handle casematch/nomatch DONE
-     *   if greater or lesser equal, then add left/right childs accordingly
-     * - splay the tree DONE
-     */
     PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
     ULONG NameCount;
     RTL_GENERIC_COMPARE_RESULTS Result;
@@ -237,11 +226,49 @@ RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
         }
         else if (Result == GenericGreaterThan)
         {
-            /* TODO: Check out the left child and add us */
+            /* Check out if we have a left child */
+            if (RtlLeftChild(&Entry->Links))
+            {
+                /* We do, enter it and restart the loop */
+                SplayLinks = RtlLeftChild(&Entry->Links);
+                Entry = CONTAINING_RECORD(SplayLinks,
+                                          UNICODE_PREFIX_TABLE_ENTRY,
+                                          Links);
+            }
+            else
+            {
+                /* We don't, set this entry as a child */
+                PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
+                PrefixTableEntry->NextPrefixTree = NULL;
+                PrefixTableEntry->CaseMatch = PrefixTableEntry;
+
+                /* Insert us into the tree */
+                RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
+                break;
+            }
         }
         else
         {
-            /* TODO: Check out the right child and add us */
+            /* Check out if we have a right child */
+            if (RtlRightChild(&Entry->Links))
+            {
+                /* We do, enter it and restart the loop */
+                SplayLinks = RtlLeftChild(&Entry->Links);
+                Entry = CONTAINING_RECORD(SplayLinks,
+                                          UNICODE_PREFIX_TABLE_ENTRY,
+                                          Links);
+            }
+            else
+            {
+                /* We don't, set this entry as a child */
+                PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
+                PrefixTableEntry->NextPrefixTree = NULL;
+                PrefixTableEntry->CaseMatch = PrefixTableEntry;
+
+                /* Insert us into the tree */
+                RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
+                break;
+            }
         }
     }