avl_Base.cpp.h@ 5422

Last change on this file since 5422 was 4071, checked in by vboxsync, 17 years ago
Biggest check-in ever. New source code headers for all (C) innotek files.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 16.0 KB

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

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

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

Download in other formats: