f4bdf909a1f267551466300a991fe4680821d50a
[reactos.git] / drivers / filesystems / ntfs / btree.c
1 /*
2 * ReactOS kernel
3 * Copyright (C) 2002, 2017 ReactOS Team
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
18 *
19 * COPYRIGHT: See COPYING in the top level directory
20 * PROJECT: ReactOS kernel
21 * FILE: drivers/filesystem/ntfs/btree.c
22 * PURPOSE: NTFS filesystem driver
23 * PROGRAMMERS: Trevor Thompson
24 */
25
26 /* INCLUDES *****************************************************************/
27
28 #include "ntfs.h"
29
30 #define NDEBUG
31 #include <debug.h>
32
33 /* FUNCTIONS ****************************************************************/
34
35 // TEMP FUNCTION for diagnostic purposes.
36 // Prints VCN of every node in an index allocation
37 VOID
38 PrintAllVCNs(PDEVICE_EXTENSION Vcb,
39 PNTFS_ATTR_CONTEXT IndexAllocationContext,
40 ULONG NodeSize)
41 {
42 ULONGLONG CurrentOffset = 0;
43 PINDEX_BUFFER CurrentNode, Buffer;
44 ULONGLONG BufferSize = AttributeDataLength(&IndexAllocationContext->Record);
45 ULONGLONG i;
46 int Count = 0;
47
48 Buffer = ExAllocatePoolWithTag(NonPagedPool, BufferSize, TAG_NTFS);
49
50 ULONG BytesRead = ReadAttribute(Vcb, IndexAllocationContext, 0, (PCHAR)Buffer, BufferSize);
51
52 ASSERT(BytesRead = BufferSize);
53
54 CurrentNode = Buffer;
55
56 // loop through all the nodes
57 for (i = 0; i < BufferSize; i += NodeSize)
58 {
59 NTSTATUS Status = FixupUpdateSequenceArray(Vcb, &CurrentNode->Ntfs);
60 if (!NT_SUCCESS(Status))
61 {
62 DPRINT1("ERROR: Fixing fixup failed!\n");
63 continue;
64 }
65
66 DPRINT1("Node #%d, VCN: %I64u\n", Count, CurrentNode->VCN);
67
68 CurrentNode = (PINDEX_BUFFER)((ULONG_PTR)CurrentNode + NodeSize);
69 CurrentOffset += NodeSize;
70 Count++;
71 }
72
73 ExFreePoolWithTag(Buffer, TAG_NTFS);
74 }
75
76 /**
77 * @name CompareTreeKeys
78 * @implemented
79 *
80 * Compare two B_TREE_KEY's to determine their order in the tree.
81 *
82 * @param Key1
83 * Pointer to a B_TREE_KEY that will be compared.
84 *
85 * @param Key2
86 * Pointer to the other B_TREE_KEY that will be compared.
87 *
88 * @param CaseSensitive
89 * Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
90 * if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
91 *
92 * @returns
93 * 0 if the two keys are equal.
94 * < 0 if key1 is less thank key2
95 * > 0 if key1 is greater than key2
96 *
97 * @remarks
98 * Any other key is always less than the final (dummy) key in a node. Key1 must not be the dummy node.
99 */
100 LONG
101 CompareTreeKeys(PB_TREE_KEY Key1, PB_TREE_KEY Key2, BOOLEAN CaseSensitive)
102 {
103 UNICODE_STRING Key1Name, Key2Name;
104 LONG Comparison;
105
106 // Key1 must not be the final key (AKA the dummy key)
107 ASSERT(!(Key1->IndexEntry->Flags & NTFS_INDEX_ENTRY_END));
108
109 // If Key2 is the "dummy key", key 1 will always come first
110 if (Key2->NextKey == NULL)
111 return -1;
112
113 Key1Name.Buffer = Key1->IndexEntry->FileName.Name;
114 Key1Name.Length = Key1Name.MaximumLength
115 = Key1->IndexEntry->FileName.NameLength * sizeof(WCHAR);
116
117 Key2Name.Buffer = Key2->IndexEntry->FileName.Name;
118 Key2Name.Length = Key2Name.MaximumLength
119 = Key2->IndexEntry->FileName.NameLength * sizeof(WCHAR);
120
121 // Are the two keys the same length?
122 if (Key1Name.Length == Key2Name.Length)
123 return RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
124
125 // Is Key1 shorter?
126 if (Key1Name.Length < Key2Name.Length)
127 {
128 // Truncate KeyName2 to be the same length as KeyName1
129 Key2Name.Length = Key1Name.Length;
130
131 // Compare the names of the same length
132 Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
133
134 // If the truncated names are the same length, the shorter one comes first
135 if (Comparison == 0)
136 return -1;
137 }
138 else
139 {
140 // Key2 is shorter
141 // Truncate KeyName1 to be the same length as KeyName2
142 Key1Name.Length = Key2Name.Length;
143
144 // Compare the names of the same length
145 Comparison = RtlCompareUnicodeString(&Key1Name, &Key2Name, !CaseSensitive);
146
147 // If the truncated names are the same length, the shorter one comes first
148 if (Comparison == 0)
149 return 1;
150 }
151
152 return Comparison;
153 }
154
155 /**
156 * @name CreateBTreeFromIndex
157 * @implemented
158 *
159 * Parse an index and create a B-Tree in memory from it.
160 *
161 * @param IndexRootContext
162 * Pointer to an NTFS_ATTR_CONTEXT that describes the location of the index root attribute.
163 *
164 * @param NewTree
165 * Pointer to a PB_TREE that will receive the pointer to a newly-created B-Tree.
166 *
167 * @returns
168 * STATUS_SUCCESS on success.
169 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
170 *
171 * @remarks
172 * Allocates memory for the entire tree. Caller is responsible for destroying the tree with DestroyBTree().
173 */
174 NTSTATUS
175 CreateBTreeFromIndex(PNTFS_ATTR_CONTEXT IndexRootContext,
176 PINDEX_ROOT_ATTRIBUTE IndexRoot,
177 PB_TREE *NewTree)
178 {
179 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
180 PB_TREE Tree = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE), TAG_NTFS);
181 PB_TREE_FILENAME_NODE RootNode = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_FILENAME_NODE), TAG_NTFS);
182 PB_TREE_KEY CurrentKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
183 ULONG CurrentOffset = IndexRoot->Header.FirstEntryOffset;
184
185 DPRINT1("CreateBTreeFromIndex(%p, %p, %p)\n", IndexRootContext, IndexRoot, NewTree);
186
187 if (!Tree || !RootNode || !CurrentKey)
188 {
189 DPRINT1("Couldn't allocate enough memory for B-Tree!\n");
190 if (Tree)
191 ExFreePoolWithTag(Tree, TAG_NTFS);
192 if (CurrentKey)
193 ExFreePoolWithTag(CurrentKey, TAG_NTFS);
194 if (RootNode)
195 ExFreePoolWithTag(RootNode, TAG_NTFS);
196 return STATUS_INSUFFICIENT_RESOURCES;
197 }
198
199 RtlZeroMemory(Tree, sizeof(B_TREE));
200 RtlZeroMemory(RootNode, sizeof(B_TREE_FILENAME_NODE));
201 RtlZeroMemory(CurrentKey, sizeof(B_TREE_KEY));
202
203 // Setup the Tree
204 RootNode->FirstKey = CurrentKey;
205 Tree->RootNode = RootNode;
206
207 // Make sure we won't try reading past the attribute-end
208 if (FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header) + IndexRoot->Header.TotalSizeOfEntries > IndexRootContext->Record.Resident.ValueLength)
209 {
210 DPRINT1("Filesystem corruption detected!\n");
211 DestroyBTree(Tree);
212 return STATUS_FILE_CORRUPT_ERROR;
213 }
214
215 // Start at the first node entry
216 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)IndexRoot
217 + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
218 + IndexRoot->Header.FirstEntryOffset);
219
220 // Create a key for each entry in the node
221 while (CurrentOffset < IndexRoot->Header.TotalSizeOfEntries)
222 {
223 // Allocate memory for the current entry
224 CurrentKey->IndexEntry = ExAllocatePoolWithTag(NonPagedPool, CurrentNodeEntry->Length, TAG_NTFS);
225 if (!CurrentKey->IndexEntry)
226 {
227 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
228 DestroyBTree(Tree);
229 return STATUS_INSUFFICIENT_RESOURCES;
230 }
231
232 RootNode->KeyCount++;
233
234 // If this isn't the last entry
235 if (!(CurrentNodeEntry->Flags & NTFS_INDEX_ENTRY_END))
236 {
237 // Create the next key
238 PB_TREE_KEY NextKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(PB_TREE_KEY), TAG_NTFS);
239 if (!NextKey)
240 {
241 DPRINT1("ERROR: Couldn't allocate memory for next key!\n");
242 DestroyBTree(Tree);
243 return STATUS_INSUFFICIENT_RESOURCES;
244 }
245
246 RtlZeroMemory(NextKey, sizeof(PB_TREE_KEY));
247
248 // Add NextKey to the end of the list
249 CurrentKey->NextKey = NextKey;
250
251 // Copy the current entry to its key
252 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
253
254 // Make sure this B-Tree is only one level deep (flat list)
255 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
256 {
257 DPRINT1("TODO: Only directories with single-level B-Trees are supported right now!\n");
258 DestroyBTree(Tree);
259 return STATUS_NOT_IMPLEMENTED;
260 }
261
262 // Advance to the next entry
263 CurrentOffset += CurrentNodeEntry->Length;
264 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
265 CurrentKey = NextKey;
266 }
267 else
268 {
269 // Copy the final entry to its key
270 RtlCopyMemory(CurrentKey->IndexEntry, CurrentNodeEntry, CurrentNodeEntry->Length);
271 CurrentKey->NextKey = NULL;
272
273 // Make sure this B-Tree is only one level deep (flat list)
274 if (CurrentKey->IndexEntry->Flags & NTFS_INDEX_ENTRY_NODE)
275 {
276 DPRINT1("TODO: Only directories with single-level B-Trees are supported right now!\n");
277 DestroyBTree(Tree);
278 return STATUS_NOT_IMPLEMENTED;
279 }
280
281 break;
282 }
283 }
284
285 *NewTree = Tree;
286
287 return STATUS_SUCCESS;
288 }
289
290 /**
291 * @name CreateIndexRootFromBTree
292 * @implemented
293 *
294 * Parse a B-Tree in memory and convert it into an index that can be written to disk.
295 *
296 * @param DeviceExt
297 * Pointer to the DEVICE_EXTENSION of the target drive.
298 *
299 * @param Tree
300 * Pointer to a B_TREE that describes the index to be written.
301 *
302 * @param MaxIndexSize
303 * Describes how large the index can be before it will take too much space in the file record.
304 * After reaching MaxIndexSize, an index can no longer be represented with just an index root
305 * attribute, and will require an index allocation and $I30 bitmap (TODO).
306 *
307 * @param IndexRoot
308 * Pointer to a PINDEX_ROOT_ATTRIBUTE that will receive a pointer to the newly-created index.
309 *
310 * @param Length
311 * Pointer to a ULONG which will receive the length of the new index root.
312 *
313 * @returns
314 * STATUS_SUCCESS on success.
315 * STATUS_INSUFFICIENT_RESOURCES if an allocation fails.
316 * STATUS_NOT_IMPLEMENTED if the new index can't fit within MaxIndexSize.
317 *
318 * @remarks
319 * If the function succeeds, it's the caller's responsibility to free IndexRoot with ExFreePoolWithTag().
320 */
321 NTSTATUS
322 CreateIndexRootFromBTree(PDEVICE_EXTENSION DeviceExt,
323 PB_TREE Tree,
324 ULONG MaxIndexSize,
325 PINDEX_ROOT_ATTRIBUTE *IndexRoot,
326 ULONG *Length)
327 {
328 ULONG i;
329 PB_TREE_KEY CurrentKey;
330 PINDEX_ENTRY_ATTRIBUTE CurrentNodeEntry;
331 PINDEX_ROOT_ATTRIBUTE NewIndexRoot = ExAllocatePoolWithTag(NonPagedPool,
332 DeviceExt->NtfsInfo.BytesPerFileRecord,
333 TAG_NTFS);
334
335 DPRINT1("CreateIndexRootFromBTree(%p, %p, 0x%lx, %p, %p)\n", DeviceExt, Tree, MaxIndexSize, IndexRoot, Length);
336
337 if (!NewIndexRoot)
338 {
339 DPRINT1("Failed to allocate memory for Index Root!\n");
340 return STATUS_INSUFFICIENT_RESOURCES;
341 }
342
343 // Setup the new index root
344 RtlZeroMemory(NewIndexRoot, DeviceExt->NtfsInfo.BytesPerFileRecord);
345
346 NewIndexRoot->AttributeType = AttributeFileName;
347 NewIndexRoot->CollationRule = COLLATION_FILE_NAME;
348 NewIndexRoot->SizeOfEntry = DeviceExt->NtfsInfo.BytesPerIndexRecord;
349 // If Bytes per index record is less than cluster size, clusters per index record becomes sectors per index
350 if (NewIndexRoot->SizeOfEntry < DeviceExt->NtfsInfo.BytesPerCluster)
351 NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerSector;
352 else
353 NewIndexRoot->ClustersPerIndexRecord = NewIndexRoot->SizeOfEntry / DeviceExt->NtfsInfo.BytesPerCluster;
354
355 // Setup the Index node header
356 NewIndexRoot->Header.FirstEntryOffset = sizeof(INDEX_HEADER_ATTRIBUTE);
357 NewIndexRoot->Header.Flags = INDEX_ROOT_SMALL;
358
359 // Start summing the total size of this node's entries
360 NewIndexRoot->Header.TotalSizeOfEntries = NewIndexRoot->Header.FirstEntryOffset;
361
362 // Setup each Node Entry
363 CurrentKey = Tree->RootNode->FirstKey;
364 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)NewIndexRoot
365 + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
366 + NewIndexRoot->Header.FirstEntryOffset);
367 for (i = 0; i < Tree->RootNode->KeyCount; i++)
368 {
369 // Would adding the current entry to the index increase the index size beyond the limit we've set?
370 ULONG IndexSize = FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header)
371 + NewIndexRoot->Header.FirstEntryOffset
372 + NewIndexRoot->Header.TotalSizeOfEntries
373 + CurrentNodeEntry->Length;
374 if (IndexSize > MaxIndexSize)
375 {
376 DPRINT1("TODO: Adding file would require creating an index allocation!\n");
377 ExFreePoolWithTag(NewIndexRoot, TAG_NTFS);
378 return STATUS_NOT_IMPLEMENTED;
379 }
380
381 ASSERT(CurrentKey->IndexEntry->Length != 0);
382
383 // Copy the index entry
384 RtlCopyMemory(CurrentNodeEntry, CurrentKey->IndexEntry, CurrentKey->IndexEntry->Length);
385
386 DPRINT1("Index Node Entry Stream Length: %u\nIndex Node Entry Length: %u\n",
387 CurrentNodeEntry->KeyLength,
388 CurrentNodeEntry->Length);
389
390 // Add Length of Current Entry to Total Size of Entries
391 NewIndexRoot->Header.TotalSizeOfEntries += CurrentNodeEntry->Length;
392
393 // Go to the next node entry
394 CurrentNodeEntry = (PINDEX_ENTRY_ATTRIBUTE)((ULONG_PTR)CurrentNodeEntry + CurrentNodeEntry->Length);
395
396 CurrentKey = CurrentKey->NextKey;
397 }
398
399 NewIndexRoot->Header.AllocatedSize = NewIndexRoot->Header.TotalSizeOfEntries;
400
401 *IndexRoot = NewIndexRoot;
402 *Length = NewIndexRoot->Header.AllocatedSize + FIELD_OFFSET(INDEX_ROOT_ATTRIBUTE, Header);
403
404 return STATUS_SUCCESS;
405 }
406
407 VOID
408 DestroyBTreeKey(PB_TREE_KEY Key)
409 {
410 if (Key->IndexEntry)
411 ExFreePoolWithTag(Key->IndexEntry, TAG_NTFS);
412
413 // We'll destroy Key->LesserChild here after we start using it
414
415 ExFreePoolWithTag(Key, TAG_NTFS);
416 }
417
418 VOID
419 DestroyBTreeNode(PB_TREE_FILENAME_NODE Node)
420 {
421 PB_TREE_KEY NextKey;
422 PB_TREE_KEY CurrentKey = Node->FirstKey;
423 ULONG i;
424 for (i = 0; i < Node->KeyCount; i++)
425 {
426 NT_ASSERT(CurrentKey);
427 NextKey = CurrentKey->NextKey;
428 DestroyBTreeKey(CurrentKey);
429 CurrentKey = NextKey;
430 }
431
432 NT_ASSERT(NextKey == NULL);
433
434 ExFreePoolWithTag(Node, TAG_NTFS);
435 }
436
437 /**
438 * @name DestroyBTree
439 * @implemented
440 *
441 * Destroys a B-Tree.
442 *
443 * @param Tree
444 * Pointer to the B_TREE which will be destroyed.
445 *
446 * @remarks
447 * Destroys every bit of data stored in the tree.
448 */
449 VOID
450 DestroyBTree(PB_TREE Tree)
451 {
452 DestroyBTreeNode(Tree->RootNode);
453 ExFreePoolWithTag(Tree, TAG_NTFS);
454 }
455
456 VOID
457 DumpBTreeKey(PB_TREE_KEY Key, ULONG Number, ULONG Depth)
458 {
459 ULONG i;
460 for (i = 0; i < Depth; i++)
461 DbgPrint(" ");
462 DbgPrint(" Key #%d", Number);
463
464 if (!(Key->IndexEntry->Flags & NTFS_INDEX_ENTRY_END))
465 {
466 UNICODE_STRING FileName;
467 FileName.Length = Key->IndexEntry->FileName.NameLength * sizeof(WCHAR);
468 FileName.MaximumLength = FileName.Length;
469 FileName.Buffer = Key->IndexEntry->FileName.Name;
470 DbgPrint(" '%wZ'\n", &FileName);
471 }
472 else
473 {
474 DbgPrint(" (Dummy Key)\n");
475 }
476 }
477
478 VOID
479 DumpBTreeNode(PB_TREE_FILENAME_NODE Node, ULONG Number, ULONG Depth)
480 {
481 PB_TREE_KEY CurrentKey;
482 ULONG i;
483 for (i = 0; i < Depth; i++)
484 DbgPrint(" ");
485 DbgPrint("Node #%d, Depth %d\n", Number, Depth);
486
487 CurrentKey = Node->FirstKey;
488 for (i = 0; i < Node->KeyCount; i++)
489 {
490 DumpBTreeKey(CurrentKey, i, Depth);
491 CurrentKey = CurrentKey->NextKey;
492 }
493 }
494
495 /**
496 * @name DumpBTree
497 * @implemented
498 *
499 * Displays a B-Tree.
500 *
501 * @param Tree
502 * Pointer to the B_TREE which will be displayed.
503 *
504 * @remarks
505 * Displays a diagnostic summary of a B_TREE.
506 */
507 VOID
508 DumpBTree(PB_TREE Tree)
509 {
510 DbgPrint("B_TREE @ %p\n", Tree);
511 DumpBTreeNode(Tree->RootNode, 0, 0);
512 }
513
514 // Calculates start of Index Buffer relative to the index allocation, given the node's VCN
515 ULONGLONG
516 GetAllocationOffsetFromVCN(PDEVICE_EXTENSION DeviceExt,
517 ULONG IndexBufferSize,
518 ULONGLONG Vcn)
519 {
520 if (IndexBufferSize < DeviceExt->NtfsInfo.BytesPerCluster)
521 return Vcn * DeviceExt->NtfsInfo.BytesPerSector;
522
523 return Vcn * DeviceExt->NtfsInfo.BytesPerCluster;
524 }
525
526 /**
527 * @name NtfsInsertKey
528 * @implemented
529 *
530 * Inserts a FILENAME_ATTRIBUTE into a B-Tree node.
531 *
532 * @param FileReference
533 * Reference number to the file being added. This will be a combination of the MFT index and update sequence number.
534 *
535 * @param FileNameAttribute
536 * Pointer to a FILENAME_ATTRIBUTE which is the data for the key that will be added to the tree. A copy will be made.
537 *
538 * @param Node
539 * Pointer to a B_TREE_FILENAME_NODE into which a new key will be inserted, in order.
540 *
541 * @param CaseSensitive
542 * Boolean indicating if the function should operate in case-sensitive mode. This will be TRUE
543 * if an application created the file with the FILE_FLAG_POSIX_SEMANTICS flag.
544 *
545 * @remarks
546 * A node is always sorted, with the least comparable filename stored first and a dummy key to mark the end.
547 */
548 NTSTATUS
549 NtfsInsertKey(ULONGLONG FileReference,
550 PFILENAME_ATTRIBUTE FileNameAttribute,
551 PB_TREE_FILENAME_NODE Node,
552 BOOLEAN CaseSensitive)
553 {
554 // Calculate size of Attribute and Index Entry
555 ULONG AttributeSize = GetFileNameAttributeLength(FileNameAttribute);
556 ULONG EntrySize = ALIGN_UP_BY(AttributeSize + FIELD_OFFSET(INDEX_ENTRY_ATTRIBUTE, FileName), 8);
557 PINDEX_ENTRY_ATTRIBUTE NewEntry;
558 PB_TREE_KEY NewKey, CurrentKey, PreviousKey;
559 ULONG i;
560
561 DPRINT1("NtfsInsertKey(0x%02I64, %p, %p, %s)\n",
562 FileReference,
563 FileNameAttribute,
564 Node,
565 CaseSensitive ? "TRUE" : "FALSE");
566
567 // Create a new Index Entry for the file
568 NewEntry = ExAllocatePoolWithTag(NonPagedPool, EntrySize, TAG_NTFS);
569 if (!NewEntry)
570 {
571 DPRINT1("ERROR: Failed to allocate memory for Index Entry!\n");
572 return STATUS_INSUFFICIENT_RESOURCES;
573 }
574
575 // Setup the Index Entry
576 RtlZeroMemory(NewEntry, EntrySize);
577 NewEntry->Data.Directory.IndexedFile = FileReference;
578 NewEntry->Length = EntrySize;
579 NewEntry->KeyLength = AttributeSize;
580
581 // Copy the FileNameAttribute
582 RtlCopyMemory(&NewEntry->FileName, FileNameAttribute, AttributeSize);
583
584 // Setup the New Key
585 NewKey = ExAllocatePoolWithTag(NonPagedPool, sizeof(B_TREE_KEY), TAG_NTFS);
586 if (!NewKey)
587 {
588 DPRINT1("ERROR: Failed to allocate memory for new key!\n");
589 ExFreePoolWithTag(NewEntry, TAG_NTFS);
590 return STATUS_INSUFFICIENT_RESOURCES;
591 }
592 NewKey->IndexEntry = NewEntry;
593 NewKey->NextKey = NULL;
594
595 // Find where to insert the key
596 CurrentKey = Node->FirstKey;
597 PreviousKey = NULL;
598 for (i = 0; i < Node->KeyCount; i++)
599 {
600 // Should the New Key go before the current key?
601 LONG Comparison = CompareTreeKeys(NewKey, CurrentKey, CaseSensitive);
602
603 ASSERT(Comparison != 0);
604
605 // Is NewKey < CurrentKey?
606 if (Comparison < 0)
607 {
608 // Insert New Key before Current Key
609 NewKey->NextKey = CurrentKey;
610
611 // was CurrentKey the first key?
612 if (CurrentKey == Node->FirstKey)
613 Node->FirstKey = NewKey;
614 else
615 PreviousKey->NextKey = NewKey;
616 break;
617 }
618
619 PreviousKey = CurrentKey;
620 CurrentKey = CurrentKey->NextKey;
621 }
622
623 Node->KeyCount++;
624
625 // NewEntry and NewKey will be destroyed later by DestroyBTree()
626
627 return STATUS_SUCCESS;
628 }