ReactOS 0.4.16-dev-257-g6aa11ac
splaysup.c
Go to the documentation of this file.
1/*++
2
3Copyright (c) 1989-2000 Microsoft Corporation
4
5Module Name:
6
7 PrefxSup.c
8
9Abstract:
10
11 This module implements the Fat Name lookup Suport routines
12
13
14--*/
15
16#include "fatprocs.h"
17
18//
19// The Bug check file id for this module
20//
21
22#define BugCheckFileId (FAT_BUG_CHECK_SPLAYSUP)
23
24//
25// The debug trace level for this module
26//
27
28#define Dbg (DEBUG_TRACE_SPLAYSUP)
29
30#ifdef ALLOC_PRAGMA
31#pragma alloc_text(PAGE, FatInsertName)
32#pragma alloc_text(PAGE, FatRemoveNames)
33#pragma alloc_text(PAGE, FatFindFcb)
34#pragma alloc_text(PAGE, FatCompareNames)
35#endif
36
37
38VOID
40 IN PIRP_CONTEXT IrpContext,
43 )
44
45/*++
46
47Routine Description:
48
49 This routine will insert a name in the splay tree pointed to
50 by RootNode.
51
52 The name must not already exist in the splay tree.
53
54Arguments:
55
56 RootNode - Supplies a pointer to the table.
57
58 Name - Contains the New name to enter.
59
60Return Value:
61
62 None.
63
64--*/
65
66{
67 COMPARISON Comparison;
69
70 PAGED_CODE();
71
73
75
76 //
77 // If we are the first entry in the tree, just become the root.
78 //
79
80 if (*RootNode == NULL) {
81
82 *RootNode = &Name->Links;
83
84 return;
85 }
86
88
89 while (TRUE) {
90
91 //
92 // Compare the prefix in the tree with the prefix we want
93 // to insert. Note that Oem here doesn't mean anything.
94 //
95
96 Comparison = CompareNames(&Node->Name.Oem, &Name->Name.Oem);
97
98 //
99 // We should never find the name in the table already.
100 //
101
102 if (Comparison == IsEqual) {
103
104 //
105 // Almost. If the removable media was taken to another machine and
106 // back, and we have something like:
107 //
108 // Old: abcdef~1 / abcdefxyz
109 // New: abcdef~1 / abcdefxyzxyz
110 //
111 // but a handle was kept open to abcdefxyz so we couldn't purge
112 // away the Fcb in the verify path ... opening abcdefxyzxyz will
113 // try to insert a duplicate shortname. Bang!
114 //
115 // Invalidate it and the horse it came in on. This new one wins.
116 // The old one is gone. Only if the old one is in normal state
117 // do we really have a problem.
118 //
119
120 if (Node->Fcb->FcbState == FcbGood) {
121
122#ifdef _MSC_VER
123#pragma prefast( suppress:28159, "things are seriously wrong if we get here" )
124#endif
126 }
127
128 //
129 // Note, once we zap the prefix links we need to restart our walk
130 // of the tree. Note that we aren't properly synchronized to
131 // recursively mark bad.
132 //
133
134 FatMarkFcbCondition( IrpContext, Node->Fcb, FcbBad, FALSE );
135 FatRemoveNames( IrpContext, Node->Fcb );
136
137 goto Restart;
138 }
139
140 //
141 // If the tree prefix is greater than the new prefix then
142 // we go down the left subtree
143 //
144
145 if (Comparison == IsGreaterThan) {
146
147 //
148 // We want to go down the left subtree, first check to see
149 // if we have a left subtree
150 //
151
152 if (RtlLeftChild(&Node->Links) == NULL) {
153
154 //
155 // there isn't a left child so we insert ourselves as the
156 // new left child
157 //
158
159 RtlInsertAsLeftChild(&Node->Links, &Name->Links);
160
161 //
162 // and exit the while loop
163 //
164
165 break;
166
167 } else {
168
169 //
170 // there is a left child so simply go down that path, and
171 // go back to the top of the loop
172 //
173
176 Links );
177 }
178
179 } else {
180
181 //
182 // The tree prefix is either less than or a proper prefix
183 // of the new string. We treat both cases a less than when
184 // we do insert. So we want to go down the right subtree,
185 // first check to see if we have a right subtree
186 //
187
188 if (RtlRightChild(&Node->Links) == NULL) {
189
190 //
191 // These isn't a right child so we insert ourselves as the
192 // new right child
193 //
194
195 RtlInsertAsRightChild(&Node->Links, &Name->Links);
196
197 //
198 // and exit the while loop
199 //
200
201 break;
202
203 } else {
204
205 //
206 // there is a right child so simply go down that path, and
207 // go back to the top of the loop
208 //
209
212 Links );
213 }
214
215 }
216 }
217
218 return;
219}
220
221VOID
223 IN PIRP_CONTEXT IrpContext,
224 IN PFCB Fcb
225 )
226
227/*++
228
229Routine Description:
230
231 This routine will remove the short name and any long names associated
232 with the files from their repsective splay tree.
233
234Arguments:
235
236 Name - Supplies the Fcb to process.
237
238Return Value:
239
240 None.
241
242--*/
243
244{
245 PDCB Parent;
246 PRTL_SPLAY_LINKS NewRoot;
247
248 PAGED_CODE();
249 UNREFERENCED_PARAMETER( IrpContext );
250
252
253 //
254 // We used to assert this condition, but it really isn't good. If
255 // someone rapidly renames a directory multiple times and we can't
256 // flush the lower fcbs fast enough (that didn't go away synch.)
257 // well, well hit some of them again.
258 //
259 // NT_ASSERT( FlagOn( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE ));
260 //
261
263
264 //
265 // Delete the node short name.
266 //
267
268 NewRoot = RtlDelete(&Fcb->ShortName.Links);
269
270 Parent->Specific.Dcb.RootOemNode = NewRoot;
271
272 //
273 // Now check for the presence of long name and delete it.
274 //
275
277
278 NewRoot = RtlDelete(&Fcb->LongName.Oem.Links);
279
280 Parent->Specific.Dcb.RootOemNode = NewRoot;
281
283
285 }
286
288
289 NewRoot = RtlDelete(&Fcb->LongName.Unicode.Links);
290
291 Parent->Specific.Dcb.RootUnicodeNode = NewRoot;
292
294
296 }
297
299 }
300
301 return;
302}
303
304
305PFCB
307 IN PIRP_CONTEXT IrpContext,
310 OUT PBOOLEAN FileNameDos OPTIONAL
311 )
312
313/*++
314
315Routine Description:
316
317 This routine searches either the Oem or Unicode splay tree looking
318 for an Fcb with the specified name. In the case the Fcb is found,
319 rebalance the tree.
320
321Arguments:
322
323 RootNode - Supplies the parent to search.
324
325 Name - If present, search the Oem tree.
326
327 UnicodeName - If present, search the Unicode tree.
328
329Return Value:
330
331 PFCB - The Fcb, or NULL if none was found.
332
333--*/
334
335{
336 COMPARISON Comparison;
338 PRTL_SPLAY_LINKS Links;
339
340 PAGED_CODE();
341 UNREFERENCED_PARAMETER( IrpContext );
342
343 Links = *RootNode;
344
345 while (Links != NULL) {
346
347 Node = CONTAINING_RECORD(Links, FILE_NAME_NODE, Links);
348
349 //
350 // Compare the prefix in the tree with the full name
351 //
352
353 Comparison = CompareNames(&Node->Name.Oem, Name);
354
355 //
356 // See if they don't match
357 //
358
359 if (Comparison == IsGreaterThan) {
360
361 //
362 // The prefix is greater than the full name
363 // so we go down the left child
364 //
365
366 Links = RtlLeftChild(Links);
367
368 //
369 // And continue searching down this tree
370 //
371
372 } else if (Comparison == IsLessThan) {
373
374 //
375 // The prefix is less than the full name
376 // so we go down the right child
377 //
378
379 Links = RtlRightChild(Links);
380
381 //
382 // And continue searching down this tree
383 //
384
385 } else {
386
387 //
388 // We found it.
389 //
390 // Splay the tree and save the new root.
391 //
392
393 *RootNode = RtlSplay(Links);
394
395 //
396 // Tell the caller what kind of name we hit
397 //
398
399 if (FileNameDos) {
400
401 *FileNameDos = Node->FileNameDos;
402 }
403
404 return Node->Fcb;
405 }
406 }
407
408 //
409 // We didn't find the Fcb.
410 //
411
412 return NULL;
413}
414
415
416//
417// Local support routine
418//
419
422 IN PSTRING NameA,
423 IN PSTRING NameB
424 )
425
426/*++
427
428Routine Description:
429
430 This function compares two names as fast as possible. Note that since
431 this comparison is case sensitive, I neither know nor case if the names
432 are UNICODE or OEM. All that is important is that the result is
433 deterministic.
434
435Arguments:
436
437 NameA & NameB - The names to compare.
438
439Return Value:
440
441 COMPARISON - returns
442
443 IsLessThan if NameA < NameB lexicalgraphically,
444 IsGreaterThan if NameA > NameB lexicalgraphically,
445 IsEqual if NameA is equal to NameB
446
447--*/
448
449{
450 ULONG i;
451 ULONG MinLength;
452
453 PAGED_CODE();
454
455 //
456 // Figure out the minimum of the two lengths
457 //
458
459 MinLength = NameA->Length < NameB->Length ? NameA->Length :
460 NameB->Length;
461
462 //
463 // Loop through looking at all of the characters in both strings
464 // testing for equalilty, less than, and greater than
465 //
466
467 i = (ULONG)RtlCompareMemory( NameA->Buffer, NameB->Buffer, MinLength );
468
469
470 if (i < MinLength) {
471
472 return NameA->Buffer[i] < NameB->Buffer[i] ? IsLessThan :
474 }
475
476 if (NameA->Length < NameB->Length) {
477
478 return IsLessThan;
479 }
480
481 if (NameA->Length > NameB->Length) {
482
483 return IsGreaterThan;
484 }
485
486 return IsEqual;
487}
488
#define PAGED_CODE()
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn UINT32 *TableIdx UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE Parent
Definition: acpixf.h:732
_In_ PFCB Fcb
Definition: cdprocs.h:159
@ FcbGood
Definition: cdstruc.h:779
@ FcbBad
Definition: cdstruc.h:780
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
union node Node
Definition: types.h:1255
#define FatBugCheck(A, B, C)
Definition: nodetype.h:104
#define RtlCompareMemory(s1, s2, l)
Definition: env_spec_w32.h:465
#define ClearFlag(_F, _SF)
Definition: ext2fs.h:191
#define FlagOn(_F, _SF)
Definition: ext2fs.h:179
#define CompareNames(NAMEA, NAMEB)
Definition: fatprocs.h:1900
@ IsEqual
Definition: fatprocs.h:1887
@ IsLessThan
Definition: fatprocs.h:1885
@ IsGreaterThan
Definition: fatprocs.h:1886
enum _COMPARISON COMPARISON
VOID FatMarkFcbCondition(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb, IN FCB_CONDITION FcbCondition, IN BOOLEAN Recursive)
#define FCB_STATE_HAS_OEM_LONG_NAME
Definition: fatstruc.h:1201
#define FCB_STATE_NAMES_IN_SPLAY_TREE
Definition: fatstruc.h:1200
#define FCB_STATE_HAS_UNICODE_LONG_NAME
Definition: fatstruc.h:1202
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
VOID NTAPI RtlFreeOemString(POEM_STRING OemString)
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
NTSYSAPI VOID NTAPI RtlFreeUnicodeString(PUNICODE_STRING UnicodeString)
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:325
@ Restart
Definition: sacdrv.h:269
VOID FatInsertName(IN PIRP_CONTEXT IrpContext, IN PRTL_SPLAY_LINKS *RootNode, IN PFILE_NAME_NODE Name)
Definition: splaysup.c:39
PFCB FatFindFcb(IN PIRP_CONTEXT IrpContext, IN OUT PRTL_SPLAY_LINKS *RootNode, IN PSTRING Name, OUT PBOOLEAN FileNameDos OPTIONAL)
Definition: splaysup.c:306
VOID FatRemoveNames(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb)
Definition: splaysup.c:222
COMPARISON FatCompareNames(IN PSTRING NameA, IN PSTRING NameB)
Definition: splaysup.c:421
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68
Definition: cdstruc.h:902
struct _FCB * ParentDcb
Definition: fatstruc.h:836
FILE_NAME_NODE Oem
Definition: fatstruc.h:1159
FILE_NAME_NODE Unicode
Definition: fatstruc.h:1166
ULONG FcbState
Definition: cdstruc.h:971
FILE_NAME_NODE ShortName
Definition: fatstruc.h:1115
union _FCB::@730 LongName
UNICODE_STRING Unicode
Definition: fatstruc.h:695
RTL_SPLAY_LINKS Links
Definition: fatstruc.h:710
union _FILE_NAME_NODE::@728 Name
OEM_STRING Oem
Definition: fatstruc.h:693
unsigned char * PBOOLEAN
Definition: typedefs.h:53
uint32_t ULONG_PTR
Definition: typedefs.h:65
#define IN
Definition: typedefs.h:39
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
#define OUT
Definition: typedefs.h:40
Definition: dlist.c:348
#define RtlRightChild(Links)
#define RtlLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
#define RtlInitializeSplayLinks(Links)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)