Windows NT 4.0 source code leak
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

639 lines
15 KiB

/*++
Copyright (c) 1991 Microsoft Corporation
Module Name:
indxroot.hxx
Abstract:
this module contains the member funciton definitions for the
NTFS_INDEX_ROOT class, which models the root of an NTFS index
Author:
Bill McJohn (billmc) 06-Sept-1991
Environment:
ULIB, User Mode
--*/
#include <pch.cxx>
#define _NTAPI_ULIB_
#define _UNTFS_MEMBER_
#include "ulib.hxx"
#include "error.hxx"
#include "untfs.hxx"
#include "drive.hxx"
#include "attrib.hxx"
#include "frs.hxx"
#include "indxroot.hxx"
#include "indxtree.hxx"
DEFINE_CONSTRUCTOR( NTFS_INDEX_ROOT, OBJECT );
NTFS_INDEX_ROOT::~NTFS_INDEX_ROOT(
)
{
Destroy();
}
VOID
NTFS_INDEX_ROOT::Construct(
)
/*++
Routine Description:
Worker function for object construction.
Arguments:
None.
Return Value:
None.
--*/
{
_MaximumSize = 0;
_DataLength = 0;
_Data = NULL;
_IsModified = FALSE;
_UpcaseTable = NULL;
}
VOID
NTFS_INDEX_ROOT::Destroy(
)
/*++
Routine Description:
This method cleans up an NTFS_INDEX_ROOT object in preparation
for destruction or reinitialization.
Arguments:
None.
Return Value:
None.
--*/
{
_MaximumSize = 0;
_DataLength = 0;
FREE( _Data );
_IsModified = FALSE;
_UpcaseTable = NULL;
}
BOOLEAN
NTFS_INDEX_ROOT::Initialize(
IN PNTFS_ATTRIBUTE RootAttribute,
IN PNTFS_UPCASE_TABLE UpcaseTable,
IN ULONG MaximumSize
)
/*++
Routine Description:
This method initializes the index root based on an $INDEX_ROOT
attribute. It is used to initialize an index root object for
an extant index.
Arguments:
RootAttribute -- supplies the $INDEX_ROOT attribute for
this index.
UpcaseTable -- supplies the volume upcase table.
MaximumSize -- supplies the maximum size of this index root
Return Value:
TRUE upon successful completion.
Notes:
If the existing attribute's value length is greater than the
supplied maximum size, the maximum size will be adjusted.
--*/
{
BIG_INT ValueLength;
ULONG BytesRead;
DebugPtrAssert( RootAttribute );
Destroy();
RootAttribute->QueryValueLength( &ValueLength );
// Check that the attribute is the correct type and that
// it is a reasonable size.
if( RootAttribute->QueryTypeCode() != $INDEX_ROOT ||
ValueLength.GetHighPart() != 0 ) {
return FALSE;
}
// If the existing attribute is already bigger than the specified
// maximum size, then increase the maximum size, since it is only
// provided to give an upper bound on the size of the attribute.
if( ValueLength.GetLowPart() > MaximumSize ) {
MaximumSize = ValueLength.GetLowPart();
}
_DataLength = ValueLength.GetLowPart();
_MaximumSize = MaximumSize;
_IsModified = FALSE;
if( (_Data = (PINDEX_ROOT)MALLOC( _MaximumSize )) == NULL ) {
Destroy();
return FALSE;
}
if( !RootAttribute->Read( _Data,
0,
_DataLength,
&BytesRead ) ||
BytesRead != _DataLength ) {
Destroy();
return FALSE;
}
_UpcaseTable = UpcaseTable;
return TRUE;
}
BOOLEAN
NTFS_INDEX_ROOT::Initialize(
IN ATTRIBUTE_TYPE_CODE IndexedAttributeType,
IN COLLATION_RULE CollationRule,
IN PNTFS_UPCASE_TABLE UpcaseTable,
IN ULONG ClustersPerBuffer,
IN ULONG BytesPerBuffer,
IN ULONG MaximumRootSize
)
/*++
Routine Description:
This method initializes the index root based on the fundamental
information of the index. It is used to initialize an index root
for a new index.
Arguments:
IndexedAttributeType -- supplies the type code of the attribute
which is indexed by this index.
CollationRule -- supplies the collation rule for this index.
UpcaseTable -- supplies the volume upcase table.
BytesPerBuffer -- supplies the number of bytes per Index
Allocation Buffer in this index.
MaximumRootSize -- supplies the maximum size of this index root.
Return Value:
TRUE upon successful completion.
Notes:
This method marks the index root as modified, since it is being
created ex nihilo instead of being read from an attribute.
It creates an empty leaf index root (ie. with only an END entry).
--*/
{
PINDEX_ENTRY EndEntry;
DebugAssert( sizeof( INDEX_ROOT ) % 8 == 0 );
DebugAssert( sizeof( INDEX_HEADER ) % 8 == 0 );
Destroy();
_UpcaseTable = UpcaseTable;
_MaximumSize = MaximumRootSize;
_IsModified = TRUE;
_DataLength = sizeof( INDEX_ROOT ) + NtfsIndexLeafEndEntrySize;
// check to make sure that an empty index root will fit in the
// maximum size given. Note that we also reserve space for a
// VCN downpointer, in case this index root gets converted into
// a node by Recreate.
if( _DataLength + sizeof(VCN) > _MaximumSize ) {
Destroy();
return FALSE;
}
if( (_Data = (PINDEX_ROOT)MALLOC( _MaximumSize )) == NULL ) {
Destroy();
return FALSE;
}
memset( _Data, 0, _MaximumSize );
_Data->IndexedAttributeType = IndexedAttributeType;
_Data->CollationRule = CollationRule;
_Data->BytesPerIndexBuffer = BytesPerBuffer;
_Data->ClustersPerIndexBuffer = (UCHAR)ClustersPerBuffer;
_Data->IndexHeader.FirstIndexEntry = sizeof( INDEX_HEADER );
_Data->IndexHeader.FirstFreeByte = sizeof( INDEX_HEADER ) +
NtfsIndexLeafEndEntrySize;
_Data->IndexHeader.BytesAvailable = _Data->IndexHeader.FirstFreeByte;
_Data->IndexHeader.Flags = 0;
// Fill in the end entry. Its only meaningful fields are Length
// and Flags.
EndEntry = GetFirstEntry();
EndEntry->Length = NtfsIndexLeafEndEntrySize;
EndEntry->AttributeLength = 0;
EndEntry->Flags = INDEX_ENTRY_END;
return TRUE;
}
BOOLEAN
NTFS_INDEX_ROOT::FindEntry(
IN PCINDEX_ENTRY SearchEntry,
IN OUT PULONG Ordinal,
OUT PINDEX_ENTRY* EntryFound
)
/*++
Routine Description:
This method locates an entry in the index root. Note that it does
not search the index allocation b-tree (if any).
Arguments:
SearchEntry -- Supplies a search entry, which gives the attribute
value to find.
Ordinal -- supplies an ordinal showing which matching entry
to return; see note below. A value of INDEX_SKIP
indicates that all matching entries should be skipped.
EntryFound -- receives a pointer to the located entry. Receives
NULL if an error has occurred.
Return Value:
TRUE if a matching entry is found.
If an error occurs, *EntryFound is set to NULL.
If no error occurs, and no matching entry is found, *EntryFound
is set to the next entry (i.e. the point at which the search key
would be inserted into this index root) and the method returns
FALSE.
Notes:
This method assumes that the index root is consistent.
The ordinal argument indicates how many matching entries should be
passed over before one is returned. When an entry is found which
matches the search key, if *Ordinal is zero, that entry is returned;
otherwise, *Ordinal is decremented, and the FindEntry goes on to
the next entry.
If *Ordinal is INDEX_SKIP, all matching entries are skipped.
--*/
{
PINDEX_ENTRY CurrentEntry;
BOOLEAN Found;
int CompareResult;
CurrentEntry = GetFirstEntry();
Found = FALSE;
while( !(CurrentEntry->Flags & INDEX_ENTRY_END) ) {
CompareResult = CompareNtfsIndexEntries( SearchEntry,
CurrentEntry,
_Data->CollationRule,
_UpcaseTable);
if( CompareResult < 0 ) {
// The search value is less than the current entry's
// value, so we've overshot where our search key would
// be. Stop (and return the current entry).
break;
} else if( CompareResult == 0 ) {
// The current entry matches the search entry. Check
// the ordinal argument to see if we should return this
// entry or skip it.
if( *Ordinal == 0 ) {
Found = TRUE;
break;
} else if( *Ordinal != INDEX_SKIP ) {
*Ordinal -= 1;
}
}
// Haven't found our entry, so we'll just go on to the next.
CurrentEntry = GetNextEntry( CurrentEntry );
}
*EntryFound = CurrentEntry;
return( Found );
}
BOOLEAN
NTFS_INDEX_ROOT::InsertEntry(
IN PCINDEX_ENTRY NewEntry,
IN PINDEX_ENTRY InsertPoint
)
/*++
Routine Description:
This inserts an index entry into the index root. It will
expand the index root (if possible), but it will not split it.
Arguments:
NewEntry -- supplies the new entry to be inserted.
InsertPoint -- supplies the point at which the new entry should be
inserted--it may be NULL, in which case the index
root should decide for itself.
Return Value:
TRUE upon successful completion.
Notes:
A return value of FALSE indicates that there is not enough room
for the entry in this index root.
If an insertion point is specified, it must be a pointer returned
by a previous call to FindEntry or GetFirstEntry (with no intervening
inserts or deletes).
This method assumes that the index root and the new entry are
consistent, which includes that the entry has a downpointer if
and only if the index root is a node.
--*/
{
ULONG Ordinal, BytesToMove;
// Check to see if there's room.
if( _DataLength + NewEntry->Length > _MaximumSize ) {
return FALSE;
}
// There's enough room, so we're bound to succeed.
if( InsertPoint == NULL ) {
// The client has not supplied the insert point, so we get to
// figure it out for ourselves. Fortunately, we can get FindEntry
// to do our work for us.
// Note that we don't care what InsertEntry returns--we know it
// won't hit an error, and we don't care whether there are any
// matching entries in the buffer. (If we get a matching buffer,
// we insert the new one before it, which is just fine.)
Ordinal = 0;
FindEntry( NewEntry,
&Ordinal,
&InsertPoint );
DebugPtrAssert( InsertPoint );
}
// Make room for the new entry...
BytesToMove = _Data->IndexHeader.FirstFreeByte -
((PBYTE)InsertPoint - (PBYTE)&(_Data->IndexHeader));
memmove( (PBYTE)InsertPoint + NewEntry->Length,
InsertPoint,
BytesToMove );
_Data->IndexHeader.FirstFreeByte += NewEntry->Length;
_Data->IndexHeader.BytesAvailable = _Data->IndexHeader.FirstFreeByte;
memcpy( InsertPoint, NewEntry, NewEntry->Length );
_DataLength += NewEntry->Length;
return TRUE;
}
VOID
NTFS_INDEX_ROOT::RemoveEntry(
PINDEX_ENTRY EntryToRemove
)
/*++
Routine Description:
This method removes an entry from the index root. Note that it will
not find a replacement entry for nodes, or perform any other b-tree
maintenance; it just expunges the entry from the root.
Arguments:
EntryToRemove -- supplies the index entry to be removed. This
must be an entry returned by a previous call
to FindEntry or GetFirstEntry.
Return Value:
None.
Notes:
This method assumes that the index root is consistent.
--*/
{
PBYTE NextEntry;
ULONG BytesToMove;
DebugAssert( (PBYTE)EntryToRemove <
(PBYTE)&(_Data->IndexHeader) +
_Data->IndexHeader.FirstFreeByte );
DebugAssert( (PBYTE)EntryToRemove >=
(PBYTE)&(_Data->IndexHeader) +
_Data->IndexHeader.FirstIndexEntry );
NextEntry = (PBYTE)GetNextEntry( EntryToRemove );
BytesToMove = _Data->IndexHeader.FirstFreeByte -
( NextEntry - (PBYTE)&(_Data->IndexHeader) );
_Data->IndexHeader.FirstFreeByte -= EntryToRemove->Length;
_Data->IndexHeader.BytesAvailable = _Data->IndexHeader.FirstFreeByte;
_DataLength -= EntryToRemove->Length;
memmove( EntryToRemove,
NextEntry,
BytesToMove );
}
VOID
NTFS_INDEX_ROOT::Recreate(
IN BOOLEAN IsLeaf,
IN VCN EndEntryDownpointer
)
/*++
Routine Description:
This method recreates the Index Root with only an end entry.
Arguments:
IsLeaf -- supplies an indicator whether this index root
is a leaf (TRUE) or a node (FALSE).
EndEntryDownpointer -- supplies the VCN DownPointer for the End
Entry. (If IsLeaf is TRUE, this parameter
is ignored.)
Return Value:
None.
Notes:
The basic information of the index root is not changed; just the
index entries and flags.
--*/
{
PINDEX_ENTRY EndEntry;
ULONG EndEntrySize;
_IsModified = TRUE;
_DataLength = sizeof( INDEX_ROOT ) + NtfsIndexLeafEndEntrySize;
EndEntrySize = NtfsIndexLeafEndEntrySize;
if( !IsLeaf ) {
_Data->IndexHeader.Flags = INDEX_NODE;
_DataLength += sizeof(VCN);
EndEntrySize += sizeof( VCN );
} else {
_Data->IndexHeader.Flags = 0;
}
DebugAssert( _MaximumSize >= _DataLength );
_Data->IndexHeader.FirstFreeByte = sizeof( INDEX_HEADER ) +
EndEntrySize;
_Data->IndexHeader.BytesAvailable = _Data->IndexHeader.FirstFreeByte;
// Fill in the end entry. Its only meaningful fields are Length,
// Flags, and downpointer (if any).
EndEntry = GetFirstEntry();
EndEntry->Length = (USHORT)EndEntrySize;
EndEntry->AttributeLength = 0;
EndEntry->Flags = INDEX_ENTRY_END;
if( !IsLeaf ) {
EndEntry->Flags |= INDEX_ENTRY_NODE;
GetDownpointer( EndEntry ) = EndEntryDownpointer;
}
}
BOOLEAN
NTFS_INDEX_ROOT::Write(
PNTFS_ATTRIBUTE RootAttribute
)
/*++
Routine Description:
This method writes the index root to the supplied attribute.
Arguments:
RootAttribute -- supplies the INDEX_ROOT attribute.
Return Value:
TRUE upon successful completion.
--*/
{
ULONG BytesWritten;
// Resize the attribute to the correct size, and then write
// the root's data to it. Since this attribute is always
// resident, pass in NULL for the bitmap.
//
return( RootAttribute->IsResident() &&
RootAttribute->Resize( _DataLength, NULL ) &&
RootAttribute->Write( _Data,
0,
_DataLength,
&BytesWritten,
NULL ) &&
BytesWritten == _DataLength );
}