Context Navigation

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

Last change on this file since 8 was 7, checked in by bird, 18 years ago
kAVL: Implemented locking, root node and a direct cache.
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 22.3 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: