1 /* $Id: avl_DoWithAll.cpp.h $ */
3 * kAVLDoWithAll - Do with all nodes routine for AVL trees.
7 * Copyright (C) 1999-2011 knut st. osmundsen (bird-src-spam@anduin.net)
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 _kAVLDoWithAll_h_
28 #define _kAVLDoWithAll_h_
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.
40 KAVL_DECL(int) KAVL_FN(DoWithAll
)(PPKAVLNODECORE ppTree
, int fFromLeft
, PKAVLCALLBACK pfnCallBack
, void * pvParam
)
44 #ifdef KAVL_EQUAL_ALLOWED
49 if (*ppTree
== KAVL_NULL
)
52 AVLStack
.cEntries
= 1;
53 AVLStack
.achFlags
[0] = 0;
54 AVLStack
.aEntries
[0] = KAVL_GET_POINTER(ppTree
);
58 while (AVLStack
.cEntries
> 0)
60 pNode
= AVLStack
.aEntries
[AVLStack
.cEntries
- 1];
63 if (!AVLStack
.achFlags
[AVLStack
.cEntries
- 1]++)
65 if (pNode
->pLeft
!= KAVL_NULL
)
67 AVLStack
.achFlags
[AVLStack
.cEntries
] = 0; /* 0 first, 1 last */
68 AVLStack
.aEntries
[AVLStack
.cEntries
++] = KAVL_GET_POINTER(&pNode
->pLeft
);
74 rc
= pfnCallBack(pNode
, pvParam
);
75 if (rc
!= VINF_SUCCESS
)
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
))
81 rc
= pfnCallBack(pEqual
, pvParam
);
82 if (rc
!= VINF_SUCCESS
)
89 if (pNode
->pRight
!= KAVL_NULL
)
91 AVLStack
.achFlags
[AVLStack
.cEntries
] = 0;
92 AVLStack
.aEntries
[AVLStack
.cEntries
++] = KAVL_GET_POINTER(&pNode
->pRight
);
98 while (AVLStack
.cEntries
> 0)
100 pNode
= AVLStack
.aEntries
[AVLStack
.cEntries
- 1];
103 if (!AVLStack
.achFlags
[AVLStack
.cEntries
- 1]++)
105 if (pNode
->pRight
!= KAVL_NULL
)
107 AVLStack
.achFlags
[AVLStack
.cEntries
] = 0; /* 0 first, 1 last */
108 AVLStack
.aEntries
[AVLStack
.cEntries
++] = KAVL_GET_POINTER(&pNode
->pRight
);
114 rc
= pfnCallBack(pNode
, pvParam
);
115 if (rc
!= VINF_SUCCESS
)
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
))
121 rc
= pfnCallBack(pEqual
, pvParam
);
122 if (rc
!= VINF_SUCCESS
)
129 if (pNode
->pLeft
!= KAVL_NULL
)
131 AVLStack
.achFlags
[AVLStack
.cEntries
] = 0;
132 AVLStack
.aEntries
[AVLStack
.cEntries
++] = KAVL_GET_POINTER(&pNode
->pLeft
);