avl_Base.cpp.h@ 65817

Last change on this file since 65817 was 65208, checked in by vboxsync, 8 years ago
Runtime/AVL: fixed headers
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 16.8 KB

Line
1	/* $Id: avl_Base.cpp.h 65208 2017-01-09 14:39:54Z vboxsync $ */
2	/** @file
3	* kAVLBase - basic routines for all AVL trees.
4	*/
5
6	/*
7	* Copyright (C) 2001-2012 knut st. osmundsen ([email protected])
8	*
9	* Permission is hereby granted, free of charge, to any person
10	* obtaining a copy of this software and associated documentation
11	* files (the "Software"), to deal in the Software without
12	* restriction, including without limitation the rights to use,
13	* copy, modify, merge, publish, distribute, sublicense, and/or sell
14	* copies of the Software, and to permit persons to whom the
15	* Software is furnished to do so, subject to the following
16	* conditions:
17	*
18	* The above copyright notice and this permission notice shall be
19	* included in all copies or substantial portions of the Software.
20	*
21	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22	* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
23	* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24	* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
25	* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
26	* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
28	* OTHER DEALINGS IN THE SOFTWARE.
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	/** @def KAVL_DECL
134	* Function declation macro in the RTDECL tradition.
135	* @param a_Type The function return type. */
136	#ifndef KAVL_DECL
137	# define KAVL_DECL(a_Type) RTDECL(a_Type)
138	#endif
139
140
141	/*******************************************************************************
142	* Structures and Typedefs *
143	*******************************************************************************/
144	/*
145	* A stack used to avoid recursive calls...
146	*/
147	typedef struct _kAvlStack
148	{
149	unsigned cEntries;
150	PPKAVLNODECORE aEntries[KAVL_MAX_STACK];
151	} KAVLSTACK, *PKAVLSTACK;
152
153	typedef struct _kAvlStack2
154	{
155	unsigned cEntries;
156	PKAVLNODECORE aEntries[KAVL_MAX_STACK];
157	char achFlags[KAVL_MAX_STACK];
158	} KAVLSTACK2, *PLAVLSTACK2;
159
160
161
162	/**
163	* Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
164	* @param pStack Pointer to stack to rewind.
165	* @sketch LOOP thru all stack entries
166	* BEGIN
167	* Get pointer to pointer to node (and pointer to node) from the stack.
168	* IF 2 higher left subtree than in right subtree THEN
169	* BEGIN
170	* IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
171	* * n+2\|n+3
172	* / \ / \
173	* n+2 n ==> n+1 n+1\|n+2
174	* / \ / \
175	* n+1 n\|n+1 n\|n+1 n
176	*
177	* Or with keys:
178	*
179	* 4 2
180	* / \ / \
181	* 2 5 ==> 1 4
182	* / \ / \
183	* 1 3 3 5
184	*
185	* ELSE
186	* * n+2
187	* / \ / \
188	* n+2 n n+1 n+1
189	* / \ ==> / \ / \
190	* n n+1 n L R n
191	* / \
192	* L R
193	*
194	* Or with keys:
195	* 6 4
196	* / \ / \
197	* 2 7 ==> 2 6
198	* / \ / \ / \
199	* 1 4 1 3 5 7
200	* / \
201	* 3 5
202	* END
203	* ELSE IF 2 higher in right subtree than in left subtree THEN
204	* BEGIN
205	* Same as above but left <==> right. (invert the picture)
206	* ELSE
207	* IF correct height THEN break
208	* ELSE correct height.
209	* END
210	*/
211	DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack)
212	{
213	while (pStack->cEntries > 0)
214	{
215	/** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */
216	PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
217	PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode);
218	PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
219	unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
220	PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
221	unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
222
223	if (uchRightHeight + 1 < uchLeftHeight)
224	{
225	PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
226	PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
227	unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
228
229	if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
230	{
231	KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
232	KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
233	pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
234	KAVL_SET_POINTER(ppNode, pLeftNode);
235	}
236	else
237	{
238	KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
239	KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
240	KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
241	KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
242	pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
243	pLeftRightNode->uchHeight = uchLeftHeight;
244	KAVL_SET_POINTER(ppNode, pLeftRightNode);
245	}
246	}
247	else if (uchLeftHeight + 1 < uchRightHeight)
248	{
249	PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
250	unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
251	PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
252
253	if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
254	{
255	KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
256	KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
257	pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
258	KAVL_SET_POINTER(ppNode, pRightNode);
259	}
260	else
261	{
262	KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
263	KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
264	KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
265	KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
266	pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
267	pRightLeftNode->uchHeight = uchRightHeight;
268	KAVL_SET_POINTER(ppNode, pRightLeftNode);
269	}
270	}
271	else
272	{
273	register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
274	if (uchHeight == pNode->uchHeight)
275	break;
276	pNode->uchHeight = uchHeight;
277	}
278	}
279
280	}
281
282
283
284
285	/**
286	* Inserts a node into the AVL-tree.
287	* @returns TRUE if inserted.
288	* FALSE if node exists in tree.
289	* @param ppTree Pointer to the AVL-tree root node pointer.
290	* @param pNode Pointer to the node which is to be added.
291	* @sketch Find the location of the node (using binary tree algorithm.):
292	* LOOP until KAVL_NULL leaf pointer
293	* BEGIN
294	* Add node pointer pointer to the AVL-stack.
295	* IF new-node-key < node key THEN
296	* left
297	* ELSE
298	* right
299	* END
300	* Fill in leaf node and insert it.
301	* Rebalance the tree.
302	*/
303	KAVL_DECL(bool) KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
304	{
305	KAVLSTACK AVLStack;
306	PPKAVLNODECORE ppCurNode = ppTree;
307	register PKAVLNODECORE pCurNode;
308	register KAVLKEY Key = pNode->Key; NOREF(Key);
309	#ifdef KAVL_RANGE
310	register KAVLKEY KeyLast = pNode->KeyLast; NOREF(KeyLast);
311	#endif
312
313	AVLStack.cEntries = 0;
314
315	#ifdef KAVL_RANGE
316	if (Key > KeyLast)
317	return false;
318	#endif
319
320	for (;;)
321	{
322	if (*ppCurNode != KAVL_NULL)
323	pCurNode = KAVL_GET_POINTER(ppCurNode);
324	else
325	break;
326
327	kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
328	AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
329	#ifdef KAVL_EQUAL_ALLOWED
330	if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
331	{
332	/*
333	* If equal then we'll use a list of equal nodes.
334	*/
335	pNode->pLeft = pNode->pRight = KAVL_NULL;
336	pNode->uchHeight = 0;
337	KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
338	KAVL_SET_POINTER(&pCurNode->pList, pNode);
339	return true;
340	}
341	#endif
342	#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
343	if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
344	return false;
345	#endif
346	if (KAVL_G(pCurNode->Key, Key))
347	ppCurNode = &pCurNode->pLeft;
348	else
349	ppCurNode = &pCurNode->pRight;
350	}
351
352	pNode->pLeft = pNode->pRight = KAVL_NULL;
353	#ifdef KAVL_EQUAL_ALLOWED
354	pNode->pList = KAVL_NULL;
355	#endif
356	pNode->uchHeight = 1;
357	KAVL_SET_POINTER(ppCurNode, pNode);
358
359	KAVL_FN(Rebalance)(SSToDS(&AVLStack));
360	return true;
361	}
362
363
364	/**
365	* Removes a node from the AVL-tree.
366	* @returns Pointer to the node.
367	* @param ppTree Pointer to the AVL-tree root node pointer.
368	* @param Key Key value of the node which is to be removed.
369	* @sketch Find the node which is to be removed:
370	* LOOP until not found
371	* BEGIN
372	* Add node pointer pointer to the AVL-stack.
373	* IF the keys matches THEN break!
374	* IF remove key < node key THEN
375	* left
376	* ELSE
377	* right
378	* END
379	* IF found THEN
380	* BEGIN
381	* IF left node not empty THEN
382	* BEGIN
383	* Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
384	* Start at left node.
385	* LOOP until right node is empty
386	* BEGIN
387	* Add to stack.
388	* go right.
389	* END
390	* Link out the found node.
391	* Replace the node which is to be removed with the found node.
392	* Correct the stack entry for the pointer to the left tree.
393	* END
394	* ELSE
395	* BEGIN
396	* Move up right node.
397	* Remove last stack entry.
398	* END
399	* Balance tree using stack.
400	* END
401	* return pointer to the removed node (if found).
402	*/
403	KAVL_DECL(PKAVLNODECORE) KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
404	{
405	KAVLSTACK AVLStack;
406	PPKAVLNODECORE ppDeleteNode = ppTree;
407	register PKAVLNODECORE pDeleteNode;
408
409	AVLStack.cEntries = 0;
410
411	for (;;)
412	{
413	if (*ppDeleteNode != KAVL_NULL)
414	pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
415	else
416	return NULL;
417
418	kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
419	AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
420	if (KAVL_E(pDeleteNode->Key, Key))
421	break;
422
423	if (KAVL_G(pDeleteNode->Key, Key))
424	ppDeleteNode = &pDeleteNode->pLeft;
425	else
426	ppDeleteNode = &pDeleteNode->pRight;
427	}
428
429	if (pDeleteNode->pLeft != KAVL_NULL)
430	{
431	/* find the rightmost node in the left tree. */
432	const unsigned iStackEntry = AVLStack.cEntries;
433	PPKAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
434	register PKAVLNODECORE pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
435
436	while (pLeftLeast->pRight != KAVL_NULL)
437	{
438	kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
439	AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
440	ppLeftLeast = &pLeftLeast->pRight;
441	pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
442	}
443
444	/* link out pLeftLeast */
445	KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
446
447	/* link it in place of the delete node. */
448	KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
449	KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
450	pLeftLeast->uchHeight = pDeleteNode->uchHeight;
451	KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
452	AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
453	}
454	else
455	{
456	KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
457	AVLStack.cEntries--;
458	}
459
460	KAVL_FN(Rebalance)(SSToDS(&AVLStack));
461	return pDeleteNode;
462	}
463
464	#endif

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

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

Download in other formats: