- Implement PFX_NTC_ROOT/PFX_NTC_CHILD deletions in RtlRemoveUnicodePrefix, if the...
[reactos.git] / reactos / lib / rtl / unicodeprefix.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * PURPOSE: Unicode Prefix implementation
5 * FILE: lib/rtl/unicodeprefix.c
6 * PROGRAMMER: Alex Ionescu (alex@relsoft.net)
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 /*
17 * FIXME: Try to find the official names and add to NDK
18 * Definitions come from fastfat driver.
19 */
20 typedef USHORT NODE_TYPE_CODE;
21 #define PFX_NTC_TABLE ((NODE_TYPE_CODE)0x0800)
22 #define PFX_NTC_ROOT ((NODE_TYPE_CODE)0x0801)
23 #define PFX_NTC_CHILD ((NODE_TYPE_CODE)0x0802)
24 #define PFX_NTC_CASE_MATCH ((NODE_TYPE_CODE)0x0803)
25
26 /* FUNCTIONS ***************************************************************/
27
28 /*STATIC*/
29 ULONG
30 NTAPI
31 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
32 {
33 ULONG Chars = UnicodeName->Length / sizeof(WCHAR);
34 ULONG i, NamesFound = 1;
35
36 /* Loop the string */
37 for (i = 0; i < (Chars - 1); i++)
38 {
39 /* Check if we found a backslash, meaning another name */
40 if (UnicodeName->Buffer[i] == '\\') NamesFound++;
41 }
42
43 /* Return the number of names found */
44 return NamesFound;
45 }
46
47 /*
48 * @unimplemented
49 */
50 PUNICODE_PREFIX_TABLE_ENTRY
51 NTAPI
52 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
53 PUNICODE_STRING FullName,
54 ULONG CaseInsensitiveIndex)
55 {
56 UNIMPLEMENTED;
57 return 0;
58 }
59
60 /*
61 * @implemented
62 */
63 VOID
64 NTAPI
65 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
66 {
67 /* Setup the table */
68 PrefixTable->NameLength = 0;
69 PrefixTable->LastNextEntry = NULL;
70 PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
71 PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
72 }
73
74 /*
75 * @unimplemented
76 */
77 BOOLEAN
78 NTAPI
79 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
80 PUNICODE_STRING Prefix,
81 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
82 {
83 /*
84 * implementation notes:
85 * - get name length (number of names)
86 * - init splay links
87 * - find a matching tree
88 * - if !found, insert a new NTC_ROOT entry and return TRUE;
89 * - if found, loop tree and compare strings:
90 * if equal, handle casematch/nomatch
91 * if greater or lesser equal, then add left/right childs accordingly
92 * - splay the tree
93 */
94 UNIMPLEMENTED;
95 return FALSE;
96 }
97
98 /*
99 * @implemented
100 */
101 PUNICODE_PREFIX_TABLE_ENTRY
102 NTAPI
103 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
104 BOOLEAN Restart)
105 {
106 PRTL_SPLAY_LINKS SplayLinks;
107 PUNICODE_PREFIX_TABLE_ENTRY Entry;
108 PUNICODE_PREFIX_TABLE_ENTRY CaseMatchEntry;
109
110 /* We might need this entry 2/3rd of the time, so cache it now */
111 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
112
113 /* Check if this is a restart or if we don't have a last entry */
114 if ((Restart) || !(PrefixTable->LastNextEntry))
115 {
116 /* Get the next entry and validate it */
117 Entry = PrefixTable->NextPrefixTree;
118 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
119
120 /* Now get the Splay Tree Links */
121 SplayLinks = &Entry->Links;
122
123 /* Loop until we get the first node in the tree */
124 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
125
126 /* Get the entry from it */
127 Entry = CONTAINING_RECORD(SplayLinks,
128 UNICODE_PREFIX_TABLE_ENTRY,
129 Links);
130 }
131 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
132 {
133 /* If the last entry was a Case Match, then return it */
134 Entry = CaseMatchEntry;
135 }
136 else
137 {
138 /* Find the successor */
139 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
140 if (!SplayLinks)
141 {
142 /* Didn't find one, we'll have to search the tree */
143 SplayLinks = &PrefixTable->LastNextEntry->Links;
144
145 /* Get the topmost node (root) */
146 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
147 Entry = CONTAINING_RECORD(SplayLinks,
148 UNICODE_PREFIX_TABLE_ENTRY,
149 Links);
150
151 /* Get its tree and make sure somethign is in it */
152 Entry = Entry->NextPrefixTree;
153 if (Entry->NameLength <= 0) return NULL;
154
155 /* Select these new links and find the first node */
156 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
157 }
158
159 /* Get the entry from it */
160 Entry = CONTAINING_RECORD(SplayLinks,
161 UNICODE_PREFIX_TABLE_ENTRY,
162 Links);
163 }
164
165 /* Save this entry as the last one returned, and return it */
166 PrefixTable->LastNextEntry = Entry;
167 return Entry;
168 }
169
170 /*
171 * @unimplemented
172 */
173 VOID
174 NTAPI
175 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
176 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
177 {
178 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
179 PRTL_SPLAY_LINKS SplayLinks;
180
181 /* Erase the last entry */
182 PrefixTable->LastNextEntry = NULL;
183
184 /* Check if this was a Case Match Entry */
185 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
186 {
187 /* Get the case match entry */
188 Entry = PrefixTableEntry->CaseMatch;
189
190 /* Now loop until we find one referencing what the caller sent */
191 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
192
193 /* We found the entry that was sent, link them to delete this entry */
194 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
195 }
196 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
197 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
198 {
199 /* Check if this entry is a case match */
200 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
201 {
202 /* FIXME */
203 }
204 else
205 {
206 /* It's not a case match, so we'll delete the actual entry */
207 SplayLinks = &PrefixTableEntry->Links;
208
209 /* Find the root entry */
210 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
211 Entry = CONTAINING_RECORD(SplayLinks,
212 UNICODE_PREFIX_TABLE_ENTRY,
213 Links);
214
215 /* Delete the entry and check if the whole tree is gone */
216 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
217 if (!SplayLinks)
218 {
219 /* The tree is also gone now, find the entry referencing us */
220 RefEntry = Entry->NextPrefixTree;
221 while (RefEntry->NextPrefixTree != Entry)
222 {
223 /* Not this one, move to the next entry */
224 RefEntry = RefEntry->NextPrefixTree;
225 }
226
227 /* Link them so this entry stops being referenced */
228 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
229 }
230 else if (&Entry->Links != SplayLinks)
231 {
232 /* The tree is still here, but we got moved to a new one */
233 NewEntry = CONTAINING_RECORD(SplayLinks,
234 UNICODE_PREFIX_TABLE_ENTRY,
235 Links);
236
237 /* Find the entry referencing us */
238 RefEntry = Entry->NextPrefixTree;
239 while (RefEntry->NextPrefixTree != Entry)
240 {
241 /* Not this one, move to the next entry */
242 RefEntry = RefEntry->NextPrefixTree;
243 }
244
245 /* Since we got moved, make us the new root entry */
246 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
247
248 /* Link us with the entry referencing the old root */
249 RefEntry->NextPrefixTree = NewEntry;
250
251 /* And link us with the old tree */
252 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
253
254 /* Set the old tree as a child */
255 Entry->NodeTypeCode = PFX_NTC_CHILD;
256 Entry->NextPrefixTree = NULL;
257 }
258 }
259 }
260 }
261
262 /* EOF */