- Implement simple case of RtlInsertUnicodePrefix where a new node entry needs to...
[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) DONE
86 * - init splay links DONE
87 * - find a matching tree DONE
88 * - if !found, insert a new NTC_ROOT entry and return TRUE; DONE
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 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry;
95 ULONG NameCount;
96
97 /* Find out how many names there are */
98 NameCount = ComputeUnicodeNameLength(Prefix);
99
100 /* Set up the initial entry data */
101 PrefixTableEntry->NameLength = NameCount;
102 PrefixTableEntry->Prefix = Prefix;
103 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
104
105 /* Find the right spot where to insert this entry */
106 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
107 CurrentEntry = PreviousEntry->NextPrefixTree;
108 while (CurrentEntry->NameLength > NameCount)
109 {
110 /* Not a match, move to the next entry */
111 PreviousEntry = CurrentEntry;
112 CurrentEntry = CurrentEntry->NextPrefixTree;
113 }
114
115 /* Check if we did find a tree by now */
116 if (CurrentEntry->NameLength != NameCount)
117 {
118 /* We didn't, so insert a new entry in the list */
119 PreviousEntry->NextPrefixTree = PrefixTableEntry;
120 PrefixTableEntry->NextPrefixTree = CurrentEntry;
121
122 /* This is now a root entry with case match */
123 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
124 PrefixTableEntry->CaseMatch = PrefixTableEntry;
125
126 /* Quick return */
127 return TRUE;
128 }
129
130 /* FIXME */
131 UNIMPLEMENTED;
132 return FALSE;
133 }
134
135 /*
136 * @implemented
137 */
138 PUNICODE_PREFIX_TABLE_ENTRY
139 NTAPI
140 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
141 BOOLEAN Restart)
142 {
143 PRTL_SPLAY_LINKS SplayLinks;
144 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
145
146 /* We might need this entry 2/3rd of the time, so cache it now */
147 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
148
149 /* Check if this is a restart or if we don't have a last entry */
150 if ((Restart) || !(PrefixTable->LastNextEntry))
151 {
152 /* Get the next entry and validate it */
153 Entry = PrefixTable->NextPrefixTree;
154 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
155
156 /* Now get the Splay Tree Links */
157 SplayLinks = &Entry->Links;
158
159 /* Loop until we get the first node in the tree */
160 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
161
162 /* Get the entry from it */
163 Entry = CONTAINING_RECORD(SplayLinks,
164 UNICODE_PREFIX_TABLE_ENTRY,
165 Links);
166 }
167 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
168 {
169 /* If the last entry was a Case Match, then return it */
170 Entry = CaseMatchEntry;
171 }
172 else
173 {
174 /* Find the successor */
175 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
176 if (!SplayLinks)
177 {
178 /* Didn't find one, we'll have to search the tree */
179 SplayLinks = &PrefixTable->LastNextEntry->Links;
180
181 /* Get the topmost node (root) */
182 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
183 Entry = CONTAINING_RECORD(SplayLinks,
184 UNICODE_PREFIX_TABLE_ENTRY,
185 Links);
186
187 /* Get its tree and make sure somethign is in it */
188 Entry = Entry->NextPrefixTree;
189 if (Entry->NameLength <= 0) return NULL;
190
191 /* Select these new links and find the first node */
192 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
193 }
194
195 /* Get the entry from it */
196 Entry = CONTAINING_RECORD(SplayLinks,
197 UNICODE_PREFIX_TABLE_ENTRY,
198 Links);
199 }
200
201 /* Save this entry as the last one returned, and return it */
202 PrefixTable->LastNextEntry = Entry;
203 return Entry;
204 }
205
206 /*
207 * @implemented
208 */
209 VOID
210 NTAPI
211 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
212 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
213 {
214 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
215 PRTL_SPLAY_LINKS SplayLinks;
216
217 /* Erase the last entry */
218 PrefixTable->LastNextEntry = NULL;
219
220 /* Check if this was a Case Match Entry */
221 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
222 {
223 /* Get the case match entry */
224 Entry = PrefixTableEntry->CaseMatch;
225
226 /* Now loop until we find one referencing what the caller sent */
227 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
228
229 /* We found the entry that was sent, link them to delete this entry */
230 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
231 }
232 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
233 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
234 {
235 /* Check if this entry is a case match */
236 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
237 {
238 /* Get the case match entry */
239 Entry = PrefixTableEntry->CaseMatch;
240
241 /* Now loop until we find one referencing what the caller sent */
242 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
243
244 /* We found the entry that was sent, link them to delete this entry */
245 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
246
247 /* Copy the data */
248 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
249 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
250 Entry->Links = PrefixTableEntry->Links;
251
252 /* Now check if we are a root entry */
253 if (RtlIsRoot(&PrefixTableEntry->Links))
254 {
255 /* We are, so make this entry root as well */
256 Entry->Links.Parent = &Entry->Links;
257
258 /* Find the entry referencing us */
259 RefEntry = Entry->NextPrefixTree;
260 while (RefEntry->NextPrefixTree != Entry)
261 {
262 /* Not this one, move to the next entry */
263 RefEntry = RefEntry->NextPrefixTree;
264 }
265
266 /* Link them to us now */
267 RefEntry->NextPrefixTree = Entry;
268 }
269 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
270 {
271 /* We were the left child, so make us as well */
272 Entry->Links.LeftChild = &Entry->Links;
273 }
274 else
275 {
276 /* We were the right child, so make us as well */
277 Entry->Links.RightChild = &Entry->Links;
278 }
279
280 /* Check if we have a left child */
281 if (RtlLeftChild(&Entry->Links))
282 {
283 /* Update its parent link */
284 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
285 }
286 /* Check if we have a right child */
287 if (RtlRightChild(&Entry->Links))
288 {
289 /* Update its parent link */
290 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
291 }
292 }
293 else
294 {
295 /* It's not a case match, so we'll delete the actual entry */
296 SplayLinks = &PrefixTableEntry->Links;
297
298 /* Find the root entry */
299 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
300 Entry = CONTAINING_RECORD(SplayLinks,
301 UNICODE_PREFIX_TABLE_ENTRY,
302 Links);
303
304 /* Delete the entry and check if the whole tree is gone */
305 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
306 if (!SplayLinks)
307 {
308 /* The tree is also gone now, find the entry referencing us */
309 RefEntry = Entry->NextPrefixTree;
310 while (RefEntry->NextPrefixTree != Entry)
311 {
312 /* Not this one, move to the next entry */
313 RefEntry = RefEntry->NextPrefixTree;
314 }
315
316 /* Link them so this entry stops being referenced */
317 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
318 }
319 else if (&Entry->Links != SplayLinks)
320 {
321 /* The tree is still here, but we got moved to a new one */
322 NewEntry = CONTAINING_RECORD(SplayLinks,
323 UNICODE_PREFIX_TABLE_ENTRY,
324 Links);
325
326 /* Find the entry referencing us */
327 RefEntry = Entry->NextPrefixTree;
328 while (RefEntry->NextPrefixTree != Entry)
329 {
330 /* Not this one, move to the next entry */
331 RefEntry = RefEntry->NextPrefixTree;
332 }
333
334 /* Since we got moved, make us the new root entry */
335 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
336
337 /* Link us with the entry referencing the old root */
338 RefEntry->NextPrefixTree = NewEntry;
339
340 /* And link us with the old tree */
341 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
342
343 /* Set the old tree as a child */
344 Entry->NodeTypeCode = PFX_NTC_CHILD;
345 Entry->NextPrefixTree = NULL;
346 }
347 }
348 }
349 }
350
351 /* EOF */