VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/table/avl_RemoveNode.cpp.h@ 68246

Last change on this file since 68246 was 65892, checked in by vboxsync, 8 years ago

iprt: Simplify the AVL stuff by simply donating the version of the code used by VBox to Oracle.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.4 KB
Line 
1/* $Id: avl_RemoveNode.cpp.h 65892 2017-02-27 17:04:46Z vboxsync $ */
2/** @file
3 * kAVLRemove2 - Remove specific node (by pointer) from an AVL tree.
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
28/**
29 * Removes the specified node from the tree.
30 *
31 * @returns Pointer to the removed node (NULL if not in the tree)
32 * @param ppTree Pointer to the AVL-tree root structure.
33 * @param pNode Pointer to the node to be removed.
34 *
35 * @remark This implementation isn't the most efficient, but it's relatively
36 * short and easier to manage.
37 */
38KAVL_DECL(PKAVLNODECORE) KAVL_FN(RemoveNode)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
39{
40#ifdef KAVL_EQUAL_ALLOWED
41 /*
42 * Find the right node by key together with the parent node.
43 */
44 KAVLKEY const Key = pNode->Key;
45 PKAVLNODECORE pParent = NULL;
46 PKAVLNODECORE pCurNode = KAVL_GET_POINTER_NULL(ppTree);
47 if (!pCurNode)
48 return NULL;
49 while (KAVL_NE(pCurNode->Key, Key))
50 {
51 pParent = pCurNode;
52 if (KAVL_G(pCurNode->Key, Key))
53 {
54 if (pCurNode->pLeft != KAVL_NULL)
55 pCurNode = KAVL_GET_POINTER(&pCurNode->pLeft);
56 else
57 return NULL;
58 }
59 else
60 {
61 if (pCurNode->pRight != KAVL_NULL)
62 pCurNode = KAVL_GET_POINTER(&pCurNode->pRight);
63 else
64 return NULL;
65 }
66 }
67
68 if (pCurNode != pNode)
69 {
70 /*
71 * It's not the one we want, but it could be in the duplicate list.
72 */
73 while (pCurNode->pList != KAVL_NULL)
74 {
75 PKAVLNODECORE pNext = KAVL_GET_POINTER(&pCurNode->pList);
76 if (pNext == pNode)
77 {
78 if (pNode->pList != KAVL_NULL)
79 KAVL_SET_POINTER(&pCurNode->pList, KAVL_GET_POINTER(&pNode->pList));
80 else
81 pCurNode->pList = KAVL_NULL;
82 pNode->pList = KAVL_NULL;
83 return pNode;
84 }
85 pCurNode = pNext;
86 }
87 return NULL;
88 }
89
90 /*
91 * Ok, it's the one we want alright.
92 *
93 * Simply remove it if it's the only one with they Key, if there are
94 * duplicates we'll have to unlink it and insert the first duplicate
95 * in our place.
96 */
97 if (pNode->pList == KAVL_NULL)
98 KAVL_FN(Remove)(ppTree, pNode->Key);
99 else
100 {
101 PKAVLNODECORE pNewUs = KAVL_GET_POINTER(&pNode->pList);
102
103 pNewUs->uchHeight = pNode->uchHeight;
104
105 if (pNode->pLeft != KAVL_NULL)
106 KAVL_SET_POINTER(&pNewUs->pLeft, KAVL_GET_POINTER(&pNode->pLeft));
107 else
108 pNewUs->pLeft = KAVL_NULL;
109
110 if (pNode->pRight != KAVL_NULL)
111 KAVL_SET_POINTER(&pNewUs->pRight, KAVL_GET_POINTER(&pNode->pRight));
112 else
113 pNewUs->pRight = KAVL_NULL;
114
115 if (pParent)
116 {
117 if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
118 KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
119 else
120 KAVL_SET_POINTER(&pParent->pRight, pNewUs);
121 }
122 else
123 KAVL_SET_POINTER(ppTree, pNewUs);
124 }
125
126 return pNode;
127
128#else
129 /*
130 * Delete it, if we got the wrong one, reinsert it.
131 *
132 * This ASSUMS that the caller is NOT going to hand us a lot
133 * of wrong nodes but just uses this API for his convenience.
134 */
135 KAVLNODE *pRemovedNode = KAVL_FN(Remove)(pRoot, pNode->Key);
136 if (pRemovedNode == pNode)
137 return pRemovedNode;
138
139 KAVL_FN(Insert)(pRoot, pRemovedNode);
140 return NULL;
141#endif
142}
143
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