VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/table/avl_Destroy.cpp.h@ 8155

Last change on this file since 8155 was 8155, checked in by vboxsync, 17 years ago

The Big Sun Rebranding Header Change

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 3.8 KB
Line 
1/* $Id: avl_Destroy.cpp.h 8155 2008-04-18 15:16:47Z vboxsync $ */
2/** @file
3 * kAVLDestroy - Walk the tree calling a callback to destroy all the nodes.
4 */
5
6/*
7 * Copyright (C) 1999-2007 knut st. osmundsen (bird-src-spam@anduin.net)
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 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27 * Clara, CA 95054 USA or visit http://www.sun.com if you need
28 * additional information or have any questions.
29 */
30
31#ifndef _kAVLDestroy_h_
32#define _kAVLDestroy_h_
33
34
35/**
36 * Destroys the specified tree, starting with the root node and working our way down.
37 *
38 * @returns 0 on success.
39 * @returns Return value from callback on failure. On failure, the tree will be in
40 * an unbalanced condition and only further calls to the Destroy should be
41 * made on it. Note that the node we fail on will be considered dead and
42 * no action is taken to link it back into the tree.
43 * @param ppTree Pointer to the AVL-tree root node pointer.
44 * @param pfnCallBack Pointer to callback function.
45 * @param pvUser User parameter passed on to the callback function.
46 */
47RTDECL(int) KAVL_FN(Destroy)(PPKAVLNODECORE ppTree, PKAVLCALLBACK pfnCallBack, void *pvUser)
48{
49 unsigned cEntries;
50 PKAVLNODECORE apEntries[KAVL_MAX_STACK];
51 int rc;
52
53 if (*ppTree == KAVL_NULL)
54 return 0;
55
56 cEntries = 1;
57 apEntries[0] = KAVL_GET_POINTER(ppTree);
58 while (cEntries > 0)
59 {
60 /*
61 * Process the subtrees first.
62 */
63 PKAVLNODECORE pNode = apEntries[cEntries - 1];
64 if (pNode->pLeft != KAVL_NULL)
65 apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
66 else if (pNode->pRight != KAVL_NULL)
67 apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
68 else
69 {
70#ifdef KAVL_EQUAL_ALLOWED
71 /*
72 * Process nodes with the same key.
73 */
74 while (pNode->pList != KAVL_NULL)
75 {
76 PKAVLNODECORE pEqual = KAVL_GET_POINTER(&pNode->pList);
77 KAVL_SET_POINTER(&pNode->pList, KAVL_GET_POINTER_NULL(&pEqual->pList));
78 pEqual->pList = KAVL_NULL;
79
80 rc = pfnCallBack(pEqual, pvUser);
81 if (rc)
82 return rc;
83 }
84#endif
85
86 /*
87 * Unlink the node.
88 */
89 if (--cEntries > 0)
90 {
91 PKAVLNODECORE pParent = apEntries[cEntries - 1];
92 if (KAVL_GET_POINTER(&pParent->pLeft) == pNode)
93 pParent->pLeft = KAVL_NULL;
94 else
95 pParent->pRight = KAVL_NULL;
96 }
97 else
98 *ppTree = KAVL_NULL;
99
100 kASSERT(pNode->pLeft == KAVL_NULL);
101 kASSERT(pNode->pRight == KAVL_NULL);
102 rc = pfnCallBack(pNode, pvUser);
103 if (rc)
104 return rc;
105 }
106 } /* while */
107
108 kASSERT(*ppTree == KAVL_NULL);
109
110 return 0;
111}
112
113#endif
114
115
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette