Alex Ionescu <ionucu(a)videotron.ca>
- Fix implementation of NT Profile Objects. Structures are guesses, but
seem pretty close to the NT ones... a lot of stuff based on David
Welch's old implementation, but simplified the way profiles are managed
extensively, and also using the same buckethash mechanism as NT, this is
required for compatibility with Nt Native APIs that use Profile Objects.
- Removed KDBG internal profile management and associated files. I will
re-write the Profiler to use NT Profile Objects, which will allow us
more extensibilty while profiling and also greater compatibility with
NT.
Modified: trunk/reactos/ntoskrnl/Makefile
Modified: trunk/reactos/ntoskrnl/dbg/kdb.h
Deleted: trunk/reactos/ntoskrnl/dbg/profile.c
Deleted: trunk/reactos/ntoskrnl/ex/btree.c
Deleted: trunk/reactos/ntoskrnl/ex/hashtab.c
Modified: trunk/reactos/ntoskrnl/ex/profile.c
Deleted: trunk/reactos/ntoskrnl/ex/stree.c
Modified: trunk/reactos/ntoskrnl/include/internal/ke.h
Modified: trunk/reactos/ntoskrnl/io/irp.c
Modified: trunk/reactos/ntoskrnl/kd/kdebug.c
Modified: trunk/reactos/ntoskrnl/ke/i386/irq.c
Modified: trunk/reactos/ntoskrnl/ke/profile.c
Modified: trunk/reactos/ntoskrnl/ke/timer.c
Modified: trunk/reactos/ntoskrnl/ntoskrnl.def
_____
Modified: trunk/reactos/ntoskrnl/Makefile
--- trunk/reactos/ntoskrnl/Makefile 2005-03-13 18:39:38 UTC (rev
14021)
+++ trunk/reactos/ntoskrnl/Makefile 2005-03-13 18:41:59 UTC (rev
14022)
@@ -33,7 +33,7 @@
OBJECTS_KDBG :=
endif
ifeq ($(DBG_OR_KDBG), 1)
-OBJECTS_KDBG := $(OBJECTS_KDBG) dbg/kdb_symbols.o dbg/profile.o
+OBJECTS_KDBG := $(OBJECTS_KDBG) dbg/kdb_symbols.o
endif
TARGET_ASFLAGS = -I./include
@@ -233,14 +233,12 @@
# Executive Subsystem (Ex)
OBJECTS_EX = \
- ex/btree.o \
ex/callback.o \
ex/error.o \
ex/event.o \
ex/evtpair.o \
ex/fmutex.o \
ex/handle.o \
- ex/hashtab.o \
ex/init.o \
ex/interlck.o \
ex/list.o \
@@ -250,7 +248,6 @@
ex/profile.o \
ex/resource.o \
ex/rundown.o \
- ex/stree.o \
ex/sem.o \
ex/synch.o \
ex/sysinfo.o \
_____
Modified: trunk/reactos/ntoskrnl/dbg/kdb.h
--- trunk/reactos/ntoskrnl/dbg/kdb.h 2005-03-13 18:39:38 UTC (rev
14021)
+++ trunk/reactos/ntoskrnl/dbg/kdb.h 2005-03-13 18:41:59 UTC (rev
14022)
@@ -255,19 +255,6 @@
KdbpAttachToProcess(
PVOID ProcessId);
-/* from profile.c */
-
-VOID
-KdbInitProfiling();
-VOID
-KdbInitProfiling2();
-VOID
-KdbDisableProfiling();
-VOID
-KdbEnableProfiling();
-VOID
-KdbProfileInterrupt(ULONG_PTR Eip);
-
/* other functions */
#define KdbpSafeReadMemory(dst, src, size) MmSafeCopyFromUser(dst,
src, size)
_____
Deleted: trunk/reactos/ntoskrnl/dbg/profile.c
--- trunk/reactos/ntoskrnl/dbg/profile.c 2005-03-13 18:39:38 UTC
(rev 14021)
+++ trunk/reactos/ntoskrnl/dbg/profile.c 2005-03-13 18:41:59 UTC
(rev 14022)
@@ -1,478 +0,0 @@
-/* $Id$
- *
- * COPYRIGHT: See COPYING in the top level directory
- * PROJECT: ReactOS kernel
- * FILE: ntoskrnl/dbg/profile.c
- * PURPOSE: Kernel profiling
- *
- * PROGRAMMERS: Casper S. Hornstrup (chorns(a)users.sourceforge.net)
- */
-
-/* INCLUDES
*****************************************************************/
-
-#include <ntoskrnl.h>
-#include "kdb.h"
-
-#define NDEBUG
-#include <internal/debug.h>
-
-/* FUNCTIONS
*****************************************************************/
-
-#define PROFILE_SESSION_LENGTH 30 /* Session length in seconds */
-
-typedef struct _PROFILE_DATABASE_ENTRY
-{
- ULONG_PTR Address;
-} PROFILE_DATABASE_ENTRY, *PPROFILE_DATABASE_ENTRY;
-
-#define PDE_BLOCK_ENTRIES ((PAGE_SIZE - (sizeof(LIST_ENTRY) +
sizeof(ULONG))) / sizeof(PROFILE_DATABASE_ENTRY))
-
-typedef struct _PROFILE_DATABASE_BLOCK
-{
- LIST_ENTRY ListEntry;
- ULONG UsedEntries;
- PROFILE_DATABASE_ENTRY Entries[PDE_BLOCK_ENTRIES];
-} PROFILE_DATABASE_BLOCK, *PPROFILE_DATABASE_BLOCK;
-
-typedef struct _PROFILE_DATABASE
-{
- LIST_ENTRY ListHead;
-} PROFILE_DATABASE, *PPROFILE_DATABASE;
-
-typedef struct _SAMPLE_GROUP_INFO
-{
- ULONG_PTR Address;
- ULONG Count;
- CHAR Description[128];
- LIST_ENTRY ListEntry;
-} SAMPLE_GROUP_INFO, *PSAMPLE_GROUP_INFO;
-
-static volatile BOOLEAN KdbProfilingInitialized = FALSE;
-static volatile BOOLEAN KdbProfilingEnabled = FALSE;
-static volatile BOOLEAN KdbProfilingSuspended = FALSE;
-static PPROFILE_DATABASE KdbProfileDatabase = NULL;
-static KDPC KdbProfilerCollectorDpc;
-static HANDLE KdbProfilerThreadHandle;
-static CLIENT_ID KdbProfilerThreadCid;
-static HANDLE KdbProfilerLogFile;
-static KTIMER KdbProfilerTimer;
-static KMUTEX KdbProfilerLock;
-static BOOLEAN KdbEnableProfiler = FALSE;
-
-VOID
-KdbDeleteProfileDatabase(PPROFILE_DATABASE ProfileDatabase)
-{
- PLIST_ENTRY current = NULL;
-
- current = RemoveHeadList(&ProfileDatabase->ListHead);
- while (current != &ProfileDatabase->ListHead)
- {
- PPROFILE_DATABASE_BLOCK block = CONTAINING_RECORD(
- current, PROFILE_DATABASE_BLOCK, ListEntry);
- ExFreePool(block);
- current = RemoveHeadList(&ProfileDatabase->ListHead);
- }
-}
-
-VOID
-KdbAddEntryToProfileDatabase(PPROFILE_DATABASE ProfileDatabase,
ULONG_PTR Address)
-{
- PPROFILE_DATABASE_BLOCK block;
-
- if (IsListEmpty(&ProfileDatabase->ListHead))
- {
- block = ExAllocatePool(NonPagedPool,
sizeof(PROFILE_DATABASE_BLOCK));
- ASSERT(block);
- block->UsedEntries = 0;
- InsertTailList(&ProfileDatabase->ListHead, &block->ListEntry);
- block->Entries[block->UsedEntries++].Address = Address;
- return;
- }
-
- block = CONTAINING_RECORD(ProfileDatabase->ListHead.Blink,
PROFILE_DATABASE_BLOCK, ListEntry);
- if (block->UsedEntries >= PDE_BLOCK_ENTRIES)
- {
- block = ExAllocatePool(NonPagedPool,
sizeof(PROFILE_DATABASE_BLOCK));
- ASSERT(block);
- block->UsedEntries = 0;
- InsertTailList(&ProfileDatabase->ListHead, &block->ListEntry);
- }
- block->Entries[block->UsedEntries++].Address = Address;
-}
-
-VOID INIT_FUNCTION
-KdbInitProfiling()
-{
- KdbEnableProfiler = TRUE;
-}
-
-VOID INIT_FUNCTION
-KdbInitProfiling2()
-{
- if (KdbEnableProfiler)
- {
- KdbEnableProfiling();
- KdbProfilingInitialized = TRUE;
- }
-}
-
-VOID
-KdbSuspendProfiling()
-{
- KdbProfilingSuspended = TRUE;
-}
-
-VOID
-KdbResumeProfiling()
-{
- KdbProfilingSuspended = FALSE;
-}
-
-BOOLEAN
-KdbProfilerGetSymbolInfo(PVOID address, OUT PCH NameBuffer)
-{
- PLIST_ENTRY current_entry;
- MODULE_TEXT_SECTION* current;
- extern LIST_ENTRY ModuleTextListHead;
- ULONG_PTR RelativeAddress;
- NTSTATUS Status;
- CHAR FileName[256];
- CHAR FunctionName[256];
-
- current_entry = ModuleTextListHead.Flink;
-
- while (current_entry != &ModuleTextListHead &&
- current_entry != NULL)
- {
- current =
- CONTAINING_RECORD(current_entry, MODULE_TEXT_SECTION,
ListEntry);
-
- if (address >= (PVOID)current->Base &&
- address < (PVOID)(current->Base + current->Length))
- {
- RelativeAddress = (ULONG_PTR) address - current->Base;
- Status = KdbSymGetAddressInformation(current->RosSymInfo,
- RelativeAddress,
- NULL,
- FileName,
- FunctionName);
- if (NT_SUCCESS(Status))
- {
- sprintf(NameBuffer, "%s (%s)", FunctionName, FileName);
- return(TRUE);
- }
- return(TRUE);
- }
- current_entry = current_entry->Flink;
- }
- return(FALSE);
-}
-
-PLIST_ENTRY
-KdbProfilerLargestSampleGroup(PLIST_ENTRY SamplesListHead)
-{
- PLIST_ENTRY current;
- PLIST_ENTRY largest;
- ULONG count;
-
- count = 0;
- largest = SamplesListHead->Flink;
- current = SamplesListHead->Flink;
- while (current != SamplesListHead)
- {
- PSAMPLE_GROUP_INFO sgi = CONTAINING_RECORD(
- current, SAMPLE_GROUP_INFO, ListEntry);
-
- if (sgi->Count > count)
- {
- largest = current;
- count = sgi->Count;
- }
-
- current = current->Flink;
- }
- if (count == 0)
- {
- return NULL;
- }
- return largest;
-}
-
-VOID
-KdbProfilerWriteString(PCH String)
-{
- IO_STATUS_BLOCK Iosb;
- NTSTATUS Status;
- ULONG Length;
-
- Length = strlen(String);
- Status = NtWriteFile(KdbProfilerLogFile,
- NULL,
- NULL,
- NULL,
- &Iosb,
- String,
- Length,
- NULL,
- NULL);
-
- if (!NT_SUCCESS(Status))
- {
- DPRINT1("NtWriteFile() failed with status 0x%.08x\n", Status);
- }
-}
-
-NTSTATUS
-KdbProfilerWriteSampleGroups(PLIST_ENTRY SamplesListHead)
-{
- CHAR Buffer[256];
- PLIST_ENTRY current = NULL;
- PLIST_ENTRY Largest;
-
- KdbProfilerWriteString("\r\n\r\n");
- KdbProfilerWriteString("Count Symbol\r\n");
-
KdbProfilerWriteString("------------------------------------------------
--\r\n");
-
- current = SamplesListHead->Flink;
- while (current != SamplesListHead)
- {
- Largest = KdbProfilerLargestSampleGroup(SamplesListHead);
- if (Largest != NULL)
- {
- PSAMPLE_GROUP_INFO sgi = CONTAINING_RECORD(
- Largest, SAMPLE_GROUP_INFO, ListEntry);
-
- //DbgPrint("%.08lu %s\n", sgi->Count,
sgi->Description);
-
- sprintf(Buffer, "%.08lu %s\r\n", sgi->Count,
sgi->Description);
- KdbProfilerWriteString(Buffer);
-
- RemoveEntryList(Largest);
- ExFreePool(sgi);
- }
- else
- {
- break;
- }
-
- current = SamplesListHead->Flink;
- }
-
- return STATUS_SUCCESS;
-}
-
-LONG STDCALL
-KdbProfilerKeyCompare(IN PVOID Key1,
- IN PVOID Key2)
-{
- int value = strcmp(Key1, Key2);
-
- if (value == 0)
- return 0;
-
- return (value < 0) ? -1 : 1;
-}
-
-
-NTSTATUS
-KdbProfilerAnalyzeSamples()
-{
- CHAR NameBuffer[512];
- ULONG KeyLength;
- PLIST_ENTRY current = NULL;
- HASH_TABLE Hashtable;
- LIST_ENTRY SamplesListHead;
- ULONG Index;
- ULONG_PTR Address;
-
- if (!ExInitializeHashTable(&Hashtable, 12, KdbProfilerKeyCompare,
TRUE))
- {
- DPRINT1("ExInitializeHashTable() failed.");
- KEBUGCHECK(0);
- }
-
- InitializeListHead(&SamplesListHead);
-
- current = RemoveHeadList(&KdbProfileDatabase->ListHead);
- while (current != &KdbProfileDatabase->ListHead)
- {
- PPROFILE_DATABASE_BLOCK block;
-
- block = CONTAINING_RECORD(current, PROFILE_DATABASE_BLOCK,
ListEntry);
-
- for (Index = 0; Index < block->UsedEntries; Index++)
- {
- PSAMPLE_GROUP_INFO sgi;
- Address = block->Entries[Index].Address;
- if (KdbProfilerGetSymbolInfo((PVOID) Address, (PCH)
&NameBuffer))
- {
- }
- else
- {
- sprintf(NameBuffer, "(0x%.08lx)", (ULONG) Address);
- }
-
- KeyLength = strlen(NameBuffer);
- if (!ExSearchHashTable(&Hashtable, (PVOID) NameBuffer,
KeyLength, (PVOID *) &sgi))
- {
- sgi = ExAllocatePool(NonPagedPool,
sizeof(SAMPLE_GROUP_INFO));
- ASSERT(sgi);
- sgi->Address = Address;
- sgi->Count = 1;
- strcpy(sgi->Description, NameBuffer);
- InsertTailList(&SamplesListHead, &sgi->ListEntry);
- ExInsertHashTable(&Hashtable, sgi->Description,
KeyLength, (PVOID) sgi);
- }
- else
- {
- sgi->Count++;
- }
- }
-
- ExFreePool(block);
-
- current = RemoveHeadList(&KdbProfileDatabase->ListHead);
- }
-
- KdbProfilerWriteSampleGroups(&SamplesListHead);
-
- ExDeleteHashTable(&Hashtable);
-
- KdbDeleteProfileDatabase(KdbProfileDatabase);
-
- return STATUS_SUCCESS;
-}
-
-VOID STDCALL
-KdbProfilerThreadMain(PVOID Context)
-{
- for (;;)
- {
- KeWaitForSingleObject(&KdbProfilerTimer, Executive, KernelMode,
TRUE, NULL);
-
- KeWaitForSingleObject(&KdbProfilerLock, Executive, KernelMode,
FALSE, NULL);
-
- KdbSuspendProfiling();
-
- KdbProfilerAnalyzeSamples();
-
- KdbResumeProfiling();
-
- KeReleaseMutex(&KdbProfilerLock, FALSE);
- }
-}
-
-VOID
-KdbDisableProfiling()
-{
- if (KdbProfilingEnabled == TRUE)
- {
- /* FIXME: Implement */
-#if 0
- KdbProfilingEnabled = FALSE;
- /* Stop timer */
- /* Close file */
- if (KdbProfileDatabase != NULL)
- {
- KdbDeleteProfileDatabase(KdbProfileDatabase);
- ExFreePool(KdbProfileDatabase);
- KdbProfileDatabase = NULL;
- }
-#endif
- }
-}
-
-/*
- * SystemArgument1 = EIP
- */
-static VOID STDCALL
-KdbProfilerCollectorDpcRoutine(PKDPC Dpc, PVOID DeferredContext,
- PVOID SystemArgument1, PVOID SystemArgument2)
-{
- ULONG_PTR address = (ULONG_PTR) SystemArgument1;
-
- KdbAddEntryToProfileDatabase(KdbProfileDatabase, address);
-}
-
-VOID INIT_FUNCTION
-KdbEnableProfiling()
-{
- if (KdbProfilingEnabled == FALSE)
- {
- NTSTATUS Status;
- OBJECT_ATTRIBUTES ObjectAttributes;
- UNICODE_STRING FileName;
- IO_STATUS_BLOCK Iosb;
- LARGE_INTEGER DueTime;
-
- RtlInitUnicodeString(&FileName,
L"\\SystemRoot\\profiler.log");
- InitializeObjectAttributes(&ObjectAttributes,
- &FileName,
- 0,
- NULL,
- NULL);
-
- Status = NtCreateFile(&KdbProfilerLogFile,
- FILE_ALL_ACCESS,
- &ObjectAttributes,
- &Iosb,
- NULL,
- FILE_ATTRIBUTE_NORMAL,
- 0,
- FILE_SUPERSEDE,
- FILE_WRITE_THROUGH | FILE_SYNCHRONOUS_IO_NONALERT,
- NULL,
- 0);
- if (!NT_SUCCESS(Status))
- {
- DPRINT1("Failed to create profiler log file\n");
- return;
- }
- KeInitializeMutex(&KdbProfilerLock, 0);
-
- KdbProfileDatabase = ExAllocatePool(NonPagedPool,
sizeof(PROFILE_DATABASE));
- ASSERT(KdbProfileDatabase);
- InitializeListHead(&KdbProfileDatabase->ListHead);
- KeInitializeDpc(&KdbProfilerCollectorDpc,
KdbProfilerCollectorDpcRoutine, NULL);
-
- /* Initialize our periodic timer and its associated DPC
object. When the timer
- expires, the KdbProfilerSessionEndDpc deferred procedure
call (DPC) is queued */
- KeInitializeTimerEx(&KdbProfilerTimer, SynchronizationTimer);
-
- Status = PsCreateSystemThread(&KdbProfilerThreadHandle,
- THREAD_ALL_ACCESS,
- NULL,
- NULL,
- &KdbProfilerThreadCid,
- KdbProfilerThreadMain,
- NULL);
- if (!NT_SUCCESS(Status))
- {
- DPRINT1("Failed to create profiler thread\n");
- return;
- }
-
- /* Start the periodic timer with an initial and periodic
- relative expiration time of PROFILE_SESSION_LENGTH seconds
*/
- DueTime.QuadPart = -(LONGLONG) PROFILE_SESSION_LENGTH * 1000 *
10000;
- KeSetTimerEx(&KdbProfilerTimer, DueTime,
PROFILE_SESSION_LENGTH * 1000, NULL);
-
- KdbProfilingEnabled = TRUE;
- }
-}
-
-VOID
-KdbProfileInterrupt(ULONG_PTR Address)
-{
- ASSERT(KeGetCurrentIrql() == PROFILE_LEVEL);
-
- if (KdbProfilingInitialized != TRUE)
- {
- return;
- }
-
- if ((KdbProfilingEnabled) && (!KdbProfilingSuspended))
- {
- (BOOLEAN) KeInsertQueueDpc(&KdbProfilerCollectorDpc, (PVOID)
Address, NULL);
- }
-}
_____
Deleted: trunk/reactos/ntoskrnl/ex/btree.c
--- trunk/reactos/ntoskrnl/ex/btree.c 2005-03-13 18:39:38 UTC (rev
14021)
+++ trunk/reactos/ntoskrnl/ex/btree.c 2005-03-13 18:41:59 UTC (rev
14022)
@@ -1,644 +0,0 @@
-/* $Id:$
- *
- * COPYRIGHT: See COPYING in the top level directory
- * PROJECT: ReactOS kernel
- * FILE: ntoskrnl/ex/btree.c
- * PURPOSE: Binary tree support
- *
- * PROGRAMMERS: Casper S. Hornstrup (chorns(a)users.sourceforge.net)
- */
-
-#include <ntoskrnl.h>
-#define NDEBUG
-#include <internal/debug.h>
-
-/* DATA
**********************************************************************/
-
-typedef struct _BINARY_TREE_NODE
-{
- struct _BINARY_TREE_NODE * Parent;
- struct _BINARY_TREE_NODE * LeftChild;
- struct _BINARY_TREE_NODE * RightChild;
- PVOID Key;
- PVOID Value;
-} BINARY_TREE_NODE, *PBINARY_TREE_NODE;
-
-typedef struct _TRAVERSE_CONTEXT {
- PTRAVERSE_ROUTINE Routine;
- PVOID Context;
-} TRAVERSE_CONTEXT, *PTRAVERSE_CONTEXT;
-
-/* FUNCTIONS
****************************************************************/
-
-#define ExpBinaryTreeRootNode(Tree)(((PBINARY_TREE) (Tree))->RootNode)
-#define ExpBinaryTreeIsExternalNode(Node)(((Node)->LeftChild == NULL)
&& ((Node)->RightChild == NULL))
-#define
ExpBinaryTreeIsInternalNode(Node)(!ExpBinaryTreeIsExternalNode(Node))
-#define ExpBinaryTreeNodeKey(Node)((Node)->Key)
-#define ExpBinaryTreeNodeValue(Node)((Node)->Value)
-#define ExpBinaryTreeParentNode(Node)((Node)->Parent)
-#define ExpBinaryTreeLeftChildNode(Node)((Node)->LeftChild)
-#define ExpBinaryTreeRightChildNode(Node)((Node)->RightChild)
-#define ExpBinaryTreeNodeEqual(Equality)((Equality) == 0)
-#define ExpBinaryTreeNodeLess(Equality)((Equality) < 0)
-#define ExpBinaryTreeNodeMore(Equality)((Equality) > 0)
-
-
-/*
- * Lock the binary tree
- */
-inline VOID
-ExpLockBinaryTree(PBINARY_TREE Tree,
- PKIRQL OldIrql)
-{
- if (Tree->UseNonPagedPool)
- {
- KeAcquireSpinLock(&Tree->Lock.NonPaged, OldIrql);
- }
- else
- {
- ExAcquireFastMutex(&Tree->Lock.Paged);
- }
-}
-
-
-/*
- * Unlock the binary tree
- */
-inline VOID
-ExpUnlockBinaryTree(PBINARY_TREE Tree,
- PKIRQL OldIrql)
-{
- if (Tree->UseNonPagedPool)
- {
- KeReleaseSpinLock(&Tree->Lock.NonPaged, *OldIrql);
- }
- else
- {
- ExReleaseFastMutex(&Tree->Lock.Paged);
- }
-}
-
-
-/*
- * Allocate resources for a new node and initialize it.
- */
-inline PBINARY_TREE_NODE
-ExpCreateBinaryTreeNode(PBINARY_TREE Tree,
- PBINARY_TREE_NODE Parent,
- PVOID Value)
-{
- PBINARY_TREE_NODE Node;
-
- if (Tree->UseNonPagedPool)
- {
- Node = (PBINARY_TREE_NODE)
ExAllocateFromNPagedLookasideList(&Tree->List.NonPaged);
- }
- else
- {
- Node = (PBINARY_TREE_NODE)
ExAllocateFromPagedLookasideList(&Tree->List.Paged);
- }
-
- if (Node)
- {
- ExpBinaryTreeParentNode(Node) = Parent;
- ExpBinaryTreeLeftChildNode(Node) = NULL;
- ExpBinaryTreeRightChildNode(Node) = NULL;
- ExpBinaryTreeNodeValue(Node) = Value;
- }
-
- return Node;
-}
-
-
-/*
- * Release resources for the node.
- */
-inline VOID
-ExpDestroyBinaryTreeNode(PBINARY_TREE Tree,
- PBINARY_TREE_NODE Node)
-{
- if (Tree->UseNonPagedPool)
- {
- ExFreeToNPagedLookasideList(&Tree->List.NonPaged, Node);
- }
- else
- {
- ExFreeToPagedLookasideList(&Tree->List.Paged, Node);
- }
-}
-
-
-/*
- * Replaces a child node of a node with a new node.
- * The lock for the tree must be acquired when this routine is called.
- */
-inline VOID
-ExpBinaryTreeReplaceChildNode(PBINARY_TREE_NODE Child,
- PBINARY_TREE_NODE NewChild)
-{
- if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) ==
Child)
- {
- ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) =
NewChild;
- }
- else
- {
- ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Child)) =
NewChild;
- }
-}
-
-
-/*
- * Returns the sibling node of a node.
- * The lock for the tree must be acquired when this routine is called.
- */
-inline PBINARY_TREE_NODE
-ExpSiblingBinaryTreeNode(PBINARY_TREE Tree,
- PBINARY_TREE_NODE Node)
-{
- if (Node == ExpBinaryTreeRootNode(Tree))
- {
- return NULL;
- }
- else
- {
- if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node)) ==
Node)
- {
- return
ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Node));
- }
- else
- {
- return
ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node));
- }
- }
-}
-
-
-/*
- * Expands an external node to an internal node.
- * The lock for the tree must be acquired when this routine is called.
- */
-VOID
-ExpExpandExternalBinaryTreeNode(PBINARY_TREE Tree,
- PBINARY_TREE_NODE Node)
-{
- ExpBinaryTreeLeftChildNode(Node) = ExpCreateBinaryTreeNode(Tree,
Node, NULL);
-
- if (!ExpBinaryTreeLeftChildNode(Node))
- {
- /* FIXME: Throw exception */
- DbgPrint("ExpCreateBinaryTreeNode() failed\n");
- }
-
- ExpBinaryTreeRightChildNode(Node) = ExpCreateBinaryTreeNode(Tree,
Node, NULL);
-
- if (!ExpBinaryTreeRightChildNode(Node))
- {
- ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeLeftChildNode(Node));
- /* FIXME: Throw exception */
- DbgPrint("ExpCreateBinaryTreeNode() failed\n");
- }
-}
-
-
-/*
- * Searches a tree for a node with the specified key. If a node with
the
- * specified key is not found, the external node where it should be is
- * returned.
- * The lock for the tree must be acquired when this routine is called.
- */
-inline PBINARY_TREE_NODE
-ExpSearchBinaryTree(PBINARY_TREE Tree,
- PVOID Key,
- PBINARY_TREE_NODE Node)
-{
- LONG Equality;
-
- /* FIXME: Possibly do this iteratively due to the small kernel-mode
stack */
-
- if (ExpBinaryTreeIsExternalNode(Node))
- {
- return Node;
- }
-
- Equality = (*Tree->Compare)(Key, ExpBinaryTreeNodeKey(Node));
-
- if (ExpBinaryTreeNodeEqual(Equality))
- {
- return Node;
- }
-
- if (ExpBinaryTreeNodeLess(Equality))
- {
- return ExpSearchBinaryTree(Tree, Key,
ExpBinaryTreeLeftChildNode(Node));
- }
-
-/* if (ExpBinaryTreeNodeMore(Equality)) */
- {
- return ExpSearchBinaryTree(Tree, Key,
ExpBinaryTreeRightChildNode(Node));
- }
-}
-
-
-/*
- * Removes an external node and it's parent node from the tree.
- * The lock for the tree must be acquired when this routine is called.
- */
-VOID
-ExpRemoveAboveExternalBinaryTreeNode(PBINARY_TREE Tree,
- PBINARY_TREE_NODE Node)
-{
- ASSERTMSG(ExpBinaryTreeIsExternalNode(Node), ("Node is not
external"));
-
- if (Node == ExpBinaryTreeRootNode(Tree))
- {
- return;
- }
- else
- {
- PBINARY_TREE_NODE GrandParent;
- PBINARY_TREE_NODE NewChild;
-
- GrandParent =
ExpBinaryTreeParentNode(ExpBinaryTreeParentNode(Node));
- NewChild = ExpSiblingBinaryTreeNode(Tree, Node);
-
- if (GrandParent != NULL)
- {
- ExpBinaryTreeReplaceChildNode(ExpBinaryTreeParentNode(Node),
NewChild);
- }
-
- ExpDestroyBinaryTreeNode(Tree,
ExpBinaryTreeParentNode(Node));
- ExpDestroyBinaryTreeNode(Tree, Node);
- }
-}
-
-
-/*
- * Release resources used by nodes of a binary (sub)tree.
- */
-VOID
-ExpDeleteBinaryTree(PBINARY_TREE Tree,
- PBINARY_TREE_NODE Node)
-{
- /* FIXME: Possibly do this iteratively due to the small kernel-mode
stack */
-
- if (ExpBinaryTreeIsInternalNode(Node))
- {
- ExpDeleteBinaryTree(Tree, ExpBinaryTreeLeftChildNode(Node));
- ExpDeleteBinaryTree(Tree, ExpBinaryTreeRightChildNode(Node));
- }
-
- ExpDestroyBinaryTreeNode(Tree, Node);
-}
-
-
-/*
- * Traverse a binary tree using preorder traversal method.
- * Returns FALSE, if the traversal was terminated prematurely or
- * TRUE if the callback routine did not request that the traversal
- * be terminated prematurely.
- * The lock for the tree must be acquired when this routine is called.
- */
-BOOLEAN
-ExpTraverseBinaryTreePreorder(PTRAVERSE_CONTEXT Context,
- PBINARY_TREE_NODE Node)
-{
- if (ExpBinaryTreeIsInternalNode(Node))
- {
- /* Call the traversal routine */
- if (!(*Context->Routine)(Context->Context,
- ExpBinaryTreeNodeKey(Node),
- ExpBinaryTreeNodeValue(Node)))
- {
- return FALSE;
- }
-
- /* Traverse left subtree */
- ExpTraverseBinaryTreePreorder(Context,
ExpBinaryTreeLeftChildNode(Node));
-
- /* Traverse right subtree */
- ExpTraverseBinaryTreePreorder(Context,
ExpBinaryTreeRightChildNode(Node));
- }
-
- return TRUE;
-}
-
-
-/*
- * Traverse a binary tree using inorder traversal method.
- * Returns FALSE, if the traversal was terminated prematurely or
- * TRUE if the callback routine did not request that the traversal
- * be terminated prematurely.
- * The lock for the tree must be acquired when this routine is called.
- */
-BOOLEAN
-ExpTraverseBinaryTreeInorder(PTRAVERSE_CONTEXT Context,
- PBINARY_TREE_NODE Node)
-{
- if (ExpBinaryTreeIsInternalNode(Node))
- {
- /* Traverse left subtree */
- ExpTraverseBinaryTreeInorder(Context,
ExpBinaryTreeLeftChildNode(Node));
-
- /* Call the traversal routine */
- if (!(*Context->Routine)(Context->Context,
- ExpBinaryTreeNodeKey(Node),
- ExpBinaryTreeNodeValue(Node)))
- {
- return FALSE;
- }
-
- /* Traverse right subtree */
- ExpTraverseBinaryTreeInorder(Context,
ExpBinaryTreeRightChildNode(Node));
- }
-
- return TRUE;
-}
-
-
-/*
- * Traverse a binary tree using postorder traversal method.
- * Returns FALSE, if the traversal was terminated prematurely or
- * TRUE if the callback routine did not request that the traversal
- * be terminated prematurely.
- * The lock for the tree must be acquired when this routine is called.
- */
-BOOLEAN
-ExpTraverseBinaryTreePostorder(PTRAVERSE_CONTEXT Context,
- PBINARY_TREE_NODE Node)
-{
- if (ExpBinaryTreeIsInternalNode(Node))
- {
- /* Traverse left subtree */
- ExpTraverseBinaryTreePostorder(Context,
ExpBinaryTreeLeftChildNode(Node));
-
- /* Traverse right subtree */
- ExpTraverseBinaryTreePostorder(Context,
ExpBinaryTreeRightChildNode(Node));
-
- /* Call the traversal routine */
- return (*Context->Routine)(Context->Context,
- ExpBinaryTreeNodeKey(Node),
- ExpBinaryTreeNodeValue(Node));
- }
-
- return TRUE;
-}
-
-
-/*
- * Default key compare function. Compares the integer values of the two
keys.
- */
-LONG STDCALL
-ExpBinaryTreeDefaultCompare(PVOID Key1,
- PVOID Key2)
-{
- if (Key1 == Key2)
- return 0;
-
- return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
-}
-
-
-/*
- * Initializes a binary tree.
- */
-BOOLEAN STDCALL
-ExInitializeBinaryTree(IN PBINARY_TREE Tree,
- IN PKEY_COMPARATOR Compare,
- IN BOOLEAN UseNonPagedPool)
-{
- RtlZeroMemory(Tree, sizeof(BINARY_TREE));
-
- Tree->Compare = (Compare == NULL)
- ? ExpBinaryTreeDefaultCompare : Compare;
-
- Tree->UseNonPagedPool = UseNonPagedPool;
-
- if (UseNonPagedPool)
- {
- ExInitializeNPagedLookasideList(
- &Tree->List.NonPaged, /* Lookaside list */
- NULL, /* Allocate routine
*/
- NULL, /* Free routine */
- 0, /* Flags */
- sizeof(BINARY_TREE_NODE), /* Size of each
entry */
- TAG('E','X','B','T'), /* Tag */
- 0); /* Depth */
-
- KeInitializeSpinLock(&Tree->Lock.NonPaged);
- }
- else
- {
- ExInitializePagedLookasideList(
- &Tree->List.Paged, /* Lookaside list */
- NULL, /* Allocate routine
*/
- NULL, /* Free routine */
- 0, /* Flags */
- sizeof(BINARY_TREE_NODE), /* Size of each
entry */
- TAG('E','X','B','T'), /* Tag */
- 0); /* Depth */
-
- ExInitializeFastMutex(&Tree->Lock.Paged);
- }
-
- ExpBinaryTreeRootNode(Tree) = ExpCreateBinaryTreeNode(Tree, NULL,
NULL);
-
- if (ExpBinaryTreeRootNode(Tree) == NULL)
- {
- if (UseNonPagedPool)
- {
- ExDeleteNPagedLookasideList(&Tree->List.NonPaged);
- }
- else
- {
[truncated at 1000 lines; 3443 more skipped]
