avl_Base.cpp.h@ 3680

Last change on this file since 3680 was 407, checked in by vboxsync, 18 years ago
Another try...
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 16.2 KB

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

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

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

Download in other formats: