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 RTL_GENERIC_COMPARE_RESULTS
  32 FORCEINLINE
  33 RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
  34                       IN PVOID Buffer,
  35                       IN PVOID UserData)
  36 {
  37     PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(LIST_ENTRY) - sizeof(RTL_BALANCED_LINKS));
  38     ULONG_PTR StartingVpn = (ULONG_PTR)Buffer;
  39     if (StartingVpn < CurrentNode->StartingVpn)
  40     {
  41         return GenericLessThan;
  42     }
  43     else if (StartingVpn <= CurrentNode->EndingVpn)
  44     {
  45         return GenericEqual;
  46     }
  47     else
  48     {
  49         return GenericGreaterThan;
  50     }
  51 }
  52
  53 VOID
  54 FORCEINLINE
  55 RtlSetParent(IN PRTL_BALANCED_LINKS Node,
  56              IN PRTL_BALANCED_LINKS Parent)
  57 {
  58     Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
  59 }
  60
  61 VOID
  62 FORCEINLINE
  63 RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
  64               IN SCHAR Balance)
  65 {
  66     Node->u1.Balance = Balance;
  67 }
  68
  69 SCHAR
  70 FORCEINLINE
  71 RtlBalance(IN PRTL_BALANCED_LINKS Node)
  72 {
  73     return Node->u1.Balance;
  74 }
  75
  76 PRTL_BALANCED_LINKS
  77 FORCEINLINE
  78 RtlParentAvl(IN PRTL_BALANCED_LINKS Node)
  79 {
  80     return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
  81 }
  82
  83 BOOLEAN
  84 FORCEINLINE
  85 RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node)
  86 {
  87    return (RtlParentAvl(Node) == Node);
  88 }
  89
  90 PRTL_BALANCED_LINKS
  91 FORCEINLINE
  92 RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node)
  93 {
  94     return Node->RightChild;
  95 }
  96
  97 PRTL_BALANCED_LINKS
  98 FORCEINLINE
  99 RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
 100 {
 101     return Node->LeftChild;
 102 }
 103
 104 BOOLEAN
 105 FORCEINLINE
 106 RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
 107 {
 108    return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
 109 }
 110
 111 BOOLEAN
 112 FORCEINLINE
 113 RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
 114 {
 115    return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
 116 }
 117
 118 VOID
 119 FORCEINLINE
 120 RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent,
 121                         IN PRTL_BALANCED_LINKS Node)
 122 {
 123     Parent->LeftChild = Node;
 124     RtlSetParent(Node, Parent);
 125 }
 126
 127 VOID
 128 FORCEINLINE
 129 RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent,
 130                          IN PRTL_BALANCED_LINKS Node)
 131 {
 132     Parent->RightChild = Node;
 133     RtlSetParent(Node, Parent);
 134 }
 135
 136 /* EOF */