kAvlBase.h

Last change on this file was 36, checked in by bird, 15 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	*/
273	typedef 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	*/
282	typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE , void );
283
284	#ifdef KAVL_NEED_KAVLROOT
285	/**
286	* The AVL root structure.
287	*/
288	typedef 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	*/
348	K_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	*/
424	KAVL_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	*/
456	KAVL_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	*/
559	KAVL_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.

source: kStuff/trunk/include/k/kAvlTmpl/kAvlBase.h

Download in other formats: