ReactOS 0.4.16-dev-311-g9382aa2
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
53VOID
56{
57 Node1->u1.Parent = Node2->u1.Parent;
58 Node1->LeftChild = Node2->LeftChild;
59 Node1->RightChild = Node2->RightChild;
60}
61
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
85VOID
88{
89 Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
90}
91
93VOID
96{
97 Node->u1.Balance = Balance;
98}
99
101SCHAR
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
131{
133}
134
138{
140}
141
143VOID
146{
147 Parent->LeftChild = Node;
149}
150
152VOID
155{
156 Parent->RightChild = Node;
158}
159
160/* EOF */
unsigned char BOOLEAN
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn UINT32 *TableIdx 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:732
Definition: bufpool.h:45
union node Node
Definition: types.h:1255
#define ULONG_PTR
Definition: config.h:101
ASMGENDATA Table[]
Definition: genincdata.c:61
FORCEINLINE PRTL_BALANCED_LINKS MiRightChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:116
FORCEINLINE PRTL_BALANCED_LINKS MiLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:123
FORCEINLINE VOID MiInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:144
FORCEINLINE PRTL_BALANCED_LINKS MiParentAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:109
FORCEINLINE BOOLEAN MiIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:137
#define RtlSetParent
Definition: miavl.h:41
FORCEINLINE VOID MiInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent, IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:153
#define RtlRightChildAvl
Definition: miavl.h:45
FORCEINLINE BOOLEAN MiIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:130
#define RtlParentAvl
Definition: miavl.h:44
FORCEINLINE VOID MiCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, IN PRTL_BALANCED_LINKS Node2)
Definition: miavl.h:54
#define RtlLeftChildAvl
Definition: miavl.h:46
FORCEINLINE VOID MiSetBalance(IN PRTL_BALANCED_LINKS Node, IN SCHAR Balance)
Definition: miavl.h:94
FORCEINLINE VOID MiSetParent(IN PRTL_BALANCED_LINKS Node, IN PRTL_BALANCED_LINKS Parent)
Definition: miavl.h:86
#define PRTL_BALANCED_LINKS
Definition: miavl.h:28
FORCEINLINE RTL_GENERIC_COMPARE_RESULTS MiAvlCompareRoutine(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN PVOID UserData)
Definition: miavl.h:64
FORCEINLINE SCHAR MiBalance(IN PRTL_BALANCED_LINKS Node)
Definition: miavl.h:102
signed char SCHAR
Definition: sqltypes.h:14
void * PVOID
Definition: typedefs.h:50
uint32_t ULONG_PTR
Definition: typedefs.h:65
#define IN
Definition: typedefs.h:39
Definition: dlist.c:348
static const UCHAR Balance[]
Definition: usbehci.c:97
#define FORCEINLINE
Definition: wdftypes.h:67
struct _RTL_BALANCED_LINKS RTL_BALANCED_LINKS
@ GenericLessThan
Definition: rtltypes.h:389
@ GenericEqual
Definition: rtltypes.h:391
@ GenericGreaterThan
Definition: rtltypes.h:390
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS