avl_Base.cpp.h@ 65892

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

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

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

Download in other formats: