1 | /* $Id: avl_Base.cpp.h 8155 2008-04-18 15:16:47Z vboxsync $ */
|
---|
2 | /** @file
|
---|
3 | * kAVLBase - basic routines for all AVL trees.
|
---|
4 | */
|
---|
5 |
|
---|
6 | /*
|
---|
7 | * Copyright (C) 2001-2002 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 _kAVLBase_h_
|
---|
32 | #define _kAVLBase_h_
|
---|
33 |
|
---|
34 |
|
---|
35 | /** @page pg_rt_kAVL kAVL Template configuration.
|
---|
36 | * @internal
|
---|
37 | *
|
---|
38 | * This is a template made to implement multiple AVL trees. The differences
|
---|
39 | * among the implementations are related to the key used.
|
---|
40 | *
|
---|
41 | * \#define KAVL_FN
|
---|
42 | * Use this to alter the names of the AVL functions.
|
---|
43 | * Must be defined.
|
---|
44 | *
|
---|
45 | * \#define KAVL_EQUAL_ALLOWED
|
---|
46 | * Define this to tell us that equal keys are allowed.
|
---|
47 | * Then Equal keys will be put in a list pointed to by pList in the KAVLNODECORE.
|
---|
48 | * This is by default not defined.
|
---|
49 | *
|
---|
50 | * \#define KAVL_CHECK_FOR_EQUAL_INSERT
|
---|
51 | * Define this to enable insert check for equal nodes.
|
---|
52 | * This is by default not defined.
|
---|
53 | *
|
---|
54 | * \#define KAVL_MAX_STACK
|
---|
55 | * Use this to specify the number of stack entries the stack will use when inserting
|
---|
56 | * and removing nodes from the tree. I think the size should be about
|
---|
57 | * log2(<max nodes>) + 3
|
---|
58 | * Must be defined.
|
---|
59 | *
|
---|
60 | */
|
---|
61 |
|
---|
62 | /*******************************************************************************
|
---|
63 | * Defined Constants And Macros *
|
---|
64 | *******************************************************************************/
|
---|
65 | #define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
|
---|
66 |
|
---|
67 | /** @def KAVL_GET_POINTER
|
---|
68 | * Reads a 'pointer' value.
|
---|
69 | *
|
---|
70 | * @returns The native pointer.
|
---|
71 | * @param pp Pointer to the pointer to read.
|
---|
72 | */
|
---|
73 |
|
---|
74 | /** @def KAVL_GET_POINTER_NULL
|
---|
75 | * Reads a 'pointer' value which can be KAVL_NULL.
|
---|
76 | *
|
---|
77 | * @returns The native pointer.
|
---|
78 | * @returns NULL pointer if KAVL_NULL.
|
---|
79 | * @param pp Pointer to the pointer to read.
|
---|
80 | */
|
---|
81 |
|
---|
82 | /** @def KAVL_SET_POINTER
|
---|
83 | * Writes a 'pointer' value.
|
---|
84 | * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
|
---|
85 | *
|
---|
86 | * @returns stored pointer.
|
---|
87 | * @param pp Pointer to where to store the pointer.
|
---|
88 | * @param p Native pointer to assign to *pp.
|
---|
89 | */
|
---|
90 |
|
---|
91 | /** @def KAVL_SET_POINTER_NULL
|
---|
92 | * Writes a 'pointer' value which can be KAVL_NULL.
|
---|
93 | *
|
---|
94 | * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
|
---|
95 | * if p is not KAVL_NULL of course.
|
---|
96 | *
|
---|
97 | * @returns stored pointer.
|
---|
98 | * @param pp Pointer to where to store the pointer.
|
---|
99 | * @param pp2 Pointer to where to pointer to assign to pp. This can be KAVL_NULL
|
---|
100 | */
|
---|
101 |
|
---|
102 | #ifndef KAVL_GET_POINTER
|
---|
103 | # ifdef KAVL_OFFSET
|
---|
104 | # define KAVL_GET_POINTER(pp) ( (PKAVLNODECORE)((intptr_t)(pp) + *(pp)) )
|
---|
105 | # define KAVL_GET_POINTER_NULL(pp) ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
|
---|
106 | # define KAVL_SET_POINTER(pp, p) ( (*(pp)) = ((intptr_t)(p) - (intptr_t)(pp)) )
|
---|
107 | # define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KAVL_NULL ? (intptr_t)KAVL_GET_POINTER(pp2) - (intptr_t)(pp) : KAVL_NULL )
|
---|
108 | # else
|
---|
109 | # define KAVL_GET_POINTER(pp) ( *(pp) )
|
---|
110 | # define KAVL_GET_POINTER_NULL(pp) ( *(pp) )
|
---|
111 | # define KAVL_SET_POINTER(pp, p) ( (*(pp)) = (p) )
|
---|
112 | # define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) )
|
---|
113 | # endif
|
---|
114 | #endif
|
---|
115 |
|
---|
116 |
|
---|
117 | /** @def KAVL_NULL
|
---|
118 | * The NULL 'pointer' equivalent.
|
---|
119 | */
|
---|
120 | #ifndef KAVL_NULL
|
---|
121 | # ifdef KAVL_OFFSET
|
---|
122 | # define KAVL_NULL 0
|
---|
123 | # else
|
---|
124 | # define KAVL_NULL NULL
|
---|
125 | # endif
|
---|
126 | #endif
|
---|
127 |
|
---|
128 | #ifndef KAVL_RANGE
|
---|
129 | # define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
|
---|
130 | # define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
|
---|
131 | #endif
|
---|
132 |
|
---|
133 |
|
---|
134 |
|
---|
135 | /*******************************************************************************
|
---|
136 | * Structures and Typedefs *
|
---|
137 | *******************************************************************************/
|
---|
138 | /*
|
---|
139 | * A stack used to avoid recursive calls...
|
---|
140 | */
|
---|
141 | typedef struct _kAvlStack
|
---|
142 | {
|
---|
143 | unsigned cEntries;
|
---|
144 | PPKAVLNODECORE aEntries[KAVL_MAX_STACK];
|
---|
145 | } KAVLSTACK, *PKAVLSTACK;
|
---|
146 |
|
---|
147 | typedef struct _kAvlStack2
|
---|
148 | {
|
---|
149 | unsigned cEntries;
|
---|
150 | PKAVLNODECORE aEntries[KAVL_MAX_STACK];
|
---|
151 | char achFlags[KAVL_MAX_STACK];
|
---|
152 | } KAVLSTACK2, *PLAVLSTACK2;
|
---|
153 |
|
---|
154 |
|
---|
155 |
|
---|
156 | /**
|
---|
157 | * Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
|
---|
158 | * @param pStack Pointer to stack to rewind.
|
---|
159 | * @sketch LOOP thru all stack entries
|
---|
160 | * BEGIN
|
---|
161 | * Get pointer to pointer to node (and pointer to node) from the stack.
|
---|
162 | * IF 2 higher left subtree than in right subtree THEN
|
---|
163 | * BEGIN
|
---|
164 | * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
|
---|
165 | * * n+2|n+3
|
---|
166 | * / \ / \
|
---|
167 | * n+2 n ==> n+1 n+1|n+2
|
---|
168 | * / \ / \
|
---|
169 | * n+1 n|n+1 n|n+1 n
|
---|
170 | *
|
---|
171 | * Or with keys:
|
---|
172 | *
|
---|
173 | * 4 2
|
---|
174 | * / \ / \
|
---|
175 | * 2 5 ==> 1 4
|
---|
176 | * / \ / \
|
---|
177 | * 1 3 3 5
|
---|
178 | *
|
---|
179 | * ELSE
|
---|
180 | * * n+2
|
---|
181 | * / \ / \
|
---|
182 | * n+2 n n+1 n+1
|
---|
183 | * / \ ==> / \ / \
|
---|
184 | * n n+1 n L R n
|
---|
185 | * / \
|
---|
186 | * L R
|
---|
187 | *
|
---|
188 | * Or with keys:
|
---|
189 | * 6 4
|
---|
190 | * / \ / \
|
---|
191 | * 2 7 ==> 2 6
|
---|
192 | * / \ / \ / \
|
---|
193 | * 1 4 1 3 5 7
|
---|
194 | * / \
|
---|
195 | * 3 5
|
---|
196 | * END
|
---|
197 | * ELSE IF 2 higher in right subtree than in left subtree THEN
|
---|
198 | * BEGIN
|
---|
199 | * Same as above but left <==> right. (invert the picture)
|
---|
200 | * ELSE
|
---|
201 | * IF correct height THEN break
|
---|
202 | * ELSE correct height.
|
---|
203 | * END
|
---|
204 | */
|
---|
205 | DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack)
|
---|
206 | {
|
---|
207 | while (pStack->cEntries > 0)
|
---|
208 | {
|
---|
209 | /** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */
|
---|
210 | PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
|
---|
211 | PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode);
|
---|
212 | PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
|
---|
213 | unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
|
---|
214 | PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
|
---|
215 | unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
|
---|
216 |
|
---|
217 | if (uchRightHeight + 1 < uchLeftHeight)
|
---|
218 | {
|
---|
219 | PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
|
---|
220 | PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
|
---|
221 | unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
|
---|
222 |
|
---|
223 | if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
|
---|
224 | {
|
---|
225 | KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
|
---|
226 | KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
|
---|
227 | pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
|
---|
228 | KAVL_SET_POINTER(ppNode, pLeftNode);
|
---|
229 | }
|
---|
230 | else
|
---|
231 | {
|
---|
232 | KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
|
---|
233 | KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
|
---|
234 | KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
|
---|
235 | KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
|
---|
236 | pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
|
---|
237 | pLeftRightNode->uchHeight = uchLeftHeight;
|
---|
238 | KAVL_SET_POINTER(ppNode, pLeftRightNode);
|
---|
239 | }
|
---|
240 | }
|
---|
241 | else if (uchLeftHeight + 1 < uchRightHeight)
|
---|
242 | {
|
---|
243 | PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
|
---|
244 | unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
|
---|
245 | PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
|
---|
246 |
|
---|
247 | if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
|
---|
248 | {
|
---|
249 | KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
|
---|
250 | KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
|
---|
251 | pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
|
---|
252 | KAVL_SET_POINTER(ppNode, pRightNode);
|
---|
253 | }
|
---|
254 | else
|
---|
255 | {
|
---|
256 | KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
|
---|
257 | KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
|
---|
258 | KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
|
---|
259 | KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
|
---|
260 | pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
|
---|
261 | pRightLeftNode->uchHeight = uchRightHeight;
|
---|
262 | KAVL_SET_POINTER(ppNode, pRightLeftNode);
|
---|
263 | }
|
---|
264 | }
|
---|
265 | else
|
---|
266 | {
|
---|
267 | register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
|
---|
268 | if (uchHeight == pNode->uchHeight)
|
---|
269 | break;
|
---|
270 | pNode->uchHeight = uchHeight;
|
---|
271 | }
|
---|
272 | }
|
---|
273 |
|
---|
274 | }
|
---|
275 |
|
---|
276 |
|
---|
277 |
|
---|
278 |
|
---|
279 | /**
|
---|
280 | * Inserts a node into the AVL-tree.
|
---|
281 | * @returns TRUE if inserted.
|
---|
282 | * FALSE if node exists in tree.
|
---|
283 | * @param ppTree Pointer to the AVL-tree root node pointer.
|
---|
284 | * @param pNode Pointer to the node which is to be added.
|
---|
285 | * @sketch Find the location of the node (using binary tree algorithm.):
|
---|
286 | * LOOP until KAVL_NULL leaf pointer
|
---|
287 | * BEGIN
|
---|
288 | * Add node pointer pointer to the AVL-stack.
|
---|
289 | * IF new-node-key < node key THEN
|
---|
290 | * left
|
---|
291 | * ELSE
|
---|
292 | * right
|
---|
293 | * END
|
---|
294 | * Fill in leaf node and insert it.
|
---|
295 | * Rebalance the tree.
|
---|
296 | */
|
---|
297 | RTDECL(bool) KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
|
---|
298 | {
|
---|
299 | KAVLSTACK AVLStack;
|
---|
300 | PPKAVLNODECORE ppCurNode = ppTree;
|
---|
301 | register KAVLKEY Key = pNode->Key; NOREF(Key);
|
---|
302 | #ifdef KAVL_RANGE
|
---|
303 | register KAVLKEY KeyLast = pNode->KeyLast; NOREF(KeyLast);
|
---|
304 | #endif
|
---|
305 | register PKAVLNODECORE pCurNode;
|
---|
306 |
|
---|
307 | AVLStack.cEntries = 0;
|
---|
308 |
|
---|
309 | #ifdef KAVL_RANGE
|
---|
310 | if (Key > KeyLast)
|
---|
311 | return false;
|
---|
312 | #endif
|
---|
313 |
|
---|
314 | for (;;)
|
---|
315 | {
|
---|
316 | if (*ppCurNode != KAVL_NULL)
|
---|
317 | pCurNode = KAVL_GET_POINTER(ppCurNode);
|
---|
318 | else
|
---|
319 | break;
|
---|
320 |
|
---|
321 | kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
|
---|
322 | AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
|
---|
323 | #ifdef KAVL_EQUAL_ALLOWED
|
---|
324 | if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
|
---|
325 | {
|
---|
326 | /*
|
---|
327 | * If equal then we'll use a list of equal nodes.
|
---|
328 | */
|
---|
329 | pNode->pLeft = pNode->pRight = KAVL_NULL;
|
---|
330 | pNode->uchHeight = 0;
|
---|
331 | KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
|
---|
332 | KAVL_SET_POINTER(&pCurNode->pList, pNode);
|
---|
333 | return true;
|
---|
334 | }
|
---|
335 | #endif
|
---|
336 | #ifdef KAVL_CHECK_FOR_EQUAL_INSERT
|
---|
337 | if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
|
---|
338 | return false;
|
---|
339 | #endif
|
---|
340 | if (KAVL_G(pCurNode->Key, Key))
|
---|
341 | ppCurNode = &pCurNode->pLeft;
|
---|
342 | else
|
---|
343 | ppCurNode = &pCurNode->pRight;
|
---|
344 | }
|
---|
345 |
|
---|
346 | pNode->pLeft = pNode->pRight = KAVL_NULL;
|
---|
347 | #ifdef KAVL_EQUAL_ALLOWED
|
---|
348 | pNode->pList = KAVL_NULL;
|
---|
349 | #endif
|
---|
350 | pNode->uchHeight = 1;
|
---|
351 | KAVL_SET_POINTER(ppCurNode, pNode);
|
---|
352 |
|
---|
353 | KAVL_FN(Rebalance)(SSToDS(&AVLStack));
|
---|
354 | return true;
|
---|
355 | }
|
---|
356 |
|
---|
357 |
|
---|
358 | /**
|
---|
359 | * Removes a node from the AVL-tree.
|
---|
360 | * @returns Pointer to the node.
|
---|
361 | * @param ppTree Pointer to the AVL-tree root node pointer.
|
---|
362 | * @param Key Key value of the node which is to be removed.
|
---|
363 | * @sketch Find the node which is to be removed:
|
---|
364 | * LOOP until not found
|
---|
365 | * BEGIN
|
---|
366 | * Add node pointer pointer to the AVL-stack.
|
---|
367 | * IF the keys matches THEN break!
|
---|
368 | * IF remove key < node key THEN
|
---|
369 | * left
|
---|
370 | * ELSE
|
---|
371 | * right
|
---|
372 | * END
|
---|
373 | * IF found THEN
|
---|
374 | * BEGIN
|
---|
375 | * IF left node not empty THEN
|
---|
376 | * BEGIN
|
---|
377 | * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
|
---|
378 | * Start at left node.
|
---|
379 | * LOOP until right node is empty
|
---|
380 | * BEGIN
|
---|
381 | * Add to stack.
|
---|
382 | * go right.
|
---|
383 | * END
|
---|
384 | * Link out the found node.
|
---|
385 | * Replace the node which is to be removed with the found node.
|
---|
386 | * Correct the stack entry for the pointer to the left tree.
|
---|
387 | * END
|
---|
388 | * ELSE
|
---|
389 | * BEGIN
|
---|
390 | * Move up right node.
|
---|
391 | * Remove last stack entry.
|
---|
392 | * END
|
---|
393 | * Balance tree using stack.
|
---|
394 | * END
|
---|
395 | * return pointer to the removed node (if found).
|
---|
396 | */
|
---|
397 | RTDECL(PKAVLNODECORE) KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
|
---|
398 | {
|
---|
399 | KAVLSTACK AVLStack;
|
---|
400 | PPKAVLNODECORE ppDeleteNode = ppTree;
|
---|
401 | register PKAVLNODECORE pDeleteNode;
|
---|
402 |
|
---|
403 | AVLStack.cEntries = 0;
|
---|
404 |
|
---|
405 | for (;;)
|
---|
406 | {
|
---|
407 | if (*ppDeleteNode != KAVL_NULL)
|
---|
408 | pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
|
---|
409 | else
|
---|
410 | return NULL;
|
---|
411 |
|
---|
412 | kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
|
---|
413 | AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
|
---|
414 | if (KAVL_E(pDeleteNode->Key, Key))
|
---|
415 | break;
|
---|
416 |
|
---|
417 | if (KAVL_G(pDeleteNode->Key, Key))
|
---|
418 | ppDeleteNode = &pDeleteNode->pLeft;
|
---|
419 | else
|
---|
420 | ppDeleteNode = &pDeleteNode->pRight;
|
---|
421 | }
|
---|
422 |
|
---|
423 | if (pDeleteNode->pLeft != KAVL_NULL)
|
---|
424 | {
|
---|
425 | /* find the rightmost node in the left tree. */
|
---|
426 | const unsigned iStackEntry = AVLStack.cEntries;
|
---|
427 | PPKAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
|
---|
428 | register PKAVLNODECORE pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
|
---|
429 |
|
---|
430 | while (pLeftLeast->pRight != KAVL_NULL)
|
---|
431 | {
|
---|
432 | kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
|
---|
433 | AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
|
---|
434 | ppLeftLeast = &pLeftLeast->pRight;
|
---|
435 | pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
|
---|
436 | }
|
---|
437 |
|
---|
438 | /* link out pLeftLeast */
|
---|
439 | KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
|
---|
440 |
|
---|
441 | /* link it in place of the delete node. */
|
---|
442 | KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
|
---|
443 | KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
|
---|
444 | pLeftLeast->uchHeight = pDeleteNode->uchHeight;
|
---|
445 | KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
|
---|
446 | AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
|
---|
447 | }
|
---|
448 | else
|
---|
449 | {
|
---|
450 | KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
|
---|
451 | AVLStack.cEntries--;
|
---|
452 | }
|
---|
453 |
|
---|
454 | KAVL_FN(Rebalance)(SSToDS(&AVLStack));
|
---|
455 | return pDeleteNode;
|
---|
456 | }
|
---|
457 |
|
---|
458 | #endif
|
---|