ReactOS  0.4.14-dev-98-gb0d4763
splaysup.c
Go to the documentation of this file.
1 /*++
2 
3 Copyright (c) 1989-2000 Microsoft Corporation
4 
5 Module Name:
6 
7  PrefxSup.c
8 
9 Abstract:
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 
38 VOID
40  IN PIRP_CONTEXT IrpContext,
43  )
44 
45 /*++
46 
47 Routine 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 
54 Arguments:
55 
56  RootNode - Supplies a pointer to the table.
57 
58  Name - Contains the New name to enter.
59 
60 Return Value:
61 
62  None.
63 
64 --*/
65 
66 {
67  COMPARISON Comparison;
69 
70  PAGED_CODE();
71 
73 
74 Restart:
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 
221 VOID
223  IN PIRP_CONTEXT IrpContext,
224  IN PFCB Fcb
225  )
226 
227 /*++
228 
229 Routine 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 
234 Arguments:
235 
236  Name - Supplies the Fcb to process.
237 
238 Return 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 
251  Parent = Fcb->ParentDcb;
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 
305 PFCB
307  IN PIRP_CONTEXT IrpContext,
309  IN PSTRING Name,
310  OUT PBOOLEAN FileNameDos OPTIONAL
311  )
312 
313 /*++
314 
315 Routine 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 
321 Arguments:
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 
329 Return 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 
428 Routine 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 
435 Arguments:
436 
437  NameA & NameB - The names to compare.
438 
439 Return 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 
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
#define IN
Definition: typedefs.h:38
#define TRUE
Definition: types.h:120
FILE_NAME_NODE Oem
Definition: fatstruc.h:1158
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:323
Definition: cdstruc.h:908
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
VOID NTAPI RtlFreeOemString(POEM_STRING OemString)
#define FCB_STATE_HAS_UNICODE_LONG_NAME
Definition: fatstruc.h:1201
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical 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:722
VOID FatInsertName(IN PIRP_CONTEXT IrpContext, IN PRTL_SPLAY_LINKS *RootNode, IN PFILE_NAME_NODE Name)
Definition: splaysup.c:39
struct _FCB * ParentDcb
Definition: fatstruc.h:835
#define PAGED_CODE()
Definition: video.h:57
PFCB FatFindFcb(IN PIRP_CONTEXT IrpContext, IN OUT PRTL_SPLAY_LINKS *RootNode, IN PSTRING Name, OUT PBOOLEAN FileNameDos OPTIONAL)
Definition: splaysup.c:306
RTL_SPLAY_LINKS Links
Definition: fatstruc.h:709
union _FILE_NAME_NODE::@696 Name
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
uint32_t ULONG_PTR
Definition: typedefs.h:63
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
#define FCB_STATE_NAMES_IN_SPLAY_TREE
Definition: fatstruc.h:1199
union node Node
Definition: types.h:1255
#define RtlInitializeSplayLinks(Links)
#define FatBugCheck(A, B, C)
Definition: nodetype.h:104
union _FCB::@698 LongName
smooth NULL
Definition: ftsmooth.c:416
FILE_NAME_NODE Unicode
Definition: fatstruc.h:1165
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
OEM_STRING Oem
Definition: fatstruc.h:692
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
NTSYSAPI VOID NTAPI RtlFreeUnicodeString(PUNICODE_STRING UnicodeString)
#define RtlLeftChild(Links)
VOID FatMarkFcbCondition(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb, IN FCB_CONDITION FcbCondition, IN BOOLEAN Recursive)
char * PBOOLEAN
Definition: retypes.h:11
VOID FatRemoveNames(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb)
Definition: splaysup.c:222
#define FlagOn(_F, _SF)
Definition: ext2fs.h:179
#define FCB_STATE_HAS_OEM_LONG_NAME
Definition: fatstruc.h:1200
ClearFlag(Dirent->Flags, DIRENT_FLAG_NOT_PERSISTENT)
UNICODE_STRING Unicode
Definition: fatstruc.h:694
enum _COMPARISON COMPARISON
COMPARISON FatCompareNames(IN PSTRING NameA, IN PSTRING NameB)
Definition: splaysup.c:421
#define OUT
Definition: typedefs.h:39
unsigned int ULONG
Definition: retypes.h:1
#define CompareNames(NAMEA, NAMEB)
Definition: fatprocs.h:1890
#define RtlRightChild(Links)
_In_ PFCB Fcb
Definition: cdprocs.h:151
FILE_NAME_NODE ShortName
Definition: fatstruc.h:1114
ULONG FcbState
Definition: cdstruc.h:977
#define RtlCompareMemory(s1, s2, l)
Definition: env_spec_w32.h:465
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
Definition: dlist.c:348
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68