avl_Base.cpp.h@ 8061

Last change on this file since 8061 was 5999, checked in by vboxsync, 17 years ago
The Giant CDDL Dual-License Header Change.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 16.5 KB

Line
1	/* $Id: avl_Base.cpp.h 5999 2007-12-07 15:05:06Z 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
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
130
131	/*******************************************************************************
132	* Structures and Typedefs *
133	*******************************************************************************/
134	/*
135	* A stack used to avoid recursive calls...
136	*/
137	typedef struct _kAvlStack
138	{
139	unsigned cEntries;
140	PPKAVLNODECORE aEntries[KAVL_MAX_STACK];
141	} KAVLSTACK, *PKAVLSTACK;
142
143	typedef struct _kAvlStack2
144	{
145	unsigned cEntries;
146	PKAVLNODECORE aEntries[KAVL_MAX_STACK];
147	char achFlags[KAVL_MAX_STACK];
148	} KAVLSTACK2, *PLAVLSTACK2;
149
150
151
152	/**
153	* Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
154	* @param pStack Pointer to stack to rewind.
155	* @sketch LOOP thru all stack entries
156	* BEGIN
157	* Get pointer to pointer to node (and pointer to node) from the stack.
158	* IF 2 higher left subtree than in right subtree THEN
159	* BEGIN
160	* IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
161	* * n+2\|n+3
162	* / \ / \
163	* n+2 n ==> n+1 n+1\|n+2
164	* / \ / \
165	* n+1 n\|n+1 n\|n+1 n
166	*
167	* Or with keys:
168	*
169	* 4 2
170	* / \ / \
171	* 2 5 ==> 1 4
172	* / \ / \
173	* 1 3 3 5
174	*
175	* ELSE
176	* * n+2
177	* / \ / \
178	* n+2 n n+1 n+1
179	* / \ ==> / \ / \
180	* n n+1 n L R n
181	* / \
182	* L R
183	*
184	* Or with keys:
185	* 6 4
186	* / \ / \
187	* 2 7 ==> 2 6
188	* / \ / \ / \
189	* 1 4 1 3 5 7
190	* / \
191	* 3 5
192	* END
193	* ELSE IF 2 higher in right subtree than in left subtree THEN
194	* BEGIN
195	* Same as above but left <==> right. (invert the picture)
196	* ELSE
197	* IF correct height THEN break
198	* ELSE correct height.
199	* END
200	*/
201	DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack)
202	{
203	while (pStack->cEntries > 0)
204	{
205	/** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */
206	PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
207	PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode);
208	PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
209	unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
210	PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
211	unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
212
213	if (uchRightHeight + 1 < uchLeftHeight)
214	{
215	PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
216	PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
217	unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
218
219	if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
220	{
221	KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
222	KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
223	pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
224	KAVL_SET_POINTER(ppNode, pLeftNode);
225	}
226	else
227	{
228	KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
229	KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
230	KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
231	KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
232	pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
233	pLeftRightNode->uchHeight = uchLeftHeight;
234	KAVL_SET_POINTER(ppNode, pLeftRightNode);
235	}
236	}
237	else if (uchLeftHeight + 1 < uchRightHeight)
238	{
239	PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
240	unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
241	PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
242
243	if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
244	{
245	KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
246	KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
247	pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
248	KAVL_SET_POINTER(ppNode, pRightNode);
249	}
250	else
251	{
252	KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
253	KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
254	KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
255	KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
256	pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
257	pRightLeftNode->uchHeight = uchRightHeight;
258	KAVL_SET_POINTER(ppNode, pRightLeftNode);
259	}
260	}
261	else
262	{
263	register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
264	if (uchHeight == pNode->uchHeight)
265	break;
266	pNode->uchHeight = uchHeight;
267	}
268	}
269
270	}
271
272
273
274
275	/**
276	* Inserts a node into the AVL-tree.
277	* @returns TRUE if inserted.
278	* FALSE if node exists in tree.
279	* @param ppTree Pointer to the AVL-tree root node pointer.
280	* @param pNode Pointer to the node which is to be added.
281	* @sketch Find the location of the node (using binary tree algorithm.):
282	* LOOP until KAVL_NULL leaf pointer
283	* BEGIN
284	* Add node pointer pointer to the AVL-stack.
285	* IF new-node-key < node key THEN
286	* left
287	* ELSE
288	* right
289	* END
290	* Fill in leaf node and insert it.
291	* Rebalance the tree.
292	*/
293	RTDECL(bool) KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
294	{
295	KAVLSTACK AVLStack;
296	PPKAVLNODECORE ppCurNode = ppTree;
297	register KAVLKEY Key = pNode->Key; NOREF(Key);
298	#ifdef KAVL_RANGE
299	register KAVLKEY KeyLast = pNode->KeyLast; NOREF(KeyLast);
300	#endif
301	register PKAVLNODECORE pCurNode;
302
303	AVLStack.cEntries = 0;
304
305	#ifdef KAVL_RANGE
306	if (Key > KeyLast)
307	return false;
308	#endif
309
310	for (;;)
311	{
312	if (*ppCurNode != KAVL_NULL)
313	pCurNode = KAVL_GET_POINTER(ppCurNode);
314	else
315	break;
316
317	kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
318	AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
319	#ifdef KAVL_EQUAL_ALLOWED
320	if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
321	{
322	/*
323	* If equal then we'll use a list of equal nodes.
324	*/
325	pNode->pLeft = pNode->pRight = KAVL_NULL;
326	pNode->uchHeight = 0;
327	KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
328	KAVL_SET_POINTER(&pCurNode->pList, pNode);
329	return true;
330	}
331	#endif
332	#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
333	if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
334	return false;
335	#endif
336	if (KAVL_G(pCurNode->Key, Key))
337	ppCurNode = &pCurNode->pLeft;
338	else
339	ppCurNode = &pCurNode->pRight;
340	}
341
342	pNode->pLeft = pNode->pRight = KAVL_NULL;
343	#ifdef KAVL_EQUAL_ALLOWED
344	pNode->pList = KAVL_NULL;
345	#endif
346	pNode->uchHeight = 1;
347	KAVL_SET_POINTER(ppCurNode, pNode);
348
349	KAVL_FN(Rebalance)(SSToDS(&AVLStack));
350	return true;
351	}
352
353
354	/**
355	* Removes a node from the AVL-tree.
356	* @returns Pointer to the node.
357	* @param ppTree Pointer to the AVL-tree root node pointer.
358	* @param Key Key value of the node which is to be removed.
359	* @sketch Find the node which is to be removed:
360	* LOOP until not found
361	* BEGIN
362	* Add node pointer pointer to the AVL-stack.
363	* IF the keys matches THEN break!
364	* IF remove key < node key THEN
365	* left
366	* ELSE
367	* right
368	* END
369	* IF found THEN
370	* BEGIN
371	* IF left node not empty THEN
372	* BEGIN
373	* Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
374	* Start at left node.
375	* LOOP until right node is empty
376	* BEGIN
377	* Add to stack.
378	* go right.
379	* END
380	* Link out the found node.
381	* Replace the node which is to be removed with the found node.
382	* Correct the stack entry for the pointer to the left tree.
383	* END
384	* ELSE
385	* BEGIN
386	* Move up right node.
387	* Remove last stack entry.
388	* END
389	* Balance tree using stack.
390	* END
391	* return pointer to the removed node (if found).
392	*/
393	RTDECL(PKAVLNODECORE) KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
394	{
395	KAVLSTACK AVLStack;
396	PPKAVLNODECORE ppDeleteNode = ppTree;
397	register PKAVLNODECORE pDeleteNode;
398
399	AVLStack.cEntries = 0;
400
401	for (;;)
402	{
403	if (*ppDeleteNode != KAVL_NULL)
404	pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
405	else
406	return NULL;
407
408	kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
409	AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
410	if (KAVL_E(pDeleteNode->Key, Key))
411	break;
412
413	if (KAVL_G(pDeleteNode->Key, Key))
414	ppDeleteNode = &pDeleteNode->pLeft;
415	else
416	ppDeleteNode = &pDeleteNode->pRight;
417	}
418
419	if (pDeleteNode->pLeft != KAVL_NULL)
420	{
421	/* find the rightmost node in the left tree. */
422	const unsigned iStackEntry = AVLStack.cEntries;
423	PPKAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
424	register PKAVLNODECORE pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
425
426	while (pLeftLeast->pRight != KAVL_NULL)
427	{
428	kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
429	AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
430	ppLeftLeast = &pLeftLeast->pRight;
431	pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
432	}
433
434	/* link out pLeftLeast */
435	KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
436
437	/* link it in place of the delete node. */
438	KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
439	KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
440	pLeftLeast->uchHeight = pDeleteNode->uchHeight;
441	KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
442	AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
443	}
444	else
445	{
446	KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
447	AVLStack.cEntries--;
448	}
449
450	KAVL_FN(Rebalance)(SSToDS(&AVLStack));
451	return pDeleteNode;
452	}
453
454	#endif

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

source: vbox/trunk/src/VBox/Runtime/common/table/avl_Base.cpp.h@ 8061

Download in other formats: