VirtualBox

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

Last change on this file since 104212 was 99760, checked in by vboxsync, 19 months ago

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