hardavlrange.h@ 93709

Last change on this file since 93709 was 93709, checked in by vboxsync, 3 years ago
IPRT/hardavl: Added the right-to-left enumerator. Mark methods as noexcept. bugref:10093
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 51.2 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	* Check that the tree heights make sense for the current node.
40	*
41	* This is a RT_STRICT test as it's expensive and we should have sufficient
42	* other checks to ensure safe AVL tree operation.
43	*
44	* @note the a_cStackEntries parameter is a hack to avoid running into gcc's
45	* "the address of 'AVLStack' will never be NULL" errors.
46	*/
47	#ifdef RT_STRICT
48	# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { \
49	NodeType * const pLeftNodeX = a_pAllocator->ptrFromInt(readIdx(&(a_pNode)->idxLeft)); \
50	AssertReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \
51	NodeType * const pRightNodeX = a_pAllocator->ptrFromInt(readIdx(&(a_pNode)->idxRight)); \
52	AssertReturnStmt(a_pAllocator->isPtrRetOkay(pRightNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \
53	uint8_t const cLeftHeightX = pLeftNodeX ? pLeftNodeX->cHeight : 0; \
54	uint8_t const cRightHeightX = pRightNodeX ? pRightNodeX->cHeight : 0; \
55	if (RT_LIKELY((a_pNode)->cHeight == RT_MAX(cLeftHeightX, cRightHeightX) + 1)) { /likely/ } \
56	else \
57	{ \
58	RTAssertMsg2("line %u: %u l=%u r=%u\n", __LINE__, (a_pNode)->cHeight, cLeftHeightX, cRightHeightX); \
59	if ((a_cStackEntries)) dumpStack(a_pAllocator, (a_pAvlStack)); \
60	AssertMsgReturnStmt((a_pNode)->cHeight == RT_MAX(cLeftHeightX, cRightHeightX) + 1, \
61	("%u l=%u r=%u\n", (a_pNode)->cHeight, cLeftHeightX, cRightHeightX), \
62	m_cErrors++, VERR_HARDAVL_BAD_HEIGHT); \
63	} \
64	AssertMsgReturnStmt(RT_ABS(cLeftHeightX - cRightHeightX) <= 1, ("l=%u r=%u\n", cLeftHeightX, cRightHeightX), \
65	m_cErrors++, VERR_HARDAVL_UNBALANCED); \
66	Assert(!pLeftNodeX \|\| pLeftNodeX->Key < (a_pNode)->Key); \
67	Assert(!pRightNodeX \|\| pRightNodeX->Key > (a_pNode)->Key); \
68	} while (0)
69	#else
70	# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { } while (0)
71	#endif
72
73
74	/**
75	* Hardened AVL tree for nodes with key ranges.
76	*
77	* This is very crude and therefore expects the NodeType to feature:
78	* - Key and KeyLast members of KeyType.
79	* - idxLeft and idxRight members with type uint32_t.
80	* - cHeight members of type uint8_t.
81	*
82	* The code is very C-ish because of it's sources and initial use (ring-0
83	* without C++ exceptions enabled).
84	*/
85	template<typename NodeType, typename KeyType>
86	struct RTCHardAvlRangeTree
87	{
88	/** The root index. */
89	uint32_t m_idxRoot;
90	/** The error count. */
91	uint32_t m_cErrors;
92
93	/** The max stack depth. */
94	enum { kMaxStack = 28 };
95	/** The max height value we allow. */
96	enum { kMaxHeight = kMaxStack + 1 };
97
98	/** A stack used internally to avoid recursive calls.
99	* This is used with operations invoking i_rebalance(). */
100	typedef struct HardAvlStack
101	{
102	/** Number of entries on the stack. */
103	unsigned cEntries;
104	/** The stack. */
105	uint32_t *apidxEntries[kMaxStack];
106	} HardAvlStack;
107
108	/** @name Key comparisons
109	* @{ */
110	static inline int areKeyRangesIntersecting(KeyType a_Key1First, KeyType a_Key2First,
111	KeyType a_Key1Last, KeyType a_Key2Last) RT_NOEXCEPT
112	{
113	return a_Key1First <= a_Key2Last && a_Key1Last >= a_Key2First;
114	}
115
116	static inline int isKeyInRange(KeyType a_Key, KeyType a_KeyFirst, KeyType a_KeyLast) RT_NOEXCEPT
117	{
118	return a_Key <= a_KeyLast && a_Key >= a_KeyFirst;
119	}
120
121	static inline int isKeyGreater(KeyType a_Key1, KeyType a_Key2) RT_NOEXCEPT
122	{
123	return a_Key1 > a_Key2;
124	}
125	/** @} */
126
127	/**
128	* Read an index value trying to prevent the compiler from re-reading it.
129	*/
130	DECL_FORCE_INLINE(uint32_t) readIdx(uint32_t volatile *pidx) RT_NOEXCEPT
131	{
132	uint32_t idx = *pidx;
133	ASMCompilerBarrier();
134	return idx;
135	}
136
137	RTCHardAvlRangeTree() RT_NOEXCEPT
138	: m_idxRoot(0)
139	, m_cErrors(0)
140	{ }
141
142	RTCHardAvlRangeTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator) RT_NOEXCEPT
143	{
144	initWithAllocator(a_pAllocator);
145	}
146
147	void initWithAllocator(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator) RT_NOEXCEPT
148	{
149	m_idxRoot = a_pAllocator->kNilIndex;
150	m_cErrors = 0;
151	}
152
153	/**
154	* Inserts a node into the AVL-tree.
155	*
156	* @returns IPRT status code.
157	* @retval VERR_ALREADY_EXISTS if a node with overlapping key range exists.
158	*
159	* @param a_pAllocator Pointer to the allocator.
160	* @param a_pNode Pointer to the node which is to be added.
161	*
162	* @code
163	* Find the location of the node (using binary tree algorithm.):
164	* LOOP until KAVL_NULL leaf pointer
165	* BEGIN
166	* Add node pointer pointer to the AVL-stack.
167	* IF new-node-key < node key THEN
168	* left
169	* ELSE
170	* right
171	* END
172	* Fill in leaf node and insert it.
173	* Rebalance the tree.
174	* @endcode
175	*/
176	int insert(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, NodeType a_pNode) RT_NOEXCEPT
177	{
178	KeyType const Key = a_pNode->Key;
179	KeyType const KeyLast = a_pNode->KeyLast;
180	AssertMsgReturn(Key <= KeyLast, ("Key=%#RX64 KeyLast=%#RX64\n", (uint64_t)Key, (uint64_t)KeyLast),
181	VERR_HARDAVL_INSERT_INVALID_KEY_RANGE);
182
183	uint32_t *pidxCurNode = &m_idxRoot;
184	HardAvlStack AVLStack;
185	AVLStack.cEntries = 0;
186	for (;;)
187	{
188	NodeType *pCurNode = a_pAllocator->ptrFromInt(readIdx(pidxCurNode));
189	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pCurNode), ("pidxCurNode=%#x pCurNode=%p\n", pidxCurNode, pCurNode),
190	m_cErrors++, a_pAllocator->ptrErrToStatus(pCurNode));
191	if (!pCurNode)
192	break;
193
194	unsigned const cEntries = AVLStack.cEntries;
195	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
196	("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n", pidxCurNode, *pidxCurNode, pCurNode,
197	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
198	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
199	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3],
200	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4],
201	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
202	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
203	AVLStack.apidxEntries[cEntries] = pidxCurNode;
204	AVLStack.cEntries = cEntries + 1;
205
206	RTHARDAVL_STRICT_CHECK_HEIGHTS(pCurNode, &AVLStack, AVLStack.cEntries);
207
208	/* Range check: */
209	if (areKeyRangesIntersecting(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
210	return VERR_ALREADY_EXISTS;
211
212	/* Descend: */
213	if (isKeyGreater(pCurNode->Key, Key))
214	pidxCurNode = &pCurNode->idxLeft;
215	else
216	pidxCurNode = &pCurNode->idxRight;
217	}
218
219	a_pNode->idxLeft = a_pAllocator->kNilIndex;
220	a_pNode->idxRight = a_pAllocator->kNilIndex;
221	a_pNode->cHeight = 1;
222
223	uint32_t const idxNode = a_pAllocator->ptrToInt(a_pNode);
224	AssertMsgReturn(a_pAllocator->isIdxRetOkay(idxNode), ("pNode=%p idxNode=%#x\n", a_pNode, idxNode),
225	a_pAllocator->idxErrToStatus(idxNode));
226	*pidxCurNode = idxNode;
227
228	return i_rebalance(a_pAllocator, &AVLStack);
229	}
230
231	/**
232	* Removes a node from the AVL-tree by a key value.
233	*
234	* @returns IPRT status code.
235	* @retval VERR_NOT_FOUND if not found.
236	* @param a_pAllocator Pointer to the allocator.
237	* @param a_Key A key value in the range of the node to be removed.
238	* @param a_ppRemoved Where to return the pointer to the removed node.
239	*
240	* @code
241	* Find the node which is to be removed:
242	* LOOP until not found
243	* BEGIN
244	* Add node pointer pointer to the AVL-stack.
245	* IF the keys matches THEN break!
246	* IF remove key < node key THEN
247	* left
248	* ELSE
249	* right
250	* END
251	* IF found THEN
252	* BEGIN
253	* IF left node not empty THEN
254	* BEGIN
255	* Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
256	* Start at left node.
257	* LOOP until right node is empty
258	* BEGIN
259	* Add to stack.
260	* go right.
261	* END
262	* Link out the found node.
263	* Replace the node which is to be removed with the found node.
264	* Correct the stack entry for the pointer to the left tree.
265	* END
266	* ELSE
267	* BEGIN
268	* Move up right node.
269	* Remove last stack entry.
270	* END
271	* Balance tree using stack.
272	* END
273	* return pointer to the removed node (if found).
274	* @endcode
275	*/
276	int remove(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, KeyType a_Key, NodeType *a_ppRemoved) RT_NOEXCEPT
277	{
278	*a_ppRemoved = NULL;
279
280	/*
281	* Walk the tree till we locate the node that is to be deleted.
282	*/
283	uint32_t *pidxDeleteNode = &m_idxRoot;
284	NodeType *pDeleteNode;
285	HardAvlStack AVLStack;
286	AVLStack.cEntries = 0;
287	for (;;)
288	{
289	pDeleteNode = a_pAllocator->ptrFromInt(readIdx(pidxDeleteNode));
290	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteNode),
291	("pidxCurNode=%#x pDeleteNode=%p\n", pidxDeleteNode, pDeleteNode),
292	m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteNode));
293	if (pDeleteNode)
294	{ /likely/ }
295	else
296	return VERR_NOT_FOUND;
297
298	unsigned const cEntries = AVLStack.cEntries;
299	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
300	("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n",
301	pidxDeleteNode, *pidxDeleteNode, pDeleteNode,
302	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
303	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
304	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3],
305	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4],
306	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
307	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
308	AVLStack.apidxEntries[cEntries] = pidxDeleteNode;
309	AVLStack.cEntries = cEntries + 1;
310
311	RTHARDAVL_STRICT_CHECK_HEIGHTS(pDeleteNode, &AVLStack, AVLStack.cEntries);
312
313	/* Range check: */
314	if (isKeyInRange(a_Key, pDeleteNode->Key, pDeleteNode->KeyLast))
315	break;
316
317	/* Descend: */
318	if (isKeyGreater(pDeleteNode->Key, a_Key))
319	pidxDeleteNode = &pDeleteNode->idxLeft;
320	else
321	pidxDeleteNode = &pDeleteNode->idxRight;
322	}
323
324	/*
325	* Do the deletion.
326	*/
327	uint32_t const idxDeleteLeftNode = readIdx(&pDeleteNode->idxLeft);
328	if (idxDeleteLeftNode != a_pAllocator->kNilIndex)
329	{
330	/*
331	* Replace the deleted node with the rightmost node in the left subtree.
332	*/
333	NodeType * const pDeleteLeftNode = a_pAllocator->ptrFromInt(idxDeleteLeftNode);
334	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteLeftNode),
335	("idxDeleteLeftNode=%#x pDeleteLeftNode=%p\n", idxDeleteLeftNode, pDeleteLeftNode),
336	m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteLeftNode));
337
338	uint32_t const idxDeleteRightNode = readIdx(&pDeleteNode->idxRight);
339	AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
340
341	const unsigned iStackEntry = AVLStack.cEntries;
342
343	uint32_t *pidxLeftBiggest = &pDeleteNode->idxLeft;
344	uint32_t idxLeftBiggestNode = idxDeleteLeftNode;
345	NodeType *pLeftBiggestNode = pDeleteLeftNode;
346	RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries);
347
348	uint32_t idxRightTmp;
349	while ((idxRightTmp = readIdx(&pLeftBiggestNode->idxRight)) != a_pAllocator->kNilIndex)
350	{
351	unsigned const cEntries = AVLStack.cEntries;
352	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(AVLStack.apidxEntries),
353	("%p[%#x/%p] %p[%#x] %p[%#x] %p[%#x] %p[%#x] %p[%#x]\n",
354	pidxLeftBiggest, *pidxLeftBiggest, pLeftBiggestNode,
355	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 1],
356	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 2],
357	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 3],
358	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 4],
359	AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
360	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
361	AVLStack.apidxEntries[cEntries] = pidxLeftBiggest;
362	AVLStack.cEntries = cEntries + 1;
363
364	pidxLeftBiggest = &pLeftBiggestNode->idxRight;
365	idxLeftBiggestNode = idxRightTmp;
366	pLeftBiggestNode = a_pAllocator->ptrFromInt(idxRightTmp);
367	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftBiggestNode),
368	("idxLeftBiggestNode=%#x pLeftBiggestNode=%p\n", idxLeftBiggestNode, pLeftBiggestNode),
369	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftBiggestNode));
370	RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries);
371	}
372
373	uint32_t const idxLeftBiggestLeftNode = readIdx(&pLeftBiggestNode->idxLeft);
374	AssertReturnStmt(a_pAllocator->isIntValid(idxLeftBiggestLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
375
376	/* link out pLeftBiggestNode */
377	*pidxLeftBiggest = idxLeftBiggestLeftNode;
378
379	/* link it in place of the deleted node. */
380	if (idxDeleteLeftNode != idxLeftBiggestNode)
381	pLeftBiggestNode->idxLeft = idxDeleteLeftNode;
382	pLeftBiggestNode->idxRight = idxDeleteRightNode;
383	pLeftBiggestNode->cHeight = AVLStack.cEntries > iStackEntry ? pDeleteNode->cHeight : 0;
384
385	*pidxDeleteNode = idxLeftBiggestNode;
386
387	if (AVLStack.cEntries > iStackEntry)
388	AVLStack.apidxEntries[iStackEntry] = &pLeftBiggestNode->idxLeft;
389	}
390	else
391	{
392	/* No left node, just pull up the right one. */
393	uint32_t const idxDeleteRightNode = readIdx(&pDeleteNode->idxRight);
394	AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
395	*pidxDeleteNode = idxDeleteRightNode;
396	AVLStack.cEntries--;
397	}
398	*a_ppRemoved = pDeleteNode;
399
400	return i_rebalance(a_pAllocator, &AVLStack);
401	}
402
403	/**
404	* Looks up a node from the tree.
405	*
406	* @returns IPRT status code.
407	* @retval VERR_NOT_FOUND if not found.
408	*
409	* @param a_pAllocator Pointer to the allocator.
410	* @param a_Key A key value in the range of the desired node.
411	* @param a_ppFound Where to return the pointer to the node.
412	*/
413	int lookup(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, KeyType a_Key, NodeType *a_ppFound) RT_NOEXCEPT
414	{
415	*a_ppFound = NULL;
416
417	NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
418	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
419	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
420	#ifdef RT_STRICT
421	HardAvlStack AVLStack;
422	AVLStack.apidxEntries[0] = &m_idxRoot;
423	AVLStack.cEntries = 1;
424	#endif
425	unsigned cDepth = 0;
426	while (pNode)
427	{
428	RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, &AVLStack, AVLStack.cEntries);
429	AssertReturn(cDepth <= kMaxHeight, VERR_HARDAVL_LOOKUP_TOO_DEEP);
430	cDepth++;
431
432	if (isKeyInRange(a_Key, pNode->Key, pNode->KeyLast))
433	{
434	*a_ppFound = pNode;
435	return VINF_SUCCESS;
436	}
437	if (isKeyGreater(pNode->Key, a_Key))
438	{
439	#ifdef RT_STRICT
440	AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxLeft;
441	#endif
442	uint32_t const idxLeft = readIdx(&pNode->idxLeft);
443	pNode = a_pAllocator->ptrFromInt(idxLeft);
444	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxLeft=%#x pNode=%p\n", idxLeft, pNode),
445	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
446	}
447	else
448	{
449	#ifdef RT_STRICT
450	AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxRight;
451	#endif
452	uint32_t const idxRight = readIdx(&pNode->idxRight);
453	pNode = a_pAllocator->ptrFromInt(idxRight);
454	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxRight=%#x pNode=%p\n", idxRight, pNode),
455	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
456	}
457	}
458
459	return VERR_NOT_FOUND;
460	}
461
462	/**
463	* A callback for doWithAllFromLeft and doWithAllFromRight.
464	*
465	* @returns IPRT status code. Any non-zero status causes immediate return from
466	* the enumeration function.
467	* @param pNode The current node.
468	* @param pvUser The user argument.
469	*/
470	typedef DECLCALLBACKTYPE(int, FNCALLBACK,(NodeType pNode, void pvUser));
471	/** Pointer to a callback for doWithAllFromLeft and doWithAllFromRight. */
472	typedef FNCALLBACK *PFNCALLBACK;
473
474	/**
475	* Iterates thru all nodes in the tree from left (smaller) to right.
476	*
477	* @returns IPRT status code.
478	*
479	* @param a_pAllocator Pointer to the allocator.
480	* @param a_pfnCallBack Pointer to callback function.
481	* @param a_pvUser Callback user argument.
482	*
483	* @note This is very similar code to doWithAllFromRight() and destroy().
484	*/
485	int doWithAllFromLeft(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator,
486	PFNCALLBACK a_pfnCallBack, void *a_pvUser) RT_NOEXCEPT
487	{
488	NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
489	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
490	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
491	if (!pNode)
492	return VINF_SUCCESS;
493
494	/*
495	* We simulate recursive calling here. For safety reasons, we do not
496	* pop before going down the right tree like the original code did.
497	*/
498	uint32_t cNodesLeft = a_pAllocator->m_cNodes;
499	NodeType *apEntries[kMaxStack];
500	uint8_t abState[kMaxStack];
501	unsigned cEntries = 1;
502	abState[0] = 0;
503	apEntries[0] = pNode;
504	while (cEntries > 0)
505	{
506	pNode = apEntries[cEntries - 1];
507	switch (abState[cEntries - 1])
508	{
509	/* Go left. */
510	case 0:
511	{
512	abState[cEntries - 1] = 1;
513
514	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft));
515	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
516	("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
517	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
518	if (pLeftNode)
519	{
520	#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
521	AssertCompile(kMaxStack > 6);
522	#endif
523	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
524	("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
525	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
526	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
527	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
528	apEntries[cEntries] = pLeftNode;
529	abState[cEntries] = 0;
530	cEntries++;
531
532	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
533	cNodesLeft--;
534	break;
535	}
536	RT_FALL_THROUGH();
537	}
538
539	/* center then right. */
540	case 1:
541	{
542	abState[cEntries - 1] = 2;
543
544	RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
545
546	int rc = a_pfnCallBack(pNode, a_pvUser);
547	if (rc != VINF_SUCCESS)
548	return rc;
549
550	NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight));
551	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
552	("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
553	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
554	if (pRightNode)
555	{
556	#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
557	AssertCompile(kMaxStack > 6);
558	#endif
559	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
560	("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],
561	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
562	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
563	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
564	apEntries[cEntries] = pRightNode;
565	abState[cEntries] = 0;
566	cEntries++;
567
568	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
569	cNodesLeft--;
570	break;
571	}
572	RT_FALL_THROUGH();
573	}
574
575	default:
576	/* pop it. */
577	cEntries -= 1;
578	break;
579	}
580	}
581	return VINF_SUCCESS;
582	}
583
584	/**
585	* Iterates thru all nodes in the tree from right (larger) to left (smaller).
586	*
587	* @returns IPRT status code.
588	*
589	* @param a_pAllocator Pointer to the allocator.
590	* @param a_pfnCallBack Pointer to callback function.
591	* @param a_pvUser Callback user argument.
592	*
593	* @note This is very similar code to doWithAllFromLeft() and destroy().
594	*/
595	int doWithAllFromRight(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator,
596	PFNCALLBACK a_pfnCallBack, void *a_pvUser) RT_NOEXCEPT
597	{
598	NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
599	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
600	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
601	if (!pNode)
602	return VINF_SUCCESS;
603
604	/*
605	* We simulate recursive calling here. For safety reasons, we do not
606	* pop before going down the right tree like the original code did.
607	*/
608	uint32_t cNodesLeft = a_pAllocator->m_cNodes;
609	NodeType *apEntries[kMaxStack];
610	uint8_t abState[kMaxStack];
611	unsigned cEntries = 1;
612	abState[0] = 0;
613	apEntries[0] = pNode;
614	while (cEntries > 0)
615	{
616	pNode = apEntries[cEntries - 1];
617	switch (abState[cEntries - 1])
618	{
619	/* Go right. */
620	case 0:
621	{
622	abState[cEntries - 1] = 1;
623
624	NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight));
625	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
626	("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
627	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
628	if (pRightNode)
629	{
630	#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
631	AssertCompile(kMaxStack > 6);
632	#endif
633	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
634	("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],
635	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
636	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
637	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
638	apEntries[cEntries] = pRightNode;
639	abState[cEntries] = 0;
640	cEntries++;
641
642	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
643	cNodesLeft--;
644	break;
645	}
646	RT_FALL_THROUGH();
647	}
648
649	/* center then left. */
650	case 1:
651	{
652	abState[cEntries - 1] = 2;
653
654	RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
655
656	int rc = a_pfnCallBack(pNode, a_pvUser);
657	if (rc != VINF_SUCCESS)
658	return rc;
659
660	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft));
661	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
662	("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
663	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
664	if (pLeftNode)
665	{
666	#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
667	AssertCompile(kMaxStack > 6);
668	#endif
669	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
670	("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
671	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
672	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
673	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
674	apEntries[cEntries] = pLeftNode;
675	abState[cEntries] = 0;
676	cEntries++;
677
678	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
679	cNodesLeft--;
680	break;
681	}
682	RT_FALL_THROUGH();
683	}
684
685	default:
686	/* pop it. */
687	cEntries -= 1;
688	break;
689	}
690	}
691	return VINF_SUCCESS;
692	}
693
694	/**
695	* A callback for destroy to do additional cleanups before the node is freed.
696	*
697	* @param pNode The current node.
698	* @param pvUser The user argument.
699	*/
700	typedef DECLCALLBACKTYPE(void, FNDESTROYCALLBACK,(NodeType pNode, void pvUser));
701	/** Pointer to a callback for destroy. */
702	typedef FNDESTROYCALLBACK *PFNDESTROYCALLBACK;
703
704	/**
705	* Destroys the tree, starting with the root node.
706	*
707	* This will invoke the freeNode() method on the allocate for every node after
708	* first doing the callback to let the caller free additional resources
709	* referenced by the node.
710	*
711	* @returns IPRT status code.
712	*
713	* @param a_pAllocator Pointer to the allocator.
714	* @param a_pfnCallBack Pointer to callback function. Optional.
715	* @param a_pvUser Callback user argument.
716	*
717	* @note This is mostly the same code as the doWithAllFromLeft().
718	*/
719	int destroy(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator,
720	PFNDESTROYCALLBACK a_pfnCallBack = NULL, void *a_pvUser = NULL) RT_NOEXCEPT
721	{
722	NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
723	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
724	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
725	if (!pNode)
726	return VINF_SUCCESS;
727
728	/*
729	* We simulate recursive calling here. For safety reasons, we do not
730	* pop before going down the right tree like the original code did.
731	*/
732	uint32_t cNodesLeft = a_pAllocator->m_cNodes;
733	NodeType *apEntries[kMaxStack];
734	uint8_t abState[kMaxStack];
735	unsigned cEntries = 1;
736	abState[0] = 0;
737	apEntries[0] = pNode;
738	while (cEntries > 0)
739	{
740	pNode = apEntries[cEntries - 1];
741	switch (abState[cEntries - 1])
742	{
743	/* Go left. */
744	case 0:
745	{
746	abState[cEntries - 1] = 1;
747
748	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft));
749	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
750	("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
751	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
752	if (pLeftNode)
753	{
754	#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
755	AssertCompile(kMaxStack > 6);
756	#endif
757	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
758	("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
759	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
760	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
761	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
762	apEntries[cEntries] = pLeftNode;
763	abState[cEntries] = 0;
764	cEntries++;
765
766	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
767	cNodesLeft--;
768	break;
769	}
770	RT_FALL_THROUGH();
771	}
772
773	/* right. */
774	case 1:
775	{
776	abState[cEntries - 1] = 2;
777
778	NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight));
779	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
780	("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
781	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
782	if (pRightNode)
783	{
784	#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
785	AssertCompile(kMaxStack > 6);
786	#endif
787	AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
788	("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],
789	apEntries[kMaxStack - 2], apEntries[kMaxStack - 3], apEntries[kMaxStack - 4],
790	apEntries[kMaxStack - 5], apEntries[kMaxStack - 6]),
791	m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
792	apEntries[cEntries] = pRightNode;
793	abState[cEntries] = 0;
794	cEntries++;
795
796	AssertReturn(cNodesLeft > 0, VERR_HARDAVL_TRAVERSED_TOO_MANY_NODES);
797	cNodesLeft--;
798	break;
799	}
800	RT_FALL_THROUGH();
801	}
802
803	default:
804	{
805	/* pop it and destroy it. */
806	if (a_pfnCallBack)
807	a_pfnCallBack(pNode, a_pvUser);
808
809	int rc = a_pAllocator->freeNode(pNode);
810	AssertRCReturnStmt(rc, m_cErrors++, rc);
811
812	cEntries -= 1;
813	break;
814	}
815	}
816	}
817
818	Assert(m_idxRoot == a_pAllocator->kNilIndex);
819	return VINF_SUCCESS;
820	}
821
822
823	/**
824	* Gets the tree height value (reads cHeigh from the root node).
825	*
826	* @retval UINT8_MAX if bogus tree.
827	*/
828	uint8_t getHeight(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator) RT_NOEXCEPT
829	{
830	NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
831	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
832	m_cErrors++, UINT8_MAX);
833	if (pNode)
834	return pNode->cHeight;
835	return 0;
836	}
837
838	#ifdef RT_STRICT
839
840	static void dumpStack(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, HardAvlStack const pStack) RT_NOEXCEPT
841	{
842	uint32_t const * const *paidx = pStack->apidxEntries;
843	RTAssertMsg2("stack: %u:\n", pStack->cEntries);
844	for (unsigned i = 0; i < pStack->cEntries; i++)
845	{
846	uint32_t idx = *paidx[i];
847	uint32_t idxNext = i + 1 < pStack->cEntries ? *paidx[i + 1] : UINT32_MAX;
848	NodeType const *pNode = a_pAllocator->ptrFromInt(idx);
849	RTAssertMsg2(" #%02u: %p[%#06x] pNode=%p h=%02d l=%#06x%c r=%#06x%c\n", i, paidx[i], idx, pNode, pNode->cHeight,
850	pNode->idxLeft, pNode->idxLeft == idxNext ? '*' : ' ',
851	pNode->idxRight, pNode->idxRight == idxNext ? '*' : ' ');
852	}
853	}
854
855	static void printTree(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, uint32_t a_idxRoot,
856	unsigned a_uLevel = 0, unsigned a_uMaxLevel = 8, const char *a_pszDir = "") RT_NOEXCEPT
857	{
858	if (a_idxRoot == a_pAllocator->kNilIndex)
859	RTAssertMsg2("%snil\n", a_uLevel 6, a_pszDir);
860	else if (a_uLevel < a_uMaxLevel)
861	{
862	NodeType *pNode = a_pAllocator->ptrFromInt(a_idxRoot);
863	printTree(a_pAllocator, readIdx(&pNode->idxRight), a_uLevel + 1, a_uMaxLevel, "/ ");
864	RTAssertMsg2("%s%#x/%u\n", a_uLevel 6, a_pszDir, a_idxRoot, pNode->cHeight);
865	printTree(a_pAllocator, readIdx(&pNode->idxLeft), a_uLevel + 1, a_uMaxLevel, "\\ ");
866	}
867	else
868	RTAssertMsg2("%stoo deep\n", a_uLevel 6, a_pszDir);
869	}
870
871	#endif
872
873	private:
874	/**
875	* Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
876	*
877	* @returns IPRT status code.
878	*
879	* @param a_pAllocator Pointer to the allocator.
880	* @param a_pStack Pointer to stack to rewind.
881	* @param a_fLog Log is done (DEBUG builds only).
882	*
883	* @code
884	* LOOP thru all stack entries
885	* BEGIN
886	* Get pointer to pointer to node (and pointer to node) from the stack.
887	* IF 2 higher left subtree than in right subtree THEN
888	* BEGIN
889	* IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
890	* * n+2\|n+3
891	* / \ / \
892	* n+2 n ==> n+1 n+1\|n+2
893	* / \ / \
894	* n+1 n\|n+1 n\|n+1 n
895	*
896	* Or with keys:
897	*
898	* 4 2
899	* / \ / \
900	* 2 5 ==> 1 4
901	* / \ / \
902	* 1 3 3 5
903	*
904	* ELSE
905	* * n+2
906	* / \ / \
907	* n+2 n n+1 n+1
908	* / \ ==> / \ / \
909	* n n+1 n L R n
910	* / \
911	* L R
912	*
913	* Or with keys:
914	* 6 4
915	* / \ / \
916	* 2 7 ==> 2 6
917	* / \ / \ / \
918	* 1 4 1 3 5 7
919	* / \
920	* 3 5
921	* END
922	* ELSE IF 2 higher in right subtree than in left subtree THEN
923	* BEGIN
924	* Same as above but left <==> right. (invert the picture)
925	* ELSE
926	* IF correct height THEN break
927	* ELSE correct height.
928	* END
929	* @endcode
930	* @internal
931	*/
932	int i_rebalance(RTCHardAvlTreeSlabAllocator<NodeType> a_pAllocator, HardAvlStack a_pStack, bool a_fLog = false) RT_NOEXCEPT
933	{
934	RT_NOREF(a_fLog);
935
936	while (a_pStack->cEntries > 0)
937	{
938	/* pop */
939	uint32_t * const pidxNode = a_pStack->apidxEntries[--a_pStack->cEntries];
940	uint32_t const idxNode = readIdx(pidxNode);
941	NodeType * const pNode = a_pAllocator->ptrFromInt(idxNode);
942	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode),
943	("pidxNode=%p[%#x] pNode=%p\n", pidxNode, *pidxNode, pNode),
944	m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
945
946	/* Read node properties: */
947	uint32_t const idxLeftNode = readIdx(&pNode->idxLeft);
948	NodeType * const pLeftNode = a_pAllocator->ptrFromInt(idxLeftNode);
949	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
950	("idxLeftNode=%#x pLeftNode=%p\n", idxLeftNode, pLeftNode),
951	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
952
953	uint32_t const idxRightNode = readIdx(&pNode->idxRight);
954	NodeType * const pRightNode = a_pAllocator->ptrFromInt(idxRightNode);
955	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
956	("idxRight=%#x pRightNode=%p\n", idxRightNode, pRightNode),
957	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightNode));
958
959	uint8_t const cLeftHeight = pLeftNode ? pLeftNode->cHeight : 0;
960	AssertReturnStmt(cLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT);
961
962	uint8_t const cRightHeight = pRightNode ? pRightNode->cHeight : 0;
963	AssertReturnStmt(cRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT);
964
965	/* Decide what needs doing: */
966	if (cRightHeight + 1 < cLeftHeight)
967	{
968	Assert(cRightHeight + 2 == cLeftHeight);
969	AssertReturnStmt(pLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
970
971	uint32_t const idxLeftLeftNode = readIdx(&pLeftNode->idxLeft);
972	NodeType * const pLeftLeftNode = a_pAllocator->ptrFromInt(idxLeftLeftNode);
973	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeftNode),
974	("idxLeftLeftNode=%#x pLeftLeftNode=%p\n", idxLeftLeftNode, pLeftLeftNode),
975	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeftNode));
976
977	uint32_t const idxLeftRightNode = readIdx(&pLeftNode->idxRight);
978	NodeType * const pLeftRightNode = a_pAllocator->ptrFromInt(idxLeftRightNode);
979	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftRightNode),
980	("idxLeftRightNode=%#x pLeftRightNode=%p\n", idxLeftRightNode, pLeftRightNode),
981	m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftRightNode));
982
983	uint8_t const cLeftRightHeight = pLeftRightNode ? pLeftRightNode->cHeight : 0;
984	if ((pLeftLeftNode ? pLeftLeftNode->cHeight : 0) >= cLeftRightHeight)
985	{
986	AssertReturnStmt(cLeftRightHeight + 2 <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
987	pNode->idxLeft = idxLeftRightNode;
988	pNode->cHeight = (uint8_t)(cLeftRightHeight + 1);
989	pLeftNode->cHeight = (uint8_t)(cLeftRightHeight + 2);
990	pLeftNode->idxRight = idxNode;
991	*pidxNode = idxLeftNode;
992	#ifdef DEBUG
993	if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #1\n", a_pStack->cEntries);
994	#endif
995	}
996	else
997	{
998	AssertReturnStmt(cLeftRightHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_RIGHT_HEIGHT);
999	AssertReturnStmt(pLeftRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
1000
1001	uint32_t const idxLeftRightLeftNode = readIdx(&pLeftRightNode->idxLeft);
1002	AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
1003	uint32_t const idxLeftRightRightNode = readIdx(&pLeftRightNode->idxRight);
1004	AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
1005	pLeftNode->idxRight = idxLeftRightLeftNode;
1006	pNode->idxLeft = idxLeftRightRightNode;
1007
1008	pLeftRightNode->idxLeft = idxLeftNode;
1009	pLeftRightNode->idxRight = idxNode;
1010	pLeftNode->cHeight = cLeftRightHeight;
1011	pNode->cHeight = cLeftRightHeight;
1012	pLeftRightNode->cHeight = cLeftHeight;
1013	*pidxNode = idxLeftRightNode;
1014	#ifdef DEBUG
1015	if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #2\n", a_pStack->cEntries);
1016	#endif
1017	}
1018	}
1019	else if (cLeftHeight + 1 < cRightHeight)
1020	{
1021	Assert(cLeftHeight + 2 == cRightHeight);
1022	AssertReturnStmt(pRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
1023
1024	uint32_t const idxRightLeftNode = readIdx(&pRightNode->idxLeft);
1025	NodeType * const pRightLeftNode = a_pAllocator->ptrFromInt(idxRightLeftNode);
1026	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightLeftNode),
1027	("idxRightLeftNode=%#x pRightLeftNode=%p\n", idxRightLeftNode, pRightLeftNode),
1028	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightLeftNode));
1029
1030	uint32_t const idxRightRightNode = readIdx(&pRightNode->idxRight);
1031	NodeType * const pRightRightNode = a_pAllocator->ptrFromInt(idxRightRightNode);
1032	AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightRightNode),
1033	("idxRightRightNode=%#x pRightRightNode=%p\n", idxRightRightNode, pRightRightNode),
1034	m_cErrors++, a_pAllocator->ptrErrToStatus(pRightRightNode));
1035
1036	uint8_t const cRightLeftHeight = pRightLeftNode ? pRightLeftNode->cHeight : 0;
1037	if ((pRightRightNode ? pRightRightNode->cHeight : 0) >= cRightLeftHeight)
1038	{
1039	AssertReturnStmt(cRightLeftHeight + 2 <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
1040
1041	pNode->idxRight = idxRightLeftNode;
1042	pRightNode->idxLeft = idxNode;
1043	pNode->cHeight = (uint8_t)(cRightLeftHeight + 1);
1044	pRightNode->cHeight = (uint8_t)(cRightLeftHeight + 2);
1045	*pidxNode = idxRightNode;
1046	#ifdef DEBUG
1047	if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #3 h=%d, pidxNode=%#x\n", a_pStack->cEntries, pRightNode->cHeight, pidxNode);
1048	#endif
1049	RTHARDAVL_STRICT_CHECK_HEIGHTS(pRightNode, NULL, 0);
1050	RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
1051	}
1052	else
1053	{
1054	AssertReturnStmt(cRightLeftHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_LEFT_HEIGHT);
1055	AssertReturnStmt(pRightLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
1056
1057	uint32_t const idxRightLeftRightNode = readIdx(&pRightLeftNode->idxRight);
1058	AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
1059	uint32_t const idxRightLeftLeftNode = readIdx(&pRightLeftNode->idxLeft);
1060	AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
1061	pRightNode->idxLeft = idxRightLeftRightNode;
1062	pNode->idxRight = idxRightLeftLeftNode;
1063
1064	pRightLeftNode->idxRight = idxRightNode;
1065	pRightLeftNode->idxLeft = idxNode;
1066	pRightNode->cHeight = cRightLeftHeight;
1067	pNode->cHeight = cRightLeftHeight;
1068	pRightLeftNode->cHeight = cRightHeight;
1069	*pidxNode = idxRightLeftNode;
1070	#ifdef DEBUG
1071	if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #4 h=%d, pidxNode=%#x\n", a_pStack->cEntries, pRightLeftNode->cHeight, pidxNode);
1072	#endif
1073	}
1074	}
1075	else
1076	{
1077	uint8_t const cHeight = (uint8_t)(RT_MAX(cLeftHeight, cRightHeight) + 1);
1078	AssertReturnStmt(cHeight <= kMaxHeight, m_cErrors++, VERR_HARDAVL_BAD_NEW_HEIGHT);
1079	if (cHeight == pNode->cHeight)
1080	{
1081	#ifdef DEBUG
1082	if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #5, h=%d - done\n", a_pStack->cEntries, cHeight);
1083	#endif
1084	RTHARDAVL_STRICT_CHECK_HEIGHTS(pNode, NULL, 0);
1085	if (pLeftNode)
1086	RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftNode, NULL, 0);
1087	if (pRightNode)
1088	RTHARDAVL_STRICT_CHECK_HEIGHTS(pRightNode, NULL, 0);
1089	break;
1090	}
1091	#ifdef DEBUG
1092	if (a_fLog) RTAssertMsg2("rebalance: %#2u: op #5, h=%d - \n", a_pStack->cEntries, cHeight);
1093	#endif
1094	pNode->cHeight = cHeight;
1095	}
1096	}
1097	return VINF_SUCCESS;
1098	}
1099	};
1100
1101	/** @} */
1102
1103	#endif /* !IPRT_INCLUDED_cpp_hardavlrange_h */
1104

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

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

Download in other formats: