reactos/ntoskrnl/mm/ARM3/miavl.h

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         BSD - See COPYING.ARM in the top level directory
   4  * FILE:            ntoskrnl/mm/ARM3/miavl.h
   5  * PURPOSE:         ARM Memory Manager VAD Node Algorithms
   6  * PROGRAMMERS:     ReactOS Portable Systems Group
   7  */
   8
   9 /* INCLUDES ******************************************************************/
  10
  11 /*
  12  * This is the glue code for the Memory Manager version of AVL Trees that is used
  13  * to store the MM_AVL_TABLE for Virtual Address Descriptors (VAD) in the VadRoot
  14  * field in EPROCESS.
  15  *
  16  * In this version of the package, the balance and parent pointers are stored in
  17  * the same field as a union (since we know the parent will be at least 8-byte
  18  * aligned), saving some space, but requiring special logic to handle setting and
  19  * querying the parent and balance.
  20  *
  21  * The other difference is that the AVL package for Rtl has custom callbacks for
  22  * comparison purposes (which would access some internal, opaque, user data) while
  23  * the Mm package stores the user-data inline as StartingVpn and EndingVpn. So
  24  * when a compare is being made, RtlpAvlCompareRoutine is called, which will either
  25  * perform the Mm work, or call the user-specified callback in the Rtl case.
  26  */
  27 #define PRTL_AVL_TABLE              PMM_AVL_TABLE
  28 #define PRTL_BALANCED_LINKS         PMMADDRESS_NODE
  29 #define MI_ASSERT(x)                ASSERT(x)
  30
  31 VOID
  32 FORCEINLINE
  33 RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1,
  34                     IN PRTL_BALANCED_LINKS Node2)
  35 {
  36     Node1->u1.Parent = Node2->u1.Parent;
  37     Node1->LeftChild = Node2->LeftChild;
  38     Node1->RightChild = Node2->RightChild;
  39 }
  40
  41 RTL_GENERIC_COMPARE_RESULTS
  42 FORCEINLINE
  43 RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
  44                       IN PVOID Buffer,
  45                       IN PVOID UserData)
  46 {
  47     PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(LIST_ENTRY) - sizeof(RTL_BALANCED_LINKS));
  48     ULONG_PTR StartingVpn = (ULONG_PTR)Buffer;
  49     if (StartingVpn < CurrentNode->StartingVpn)
  50     {
  51         return GenericLessThan;
  52     }
  53     else if (StartingVpn <= CurrentNode->EndingVpn)
  54     {
  55         return GenericEqual;
  56     }
  57     else
  58     {
  59         return GenericGreaterThan;
  60     }
  61 }
  62
  63 VOID
  64 FORCEINLINE
  65 RtlSetParent(IN PRTL_BALANCED_LINKS Node,
  66              IN PRTL_BALANCED_LINKS Parent)
  67 {
  68     Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
  69 }
  70
  71 VOID
  72 FORCEINLINE
  73 RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
  74               IN SCHAR Balance)
  75 {
  76     Node->u1.Balance = Balance;
  77 }
  78
  79 SCHAR
  80 FORCEINLINE
  81 RtlBalance(IN PRTL_BALANCED_LINKS Node)
  82 {
  83     return Node->u1.Balance;
  84 }
  85
  86 PRTL_BALANCED_LINKS
  87 FORCEINLINE
  88 RtlParentAvl(IN PRTL_BALANCED_LINKS Node)
  89 {
  90     return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
  91 }
  92
  93 BOOLEAN
  94 FORCEINLINE
  95 RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node)
  96 {
  97    return (RtlParentAvl(Node) == Node);
  98 }
  99
 100 PRTL_BALANCED_LINKS
 101 FORCEINLINE
 102 RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node)
 103 {
 104     return Node->RightChild;
 105 }
 106
 107 PRTL_BALANCED_LINKS
 108 FORCEINLINE
 109 RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
 110 {
 111     return Node->LeftChild;
 112 }
 113
 114 BOOLEAN
 115 FORCEINLINE
 116 RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
 117 {
 118    return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
 119 }
 120
 121 BOOLEAN
 122 FORCEINLINE
 123 RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
 124 {
 125    return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
 126 }
 127
 128 VOID
 129 FORCEINLINE
 130 RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent,
 131                         IN PRTL_BALANCED_LINKS Node)
 132 {
 133     Parent->LeftChild = Node;
 134     RtlSetParent(Node, Parent);
 135 }
 136
 137 VOID
 138 FORCEINLINE
 139 RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent,
 140                          IN PRTL_BALANCED_LINKS Node)
 141 {
 142     Parent->RightChild = Node;
 143     RtlSetParent(Node, Parent);
 144 }
 145
 146 /* EOF */