VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/table/avl_DoWithAll.cpp.h@ 49788

Last change on this file since 49788 was 49788, checked in by vboxsync, 11 years ago

Runtime: AVL callback functions return an IPRT status code and so do RTAvl*DoWithAll() and RTAvl*Destroy()

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.7 KB
Line 
1/* $Id: avl_DoWithAll.cpp.h 49788 2013-12-05 12:39:28Z vboxsync $ */
2/** @file
3 * kAVLDoWithAll - Do with all nodes routine for AVL trees.
4 */
5
6/*
7 * Copyright (C) 1999-2011 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
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 */
40KAVL_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
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