hardavlrange.h@ 93693

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

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

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

Download in other formats: