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 #pragma once
  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 /* We need to rename the functions to prevent conflicts when not inlined! */
  32 #define RtlpFindAvlTableNodeOrParent MiFindAvlTableNodeOrParent
  33 #define RtlpPromoteAvlTreeNode MiPromoteAvlTreeNode
  34 #define RtlpRebalanceAvlTreeNode MiRebalanceAvlTreeNode
  35 #define RtlpInsertAvlTreeNode MiInsertAvlTreeNode
  36 #define RtlpDeleteAvlTreeNode MiDeleteAvlTreeNode
  37
  38 /* These are implementation specific */
  39 #define RtlpCopyAvlNodeData MiCopyAvlNodeData
  40 #define RtlpAvlCompareRoutine MiAvlCompareRoutine
  41 #define RtlSetParent MiSetParent
  42 #define RtlSetBalance MiSetBalance
  43 #define RtlBalance MiBalance
  44 #define RtlParentAvl MiParentAvl
  45 #define RtlRightChildAvl MiRightChildAvl
  46 #define RtlLeftChildAvl MiLeftChildAvl
  47 #define RtlIsLeftChildAvl MiIsLeftChildAvl
  48 #define RtlIsRightChildAvl MiIsRightChildAvl
  49 #define RtlInsertAsLeftChildAvl MiInsertAsLeftChildAvl
  50 #define RtlInsertAsRightChildAvl MiInsertAsRightChildAvl
  51
  52 FORCEINLINE
  53 VOID
  54 MiCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1,
  55                     IN PRTL_BALANCED_LINKS Node2)
  56 {
  57     Node1->u1.Parent = Node2->u1.Parent;
  58     Node1->LeftChild = Node2->LeftChild;
  59     Node1->RightChild = Node2->RightChild;
  60 }
  61
  62 FORCEINLINE
  63 RTL_GENERIC_COMPARE_RESULTS
  64 MiAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
  65                       IN PVOID Buffer,
  66                       IN PVOID UserData)
  67 {
  68     PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(RTL_BALANCED_LINKS));
  69     ULONG_PTR StartingVpn = (ULONG_PTR)Buffer;
  70     if (StartingVpn < CurrentNode->StartingVpn)
  71     {
  72         return GenericLessThan;
  73     }
  74     else if (StartingVpn <= CurrentNode->EndingVpn)
  75     {
  76         return GenericEqual;
  77     }
  78     else
  79     {
  80         return GenericGreaterThan;
  81     }
  82 }
  83
  84 FORCEINLINE
  85 VOID
  86 MiSetParent(IN PRTL_BALANCED_LINKS Node,
  87              IN PRTL_BALANCED_LINKS Parent)
  88 {
  89     Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
  90 }
  91
  92 FORCEINLINE
  93 VOID
  94 MiSetBalance(IN PRTL_BALANCED_LINKS Node,
  95               IN SCHAR Balance)
  96 {
  97     Node->u1.Balance = Balance;
  98 }
  99
 100 FORCEINLINE
 101 SCHAR
 102 MiBalance(IN PRTL_BALANCED_LINKS Node)
 103 {
 104     return (SCHAR)Node->u1.Balance;
 105 }
 106
 107 FORCEINLINE
 108 PRTL_BALANCED_LINKS
 109 MiParentAvl(IN PRTL_BALANCED_LINKS Node)
 110 {
 111     return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
 112 }
 113
 114 FORCEINLINE
 115 PRTL_BALANCED_LINKS
 116 MiRightChildAvl(IN PRTL_BALANCED_LINKS Node)
 117 {
 118     return Node->RightChild;
 119 }
 120
 121 FORCEINLINE
 122 PRTL_BALANCED_LINKS
 123 MiLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
 124 {
 125     return Node->LeftChild;
 126 }
 127
 128 FORCEINLINE
 129 BOOLEAN
 130 MiIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
 131 {
 132    return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
 133 }
 134
 135 FORCEINLINE
 136 BOOLEAN
 137 MiIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
 138 {
 139    return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
 140 }
 141
 142 FORCEINLINE
 143 VOID
 144 MiInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent,
 145                         IN PRTL_BALANCED_LINKS Node)
 146 {
 147     Parent->LeftChild = Node;
 148     RtlSetParent(Node, Parent);
 149 }
 150
 151 FORCEINLINE
 152 VOID
 153 MiInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent,
 154                          IN PRTL_BALANCED_LINKS Node)
 155 {
 156     Parent->RightChild = Node;
 157     RtlSetParent(Node, Parent);
 158 }
 159
 160 /* EOF */