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
--- 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 \
--- 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)
--- 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@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);
- }
-}
--- 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@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]