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

   1 /* $Id: avl_DoWithAll.cpp.h $ */
   2 /** @file
   3  * kAVLDoWithAll - Do with all nodes routine for AVL trees.
   4  */
   5
   6 /*
   7  * Copyright (C) 2006-2017 Oracle Corporation
   8  *
   9  * This file is part of VirtualBox Open Source Edition (OSE), as
  10  * available from http://www.virtualbox.org. This file is free software;
  11  * you can redistribute it and/or modify it under the terms of the GNU
  12  * General Public License (GPL) as published by the Free Software
  13  * Foundation, in version 2 as it comes in the "COPYING" file of the
  14  * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
  15  * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
  16  *
  17  * The contents of this file may alternatively be used under the terms
  18  * of the Common Development and Distribution License Version 1.0
  19  * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
  20  * VirtualBox OSE distribution, in which case the provisions of the
  21  * CDDL are applicable instead of those of the GPL.
  22  *
  23  * You may elect to license modified versions of this file under the
  24  * terms and conditions of either the GPL or the CDDL or both.
  25  */
  26
  27 #ifndef _kAVLDoWithAll_h_
  28 #define _kAVLDoWithAll_h_
  29
  30
  31 /**
  32  * Iterates thru all nodes in the given tree.
  33  * @returns   0 on success. Return from callback on failure.
  34  * @param     ppTree   Pointer to the AVL-tree root node pointer.
  35  * @param     fFromLeft    TRUE:  Left to right.
  36  *                         FALSE: Right to left.
  37  * @param     pfnCallBack  Pointer to callback function.
  38  * @param     pvParam      Userparameter passed on to the callback function.
  39  */
  40 KAVL_DECL(int) KAVL_FN(DoWithAll)(PPKAVLNODECORE ppTree, int fFromLeft, PKAVLCALLBACK pfnCallBack, void * pvParam)
  41 {
  42     KAVLSTACK2      AVLStack;
  43     PKAVLNODECORE   pNode;
  44 #ifdef KAVL_EQUAL_ALLOWED
  45     PKAVLNODECORE   pEqual;
  46 #endif
  47     int             rc;
  48
  49     if (*ppTree == KAVL_NULL)
  50         return VINF_SUCCESS;
  51
  52     AVLStack.cEntries = 1;
  53     AVLStack.achFlags[0] = 0;
  54     AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
  55
  56     if (fFromLeft)
  57     {   /* from left */
  58         while (AVLStack.cEntries > 0)
  59         {
  60             pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
  61
  62             /* left */
  63             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
  64             {
  65                 if (pNode->pLeft != KAVL_NULL)
  66                 {
  67                     AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
  68                     AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
  69                     continue;
  70                 }
  71             }
  72
  73             /* center */
  74             rc = pfnCallBack(pNode, pvParam);
  75             if (rc != VINF_SUCCESS)
  76                 return rc;
  77 #ifdef KAVL_EQUAL_ALLOWED
  78             if (pNode->pList != KAVL_NULL)
  79                 for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
  80                 {
  81                     rc = pfnCallBack(pEqual, pvParam);
  82                     if (rc != VINF_SUCCESS)
  83                         return rc;
  84                 }
  85 #endif
  86
  87             /* right */
  88             AVLStack.cEntries--;
  89             if (pNode->pRight != KAVL_NULL)
  90             {
  91                 AVLStack.achFlags[AVLStack.cEntries] = 0;
  92                 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
  93             }
  94         } /* while */
  95     }
  96     else
  97     {   /* from right */
  98         while (AVLStack.cEntries > 0)
  99         {
 100             pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
 101
 102             /* right */
 103             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
 104             {
 105                 if (pNode->pRight != KAVL_NULL)
 106                 {
 107                     AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
 108                     AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
 109                     continue;
 110                 }
 111             }
 112
 113             /* center */
 114             rc = pfnCallBack(pNode, pvParam);
 115             if (rc != VINF_SUCCESS)
 116                 return rc;
 117 #ifdef KAVL_EQUAL_ALLOWED
 118             if (pNode->pList != KAVL_NULL)
 119                 for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
 120                 {
 121                     rc = pfnCallBack(pEqual, pvParam);
 122                     if (rc != VINF_SUCCESS)
 123                         return rc;
 124                 }
 125 #endif
 126
 127             /* left */
 128             AVLStack.cEntries--;
 129             if (pNode->pLeft != KAVL_NULL)
 130             {
 131                 AVLStack.achFlags[AVLStack.cEntries] = 0;
 132                 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
 133             }
 134         } /* while */
 135     }
 136
 137     return VINF_SUCCESS;
 138 }
 139
 140
 141 #endif
 142