VirtualBox

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

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

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

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