ReactOS  0.4.15-dev-1171-gab82533
miavl.h
Go to the documentation of this file.
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 
53 VOID
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 
65  IN PVOID Buffer,
67 {
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 
85 VOID
88 {
89  Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
90 }
91 
93 VOID
96 {
97  Node->u1.Balance = Balance;
98 }
99 
101 SCHAR
103 {
104  return (SCHAR)Node->u1.Balance;
105 }
106 
110 {
111  return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
112 }
113 
117 {
118  return Node->RightChild;
119 }
120 
124 {
125  return Node->LeftChild;
126 }
127 
129 BOOLEAN
131 {
132  return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
133 }
134 
136 BOOLEAN
138 {
139  return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
140 }
141 
143 VOID
146 {
147  Parent->LeftChild = Node;
149 }
150 
152 VOID
155 {
156  Parent->RightChild = Node;
158 }
159 
160 /* EOF */
#define IN
Definition: typedefs.h:39
ASMGENDATA Table[]
Definition: genincdata.c:61
static const UCHAR Balance[]
Definition: usbehci.c:97
struct _RTL_BALANCED_LINKS RTL_BALANCED_LINKS
#define RtlRightChildAvl
Definition: miavl.h:45
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE Parent
Definition: acpixf.h:728
FORCEINLINE RTL_GENERIC_COMPARE_RESULTS MiAvlCompareRoutine(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN PVOID UserData)
Definition: miavl.h:64
uint32_t ULONG_PTR
Definition: typedefs.h:65
FORCEINLINE VOID MiCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, IN PRTL_BALANCED_LINKS Node2)
Definition: miavl.h:54
FORCEINLINE PRTL_BALANCED_LINKS MiLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:123
FORCEINLINE PRTL_BALANCED_LINKS MiParentAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:109
union node Node
Definition: types.h:1255
FORCEINLINE VOID MiInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:144
FORCEINLINE VOID MiInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent, IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:153
unsigned char BOOLEAN
#define FORCEINLINE
Definition: ntbasedef.h:216
Definition: bufpool.h:45
void * PVOID
Definition: retypes.h:9
signed char SCHAR
Definition: sqltypes.h:14
FORCEINLINE BOOLEAN MiIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:130
FORCEINLINE VOID MiSetParent(IN PRTL_BALANCED_LINKS Node, IN PRTL_BALANCED_LINKS Parent)
Definition: miavl.h:86
#define RtlSetParent
Definition: miavl.h:41
#define RtlLeftChildAvl
Definition: miavl.h:46
FORCEINLINE BOOLEAN MiIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:137
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS
FORCEINLINE VOID MiSetBalance(IN PRTL_BALANCED_LINKS Node, IN SCHAR Balance)
Definition: miavl.h:94
FORCEINLINE SCHAR MiBalance(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:102
#define ULONG_PTR
Definition: config.h:101
#define RtlParentAvl
Definition: miavl.h:44
#define PRTL_BALANCED_LINKS
Definition: miavl.h:28
FORCEINLINE PRTL_BALANCED_LINKS MiRightChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:116
Definition: dlist.c:348