avl_Base.cpp.h@ 331

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

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

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

Download in other formats: