- Finish implementation of RtlRemoveUnicodePrefix
[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 * @implemented
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 /* Get the case match entry */
203 Entry = PrefixTableEntry->CaseMatch;
204
205 /* Now loop until we find one referencing what the caller sent */
206 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
207
208 /* We found the entry that was sent, link them to delete this entry */
209 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
210
211 /* Copy the data */
212 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
213 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
214 Entry->Links = PrefixTableEntry->Links;
215
216 /* Now check if we are a root entry */
217 if (RtlIsRoot(&PrefixTableEntry->Links))
218 {
219 /* We are, so make this entry root as well */
220 Entry->Links.Parent = &Entry->Links;
221
222 /* Find the entry referencing us */
223 RefEntry = Entry->NextPrefixTree;
224 while (RefEntry->NextPrefixTree != Entry)
225 {
226 /* Not this one, move to the next entry */
227 RefEntry = RefEntry->NextPrefixTree;
228 }
229
230 /* Link them to us now */
231 RefEntry->NextPrefixTree = Entry;
232 }
233 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
234 {
235 /* We were the left child, so make us as well */
236 Entry->Links.LeftChild = &Entry->Links;
237 }
238 else
239 {
240 /* We were the right child, so make us as well */
241 Entry->Links.RightChild = &Entry->Links;
242 }
243
244 /* Check if we have a left child */
245 if (RtlLeftChild(&Entry->Links))
246 {
247 /* Update its parent link */
248 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
249 }
250 /* Check if we have a right child */
251 if (RtlRightChild(&Entry->Links))
252 {
253 /* Update its parent link */
254 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
255 }
256 }
257 else
258 {
259 /* It's not a case match, so we'll delete the actual entry */
260 SplayLinks = &PrefixTableEntry->Links;
261
262 /* Find the root entry */
263 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
264 Entry = CONTAINING_RECORD(SplayLinks,
265 UNICODE_PREFIX_TABLE_ENTRY,
266 Links);
267
268 /* Delete the entry and check if the whole tree is gone */
269 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
270 if (!SplayLinks)
271 {
272 /* The tree is also gone now, find the entry referencing us */
273 RefEntry = Entry->NextPrefixTree;
274 while (RefEntry->NextPrefixTree != Entry)
275 {
276 /* Not this one, move to the next entry */
277 RefEntry = RefEntry->NextPrefixTree;
278 }
279
280 /* Link them so this entry stops being referenced */
281 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
282 }
283 else if (&Entry->Links != SplayLinks)
284 {
285 /* The tree is still here, but we got moved to a new one */
286 NewEntry = CONTAINING_RECORD(SplayLinks,
287 UNICODE_PREFIX_TABLE_ENTRY,
288 Links);
289
290 /* Find the entry referencing us */
291 RefEntry = Entry->NextPrefixTree;
292 while (RefEntry->NextPrefixTree != Entry)
293 {
294 /* Not this one, move to the next entry */
295 RefEntry = RefEntry->NextPrefixTree;
296 }
297
298 /* Since we got moved, make us the new root entry */
299 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
300
301 /* Link us with the entry referencing the old root */
302 RefEntry->NextPrefixTree = NewEntry;
303
304 /* And link us with the old tree */
305 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
306
307 /* Set the old tree as a child */
308 Entry->NodeTypeCode = PFX_NTC_CHILD;
309 Entry->NextPrefixTree = NULL;
310 }
311 }
312 }
313 }
314
315 /* EOF */