source: trunk/include/k/kAvlTmpl/kAvlBase.h@ 87

Last change on this file since 87 was 36, checked in by bird, 16 years ago

kAvlBase.h: Another typo in currently unused code.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
File size: 22.2 KB
Line 
1/* $Id: kAvlBase.h 36 2009-11-09 22:49:02Z bird $ */
2/** @file
3 * kAvlTmpl - Templated AVL Trees, The Mandatory Base Code.
4 */
5
6/*
7 * Copyright (c) 2001-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
8 *
9 * Permission is hereby granted, free of charge, to any person
10 * obtaining a copy of this software and associated documentation
11 * files (the "Software"), to deal in the Software without
12 * restriction, including without limitation the rights to use,
13 * copy, modify, merge, publish, distribute, sublicense, and/or sell
14 * copies of the Software, and to permit persons to whom the
15 * Software is furnished to do so, subject to the following
16 * conditions:
17 *
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
23 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
25 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
26 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
28 * OTHER DEALINGS IN THE SOFTWARE.
29 */
30
31/** @page pg_kAvlTmpl Template Configuration.
32 *
33 * This is a templated implementation of AVL trees in C. The template
34 * parameters relates to the kind of key used and how duplicates are
35 * treated.
36 *
37 * \#define KAVL_EQUAL_ALLOWED
38 * Define this to tell us that equal keys are allowed.
39 * Then Equal keys will be put in a list pointed to by KAVLNODE::pList.
40 * This is by default not defined.
41 *
42 * \#define KAVL_CHECK_FOR_EQUAL_INSERT
43 * Define this to enable insert check for equal nodes.
44 * This is by default not defined.
45 *
46 * \#define KAVL_MAX_STACK
47 * Use this to specify the max number of stack entries the stack will use when
48 * inserting and removing nodes from the tree. The size should be something like
49 * log2(<max nodes>) + 3
50 * Must be defined.
51 *
52 * \#define KAVL_RANGE
53 * Define this to enable key ranges.
54 *
55 * \#define KAVL_OFFSET
56 * Define this to link the tree together using self relative offset
57 * instead of memory pointers, thus making the entire tree relocatable
58 * provided all the nodes - including the root node variable - are moved
59 * the exact same distance.
60 *
61 * \#define KAVL_LOOKTHRU
62 * Define this to employ a lookthru cache (direct) to speed up lookup for
63 * some usage patterns. The value should be the number of members of the
64 * array.
65 *
66 * \#define KAVL_LOOKTHRU_HASH(Key)
67 * Define this to specify a more efficient translation of the key into
68 * a lookthru array index. The default is key % size.
69 * For some key types this is required as the default will not compile.
70 *
71 * \#define KAVL_LOCKED
72 * Define this if you wish for the tree to be locked via the
73 * KAVL_WRITE_LOCK, KAVL_WRITE_UNLOCK, KAVL_READ_LOCK and
74 * KAVL_READ_UNLOCK macros. If not defined the tree will not be subject
75 * do any kind of locking and the problem of concurrency is left the user.
76 *
77 * \#define KAVL_WRITE_LOCK(pRoot)
78 * Lock the tree for writing.
79 *
80 * \#define KAVL_WRITE_UNLOCK(pRoot)
81 * Counteracts KAVL_WRITE_LOCK.
82 *
83 * \#define KAVL_READ_LOCK(pRoot)
84 * Lock the tree for reading.
85 *
86 * \#define KAVL_READ_UNLOCK(pRoot)
87 * Counteracts KAVL_READ_LOCK.
88 *
89 * \#define KAVLKEY
90 * Define this to the name of the AVL key type.
91 *
92 * \#define KAVL_STD_KEY_COMP
93 * Define this to use the standard key compare macros. If not set all the
94 * compare operations for KAVLKEY have to be defined: KAVL_G, KAVL_E, KAVL_NE,
95 * KAVL_R_IS_IDENTICAL, KAVL_R_IS_INTERSECTING and KAVL_R_IS_IN_RANGE. The
96 * latter three are only required when KAVL_RANGE is defined.
97 *
98 * \#define KAVLNODE
99 * Define this to the name (typedef) of the AVL node structure. This
100 * structure must have a mpLeft, mpRight, mKey and mHeight member.
101 * If KAVL_RANGE is defined a mKeyLast is also required.
102 * If KAVL_EQUAL_ALLOWED is defined a mpList member is required.
103 * It's possible to use other member names by redefining the names.
104 *
105 * \#define KAVLTREEPTR
106 * Define this to the name (typedef) of the tree pointer type. This is
107 * required when KAVL_OFFSET is defined. When not defined it defaults
108 * to KAVLNODE *.
109 *
110 * \#define KAVLROOT
111 * Define this to the name (typedef) of the AVL root structure. This
112 * is optional. However, if specified it must at least have a mpRoot
113 * member of KAVLTREEPTR type. If KAVL_LOOKTHRU is non-zero a
114 * maLookthru[KAVL_LOOKTHRU] member of the KAVLTREEPTR type is also
115 * required.
116 *
117 * \#define KAVL_FN
118 * Use this to alter the names of the AVL functions.
119 * Must be defined.
120 *
121 * \#define KAVL_TYPE(prefix, name)
122 * Use this to make external type names and unique. The prefix may be empty.
123 * Must be defined.
124 *
125 * \#define KAVL_INT(name)
126 * Use this to make internal type names and unique. The prefix may be empty.
127 * Must be defined.
128 *
129 * \#define KAVL_DECL(rettype)
130 * Function declaration macro that should be set according to the scope
131 * the instantiated template should have. For instance an inlined scope
132 * (private or public) should K_DECL_INLINE(rettype) here.
133 *
134 * This version of the kAVL tree offers the option of inlining the entire
135 * implementation. This depends on the compiler doing a decent job in both
136 * making use of the inlined code and to eliminate const variables.
137 */
138
139
140/*******************************************************************************
141* Internal Functions *
142*******************************************************************************/
143#include <k/kDefs.h>
144#include <k/kTypes.h>
145#include <k/kHlpAssert.h>
146
147
148/*******************************************************************************
149* Defined Constants And Macros *
150*******************************************************************************/
151#define KAVL_HEIGHTOF(pNode) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
152
153/** @def KAVL_GET_POINTER
154 * Reads a 'pointer' value.
155 *
156 * @returns The native pointer.
157 * @param pp Pointer to the pointer to read.
158 * @internal
159 */
160
161/** @def KAVL_GET_POINTER_NULL
162 * Reads a 'pointer' value which can be KAVL_NULL.
163 *
164 * @returns The native pointer.
165 * @returns NULL pointer if KAVL_NULL.
166 * @param pp Pointer to the pointer to read.
167 * @internal
168 */
169
170/** @def KAVL_SET_POINTER
171 * Writes a 'pointer' value.
172 * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
173 *
174 * @returns stored pointer.
175 * @param pp Pointer to where to store the pointer.
176 * @param p Native pointer to assign to *pp.
177 * @internal
178 */
179
180/** @def KAVL_SET_POINTER_NULL
181 * Writes a 'pointer' value which can be KAVL_NULL.
182 *
183 * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
184 * if p is not KAVL_NULL of course.
185 *
186 * @returns stored pointer.
187 * @param pp Pointer to where to store the pointer.
188 * @param pp2 Pointer to where to pointer to assign to pp. This can be KAVL_NULL
189 * @internal
190 */
191
192#ifndef KAVLTREEPTR
193# define KAVLTREEPTR KAVLNODE *
194#endif
195
196#ifndef KAVLROOT
197# define KAVLROOT KAVL_TYPE(,ROOT)
198# define KAVL_NEED_KAVLROOT
199#endif
200
201#ifdef KAVL_LOOKTHRU
202# ifndef KAVL_LOOKTHRU_HASH
203# define KAVL_LOOKTHRU_HASH(Key) ( (Key) % (KAVL_LOOKTHRU) )
204# endif
205#elif defined(KAVL_LOOKTHRU_HASH)
206# error "KAVL_LOOKTHRU_HASH without KAVL_LOOKTHRU!"
207#endif
208
209#ifdef KAVL_LOOKTHRU
210# define KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, Key) \
211 do { \
212 KAVLTREEPTR **ppEntry = &pRoot->maLookthru[KAVL_LOOKTHRU_HASH(Key)]; \
213 if ((pNode) == KAVL_GET_POINTER_NULL(ppEntry)) \
214 *ppEntry = KAVL_NULL; \
215 } while (0)
216#else
217# define KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0)
218#endif
219
220#ifndef KAVL_LOCKED
221# define KAVL_WRITE_LOCK(pRoot) do { } while (0)
222# define KAVL_WRITE_UNLOCK(pRoot) do { } while (0)
223# define KAVL_READ_LOCK(pRoot) do { } while (0)
224# define KAVL_READ_UNLOCK(pRoot) do { } while (0)
225#endif
226
227#ifdef KAVL_OFFSET
228# define KAVL_GET_POINTER(pp) ( (KAVLNODE *)((KIPTR)(pp) + *(pp)) )
229# define KAVL_GET_POINTER_NULL(pp) ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
230# define KAVL_SET_POINTER(pp, p) ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
231# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KAVL_NULL ? (KIPTR)KAVL_GET_POINTER(pp2) - (KIPTR)(pp) : KAVL_NULL )
232#else
233# define KAVL_GET_POINTER(pp) ( *(pp) )
234# define KAVL_GET_POINTER_NULL(pp) ( *(pp) )
235# define KAVL_SET_POINTER(pp, p) ( (*(pp)) = (p) )
236# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) )
237#endif
238
239
240/** @def KAVL_NULL
241 * The NULL 'pointer' equivalent.
242 */
243#ifdef KAVL_OFFSET
244# define KAVL_NULL 0
245#else
246# define KAVL_NULL NULL
247#endif
248
249#ifdef KAVL_STD_KEY_COMP
250# define KAVL_G(key1, key2) ( (key1) > (key2) )
251# define KAVL_E(key1, key2) ( (key1) == (key2) )
252# define KAVL_NE(key1, key2) ( (key1) != (key2) )
253# ifdef KAVL_RANGE
254# define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
255# define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
256# define KAVL_R_IS_IN_RANGE(key1B, key1E, key2) KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
257# endif
258#endif
259
260#ifndef KAVL_RANGE
261# define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
262# define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
263#endif
264
265
266
267/*******************************************************************************
268* Structures and Typedefs *
269*******************************************************************************/
270/**
271 * Stack used to avoid recursive calls during insert and removal.
272 */
273typedef struct
274{
275 unsigned cEntries;
276 KAVLTREEPTR *aEntries[KAVL_MAX_STACK];
277} KAVL_INT(STACK);
278
279/**
280 * The callback used by the Destroy and DoWithAll functions.
281 */
282typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);
283
284#ifdef KAVL_NEED_KAVLROOT
285/**
286 * The AVL root structure.
287 */
288typedef struct
289{
290 KAVLTREEPTR mpRoot;
291# ifdef KAVL_LOOKTHRU
292 KAVLTREEPTR maLookthru[KAVL_LOOKTHRU];
293# endif
294} KAVLROOT;
295#endif
296
297
298/**
299 * Rewinds a stack of node pointer pointers, rebalancing the tree.
300 *
301 * @param pStack Pointer to stack to rewind.
302 * @sketch LOOP thru all stack entries
303 * BEGIN
304 * Get pointer to pointer to node (and pointer to node) from the stack.
305 * IF 2 higher left subtree than in right subtree THEN
306 * BEGIN
307 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
308 * * n+2|n+3
309 * / \ / \
310 * n+2 n ==> n+1 n+1|n+2
311 * / \ / \
312 * n+1 n|n+1 n|n+1 n
313 *
314 * Or with keys:
315 *
316 * 4 2
317 * / \ / \
318 * 2 5 ==> 1 4
319 * / \ / \
320 * 1 3 3 5
321 *
322 * ELSE
323 * * n+2
324 * / \ / \
325 * n+2 n n+1 n+1
326 * / \ ==> / \ / \
327 * n n+1 n L R n
328 * / \
329 * L R
330 *
331 * Or with keys:
332 * 6 4
333 * / \ / \
334 * 2 7 ==> 2 6
335 * / \ / \ / \
336 * 1 4 1 3 5 7
337 * / \
338 * 3 5
339 * END
340 * ELSE IF 2 higher in right subtree than in left subtree THEN
341 * BEGIN
342 * Same as above but left <==> right. (invert the picture)
343 * ELSE
344 * IF correct height THEN break
345 * ELSE correct height.
346 * END
347 */
348K_DECL_INLINE(void) KAVL_FN(Rebalance)(KAVL_INT(STACK) *pStack)
349{
350 while (pStack->cEntries > 0)
351 {
352 KAVLTREEPTR *ppNode = pStack->aEntries[--pStack->cEntries];
353 KAVLNODE *pNode = KAVL_GET_POINTER(ppNode);
354 KAVLNODE *pLeftNode = KAVL_GET_POINTER_NULL(&pNode->mpLeft);
355 KU8 uLeftHeight = KAVL_HEIGHTOF(pLeftNode);
356 KAVLNODE *pRightNode = KAVL_GET_POINTER_NULL(&pNode->mpRight);
357 KU8 uRightHeight = KAVL_HEIGHTOF(pRightNode);
358
359 if (uRightHeight + 1 < uLeftHeight)
360 {
361 KAVLNODE *pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpLeft);
362 KAVLNODE *pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpRight);
363 KU8 uLeftRightHeight = KAVL_HEIGHTOF(pLeftRightNode);
364
365 if (KAVL_HEIGHTOF(pLeftLeftNode) >= uLeftRightHeight)
366 {
367 KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftNode->mpRight);
368 KAVL_SET_POINTER(&pLeftNode->mpRight, pNode);
369 pLeftNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uLeftRightHeight)));
370 KAVL_SET_POINTER(ppNode, pLeftNode);
371 }
372 else
373 {
374 KAVL_SET_POINTER_NULL(&pLeftNode->mpRight, &pLeftRightNode->mpLeft);
375 KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftRightNode->mpRight);
376 KAVL_SET_POINTER(&pLeftRightNode->mpLeft, pLeftNode);
377 KAVL_SET_POINTER(&pLeftRightNode->mpRight, pNode);
378 pLeftNode->mHeight = pNode->mHeight = uLeftRightHeight;
379 pLeftRightNode->mHeight = uLeftHeight;
380 KAVL_SET_POINTER(ppNode, pLeftRightNode);
381 }
382 }
383 else if (uLeftHeight + 1 < uRightHeight)
384 {
385 KAVLNODE *pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->mpLeft);
386 KU8 uRightLeftHeight = KAVL_HEIGHTOF(pRightLeftNode);
387 KAVLNODE *pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->mpRight);
388
389 if (KAVL_HEIGHTOF(pRightRightNode) >= uRightLeftHeight)
390 {
391 KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightNode->mpLeft);
392 KAVL_SET_POINTER(&pRightNode->mpLeft, pNode);
393 pRightNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uRightLeftHeight)));
394 KAVL_SET_POINTER(ppNode, pRightNode);
395 }
396 else
397 {
398 KAVL_SET_POINTER_NULL(&pRightNode->mpLeft, &pRightLeftNode->mpRight);
399 KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightLeftNode->mpLeft);
400 KAVL_SET_POINTER(&pRightLeftNode->mpRight, pRightNode);
401 KAVL_SET_POINTER(&pRightLeftNode->mpLeft, pNode);
402 pRightNode->mHeight = pNode->mHeight = uRightLeftHeight;
403 pRightLeftNode->mHeight = uRightHeight;
404 KAVL_SET_POINTER(ppNode, pRightLeftNode);
405 }
406 }
407 else
408 {
409 KU8 uHeight = (KU8)(K_MAX(uLeftHeight, uRightHeight) + 1);
410 if (uHeight == pNode->mHeight)
411 break;
412 pNode->mHeight = uHeight;
413 }
414 }
415
416}
417
418
419/**
420 * Initializes the root of the AVL-tree.
421 *
422 * @param pTree Pointer to the root structure.
423 */
424KAVL_DECL(void) KAVL_FN(Init)(KAVLROOT *pRoot)
425{
426#ifdef KAVL_LOOKTHRU
427 unsigned i;
428#endif
429
430 pRoot->mpRoot = KAVL_NULL;
431#ifdef KAVL_LOOKTHRU
432 for (i = 0; i < (KAVL_LOOKTHRU); i++)
433 pRoot->maLookthru[i] = KAVL_NULL;
434#endif
435}
436
437
438/**
439 * Inserts a node into the AVL-tree.
440 * @returns K_TRUE if inserted.
441 * K_FALSE if node exists in tree.
442 * @param pRoot Pointer to the AVL-tree root structure.
443 * @param pNode Pointer to the node which is to be added.
444 * @sketch Find the location of the node (using binary tree algorithm.):
445 * LOOP until NULL leaf pointer
446 * BEGIN
447 * Add node pointer pointer to the AVL-stack.
448 * IF new-node-key < node key THEN
449 * left
450 * ELSE
451 * right
452 * END
453 * Fill in leaf node and insert it.
454 * Rebalance the tree.
455 */
456KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLROOT *pRoot, KAVLNODE *pNode)
457{
458 KAVL_INT(STACK) AVLStack;
459 KAVLTREEPTR *ppCurNode = &pRoot->mpRoot;
460 register KAVLKEY Key = pNode->mKey;
461#ifdef KAVL_RANGE
462 register KAVLKEY KeyLast = pNode->mKeyLast;
463#endif
464
465#ifdef KAVL_RANGE
466 if (Key > KeyLast)
467 return K_FALSE;
468#endif
469
470 KAVL_WRITE_LOCK(pRoot);
471
472 AVLStack.cEntries = 0;
473 while (*ppCurNode != KAVL_NULL)
474 {
475 register KAVLNODE *pCurNode = KAVL_GET_POINTER(ppCurNode);
476
477 kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
478 AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
479#ifdef KAVL_EQUAL_ALLOWED
480 if (KAVL_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
481 {
482 /*
483 * If equal then we'll use a list of equal nodes.
484 */
485 pNode->mpLeft = pNode->mpRight = KAVL_NULL;
486 pNode->mHeight = 0;
487 KAVL_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
488 KAVL_SET_POINTER(&pCurNode->mpList, pNode);
489 KAVL_WRITE_UNLOCK(pRoot);
490 return K_TRUE;
491 }
492#endif
493#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
494 if (KAVL_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
495 {
496 KAVL_WRITE_UNLOCK(pRoot);
497 return K_FALSE;
498 }
499#endif
500 if (KAVL_G(pCurNode->mKey, Key))
501 ppCurNode = &pCurNode->mpLeft;
502 else
503 ppCurNode = &pCurNode->mpRight;
504 }
505
506 pNode->mpLeft = pNode->mpRight = KAVL_NULL;
507#ifdef KAVL_EQUAL_ALLOWED
508 pNode->mpList = KAVL_NULL;
509#endif
510 pNode->mHeight = 1;
511 KAVL_SET_POINTER(ppCurNode, pNode);
512
513 KAVL_FN(Rebalance)(&AVLStack);
514
515 KAVL_WRITE_UNLOCK(pRoot);
516 return K_TRUE;
517}
518
519
520/**
521 * Removes a node from the AVL-tree.
522 * @returns Pointer to the node.
523 * @param pRoot Pointer to the AVL-tree root structure.
524 * @param Key Key value of the node which is to be removed.
525 * @sketch Find the node which is to be removed:
526 * LOOP until not found
527 * BEGIN
528 * Add node pointer pointer to the AVL-stack.
529 * IF the keys matches THEN break!
530 * IF remove key < node key THEN
531 * left
532 * ELSE
533 * right
534 * END
535 * IF found THEN
536 * BEGIN
537 * IF left node not empty THEN
538 * BEGIN
539 * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
540 * Start at left node.
541 * LOOP until right node is empty
542 * BEGIN
543 * Add to stack.
544 * go right.
545 * END
546 * Link out the found node.
547 * Replace the node which is to be removed with the found node.
548 * Correct the stack entry for the pointer to the left tree.
549 * END
550 * ELSE
551 * BEGIN
552 * Move up right node.
553 * Remove last stack entry.
554 * END
555 * Balance tree using stack.
556 * END
557 * return pointer to the removed node (if found).
558 */
559KAVL_DECL(KAVLNODE *) KAVL_FN(Remove)(KAVLROOT *pRoot, KAVLKEY Key)
560{
561 KAVL_INT(STACK) AVLStack;
562 KAVLTREEPTR *ppDeleteNode = &pRoot->mpRoot;
563 register KAVLNODE *pDeleteNode;
564
565 KAVL_WRITE_LOCK(pRoot);
566
567 AVLStack.cEntries = 0;
568 for (;;)
569 {
570 if (*ppDeleteNode == KAVL_NULL)
571 {
572 KAVL_WRITE_UNLOCK(pRoot);
573 return NULL;
574 }
575 pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
576
577 kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
578 AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
579 if (KAVL_E(pDeleteNode->mKey, Key))
580 break;
581
582 if (KAVL_G(pDeleteNode->mKey, Key))
583 ppDeleteNode = &pDeleteNode->mpLeft;
584 else
585 ppDeleteNode = &pDeleteNode->mpRight;
586 }
587
588 if (pDeleteNode->mpLeft != KAVL_NULL)
589 {
590 /* find the rightmost node in the left tree. */
591 const unsigned iStackEntry = AVLStack.cEntries;
592 KAVLTREEPTR *ppLeftLeast = &pDeleteNode->mpLeft;
593 register KAVLNODE *pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
594
595 while (pLeftLeast->mpRight != KAVL_NULL)
596 {
597 kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
598 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
599 ppLeftLeast = &pLeftLeast->mpRight;
600 pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
601 }
602
603 /* link out pLeftLeast */
604 KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
605
606 /* link it in place of the delete node. */
607 KAVL_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
608 KAVL_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
609 pLeftLeast->mHeight = pDeleteNode->mHeight;
610 KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
611 AVLStack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
612 }
613 else
614 {
615 KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
616 AVLStack.cEntries--;
617 }
618
619 KAVL_FN(Rebalance)(&AVLStack);
620
621 KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
622
623 KAVL_WRITE_UNLOCK(pRoot);
624 return pDeleteNode;
625}
626
Note: See TracBrowser for help on using the repository browser.