hardavlrange.h@ 93690

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

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

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

Download in other formats: