ReactOS  0.4.14-dev-368-gfa26425
splaysup.c File Reference
#include "fatprocs.h"
Include dependency graph for splaysup.c:

Go to the source code of this file.

Macros

#define BugCheckFileId   (FAT_BUG_CHECK_SPLAYSUP)
 
#define Dbg   (DEBUG_TRACE_SPLAYSUP)
 

Functions

VOID FatInsertName (IN PIRP_CONTEXT IrpContext, IN PRTL_SPLAY_LINKS *RootNode, IN PFILE_NAME_NODE Name)
 
VOID FatRemoveNames (IN PIRP_CONTEXT IrpContext, IN PFCB Fcb)
 
PFCB FatFindFcb (IN PIRP_CONTEXT IrpContext, IN OUT PRTL_SPLAY_LINKS *RootNode, IN PSTRING Name, OUT PBOOLEAN FileNameDos OPTIONAL)
 
COMPARISON FatCompareNames (IN PSTRING NameA, IN PSTRING NameB)
 

Macro Definition Documentation

◆ BugCheckFileId

#define BugCheckFileId   (FAT_BUG_CHECK_SPLAYSUP)

Definition at line 22 of file splaysup.c.

◆ Dbg

#define Dbg   (DEBUG_TRACE_SPLAYSUP)

Definition at line 28 of file splaysup.c.

Function Documentation

◆ FatCompareNames()

COMPARISON FatCompareNames ( IN PSTRING  NameA,
IN PSTRING  NameB 
)

Definition at line 421 of file splaysup.c.

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 }
#define PAGED_CODE()
Definition: video.h:57
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
unsigned int ULONG
Definition: retypes.h:1
#define RtlCompareMemory(s1, s2, l)
Definition: env_spec_w32.h:465

◆ FatFindFcb()

PFCB FatFindFcb ( IN PIRP_CONTEXT  IrpContext,
IN OUT PRTL_SPLAY_LINKS RootNode,
IN PSTRING  Name,
OUT PBOOLEAN FileNameDos  OPTIONAL 
)

Definition at line 306 of file splaysup.c.

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 }
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:323
#define PAGED_CODE()
Definition: video.h:57
union node Node
Definition: types.h:1255
smooth NULL
Definition: ftsmooth.c:416
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
#define RtlLeftChild(Links)
enum _COMPARISON COMPARISON
#define CompareNames(NAMEA, NAMEB)
Definition: fatprocs.h:1890
#define RtlRightChild(Links)
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
Definition: dlist.c:348

Referenced by FatConstructNamesInFcb().

◆ FatInsertName()

VOID FatInsertName ( IN PIRP_CONTEXT  IrpContext,
IN PRTL_SPLAY_LINKS RootNode,
IN PFILE_NAME_NODE  Name 
)

Definition at line 39 of file splaysup.c.

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 }
#define TRUE
Definition: types.h:120
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
#define PAGED_CODE()
Definition: video.h:57
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
uint32_t ULONG_PTR
Definition: typedefs.h:63
union node Node
Definition: types.h:1255
#define RtlInitializeSplayLinks(Links)
#define FatBugCheck(A, B, C)
Definition: nodetype.h:104
smooth NULL
Definition: ftsmooth.c:416
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
#define RtlLeftChild(Links)
VOID FatMarkFcbCondition(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb, IN FCB_CONDITION FcbCondition, IN BOOLEAN Recursive)
VOID FatRemoveNames(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb)
Definition: splaysup.c:222
enum _COMPARISON COMPARISON
#define CompareNames(NAMEA, NAMEB)
Definition: fatprocs.h:1890
#define RtlRightChild(Links)
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
Definition: dlist.c:348

Referenced by FatConstructNamesInFcb().

◆ FatRemoveNames()

VOID FatRemoveNames ( IN PIRP_CONTEXT  IrpContext,
IN PFCB  Fcb 
)

Definition at line 222 of file splaysup.c.

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 }
union _FCB::@709 LongName
FILE_NAME_NODE Oem
Definition: fatstruc.h:1158
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:323
Definition: cdstruc.h:908
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:728
struct _FCB * ParentDcb
Definition: fatstruc.h:835
#define PAGED_CODE()
Definition: video.h:57
RTL_SPLAY_LINKS Links
Definition: fatstruc.h:709
#define FCB_STATE_NAMES_IN_SPLAY_TREE
Definition: fatstruc.h:1199
FILE_NAME_NODE Unicode
Definition: fatstruc.h:1165
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)
union _FILE_NAME_NODE::@707 Name
#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
_In_ PFCB Fcb
Definition: cdprocs.h:151
FILE_NAME_NODE ShortName
Definition: fatstruc.h:1114
ULONG FcbState
Definition: cdstruc.h:977

Referenced by _Requires_lock_held_(), FatDeleteFcb(), FatInsertName(), and FatSetRenameInfo().