[ion] 13809: Remove kdbg profiling so that NT Native Kernel profiling can be used with it (to come before the merge), more cleanup and movning stuff around, fix building with kdbg (a bug is left with debug flag though), implement KeRemoveSystemDescriptorTable, merge with latest HEAD
4 Mar
2005
4 Mar
'05
12:18 a.m.
Remove kdbg profiling so that NT Native Kernel profiling can be used
with it (to come before the merge), more cleanup and movning stuff
around, fix building with kdbg (a bug is left with debug flag though),
implement KeRemoveSystemDescriptorTable, merge with latest HEAD
Modified: branches/alex_devel_branch/reactos/config
Modified: branches/alex_devel_branch/reactos/include/ddk/kefuncs.h
Modified: branches/alex_devel_branch/reactos/lib/user32/misc/display.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/Makefile
Deleted: branches/alex_devel_branch/reactos/ntoskrnl/dbg/profile.c
Deleted: branches/alex_devel_branch/reactos/ntoskrnl/ex/btree.c
Deleted: branches/alex_devel_branch/reactos/ntoskrnl/ex/hashtab.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ex/init.c
Deleted: branches/alex_devel_branch/reactos/ntoskrnl/ex/stree.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ex/sysinfo.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/io/iomgr.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/kd/kdebug.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ke/i386/gdt.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ke/i386/idt.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ke/i386/irq.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ke/i386/ldt.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ke/i386/main.S
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ke/process.c
Modified: branches/alex_devel_branch/reactos/ntoskrnl/ntoskrnl.def
Modified: branches/alex_devel_branch/reactos/subsys/smss/initss.c
Modified: branches/alex_devel_branch/reactos/subsys/smss/smapiexec.c
Modified: branches/alex_devel_branch/reactos/subsys/smss/smss.h
_____
Modified: branches/alex_devel_branch/reactos/config
--- branches/alex_devel_branch/reactos/config 2005-03-03 21:26:27 UTC
(rev 13808)
+++ branches/alex_devel_branch/reactos/config 2005-03-04 00:18:25 UTC
(rev 13809)
@@ -7,12 +7,12 @@
#
-# Which cpu should reactos optimze for
+# Which cpu should reactos optimize for
# example : i486, i586, pentium, pentium2, pentium3, pentium4
# athlon-xp, athlon-mp, k6-2,
#
-# see gcc manual for more cpu name and which cpu it can
-# be optimze for.
+# see gcc manual for more cpu names and which cpus it can
+# be optimized for.
#
OARCH := pentium2
@@ -20,7 +20,7 @@
#
# Whether to compile in the kernel debugger
#
-KDBG := 0
+KDBG := 1
#
# Whether to compile for debugging
_____
Modified: branches/alex_devel_branch/reactos/include/ddk/kefuncs.h
--- branches/alex_devel_branch/reactos/include/ddk/kefuncs.h
2005-03-03 21:26:27 UTC (rev 13808)
+++ branches/alex_devel_branch/reactos/include/ddk/kefuncs.h
2005-03-04 00:18:25 UTC (rev 13809)
@@ -720,7 +720,7 @@
BOOLEAN
STDCALL
KeRemoveSystemServiceTable(
- IN PUCHAR Number
+ IN ULONG TableIndex
);
NTSTATUS
_____
Modified: branches/alex_devel_branch/reactos/lib/user32/misc/display.c
--- branches/alex_devel_branch/reactos/lib/user32/misc/display.c
2005-03-03 21:26:27 UTC (rev 13808)
+++ branches/alex_devel_branch/reactos/lib/user32/misc/display.c
2005-03-04 00:18:25 UTC (rev 13809)
@@ -200,22 +200,32 @@
{
BOOL rc;
UNICODE_STRING DeviceName;
+ LPDEVMODEW lpDevModeW;
+ lpDevModeW = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY,
+ sizeof(DEVMODEW) + lpDevMode->dmDriverExtra);
+ if ( lpDevModeW == NULL )
+ {
+ SetLastError ( ERROR_OUTOFMEMORY );
+ return FALSE;
+ }
+
if ( !RtlCreateUnicodeStringFromAsciiz ( &DeviceName,
(PCSZ)lpszDeviceName ) )
{
SetLastError ( ERROR_OUTOFMEMORY );
return FALSE;
}
- /*
- * NOTE: We don't need to convert between DEVMODEW and DEVMODEA
because
- * only dmBitsPerPel, dmPelsWidth, dmPelsHeight, dmDisplayFlags and
- * dmDisplayFrequency fields are set.
- */
- rc = NtUserEnumDisplaySettings ( &DeviceName, iModeNum,
(LPDEVMODEW)lpDevMode,
+ lpDevModeW->dmSize = sizeof(DEVMODEW);
+ lpDevModeW->dmDriverExtra = 0;
+
+ rc = NtUserEnumDisplaySettings ( &DeviceName, iModeNum, lpDevModeW,
dwFlags );
+ RosRtlDevModeW2A ( lpDevMode, lpDevModeW );
+
RtlFreeUnicodeString ( &DeviceName );
+ HeapFree ( GetProcessHeap(), 0, lpDevModeW );
return rc;
}
_____
Modified: branches/alex_devel_branch/reactos/ntoskrnl/Makefile
--- branches/alex_devel_branch/reactos/ntoskrnl/Makefile
2005-03-03 21:26:27 UTC (rev 13808)
+++ branches/alex_devel_branch/reactos/ntoskrnl/Makefile
2005-03-04 00:18:25 UTC (rev 13809)
@@ -37,7 +37,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
@@ -58,9 +58,6 @@
TARGET_CFLAGS += -DDBG
endif
-# enable thread event pair features (NT4 only!)
-# TARGET_CFLAGS += -D_ENABLE_THRDEVTPAIR
-
#
# Javascript extension for kdb
#
@@ -238,24 +235,20 @@
# Executive Subsystem (Ex)
OBJECTS_EX = \
- ex/btree.o \
ex/callback.o \
ex/error.o \
ex/event.o \
ex/evtpair.o \
ex/fmutex.o \
- ex/hashtab.o \
ex/init.o \
ex/interlck.o \
ex/list.o \
ex/lookas.o \
ex/mutant.o \
- ex/napi.o \
ex/power.o \
ex/profile.o \
ex/resource.o \
ex/rundown.o \
- ex/stree.o \
ex/sem.o \
ex/synch.o \
ex/sysinfo.o \
@@ -549,8 +542,6 @@
$(PATH_TO_TOP)/include/reactos/bugcodes.h \
$(DEP_OBJECTS) $(DEP_FILES) MSG00409.bin bugcodes.rc
-ex/napi.o: ex/zw.S $(PATH_TO_TOP)/include/ntdll/napi.h
-
ke/main.o: ke/main.c $(PATH_TO_TOP)/include/reactos/buildno.h
$(TARGET_PCH): $(PATH_TO_TOP)/include/reactos/bugcodes.h
_____
Deleted: branches/alex_devel_branch/reactos/ntoskrnl/dbg/profile.c
--- branches/alex_devel_branch/reactos/ntoskrnl/dbg/profile.c
2005-03-03 21:26:27 UTC (rev 13808)
+++ branches/alex_devel_branch/reactos/ntoskrnl/dbg/profile.c
2005-03-04 00:18:25 UTC (rev 13809)
@@ -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: branches/alex_devel_branch/reactos/ntoskrnl/ex/btree.c
--- branches/alex_devel_branch/reactos/ntoskrnl/ex/btree.c
2005-03-03 21:26:27 UTC (rev 13808)
+++ branches/alex_devel_branch/reactos/ntoskrnl/ex/btree.c
2005-03-04 00:18:25 UTC (rev 13809)
@@ -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))
- {
[truncated at 1000 lines; 3008 more skipped]
7236
days inactive
7236
days old
0 comments
1 participants
participants (1)
-
ion＠svn.reactos.com