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