Ros-diffs July 2010

ros-diffs@reactos.org

17 participants
467 discussions

[sir_richard] 48176: [NTOS]: MiRosTakeOverPebTebRanges now creates a small ~1MB ARM3 memory range on top of the ReactOS per-process VA. This does a couple of things: First of all, it changes the default PEB address to another static address. Still not dynamic like it will be soon, but at least it changes it a bit so we can test if anything breaks due to that. It also likewise changes the addresses of the TEBs (Shifted down by 1MB, basically). Finally, it blocks off that part of address space, wh

by sir_richard＠svn.reactos.org

Author: sir_richard Date: Thu Jul 22 03:22:43 2010 New Revision: 48176 URL: http://svn.reactos.org/svn/reactos?rev=48176&view=rev Log: [NTOS]: MiRosTakeOverPebTebRanges now creates a small ~1MB ARM3 memory range on top of the ReactOS per-process VA. This does a couple of things: First of all, it changes the default PEB address to another static address. Still not dynamic like it will be soon, but at least it changes it a bit so we can test if anything breaks due to that. It also likewise changes the addresses of the TEBs (Shifted down by 1MB, basically). Finally, it blocks off that part of address space, which nobody should be using now, to see if anyone does indeed touch it. [NTOS]: Knowing if this change causes issues will help later in determining regressions due to TEB/PEBs mapped as VADs by ARM3, and regressions simply due to the change in VA layout. [NTOS]: When implemented, the VAD mapping for PEB/TEB will only use that ~1MB, which yes, will limit ReactOS processes to each have only 256 threads. That is obviously a temporary limitation, one I doubt we'll even hit, but I'm putting it out here so you know. Modified: trunk/reactos/ntoskrnl/mm/ARM3/procsup.c trunk/reactos/ntoskrnl/mm/procsup.c Modified: trunk/reactos/ntoskrnl/mm/ARM3/procsup.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/procsup.c… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/procsup.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/mm/ARM3/procsup.c [iso-8859-1] Thu Jul 22 03:22:43 2010 @@ -24,6 +24,29 @@ PVOID BaseAddress); /* PRIVATE FUNCTIONS **********************************************************/ + +VOID +NTAPI +MiRosTakeOverPebTebRanges(IN PEPROCESS Process) +{ + NTSTATUS Status; + PMEMORY_AREA MemoryArea; + PHYSICAL_ADDRESS BoundaryAddressMultiple; + PVOID AllocatedBase = (PVOID)MI_LOWEST_VAD_ADDRESS; + BoundaryAddressMultiple.QuadPart = 0; + + Status = MmCreateMemoryArea(&Process->Vm, + MEMORY_AREA_OWNED_BY_ARM3, + &AllocatedBase, + ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS - 1) - + (ULONG_PTR)MI_LOWEST_VAD_ADDRESS, + PAGE_READWRITE, + &MemoryArea, + TRUE, + 0, + BoundaryAddressMultiple); + ASSERT(NT_SUCCESS(Status)); +} VOID NTAPI @@ -394,8 +417,8 @@ // Peb = MiCreatePebOrTeb(Process, (PVOID)((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1)); - ASSERT(Peb == (PVOID)0x7FFDF000); - + if (!Peb) return STATUS_INSUFFICIENT_RESOURCES; + // // Map NLS Tables // Modified: trunk/reactos/ntoskrnl/mm/procsup.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/procsup.c?rev=… ============================================================================== --- trunk/reactos/ntoskrnl/mm/procsup.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/mm/procsup.c [iso-8859-1] Thu Jul 22 03:22:43 2010 @@ -13,8 +13,10 @@ #define NDEBUG #include <debug.h> +VOID NTAPI MiRosTakeOverPebTebRanges(IN PEPROCESS Process); + /* FUNCTIONS *****************************************************************/ - + PVOID NTAPI MiCreatePebOrTeb(PEPROCESS Process, @@ -111,6 +113,9 @@ FALSE, 0, BoundaryAddressMultiple); + + /* Lock the VAD, ARM3-owned ranges away */ + MiRosTakeOverPebTebRanges(Process); return Status; } @@ -192,7 +197,10 @@ { DPRINT1("Failed to create Shared User Data\n"); goto exit; - } + } + + /* Lock the VAD, ARM3-owned ranges away */ + MiRosTakeOverPebTebRanges(Process); /* The process now has an address space */ Process->HasAddressSpace = TRUE; @@ -319,6 +327,7 @@ case MEMORY_AREA_SHARED_DATA: case MEMORY_AREA_NO_ACCESS: + case MEMORY_AREA_OWNED_BY_ARM3: MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL,

14 years, 5 months

[sir_richard] 48175: [NTOS]: Learn to build User PTEs as well, with MI_MAKE_HARDWARE_PTE_USER. [NTOS]: MI_MAKE_HARDWARE_PTE becomes MI_MAKE_HARDWARE_PTE_KERNEL, since it assumed this. MI_MAKE_HARDWARE_PTE is now a "generic" you can use when you don't know what the PTE should be. It uses MiDetermineUserGlobalMask to set the right bits. [NTOS]: Add two more helpers: MI_IS_PAGE_TABLE_ADDRESS and MI_IS_SYSTEM_PAGE_TABLE_ADDDRESS. One is in the symbols, the other I made up to make things clearer. [NT

by sir_richard＠svn.reactos.org

Author: sir_richard Date: Thu Jul 22 02:20:27 2010 New Revision: 48175 URL: http://svn.reactos.org/svn/reactos?rev=48175&view=rev Log: [NTOS]: Learn to build User PTEs as well, with MI_MAKE_HARDWARE_PTE_USER. [NTOS]: MI_MAKE_HARDWARE_PTE becomes MI_MAKE_HARDWARE_PTE_KERNEL, since it assumed this. MI_MAKE_HARDWARE_PTE is now a "generic" you can use when you don't know what the PTE should be. It uses MiDetermineUserGlobalMask to set the right bits. [NTOS]: Add two more helpers: MI_IS_PAGE_TABLE_ADDRESS and MI_IS_SYSTEM_PAGE_TABLE_ADDDRESS. One is in the symbols, the other I made up to make things clearer. [NTOS]: MiResolveDemandZeroFault now knnows how to resolve user-demand-zero-faults. [NTOS]: Implement MiZeroPfn to do the actual zeroing during user-demand-zero-faults (also later for VAD faults). Modified: trunk/reactos/ntoskrnl/mm/ARM3/miarm.h trunk/reactos/ntoskrnl/mm/ARM3/pagfault.c trunk/reactos/ntoskrnl/mm/ARM3/procsup.c Modified: trunk/reactos/ntoskrnl/mm/ARM3/miarm.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miarm.h?r… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] Thu Jul 22 02:20:27 2010 @@ -192,6 +192,12 @@ #define MI_IS_SESSION_PTE(Pte) \ ((((PMMPTE)Pte) >= MiSessionBasePte) && (((PMMPTE)Pte) < MiSessionLastPte)) + +#define MI_IS_PAGE_TABLE_ADDRESS(Address) \ + (((PVOID)(Address) >= (PVOID)PTE_BASE) && ((PVOID)(Address) <= (PVOID)PTE_TOP)) + +#define MI_IS_SYSTEM_PAGE_TABLE_ADDRESS(Address) \ + (((Address) >= (PVOID)MiAddressToPte(MmSystemRangeStart)) && ((Address) <= (PVOID)PTE_TOP)) // // Corresponds to MMPTE_SOFTWARE.Protection @@ -470,7 +476,60 @@ #define MI_PFNENTRY_TO_PFN(x) (x - MmPfnDatabase[1]) // +// Figures out the hardware bits for a PTE +// +ULONG +FORCEINLINE +MiDetermineUserGlobalPteMask(IN PMMPTE PointerPte) +{ + MMPTE TempPte; + + /* Start fresh */ + TempPte.u.Long = 0; + + /* Make it valid and accessed */ + TempPte.u.Hard.Valid = TRUE; + TempPte.u.Hard.Accessed = TRUE; + + /* Is this for user-mode? */ + if ((PointerPte <= MiHighestUserPte) || + ((PointerPte >= MiAddressToPde(NULL)) && (PointerPte <= MiHighestUserPde))) + { + /* Set the owner bit */ + TempPte.u.Hard.Owner = TRUE; + } + + /* FIXME: We should also set the global bit */ + + /* Return the protection */ + return TempPte.u.Long; +} + +// // Creates a valid kernel PTE with the given protection +// +FORCEINLINE +VOID +MI_MAKE_HARDWARE_PTE_KERNEL(IN PMMPTE NewPte, + IN PMMPTE MappingPte, + IN ULONG ProtectionMask, + IN PFN_NUMBER PageFrameNumber) +{ + /* Only valid for kernel, non-session PTEs */ + ASSERT(MappingPte > MiHighestUserPte); + ASSERT(!MI_IS_SESSION_PTE(MappingPte)); + ASSERT((MappingPte < (PMMPTE)PDE_BASE) || (MappingPte > (PMMPTE)PDE_TOP)); + + /* Start fresh */ + *NewPte = ValidKernelPte; + + /* Set the protection and page */ + NewPte->u.Hard.PageFrameNumber = PageFrameNumber; + NewPte->u.Long |= MmProtectToPteMask[ProtectionMask]; +} + +// +// Creates a valid PTE with the given protection // FORCEINLINE VOID @@ -479,15 +538,30 @@ IN ULONG ProtectionMask, IN PFN_NUMBER PageFrameNumber) { + /* Set the protection and page */ + NewPte->u.Long = MiDetermineUserGlobalPteMask(MappingPte); + NewPte->u.Long |= MmProtectToPteMask[ProtectionMask]; + NewPte->u.Hard.PageFrameNumber = PageFrameNumber; +} + +// +// Creates a valid user PTE with the given protection +// +FORCEINLINE +VOID +MI_MAKE_HARDWARE_PTE_USER(IN PMMPTE NewPte, + IN PMMPTE MappingPte, + IN ULONG ProtectionMask, + IN PFN_NUMBER PageFrameNumber) +{ /* Only valid for kernel, non-session PTEs */ - ASSERT(MappingPte > MiHighestUserPte); - ASSERT(!MI_IS_SESSION_PTE(MappingPte)); - ASSERT((MappingPte < (PMMPTE)PDE_BASE) || (MappingPte > (PMMPTE)PDE_TOP)); + ASSERT(MappingPte <= MiHighestUserPte); /* Start fresh */ *NewPte = ValidKernelPte; /* Set the protection and page */ + NewPte->u.Hard.Owner = TRUE; NewPte->u.Hard.PageFrameNumber = PageFrameNumber; NewPte->u.Long |= MmProtectToPteMask[ProtectionMask]; } Modified: trunk/reactos/ntoskrnl/mm/ARM3/pagfault.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/pagfault.… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/pagfault.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/mm/ARM3/pagfault.c [iso-8859-1] Thu Jul 22 02:20:27 2010 @@ -34,8 +34,7 @@ // // Check if this is a fault while trying to access the page table itself // - if ((Address >= (PVOID)MiAddressToPte(MmSystemRangeStart)) && - (Address < (PVOID)PTE_TOP)) + if (MI_IS_SYSTEM_PAGE_TABLE_ADDRESS(Address)) { // // Send a hint to the page fault handler that this is only a valid fault @@ -82,6 +81,52 @@ // Return status // return Status; +} + +VOID +NTAPI +MiZeroPfn(IN PFN_NUMBER PageFrameNumber) +{ + PMMPTE ZeroPte; + MMPTE TempPte; + PMMPFN Pfn1; + PVOID ZeroAddress; + + /* Get the PFN for this page */ + Pfn1 = MiGetPfnEntry(PageFrameNumber); + ASSERT(Pfn1); + + /* Grab a system PTE we can use to zero the page */ + ZeroPte = MiReserveSystemPtes(1, SystemPteSpace); + ASSERT(ZeroPte); + + /* Initialize the PTE for it */ + TempPte = ValidKernelPte; + TempPte.u.Hard.PageFrameNumber = PageFrameNumber; + + /* Setup caching */ + if (Pfn1->u3.e1.CacheAttribute == MiWriteCombined) + { + /* Write combining, no caching */ + MI_PAGE_DISABLE_CACHE(&TempPte); + MI_PAGE_WRITE_COMBINED(&TempPte); + } + else if (Pfn1->u3.e1.CacheAttribute == MiNonCached) + { + /* Write through, no caching */ + MI_PAGE_DISABLE_CACHE(&TempPte); + MI_PAGE_WRITE_THROUGH(&TempPte); + } + + /* Make the system PTE valid with our PFN */ + MI_WRITE_VALID_PTE(ZeroPte, TempPte); + + /* Get the address it maps to, and zero it out */ + ZeroAddress = MiPteToAddress(ZeroPte); + KeZeroPages(ZeroAddress, PAGE_SIZE); + + /* Now get rid of it */ + MiReleaseSystemPtes(ZeroPte, 1, SystemPteSpace); } NTSTATUS @@ -93,13 +138,24 @@ { PFN_NUMBER PageFrameNumber; MMPTE TempPte; + BOOLEAN NeedZero = FALSE; DPRINT("ARM3 Demand Zero Page Fault Handler for address: %p in process: %p\n", Address, Process); - /* Must currently only be called by paging path, for system addresses only */ + /* Must currently only be called by paging path */ ASSERT(OldIrql == MM_NOIRQL); - ASSERT(Process == NULL); + if (Process) + { + /* Sanity check */ + ASSERT(MI_IS_PAGE_TABLE_ADDRESS(PointerPte)); + + /* No forking yet */ + ASSERT(Process->ForkInProgress == NULL); + + /* We'll need a zero page */ + NeedZero = TRUE; + } // // Lock the PFN database @@ -124,11 +180,31 @@ // InterlockedIncrement(&KeGetCurrentPrcb()->MmDemandZeroCount); - /* Shouldn't see faults for user PTEs yet */ - ASSERT(PointerPte > MiHighestUserPte); + /* Zero the page if need be */ + if (NeedZero) MiZeroPfn(PageFrameNumber); /* Build the PTE */ - MI_MAKE_HARDWARE_PTE(&TempPte, PointerPte, PointerPte->u.Soft.Protection, PageFrameNumber); + if (PointerPte <= MiHighestUserPte) + { + /* For user mode */ + MI_MAKE_HARDWARE_PTE_USER(&TempPte, + PointerPte, + PointerPte->u.Soft.Protection, + PageFrameNumber); + } + else + { + /* For kernel mode */ + MI_MAKE_HARDWARE_PTE(&TempPte, + PointerPte, + PointerPte->u.Soft.Protection, + PageFrameNumber); + } + + /* Set it dirty if it's a writable page */ + if (TempPte.u.Hard.Write) TempPte.u.Hard.Dirty = TRUE; + + /* Write it */ MI_WRITE_VALID_PTE(PointerPte, TempPte); // Modified: trunk/reactos/ntoskrnl/mm/ARM3/procsup.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/procsup.c… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/procsup.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/mm/ARM3/procsup.c [iso-8859-1] Thu Jul 22 02:20:27 2010 @@ -156,7 +156,7 @@ MI_MAKE_SOFTWARE_PTE(&InvalidPte, MM_NOACCESS); /* Setup the template stack PTE */ - MI_MAKE_HARDWARE_PTE(&TempPte, PointerPte + 1, MM_READWRITE, 0); + MI_MAKE_HARDWARE_PTE_KERNEL(&TempPte, PointerPte + 1, MM_READWRITE, 0); // // Acquire the PFN DB lock @@ -270,7 +270,7 @@ MiInitializePfn(PageFrameIndex, LimitPte, 1); /* Setup the template stack PTE */ - MI_MAKE_HARDWARE_PTE(&TempPte, LimitPte, MM_READWRITE, PageFrameIndex); + MI_MAKE_HARDWARE_PTE_KERNEL(&TempPte, LimitPte, MM_READWRITE, PageFrameIndex); /* Write the valid PTE */ MI_WRITE_VALID_PTE(LimitPte--, TempPte);

14 years, 5 months

[sir_richard] 48174: [NTOS]: Add missing definitions, should fix build.

by sir_richard＠svn.reactos.org

Author: sir_richard Date: Thu Jul 22 02:10:43 2010 New Revision: 48174 URL: http://svn.reactos.org/svn/reactos?rev=48174&view=rev Log: [NTOS]: Add missing definitions, should fix build. Modified: trunk/reactos/ntoskrnl/mm/ARM3/miarm.h Modified: trunk/reactos/ntoskrnl/mm/ARM3/miarm.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miarm.h?r… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] Thu Jul 22 02:10:43 2010 @@ -39,6 +39,9 @@ #define MM_HIGHEST_VAD_ADDRESS \ (PVOID)((ULONG_PTR)MM_HIGHEST_USER_ADDRESS - (16 * PAGE_SIZE)) + +/* The range 0x10000->0x7FEFFFFF is reserved for the ROSMM MAREA Allocator */ +#define MI_LOWEST_VAD_ADDRESS (PVOID)0x7FF00000 #endif /* !_M_AMD64 */ @@ -826,4 +829,35 @@ IN PMMPFN Pfn1 ); +PMMVAD +NTAPI +MiLocateAddress( + IN PVOID VirtualAddress +); + +PMMADDRESS_NODE +NTAPI +MiCheckForConflictingNode( + IN ULONG_PTR StartVpn, + IN ULONG_PTR EndVpn, + IN PMM_AVL_TABLE Table +); + +NTSTATUS +NTAPI +MiFindEmptyAddressRangeDownTree( + IN SIZE_T Length, + IN ULONG_PTR BoundaryAddress, + IN ULONG_PTR Alignment, + IN PMM_AVL_TABLE Table, + OUT PULONG_PTR Base +); + +VOID +NTAPI +MiInsertNode( + IN PMMADDRESS_NODE NewNode, + IN PMM_AVL_TABLE Table +); + /* EOF */

14 years, 5 months

[sir_richard] 48173: This patch introduces a highly-shareable version of AVL trees both for RTL usage and for ARM3's MM_AVL_TABLE/MMADDRESS_NODE structures used by VADs on Windows (and soon, ReactOS): [RTL]: Uncouple generic table from AVL table implementation into its own avltable.c [RTL]: Get rid of "Austin" and fix prototypes of AVL table functions. [RTL]: Re-implement AVL table functions, sharing as much code as possible with the SPLAY tree implementation which is pretty decent. Lookup, inse

by sir_richard＠svn.reactos.org

Author: sir_richard Date: Thu Jul 22 01:41:45 2010 New Revision: 48173 URL: http://svn.reactos.org/svn/reactos?rev=48173&view=rev Log: This patch introduces a highly-shareable version of AVL trees both for RTL usage and for ARM3's MM_AVL_TABLE/MMADDRESS_NODE structures used by VADs on Windows (and soon, ReactOS): [RTL]: Uncouple generic table from AVL table implementation into its own avltable.c [RTL]: Get rid of "Austin" and fix prototypes of AVL table functions. [RTL]: Re-implement AVL table functions, sharing as much code as possible with the SPLAY tree implementation which is pretty decent. Lookup, insert, enumeration are implemented, but not delete. [RTL]: Make large part of the RTL AVL package into its own "support" file that can work both with MMADDRESS_NODE and RTL_BALANCED_LINKS structures. The former is used by ARM3 for VADs. [NTOS]: Implement basic VAD AVL tree routines (Insert, LookupEmpty, GetPrevious, CheckForConflict, Locate). This is enough to insert VADs, find a free address range, and locate a VAD by address. No delete yet Thanks to Timo Kreuzer for some clever definitions, Knuth for his genius, several online C implementations for ideas, the HPI kernel blog for insight on how Windows does it, and others. Added: trunk/reactos/lib/rtl/avlsupp.c (with props) trunk/reactos/lib/rtl/avltable.c (with props) trunk/reactos/lib/rtl/rtlavl.h (with props) trunk/reactos/ntoskrnl/mm/ARM3/miavl.h (with props) trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c (with props) Removed: trunk/reactos/lib/rtl/austin/ Modified: trunk/reactos/lib/rtl/generictable.c trunk/reactos/lib/rtl/rtl.rbuild trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild Added: trunk/reactos/lib/rtl/avlsupp.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avlsupp.c?rev=4817… ============================================================================== --- trunk/reactos/lib/rtl/avlsupp.c (added) +++ trunk/reactos/lib/rtl/avlsupp.c [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -1,0 +1,295 @@ +/* + * PROJECT: ReactOS Runtime Library + * LICENSE: BSD - See COPYING.ARM in the top level directory + * FILE: lib/rtl/avlsupp.c + * PURPOSE: AVL Tree Internal Support Routines/Main Algorithms + * PROGRAMMERS: ReactOS Portable Systems Group + */ + +/* INCLUDES ******************************************************************/ + +/* Internal header for table entries */ +typedef struct _TABLE_ENTRY_HEADER +{ + RTL_BALANCED_LINKS BalancedLinks; + LIST_ENTRY ListEntry; + LONGLONG UserData; +} TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER; + +typedef enum _RTL_AVL_BALANCE_FACTOR +{ + RtlUnbalancedAvlTree = -2, + RtlLeftHeavyAvlTree, + RtlBalancedAvlTree, + RtlRightHeavyAvlTree, +} RTL_AVL_BALANCE_FACTOR; + +C_ASSERT(RtlBalancedAvlTree == 0); + +/* FUNCTIONS ******************************************************************/ + +TABLE_SEARCH_RESULT +FORCEINLINE +RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + OUT PRTL_BALANCED_LINKS *NodeOrParent) +{ + PRTL_BALANCED_LINKS CurrentNode, ChildNode; + RTL_GENERIC_COMPARE_RESULTS Result; + + /* Quick check to see if the table is empty */ + if (!Table->NumberGenericTableElements) return TableEmptyTree; + + /* Set the current node */ + CurrentNode = RtlRightChildAvl(&Table->BalancedRoot); + + /* Start compare loop */ + while (TRUE) + { + /* Compare which side is greater */ + Result = RtlpAvlCompareRoutine(Table, + Buffer, + &((PTABLE_ENTRY_HEADER)CurrentNode)-> + UserData); + if (Result == GenericLessThan) + { + /* We're less, check if this is the left child */ + ChildNode = RtlLeftChildAvl(CurrentNode); + if (ChildNode) + { + /* Continue searching from this node */ + CurrentNode = ChildNode; + } + else + { + /* Otherwise, the element isn't in this tree */ + *NodeOrParent = CurrentNode; + return TableInsertAsLeft; + } + } + else if (Result == GenericGreaterThan) + { + /* We're more, check if this is the right child */ + ChildNode = RtlRightChildAvl(CurrentNode); + if (ChildNode) + { + /* Continue searching from this node */ + CurrentNode = ChildNode; + } + else + { + /* Otherwise, the element isn't in this tree */ + *NodeOrParent = CurrentNode; + return TableInsertAsRight; + } + } + else + { + /* We should've found the node */ + ASSERT(Result == GenericEqual); + + /* Return node found */ + *NodeOrParent = CurrentNode; + return TableFoundNode; + } + } +} + +VOID +FORCEINLINE +RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node) +{ + PRTL_BALANCED_LINKS ParentNode, SuperParentNode; + PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2; + + /* Grab parents up to 2 levels high */ + ParentNode = RtlParentAvl(Node); + SuperParentNode = RtlParentAvl(ParentNode); + + /* Pick which nodes will be rotated */ + SwapNode1 = RtlIsLeftChildAvl(Node) ? &ParentNode->LeftChild : &ParentNode->RightChild; + SwapNode2 = RtlIsLeftChildAvl(Node) ? &Node->RightChild : &Node->LeftChild; + + /* Do the rotate, and update the parent and super-parent as needed */ + *SwapNode1 = *SwapNode2; + if (*SwapNode1) RtlSetParent(*SwapNode1, ParentNode); + *SwapNode2 = ParentNode; + RtlSetParent(ParentNode, Node); + + /* Now update the super-parent child link, and make it parent of the node*/ + SwapNode1 = (RtlLeftChildAvl(SuperParentNode) == ParentNode) ? + &SuperParentNode->LeftChild: &SuperParentNode->RightChild; + *SwapNode1 = Node; + RtlSetParent(Node, SuperParentNode); +} + +BOOLEAN +FORCEINLINE +RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node) +{ + PRTL_BALANCED_LINKS ChildNode, SubChildNode; + CHAR Balance; + ASSERT(RtlParentAvl(Node) != Node); + + /* Get the balance, and figure out which child node to go down on */ + Balance = RtlBalance(Node); + ChildNode = (Balance == RtlRightHeavyAvlTree) ? + RtlRightChildAvl(Node) : RtlLeftChildAvl(Node); + + /* The child and node have the same balance, promote the child upwards */ + if (RtlBalance(ChildNode) == Balance) + { + /* This performs the rotation described in Knuth A8-A10 for Case 1 */ + RtlPromoteAvlTreeNode(ChildNode); + + /* The nodes are now balanced */ + RtlSetBalance(ChildNode, RtlBalancedAvlTree); + RtlSetBalance(Node, RtlBalancedAvlTree); + return FALSE; + } + + /* The child has the opposite balance, a double promotion of the child's child must happen */ + if (RtlBalance(ChildNode) == -Balance) + { + /* Pick which sub-child to use based on the balance */ + SubChildNode = (Balance == RtlRightHeavyAvlTree) ? + RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode); + + /* Do the double-rotation described in Knuth A8-A10 for Case 2 */ + RtlPromoteAvlTreeNode(SubChildNode); + RtlPromoteAvlTreeNode(SubChildNode); + + /* Was the sub-child sharing the same balance as the node? */ + if (RtlBalance(SubChildNode) == Balance) + { + /* Then the subchild is now balanced, and the node's weight is inversed */ + RtlSetBalance(ChildNode, RtlBalancedAvlTree); + RtlSetBalance(Node, -Balance); + } + else if (RtlBalance(SubChildNode) == -Balance) + { + /* + * In this case, the sub-child weight was the inverse of the node, so + * the child now shares the node's balance original weight, while the + * node becomes balanced. + */ + RtlSetBalance(ChildNode, Balance); + RtlSetBalance(Node, RtlBalancedAvlTree); + } + else + { + /* + * Otherwise, the sub-child was unbalanced, so both the child and node + * now become balanced. + */ + RtlSetBalance(ChildNode, RtlBalancedAvlTree); + RtlSetBalance(Node, RtlBalancedAvlTree); + } + + /* In all cases, the sub-child is now balanced */ + RtlSetBalance(SubChildNode, RtlBalancedAvlTree); + return FALSE; + } + + /* + * The case that remains is that the child was already balanced, so this is + * This is the rotation required for Case 3 in Knuth A8-A10 + */ + RtlPromoteAvlTreeNode(ChildNode); + + /* Now the child has the opposite weight of the node */ + RtlSetBalance(ChildNode, -Balance); + + /* This only happens on deletion, so we return TRUE to terminate the delete */ + return TRUE; +} + +VOID +FORCEINLINE +RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table, + IN PRTL_BALANCED_LINKS NewNode, + IN OUT PVOID NodeOrParent, + IN OUT TABLE_SEARCH_RESULT SearchResult) +{ + CHAR Balance; + + /* Initialize the new inserted element */ + MI_ASSERT(SearchResult != TableFoundNode); + NewNode->LeftChild = NewNode->RightChild = NULL; + + /* Increase element count */ + Table->NumberGenericTableElements++; + + /* Check where we should insert the entry */ + if (SearchResult == TableEmptyTree) + { + /* This is the new root node */ + RtlInsertAsRightChildAvl(&Table->BalancedRoot, NewNode); + MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree); + + /* On AVL trees, we also update the depth */ + ASSERT(Table->DepthOfTree == 0); + Table->DepthOfTree = 1; + return; + } + else if (SearchResult == TableInsertAsLeft) + { + /* Insert it left */ + RtlInsertAsLeftChildAvl(NodeOrParent, NewNode); + } + else + { + /* Right node */ + RtlInsertAsRightChildAvl(NodeOrParent, NewNode); + } + + /* Little cheat to save on loop processing, taken from Timo */ + MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree); + RtlSetBalance(&Table->BalancedRoot, RtlLeftHeavyAvlTree); + + /* + * This implements A6-A7 from Knuth based on http://coding.derkeiler.com + * /pdf/Archive/C_CPP/comp.lang.c/2004-01/1812.pdf, however the algorithm + * is slightly modified to follow the tree based on the Parent Node such + * as the Windows algorithm does it, instead of following the nodes down. + */ + while (TRUE) + { + /* Calculate which side to balance on */ + Balance = RtlIsLeftChildAvl(NewNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree; + + /* Check if the parent node was balanced */ + if (RtlBalance(NodeOrParent) == RtlBalancedAvlTree) + { + /* It's not balanced anymore (heavy on one side) */ + RtlSetBalance(NodeOrParent, Balance); + + /* Move up */ + NewNode = NodeOrParent; + NodeOrParent = RtlParentAvl(NodeOrParent); + } + else if (RtlBalance(NodeOrParent) != Balance) + { + /* The parent's balance is opposite, so the tree is balanced now */ + RtlSetBalance(NodeOrParent, RtlBalancedAvlTree); + + /* Check if this is the root (the cheat applied earlier gets us here) */ + if (RtlBalance(&Table->BalancedRoot) == RtlBalancedAvlTree) + { + /* The depth has thus increased */ + Table->DepthOfTree++; + } + + /* We reached the root or a balanced node, so we're done */ + break; + } + else + { + /* The tree is now unbalanced, so AVL rebalancing must happen */ + RtlpRebalanceAvlTreeNode(NodeOrParent); + break; + } + } +} + +/* EOF */ Propchange: trunk/reactos/lib/rtl/avlsupp.c ------------------------------------------------------------------------------ svn:eol-style = native Added: trunk/reactos/lib/rtl/avltable.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avltable.c?rev=481… ============================================================================== --- trunk/reactos/lib/rtl/avltable.c (added) +++ trunk/reactos/lib/rtl/avltable.c [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -1,0 +1,303 @@ +/* +* PROJECT: ReactOS Runtime Library +* LICENSE: BSD - See COPYING.ARM in the top level directory +* FILE: lib/rtl/avltable.c +* PURPOSE: AVL Tree Generic Table Implementation +* PROGRAMMERS: ReactOS Portable Systems Group +*/ + +/* INCLUDES ******************************************************************/ + +#include <rtl.h> +#define NDEBUG +#include <debug.h> + +/* Include RTL version of AVL support */ +#include "rtlavl.h" +#include "avlsupp.c" + +/* AVL FUNCTIONS *************************************************************/ + +/* + * @implemented + */ +VOID +NTAPI +RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table, + IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine, + IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine, + IN PRTL_AVL_FREE_ROUTINE FreeRoutine, + IN PVOID TableContext) +{ + /* Setup the table */ + RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE)); + Table->BalancedRoot.Parent = &Table->BalancedRoot; + Table->CompareRoutine = CompareRoutine; + Table->AllocateRoutine = AllocateRoutine; + Table->FreeRoutine = FreeRoutine; + Table->TableContext = TableContext; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN ULONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL, + IN OUT PVOID NodeOrParent, + IN OUT TABLE_SEARCH_RESULT SearchResult) +{ + PRTL_BALANCED_LINKS NewNode; + PVOID UserData; + + /* Check if the entry wasn't already found */ + if (SearchResult != TableFoundNode) + { + /* We're doing an allocation, sanity check */ + ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1)); + + /* Allocate a node */ + NewNode = Table->AllocateRoutine(Table, + BufferSize + + FIELD_OFFSET(TABLE_ENTRY_HEADER, + UserData)); + if (!NewNode) + { + /* No memory or other allocation error, fail */ + if (NewElement) *NewElement = FALSE; + return NULL; + } + + /* Data to return to user */ + UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData; + + /* Insert the node in the tree */ + RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, SearchResult); + + /* Copy user buffer */ + RtlCopyMemory(UserData, Buffer, BufferSize); + } + else + { + /* Return the node we already found */ + NewNode = NodeOrParent; + UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData; + } + + /* Return status */ + if (NewElement) *NewElement = (SearchResult == TableFoundNode); + + /* Return pointer to user data */ + return UserData; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN ULONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL) +{ + PRTL_BALANCED_LINKS NodeOrParent = NULL; + TABLE_SEARCH_RESULT Result; + + /* Get the balanced links and table search result immediately */ + Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent); + + /* Now call the routine to do the full insert */ + return RtlInsertElementGenericTableFullAvl(Table, + Buffer, + BufferSize, + NewElement, + NodeOrParent, + Result); +} + +/* + * @implemented + */ +BOOLEAN +NTAPI +RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table) +{ + /* If there's no elements, the table is empty */ + return Table->NumberGenericTableElements == 0; +} + +/* + * @implemented + */ +ULONG +NTAPI +RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table) +{ + /* Return the element count */ + return Table->NumberGenericTableElements; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN OUT PVOID *NodeOrParent, + IN OUT TABLE_SEARCH_RESULT *SearchResult) +{ + /* Find the node */ + *SearchResult = RtlpFindAvlTableNodeOrParent(Table, + Buffer, + (PRTL_BALANCED_LINKS*)NodeOrParent); + if (*SearchResult != TableFoundNode) return NULL; + + /* Node found, return the user data */ + return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer) +{ + PRTL_BALANCED_LINKS NodeOrParent; + TABLE_SEARCH_RESULT Lookup; + + /* Call the full function */ + return RtlLookupElementGenericTableFullAvl(Table, + Buffer, + (PVOID*)&NodeOrParent, + &Lookup); +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN BOOLEAN Restart) +{ + /* Reset the restart key if needed */ + if (Restart) Table->RestartKey = NULL; + + /* Call the full function */ + return RtlEnumerateGenericTableWithoutSplayingAvl(Table, + (PVOID*)&Table->RestartKey); +} + +/* +* @implemented +*/ +PVOID +NTAPI +RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + OUT PVOID *RestartKey) +{ + PRTL_BALANCED_LINKS Node, PreviousNode; + TABLE_SEARCH_RESULT SearchResult; + RTL_GENERIC_COMPARE_RESULTS Result = GenericEqual; + + /* Assume failure */ + *RestartKey = NULL; + + /* Find the node */ + SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node); + if (SearchResult != TableFoundNode) return NULL; + + /* Scan each predecessor until a match is found */ + PreviousNode = Node; + while (Result == GenericEqual) + { + /* Save the node */ + Node = PreviousNode; + + /* Get the predecessor */ + PreviousNode = RtlRealPredecessorAvl(Node); + if ((!PreviousNode) || (RtlParentAvl(PreviousNode) == PreviousNode)) break; + + /* Check if this node matches */ + Result = RtlpAvlCompareRoutine(Table, + Buffer, + &((PTABLE_ENTRY_HEADER)PreviousNode)-> + UserData); + } + + /* Save the node as the restart key, and return its data */ + *RestartKey = Node; + return &((PTABLE_ENTRY_HEADER)Node)->UserData; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, + IN OUT PVOID *RestartKey) +{ + PRTL_BALANCED_LINKS CurrentNode; + + /* Skip an empty tree */ + if (RtlIsGenericTableEmptyAvl(Table)) return NULL; + + /* Check if we have a starting point */ + if (!*RestartKey) + { + /* We'll have to find it, keep going until the leftmost child */ + for (CurrentNode = RtlRightChildAvl(&Table->BalancedRoot); + RtlLeftChildAvl(CurrentNode); + CurrentNode = RtlLeftChildAvl(CurrentNode)); + + /* Found it */ + *RestartKey = CurrentNode; + } + else + { + /* We already had a child, keep going by getting its successor */ + CurrentNode = RtlRealSuccessorAvl(*RestartKey); + + /* If there was one, update the restart key */ + if (CurrentNode) *RestartKey = CurrentNode; + } + + /* Return the node's data if it was found, otherwise return NULL */ + if (CurrentNode) return &((PTABLE_ENTRY_HEADER)CurrentNode)->UserData; + return NULL; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN ULONG I) +{ + UNIMPLEMENTED; + return NULL; +} + +/* + * @implemented + */ +BOOLEAN +NTAPI +RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer) +{ + UNIMPLEMENTED; + return FALSE; +} + +/* EOF */ Propchange: trunk/reactos/lib/rtl/avltable.c ------------------------------------------------------------------------------ svn:eol-style = native Modified: trunk/reactos/lib/rtl/generictable.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev… ============================================================================== --- trunk/reactos/lib/rtl/generictable.c [iso-8859-1] (original) +++ trunk/reactos/lib/rtl/generictable.c [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -1,16 +1,14 @@ /* -* PROJECT: ReactOS Kernel +* PROJECT: ReactOS Runtime Library * LICENSE: GPL - See COPYING in the top level directory * FILE: lib/rtl/generictable.c -* PURPOSE: Splay Tree and AVL Tree Generic Table Implementation +* PURPOSE: Splay Tree Generic Table Implementation * PROGRAMMERS: Alex Ionescu (alex.ionescu(a)reactos.org) -* Art Yerks (ayerkes(a)speakeasy.net) */ /* INCLUDES ******************************************************************/ #include <rtl.h> -#include "austin/avl.h" #define NDEBUG #include <debug.h> @@ -508,261 +506,4 @@ ListEntry))->UserData; } -/* AVL FUNCTIONS *************************************************************/ - -/* - * @implemented - */ -PVOID -NTAPI -RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, - IN PVOID Buffer, - IN OUT PVOID *NodeOrParent, - IN OUT TABLE_SEARCH_RESULT *SearchResult) -{ - PRTL_BALANCED_LINKS OurNodeOrParent; - TABLE_SEARCH_RESULT OurSearchResult; - - if( !Table->NumberGenericTableElements ) - { - *SearchResult = TableEmptyTree; - *NodeOrParent = NULL; - return NULL; - } - - OurSearchResult = avl_search - (Table, Buffer, - Table->BalancedRoot.LeftChild, &OurNodeOrParent); - - if(SearchResult) *SearchResult = OurSearchResult; - if(NodeOrParent) *NodeOrParent = OurNodeOrParent; - - if(OurSearchResult == TableFoundNode) - return avl_data(OurNodeOrParent); - else - return NULL; -} - -/* - * @implemented - */ -PVOID -NTAPI -RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table, - IN PVOID Buffer) -{ - PRTL_BALANCED_LINKS OurNodeOrParent; - TABLE_SEARCH_RESULT OurSearchResult; - return RtlLookupElementGenericTableFullAvl - (Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult); -} - -/* - * @implemented - */ -BOOLEAN -NTAPI -RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table, - IN PVOID Buffer) -{ - TABLE_SEARCH_RESULT Result; - PRTL_BALANCED_LINKS Node; - - RtlLookupElementGenericTableFullAvl - ( Table, Buffer, (PVOID *)&Node, &Result ); - - if( Result == TableFoundNode ) - { - avl_delete_node(Table, Node); - Table->FreeRoutine(Table, Node); - if( Table->NumberGenericTableElements == 0 ) - avl_deinit(Table); - return TRUE; - } - else - { - return FALSE; - } -} - -/* - * @implemented - */ -PVOID -NTAPI -RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table, - IN BOOLEAN Restart) -{ - if( Table->NumberGenericTableElements == 0 ) - return NULL; - - if( Restart ) - { - Table->RestartKey = avl_first(Table); - } - else - { - Table->RestartKey = avl_next(Table, Table->RestartKey); - } - if( !Table->RestartKey ) - return NULL; - else - return avl_data(Table->RestartKey); -} - -/* - * @implemented - */ -PVOID -NTAPI -RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, - IN OUT PVOID *RestartKey) -{ - /* FIXME! */ - return NULL; -} - -/* - * @implemented - */ -PVOID -NTAPI -RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table, - IN ULONG I) -{ - PRTL_BALANCED_LINKS Node; - - if( I >= Table->NumberGenericTableElements ) return NULL; - else - { - Node = avl_first(Table); - while(I--) Node = avl_next(Table, Node); - return avl_data(Node); - } -} - -/* - * @implemented - */ -VOID -NTAPI -RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table, - IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine, - IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine, - IN PRTL_AVL_FREE_ROUTINE FreeRoutine, - IN PVOID TableContext) -{ - RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE)); - Table->BalancedRoot.Parent = &Table->BalancedRoot; - Table->CompareRoutine = CompareRoutine; - Table->AllocateRoutine = AllocateRoutine; - Table->FreeRoutine = FreeRoutine; - Table->TableContext = TableContext; -} - -/* - * @implemented - */ -PVOID -NTAPI -RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, - IN PVOID Buffer, - IN ULONG BufferSize, - OUT PBOOLEAN NewElement OPTIONAL, - IN OUT PVOID *NodeOrParent, - IN OUT TABLE_SEARCH_RESULT *SearchResult) -{ - PRTL_BALANCED_LINKS OurNodeOrParent; - TABLE_SEARCH_RESULT OurSearchResult; - - if(Table->NumberGenericTableElements == 0) { - avl_init(Table); - } - - if(NewElement) - *NewElement = FALSE; - - OurSearchResult = avl_search - (Table, Buffer, - Table->BalancedRoot.LeftChild, &OurNodeOrParent); - - if(NodeOrParent) *NodeOrParent = OurNodeOrParent; - if(SearchResult) *SearchResult = OurSearchResult; - - if(OurSearchResult == TableFoundNode) - { - RtlDeleteElementGenericTableAvl(Table, Buffer); - return RtlInsertElementGenericTableFullAvl - (Table, Buffer, BufferSize, - NewElement, NodeOrParent, SearchResult); - } - else - { - PRTL_BALANCED_LINKS NewNode = - Table->AllocateRoutine - (Table, - BufferSize + sizeof(RTL_BALANCED_LINKS) + BufferSize); - - if( !NewNode ) return NULL; - - NewNode->Balance = 0; - RtlCopyMemory(avl_data(NewNode), Buffer, BufferSize); - - OurNodeOrParent = NewNode; - - avl_insert_node(Table, NewNode); - return avl_data(NewNode); - } -} - -/* - * @implemented - */ -PVOID -NTAPI -RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table, - IN PVOID Buffer, - IN ULONG BufferSize, - OUT PBOOLEAN NewElement OPTIONAL) -{ - PVOID NodeOrParent; - TABLE_SEARCH_RESULT SearchResult; - - return RtlInsertElementGenericTableFullAvl - (Table, Buffer, BufferSize, NewElement, &NodeOrParent, &SearchResult); -} - -/* - * @implemented - */ -BOOLEAN -NTAPI -RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE Table) -{ - return Table->NumberGenericTableElements == 0; -} - -/* - * @implemented - */ -ULONG -NTAPI -RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table) -{ - return Table->NumberGenericTableElements; -} - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table, - IN PVOID Buffer, - OUT PVOID *RestartKey) -{ - UNIMPLEMENTED; - return NULL; -} - /* EOF */ Modified: trunk/reactos/lib/rtl/rtl.rbuild URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/rtl.rbuild?rev=481… ============================================================================== --- trunk/reactos/lib/rtl/rtl.rbuild [iso-8859-1] (original) +++ trunk/reactos/lib/rtl/rtl.rbuild [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -46,16 +46,12 @@ <file>mem.c</file> <file>memgen.c</file> </if> - <directory name="austin"> - <file>avl.c</file> - <file>tree.c</file> - </directory> - <file>access.c</file> <file>acl.c</file> <file>actctx.c</file> <file>assert.c</file> <file>atom.c</file> + <file>avltable.c</file> <file>bitmap.c</file> <file>bootdata.c</file> <file>compress.c</file> Added: trunk/reactos/lib/rtl/rtlavl.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/rtlavl.h?rev=48173… ============================================================================== --- trunk/reactos/lib/rtl/rtlavl.h (added) +++ trunk/reactos/lib/rtl/rtlavl.h [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -1,0 +1,62 @@ +/* + * PROJECT: ReactOS Runtime Library + * LICENSE: BSD - See COPYING.ARM in the top level directory + * FILE: lib/rtl/rtlavl.h + * PURPOSE: RTL AVL Glue + * PROGRAMMERS: ReactOS Portable Systems Group + */ + +/* INCLUDES ******************************************************************/ + +/* + * This is the glue code for the AVL package in the RTL meant for external callers. + * It's not very exciting, it just uses the RTL-defined fields without any magic, + * unlike the Mm version which has special handling for balances and parents, and + * does not implement custom comparison callbacks. + */ +#define MI_ASSERT(x) +#define RtlLeftChildAvl(x) (PRTL_BALANCED_LINKS)(RtlLeftChild(x)) +#define RtlRightChildAvl(x) (PRTL_BALANCED_LINKS)(RtlRightChild(x)) +#define RtlParentAvl(x) (PRTL_BALANCED_LINKS)(RtlParent(x)) +#define RtlRealPredecessorAvl(x) (PRTL_BALANCED_LINKS)(RtlRealPredecessor((PRTL_SPLAY_LINKS)(x))) +#define RtlRealSuccessorAvl(x) (PRTL_BALANCED_LINKS)(RtlRealSuccessor((PRTL_SPLAY_LINKS)(x))) +#define RtlInsertAsRightChildAvl RtlInsertAsRightChild +#define RtlInsertAsLeftChildAvl RtlInsertAsLeftChild +#define RtlIsLeftChildAvl RtlIsLeftChild + +RTL_GENERIC_COMPARE_RESULTS +FORCEINLINE +RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN PVOID UserData) +{ + /* Do the compare */ + return Table->CompareRoutine(Table, + Buffer, + UserData); +} + +VOID +FORCEINLINE +RtlSetParent(IN PRTL_BALANCED_LINKS Node, + IN PRTL_BALANCED_LINKS Parent) +{ + Node->Parent = Parent; +} + +VOID +FORCEINLINE +RtlSetBalance(IN PRTL_BALANCED_LINKS Node, + IN CHAR Balance) +{ + Node->Balance = Balance; +} + +CHAR +FORCEINLINE +RtlBalance(IN PRTL_BALANCED_LINKS Node) +{ + return Node->Balance; +} + +/* EOF */ Propchange: trunk/reactos/lib/rtl/rtlavl.h ------------------------------------------------------------------------------ svn:eol-style = native Added: trunk/reactos/ntoskrnl/mm/ARM3/miavl.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miavl.h?r… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/miavl.h (added) +++ trunk/reactos/ntoskrnl/mm/ARM3/miavl.h [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -1,0 +1,136 @@ +/* + * PROJECT: ReactOS Kernel + * LICENSE: BSD - See COPYING.ARM in the top level directory + * FILE: ntoskrnl/mm/ARM3/miavl.h + * PURPOSE: ARM Memory Manager VAD Node Algorithms + * PROGRAMMERS: ReactOS Portable Systems Group + */ + +/* INCLUDES ******************************************************************/ + +/* + * This is the glue code for the Memory Manager version of AVL Trees that is used + * to store the MM_AVL_TABLE for Virtual Address Descriptors (VAD) in the VadRoot + * field in EPROCESS. + * + * In this version of the package, the balance and parent pointers are stored in + * the same field as a union (since we know the parent will be at least 8-byte + * aligned), saving some space, but requiring special logic to handle setting and + * querying the parent and balance. + * + * The other difference is that the AVL package for Rtl has custom callbacks for + * comparison purposes (which would access some internal, opaque, user data) while + * the Mm package stores the user-data inline as StartingVpn and EndingVpn. So + * when a compare is being made, RtlpAvlCompareRoutine is called, which will either + * perform the Mm work, or call the user-specified callback in the Rtl case. + */ +#define PRTL_AVL_TABLE PMM_AVL_TABLE +#define PRTL_BALANCED_LINKS PMMADDRESS_NODE +#define MI_ASSERT(x) ASSERT(x) + +RTL_GENERIC_COMPARE_RESULTS +FORCEINLINE +RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN PVOID UserData) +{ + PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(LIST_ENTRY) - sizeof(RTL_BALANCED_LINKS)); + ULONG_PTR StartingVpn = (ULONG_PTR)Buffer; + if (StartingVpn < CurrentNode->StartingVpn) + { + return GenericLessThan; + } + else if (StartingVpn <= CurrentNode->EndingVpn) + { + return GenericEqual; + } + else + { + return GenericGreaterThan; + } +} + +VOID +FORCEINLINE +RtlSetParent(IN PRTL_BALANCED_LINKS Node, + IN PRTL_BALANCED_LINKS Parent) +{ + Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3)); +} + +VOID +FORCEINLINE +RtlSetBalance(IN PRTL_BALANCED_LINKS Node, + IN SCHAR Balance) +{ + Node->u1.Balance = Balance; +} + +SCHAR +FORCEINLINE +RtlBalance(IN PRTL_BALANCED_LINKS Node) +{ + return Node->u1.Balance; +} + +PRTL_BALANCED_LINKS +FORCEINLINE +RtlParentAvl(IN PRTL_BALANCED_LINKS Node) +{ + return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3); +} + +BOOLEAN +FORCEINLINE +RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node) +{ + return (RtlParentAvl(Node) == Node); +} + +PRTL_BALANCED_LINKS +FORCEINLINE +RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node) +{ + return Node->RightChild; +} + +PRTL_BALANCED_LINKS +FORCEINLINE +RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node) +{ + return Node->LeftChild; +} + +BOOLEAN +FORCEINLINE +RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node) +{ + return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node); +} + +BOOLEAN +FORCEINLINE +RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node) +{ + return (RtlRightChildAvl(RtlParentAvl(Node)) == Node); +} + +VOID +FORCEINLINE +RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, + IN PRTL_BALANCED_LINKS Node) +{ + Parent->LeftChild = Node; + RtlSetParent(Node, Parent); +} + +VOID +FORCEINLINE +RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent, + IN PRTL_BALANCED_LINKS Node) +{ + Parent->RightChild = Node; + RtlSetParent(Node, Parent); +} + +/* EOF */ Propchange: trunk/reactos/ntoskrnl/mm/ARM3/miavl.h ------------------------------------------------------------------------------ svn:eol-style = native Added: trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c… ============================================================================== --- trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c (added) +++ trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -1,0 +1,268 @@ +/* + * PROJECT: ReactOS Kernel + * LICENSE: BSD - See COPYING.ARM in the top level directory + * FILE: ntoskrnl/mm/ARM3/vadnode.c + * PURPOSE: ARM Memory Manager VAD Node Algorithms + * PROGRAMMERS: ReactOS Portable Systems Group + */ + +/* INCLUDES *******************************************************************/ + +#include <ntoskrnl.h> +#define NDEBUG +#include <debug.h> + +#line 15 "ARMÂ³::VADNODE" +#define MODULE_INVOLVED_IN_ARM3 +#include "../ARM3/miarm.h" + +/* Include Mm version of AVL support */ +#include "../ARM3/miavl.h" +#include "../../../lib/rtl/avlsupp.c" + +/* FUNCTIONS ******************************************************************/ + +PMMVAD +NTAPI +MiLocateAddress(IN PVOID VirtualAddress) +{ + PMMVAD FoundVad; + ULONG_PTR Vpn; + PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot; + TABLE_SEARCH_RESULT SearchResult; + + /* Start with the the hint */ + FoundVad = (PMMVAD)Table->NodeHint; + if (!FoundVad) return NULL; + + /* Check if this VPN is in the hint, if so, use it */ + Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT; + if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad; + + /* VAD hint didn't work, go look for it */ + SearchResult = RtlpFindAvlTableNodeOrParent(Table, + (PVOID)Vpn, + (PMMADDRESS_NODE*)&FoundVad); + if (SearchResult != TableFoundNode) return NULL; + + /* We found it, update the hint */ + ASSERT(FoundVad != NULL); + ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)); + Table->NodeHint = FoundVad; + return FoundVad; +} + +PMMADDRESS_NODE +NTAPI +MiCheckForConflictingNode(IN ULONG_PTR StartVpn, + IN ULONG_PTR EndVpn, + IN PMM_AVL_TABLE Table) +{ + PMMADDRESS_NODE CurrentNode; + + /* If the tree is empty, there is no conflict */ + if (!Table->NumberGenericTableElements) return NULL; + + /* Start looping from the right */ + CurrentNode = RtlRightChildAvl(&Table->BalancedRoot); + ASSERT(CurrentNode != NULL); + while (CurrentNode) + { + /* This address comes after */ + if (StartVpn > CurrentNode->EndingVpn) + { + /* Keep searching on the right */ + CurrentNode = RtlRightChildAvl(CurrentNode); + } + else if (EndVpn < CurrentNode->StartingVpn) + { + /* This address ends before the node starts, search on the left */ + CurrentNode = RtlLeftChildAvl(CurrentNode); + } + else + { + /* This address is part of this node, return it */ + break; + } + } + + /* Return either the conflicting node, or no node at all */ + return CurrentNode; +} + +VOID +NTAPI +MiInsertNode(IN PMMADDRESS_NODE NewNode, + IN PMM_AVL_TABLE Table) +{ + PMMADDRESS_NODE NodeOrParent = NULL; + TABLE_SEARCH_RESULT Result; + + /* Find the node's parent, and where to insert this node */ + Result = RtlpFindAvlTableNodeOrParent(Table, + (PVOID)NewNode->StartingVpn, + &NodeOrParent); + + /* Insert it into the tree */ + RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result); +} + +PMMADDRESS_NODE +NTAPI +MiGetPreviousNode(IN PMMADDRESS_NODE Node) +{ + PMMADDRESS_NODE Parent; + + /* Get the left child */ + if (RtlLeftChildAvl(Node)) + { + /* Get right-most child */ + Node = RtlLeftChildAvl(Node); + while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node); + return Node; + } + + Parent = RtlParentAvl(Node); + ASSERT(Parent != NULL); + while (Parent != Node) + { + /* The parent should be a right child, return the real predecessor */ + if (RtlIsRightChildAvl(Node)) + { + /* Return it unless it's the root */ + if (Parent == RtlParentAvl(Parent)) Parent = NULL; + return Parent; + } + + /* Keep lopping until we find our parent */ + Node = Parent; + Parent = RtlParentAvl(Node); + } + + /* Nothing found */ + return NULL; +} + +NTSTATUS +NTAPI +MiFindEmptyAddressRangeDownTree(IN SIZE_T Length, + IN ULONG_PTR BoundaryAddress, + IN ULONG_PTR Alignment, + IN PMM_AVL_TABLE Table, + OUT PULONG_PTR Base) +{ + PMMADDRESS_NODE Node, PreviousNode; + ULONG_PTR CandidateAddress, EndAddress; + ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn; + PFN_NUMBER PageCount; + + /* Sanity checks */ + ASSERT(BoundaryAddress); + ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1)); + + /* Compute page length, make sure the boundary address is valid */ + Length = PAGE_ROUND_UP(Length); + if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY; + + /* Compute the highest address to start at */ + CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment); + + /* Check if the table is empty */ + if (!Table->NumberGenericTableElements) + { + /* Tree is empty, the candidate address is already the best one */ + *Base = CandidateAddress; + return STATUS_SUCCESS; + } + + /* Starting from the root, go down until the right-most child */ + Node = RtlRightChildAvl(&Table->BalancedRoot); + while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node); + + /* Get the aligned ending address of this VPN */ + EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1), + Alignment); + + /* Can we fit the address without overflowing into the node? */ + if ((EndAddress < BoundaryAddress) && + ((BoundaryAddress - EndAddress) > Length)) + { + /* There is enough space to add our address */ + *Base = ROUND_UP(BoundaryAddress - Length, Alignment); + return STATUS_SUCCESS; + } + + PageCount = Length >> PAGE_SHIFT; + CandidateVpn = CandidateAddress >> PAGE_SHIFT; + BoundaryVpn = BoundaryAddress >> PAGE_SHIFT; + LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT; + + PreviousNode = MiGetPreviousNode(Node); + + StartVpn = Node->StartingVpn; + EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0; + AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT); + + /* Loop until a gap is found */ + for (PageCount = Length >> PAGE_SHIFT, + CandidateVpn = CandidateAddress >> PAGE_SHIFT, + BoundaryVpn = BoundaryAddress >> PAGE_SHIFT, + LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT, + PreviousNode = MiGetPreviousNode(Node), + StartVpn = Node->StartingVpn, + EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0, + AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT); + PreviousNode; + Node = PreviousNode, + PreviousNode = MiGetPreviousNode(Node), + StartVpn = Node->StartingVpn, + EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0, + AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT)) + { + /* Can we fit the address without overflowing into the node? */ + if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount)) + { + /* Check if we can get our candidate address */ + if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn)) + { + /* Use it */ + *Base = CandidateAddress; + return STATUS_SUCCESS; + } + + /* Otherwise, can we fit it by changing the start address? */ + if (StartVpn > AlignEndVpn) + { + /* It'll fit, compute the new base address for that to work */ + *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment); + return STATUS_SUCCESS; + } + } + + PreviousNode = MiGetPreviousNode(Node); + StartVpn = Node->StartingVpn; + EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0; + AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT); + } + + /* See if we could squeeze into the last descriptor */ + if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount)) + { + /* Check if we can try our candidate address */ + if (BoundaryVpn < StartVpn) + { + /* Use it */ + *Base = CandidateAddress; + return STATUS_SUCCESS; + } + + /* Otherwise, change the base address to what's needed to fit in */ + *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment); + return STATUS_SUCCESS; + } + + /* No address space left at all */ + return STATUS_NO_MEMORY; +} + +/* EOF */ Propchange: trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c ------------------------------------------------------------------------------ svn:eol-style = native Modified: trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ntoskrnl-generic.… ============================================================================== --- trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild [iso-8859-1] Thu Jul 22 01:41:45 2010 @@ -408,6 +408,7 @@ <file>procsup.c</file> <file>sysldr.c</file> <file>syspte.c</file> + <file>vadnode.c</file> <file>virtual.c</file> </directory> <file>anonmem.c</file>

14 years, 5 months

[sir_richard] 48172: [NDK]: Add all the definitions regarding VADs.

by sir_richard＠svn.reactos.org

Author: sir_richard Date: Thu Jul 22 01:41:20 2010 New Revision: 48172 URL: http://svn.reactos.org/svn/reactos?rev=48172&view=rev Log: [NDK]: Add all the definitions regarding VADs. Modified: trunk/reactos/include/ndk/mmtypes.h Modified: trunk/reactos/include/ndk/mmtypes.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/include/ndk/mmtypes.h?rev=… ============================================================================== --- trunk/reactos/include/ndk/mmtypes.h [iso-8859-1] (original) +++ trunk/reactos/include/ndk/mmtypes.h [iso-8859-1] Thu Jul 22 01:41:20 2010 @@ -170,6 +170,21 @@ SectionBasicInformation, SectionImageInformation, } SECTION_INFORMATION_CLASS; + +// +// Kinds of VADs +// +typedef enum _MI_VAD_TYPE +{ + VadNone, + VadDevicePhysicalMemory, + VadImageMap, + VadAwe, + VadWriteWatch, + VadLargePages, + VadRotatePhysical, + VadLargePageSection +} MI_VAD_TYPE, *PMI_VAD_TYPE; #ifdef NTOS_MODE_USER @@ -613,6 +628,113 @@ PVOID NodeHint; PVOID NodeFreeHint; } MM_AVL_TABLE, *PMM_AVL_TABLE; + +// +// Virtual Adress List used in VADs +// +typedef struct _MMADDRESS_LIST +{ + ULONG StartVpn; + ULONG EndVpn; +} MMADDRESS_LIST, *PMMADDRESS_LIST; + +// +// Flags used in the VAD +// +typedef struct _MMVAD_FLAGS +{ + ULONG CommitCharge:19; + ULONG NoChange:1; + ULONG VadType:3; + ULONG MemCommit:1; + ULONG Protection:5; + ULONG Spare:2; + ULONG PrivateMemory:1; +} MMVAD_FLAGS, *PMMVAD_FLAGS; + +// +// Extended flags used in the VAD +// +typedef struct _MMVAD_FLAGS2 +{ + ULONG FileOffset:24; + ULONG SecNoChange:1; + ULONG OneSecured:1; + ULONG MultipleSecured:1; + ULONG ReadOnly:1; + ULONG LongVad:1; + ULONG ExtendableFile:1; + ULONG Inherit:1; + ULONG CopyOnWrite:1; +} MMVAD_FLAGS2, *PMMVAD_FLAGS2; + +// +// Virtual Address Descriptor (VAD) Structure +// +typedef struct _MMVAD +{ + union + { + LONG_PTR Balance:2; + struct _MMVAD *Parent; + } u1; + struct _MMVAD *LeftChild; + struct _MMVAD *RightChild; + ULONG StartingVpn; + ULONG EndingVpn; + union + { + ULONG LongFlags; + MMVAD_FLAGS VadFlags; + } u; + PCONTROL_AREA ControlArea; + PMMPTE FirstPrototypePte; + PMMPTE LastContiguousPte; + union + { + ULONG LongFlags2; + MMVAD_FLAGS2 VadFlags2; + } u2; +} MMVAD, *PMMVAD; + +// +// Long VAD used in section and private allocations +// +typedef struct _MMVAD_LONG +{ + union + { + LONG_PTR Balance:2; + PMMVAD Parent; + } u1; + PMMVAD LeftChild; + PMMVAD RightChild; + ULONG StartingVpn; + ULONG EndingVpn; + union + { + ULONG LongFlags; + MMVAD_FLAGS VadFlags; + } u; + PCONTROL_AREA ControlArea; + PMMPTE FirstPrototypePte; + PMMPTE LastContiguousPte; + union + { + ULONG LongFlags2; + MMVAD_FLAGS2 VadFlags2; + } u2; + union + { + LIST_ENTRY List; + MMADDRESS_LIST Secured; + } u3; + union + { + PVOID Banked; + PMMEXTEND_INFO ExtendedInfo; + } u4; +} MMVAD_LONG, *PMMVAD_LONG; // // Actual Section Object

14 years, 5 months

[sir_richard] 48171: [NDK]: Add missing RTL AVL Tree definitions, when used by user-mode applications.

by sir_richard＠svn.reactos.org

Author: sir_richard Date: Thu Jul 22 01:09:43 2010 New Revision: 48171 URL: http://svn.reactos.org/svn/reactos?rev=48171&view=rev Log: [NDK]: Add missing RTL AVL Tree definitions, when used by user-mode applications. Modified: trunk/reactos/include/ndk/rtlfuncs.h Modified: trunk/reactos/include/ndk/rtlfuncs.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/include/ndk/rtlfuncs.h?rev… ============================================================================== --- trunk/reactos/include/ndk/rtlfuncs.h [iso-8859-1] (original) +++ trunk/reactos/include/ndk/rtlfuncs.h [iso-8859-1] Thu Jul 22 01:09:43 2010 @@ -328,6 +328,129 @@ _SplayParent->RightChild = _SplayChild; \ _SplayChild->Parent = _SplayParent; \ } + +// +// RTL AVL Tree Functions +// +NTSYSAPI +VOID +NTAPI +RtlInitializeGenericTableAvl( + OUT PRTL_AVL_TABLE Table, + IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine, + IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine, + IN PRTL_AVL_FREE_ROUTINE FreeRoutine, + IN PVOID TableContext OPTIONAL +); + +NTSYSAPI +PVOID +NTAPI +RtlInsertElementGenericTableAvl( + IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN CLONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL +); + +NTSYSAPI +PVOID +NTAPI +RtlInsertElementGenericTableFullAvl( + IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN CLONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL, + IN PVOID NodeOrParent, + IN TABLE_SEARCH_RESULT SearchResult +); + +NTSYSAPI +BOOLEAN +NTAPI +RtlDeleteElementGenericTableAvl( + IN PRTL_AVL_TABLE Table, + IN PVOID Buffer +); + +NTSYSAPI +PVOID +NTAPI +RtlLookupElementGenericTableAvl( + IN PRTL_AVL_TABLE Table, + IN PVOID Buffer +); + +NTSYSAPI +PVOID +NTAPI +RtlLookupElementGenericTableFullAvl( + IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + OUT PVOID *NodeOrParent, + OUT TABLE_SEARCH_RESULT *SearchResult +); + +NTSYSAPI +PVOID +NTAPI +RtlEnumerateGenericTableAvl( + IN PRTL_AVL_TABLE Table, + IN BOOLEAN Restart +); + +NTSYSAPI +PVOID +NTAPI +RtlEnumerateGenericTableWithoutSplayingAvl( + IN PRTL_AVL_TABLE Table, + IN OUT PVOID *RestartKey +); + +NTSYSAPI +PVOID +NTAPI +RtlLookupFirstMatchingElementGenericTableAvl( + IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + OUT PVOID *RestartKey +); + +NTSYSAPI +PVOID +NTAPI +RtlEnumerateGenericTableLikeADirectory( + IN PRTL_AVL_TABLE Table, + IN PRTL_AVL_MATCH_FUNCTION MatchFunction OPTIONAL, + IN PVOID MatchData OPTIONAL, + IN ULONG NextFlag, + IN OUT PVOID *RestartKey, + IN OUT PULONG DeleteCount, + IN PVOID Buffer +); + +NTSYSAPI +PVOID +NTAPI +RtlGetElementGenericTableAvl( + IN PRTL_AVL_TABLE Table, + IN ULONG I +); + +NTSYSAPI +ULONG +NTAPI +RtlNumberGenericTableElementsAvl( + IN PRTL_AVL_TABLE Table +); + +NTSYSAPI +BOOLEAN +NTAPI +RtlIsGenericTableEmptyAvl( + IN PRTL_AVL_TABLE Table +); + #endif //

14 years, 5 months

[akhaldi] 48170: [PSDK] - Forgot to commit this.

by akhaldi＠svn.reactos.org

Author: akhaldi Date: Wed Jul 21 23:47:33 2010 New Revision: 48170 URL: http://svn.reactos.org/svn/reactos?rev=48170&view=rev Log: [PSDK] - Forgot to commit this. Modified: trunk/reactos/include/psdk/ntddndis.h Modified: trunk/reactos/include/psdk/ntddndis.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/include/psdk/ntddndis.h?re… ============================================================================== --- trunk/reactos/include/psdk/ntddndis.h [iso-8859-1] (original) +++ trunk/reactos/include/psdk/ntddndis.h [iso-8859-1] Wed Jul 21 23:47:33 2010 @@ -176,6 +176,8 @@ NdisPhysicalMediumOther, NdisPhysicalMediumMax } NDIS_PHYSICAL_MEDIUM, *PNDIS_PHYSICAL_MEDIUM; + +typedef ULONG NDIS_OID, *PNDIS_OID; /* Required Object IDs (OIDs) */ #define OID_GEN_SUPPORTED_LIST 0x00010101

14 years, 5 months

[akhaldi] 48169: [DDK/NDIS] - Group some related definitions. - Remove some duplicated NDIS_MINIPORT_MAJOR_VERSION/NDIS_MINIPORT_MINOR_VERSION combinations. - Add some missing NDIS_LEGACY_DRIVER guards. - _ANONYMOUS_UNION -> __MINGW_EXTENSION - Update NDIS_PROCESSOR_TYPE and NDIS_INTERFACE_TYPE. - Guard NDIS_GENERIC_OBJECT with NDIS_SUPPORT_NDIS6. - Add missing NDIS_WAN_GET_STATS, NdisAllocateGenericObject, NdisFreeGenericObject, fPACKET_WRAPPER_RESERVED and NDIS_FLAGS_* definitions. - PNDIS_PAC

by akhaldi＠svn.reactos.org

Author: akhaldi Date: Wed Jul 21 23:32:51 2010 New Revision: 48169 URL: http://svn.reactos.org/svn/reactos?rev=48169&view=rev Log: [DDK/NDIS] - Group some related definitions. - Remove some duplicated NDIS_MINIPORT_MAJOR_VERSION/NDIS_MINIPORT_MINOR_VERSION combinations. - Add some missing NDIS_LEGACY_DRIVER guards. - _ANONYMOUS_UNION -> __MINGW_EXTENSION - Update NDIS_PROCESSOR_TYPE and NDIS_INTERFACE_TYPE. - Guard NDIS_GENERIC_OBJECT with NDIS_SUPPORT_NDIS6. - Add missing NDIS_WAN_GET_STATS, NdisAllocateGenericObject, NdisFreeGenericObject, fPACKET_WRAPPER_RESERVED and NDIS_FLAGS_* definitions. - PNDIS_PACKET_POOL : HANDLE -> NDIS_HANDLE. - Improve MEDIA_SPECIFIC_INFORMATION - Some minor formatting. Modified: trunk/reactos/include/ddk/ndis.h Modified: trunk/reactos/include/ddk/ndis.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/include/ddk/ndis.h?rev=481… ============================================================================== --- trunk/reactos/include/ddk/ndis.h [iso-8859-1] (original) +++ trunk/reactos/include/ddk/ndis.h [iso-8859-1] Wed Jul 21 23:32:51 2010 @@ -251,38 +251,73 @@ #endif /* !defined(NDIS_LEGACY_PROTOCOL) */ +#if !defined(NDIS_LEGACY_DRIVER) + +#if (NDIS_LEGACY_MINIPORT || NDIS_LEGACY_PROTOCOL || NDIS_WRAPPER) +#define NDIS_LEGACY_DRIVER 1 +#else +#define NDIS_LEGACY_DRIVER 0 +#endif + +#endif /* !defined(NDIS_LEGACY_DRIVER) */ + +#if !defined(NDIS_SUPPORT_NDIS6) + +#if ((defined (NDIS_MINIPORT_MAJOR_VERSION) && (NDIS_MINIPORT_MAJOR_VERSION >= 6)) || \ + (defined (NDIS60)) || NDIS_WRAPPER) +#define NDIS_SUPPORT_NDIS6 1 +#else +#define NDIS_SUPPORT_NDIS6 0 +#endif + +#endif /* !defined(NDIS_SUPPORT_NDIS6) */ + +#if !defined(NDIS_SUPPORT_NDIS61) +#if (((defined (NDIS_MINIPORT_MAJOR_VERSION) && (NDIS_MINIPORT_MAJOR_VERSION >= 6)) && \ + (defined (NDIS_MINIPORT_MINOR_VERSION) && (NDIS_MINIPORT_MINOR_VERSION >= 1))) || \ + (defined (NDIS61)) || NDIS_WRAPPER) +#define NDIS_SUPPORT_NDIS61 1 +#else +#define NDIS_SUPPORT_NDIS61 0 +#endif +#endif // !defined(NDIS_SUPPORT_NDIS61) + +#if !defined(NDIS_SUPPORT_NDIS620) + +#if (((defined (NDIS_MINIPORT_MAJOR_VERSION) && (NDIS_MINIPORT_MAJOR_VERSION >= 6)) && \ + (defined (NDIS_MINIPORT_MINOR_VERSION) && (NDIS_MINIPORT_MINOR_VERSION >= 20))) || \ + (defined (NDIS620)) || NDIS_WRAPPER) +#define NDIS_SUPPORT_NDIS620 1 +#else +#define NDIS_SUPPORT_NDIS620 0 +#endif + +#endif /* !defined(NDIS_SUPPORT_NDIS620) */ + +#if (NDIS_SUPPORT_NDIS620) +#undef NDIS_SUPPORT_NDIS61 +#define NDIS_SUPPORT_NDIS61 1 +#endif + +#if (NDIS_SUPPORT_NDIS61) +#undef NDIS_SUPPORT_NDIS6 +#define NDIS_SUPPORT_NDIS6 1 +#endif + +#if defined(NDIS61_MINIPORT) || defined(NDIS60_MINIPORT) || defined(NDIS61) || \ + defined(NDIS60) || defined(NDIS_WRAPPER) || defined(NDIS_LEGACY_DRIVER) +#define NDIS_SUPPORT_60_COMPATIBLE_API 1 +#else +#define NDIS_SUPPORT_60_COMPATIBLE_API 0 +#endif + #if defined(NDIS_WRAPPER) #define NDISAPI #else #define NDISAPI DECLSPEC_IMPORT #endif -#if defined(NDIS50_MINIPORT) && !defined(NDIS_MINIPORT_MAJOR_VERSION) && !defined(NDIS_MINIPORT_MINOR_VERSION) -#define NDIS_MINIPORT_MAJOR_VERSION 5 -#define NDIS_MINIPORT_MINOR_VERSION 0 -#endif - -#if defined(NDIS51_MINIPORT) && !defined(NDIS_MINIPORT_MAJOR_VERSION) && !defined(NDIS_MINIPORT_MINOR_VERSION) -#define NDIS_MINIPORT_MAJOR_VERSION 5 -#define NDIS_MINIPORT_MINOR_VERSION 1 -#endif - -#if defined(NDIS50) && !defined(NDIS_PROTOCOL_MAJOR_VERSION) && !defined(NDIS_PROTOCOL_MINOR_VERSION) -#define NDIS_PROTOCOL_MAJOR_VERSION 5 -#define NDIS_PROTOCOL_MINOR_VERSION 0 -#endif - -#if defined(NDIS51) && !defined(NDIS_PROTOCOL_MAJOR_VERSION) && !defined(NDIS_PROTOCOL_MINOR_VERSION) -#define NDIS_PROTOCOL_MAJOR_VERSION 5 -#define NDIS_PROTOCOL_MINOR_VERSION 1 -#endif - -#if 1 -/* FIXME: */ -typedef PVOID QUEUED_CLOSE; -#endif - -typedef ULONG NDIS_OID, *PNDIS_OID; +typedef PVOID QUEUED_CLOSE; //FIXME : Doesn't exist in public headers typedef struct _X_FILTER FDDI_FILTER, *PFDDI_FILTER; typedef struct _X_FILTER TR_FILTER, *PTR_FILTER; @@ -298,12 +333,12 @@ /* NDIS base types */ typedef struct _NDIS_SPIN_LOCK { - KSPIN_LOCK SpinLock; - KIRQL OldIrql; -} NDIS_SPIN_LOCK, * PNDIS_SPIN_LOCK; + KSPIN_LOCK SpinLock; + KIRQL OldIrql; +} NDIS_SPIN_LOCK, *PNDIS_SPIN_LOCK; typedef struct _NDIS_EVENT { - KEVENT Event; + KEVENT Event; } NDIS_EVENT, *PNDIS_EVENT; typedef PVOID NDIS_HANDLE, *PNDIS_HANDLE; @@ -561,24 +596,44 @@ #define NDIS_GUID_UNICODE_STRING 0x00000008 #define NDIS_GUID_ARRAY 0x00000010 -typedef HANDLE PNDIS_PACKET_POOL; +#if NDIS_LEGACY_DRIVER /* NDIS_PACKET_PRIVATE.Flags constants */ -#define fPACKET_CONTAINS_MEDIA_SPECIFIC_INFO 0x40 -#define fPACKET_ALLOCATED_BY_NDIS 0x80 +#define fPACKET_WRAPPER_RESERVED 0x3f +#define fPACKET_CONTAINS_MEDIA_SPECIFIC_INFO 0x40 +#define fPACKET_ALLOCATED_BY_NDIS 0x80 + +#define NDIS_FLAGS_PROTOCOL_ID_MASK 0x0000000f +#define NDIS_FLAGS_MULTICAST_PACKET 0x00000010 +#define NDIS_FLAGS_RESERVED2 0x00000020 +#define NDIS_FLAGS_RESERVED3 0x00000040 +#define NDIS_FLAGS_DONT_LOOPBACK 0x00000080 +#define NDIS_FLAGS_IS_LOOPBACK_PACKET 0x00000100 +#define NDIS_FLAGS_LOOPBACK_ONLY 0x00000200 +#define NDIS_FLAGS_RESERVED4 0x00000400 +#define NDIS_FLAGS_DOUBLE_BUFFERED 0x00000800 +#define NDIS_FLAGS_SENT_AT_DPC 0x00001000 +#define NDIS_FLAGS_USES_SG_BUFFER_LIST 0x00002000 +#define NDIS_FLAGS_USES_ORIGINAL_PACKET 0x00004000 +#define NDIS_FLAGS_PADDED 0x00010000 +#define NDIS_FLAGS_XLATE_AT_TOP 0x00020000 + +typedef NDIS_HANDLE PNDIS_PACKET_POOL; typedef struct _NDIS_PACKET_PRIVATE { - UINT PhysicalCount; - UINT TotalLength; - PNDIS_BUFFER Head; - PNDIS_BUFFER Tail; - PNDIS_PACKET_POOL Pool; - UINT Count; - ULONG Flags; - BOOLEAN ValidCounts; - UCHAR NdisPacketFlags; - USHORT NdisPacketOobOffset; -} NDIS_PACKET_PRIVATE, * PNDIS_PACKET_PRIVATE; + UINT PhysicalCount; + UINT TotalLength; + PNDIS_BUFFER Head; + PNDIS_BUFFER Tail; + PNDIS_PACKET_POOL Pool; + UINT Count; + ULONG Flags; + BOOLEAN ValidCounts; + UCHAR NdisPacketFlags; + USHORT NdisPacketOobOffset; +} NDIS_PACKET_PRIVATE, *PNDIS_PACKET_PRIVATE; + +#endif /* NDIS_LEGACY_DRIVER */ typedef struct _NDIS_PACKET { NDIS_PACKET_PRIVATE Private; @@ -600,30 +655,32 @@ } NDIS_PACKET, *PNDIS_PACKET, **PPNDIS_PACKET; typedef enum _NDIS_CLASS_ID { - NdisClass802_3Priority, - NdisClassWirelessWanMbxMailbox, - NdisClassIrdaPacketInfo, - NdisClassAtmAALInfo + NdisClass802_3Priority, + NdisClassWirelessWanMbxMailbox, + NdisClassIrdaPacketInfo, + NdisClassAtmAALInfo } NDIS_CLASS_ID; -typedef struct MediaSpecificInformation { - UINT NextEntryOffset; - NDIS_CLASS_ID ClassId; - UINT Size; - UCHAR ClassInformation[1]; -} MEDIA_SPECIFIC_INFORMATION; - +typedef struct _MEDIA_SPECIFIC_INFORMATION { + UINT NextEntryOffset; + NDIS_CLASS_ID ClassId; + UINT Size; + UCHAR ClassInformation[1]; +} MEDIA_SPECIFIC_INFORMATION, *PMEDIA_SPECIFIC_INFORMATION; + +#if NDIS_LEGACY_DRIVER typedef struct _NDIS_PACKET_OOB_DATA { - _ANONYMOUS_UNION union { - ULONGLONG TimeToSend; - ULONGLONG TimeSent; - } DUMMYUNIONNAME; - ULONGLONG TimeReceived; - UINT HeaderSize; - UINT SizeMediaSpecificInfo; - PVOID MediaSpecificInformation; - NDIS_STATUS Status; + __MINGW_EXTENSION union { + ULONGLONG TimeToSend; + ULONGLONG TimeSent; + }; + ULONGLONG TimeReceived; + UINT HeaderSize; + UINT SizeMediaSpecificInfo; + PVOID MediaSpecificInformation; + NDIS_STATUS Status; } NDIS_PACKET_OOB_DATA, *PNDIS_PACKET_OOB_DATA; +#endif typedef struct _NDIS_PM_PACKET_PATTERN { ULONG Priority; @@ -733,41 +790,45 @@ #define NDIS_DMA_64BITS ((NDIS_DMA_SIZE)2) typedef enum _NDIS_PROCESSOR_TYPE { - NdisProcessorX86, - NdisProcessorMips, - NdisProcessorAlpha, - NdisProcessorPpc, - NdisProcessorAmd64 + NdisProcessorX86, + NdisProcessorMips, + NdisProcessorAlpha, + NdisProcessorPpc, + NdisProcessorAmd64, + NdisProcessorIA64 } NDIS_PROCESSOR_TYPE, *PNDIS_PROCESSOR_TYPE; typedef enum _NDIS_ENVIRONMENT_TYPE { - NdisEnvironmentWindows, - NdisEnvironmentWindowsNt + NdisEnvironmentWindows, + NdisEnvironmentWindowsNt } NDIS_ENVIRONMENT_TYPE, *PNDIS_ENVIRONMENT_TYPE; /* Possible hardware architecture */ typedef enum _NDIS_INTERFACE_TYPE { - NdisInterfaceInternal = Internal, - NdisInterfaceIsa = Isa, - NdisInterfaceEisa = Eisa, - NdisInterfaceMca = MicroChannel, - NdisInterfaceTurboChannel = TurboChannel, - NdisInterfacePci = PCIBus, - NdisInterfacePcMcia = PCMCIABus, - NdisInterfaceCBus = CBus, - NdisInterfaceMPIBus = MPIBus, - NdisInterfaceMPSABus = MPSABus, - NdisInterfaceProcessorInternal = ProcessorInternal, - NdisInterfaceInternalPowerBus = InternalPowerBus, - NdisInterfacePNPISABus = PNPISABus, - NdisInterfacePNPBus = PNPBus, - NdisMaximumInterfaceType + NdisInterfaceInternal = Internal, + NdisInterfaceIsa = Isa, + NdisInterfaceEisa = Eisa, + NdisInterfaceMca = MicroChannel, + NdisInterfaceTurboChannel = TurboChannel, + NdisInterfacePci = PCIBus, + NdisInterfacePcMcia = PCMCIABus, + NdisInterfaceCBus = CBus, + NdisInterfaceMPIBus = MPIBus, + NdisInterfaceMPSABus = MPSABus, + NdisInterfaceProcessorInternal = ProcessorInternal, + NdisInterfaceInternalPowerBus = InternalPowerBus, + NdisInterfacePNPISABus = PNPISABus, + NdisInterfacePNPBus = PNPBus, + NdisInterfaceUSB, + NdisInterfaceIrda, + NdisInterface1394, + NdisMaximumInterfaceType } NDIS_INTERFACE_TYPE, *PNDIS_INTERFACE_TYPE; #define NdisInterruptLevelSensitive LevelSensitive #define NdisInterruptLatched Latched + typedef KINTERRUPT_MODE NDIS_INTERRUPT_MODE, *PNDIS_INTERRUPT_MODE; - typedef enum _NDIS_PARAMETER_TYPE { NdisParameterInteger, @@ -777,20 +838,19 @@ NdisParameterBinary } NDIS_PARAMETER_TYPE, *PNDIS_PARAMETER_TYPE; -typedef struct { - USHORT Length; - PVOID Buffer; +typedef struct _BINARY_DATA { + USHORT Length; + PVOID Buffer; } BINARY_DATA; typedef struct _NDIS_CONFIGURATION_PARAMETER { - NDIS_PARAMETER_TYPE ParameterType; + NDIS_PARAMETER_TYPE ParameterType; union { - ULONG IntegerData; - NDIS_STRING StringData; - BINARY_DATA BinaryData; + ULONG IntegerData; + NDIS_STRING StringData; + BINARY_DATA BinaryData; } ParameterData; } NDIS_CONFIGURATION_PARAMETER, *PNDIS_CONFIGURATION_PARAMETER; - typedef PHYSICAL_ADDRESS NDIS_PHYSICAL_ADDRESS, *PNDIS_PHYSICAL_ADDRESS; @@ -800,23 +860,22 @@ } NDIS_PHYSICAL_ADDRESS_UNIT, *PNDIS_PHYSICAL_ADDRESS_UNIT; typedef struct _NDIS_WAN_LINE_DOWN { - UCHAR RemoteAddress[6]; - UCHAR LocalAddress[6]; + UCHAR RemoteAddress[6]; + UCHAR LocalAddress[6]; } NDIS_WAN_LINE_DOWN, *PNDIS_WAN_LINE_DOWN; typedef struct _NDIS_WAN_LINE_UP { - ULONG LinkSpeed; - ULONG MaximumTotalSize; - NDIS_WAN_QUALITY Quality; - USHORT SendWindow; - UCHAR RemoteAddress[6]; - OUT UCHAR LocalAddress[6]; - ULONG ProtocolBufferLength; - PUCHAR ProtocolBuffer; - USHORT ProtocolType; - NDIS_STRING DeviceName; + ULONG LinkSpeed; + ULONG MaximumTotalSize; + NDIS_WAN_QUALITY Quality; + USHORT SendWindow; + UCHAR RemoteAddress[6]; + OUT UCHAR LocalAddress[6]; + ULONG ProtocolBufferLength; + PUCHAR ProtocolBuffer; + USHORT ProtocolType; + NDIS_STRING DeviceName; } NDIS_WAN_LINE_UP, *PNDIS_WAN_LINE_UP; - typedef VOID (NTAPI *ADAPTER_SHUTDOWN_HANDLER)( @@ -1032,12 +1091,14 @@ PVOID NdisPacketInfo[MaxPerPacketInfo]; } NDIS_PACKET_EXTENSION, *PNDIS_PACKET_EXTENSION; +#if NDIS_SUPPORT_NDIS6 typedef struct _NDIS_GENERIC_OBJECT { - NDIS_OBJECT_HEADER Header; - PVOID Caller; - PVOID CallersCaller; - PDRIVER_OBJECT DriverObject; + NDIS_OBJECT_HEADER Header; + PVOID Caller; + PVOID CallersCaller; + PDRIVER_OBJECT DriverObject; } NDIS_GENERIC_OBJECT, *PNDIS_GENERIC_OBJECT; +#endif /* * PNDIS_PACKET @@ -1230,20 +1291,37 @@ } NDIS_TCP_IP_CHECKSUM_PACKET_INFO, *PNDIS_TCP_IP_CHECKSUM_PACKET_INFO; typedef struct _NDIS_WAN_CO_FRAGMENT { - ULONG Errors; + ULONG Errors; } NDIS_WAN_CO_FRAGMENT, *PNDIS_WAN_CO_FRAGMENT; typedef struct _NDIS_WAN_FRAGMENT { - UCHAR RemoteAddress[6]; - UCHAR LocalAddress[6]; + UCHAR RemoteAddress[6]; + UCHAR LocalAddress[6]; } NDIS_WAN_FRAGMENT, *PNDIS_WAN_FRAGMENT; typedef struct _WAN_CO_LINKPARAMS { - ULONG TransmitSpeed; - ULONG ReceiveSpeed; - ULONG SendWindow; + ULONG TransmitSpeed; + ULONG ReceiveSpeed; + ULONG SendWindow; } WAN_CO_LINKPARAMS, *PWAN_CO_LINKPARAMS; +typedef struct _NDIS_WAN_GET_STATS { + UCHAR LocalAddress[6]; + ULONG BytesSent; + ULONG BytesRcvd; + ULONG FramesSent; + ULONG FramesRcvd; + ULONG CRCErrors; + ULONG TimeoutErrors; + ULONG AlignmentErrors; + ULONG SerialOverrunErrors; + ULONG FramingErrors; + ULONG BufferOverrunErrors; + ULONG BytesTransmittedUncompressed; + ULONG BytesReceivedUncompressed; + ULONG BytesTransmittedCompressed; + ULONG BytesReceivedCompressed; +} NDIS_WAN_GET_STATS, *PNDIS_WAN_GET_STATS; /* Call Manager */ @@ -2116,10 +2194,9 @@ * NDIS_GET_PACKET_HEADER_SIZE( * IN PNDIS_PACKET Packet); */ -#define NDIS_GET_PACKET_HEADER_SIZE(_Packet) \ - ((PNDIS_PACKET_OOB_DATA)((PUCHAR)(_Packet) + \ - (_Packet)->Private.NdisPacketOobOffset))->HeaderSize - +#define NDIS_GET_PACKET_HEADER_SIZE(_Packet) \ + ((PNDIS_PACKET_OOB_DATA)((PUCHAR)(_Packet) + \ + (_Packet)->Private.NdisPacketOobOffset))->HeaderSize /* * NDIS_STATUS @@ -4238,11 +4315,11 @@ struct _NDIS_WORK_ITEM; typedef VOID (*NDIS_PROC)(struct _NDIS_WORK_ITEM *, PVOID); -typedef struct _NDIS_WORK_ITEM -{ - PVOID Context; - NDIS_PROC Routine; - UCHAR WrapperReserved[8*sizeof(PVOID)]; + +typedef struct _NDIS_WORK_ITEM { + PVOID Context; + NDIS_PROC Routine; + UCHAR WrapperReserved[8*sizeof(PVOID)]; } NDIS_WORK_ITEM, *PNDIS_WORK_ITEM; typedef struct _NDIS_BIND_PATHS { @@ -4700,9 +4777,25 @@ #endif }; - - /* Routines for NDIS miniport drivers */ + +#if NDIS_SUPPORT_NDIS6 + +NDISAPI +PNDIS_GENERIC_OBJECT +NTAPI +NdisAllocateGenericObject( + PDRIVER_OBJECT DriverObject OPTIONAL, + ULONG Tag, + USHORT Size); + +NDISAPI +VOID +NTAPI +NdisFreeGenericObject( + IN PNDIS_GENERIC_OBJECT NdisObject); + +#endif /* NDIS_SUPPORT_NDIS6 */ NDISAPI VOID

14 years, 5 months

[tkreuzer] 48168: [RBUILD] Generate an RSP rule for the bootloader, this fixes "input line too long" error reported by tower.

by tkreuzer＠svn.reactos.org

Author: tkreuzer Date: Wed Jul 21 23:17:12 2010 New Revision: 48168 URL: http://svn.reactos.org/svn/reactos?rev=48168&view=rev Log: [RBUILD] Generate an RSP rule for the bootloader, this fixes "input line too long" error reported by tower. Modified: trunk/reactos/tools/rbuild/backend/mingw/modulehandler.cpp Modified: trunk/reactos/tools/rbuild/backend/mingw/modulehandler.cpp URL: http://svn.reactos.org/svn/reactos/trunk/reactos/tools/rbuild/backend/mingw… ============================================================================== --- trunk/reactos/tools/rbuild/backend/mingw/modulehandler.cpp [iso-8859-1] (original) +++ trunk/reactos/tools/rbuild/backend/mingw/modulehandler.cpp [iso-8859-1] Wed Jul 21 23:17:12 2010 @@ -2444,11 +2444,26 @@ string libsMacro = GetLibsMacro (); GenerateRules (); + + string objectsDir = "${call RBUILD_intermediate_dir,$(" + module.name + "_TARGET)}"; + string rspFile = objectsDir + "$(SEP)" + module.name + "_objs.rsp"; + + /* Generate the rsp rule */ + fprintf(fMakefile, "%s: $(%s_OBJS) %s | %s\n" + "\t$(ECHO_RSP)\n" + "\t-@${rm} $@ 2>$(NUL)\n" + "\t${cp} $(NUL) $@ >$(NUL)\n" + "\t$(foreach obj,$(%s_LIBS),$(Q)echo $(QUOTE)$(subst \\,\\\\,$(obj))$(QUOTE)>>$@$(NL))\n\n", + rspFile.c_str(), + module.name.c_str(), + module.xmlbuildFile.c_str(), + objectsDir.c_str(), + module.name.c_str()); const FileLocation *target_file = GetTargetFilename ( module, NULL ); fprintf ( fMakefile, "%s: %s %s | %s\n", targetMacro.c_str (), - objectsMacro.c_str (), + rspFile.c_str(), libsMacro.c_str (), backend->GetFullPath ( *target_file ).c_str () ); @@ -2461,24 +2476,22 @@ /* Link the stripped booloader */ fprintf(fMakefile, - "\t${ld} --strip-all --subsystem native --entry=%s --image-base=%s %s %s $(PROJECT_CCLIBS) " + "\t${ld} --strip-all --subsystem native --entry=%s --image-base=%s @%s $(PROJECT_CCLIBS) " "$(BUILTIN_LDFLAGS) $(PROJECT_LDFLAGS) $(LDFLAG_DRIVER) %s -o $@\n", module.GetEntryPoint().c_str(), module.baseaddress.c_str(), - objectsMacro.c_str(), - libsMacro.c_str(), + rspFile.c_str(), linkerScriptArgument.c_str() ); /* Link an unstripped version */ fprintf(fMakefile, "ifeq ($(ROS_BUILDNOSTRIP),yes)\n" - "\t${ld} --subsystem native --entry=%s --image-base=%s %s %s $(PROJECT_CCLIBS) " + "\t${ld} --subsystem native --entry=%s --image-base=%s @%s $(PROJECT_CCLIBS) " "$(BUILTIN_LDFLAGS) $(PROJECT_LDFLAGS) $(LDFLAG_DRIVER) %s -o %s$(SEP)%s.nostrip.sys\n" "endif\n", module.GetEntryPoint().c_str(), module.baseaddress.c_str(), - objectsMacro.c_str(), - libsMacro.c_str(), + rspFile.c_str(), linkerScriptArgument.c_str(), backend->GetFullPath(*target_file).c_str(), module.name.c_str());

14 years, 5 months

[jgardou] 48167: update README.WINE

by jgardou＠svn.reactos.org

Author: jgardou Date: Wed Jul 21 21:28:31 2010 New Revision: 48167 URL: http://svn.reactos.org/svn/reactos?rev=48167&view=rev Log: update README.WINE Modified: trunk/reactos/media/doc/README.WINE Modified: trunk/reactos/media/doc/README.WINE URL: http://svn.reactos.org/svn/reactos/trunk/reactos/media/doc/README.WINE?rev=… ============================================================================== --- trunk/reactos/media/doc/README.WINE [iso-8859-1] (original) +++ trunk/reactos/media/doc/README.WINE [iso-8859-1] Wed Jul 21 21:28:31 2010 @@ -252,6 +252,7 @@ reactos/dll/win32/user32/misc/winhelp.c # Last sync date unknown reactos/dll/win32/user32/misc/wsprintf.c # Synced to Wine-1_1_23 + reactos/dll/win32/user32/windows/cursoricon # Forked from wine 1.2-rc7 reactos/dll/win32/user32/windows/defwnd.c # Forked reactos/dll/win32/user32/windows/draw.c # Forked at Wine-20020904 (uitools.c) reactos/dll/win32/user32/windows/mdi.c # Synced to Wine-1_1_40

14 years, 5 months

← Newer
1
...
19
20
21
22
23
24
25
...
47
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Ros-diffs July 2010