test: addrsup.c File Reference

Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

# addrsup.c File Reference

`#include "mi.h"`

Go to the source code of this file.

## Functions

VOID | MiReorderTree (IN PMMADDRESS_NODE Node, IN OUT PMMADDRESS_NODE *Root)
PMMADDRESS_NODE FASTCALL | MiGetNextNode (IN PMMADDRESS_NODE Node)
PMMADDRESS_NODE FASTCALL | MiGetPreviousNode (IN PMMADDRESS_NODE Node)
PMMADDRESS_NODE FASTCALL | MiGetFirstNode (IN PMMADDRESS_NODE Root)
VOID FASTCALL | MiInsertNode (IN PMMADDRESS_NODE Node, IN OUT PMMADDRESS_NODE *Root)
VOID FASTCALL | MiRemoveNode (IN PMMADDRESS_NODE Node, IN OUT PMMADDRESS_NODE *Root)
PMMADDRESS_NODE FASTCALL | MiLocateAddressInTree (IN ULONG_PTR Vpn, IN PMMADDRESS_NODE *Root)
PMMADDRESS_NODE | MiCheckForConflictingNode (IN ULONG_PTR StartVpn, IN ULONG_PTR EndVpn, IN PMMADDRESS_NODE Root)
PVOID | MiFindEmptyAddressRangeInTree (IN SIZE_T SizeOfRange, IN ULONG_PTR Alignment, IN PMMADDRESS_NODE Root, OUT PMMADDRESS_NODE *PreviousVad)
PVOID | MiFindEmptyAddressRangeDownTree (IN SIZE_T SizeOfRange, IN PVOID HighestAddressToEndAt, IN ULONG_PTR Alignment, IN PMMADDRESS_NODE Root)

## Function Documentation

PMMADDRESS_NODE MiCheckForConflictingNode | ( | IN ULONG_PTR | StartVpn,
|  | IN ULONG_PTR | EndVpn,
|  | IN PMMADDRESS_NODE | Root
| ) |

Definition at line 1068 of file addrsup.c.

References _MMADDRESS_NODE::EndingVpn, _MMADDRESS_NODE::LeftChild, NULL, _MMADDRESS_NODE::RightChild, and _MMADDRESS_NODE::StartingVpn.

    01076                    :
    01077
    01078     The function determines if any addresses between a given starting and
    01079     ending address is contained within a virtual address descriptor.
    01080
    01081 Arguments:
    01082
    01083     StartVpn - Supplies the virtual address to locate a containing
    01084                       descriptor.
    01085
    01086     EndVpn - Supplies the virtual address to locate a containing
    01087                       descriptor.
    01088
    01089 Return Value:
    01090
    01091     Returns a pointer to the first conflicting virtual address descriptor
    01092     if one is found, otherwise a NULL value is returned.
    01093
    01094 --*/
    01095
    01096 {
    01097     PMMADDRESS_NODE Node;
    01098
    01099     Node = Root;
    01100
    01101     for (;;) {
    01102
    01103         if (Node == (PMMADDRESS_NODE)NULL) {
    01104             return (PMMADDRESS_NODE)NULL;
    01105         }
    01106
    01107         if (StartVpn > Node->EndingVpn) {
    01108             Node = Node->RightChild;
    01109
    01110         } else if (EndVpn < Node->StartingVpn) {
    01111             Node = Node->LeftChild;
    01112
    01113         } else {
    01114
    01115             //
    01116             // The starting address is less than or equal to the end VA
    01117             // and the ending address is greater than or equal to the
    01118             // start va.  Return this node.
    01119             //
    01120
    01121             return Node;
    01122         }
    01123     }
    01124 }

PVOID MiFindEmptyAddressRangeDownTree | ( | IN SIZE_T | SizeOfRange,
|  | IN PVOID | HighestAddressToEndAt,
|  | IN ULONG_PTR | Alignment,
|  | IN PMMADDRESS_NODE | Root
| ) |

Definition at line 1252 of file addrsup.c.

References ASSERT, _MMADDRESS_NODE::EndingVpn, ExRaiseStatus(), MI_ALIGN_TO_SIZE, MI_ROUND_TO_SIZE, MI_VA_TO_VPN, MI_VPN_TO_VA, MI_VPN_TO_VA_ENDING, MiGetPreviousNode(), MM_HIGHEST_VAD_ADDRESS, NULL, PAGE_SHIFT, PAGE_SIZE, _MMADDRESS_NODE::RightChild, and _MMADDRESS_NODE::StartingVpn.

Referenced by MiFindEmptySectionBaseDown().

    01261                    :
    01262
    01263     The function examines the virtual address descriptors to locate
    01264     an unused range of the specified size and returns the starting
    01265     address of the range.  The function examines from the high
    01266     addresses down and ensures that starting address is less than
    01267     the specified address.
    01268
    01269 Arguments:
    01270
    01271     SizeOfRange - Supplies the size in bytes of the range to locate.
    01272
    01273     HighestAddressToEndAt - Supplies the virtual address that limits
    01274                             the value of the ending address.  The ending
    01275                             address of the located range must be less
    01276                             than this address.
    01277
    01278     Alignment - Supplies the alignment for the address.  Must be
    01279                  a power of 2 and greater than the page_size.
    01280
    01281     Root - Supplies the root of the tree to search through.
    01282
    01283 Return Value:
    01284
    01285     Returns the starting address of a suitable range.
    01286
    01287 --*/
    01288
    01289 {
    01290     PMMADDRESS_NODE Node;
    01291     PMMADDRESS_NODE PreviousNode;
    01292     ULONG_PTR AlignedEndingVa;
    01293     PVOID OptimalStart;
    01294     ULONG_PTR OptimalStartVpn;
    01295     ULONG_PTR HighestVpn;
    01296     ULONG_PTR AlignmentVpn;
    01297
    01298     SizeOfRange = MI_ROUND_TO_SIZE (SizeOfRange, PAGE_SIZE);
    01299
    01300     ASSERT (HighestAddressToEndAt != NULL);
    01301     ASSERT (HighestAddressToEndAt <= (PVOID)((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
    01302
    01303     HighestVpn = MI_VA_TO_VPN (HighestAddressToEndAt);
    01304
    01305     //
    01306     // Locate the Node with the highest starting address.
    01307     //
    01308
    01309     OptimalStart = (PVOID)(MI_ALIGN_TO_SIZE(
    01310                            (((ULONG_PTR)HighestAddressToEndAt + 1) - SizeOfRange),
    01311                            Alignment));
    01312     Node = Root;
    01313
    01314     if (Node == (PMMADDRESS_NODE)NULL) {
    01315
    01316         //
    01317         // The tree is empty, any range is okay.
    01318         //
    01319
    01320         return (PMMADDRESS_NODE)(OptimalStart);
    01321     }
    01322
    01323     //
    01324     // See if an empty slot exists to hold this range, locate the largest
    01325     // element in the tree.
    01326     //
    01327
    01328     while (Node->RightChild != (PMMADDRESS_NODE)NULL) {
    01329         Node = Node->RightChild;
    01330     }
    01331
    01332     //
    01333     // Check to see if a range exists between the highest address VAD
    01334     // and the highest address to end at.
    01335     //
    01336
    01337     AlignedEndingVa = (ULONG_PTR)MI_ROUND_TO_SIZE ((ULONG_PTR)MI_VPN_TO_VA_ENDING (Node->EndingVpn),
    01338                                                Alignment);
    01339
    01340     if (AlignedEndingVa < (ULONG_PTR)HighestAddressToEndAt) {
    01341
    01342         if ( SizeOfRange < ((ULONG_PTR)HighestAddressToEndAt - AlignedEndingVa)) {
    01343
    01344             return (PMMADDRESS_NODE)(MI_ALIGN_TO_SIZE(
    01345                                   ((ULONG_PTR)HighestAddressToEndAt - SizeOfRange),
    01346                                   Alignment));
    01347         }
    01348     }
    01349
    01350     //
    01351     // Walk the tree backwards looking for a fit.
    01352     //
    01353
    01354     OptimalStartVpn = MI_VA_TO_VPN (OptimalStart);
    01355     AlignmentVpn = MI_VA_TO_VPN (Alignment);
    01356
    01357     for (;;) {
    01358
    01359         PreviousNode = MiGetPreviousNode (Node);
    01360
    01361         if (PreviousNode != (PMMADDRESS_NODE)NULL) {
    01362
    01363             //
    01364             // Is the ending Va below the top of the address to end at.
    01365             //
    01366
    01367             if (PreviousNode->EndingVpn < OptimalStartVpn) {
    01368                 if ((SizeOfRange >> PAGE_SHIFT) <=
    01369                     ((ULONG_PTR)Node->StartingVpn -
    01370                     (ULONG_PTR)MI_ROUND_TO_SIZE(1 + PreviousNode->EndingVpn,
    01371                                             AlignmentVpn))) {
    01372
    01373                     //
    01374                     // See if the optimal start will fit between these
    01375                     // two VADs.
    01376                     //
    01377
    01378                     if ((OptimalStartVpn > PreviousNode->EndingVpn) &&
    01379                         (HighestVpn < Node->StartingVpn)) {
    01380                         return (PMMADDRESS_NODE)(OptimalStart);
    01381                     }
    01382
    01383                     //
    01384                     // Check to ensure that the ending address aligned upwards
    01385                     // is not greater than the starting address.
    01386                     //
    01387
    01388                     if ((ULONG_PTR)Node->StartingVpn >
    01389                             (ULONG_PTR)MI_ROUND_TO_SIZE(1 + PreviousNode->EndingVpn,
    01390                                                     AlignmentVpn)) {
    01391
    01392                         return (PMMADDRESS_NODE)MI_ALIGN_TO_SIZE(
    01393                                             (ULONG_PTR)MI_VPN_TO_VA (Node->StartingVpn) - SizeOfRange,
    01394                                             Alignment);
    01395                     }
    01396                 }
    01397             }
    01398         } else {
    01399
    01400             //
    01401             // No more descriptors, check to see if this fits into the remainder
    01402             // of the address space.
    01403             //
    01404
    01405             if (Node->StartingVpn > MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS)) {
    01406                 if ((SizeOfRange >> PAGE_SHIFT) <=
    01407                     ((ULONG_PTR)Node->StartingVpn - MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS))) {
    01408
    01409                     //
    01410                     // See if the optimal start will fit between these
    01411                     // two VADs.
    01412                     //
    01413
    01414                     if (HighestVpn < Node->StartingVpn) {
    01415                         return (PMMADDRESS_NODE)(OptimalStart);
    01416                     }
    01417
    01418                     return (PMMADDRESS_NODE)MI_ALIGN_TO_SIZE(
    01419                                   (ULONG_PTR)MI_VPN_TO_VA (Node->StartingVpn) - SizeOfRange,
    01420                                   Alignment);
    01421                 }
    01422             } else {
    01423                 ExRaiseStatus (STATUS_NO_MEMORY);
    01424             }
    01425         }
    01426         Node = PreviousNode;
    01427     }
    01428 }
    #if DBG

PVOID MiFindEmptyAddressRangeInTree | ( | IN SIZE_T | SizeOfRange,
|  | IN ULONG_PTR | Alignment,
|  | IN PMMADDRESS_NODE | Root,
|  | OUT PMMADDRESS_NODE * | PreviousVad
| ) |

Definition at line 1127 of file addrsup.c.

References ASSERT, _MMADDRESS_NODE::EndingVpn, ExRaiseStatus(), _MMADDRESS_NODE::LeftChild, MI_ROUND_TO_SIZE, MI_VA_TO_VPN, MI_VPN_TO_VA, MI_VPN_TO_VA_ENDING, MiGetNextNode(), MM_HIGHEST_VAD_ADDRESS, NULL, PAGE_SHIFT, PAGE_SIZE, _MMADDRESS_NODE::StartingVpn, and X64K.

Referenced by MiFindEmptyAddressRange().

    01136                    :
    01137
    01138     The function examines the virtual address descriptors to locate
    01139     an unused range of the specified size and returns the starting
    01140     address of the range.
    01141
    01142 Arguments:
    01143
    01144     SizeOfRange - Supplies the size in bytes of the range to locate.
    01145
    01146     Alignment - Supplies the alignment for the address.  Must be
    01147                  a power of 2 and greater than the page_size.
    01148
    01149     Root - Supplies the root of the tree to search through.
    01150
    01151     PreviousVad - Supplies the Vad which is before this the found
    01152                   address range.
    01153
    01154 Return Value:
    01155
    01156     Returns the starting address of a suitable range.
    01157
    01158 --*/
    01159
    01160 {
    01161     PMMADDRESS_NODE Node;
    01162     PMMADDRESS_NODE NextNode;
    01163     ULONG_PTR AlignmentVpn;
    01164
    01165     AlignmentVpn = Alignment >> PAGE_SHIFT;
    01166
    01167     //
    01168     // Locate the Node with the lowest starting address.
    01169     //
    01170
    01171     SizeOfRange = (SizeOfRange + (PAGE_SIZE - 1)) >> PAGE_SHIFT;
    01172     ASSERT (SizeOfRange != 0);
    01173
    01174     Node = Root;
    01175
    01176     if (Node == (PMMADDRESS_NODE)NULL) {
    01177         return MM_LOWEST_USER_ADDRESS;
    01178     }
    01179     while (Node->LeftChild != (PMMADDRESS_NODE)NULL) {
    01180         Node = Node->LeftChild;
    01181     }
    01182
    01183     //
    01184     // Check to see if a range exists between the lowest address VAD
    01185     // and lowest user address.
    01186     //
    01187
    01188     if (Node->StartingVpn > MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS)) {
    01189         if ( SizeOfRange <
    01190             (Node->StartingVpn - MI_VA_TO_VPN (MM_LOWEST_USER_ADDRESS))) {
    01191
    01192             *PreviousVad = NULL;
    01193             return MM_LOWEST_USER_ADDRESS;
    01194         }
    01195     }
    01196
    01197     for (;;) {
    01198
    01199         NextNode = MiGetNextNode (Node);
    01200
    01201         if (NextNode != (PMMADDRESS_NODE)NULL) {
    01202
    01203             if (SizeOfRange <=
    01204                 ((ULONG_PTR)NextNode->StartingVpn -
    01205                                 MI_ROUND_TO_SIZE(1 + Node->EndingVpn,
    01206                                                  AlignmentVpn))) {
    01207
    01208                 //
    01209                 // Check to ensure that the ending address aligned upwards
    01210                 // is not greater than the starting address.
    01211                 //
    01212
    01213                 if ((ULONG_PTR)NextNode->StartingVpn >
    01214                         MI_ROUND_TO_SIZE(1 + Node->EndingVpn,
    01215                                          AlignmentVpn)) {
    01216
    01217                     *PreviousVad = Node;
    01218                     return (PMMADDRESS_NODE)MI_ROUND_TO_SIZE(
    01219                                    (ULONG_PTR)MI_VPN_TO_VA_ENDING(Node->EndingVpn),
    01220                                           Alignment);
    01221                 }
    01222             }
    01223
    01224         } else {
    01225
    01226             //
    01227             // No more descriptors, check to see if this fits into the remainder
    01228             // of the address space.
    01229             //
    01230
    01231             if ((((ULONG_PTR)Node->EndingVpn + MI_VA_TO_VPN(X64K)) <
    01232                     MI_VA_TO_VPN (MM_HIGHEST_VAD_ADDRESS))
    01233                         &&
    01234                 (SizeOfRange <=
    01235                     ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS -
    01236                          (ULONG_PTR)MI_ROUND_TO_SIZE(
    01237                          (ULONG_PTR)MI_VPN_TO_VA(Node->EndingVpn), Alignment)))) {
    01238
    01239                 *PreviousVad = Node;
    01240                 return (PMMADDRESS_NODE)MI_ROUND_TO_SIZE(
    01241                                     (ULONG_PTR)MI_VPN_TO_VA_ENDING(Node->EndingVpn),
    01242                                     Alignment);
    01243             } else {
    01244                 ExRaiseStatus (STATUS_NO_MEMORY);
    01245             }
    01246         }
    01247         Node = NextNode;
    01248     }
    01249 }

PMMADDRESS_NODE FASTCALL MiGetFirstNode | ( | IN PMMADDRESS_NODE | Root | ) |

Definition at line 424 of file addrsup.c.

References _MMADDRESS_NODE::LeftChild, and NULL.

    00430                    :
    00431
    00432     This function locates the virtual address descriptor which contains
    00433     the address range which logically is first within the address space.
    00434
    00435 Arguments:
    00436
    00437     None.
    00438
    00439 Return Value:
    00440
    00441     Returns a pointer to the virtual address descriptor containing the
    00442     first address range, NULL if none.
    00443
    00444 --*/
    00445
    00446 {
    00447     PMMADDRESS_NODE First;
    00448
    00449     First = Root;
    00450
    00451     if (First == (PMMADDRESS_NODE)NULL) {
    00452         return (PMMADDRESS_NODE)NULL;
    00453     }
    00454
    00455     while (First->LeftChild != (PMMADDRESS_NODE)NULL) {
    00456         First = First->LeftChild;
    00457     }
    00458
    00459     return First;
    00460 }

PMMADDRESS_NODE FASTCALL MiGetNextNode | ( | IN PMMADDRESS_NODE | Node | ) |

Definition at line 297 of file addrsup.c.

References _MMADDRESS_NODE::LeftChild, NULL, _MMADDRESS_NODE::Parent, and _MMADDRESS_NODE::RightChild.

Referenced by MiFindEmptyAddressRangeInTree().

    00303                    :
    00304
    00305     This function locates the virtual address descriptor which contains
    00306     the address range which logically follows the specified address range.
    00307
    00308 Arguments:
    00309
    00310     Node - Supplies a pointer to a virtual address descriptor.
    00311
    00312 Return Value:
    00313
    00314     Returns a pointer to the virtual address descriptor containing the
    00315     next address range, NULL if none.
    00316
    00317 --*/
    00318
    00319 {
    00320     PMMADDRESS_NODE Next;
    00321     PMMADDRESS_NODE Parent;
    00322     PMMADDRESS_NODE Left;
    00323
    00324     Next = Node;
    00325
    00326     if (Next->RightChild == (PMMADDRESS_NODE)NULL) {
    00327
    00328         while ((Parent = Next->Parent) != (PMMADDRESS_NODE)NULL) {
    00329
    00330             //
    00331             // Locate the first ancestor of this node of which this
    00332             // node is the left child of and return that node as the
    00333             // next element.
    00334             //
    00335
    00336             if (Parent->LeftChild == Next) {
    00337                 return Parent;
    00338             }
    00339
    00340             Next = Parent;
    00341
    00342         }
    00343
    00344         return (PMMADDRESS_NODE)NULL;
    00345     }
    00346
    00347     //
    00348     // A right child exists, locate the left most child of that right child.
    00349     //
    00350
    00351     Next = Next->RightChild;
    00352
    00353     while ((Left = Next->LeftChild) != (PMMADDRESS_NODE)NULL) {
    00354         Next = Left;
    00355     }
    00356     return Next;
    00357
    00358 }

PMMADDRESS_NODE FASTCALL MiGetPreviousNode | ( | IN PMMADDRESS_NODE | Node | ) |

Definition at line 362 of file addrsup.c.

References _MMADDRESS_NODE::LeftChild, NULL, _MMADDRESS_NODE::Parent, and _MMADDRESS_NODE::RightChild.

Referenced by MiFindEmptyAddressRangeDownTree().

    00368                    :
    00369
    00370     This function locates the virtual address descriptor which contains
    00371     the address range which logically precedes the specified virtual
    00372     address descriptor.
    00373
    00374 Arguments:
    00375
    00376     Node - Supplies a pointer to a virtual address descriptor.
    00377
    00378 Return Value:
    00379
    00380     Returns a pointer to the virtual address descriptor containing the
    00381     next address range, NULL if none.
    00382
    00383 --*/
    00384
    00385 {
    00386     PMMADDRESS_NODE Previous;
    00387
    00388     Previous = Node;
    00389
    00390     if (Previous->LeftChild == (PMMADDRESS_NODE)NULL) {
    00391
    00392
    00393         while (Previous->Parent != (PMMADDRESS_NODE)NULL) {
    00394
    00395             //
    00396             // Locate the first ancestor of this node of which this
    00397             // node is the right child of and return that node as the
    00398             // Previous element.
    00399             //
    00400
    00401             if (Previous->Parent->RightChild == Previous) {
    00402                 return Previous->Parent;
    00403             }
    00404
    00405             Previous = Previous->Parent;
    00406
    00407         }
    00408         return (PMMADDRESS_NODE)NULL;
    00409     }
    00410
    00411     //
    00412     // A left child exists, locate the right most child of that left child.
    00413     //
    00414
    00415     Previous = Previous->LeftChild;
    00416     while (Previous->RightChild != (PMMADDRESS_NODE)NULL) {
    00417         Previous = Previous->RightChild;
    00418     }
    00419     return Previous;
    00420 }

VOID FASTCALL MiInsertNode | ( | IN PMMADDRESS_NODE | Node,
|  | IN OUT PMMADDRESS_NODE * | Root
| ) |

Definition at line 464 of file addrsup.c.

References _MMADDRESS_NODE::LeftChild, MiReorderTree(), NULL, _MMADDRESS_NODE::Parent, _MMADDRESS_NODE::RightChild, and _MMADDRESS_NODE::StartingVpn.

Referenced by MiInsertBasedSection(), and MiInsertVad().

    00471                    :
    00472
    00473     This function inserts a virtual address descriptor into the tree and
    00474     reorders the splay tree as appropriate.
    00475
    00476 Arguments:
    00477
    00478     Node - Supplies a pointer to a virtual address descriptor
    00479
    00480
    00481 Return Value:
    00482
    00483     None.
    00484
    00485 --*/
    00486
    00487 {
    00488     ULONG Level = 0;
    00489     PMMADDRESS_NODE Parent;
    00490
    00491     //
    00492     // Initialize virtual address descriptor child links.
    00493     //
    00494
    00495     Node->LeftChild = (PMMADDRESS_NODE)NULL;
    00496     Node->RightChild = (PMMADDRESS_NODE)NULL;
    00497
    00498     //
    00499     // If the tree is empty, then establish this virtual address descriptor
    00500     // as the root of the tree.
    00501     // Otherwise descend the tree to find the correct place to
    00502     // insert the descriptor.
    00503     //
    00504
    00505     Parent = *Root;
    00506     if (!Parent) {
    00507         *Root = Node;
    00508         Node->Parent = (PMMADDRESS_NODE)NULL;
    00509     } else {
    00510
    00511         for (;;) {
    00512
    00513             Level += 1;
    00514             if (Level == 15) {
    00515                 MiReorderTree(Parent, Root);
    00516             }
    00517
    00518             //
    00519             // If the starting address for this virtual address descriptor
    00520             // is less than the parent starting address, then
    00521             // follow the left child link. Else follow the right child link.
    00522             //
    00523
    00524             if (Node->StartingVpn < Parent->StartingVpn) {
    00525
    00526                 //
    00527                 // Starting address of the virtual address descriptor is less
    00528                 // than the parent starting virtual address.
    00529                 // Follow left child link if not null. Otherwise
    00530                 // insert the descriptor as the left child of the parent and
    00531                 // reorder the tree.
    00532                 //
    00533
    00534                 if (Parent->LeftChild) {
    00535                     Parent = Parent->LeftChild;
    00536                 } else {
    00537                     Parent->LeftChild = Node;
    00538                     Node->Parent = Parent;
    00539                     // MiReorderTree(Node, Root);
    00540                     break;
    00541                 }
    00542             } else {
    00543
    00544                 //
    00545                 // Starting address of the virtual address descriptor is greater
    00546                 // than the parent starting virtual address.
    00547                 // Follow right child link if not null. Otherwise
    00548                 // insert the descriptor as the right child of the parent and
    00549                 // reorder the tree.
    00550                 //
    00551
    00552                 if (Parent->RightChild) {
    00553                     Parent = Parent->RightChild;
    00554                 } else {
    00555                     Parent->RightChild = Node;
    00556                     Node->Parent = Parent;
    00557                     // MiReorderTree(Node, Root);
    00558                     break;
    00559                 }
    00560             }
    00561         }
    00562     }
    00563     return;
    00564 }

PMMADDRESS_NODE FASTCALL MiLocateAddressInTree | ( | IN ULONG_PTR | Vpn,
|  | IN PMMADDRESS_NODE * | Root
| ) |

Definition at line 1001 of file addrsup.c.

References _MMADDRESS_NODE::EndingVpn, _MMADDRESS_NODE::LeftChild, MiReorderTree(), NULL, _MMADDRESS_NODE::RightChild, and _MMADDRESS_NODE::StartingVpn.

Referenced by MiLocateAddress().

    01008                    :
    01009
    01010     The function locates the virtual address descriptor which describes
    01011     a given address.
    01012
    01013 Arguments:
    01014
    01015     Vpn - Supplies the virtual page number to locate a descriptor
    01016                      for.
    01017
    01018 Return Value:
    01019
    01020     Returns a pointer to the virtual address descriptor which contains
    01021     the supplied virtual address or NULL if none was located.
    01022
    01023 --*/
    01024
    01025 {
    01026
    01027     PMMADDRESS_NODE Parent;
    01028     ULONG Level = 0;
    01029
    01030     Parent = *Root;
    01031
    01032     for (;;) {
    01033
    01034         if (Parent == (PMMADDRESS_NODE)NULL) {
    01035             return (PMMADDRESS_NODE)NULL;
    01036         }
    01037
    01038         if (Level == 20) {
    01039
    01040             //
    01041             // There are 20 nodes above this point, reorder the
    01042             // tree with this node as the root.
    01043             //
    01044
    01045             MiReorderTree(Parent, Root);
    01046         }
    01047
    01048         if (Vpn < Parent->StartingVpn) {
    01049             Parent = Parent->LeftChild;
    01050             Level += 1;
    01051
    01052         } else if (Vpn > Parent->EndingVpn) {
    01053             Parent = Parent->RightChild;
    01054             Level += 1;
    01055
    01056         } else {
    01057
    01058             //
    01059             // The address is within the start and end range.
    01060             //
    01061
    01062             return Parent;
    01063         }
    01064     }
    01065 }

VOID FASTCALL MiRemoveNode | ( | IN PMMADDRESS_NODE | Node,
|  | IN OUT PMMADDRESS_NODE * | Root
| ) |

Definition at line 568 of file addrsup.c.

References _MMADDRESS_NODE::LeftChild, NULL, _MMADDRESS_NODE::Parent, and _MMADDRESS_NODE::RightChild.

Referenced by MiRemoveBasedSection(), and MiRemoveVad().

    00575                    :
    00576
    00577     This function removes a virtual address descriptor from the tree and
    00578     reorders the splay tree as appropriate.
    00579
    00580 Arguments:
    00581
    00582     Node - Supplies a pointer to a virtual address descriptor.
    00583
    00584 Return Value:
    00585
    00586     None.
    00587
    00588 --*/
    00589
    00590 {
    00591
    00592     PMMADDRESS_NODE LeftChild;
    00593     PMMADDRESS_NODE RightChild;
    00594     PMMADDRESS_NODE SplayNode;
    00595
    00596
    00597     LeftChild = Node->LeftChild;
    00598     RightChild = Node->RightChild;
    00599
    00600
    00601     //
    00602     // If the Node is the root of the tree, then establish new root. Else
    00603     // isolate splay case and perform splay tree transformation.
    00604     //
    00605
    00606     if (Node == *Root) {
    00607
    00608         //
    00609         // This Node is the root of the tree. There are four cases to
    00610         // handle:
    00611         //
    00612         //  1. the descriptor has no children
    00613         //  2. the descriptor has a left child but no right child
    00614         //  3. the descriptor has a right child but no left child
    00615         //  4. the descriptor has both a right child and a left child
    00616         //
    00617
    00618         if (LeftChild) {
    00619             if (RightChild) {
    00620
    00621                 //
    00622                 // The descriptor has both a left child and a right child.
    00623                 //
    00624
    00625                 if (LeftChild->RightChild) {
    00626
    00627                     //
    00628                     // The left child has a right child. Make the right most
    00629                     // descendent of the right child of the left child the
    00630                     // new root of the tree.
    00631                     //
    00632                     // Pictorially:
    00633                     //
    00634                     //      R          R
    00635                     //      |          |
    00636                     //      X          Z
    00637                     //     / \        / \
    00638                     //    A   B  ->  A   B
    00639                     //     \          \
    00640                     //      .          .
    00641                     //       \
    00642                     //        Z
    00643                     //
    00644
    00645                     SplayNode = LeftChild->RightChild;
    00646                     while (SplayNode->RightChild) {
    00647                         SplayNode = SplayNode->RightChild;
    00648                     }
    00649                     *Root = SplayNode;
    00650                     SplayNode->Parent->RightChild = SplayNode->LeftChild;
    00651                     if (SplayNode->LeftChild) {
    00652                         SplayNode->LeftChild->Parent = SplayNode->Parent;
    00653                     }
    00654                     SplayNode->Parent = (PMMADDRESS_NODE)NULL;
    00655                     LeftChild->Parent = SplayNode;
    00656                     RightChild->Parent = SplayNode;
    00657                     SplayNode->LeftChild = LeftChild;
    00658                     SplayNode->RightChild = RightChild;
    00659                 } else if (RightChild->LeftChild) {
    00660
    00661                     //
    00662                     // The right child has a left child. Make the left most
    00663                     // descendent of the left child of the right child the
    00664                     // new root of the tree.
    00665                     //
    00666                     // Pictorially:
    00667                     //
    00668                     //      R          R
    00669                     //      |          |
    00670                     //      X          Z
    00671                     //     / \        / \
    00672                     //    A   B  ->  A   B
    00673                     //       /          /
    00674                     //      .          .
    00675                     //     /
    00676                     //    Z
    00677                     //
    00678
    00679                     SplayNode = RightChild->LeftChild;
    00680                     while (SplayNode->LeftChild) {
    00681                         SplayNode = SplayNode->LeftChild;
    00682                     }
    00683                     *Root = SplayNode;
    00684                     SplayNode->Parent->LeftChild = SplayNode->RightChild;
    00685                     if (SplayNode->RightChild) {
    00686                         SplayNode->RightChild->Parent = SplayNode->Parent;
    00687                     }
    00688                     SplayNode->Parent = (PMMADDRESS_NODE)NULL;
    00689                     LeftChild->Parent = SplayNode;
    00690                     RightChild->Parent = SplayNode;
    00691                     SplayNode->LeftChild = LeftChild;
    00692                     SplayNode->RightChild = RightChild;
    00693                 } else {
    00694
    00695                     //
    00696                     // The left child of the descriptor does not have a right child,
    00697                     // and the right child of the descriptor does not have a left
    00698                     // child. Make the left child of the descriptor the new root of
    00699                     // the tree.
    00700                     //
    00701                     // Pictorially:
    00702                     //
    00703                     //      R          R
    00704                     //      |          |
    00705                     //      X          A
    00706                     //     / \        / \
    00707                     //    A   B  ->  .   B
    00708                     //   /          /
    00709                     //  .
    00710                     //
    00711
    00712                     *Root = LeftChild;
    00713                     LeftChild->Parent = (PMMADDRESS_NODE)NULL;
    00714                     LeftChild->RightChild = RightChild;
    00715                     LeftChild->RightChild->Parent = LeftChild;
    00716                 }
    00717             } else {
    00718
    00719                 //
    00720                 // The descriptor has a left child, but does not have a right child.
    00721                 // Make the left child the new root of the tree.
    00722                 //
    00723                 // Pictorially:
    00724                 //
    00725                 //       R      R
    00726                 //       |      |
    00727                 //       X  ->  A
    00728                 //      /
    00729                 //     A
    00730                 //
    00731
    00732                 *Root = LeftChild;
    00733                 LeftChild->Parent = (PMMADDRESS_NODE)NULL;
    00734             }
    00735         } else if (RightChild) {
    00736
    00737             //
    00738             // The descriptor has a right child, but does not have a left child.
    00739             // Make the right child the new root of the tree.
    00740             //
    00741             // Pictorially:
    00742             //
    00743             //       R         R
    00744             //       |         |
    00745             //       X    ->   A
    00746             //        \
    00747             //         A
    00748             //
    00749
    00750             *Root = RightChild;
    00751             RightChild->Parent = (PMMADDRESS_NODE)NULL;
    00752             while (RightChild->LeftChild) {
    00753                 RightChild = RightChild->LeftChild;
    00754             }
    00755         } else {
    00756
    00757             //
    00758             // The descriptor has neither a left child nor a right child. The
    00759             // tree will be empty after removing the descriptor.
    00760             //
    00761             // Pictorially:
    00762             //
    00763             //      R      R
    00764             //      |  ->
    00765             //      X
    00766             //
    00767
    00768             *Root = NULL;
    00769         }
    00770     } else if (LeftChild) {
    00771         if (RightChild) {
    00772
    00773             //
    00774             // The descriptor has both a left child and a right child.
    00775             //
    00776
    00777             if (LeftChild->RightChild) {
    00778
    00779                 //
    00780                 // The left child has a right child. Make the right most
    00781                 // descendent of the right child of the left child the new
    00782                 // root of the subtree.
    00783                 //
    00784                 // Pictorially:
    00785                 //
    00786                 //        P      P
    00787                 //       /        \
    00788                 //      X          X
    00789                 //     / \        / \
    00790                 //    A   B  or  A   B
    00791                 //     \          \
    00792                 //      .          .
    00793                 //       \          \
    00794                 //        Z          Z
    00795                 //
    00796                 //           |
    00797                 //           v
    00798                 //
    00799                 //        P      P
    00800                 //       /        \
    00801                 //      Z          Z
    00802                 //     / \        / \
    00803                 //    A   B  or  A   B
    00804                 //     \          \
    00805                 //      .          .
    00806                 //
    00807
    00808                 SplayNode = LeftChild->RightChild;
    00809                 while (SplayNode->RightChild) {
    00810                     SplayNode = SplayNode->RightChild;
    00811                 }
    00812                 SplayNode->Parent->RightChild = SplayNode->LeftChild;
    00813                 if (SplayNode->LeftChild) {
    00814                     SplayNode->LeftChild->Parent = SplayNode->Parent;
    00815                 }
    00816                 SplayNode->Parent = Node->Parent;
    00817                 if (Node == Node->Parent->LeftChild) {
    00818                     Node->Parent->LeftChild = SplayNode;
    00819                 } else {
    00820                     Node->Parent->RightChild = SplayNode;
    00821                 }
    00822                 LeftChild->Parent = SplayNode;
    00823                 RightChild->Parent = SplayNode;
    00824                 SplayNode->LeftChild = LeftChild;
    00825                 SplayNode->RightChild = RightChild;
    00826             } else if (RightChild->LeftChild) {
    00827
    00828                 //
    00829                 // The right child has a left child. Make the left most
    00830                 // descendent of the left child of the right child the
    00831                 // new root of the subtree.
    00832                 //
    00833                 // Pictorially:
    00834                 //
    00835                 //        P      P
    00836                 //       /        \
    00837                 //      X          X
    00838                 //     / \        / \
    00839                 //    A   B  or  A   B
    00840                 //       /          /
    00841                 //      .          .
    00842                 //     /          /
    00843                 //    Z          Z
    00844                 //
    00845                 //           |
    00846                 //           v
    00847                 //
    00848                 //        P      P
    00849                 //       /        \
    00850                 //      Z          Z
    00851                 //     / \        / \
    00852                 //    A   B  or  A   B
    00853                 //       /          /
    00854                 //      .          .
    00855                 //
    00856
    00857                 SplayNode = RightChild->LeftChild;
    00858                 while (SplayNode->LeftChild) {
    00859                     SplayNode = SplayNode->LeftChild;
    00860                 }
    00861                 SplayNode->Parent->LeftChild = SplayNode->RightChild;
    00862                 if (SplayNode->RightChild) {
    00863                     SplayNode->RightChild->Parent = SplayNode->Parent;
    00864                 }
    00865                 SplayNode->Parent = Node->Parent;
    00866                 if (Node == Node->Parent->LeftChild) {
    00867                     Node->Parent->LeftChild = SplayNode;
    00868                 } else {
    00869                     Node->Parent->RightChild = SplayNode;
    00870                 }
    00871                 LeftChild->Parent = SplayNode;
    00872                 RightChild->Parent = SplayNode;
    00873                 SplayNode->LeftChild = LeftChild;
    00874                 SplayNode->RightChild = RightChild;
    00875             } else {
    00876
    00877                 //
    00878                 // The left child of the descriptor does not have a right child,
    00879                 // and the right child of the descriptor does node have a left
    00880                 // child. Make the left child of the descriptor the new root of
    00881                 // the subtree.
    00882                 //
    00883                 // Pictorially:
    00884                 //
    00885                 //        P      P
    00886                 //       /        \
    00887                 //      X          X
    00888                 //     / \        / \
    00889                 //    A   B  or  A   B
    00890                 //   /          /
    00891                 //  .          .
    00892                 //
    00893                 //           |
    00894                 //           v
    00895                 //
    00896                 //        P      P
    00897                 //       /        \
    00898                 //      A          A
    00899                 //     / \        / \
    00900                 //    .   B  or  .   B
    00901                 //   /          /
    00902                 //
    00903
    00904                 SplayNode = LeftChild;
    00905                 SplayNode->Parent = Node->Parent;
    00906                 if (Node == Node->Parent->LeftChild) {
    00907                     Node->Parent->LeftChild = SplayNode;
    00908                 } else {
    00909                     Node->Parent->RightChild = SplayNode;
    00910                 }
    00911                 SplayNode->RightChild = RightChild;
    00912                 RightChild->Parent = SplayNode;
    00913             }
    00914         } else {
    00915
    00916             //
    00917             // The descriptor has a left child, but does not have a right child.
    00918             // Make the left child the new root of the subtree.
    00919             //
    00920             // Pictorially:
    00921             //
    00922             //        P   P
    00923             //       /     \
    00924             //      X   or  X
    00925             //     /       /
    00926             //    A       A
    00927             //
    00928             //          |
    00929             //          v
    00930             //
    00931             //        P   P
    00932             //       /     \
    00933             //      A       A
    00934             //
    00935
    00936             LeftChild->Parent = Node->Parent;
    00937             if (Node == Node->Parent->LeftChild) {
    00938                 Node->Parent->LeftChild = LeftChild;
    00939             } else {
    00940                 Node->Parent->RightChild = LeftChild;
    00941             }
    00942         }
    00943     } else if (RightChild) {
    00944
    00945         //
    00946         // descriptor has a right child, but does not have a left child. Make
    00947         // the right child the new root of the subtree.
    00948         //
    00949         // Pictorially:
    00950         //
    00951         //        P   P
    00952         //       /     \
    00953         //      X   or  X
    00954         //       \       \
    00955         //        A       A
    00956         //
    00957         //          |
    00958         //          v
    00959         //
    00960         //        P   P
    00961         //       /     \
    00962         //      A       A
    00963         //
    00964
    00965         RightChild->Parent = Node->Parent;
    00966         if (Node == Node->Parent->LeftChild) {
    00967             Node->Parent->LeftChild = RightChild;
    00968         } else {
    00969             Node->Parent->RightChild = RightChild;
    00970         }
    00971     } else {
    00972
    00973         //
    00974         // The descriptor has neither a left child nor a right child. Delete
    00975         // the descriptor from the tree and adjust its parent right or left
    00976         // link.
    00977         //
    00978         // Pictorially:
    00979         //
    00980         //        P   P
    00981         //       /     \
    00982         //      X   or  X
    00983         //
    00984         //          |
    00985         //          v
    00986         //
    00987         //        P   P
    00988         //
    00989
    00990         if (Node == Node->Parent->LeftChild) {
    00991             Node->Parent->LeftChild = (PMMADDRESS_NODE)NULL;
    00992         } else {
    00993             Node->Parent->RightChild = (PMMADDRESS_NODE)NULL;
    00994         }
    00995     }
    00996     return;
    00997 }

VOID MiReorderTree | ( | IN PMMADDRESS_NODE | Node,
|  | IN OUT PMMADDRESS_NODE * | Root
| ) |

Definition at line 45 of file addrsup.c.

References _MMADDRESS_NODE::LeftChild, NULL, _MMADDRESS_NODE::Parent, and _MMADDRESS_NODE::RightChild.

Referenced by MiInsertNode(), and MiLocateAddressInTree().

    00052                    :
    00053
    00054     This function reorders the Node tree by applying various splay functions
    00055     to the tree. This is a local function that is called by the insert Node
    00056     routine.
    00057
    00058 Arguments:
    00059
    00060     Node - Supplies a pointer to a virtual address descriptor.
    00061
    00062 Return Value:
    00063
    00064     None.
    00065
    00066 --*/
    00067
    00068 {
    00069     PMMADDRESS_NODE GrandParent;
    00070     PMMADDRESS_NODE Parent;
    00071     PMMADDRESS_NODE SplayNode;
    00072
    00073     //
    00074     // Reorder Node tree to make it as balanced as possible with as little
    00075     // work as possible.
    00076     //
    00077
    00078     SplayNode = Node;
    00079
    00080     while (SplayNode != *Root) {
    00081
    00082         Parent = SplayNode->Parent;
    00083         if (Parent == *Root) {
    00084
    00085             //
    00086             // Splay node's parent is the root of the tree. Rotate the tree
    00087             // left or right depending on whether the splay node is the left
    00088             // of right child of its parent.
    00089             //
    00090             // Pictorially:
    00091             //
    00092             //            Right                 Left
    00093             //
    00094             //          P        X          P          X
    00095             //         / \      / \        / \        / \
    00096             //        X   C -> A   P      C   X  ->  P   A
    00097             //       / \          / \        / \    / \
    00098             //      A   B        B   C      B   A  C   B
    00099             //
    00100
    00101             *Root = SplayNode;
    00102             SplayNode->Parent = (PMMADDRESS_NODE)NULL;
    00103             Parent->Parent = SplayNode;
    00104             if (SplayNode == Parent->LeftChild) {
    00105
    00106                 //
    00107                 // Splay node is the left child of its parent. Rotate tree
    00108                 // right.
    00109                 //
    00110
    00111                 Parent->LeftChild = SplayNode->RightChild;
    00112                 if (SplayNode->RightChild) {
    00113                     SplayNode->RightChild->Parent = Parent;
    00114                 }
    00115                 SplayNode->RightChild = Parent;
    00116             } else {
    00117
    00118                 //
    00119                 // Splay node is the right child of its parent. Rotate tree
    00120                 // left.
    00121                 //
    00122
    00123                 Parent->RightChild = SplayNode->LeftChild;
    00124                 if (SplayNode->LeftChild) {
    00125                     SplayNode->LeftChild->Parent = Parent;
    00126                 }
    00127                 SplayNode->LeftChild = Parent;
    00128             }
    00129             break;
    00130         } else {
    00131             GrandParent = Parent->Parent;
    00132             if ((SplayNode == Parent->LeftChild) &&
    00133                (Parent == GrandParent->LeftChild)) {
    00134
    00135                 //
    00136                 // Both the splay node and the parent node are left children
    00137                 // of their parents. Rotate tree right and make the parent
    00138                 // the root of the new subtree.
    00139                 //
    00140                 // Pictorially:
    00141                 //
    00142                 //        G                 P
    00143                 //       / \              /   \
    00144                 //      P   D            X     G
    00145                 //     / \       ->     / \   / \
    00146                 //    X   C            A   B C   D
    00147                 //   / \
    00148                 //  A   B
    00149                 //
    00150
    00151                 if (GrandParent == *Root) {
    00152                     *Root = Parent;
    00153                     Parent->Parent = (PMMADDRESS_NODE)NULL;
    00154                 } else {
    00155                     Parent->Parent = GrandParent->Parent;
    00156                     if (GrandParent == GrandParent->Parent->LeftChild) {
    00157                         GrandParent->Parent->LeftChild = Parent;
    00158                     } else {
    00159                         GrandParent->Parent->RightChild = Parent;
    00160                     }
    00161                 }
    00162                 GrandParent->LeftChild = Parent->RightChild;
    00163                 if (Parent->RightChild) {
    00164                     Parent->RightChild->Parent = GrandParent;
    00165                 }
    00166                 GrandParent->Parent = Parent;
    00167                 Parent->RightChild = GrandParent;
    00168                 SplayNode = Parent;
    00169             } else if ((SplayNode == Parent->RightChild) &&
    00170                       (Parent == GrandParent->RightChild)) {
    00171
    00172                 //
    00173                 // Both the splay node and the parent node are right children
    00174                 // of their parents. Rotate tree left and make the parent
    00175                 // the root of the new subtree.
    00176                 //
    00177                 // Pictorially:
    00178                 //
    00179                 //        G                 P
    00180                 //       / \              /   \
    00181                 //      D   P            G     X
    00182                 //         / \   ->     / \   / \
    00183                 //        C   X        D   C B   A
    00184                 //           / \
    00185                 //          A   B
    00186                 //
    00187
    00188                 if (GrandParent == *Root) {
    00189                     *Root = Parent;
    00190                     Parent->Parent = (PMMADDRESS_NODE)NULL;
    00191                 } else {
    00192                     Parent->Parent = GrandParent->Parent;
    00193                     if (GrandParent == GrandParent->Parent->LeftChild) {
    00194                         GrandParent->Parent->LeftChild = Parent;
    00195                     } else {
    00196                         GrandParent->Parent->RightChild = Parent;
    00197                     }
    00198                 }
    00199                 GrandParent->RightChild = Parent->LeftChild;
    00200                 if (Parent->LeftChild) {
    00201                     Parent->LeftChild->Parent = GrandParent;
    00202                 }
    00203                 GrandParent->Parent = Parent;
    00204                 Parent->LeftChild = GrandParent;
    00205                 SplayNode = Parent;
    00206             } else if ((SplayNode == Parent->LeftChild) &&
    00207                       (Parent == GrandParent->RightChild)) {
    00208
    00209                 //
    00210                 // Splay node is the left child of its parent and parent is
    00211                 // the right child of its parent. Rotate tree left and make
    00212                 // splay node the root of the new subtree.
    00213                 //
    00214                 // Pictorially:
    00215                 //
    00216                 //      G                 X
    00217                 //     / \              /   \
    00218                 //    A   P            G     P
    00219                 //       / \    ->    / \   / \
    00220                 //      X   D        A   B C   D
    00221                 //     / \
    00222                 //    B   C
    00223                 //
    00224
    00225                 if (GrandParent == *Root) {
    00226                     *Root = SplayNode;
    00227                     SplayNode->Parent = (PMMADDRESS_NODE)NULL;
    00228                 } else {
    00229                     SplayNode->Parent = GrandParent->Parent;
    00230                     if (GrandParent == GrandParent->Parent->LeftChild) {
    00231                         GrandParent->Parent->LeftChild = SplayNode;
    00232                     } else {
    00233                         GrandParent->Parent->RightChild = SplayNode;
    00234                     }
    00235                 }
    00236                 Parent->LeftChild = SplayNode->RightChild;
    00237                 if (SplayNode->RightChild) {
    00238                     SplayNode->RightChild->Parent = Parent;
    00239                 }
    00240                 GrandParent->RightChild = SplayNode->LeftChild;
    00241                 if (SplayNode->LeftChild) {
    00242                     SplayNode->LeftChild->Parent = GrandParent;
    00243                 }
    00244                 Parent->Parent = SplayNode;
    00245                 GrandParent->Parent = SplayNode;
    00246                 SplayNode->LeftChild = GrandParent;
    00247                 SplayNode->RightChild = Parent;
    00248             } else {
    00249
    00250                 //
    00251                 // Splay node is the right child of its parent and parent is
    00252                 // the left child of its parent. Rotate tree right and make
    00253                 // splay node the root of the new subtree.
    00254                 //
    00255                 // Pictorially:
    00256                 //
    00257                 //       G                 X
    00258                 //      / \              /   \
    00259                 //     P   A            P     G
    00260                 //    / \        ->    / \   / \
    00261                 //   D   X            D   C B   A
    00262                 //      / \
    00263                 //     C   B
    00264                 //
    00265
    00266                 if (GrandParent == *Root) {
    00267                     *Root = SplayNode;
    00268                     SplayNode->Parent = (PMMADDRESS_NODE)NULL;
    00269                 } else {
    00270                     SplayNode->Parent = GrandParent->Parent;
    00271                     if (GrandParent == GrandParent->Parent->LeftChild) {
    00272                         GrandParent->Parent->LeftChild = SplayNode;
    00273                     } else {
    00274                         GrandParent->Parent->RightChild = SplayNode;
    00275                     }
    00276                 }
    00277                 Parent->RightChild = SplayNode->LeftChild;
    00278                 if (SplayNode->LeftChild) {
    00279                     SplayNode->LeftChild->Parent = Parent;
    00280                 }
    00281                 GrandParent->LeftChild = SplayNode->RightChild;
    00282                 if (SplayNode->RightChild) {
    00283                     SplayNode->RightChild->Parent = GrandParent;
    00284                 }
    00285                 Parent->Parent = SplayNode;
    00286                 GrandParent->Parent = SplayNode;
    00287                 SplayNode->LeftChild = Parent;
    00288                 SplayNode->RightChild = GrandParent;
    00289             }
    00290         }
    00291     }
    00292     return;
    00293 }