704 lines
16 KiB
C++
704 lines
16 KiB
C++
/*++
|
||
|
||
Copyright (c) 1991 Microsoft Corporation
|
||
|
||
Module Name:
|
||
|
||
indxtree.hxx
|
||
|
||
Abstract:
|
||
|
||
this module contains the declarations for the NTFS_INDEX_TREE
|
||
class, which models index trees on an NTFS volume.
|
||
|
||
An NTFS Index Tree consists of an index root and a set of
|
||
index buffers. The index root is stored as the value of
|
||
an INDEX_ROOT attribute; the index buffers are part of the
|
||
value of an INDEX_ALLOCATION attribute.
|
||
|
||
Author:
|
||
|
||
Bill McJohn (billmc) 30-Aug-1991
|
||
|
||
Environment:
|
||
|
||
ULIB, User Mode
|
||
|
||
--*/
|
||
|
||
#if !defined( _NTFS_INDEX_TREE_DEFN_ )
|
||
|
||
#define _NTFS_INDEX_TREE_DEFN_
|
||
|
||
#include "hmem.hxx"
|
||
#include "intstack.hxx"
|
||
|
||
DECLARE_CLASS( LOG_IO_DP_DRIVE );
|
||
DECLARE_CLASS( WSTRING );
|
||
DECLARE_CLASS( NTFS_ATTRIBUTE );
|
||
DECLARE_CLASS( NTFS_BITMAP );
|
||
DECLARE_CLASS( NTFS_INDEX_ROOT );
|
||
DECLARE_CLASS( NTFS_INDEX_BUFFER );
|
||
DECLARE_CLASS( NTFS_FILE_RECORD_SEGMENT );
|
||
DECLARE_CLASS( NTFS_UPCASE_TABLE );
|
||
|
||
// This constant is given to FindEntry to indicate it should skip
|
||
// all matching entries.
|
||
//
|
||
CONST ULONG INDEX_SKIP = (ULONG)(-1);
|
||
|
||
typedef enum INDEX_ITERATOR_STATE {
|
||
|
||
INDEX_ITERATOR_RESET,
|
||
INDEX_ITERATOR_CURRENT,
|
||
INDEX_ITERATOR_INVALID,
|
||
INDEX_ITERATOR_DELETED,
|
||
INDEX_ITERATOR_CORRUPT
|
||
};
|
||
|
||
typedef enum INDEX_ENTRY_TYPE {
|
||
INDEX_ENTRY_WITH_DATA_TYPE_4 = 0, // value is used as an index to
|
||
INDEX_ENTRY_WITH_DATA_TYPE_8 = 1, // IndexEntryAttributeLength array;
|
||
INDEX_ENTRY_WITH_DATA_TYPE_12 = 2, // these values should not be changed
|
||
INDEX_ENTRY_WITH_DATA_TYPE_16 = 3,
|
||
INDEX_ENTRY_WITH_DATA_TYPE,
|
||
INDEX_ENTRY_WITH_FILE_NAME_TYPE,
|
||
INDEX_ENTRY_GENERIC_TYPE
|
||
};
|
||
|
||
LONG
|
||
NtfsCollate(
|
||
IN PCVOID Value1,
|
||
IN ULONG Length1,
|
||
IN PCVOID Value2,
|
||
IN ULONG Length2,
|
||
IN COLLATION_RULE CollationRule,
|
||
IN PNTFS_UPCASE_TABLE UpcaseTable OPTIONAL
|
||
);
|
||
|
||
LONG
|
||
CompareNtfsIndexEntries(
|
||
IN PCINDEX_ENTRY Entry1,
|
||
IN PCINDEX_ENTRY Entry2,
|
||
IN COLLATION_RULE CollationRule,
|
||
IN PNTFS_UPCASE_TABLE UpcaseTable OPTIONAL
|
||
);
|
||
|
||
|
||
class NTFS_INDEX_TREE : public OBJECT {
|
||
|
||
public:
|
||
|
||
UNTFS_EXPORT
|
||
DECLARE_CONSTRUCTOR( NTFS_INDEX_TREE );
|
||
|
||
VIRTUAL
|
||
UNTFS_EXPORT
|
||
~NTFS_INDEX_TREE(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
Initialize(
|
||
IN OUT PLOG_IO_DP_DRIVE Drive,
|
||
IN ULONG ClusterFactor,
|
||
IN OUT PNTFS_BITMAP VolumeBitmap,
|
||
IN PNTFS_UPCASE_TABLE UpcaseTable,
|
||
IN ULONG MaximumRootSize,
|
||
IN PNTFS_FILE_RECORD_SEGMENT SourceFrs,
|
||
IN PCWSTRING IndexName DEFAULT NULL
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
Initialize(
|
||
IN ATTRIBUTE_TYPE_CODE IndexedAttributeType,
|
||
IN OUT PLOG_IO_DP_DRIVE Drive,
|
||
IN ULONG ClusterFactor,
|
||
IN OUT PNTFS_BITMAP VolumeBitmap,
|
||
IN PNTFS_UPCASE_TABLE UpcaseTable,
|
||
IN COLLATION_RULE CollationRule,
|
||
IN ULONG IndexBufferSize,
|
||
IN ULONG MaximumRootSize,
|
||
IN PCWSTRING IndexName DEFAULT NULL
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
QueryFileReference(
|
||
IN ULONG KeyLength,
|
||
IN PVOID Key,
|
||
IN ULONG Ordinal,
|
||
OUT PMFT_SEGMENT_REFERENCE SegmentReference,
|
||
OUT PBOOLEAN Error
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
QueryEntry(
|
||
IN ULONG KeyLength,
|
||
IN PVOID Key,
|
||
IN ULONG Ordinal,
|
||
OUT PINDEX_ENTRY* FoundEntry,
|
||
OUT PNTFS_INDEX_BUFFER* ContainingBuffer,
|
||
OUT PBOOLEAN Error
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
InsertEntry(
|
||
IN ULONG KeyLength,
|
||
IN PVOID KeyValue,
|
||
IN MFT_SEGMENT_REFERENCE FileReference,
|
||
IN BOOLEAN NoDuplicates DEFAULT TRUE
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
InsertEntry(
|
||
IN PCINDEX_ENTRY NewEntry,
|
||
IN BOOLEAN NoDuplicates DEFAULT TRUE,
|
||
IN PBOOLEAN Duplicate DEFAULT NULL
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
DeleteEntry(
|
||
IN ULONG KeyLength,
|
||
IN PVOID Key,
|
||
IN ULONG Ordinal
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
Save(
|
||
IN OUT PNTFS_FILE_RECORD_SEGMENT TargetFrs
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
IsBadlyOrdered(
|
||
OUT PBOOLEAN Error,
|
||
IN BOOLEAN DuplicatesAllowed
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
Sort(
|
||
IN OUT PNTFS_FILE_RECORD_SEGMENT TargetFrs
|
||
);
|
||
|
||
NONVIRTUAL
|
||
ATTRIBUTE_TYPE_CODE
|
||
QueryTypeCode(
|
||
) CONST;
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
VOID
|
||
ResetIterator(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
PCINDEX_ENTRY
|
||
GetNext(
|
||
OUT PULONG Depth,
|
||
OUT PBOOLEAN Error,
|
||
IN BOOLEAN FilterEndEntries DEFAULT TRUE
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UNTFS_EXPORT
|
||
BOOLEAN
|
||
CopyIterator(
|
||
PNTFS_INDEX_TREE Index
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
DeleteCurrentEntry(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
WriteCurrentEntry(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
COLLATION_RULE
|
||
QueryCollationRule(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
ATTRIBUTE_TYPE_CODE
|
||
QueryIndexedAttributeType(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
UCHAR
|
||
QueryClustersPerBuffer(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
ULONG
|
||
QueryBufferSize(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
FreeAllocation(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
UpdateFileName(
|
||
IN PCFILE_NAME Name,
|
||
IN FILE_REFERENCE ContainingFile
|
||
);
|
||
|
||
NONVIRTUAL
|
||
PCWSTRING
|
||
GetName(
|
||
) CONST;
|
||
|
||
STATIC
|
||
BOOLEAN
|
||
IsIndexEntryCorrupt(
|
||
IN PCINDEX_ENTRY IndexEntry,
|
||
IN ULONG MaximumLength,
|
||
IN PMESSAGE Message,
|
||
IN INDEX_ENTRY_TYPE IndexEntryType DEFAULT INDEX_ENTRY_GENERIC_TYPE
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
ResetLsns(
|
||
IN OUT PMESSAGE Message
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
FindHighestLsn(
|
||
IN OUT PMESSAGE Message,
|
||
OUT PLSN HighestLsn
|
||
) CONST;
|
||
|
||
private:
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
Construct(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
Destroy(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
FindEntry(
|
||
IN ULONG KeyLength,
|
||
IN PVOID KeyValue,
|
||
IN ULONG Ordinal,
|
||
OUT PINDEX_ENTRY* FoundEntry,
|
||
OUT PNTFS_INDEX_BUFFER* ContainingBuffer,
|
||
OUT PINTSTACK ParentTrail
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
RemoveEntry(
|
||
IN PINDEX_ENTRY EntryToRemove,
|
||
IN PNTFS_INDEX_BUFFER ContainingBuffer,
|
||
IN PINTSTACK ParentTrail
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
QueryReplacementEntry(
|
||
IN PINDEX_ENTRY Successor,
|
||
OUT PINDEX_ENTRY ReplacementEntry,
|
||
OUT PBOOLEAN Error,
|
||
OUT PBOOLEAN EmptyLeaf,
|
||
OUT PVCN EmptyLeafVcn
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
FixupEmptyLeaf(
|
||
IN VCN EmptyLeafVcn
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
FindBuffer(
|
||
IN VCN BufferVcn,
|
||
IN PNTFS_INDEX_BUFFER ParentBuffer,
|
||
OUT PNTFS_INDEX_BUFFER FoundBuffer,
|
||
IN OUT PINTSTACK ParentTrail,
|
||
OUT PBOOLEAN Error
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
InsertIntoRoot(
|
||
IN PCINDEX_ENTRY NewEntry,
|
||
IN PINDEX_ENTRY InsertionPoint DEFAULT NULL
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
InsertIntoBuffer(
|
||
IN OUT PNTFS_INDEX_BUFFER TargetBuffer,
|
||
IN OUT PINTSTACK ParentTrail,
|
||
IN PCINDEX_ENTRY NewEntry,
|
||
IN PINDEX_ENTRY InsertionPoint DEFAULT NULL
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
WriteIndexBuffer(
|
||
IN VCN BufferVcn,
|
||
OUT PVOID Data
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
AllocateIndexBuffer(
|
||
OUT PVCN NewBufferVcn
|
||
);
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
FreeIndexBuffer(
|
||
IN VCN BufferVcn
|
||
);
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
FreeChildren(
|
||
IN PINDEX_ENTRY IndexEntry
|
||
);
|
||
|
||
NONVIRTUAL
|
||
ULONG
|
||
QueryMaximumEntrySize(
|
||
) CONST;
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
CreateAllocationAttribute(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
InvalidateIterator(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
PCINDEX_ENTRY
|
||
GetNextUnfiltered(
|
||
OUT PULONG Depth,
|
||
OUT PBOOLEAN Error
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
GetNextLeafEntry(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
BOOLEAN
|
||
GetNextParent(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
UpdateOrdinal(
|
||
);
|
||
|
||
NONVIRTUAL
|
||
VOID
|
||
SaveCurrentKey(
|
||
);
|
||
|
||
ULONG
|
||
QueryCurrentEntryDepth(
|
||
);
|
||
|
||
|
||
PLOG_IO_DP_DRIVE _Drive;
|
||
ULONG _ClusterFactor;
|
||
ULONG _ClustersPerBuffer;
|
||
ULONG _BufferSize;
|
||
PNTFS_BITMAP _VolumeBitmap;
|
||
PNTFS_ATTRIBUTE _AllocationAttribute;
|
||
PNTFS_INDEX_ROOT _IndexRoot;
|
||
PNTFS_BITMAP _IndexAllocationBitmap;
|
||
|
||
PWSTRING _Name;
|
||
ATTRIBUTE_TYPE_CODE _IndexedAttributeType;
|
||
COLLATION_RULE _CollationRule;
|
||
|
||
PNTFS_UPCASE_TABLE _UpcaseTable;
|
||
|
||
|
||
// Iterator state information:
|
||
//
|
||
// Each index tree has a single iterator associated with it.
|
||
// This iterator oscillates among the following states:
|
||
//
|
||
// INDEX_ITERATOR_RESET -- the iterator is at the beginning
|
||
// of the index, and the next call
|
||
// to GetNext will return the first
|
||
// entry in the index.
|
||
// INDEX_ITERATOR_CURRENT -- _CurrentEntry points at the current
|
||
// entry. _IsCurrentEntryInRoot is
|
||
// TRUE if that entry is in the index
|
||
// root, otherwise _CurrentEntryBuffer
|
||
// points to the buffer that contains
|
||
// the entry, and _CurrentEntryTrail
|
||
// contains the parent trail of that
|
||
// buffer. In either case,
|
||
// _CurrentKeyOrdinal gives the
|
||
// ordinal of the current entry
|
||
// (ie. it is the nth entry for
|
||
// the current key).
|
||
// INDEX_ITERATOR_INVALID -- _CurrentEntry has been invalidated,
|
||
// and the tree must relocate the
|
||
// current entry. _CurrentKey,
|
||
// _CurrentKeyLength, and
|
||
// _CurrentKeyOrdinal give the entry
|
||
// information to locate the current
|
||
// entry.
|
||
// INDEX_ITERATOR_DELETED -- Differs from INDEX_ITERATOR_INVALID
|
||
// only in that _CurrentKey,
|
||
// _CurrentKeyLength, and
|
||
// _CurrentKeyOrdinal describe the
|
||
// next entry, rather than the current.
|
||
// INDEX_ITERATOR_CORRUPT -- The iterator (or the tree itself)
|
||
// has become corrupt; any attempt to
|
||
// use it will return error.
|
||
//
|
||
// Since the iterator is very closely coupled to the index
|
||
// tree, it is built into this class, rather than being maintained
|
||
// as a separate object.
|
||
|
||
INDEX_ITERATOR_STATE _IteratorState;
|
||
|
||
BOOLEAN _IsCurrentEntryInRoot;
|
||
PINDEX_ENTRY _CurrentEntry;
|
||
PNTFS_INDEX_BUFFER _CurrentBuffer;
|
||
INTSTACK _CurrentEntryTrail;
|
||
|
||
ULONG _CurrentKeyOrdinal;
|
||
PVOID _CurrentKey;
|
||
ULONG _CurrentKeyLength;
|
||
ULONG _CurrentKeyMaxLength;
|
||
|
||
};
|
||
|
||
INLINE
|
||
ATTRIBUTE_TYPE_CODE
|
||
NTFS_INDEX_TREE::QueryTypeCode(
|
||
) CONST
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This routine returns the attribute type code over which this index
|
||
acts.
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
|
||
The attribute type code for this index.
|
||
--*/
|
||
{
|
||
return _IndexedAttributeType;
|
||
}
|
||
|
||
|
||
|
||
INLINE
|
||
NONVIRTUAL
|
||
COLLATION_RULE
|
||
NTFS_INDEX_TREE::QueryCollationRule(
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This method returns the collation rule by which this
|
||
index tree is ordered.
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
|
||
The index tree's collation rule.
|
||
|
||
--*/
|
||
{
|
||
return _CollationRule;
|
||
}
|
||
|
||
|
||
INLINE
|
||
NONVIRTUAL
|
||
ATTRIBUTE_TYPE_CODE
|
||
NTFS_INDEX_TREE::QueryIndexedAttributeType(
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This method returns the type code of the attribute which is
|
||
indexed by this index tree.
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
--*/
|
||
{
|
||
return _IndexedAttributeType;
|
||
}
|
||
|
||
|
||
INLINE
|
||
NONVIRTUAL
|
||
UCHAR
|
||
NTFS_INDEX_TREE::QueryClustersPerBuffer(
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This method returns the number of clusters in each allocation
|
||
buffer in this index tree.
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
|
||
The number of clusters per allocation buffer in this tree.
|
||
|
||
--*/
|
||
{
|
||
return (UCHAR)_ClustersPerBuffer;
|
||
}
|
||
|
||
INLINE
|
||
NONVIRTUAL
|
||
ULONG
|
||
NTFS_INDEX_TREE::QueryBufferSize(
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This method returns the size of each allocation
|
||
buffer in this index tree.
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
|
||
The number of bytes per allocation buffer in this tree.
|
||
|
||
--*/
|
||
{
|
||
return _BufferSize;
|
||
}
|
||
|
||
|
||
|
||
INLINE
|
||
ULONG
|
||
NTFS_INDEX_TREE::QueryCurrentEntryDepth(
|
||
)
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This method returns the depth in the tree of _CurrentEntry.
|
||
(Root is zero.)
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
|
||
Depth.
|
||
|
||
Notes:
|
||
|
||
This method should only be called if _IteratorState
|
||
is INDEX_ITERATOR_CURRENT.
|
||
|
||
--*/
|
||
{
|
||
ULONG Result;
|
||
|
||
if( _IteratorState == INDEX_ITERATOR_CURRENT ) {
|
||
|
||
Result = _IsCurrentEntryInRoot ?
|
||
0 :
|
||
( _CurrentEntryTrail.QuerySize() + 1 );
|
||
|
||
} else {
|
||
|
||
DebugAbort( "Tried to determine depth of invalid iterator.\n" );
|
||
Result = 0;
|
||
}
|
||
|
||
return Result;
|
||
}
|
||
|
||
|
||
INLINE
|
||
PCWSTRING
|
||
NTFS_INDEX_TREE::GetName(
|
||
) CONST
|
||
/*++
|
||
|
||
Routine Description:
|
||
|
||
This method returns the name of the index.
|
||
|
||
Arguments:
|
||
|
||
None.
|
||
|
||
Return Value:
|
||
|
||
The name of the index.
|
||
|
||
--*/
|
||
{
|
||
return _Name;
|
||
}
|
||
|
||
|
||
#endif
|