hardavlrange.h@ 93671

Last change on this file since 93671 was 93671, checked in by vboxsync, 3 years ago
IPRT/hardavl: Initial adaption of the old AVL code into something a little more sturdy and suitable for manging data shared between kernel and user space. Needs more testing and possibly more use of 'volatile'. bugref:10093
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 38.1 KB

Line
1	/** @file
2	* IPRT - Hardened AVL tree, unique key ranges.
3	*/
4
5	/*
6	* Copyright (C) 2022 Oracle Corporation
7	*
8	* This file is part of VirtualBox Open Source Edition (OSE), as
9	* available from http://www.virtualbox.org. This file is free software;
10	* you can redistribute it and/or modify it under the terms of the GNU
11	* General Public License (GPL) as published by the Free Software
12	* Foundation, in version 2 as it comes in the "COPYING" file of the
13	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
14	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
15	*
16	* The contents of this file may alternatively be used under the terms
17	* of the Common Development and Distribution License Version 1.0
18	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
19	* VirtualBox OSE distribution, in which case the provisions of the
20	* CDDL are applicable instead of those of the GPL.
21	*
22	* You may elect to license modified versions of this file under the
23	* terms and conditions of either the GPL or the CDDL or both.
24	*/
25
26	#ifndef IPRT_INCLUDED_cpp_hardavlrange_h
27	#define IPRT_INCLUDED_cpp_hardavlrange_h
28	#ifndef RT_WITHOUT_PRAGMA_ONCE
29	# pragma once
30	#endif
31
32	#include <iprt/cpp/hardavlslaballocator.h>
33
34	/** @defgroup grp_rt_cpp_hardavl Hardened AVL Trees
35	* @{
36	*/
37
38	/**
39	* Hardened AVL tree for nodes with key ranges.
40	*
41	* This is very crude and therefore expects the NodeType to feature:
42	* - Key and KeyLast members of KeyType.
43	* - idxLeft and idxRight members with type uint32_t.
44	* - cHeight members of type uint8_t.
45	*
46	* The code is very C-ish because of it's sources and initial use (ring-0
47	* without C++ exceptions enabled).
48	*/
49	template<typename NodeType, typename KeyType>
50	struct RTCHardAvlRangeTree
51	{
52	/** The root index. */
53	uint32_t m_idxRoot;
54	/** The error count. */
55	uint32_t m_cErrors;
56
57	/** The max stack depth. */
58	enum { kMaxStack = 28 };
59	/** The max height value we allow. */
60	enum { kMaxHeight = kMaxStack + 1 };
61
62	/** A stack used internally to avoid recursive calls.
63	* This is used with operations invoking i_rebalance(). */
64	typedef struct HardAvlStack
65	{
66	/** Number of entries on the stack. */
67	unsigned cEntries;
68	/** The stack. */
69	uint32_t *apidxEntries[kMaxStack];
70	} HardAvlStack;
71
72	/** @name Key comparisons
73	* @{ */
74	static inline int areKeyRangesIntersecting(KeyType a_Key1First, KeyType a_Key2First,
75	KeyType a_Key1Last, KeyType a_Key2Last) RT_NOEXCEPT
76	{
77	return a_Key1First <= a_Key2Last && a_Key1Last >= a_Key2First;
78	}
79
80	static inline int isKeyInRange(KeyType a_Key, KeyType a_KeyFirst, KeyType a_KeyLast) RT_NOEXCEPT
81	{
82	return a_Key <= a_KeyLast && a_Key >= a_KeyFirst;
83	}
84
85	static inline int isKeyGreater(KeyType a_Key1, KeyType a_Key2) RT_NOEXCEPT
86	{
87	return a_Key1 > a_Key2;
88	}
89	/** @} */
90
91	RTCHardAvlRangeTree()
92	: m_idxRoot(0)
93	, m_cErrors(0)
94	{ }
95
96	RTCHardAvlRangeTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator)
97	: m_idxRoot(a_pAllocator->kNilIndex)
98	, m_cErrors(0)
99	{ }
100
101	/**
102	* Inserts a node into the AVL-tree.
103	*
104	* @returns IPRT status code.
105	* @retval VERR_ALREADY_EXISTS if a node with overlapping key range exists.
106	*
107	* @param a_pAllocator Pointer to the allocator.
108	* @param a_pNode Pointer to the node which is to be added.
109	*
110	* @code
111	* Find the location of the node (using binary tree algorithm.):
112	* LOOP until KAVL_NULL leaf pointer
113	* BEGIN
114	* Add node pointer pointer to the AVL-stack.
115	* IF new-node-key < node key THEN
116	* left
117	* ELSE
118	* right
119	* END
120	* Fill in leaf node and insert it.
121	* Rebalance the tree.
122	* @endcode
123	*/
124	int insert(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, NodeType a_pNode)
125	{
126	KeyType const Key = a_pNode->Key;
127	KeyType const KeyLast = a_pNode->KeyLast;
128	AssertMsgReturn(Key <= KeyLast, ("Key=%#RX64 KeyLast=%#RX64\n", (uint64_t)Key, (uint64_t)KeyLast),
129	VERR_HARDAVL_INSERT_INVALID_KEY_RANGE);
130
131	uint32_t *pidxCurNode = &m_idxRoot;
132	HardAvlStack AVLStack;
133	AVLStack.cEntries = 0;
134	for (;;)
135	{
136	NodeType pCurNode = a_pAllocator->ptrFromInt(pidxCurNode);
137	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pCurNode), ("pidxCurNode=%#x pCurNode=%p\n", pidxCurNode, pCurNode),
138	m_cErrors++, a_pAllocator->ptrErrToStatus(pCurNode));
139	if (!pCurNode)
140	break;
141
142	unsigned const cEntries = AVLStack.cEntries;
143	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
144	("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n", pidxCurNode, *pidxCurNode, pCurNode,
145	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
146	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
147	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3],
148	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4],
149	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
150	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
151	AVLStack.apidxEntries[cEntries] = pidxCurNode;
152	AVLStack.cEntries = cEntries + 1;
153
154	/* Range check: */
155	if (areKeyRangesIntersecting(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
156	return VERR_ALREADY_EXISTS;
157
158	/* Descend: */
159	if (isKeyGreater(pCurNode->Key, Key))
160	pidxCurNode = &pCurNode->idxLeft;
161	else
162	pidxCurNode = &pCurNode->idxRight;
163	}
164
165	a_pNode->idxLeft = a_pAllocator->kNilIndex;
166	a_pNode->idxRight = a_pAllocator->kNilIndex;
167	a_pNode->cHeight = 1;
168
169	uint32_t const idxNode = a_pAllocator->ptrToInt(a_pNode);
170	AssertMsgReturn(a_pAllocator->isIdxRetOkay(idxNode), ("pNode=%p idxNode=%#x\n", a_pNode, idxNode),
171	a_pAllocator->idxErrToStatus(idxNode));
172	*pidxCurNode = idxNode;
173
174	return i_rebalance(a_pAllocator, &AVLStack);
175	}
176
177	/**
178	* Removes a node from the AVL-tree by a key value.
179	*
180	* @returns IPRT status code.
181	* @retval VERR_NOT_FOUND if not found.
182	* @param a_pAllocator Pointer to the allocator.
183	* @param a_Key A key value in the range of the node to be removed.
184	* @param a_ppRemoved Where to return the pointer to the removed node.
185	*
186	* @code
187	* Find the node which is to be removed:
188	* LOOP until not found
189	* BEGIN
190	* Add node pointer pointer to the AVL-stack.
191	* IF the keys matches THEN break!
192	* IF remove key < node key THEN
193	* left
194	* ELSE
195	* right
196	* END
197	* IF found THEN
198	* BEGIN
199	* IF left node not empty THEN
200	* BEGIN
201	* Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
202	* Start at left node.
203	* LOOP until right node is empty
204	* BEGIN
205	* Add to stack.
206	* go right.
207	* END
208	* Link out the found node.
209	* Replace the node which is to be removed with the found node.
210	* Correct the stack entry for the pointer to the left tree.
211	* END
212	* ELSE
213	* BEGIN
214	* Move up right node.
215	* Remove last stack entry.
216	* END
217	* Balance tree using stack.
218	* END
219	* return pointer to the removed node (if found).
220	* @endcode
221	*/
222	int remove(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, KeyType a_Key, NodeType *a_ppRemoved)
223	{
224	*a_ppRemoved = NULL;
225
226	/*
227	* Walk the tree till we locate the node that is to be deleted.
228	*/
229	uint32_t *pidxDeleteNode = &m_idxRoot;
230	NodeType *pDeleteNode;
231	HardAvlStack AVLStack;
232	AVLStack.cEntries = 0;
233	for (;;)
234	{
235	pDeleteNode = a_pAllocator->ptrFromInt(*pidxDeleteNode);
236	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteNode),
237	("pidxCurNode=%#x pDeleteNode=%p\n", pidxDeleteNode, pDeleteNode),
238	m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteNode));
239	if (pDeleteNode)
240	{ /likely/ }
241	else
242	return VERR_NOT_FOUND;
243
244	unsigned const cEntries = AVLStack.cEntries;
245	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
246	("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n",
247	pidxDeleteNode, *pidxDeleteNode, pDeleteNode,
248	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
249	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
250	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3],
251	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4],
252	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
253	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
254	AVLStack.apidxEntries[cEntries] = pidxDeleteNode;
255	AVLStack.cEntries = cEntries + 1;
256
257	/* Range check: */
258	if (isKeyInRange(a_Key, pDeleteNode->Key, pDeleteNode->KeyLast))
259	break;
260
261	/* Descend: */
262	if (isKeyGreater(pDeleteNode->Key, a_Key))
263	pidxDeleteNode = &pDeleteNode->idxLeft;
264	else
265	pidxDeleteNode = &pDeleteNode->idxRight;
266	}
267
268	/*
269	* Do the deletion.
270	*/
271	if (pDeleteNode->idxLeft != a_pAllocator->kNilIndex)
272	{
273	/* find the rightmost node in the left tree. */
274	const unsigned iStackEntry = AVLStack.cEntries;
275	uint32_t *pidxLeftLeast = &pDeleteNode->idxLeft;
276	uint32_t idxLeftLeastNode = pDeleteNode->idxLeft;
277	NodeType *pLeftLeastNode = a_pAllocator->ptrFromInt(idxLeftLeastNode);
278	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeastNode),
279	("idxLeftLeastNode=%#x pLeftLeastNode=%p\n", idxLeftLeastNode, pLeftLeastNode),
280	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeastNode));
281
282	while (pLeftLeastNode->idxRight != a_pAllocator->kNilIndex)
283	{
284	unsigned const cEntries = AVLStack.cEntries;
285	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
286	("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n",
287	pidxDeleteNode, *pidxDeleteNode, pDeleteNode,
288	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
289	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
290	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3],
291	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4],
292	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
293	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
294	AVLStack.apidxEntries[cEntries] = pidxDeleteNode;
295	AVLStack.cEntries = cEntries + 1;
296
297	pidxLeftLeast = &pLeftLeastNode->idxRight;
298	idxLeftLeastNode = pLeftLeastNode->idxRight;
299	pLeftLeastNode = a_pAllocator->ptrFromInt(idxLeftLeastNode);
300	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeastNode),
301	("idxLeftLeastNode=%#x pLeftLeastNode=%p\n", idxLeftLeastNode, pLeftLeastNode),
302	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeastNode));
303	}
304
305	uint32_t const idxLeftLeastLeftNode = pLeftLeastNode->idxLeft;
306	AssertReturnStmt(a_pAllocator->isIntValid(idxLeftLeastLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
307
308	uint32_t const idxDeleteLeftNode = pDeleteNode->idxLeft;
309	AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
310	uint32_t const idxDeleteRightNode = pDeleteNode->idxRight;
311	AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
312
313	/* link out pLeftLeast */
314	*pidxLeftLeast = idxLeftLeastLeftNode;
315
316	/* link it in place of the delete node. */
317	pLeftLeastNode->idxLeft = idxDeleteLeftNode;
318	pLeftLeastNode->idxRight = idxDeleteRightNode;
319	pLeftLeastNode->cHeight = pDeleteNode->cHeight;
320	*pidxDeleteNode = idxLeftLeastNode;
321	AVLStack.apidxEntries[iStackEntry] = &pLeftLeastNode->idxLeft;
322	}
323	else
324	{
325	/* No left node, just pull up the right one. */
326	uint32_t const idxDeleteRightNode = pDeleteNode->idxRight;
327	AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
328	*pidxDeleteNode = idxDeleteRightNode;
329	AVLStack.cEntries--;
330	}
331	*a_ppRemoved = pDeleteNode;
332
333	return i_rebalance(a_pAllocator, &AVLStack);
334	}
335
336	/**
337	* Looks up a node from the tree.
338	*
339	* @returns IPRT status code.
340	* @retval VERR_NOT_FOUND if not found.
341	*
342	* @param a_pAllocator Pointer to the allocator.
343	* @param a_Key A key value in the range of the desired node.
344	* @param a_ppFound Where to return the pointer to the node.
345	*/
346	int lookup(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, KeyType a_Key, NodeType *a_ppFound)
347	{
348	*a_ppFound = NULL;
349
350	NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
351	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
352	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
353
354	unsigned cDepth = 0;
355	while (pNode)
356	{
357	AssertReturn(cDepth <= kMaxHeight, VERR_HARDAVL_LOOKUP_TOO_DEEP);
358	cDepth++;
359
360	if (isKeyInRange(a_Key, pNode->Key, pNode->KeyLast))
361	{
362	*a_ppFound = pNode;
363	return VINF_SUCCESS;
364	}
365	if (isKeyGreater(pNode->Key, a_Key))
366	{
367	uint32_t const idxLeft = pNode->idxLeft;
368	pNode = a_pAllocator->ptrFromInt(idxLeft);
369	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxLeft=%#x pNode=%p\n", idxLeft, pNode),
370	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
371	}
372	else
373	{
374	uint32_t const idxRight = pNode->idxRight;
375	pNode = a_pAllocator->ptrFromInt(idxRight);
376	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxRight=%#x pNode=%p\n", idxRight, pNode),
377	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
378	}
379	}
380
381	return VERR_NOT_FOUND;
382	}
383
384	/**
385	* A callback for doWithAllFromLeft and doWithAllFromRight.
386	*
387	* @returns IPRT status code. Any non-zero status causes immediate return from
388	* the enumeration function.
389	* @param pNode The current node.
390	* @param pvUser The user argument.
391	*/
392	typedef DECLCALLBACKTYPE(int, FNCALLBACK,(NodeType pNode, void pvUser));
393	/** Pointer to a callback for doWithAllFromLeft and doWithAllFromRight. */
394	typedef FNCALLBACK *PFNCALLBACK;
395
396	/**
397	* Iterates thru all nodes in the tree from left (smaller) to right.
398	*
399	* @returns IPRT status code.
400	*
401	* @param a_pAllocator Pointer to the allocator.
402	* @param a_pfnCallBack Pointer to callback function.
403	* @param a_pvUser Callback user argument.
404	*/
405	int doWithAllFromLeft(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, PFNCALLBACK a_pfnCallBack, void a_pvUser)
406	{
407	NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
408	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
409	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
410	if (!pNode)
411	return VINF_SUCCESS;
412
413	/*
414	* We simulate recursive calling here. For safety reasons, we do not
415	* pop before going down the right tree like the original code did.
416	*/
417	uint32_t cNodesLeft = a_pAllocator->m_cNodes;
418	NodeType *apEntries[kMaxStack];
419	uint8_t abState[kMaxStack];
420	unsigned cEntries = 1;
421	abState[0] = 0;
422	apEntries[0] = pNode;
423	while (cEntries > 0)
424	{
425	pNode = apEntries[cEntries - 1];
426	switch (abState[cEntries - 1])
427	{
428	/* Go left. */
429	case 0:
430	{
431	abState[cEntries - 1] = 1;
432
433	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(pNode->idxLeft);
434	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
435	("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
436	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
437	if (pLeftNode)
438	{
439	AssertCompile(kMaxStack > 6);
440	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
441	("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
442	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
443	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
444	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
445	apEntries[cEntries] = pLeftNode;
446	abState[cEntries] = 0;
447	cEntries++;
448
449	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
450	cNodesLeft--;
451	break;
452	}
453	RT_FALL_THROUGH();
454	}
455
456	/* center then right. */
457	case 1:
458	{
459	abState[cEntries - 1] = 2;
460
461	int rc = a_pfnCallBack(pNode, a_pvUser);
462	if (rc != VINF_SUCCESS)
463	return rc;
464
465	NodeType * const pRightNode = a_pAllocator->ptrFromInt(pNode->idxRight);
466	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
467	("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
468	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
469	if (pRightNode)
470	{
471	AssertCompile(kMaxStack > 6);
472	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
473	("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],
474	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
475	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
476	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
477	apEntries[cEntries] = pRightNode;
478	abState[cEntries] = 0;
479	cEntries++;
480
481	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
482	cNodesLeft--;
483	break;
484	}
485	RT_FALL_THROUGH();
486	}
487
488	default:
489	/* pop it. */
490	cEntries -= 1;
491	break;
492	}
493	}
494	return VINF_SUCCESS;
495	}
496
497	/**
498	* A callback for destroy to do additional cleanups before the node is freed.
499	*
500	* @param pNode The current node.
501	* @param pvUser The user argument.
502	*/
503	typedef DECLCALLBACKTYPE(void, FNDESTROYCALLBACK,(NodeType pNode, void pvUser));
504	/** Pointer to a callback for destroy. */
505	typedef FNDESTROYCALLBACK *PFNDESTROYCALLBACK;
506
507	/**
508	* Destroys the tree, starting with the root node.
509	*
510	* This will invoke the freeNode() method on the allocate for every node after
511	* first doing the callback to let the caller free additional resources
512	* referenced by the node.
513	*
514	* @returns IPRT status code.
515	*
516	* @param a_pAllocator Pointer to the allocator.
517	* @param a_pfnCallBack Pointer to callback function. Optional.
518	* @param a_pvUser Callback user argument.
519	*
520	* @note This is mostly the same code as the doWithAllFromLeft().
521	*/
522	int destroy(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, PFNDESTROYCALLBACK a_pfnCallBack = NULL, void a_pvUser = NULL)
523	{
524	NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
525	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
526	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
527	if (!pNode)
528	return VINF_SUCCESS;
529
530	/*
531	* We simulate recursive calling here. For safety reasons, we do not
532	* pop before going down the right tree like the original code did.
533	*/
534	uint32_t cNodesLeft = a_pAllocator->m_cNodes;
535	NodeType *apEntries[kMaxStack];
536	uint8_t abState[kMaxStack];
537	unsigned cEntries = 1;
538	abState[0] = 0;
539	apEntries[0] = pNode;
540	while (cEntries > 0)
541	{
542	pNode = apEntries[cEntries - 1];
543	switch (abState[cEntries - 1])
544	{
545	/* Go left. */
546	case 0:
547	{
548	abState[cEntries - 1] = 1;
549
550	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(pNode->idxLeft);
551	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
552	("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
553	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
554	if (pLeftNode)
555	{
556	AssertCompile(kMaxStack > 6);
557	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
558	("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
559	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
560	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
561	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
562	apEntries[cEntries] = pLeftNode;
563	abState[cEntries] = 0;
564	cEntries++;
565
566	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
567	cNodesLeft--;
568	break;
569	}
570	RT_FALL_THROUGH();
571	}
572
573	/* right. */
574	case 1:
575	{
576	abState[cEntries - 1] = 2;
577
578	NodeType * const pRightNode = a_pAllocator->ptrFromInt(pNode->idxRight);
579	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
580	("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
581	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
582	if (pRightNode)
583	{
584	AssertCompile(kMaxStack > 6);
585	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
586	("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],
587	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
588	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
589	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
590	apEntries[cEntries] = pRightNode;
591	abState[cEntries] = 0;
592	cEntries++;
593
594	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
595	cNodesLeft--;
596	break;
597	}
598	RT_FALL_THROUGH();
599	}
600
601	default:
602	{
603	/* pop it and destroy it. */
604	if (a_pfnCallBack)
605	a_pfnCallBack(pNode, a_pvUser);
606
607	int rc = a_pAllocator->freeNode(pNode);
608	AssertRCReturnStmt(rc, m_cErrors++, rc);
609
610	cEntries -= 1;
611	break;
612	}
613	}
614	}
615
616	Assert(m_idxRoot == a_pAllocator->kNilIndex);
617	return VINF_SUCCESS;
618	}
619
620	private:
621	/**
622	* Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
623	*
624	* @returns IPRT status code.
625	*
626	* @param a_pAllocator Pointer to the allocator.
627	* @param a_pStack Pointer to stack to rewind.
628	*
629	* @code
630	* LOOP thru all stack entries
631	* BEGIN
632	* Get pointer to pointer to node (and pointer to node) from the stack.
633	* IF 2 higher left subtree than in right subtree THEN
634	* BEGIN
635	* IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
636	* * n+2\|n+3
637	* / \ / \
638	* n+2 n ==> n+1 n+1\|n+2
639	* / \ / \
640	* n+1 n\|n+1 n\|n+1 n
641	*
642	* Or with keys:
643	*
644	* 4 2
645	* / \ / \
646	* 2 5 ==> 1 4
647	* / \ / \
648	* 1 3 3 5
649	*
650	* ELSE
651	* * n+2
652	* / \ / \
653	* n+2 n n+1 n+1
654	* / \ ==> / \ / \
655	* n n+1 n L R n
656	* / \
657	* L R
658	*
659	* Or with keys:
660	* 6 4
661	* / \ / \
662	* 2 7 ==> 2 6
663	* / \ / \ / \
664	* 1 4 1 3 5 7
665	* / \
666	* 3 5
667	* END
668	* ELSE IF 2 higher in right subtree than in left subtree THEN
669	* BEGIN
670	* Same as above but left <==> right. (invert the picture)
671	* ELSE
672	* IF correct height THEN break
673	* ELSE correct height.
674	* END
675	* @endcode
676	* @internal
677	*/
678	int i_rebalance(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, HardAvlStack a_pStack)
679	{
680	while (a_pStack->cEntries > 0)
681	{
682	/* pop */
683	uint32_t * const pidxNode = a_pStack->apidxEntries[--a_pStack->cEntries];
684	uint32_t const idxNode = *pidxNode;
685	NodeType * const pNode = a_pAllocator->ptrFromInt(idxNode);
686	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode),
687	("pidxNode=%p[%#x] pNode=%p\n", pidxNode, *pidxNode, pNode),
688	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
689
690	/* Read node properties: */
691	uint32_t const idxLeftNode = pNode->idxLeft;
692	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(idxLeftNode);
693	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
694	("idxLeftNode=%#x pLeftNode=%p\n", idxLeftNode, pLeftNode),
695	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
696
697	uint32_t const idxRightNode = pNode->idxRight;
698	NodeType * const pRightNode = a_pAllocator->ptrFromInt(idxRightNode);
699	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
700	("idxRight=%#x pRightNode=%p\n", idxRightNode, pRightNode),
701	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
702
703	uint8_t const cLeftHeight = pLeftNode ? pLeftNode->cHeight : 0;
704	AssertReturnStmt(cLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT);
705
706	uint8_t const cRightHeight = pRightNode ? pRightNode->cHeight : 0;
707	AssertReturnStmt(cRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT);
708
709	/* Decide what needs doing: */
710	if (cRightHeight + 1 < cLeftHeight)
711	{
712	AssertReturnStmt(pLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
713
714	uint32_t const idxLeftLeftNode = pLeftNode->idxLeft;
715	NodeType * const pLeftLeftNode = a_pAllocator->ptrFromInt(idxLeftLeftNode);
716	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeftNode),
717	("idxLeftLeftNode=%#x pLeftLeftNode=%p\n", idxLeftLeftNode, pLeftLeftNode),
718	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeftNode));
719
720	uint32_t const idxLeftRightNode = pLeftNode->idxRight;
721	NodeType * const pLeftRightNode = a_pAllocator->ptrFromInt(idxLeftRightNode);
722	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftRightNode),
723	("idxLeftRightNode=%#x pLeftRightNode=%p\n", idxLeftRightNode, pLeftRightNode),
724	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftRightNode));
725
726	uint8_t const cLeftRightHeight = pLeftRightNode ? pLeftRightNode->cHeight : 0;
727	if ((pLeftLeftNode ? pLeftLeftNode->cHeight : 0) >= cLeftRightHeight)
728	{
729	AssertReturnStmt(cLeftRightHeight + 2 <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
730	pNode->idxLeft = idxLeftRightNode;
731	pNode->cHeight = (uint8_t)(cLeftRightHeight + 1);
732	pLeftNode->cHeight = (uint8_t)(cLeftRightHeight + 2);
733	pLeftNode->idxRight = idxNode;
734	*pidxNode = idxLeftNode;
735	}
736	else
737	{
738	AssertReturnStmt(cLeftRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT);
739	AssertReturnStmt(pLeftRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
740
741	uint32_t const idxLeftRightLeftNode = pLeftRightNode->idxLeft;
742	AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
743	uint32_t const idxLeftRightRightNode = pLeftRightNode->idxRight;
744	AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
745	pLeftNode->idxRight = idxLeftRightLeftNode;
746	pNode->idxLeft = idxLeftRightRightNode;
747
748	pLeftRightNode->idxLeft = idxLeftNode;
749	pLeftRightNode->idxRight = idxNode;
750	pLeftNode->cHeight = cLeftRightHeight;
751	pNode->cHeight = cLeftRightHeight;
752	pLeftRightNode->cHeight = cLeftHeight;
753	*pidxNode = idxLeftRightNode;
754	}
755	}
756	else if (cLeftHeight + 1 < cRightHeight)
757	{
758	AssertReturnStmt(pRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
759
760	uint32_t const idxRightLeftNode = pRightNode->idxLeft;
761	NodeType * const pRightLeftNode = a_pAllocator->ptrFromInt(idxRightLeftNode);
762	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightLeftNode),
763	("idxRightLeftNode=%#x pRightLeftNode=%p\n", idxRightLeftNode, pRightLeftNode),
764	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightLeftNode));
765
766	uint32_t const idxRightRightNode = pRightNode->idxRight;
767	NodeType * const pRightRightNode = a_pAllocator->ptrFromInt(idxRightRightNode);
768	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightRightNode),
769	("idxRightRightNode=%#x pRightRightNode=%p\n", idxRightRightNode, pRightRightNode),
770	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightRightNode));
771
772	uint8_t const cRightLeftHeight = pRightLeftNode ? pRightLeftNode->cHeight : 0;
773	if ((pRightRightNode ? pRightRightNode->cHeight : 0) >= cRightLeftHeight)
774	{
775	AssertReturnStmt(cRightLeftHeight + 2 <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
776
777	pNode->idxRight = idxRightLeftNode;
778	pRightNode->idxLeft = idxNode;
779	pNode->cHeight = (uint8_t)(cRightLeftHeight + 1);
780	pRightNode->cHeight = (uint8_t)(cRightLeftHeight + 2);
781	*pidxNode = idxRightNode;
782	}
783	else
784	{
785	AssertReturnStmt(cRightLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT);
786	AssertReturnStmt(pRightLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
787
788	uint32_t const idxRightLeftRightNode = pRightLeftNode->idxRight;
789	AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
790	uint32_t const idxRightLeftLeftNode = pRightLeftNode->idxLeft;
791	AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
792	pRightNode->idxLeft = idxRightLeftRightNode;
793	pNode->idxRight = idxRightLeftLeftNode;
794	pRightLeftNode->idxRight = idxRightNode;
795	pRightLeftNode->idxLeft = idxNode;
796	pRightNode->cHeight = cRightLeftHeight;
797	pNode->cHeight = cRightLeftHeight;
798	pRightLeftNode->cHeight = cRightHeight;
799	*pidxNode = idxRightLeftNode;
800	}
801	}
802	else
803	{
804	uint8_t const cHeight = (uint8_t)(RT_MAX(cLeftHeight, cRightHeight) + 1);
805	AssertReturnStmt(cHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
806	if (cHeight == pNode->cHeight)
807	break;
808	pNode->cHeight = cHeight;
809	}
810	}
811	return VINF_SUCCESS;
812	}
813	};
814
815	/** @} */
816
817	#endif /* !IPRT_INCLUDED_cpp_hardavlrange_h */
818

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

source: vbox/trunk/include/iprt/cpp/hardavlrange.h@ 93671

Download in other formats: