|
|
//+-------------------------------------------------------------------------
//
// Microsoft Windows
// Copyright (C) Microsoft Corporation, 1992 - 1992.
//
// File: prefix.hxx
//
// Contents: PREFIX table definition
//
// History: SethuR -- Implemented
//
// Notes: The DFS prefix table data structure consists of three
// entities and methods to manipulate them. They are the
// DFS_PREFIX_TABLE_ENTRY,DFS_PREFIX_TABLE_BUCKET and the
// DFS_PREFIX_TABLE.
//
// The DFS_PREFIX_TABLE is a hash table of DFS_PREFIX_TABLE_ENTRY's
// wherein collisions are resolved through linear chaining. The
// hash table is organized as an array of collision lists
// (DFS_PREFIX_TABLE_BUCKET). A brief description with each of
// these entities is attached to the declaration.
//
// There are certain characterstics that distinguish this
// hash table from other hash tables. These are the extensions
// provided to accomodate the special operations.
//
//--------------------------------------------------------------------------
#ifndef __PREFIX_H__
#define __PREFIX_H__
#include <dfsheader.h>
//+---------------------------------------------------------------------
//
// Struct: DFS_PREFIX_TABLE_ENTRY
//
// History:
//
// Notes: Each DFS_PREFIX_TABLE entry is in reality a member of two linked
// lists -- a doubly linked list chaining the entries in a bucket
// and a singly linked list establishing the path from any entry to
// the root of the name space. In addition we have the data associated
// with each entry, viz., the name and the data (pData). We also
// keep track of the number of children of each entry. It can also
// be defined as the number of paths to the root of which this entry
// is a member.
//
//----------------------------------------------------------------------
typedef struct _DFS_PREFIX_TABLE_ENTRY_{ struct _DFS_PREFIX_TABLE_ENTRY_ *pParentEntry; struct _DFS_PREFIX_TABLE_ENTRY_ *pNextEntry; struct _DFS_PREFIX_TABLE_ENTRY_ *pPrevEntry;
//
// pFirstChildEntry and pSiblingEntry are used purely for enumeration
//
struct _DFS_PREFIX_TABLE_ENTRY_ *pFirstChildEntry; struct _DFS_PREFIX_TABLE_ENTRY_ *pSiblingEntry;
ULONG Reference;
UNICODE_STRING PathSegment; PVOID pData;} DFS_PREFIX_TABLE_ENTRY, *PDFS_PREFIX_TABLE_ENTRY;
//+---------------------------------------------------------------------
//
// Struct: DFS_PREFIX_TABLE_BUCKET
//
// History:
//
// Notes: The DFS_PREFIX_TABLE_BUCKET is a doubly linked list of
// DFS_PREFIX_TABLE_ENTRY's. The current implementation employs
// the notion of a sentinel entry associated with each bucket. The
// end pointers are never null but are always looped back to the
// sentinel entry. The reason we employ such an organization is that
// it considerably simplifies the list manipulation routines. The
// reason this needs to be a doubly linked list is that we would like
// to have the ability of deleting entries without having to traverse
// the buckets from beginning.
//
// The following inline methods ( macro defns. ) are provided for
// inserting, deleting and looking up an entry in the bucket.
//
//----------------------------------------------------------------------
typedef struct _PREFIX_TABLE_BUCKET_{ ULONG NoOfEntries; // High water mark for entries hashing to the bkt.
DFS_PREFIX_TABLE_ENTRY SentinelEntry;} PREFIX_TABLE_BUCKET, *PPREFIX_TABLE_BUCKET;
//+---------------------------------------------------------------------
//
// Struct: DFS_PREFIX_TABLE
//
// History:
//
// Notes: The DFS_PREFIX_TABLE is a hashed collection of DFS_PREFIX_TABLE_ENTRY
// organized in the form of buckets. In addition one other space
// conserving measure is adopted. There is only one copy of each
// name segment stored in the table. As an example consider the
// two pathnames \foo\bar and \bar\foo. We only store one copy of foo
// and bar eventhough we accomdate both these paths. A beneficial
// side effect of storing single copies is that our traversal of the
// collision chain is considerably speeded up since once we have
// located the pointer to the name, subsequent comparisons need merely
// compare pointers as opposed to strings.
//
//----------------------------------------------------------------------
#define NO_OF_HASH_BUCKETS 57
typedef struct _DFS_PREFIX_TABLE{ DFS_OBJECT_HEADER DfsHeader; ULONG Flags; ULONG TotalEntries; LONG LockCount; PVOID pPrefixTableLock; //
// NextEntry is used purely for enumeration
//
PDFS_PREFIX_TABLE_ENTRY NextEntry; DFS_PREFIX_TABLE_ENTRY RootEntry; PREFIX_TABLE_BUCKET Buckets[NO_OF_HASH_BUCKETS];} DFS_PREFIX_TABLE, *PDFS_PREFIX_TABLE;
#define PREFIX_TABLE_CASE_SENSITIVE 0x1
#define PREFIX_TABLE_TABLE_ALLOCATED 0x2
#define PREFIX_TABLE_LOCK_ALLOCATED 0x4
#define PREFIX_TABLE_LOCK_INITIALIZED 0x8
//--------------------------------------------------------------------------
//
// PREFIX TABLE UTILITIES
//
// A Path is a sequence of one or more name segments alternated with a
// distinguished concatenation character ( typically \ in FAT,NTFS,HPFS and
// / in UNIX file systems). These utilities are used to split a given path
// into the first path segment followed by the remainder of the path.
//
// SPLIT_PATH("foo\bar\bar1",Name,RemainingPath) binds Name to foo and
// RemainingPath to bar\bar1
//
// Similarly PROCESS_CASE_SENSITIVE_NAME and PROCESS_CASE_INSENSITIVE_NAME
// compute the hash signatures ( bucket no. ) for a given string.
//
//--------------------------------------------------------------------------
//
// MAX_PATH_SEGMENT_SIZE is simply used as a good size buffer to do prefix
// lookups and insertions. This should save us from having to allocate for
// most cases.
//
#define MAX_PATH_SEGMENT_SIZE 256
#define PATH_DELIMITER L'\\'
//+---------------------------------------------------------------------------
//
// Function: SPLIT_CASE_INSENSITIVE_PATH
//
// Synopsis: Split the path name around deleimiters.
//
// Arguments: [pPath] -- path to be split(PUNICODE_STRING)
//
// [pName] -- the leftmost component of the path(PUNICODE_STRING)
//
// [BucketNo] -- Hash Bucket no. corresponding to the name(ULONG)
//
// SideEffects: the UNICODE_STRING pointed to by pName and BucketNo are
// modified.
//
// PreRequisite: pName be associated with a valid buffer.
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define SPLIT_CASE_INSENSITIVE_PATH(pPath,pName,BucketNo) \
{ \ WCHAR *pPathBuffer = (pPath)->Buffer; \ WCHAR *pNameBuffer = (pName)->Buffer; \ WCHAR *pPathBufferEnd = &pPathBuffer[(pPath)->Length / sizeof(WCHAR)]; \ \ BucketNo = 0; \ while ((pPathBufferEnd != pPathBuffer) && \ ((*pNameBuffer = *pPathBuffer++) != PATH_DELIMITER)) \ { \ *pNameBuffer = (*pNameBuffer < L'a') \ ? *pNameBuffer \ : ((*pNameBuffer < L'z') \ ? (*pNameBuffer - L'a' + L'A') \ : RtlUpcaseUnicodeChar(*pNameBuffer)); \ BucketNo *= 131; \ BucketNo += *pNameBuffer; \ pNameBuffer++; \ } \ \ BucketNo = BucketNo % NO_OF_HASH_BUCKETS; \ *pNameBuffer = L'\0'; \ (pName)->Length = (USHORT)((CHAR *)pNameBuffer - (CHAR *)(pName)->Buffer); \ \ (pPath)->Length = (USHORT)((CHAR *)pPathBufferEnd - (CHAR *)pPathBuffer); \ (pPath)->Buffer = pPathBuffer; \} \
//+---------------------------------------------------------------------------
//
// Function: SPLIT_CASE_SENSITIVE_PATH
//
// Synopsis: Split the patah name around deleimiters.
//
// Arguments: [pPath] -- path to be split(PUNICODE_STRING)
//
// [pName] -- the leftmost component of the path(PUNICODE_STRING)
//
// [BucketNo] -- Hash Bucket no. corresponding to the name(ULONG)
//
// SideEffects: the UNICODE_STRING pointed to by pName and BucketNo are modified.
//
// PreRequisite: pName be associated with a valid buffer.
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define SPLIT_CASE_SENSITIVE_PATH(pPath,pName,BucketNo) \
{ \ WCHAR *pPathBuffer = (pPath)->Buffer; \ WCHAR *pNameBuffer = (pName)->Buffer; \ WCHAR *pPathBufferEnd = &pPathBuffer[(pPath)->Length / sizeof(WCHAR)]; \ \ BucketNo = 0; \ while ((pPathBufferEnd != pPathBuffer) && \ ((*pNameBuffer = *pPathBuffer++) != PATH_DELIMITER)) \ { \ BucketNo *= 131; \ BucketNo += *pNameBuffer; \ pNameBuffer++; \ } \ \ BucketNo = BucketNo % NO_OF_HASH_BUCKETS; \ *pNameBuffer = L'\0'; \ (pName)->Length = (USHORT)((CHAR *)pNameBuffer - (CHAR *)(pName)->Buffer); \ \ (pPath)->Length = (USHORT)((CHAR *)pPathBufferEnd - (CHAR *)pPathBuffer); \ (pPath)->Buffer = pPathBuffer; \} \
//+---------------------------------------------------------------------------
//
// Function: INITIALIZE_BUCKET
//
// Synopsis: Initializes a hash bucket.
//
// Arguments: [Bucket] -- the bucket to be initialized(DFS_PREFIX_TABLE_BUCKET)
//
// SideEffects: the bucket is intialized ( the collision list and count are
// initialized
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define INITIALIZE_BUCKET(Bucket) \
{ \ (Bucket).SentinelEntry.pNextEntry = &(Bucket).SentinelEntry; \ (Bucket).SentinelEntry.pPrevEntry = &(Bucket).SentinelEntry; \ (Bucket).NoOfEntries = 0; \} \
//+---------------------------------------------------------------------------
//
// Function: LOOKUP_BUCKET
//
// Synopsis: lookups the bucket for an entry.
//
// Arguments: [Bucket] -- the bucket to be used (DFS_PREFIX_TABLE_BUCKET)
//
// [Name] -- the name to be looked up (UNICODE_STRING)
//
// [pParentEntry] -- the parent entry of the entry we are
// searching for.
//
// [pEntry] -- placeholder for the desired entry.
//
// [fNameFound] -- indicates if the name was found.
//
// SideEffects: Name,fNameFound and pEntry are modified
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
// We only store one copy of a string irrespective of the no. of
// places it appears in, e.g. foo\bar and foo1\bar will result
// in only one copy of bar being stored. This implies that the
// lookup routine will have to return sufficient info. to prevent
// the allocation of memory space for a string. If on exit
// fNameFound is set to TRUE then this indicates that a similar
// string was located in the table and the Name.Buffer field is
// modified to point to the first instance of the string in
// the table.
//
//----------------------------------------------------------------------------
#define LOOKUP_BUCKET(Bucket,Name,pParentEntry,pEntry,fNameFound) \
{ \ PDFS_PREFIX_TABLE_ENTRY pCurEntry = Bucket.SentinelEntry.pNextEntry; \ \ fNameFound = FALSE; \ pEntry = NULL; \ \ while (pCurEntry != &Bucket.SentinelEntry) \ { \ if (pCurEntry->PathSegment.Length == Name.Length) \ { \ if (fNameFound && \ (pCurEntry->PathSegment.Buffer == Name.Buffer)) \ { \ if (pCurEntry->pParentEntry == pParentEntry) \ { \ pEntry = pCurEntry; \ break; \ } \ } \ else if (!memcmp(pCurEntry->PathSegment.Buffer, \ Name.Buffer, \ Name.Length)) \ { \ fNameFound = TRUE; \ Name.Buffer = pCurEntry->PathSegment.Buffer; \ if (pCurEntry->pParentEntry == pParentEntry) \ { \ pEntry = pCurEntry; \ break; \ } \ } \ } \ \ pCurEntry = pCurEntry->pNextEntry; \ } \} \
//+---------------------------------------------------------------------------
//
// Function: INSERT_IN_BUCKET
//
// Synopsis: inserts the entry in the bucket
//
// Arguments: [Bucket] -- the bucket to be initialized(DFS_PREFIX_TABLE_BUCKET)
//
// [pEntry] -- the entry to be inserted
//
// SideEffects: Bucket is modified to include the entry
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define INSERT_IN_BUCKET(Bucket,pEntry) \
{ \ (Bucket).NoOfEntries++; \ (pEntry)->pPrevEntry = (Bucket).SentinelEntry.pPrevEntry; \ (pEntry)->pNextEntry = &((Bucket).SentinelEntry); \ ((Bucket).SentinelEntry.pPrevEntry)->pNextEntry = (pEntry); \ (Bucket).SentinelEntry.pPrevEntry = (pEntry); \} \
//+---------------------------------------------------------------------------
//
// Function: REMOVE_FROM_BUCKET
//
// Synopsis: removes the entry from the bucket
//
// Arguments: [pEntry] -- the entry to be inserted
//
// SideEffects: Bucket is modified to exclude the entry
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define REMOVE_FROM_BUCKET(pEntry) \
{ \ PDFS_PREFIX_TABLE_ENTRY pPrevEntry = (pEntry)->pPrevEntry; \ PDFS_PREFIX_TABLE_ENTRY pNextEntry = (pEntry)->pNextEntry; \ \ pPrevEntry->pNextEntry = pNextEntry; \ pNextEntry->pPrevEntry = pPrevEntry; \} \
//+---------------------------------------------------------------------------
//
// Function: INSERT_IN_CHILD_LIST
//
// Synopsis: Inserts this entry in the parent's list of children
//
// Arguments: [pEntry] -- the entry to be inserted
//
// [pParentEntry] -- the entry into whose list of children
// pEntry has to be inserted.
//
// SideEffects: Parent's list of children is modified.
//
// History: 01-09-96 MilanS Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define INSERT_IN_CHILD_LIST(pEntry, pParentEntry) \
{ \ PDFS_PREFIX_TABLE_ENTRY pLastChild; \ \ if (pParentEntry->pFirstChildEntry == NULL) { \ pParentEntry->pFirstChildEntry = pEntry; \ } else { \ for (pLastChild = pParentEntry->pFirstChildEntry; \ pLastChild->pSiblingEntry != NULL; \ pLastChild = pLastChild->pSiblingEntry) { \ NOTHING; \ } \ pLastChild->pSiblingEntry = pEntry; \ } \}
//+----------------------------------------------------------------------------
//
// Function: REMOVE_FROM_CHILD_LIST
//
// Synopsis: Removes an entry from its parent's list of children
//
// Arguments: [pEntry] -- the Entry to remove from children list.
//
// SideEffects: The children list of pParentEntry is modified.
//
// History: 01-09-96 MilanS Created
//
// Notes: Defined as a macro for inlining.
//
// This routine will ASSERT if pEntry is not in the parent's
// list of children.
//
//-----------------------------------------------------------------------------
#define REMOVE_FROM_CHILD_LIST(pEntry) \
{ \ PDFS_PREFIX_TABLE_ENTRY pParentEntry = pEntry->pParentEntry; \ PDFS_PREFIX_TABLE_ENTRY pPrevSibling; \ \ if (pParentEntry->pFirstChildEntry == pEntry) { \ pParentEntry->pFirstChildEntry = pEntry->pSiblingEntry; \ } else { \ for (pPrevSibling = pParentEntry->pFirstChildEntry; \ pPrevSibling->pSiblingEntry != pEntry; \ pPrevSibling = pPrevSibling->pSiblingEntry) { \ ASSERT(pPrevSibling->pSiblingEntry != NULL); \ } \ pPrevSibling->pSiblingEntry = pEntry->pSiblingEntry; \ } \}
//+---------------------------------------------------------------------------
//
// Function: INITIALIZE_PREFIX_TABLE_ENTRY
//
// Synopsis: initializes the prefix table entry
//
// Arguments: [pEntry] -- the entry to be initialized
//
// SideEffects: the prefix table entry is modified
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
#define INITIALIZE_PREFIX_TABLE_ENTRY(pEntry) \
{ \ RtlZeroMemory( pEntry, sizeof( DFS_PREFIX_TABLE_ENTRY ) ); \ (pEntry)->Reference = 1; \} \
//+---------------------------------------------------------------------------
//
// Function: private fns. extern declarations
//
//----------------------------------------------------------------------------
externNTSTATUS _LookupPrefixTable( IN PDFS_PREFIX_TABLE pTable, IN UNICODE_STRING *pPath, OUT UNICODE_STRING *pSuffix, OUT PDFS_PREFIX_TABLE_ENTRY *ppEntry, OUT PBOOLEAN pSubStringMatch );
VOIDDfsRemovePrefixTableEntry( PDFS_PREFIX_TABLE pTable, PDFS_PREFIX_TABLE_ENTRY pEntry );
//+---------------------------------------------------------------------------
//
// Function: ALLOCATION ROUTINES
//
// Synopsis: all the allocation routines are defined to be used in the KERNEL as
// well as user mode. The KERNEL mode is turned on by defining KERNEL
//
// History: 04-18-94 SethuR Created
//
// Notes: defined as a macro for inlining
//
//----------------------------------------------------------------------------
//
// We may be holding the PrefixLock shared. However, we won't need interlocks to
// just read the value.
//
#define IS_PREFIX_TABLE_LOCKED(_pTable) \
((_pTable)->LockCount > 0) #define ALLOCATE_PREFIX_TABLE() \
PREFIX_TABLE_ALLOCATE_MEMORY(sizeof(DFS_PREFIX_TABLE))
#define FREE_PREFIX_TABLE(_ptable) \
PREFIX_TABLE_FREE_MEMORY(_ptable)
#ifdef KERNEL_MODE
#define ALLOCATE_NAME_BUFFER(cLength) \
ExAllocatePoolWithTag(PagedPool, cLength * sizeof(WCHAR), 'PsfD'); \
#define FREE_NAME_BUFFER(pName) ExFreePool(pName);
#define ALLOCATE_DFS_PREFIX_TABLE_ENTRY(pTable) \
(PDFS_PREFIX_TABLE_ENTRY) ExAllocatePoolWithTag(PagedPool,sizeof(DFS_PREFIX_TABLE_ENTRY), 'PsfD')
#define FREE_DFS_PREFIX_TABLE_ENTRY(pTable,pEntry) ExFreePool(pEntry);
#define COMPARE_MEMORY(s,d,l) (!RtlEqualMemory(s,d,l))
#define PREFIX_TABLE_ALLOCATE_MEMORY(size) ExAllocatePoolWithTag(PagedPool, size, 'PsfD')
#define PREFIX_TABLE_ALLOCATE_NONPAGED_MEMORY(size) ExAllocatePoolWithTag(NonPagedPool, size, 'PsfD')
#define PREFIX_TABLE_FREE_MEMORY(_p) ExFreePool(_p)
#define ALLOCATE_PREFIX_TABLE_LOCK() \
PREFIX_TABLE_ALLOCATE_NONPAGED_MEMORY(sizeof(ERESOURCE))
#define FREE_PREFIX_TABLE_LOCK(_plock) PREFIX_TABLE_FREE_MEMORY(_plock)
// We may be holding the PrefixLock shared. Use Interlocks to change the LockCount.
#define UNLOCK_PREFIX_TABLE(_ptable) {InterlockedDecrement( (ULONG volatile *)&(_ptable)->LockCount ); ExReleaseResourceLite((_ptable)->pPrefixTableLock);}
#define WRITE_LOCK_PREFIX_TABLE(_ptable,_sts) {(_sts) = STATUS_UNSUCCESSFUL;if((ExAcquireResourceExclusiveLite((_ptable)->pPrefixTableLock, TRUE) == TRUE)){InterlockedIncrement((ULONG volatile *)&(_ptable)->LockCount);(_sts) = STATUS_SUCCESS;}}
#define READ_LOCK_PREFIX_TABLE(_ptable,_sts) {(_sts) = STATUS_UNSUCCESSFUL;if((ExAcquireResourceSharedLite((_ptable)->pPrefixTableLock, TRUE) == TRUE)){InterlockedIncrement((ULONG volatile *)&(_ptable)->LockCount);(_sts) = STATUS_SUCCESS;}}
#define INITIALIZE_PREFIX_TABLE_LOCK(_plock) ExInitializeResourceLite(_plock)
#define UNINITIALIZE_PREFIX_TABLE_LOCK(_plock) ExDeleteResourceLite(_plock)
#else
#define ALLOCATE_PREFIX_TABLE_LOCK() \
PREFIX_TABLE_ALLOCATE_MEMORY(sizeof(CRITICAL_SECTION)) #define FREE_PREFIX_TABLE_LOCK(_plock) \
PREFIX_TABLE_FREE_MEMORY(_plock)
#define PREFIX_TABLE_SPIN_COUNT 4000
#define INITIALIZE_PREFIX_TABLE_LOCK(_plock) ((InitializeCriticalSectionAndSpinCount(_plock, PREFIX_TABLE_SPIN_COUNT) == FALSE) ? GetLastError() : STATUS_SUCCESS)
#define UNINITIALIZE_PREFIX_TABLE_LOCK(_plock) DeleteCriticalSection(_plock)
#define UNLOCK_PREFIX_TABLE(_pTable) {(_pTable)->LockCount--; LeaveCriticalSection((_pTable)->pPrefixTableLock); }
#define READ_LOCK_PREFIX_TABLE(_ptable, _sts) \
WRITE_LOCK_PREFIX_TABLE(_ptable, _sts) #define WRITE_LOCK_PREFIX_TABLE(_pTable, _sts ) \
{ EnterCriticalSection((_pTable)->pPrefixTableLock); (_pTable)->LockCount++; (_sts) = STATUS_SUCCESS; }
#define ALLOCATE_NAME_BUFFER(cLength) \
PREFIX_TABLE_ALLOCATE_MEMORY(cLength * sizeof(WCHAR))#define FREE_NAME_BUFFER(_pName) \
PREFIX_TABLE_FREE_MEMORY(_pName)
#define ALLOCATE_DFS_PREFIX_TABLE_ENTRY(_pTable) \
(PDFS_PREFIX_TABLE_ENTRY)PREFIX_TABLE_ALLOCATE_MEMORY(sizeof(DFS_PREFIX_TABLE_ENTRY))#define FREE_DFS_PREFIX_TABLE_ENTRY(_pTable,_pEntry) \
PREFIX_TABLE_FREE_MEMORY(_pEntry)
#define COMPARE_MEMORY(s,d,l) memcmp(s,d,l)
#if defined (PREFIX_TABLE_HEAP_MEMORY)
#define PREFIX_TABLE_ALLOCATE_MEMORY(_sz) \
HeapAlloc(PrefixTableHeapHandle, 0, _sz)
#define PREFIX_TABLE_FREE_MEMORY(_addr) \
HeapFree(PrefixTableHeapHandle, 0, _addr)
#else
#define PREFIX_TABLE_ALLOCATE_MEMORY(_sz) malloc(_sz)
#define PREFIX_TABLE_FREE_MEMORY(_addr) free(_addr)
#endif
#endif /*!Kernel mode */
#endif // __PREFIX_H__
|
