avl_Base.cpp.h@ 11523

Last change on this file since 11523 was 8155, checked in by vboxsync, 17 years ago
The Big Sun Rebranding Header Change
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 16.7 KB

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

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

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

Download in other formats: