VirtualBox

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

Last change on this file since 97583 was 96407, checked in by vboxsync, 2 years ago

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