VirtualBox

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

Last change on this file since 93695 was 93695, checked in by vboxsync, 3 years ago

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette