--- trunk/reactos/include/ndk/rtlfuncs.h 2005-11-07 21:57:50 UTC (rev 19045)
+++ trunk/reactos/include/ndk/rtlfuncs.h 2005-11-07 22:05:46 UTC (rev 19046)
@@ -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 ****************************************************************/
/*
--- trunk/reactos/lib/rtl/unicodeprefix.c 2005-11-07 21:57:50 UTC (rev 19045)
+++ trunk/reactos/lib/rtl/unicodeprefix.c 2005-11-07 22:05:46 UTC (rev 19046)
@@ -139,7 +139,7 @@
}
/*
- * @unimplemented
+ * @implemented
*/
BOOLEAN
NTAPI
@@ -147,17 +147,6 @@
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 @@
}
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;
+ }
}
}