ReactOS 0.4.15-dev-8348-gc1b9bb5
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()
#define RtlCompareMemory(s1, s2, l)
Definition: env_spec_w32.h:465
@ IsEqual
Definition: fatprocs.h:1886
@ IsLessThan
Definition: fatprocs.h:1884
@ IsGreaterThan
Definition: fatprocs.h:1885
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
uint32_t ULONG
Definition: typedefs.h:59

◆ 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}
#define NULL
Definition: types.h:112
union node Node
Definition: types.h:1255
#define CompareNames(NAMEA, NAMEB)
Definition: fatprocs.h:1899
enum _COMPARISON COMPARISON
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:317
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
Definition: dlist.c:348
#define RtlRightChild(Links)
#define RtlLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)

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
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}
@ FcbGood
Definition: cdstruc.h:779
@ FcbBad
Definition: cdstruc.h:780
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define FatBugCheck(A, B, C)
Definition: nodetype.h:104
VOID FatMarkFcbCondition(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb, IN FCB_CONDITION FcbCondition, IN BOOLEAN Recursive)
@ Restart
Definition: sacdrv.h:269
VOID FatRemoveNames(IN PIRP_CONTEXT IrpContext, IN PFCB Fcb)
Definition: splaysup.c:222
uint32_t ULONG_PTR
Definition: typedefs.h:65
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
#define RtlInitializeSplayLinks(Links)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)

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
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}
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
#define ClearFlag(_F, _SF)
Definition: ext2fs.h:191
#define FlagOn(_F, _SF)
Definition: ext2fs.h:179
#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
VOID NTAPI RtlFreeOemString(POEM_STRING OemString)
NTSYSAPI VOID NTAPI RtlFreeUnicodeString(PUNICODE_STRING UnicodeString)
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
union _FCB::@720 LongName
ULONG FcbState
Definition: cdstruc.h:971
FILE_NAME_NODE ShortName
Definition: fatstruc.h:1115
UNICODE_STRING Unicode
Definition: fatstruc.h:695
union _FILE_NAME_NODE::@718 Name
RTL_SPLAY_LINKS Links
Definition: fatstruc.h:710
OEM_STRING Oem
Definition: fatstruc.h:693
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)

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