ubuntu/vbox/vboxguest/common/table/avl_GetBestFit.cpp.h

   1 /* $Id: avl_GetBestFit.cpp.h $ */
   2 /** @file
   3  * kAVLGetBestFit - Get Best Fit routine for AVL trees.
   4  *                  Intended specially on heaps. The tree should allow duplicate keys.
   5  *
   6  */
   7
   8 /*
   9  * Copyright (C) 1999-2012 knut st. osmundsen (bird-src-spam@anduin.net)
  10  *
  11  * This file is part of VirtualBox Open Source Edition (OSE), as
  12  * available from http://www.virtualbox.org. This file is free software;
  13  * you can redistribute it and/or modify it under the terms of the GNU
  14  * General Public License (GPL) as published by the Free Software
  15  * Foundation, in version 2 as it comes in the "COPYING" file of the
  16  * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
  17  * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
  18  *
  19  * The contents of this file may alternatively be used under the terms
  20  * of the Common Development and Distribution License Version 1.0
  21  * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
  22  * VirtualBox OSE distribution, in which case the provisions of the
  23  * CDDL are applicable instead of those of the GPL.
  24  *
  25  * You may elect to license modified versions of this file under the
  26  * terms and conditions of either the GPL or the CDDL or both.
  27  */
  28
  29 #ifndef _kAVLGetBestFit_h_
  30 #define _kAVLGetBestFit_h_
  31
  32
  33 /**
  34  * Finds the best fitting node in the tree for the given Key value.
  35  * @returns   Pointer to the best fitting node found.
  36  * @param     ppTree  Pointer to Pointer to the tree root node.
  37  * @param     Key     The Key of which is to be found a best fitting match for..
  38  * @param     fAbove  TRUE:  Returned node is have the closest key to Key from above.
  39  *                    FALSE: Returned node is have the closest key to Key from below.
  40  * @sketch    The best fitting node is always located in the searchpath above you.
  41  *            >= (above): The node where you last turned left.
  42  *            <= (below): the node where you last turned right.
  43  */
  44 KAVL_DECL(PKAVLNODECORE) KAVL_FN(GetBestFit)(PPKAVLNODECORE ppTree, KAVLKEY Key, bool fAbove)
  45 {
  46     register PKAVLNODECORE  pNode = KAVL_GET_POINTER_NULL(ppTree);
  47     if (pNode)
  48     {
  49         PKAVLNODECORE           pNodeLast = NULL;
  50         if (fAbove)
  51         {   /* pNode->Key >= Key */
  52             while (KAVL_NE(pNode->Key, Key))
  53             {
  54                 if (KAVL_G(pNode->Key, Key))
  55                 {
  56                     if (pNode->pLeft != KAVL_NULL)
  57                     {
  58                         pNodeLast = pNode;
  59                         pNode = KAVL_GET_POINTER(&pNode->pLeft);
  60                     }
  61                     else
  62                         return pNode;
  63                 }
  64                 else
  65                 {
  66                     if (pNode->pRight != KAVL_NULL)
  67                         pNode = KAVL_GET_POINTER(&pNode->pRight);
  68                     else
  69                         return pNodeLast;
  70                 }
  71             }
  72         }
  73         else
  74         {   /* pNode->Key <= Key */
  75             while (KAVL_NE(pNode->Key, Key))
  76             {
  77                 if (KAVL_G(pNode->Key, Key))
  78                 {
  79                     if (pNode->pLeft != KAVL_NULL)
  80                         pNode = KAVL_GET_POINTER(&pNode->pLeft);
  81                     else
  82                         return pNodeLast;
  83                 }
  84                 else
  85                 {
  86                     if (pNode->pRight != KAVL_NULL)
  87                     {
  88                         pNodeLast = pNode;
  89                         pNode = KAVL_GET_POINTER(&pNode->pRight);
  90                     }
  91                     else
  92                         return pNode;
  93                 }
  94             }
  95         }
  96     }
  97
  98     /* perfect match or nothing. */
  99     return pNode;
 100 }
 101
 102
 103 #endif