VirtualBox

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

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

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