1 /* $Id: avl_Destroy.cpp.h $ */
3 * kAVLDestroy - Walk the tree calling a callback to destroy all the nodes.
7 * Copyright (C) 2006-2017 Oracle Corporation
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.
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.
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.
27 #ifndef _kAVLDestroy_h_
28 #define _kAVLDestroy_h_
32 * Destroys the specified tree, starting with the root node and working our way down.
34 * @returns 0 on success.
35 * @returns Return value from callback on failure. On failure, the tree will be in
36 * an unbalanced condition and only further calls to the Destroy should be
37 * made on it. Note that the node we fail on will be considered dead and
38 * no action is taken to link it back into the tree.
39 * @param ppTree Pointer to the AVL-tree root node pointer.
40 * @param pfnCallBack Pointer to callback function.
41 * @param pvUser User parameter passed on to the callback function.
43 KAVL_DECL(int) KAVL_FN(Destroy
)(PPKAVLNODECORE ppTree
, PKAVLCALLBACK pfnCallBack
, void *pvUser
)
46 PKAVLNODECORE apEntries
[KAVL_MAX_STACK
];
49 if (*ppTree
== KAVL_NULL
)
53 apEntries
[0] = KAVL_GET_POINTER(ppTree
);
57 * Process the subtrees first.
59 PKAVLNODECORE pNode
= apEntries
[cEntries
- 1];
60 if (pNode
->pLeft
!= KAVL_NULL
)
61 apEntries
[cEntries
++] = KAVL_GET_POINTER(&pNode
->pLeft
);
62 else if (pNode
->pRight
!= KAVL_NULL
)
63 apEntries
[cEntries
++] = KAVL_GET_POINTER(&pNode
->pRight
);
66 #ifdef KAVL_EQUAL_ALLOWED
68 * Process nodes with the same key.
70 while (pNode
->pList
!= KAVL_NULL
)
72 PKAVLNODECORE pEqual
= KAVL_GET_POINTER(&pNode
->pList
);
73 KAVL_SET_POINTER(&pNode
->pList
, KAVL_GET_POINTER_NULL(&pEqual
->pList
));
74 pEqual
->pList
= KAVL_NULL
;
76 rc
= pfnCallBack(pEqual
, pvUser
);
77 if (rc
!= VINF_SUCCESS
)
87 PKAVLNODECORE pParent
= apEntries
[cEntries
- 1];
88 if (KAVL_GET_POINTER(&pParent
->pLeft
) == pNode
)
89 pParent
->pLeft
= KAVL_NULL
;
91 pParent
->pRight
= KAVL_NULL
;
96 kASSERT(pNode
->pLeft
== KAVL_NULL
);
97 kASSERT(pNode
->pRight
== KAVL_NULL
);
98 rc
= pfnCallBack(pNode
, pvUser
);
99 if (rc
!= VINF_SUCCESS
)
104 kASSERT(*ppTree
== KAVL_NULL
);