VirtualBox

source: vbox/trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp@ 76553

Last change on this file since 76553 was 76553, checked in by vboxsync, 5 years ago

scm --update-copyright-year
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
File size: 29.8 KB
Line 
1/* $Id: tstRTAvl.cpp 76553 2019-01-01 01:45:53Z vboxsync $ */
2/** @file
3 * IPRT Testcase - AVL trees.
4 */
5
6/*
7 * Copyright (C) 2006-2019 Oracle Corporation
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License (GPL) as published by the Free Software
13 * Foundation, in version 2 as it comes in the "COPYING" file of the
14 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 *
17 * The contents of this file may alternatively be used under the terms
18 * of the Common Development and Distribution License Version 1.0
19 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20 * VirtualBox OSE distribution, in which case the provisions of the
21 * CDDL are applicable instead of those of the GPL.
22 *
23 * You may elect to license modified versions of this file under the
24 * terms and conditions of either the GPL or the CDDL or both.
25 */
26
27
28/*********************************************************************************************************************************
29* Header Files *
30*********************************************************************************************************************************/
31#include <iprt/avl.h>
32
33#include <iprt/asm.h>
34#include <iprt/initterm.h>
35#include <iprt/mem.h>
36#include <iprt/rand.h>
37#include <iprt/stdarg.h>
38#include <iprt/string.h>
39#include <iprt/test.h>
40
41
42/*********************************************************************************************************************************
43* Structures and Typedefs *
44*********************************************************************************************************************************/
45typedef struct TRACKER
46{
47 /** The max key value (exclusive). */
48 uint32_t MaxKey;
49 /** The last allocated key. */
50 uint32_t LastAllocatedKey;
51 /** The number of set bits in the bitmap. */
52 uint32_t cSetBits;
53 /** The bitmap size. */
54 uint32_t cbBitmap;
55 /** Bitmap containing the allocated nodes. */
56 uint8_t abBitmap[1];
57} TRACKER, *PTRACKER;
58
59
60/*********************************************************************************************************************************
61* Global Variables *
62*********************************************************************************************************************************/
63static RTTEST g_hTest;
64static RTRAND g_hRand;
65
66
67/**
68 * Creates a new tracker.
69 *
70 * @returns Pointer to the new tracker.
71 * @param MaxKey The max key value for the tracker. (exclusive)
72 */
73static PTRACKER TrackerCreate(uint32_t MaxKey)
74{
75 uint32_t cbBitmap = (MaxKey + sizeof(uint32_t) * sizeof(uint8_t) - 1) / sizeof(uint8_t);
76 PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_UOFFSETOF_DYN(TRACKER, abBitmap[cbBitmap]));
77 if (pTracker)
78 {
79 pTracker->MaxKey = MaxKey;
80 pTracker->LastAllocatedKey = MaxKey;
81 pTracker->cbBitmap = cbBitmap;
82 Assert(pTracker->cSetBits == 0);
83 }
84 return pTracker;
85}
86
87
88/**
89 * Destroys a tracker.
90 *
91 * @param pTracker The tracker.
92 */
93static void TrackerDestroy(PTRACKER pTracker)
94{
95 RTMemFree(pTracker);
96}
97
98
99/**
100 * Inserts a key range into the tracker.
101 *
102 * @returns success indicator.
103 * @param pTracker The tracker.
104 * @param Key The first key in the range.
105 * @param KeyLast The last key in the range. (inclusive)
106 */
107static bool TrackerInsert(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
108{
109 bool fRc = !ASMBitTestAndSet(pTracker->abBitmap, Key);
110 if (fRc)
111 pTracker->cSetBits++;
112 while (KeyLast != Key)
113 {
114 if (!ASMBitTestAndSet(pTracker->abBitmap, KeyLast))
115 pTracker->cSetBits++;
116 else
117 fRc = false;
118 KeyLast--;
119 }
120 return fRc;
121}
122
123
124/**
125 * Removes a key range from the tracker.
126 *
127 * @returns success indicator.
128 * @param pTracker The tracker.
129 * @param Key The first key in the range.
130 * @param KeyLast The last key in the range. (inclusive)
131 */
132static bool TrackerRemove(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
133{
134 bool fRc = ASMBitTestAndClear(pTracker->abBitmap, Key);
135 if (fRc)
136 pTracker->cSetBits--;
137 while (KeyLast != Key)
138 {
139 if (ASMBitTestAndClear(pTracker->abBitmap, KeyLast))
140 pTracker->cSetBits--;
141 else
142 fRc = false;
143 KeyLast--;
144 }
145 return fRc;
146}
147
148
149/**
150 * Random key range allocation.
151 *
152 * @returns success indicator.
153 * @param pTracker The tracker.
154 * @param pKey Where to store the first key in the allocated range.
155 * @param pKeyLast Where to store the first key in the allocated range.
156 * @param cMaxKey The max range length.
157 * @remark The caller has to call TrackerInsert.
158 */
159static bool TrackerNewRandomEx(PTRACKER pTracker, uint32_t *pKey, uint32_t *pKeyLast, uint32_t cMaxKeys)
160{
161 /*
162 * Find a key.
163 */
164 uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
165 if (ASMBitTest(pTracker->abBitmap, Key))
166 {
167 if (pTracker->cSetBits >= pTracker->MaxKey)
168 return false;
169
170 int Key2 = ASMBitNextClear(pTracker->abBitmap, pTracker->MaxKey, Key);
171 if (Key2 > 0)
172 Key = Key2;
173 else
174 {
175 /* we're missing a ASMBitPrevClear function, so just try another, lower, value.*/
176 for (;;)
177 {
178 const uint32_t KeyPrev = Key;
179 Key = RTRandAdvU32Ex(g_hRand, 0, KeyPrev - 1);
180 if (!ASMBitTest(pTracker->abBitmap, Key))
181 break;
182 Key2 = ASMBitNextClear(pTracker->abBitmap, RT_ALIGN_32(KeyPrev, 32), Key);
183 if (Key2 > 0)
184 {
185 Key = Key2;
186 break;
187 }
188 }
189 }
190 }
191
192 /*
193 * Determine the range.
194 */
195 uint32_t KeyLast;
196 if (cMaxKeys == 1 || !pKeyLast)
197 KeyLast = Key;
198 else
199 {
200 uint32_t cKeys = RTRandAdvU32Ex(g_hRand, 0, RT_MIN(pTracker->MaxKey - Key, cMaxKeys - 1));
201 KeyLast = Key + cKeys;
202 int Key2 = ASMBitNextSet(pTracker->abBitmap, RT_ALIGN_32(KeyLast, 32), Key);
203 if ( Key2 > 0
204 && (unsigned)Key2 <= KeyLast)
205 KeyLast = Key2 - 1;
206 }
207
208 /*
209 * Return.
210 */
211 *pKey = Key;
212 if (pKeyLast)
213 *pKeyLast = KeyLast;
214 return true;
215}
216
217
218/**
219 * Random single key allocation.
220 *
221 * @returns success indicator.
222 * @param pTracker The tracker.
223 * @param pKey Where to store the allocated key.
224 * @remark The caller has to call TrackerInsert.
225 */
226static bool TrackerNewRandom(PTRACKER pTracker, uint32_t *pKey)
227{
228 return TrackerNewRandomEx(pTracker, pKey, NULL, 1);
229}
230
231
232/**
233 * Random single key 'lookup'.
234 *
235 * @returns success indicator.
236 * @param pTracker The tracker.
237 * @param pKey Where to store the allocated key.
238 * @remark The caller has to call TrackerRemove.
239 */
240static bool TrackerFindRandom(PTRACKER pTracker, uint32_t *pKey)
241{
242 uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
243 if (!ASMBitTest(pTracker->abBitmap, Key))
244 {
245 if (!pTracker->cSetBits)
246 return false;
247
248 int Key2 = ASMBitNextSet(pTracker->abBitmap, pTracker->MaxKey, Key);
249 if (Key2 > 0)
250 Key = Key2;
251 else
252 {
253 /* we're missing a ASMBitPrevSet function, so here's a quick replacement hack. */
254 uint32_t *pu32Start = (uint32_t *)&pTracker->abBitmap[0];
255 uint32_t *pu32Cur = (uint32_t *)&pTracker->abBitmap[Key >> 8];
256 while (pu32Cur >= pu32Start)
257 {
258 if (*pu32Cur)
259 {
260 *pKey = ASMBitLastSetU32(*pu32Cur) - 1 + (uint32_t)((pu32Cur - pu32Start) * 32);
261 return true;
262 }
263 pu32Cur--;
264 }
265 Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
266 if (Key2 == -1)
267 {
268 RTTestIFailed("cSetBits=%u - but ASMBitFirstSet failed to find any", pTracker->cSetBits);
269 return false;
270 }
271 Key = Key2;
272 }
273 }
274
275 *pKey = Key;
276 return true;
277}
278
279
280/*
281bool TrackerAllocSeq(PTRACKER pTracker, uint32_t *pKey, uint32_t *pKeyLast, uint32_t cMaxKeys)
282{
283 return false;
284}*/
285
286
287/**
288 * Prints an unbuffered char.
289 * @param ch The char.
290 */
291static void ProgressChar(char ch)
292{
293 //RTTestIPrintf(RTTESTLVL_INFO, "%c", ch);
294 RTTestIPrintf(RTTESTLVL_SUB_TEST, "%c", ch);
295}
296
297/**
298 * Prints a progress indicator label.
299 * @param cMax The max number of operations (exclusive).
300 * @param pszFormat The format string.
301 * @param ... The arguments to the format string.
302 */
303DECLINLINE(void) ProgressPrintf(unsigned cMax, const char *pszFormat, ...)
304{
305 if (cMax < 10000)
306 return;
307
308 va_list va;
309 va_start(va, pszFormat);
310 //RTTestIPrintfV(RTTESTLVL_INFO, pszFormat, va);
311 RTTestIPrintfV(RTTESTLVL_SUB_TEST, pszFormat, va);
312 va_end(va);
313}
314
315
316/**
317 * Prints a progress indicator dot.
318 * @param iCur The current operation. (can be descending too)
319 * @param cMax The max number of operations (exclusive).
320 */
321DECLINLINE(void) Progress(unsigned iCur, unsigned cMax)
322{
323 if (cMax < 10000)
324 return;
325 if (!(iCur % (cMax / 20)))
326 ProgressChar('.');
327}
328
329
330static int avlogcphys(unsigned cMax)
331{
332 /*
333 * Simple linear insert and remove.
334 */
335 if (cMax >= 10000)
336 RTTestISubF("oGCPhys(%d): linear left", cMax);
337 PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
338 unsigned i;
339 for (i = 0; i < cMax; i++)
340 {
341 Progress(i, cMax);
342 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
343 pNode->Key = i;
344 if (!RTAvloGCPhysInsert(pTree, pNode))
345 {
346 RTTestIFailed("linear left insert i=%d\n", i);
347 return 1;
348 }
349 /* negative. */
350 AVLOGCPHYSNODECORE Node = *pNode;
351 if (RTAvloGCPhysInsert(pTree, &Node))
352 {
353 RTTestIFailed("linear left negative insert i=%d\n", i);
354 return 1;
355 }
356 }
357
358 ProgressPrintf(cMax, "~");
359 for (i = 0; i < cMax; i++)
360 {
361 Progress(i, cMax);
362 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
363 if (!pNode)
364 {
365 RTTestIFailed("linear left remove i=%d\n", i);
366 return 1;
367 }
368 memset(pNode, 0xcc, sizeof(*pNode));
369 RTMemFree(pNode);
370
371 /* negative */
372 pNode = RTAvloGCPhysRemove(pTree, i);
373 if (pNode)
374 {
375 RTTestIFailed("linear left negative remove i=%d\n", i);
376 return 1;
377 }
378 }
379
380 /*
381 * Simple linear insert and remove from the right.
382 */
383 if (cMax >= 10000)
384 RTTestISubF("oGCPhys(%d): linear right", cMax);
385 for (i = 0; i < cMax; i++)
386 {
387 Progress(i, cMax);
388 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
389 pNode->Key = i;
390 if (!RTAvloGCPhysInsert(pTree, pNode))
391 {
392 RTTestIFailed("linear right insert i=%d\n", i);
393 return 1;
394 }
395 /* negative. */
396 AVLOGCPHYSNODECORE Node = *pNode;
397 if (RTAvloGCPhysInsert(pTree, &Node))
398 {
399 RTTestIFailed("linear right negative insert i=%d\n", i);
400 return 1;
401 }
402 }
403
404 ProgressPrintf(cMax, "~");
405 while (i-- > 0)
406 {
407 Progress(i, cMax);
408 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
409 if (!pNode)
410 {
411 RTTestIFailed("linear right remove i=%d\n", i);
412 return 1;
413 }
414 memset(pNode, 0xcc, sizeof(*pNode));
415 RTMemFree(pNode);
416
417 /* negative */
418 pNode = RTAvloGCPhysRemove(pTree, i);
419 if (pNode)
420 {
421 RTTestIFailed("linear right negative remove i=%d\n", i);
422 return 1;
423 }
424 }
425
426 /*
427 * Linear insert but root based removal.
428 */
429 if (cMax >= 10000)
430 RTTestISubF("oGCPhys(%d): linear root", cMax);
431 for (i = 0; i < cMax; i++)
432 {
433 Progress(i, cMax);
434 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
435 pNode->Key = i;
436 if (!RTAvloGCPhysInsert(pTree, pNode))
437 {
438 RTTestIFailed("linear root insert i=%d\n", i);
439 return 1;
440 }
441 /* negative. */
442 AVLOGCPHYSNODECORE Node = *pNode;
443 if (RTAvloGCPhysInsert(pTree, &Node))
444 {
445 RTTestIFailed("linear root negative insert i=%d\n", i);
446 return 1;
447 }
448 }
449
450 ProgressPrintf(cMax, "~");
451 while (i-- > 0)
452 {
453 Progress(i, cMax);
454 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)((intptr_t)pTree + *pTree);
455 RTGCPHYS Key = pNode->Key;
456 pNode = RTAvloGCPhysRemove(pTree, Key);
457 if (!pNode)
458 {
459 RTTestIFailed("linear root remove i=%d Key=%d\n", i, (unsigned)Key);
460 return 1;
461 }
462 memset(pNode, 0xcc, sizeof(*pNode));
463 RTMemFree(pNode);
464
465 /* negative */
466 pNode = RTAvloGCPhysRemove(pTree, Key);
467 if (pNode)
468 {
469 RTTestIFailed("linear root negative remove i=%d Key=%d\n", i, (unsigned)Key);
470 return 1;
471 }
472 }
473 if (*pTree)
474 {
475 RTTestIFailed("sparse remove didn't remove it all!\n");
476 return 1;
477 }
478
479 /*
480 * Make a sparsely populated tree and remove the nodes using best fit in 5 cycles.
481 */
482 const unsigned cMaxSparse = RT_ALIGN(cMax, 32);
483 if (cMaxSparse >= 10000)
484 RTTestISubF("oGCPhys(%d): sparse", cMax);
485 for (i = 0; i < cMaxSparse; i += 8)
486 {
487 Progress(i, cMaxSparse);
488 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
489 pNode->Key = i;
490 if (!RTAvloGCPhysInsert(pTree, pNode))
491 {
492 RTTestIFailed("sparse insert i=%d\n", i);
493 return 1;
494 }
495 /* negative. */
496 AVLOGCPHYSNODECORE Node = *pNode;
497 if (RTAvloGCPhysInsert(pTree, &Node))
498 {
499 RTTestIFailed("sparse negative insert i=%d\n", i);
500 return 1;
501 }
502 }
503
504 /* Remove using best fit in 5 cycles. */
505 ProgressPrintf(cMaxSparse, "~");
506 unsigned j;
507 for (j = 0; j < 4; j++)
508 {
509 for (i = 0; i < cMaxSparse; i += 8 * 4)
510 {
511 Progress(i, cMax); // good enough
512 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemoveBestFit(pTree, i, true);
513 if (!pNode)
514 {
515 RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
516 return 1;
517 }
518 if (pNode->Key - (unsigned long)i >= 8 * 4)
519 {
520 RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)pNode->Key);
521 return 1;
522 }
523 memset(pNode, 0xdd, sizeof(*pNode));
524 RTMemFree(pNode);
525 }
526 }
527 if (*pTree)
528 {
529 RTTestIFailed("sparse remove didn't remove it all!\n");
530 return 1;
531 }
532 RTMemFree(pTree);
533 ProgressPrintf(cMaxSparse, "\n");
534 return 0;
535}
536
537
538int avlogcphysRand(unsigned cMax, unsigned cMax2)
539{
540 PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
541 unsigned i;
542
543 /*
544 * Random tree.
545 */
546 if (cMax >= 10000)
547 RTTestISubF("oGCPhys(%d, %d): random", cMax, cMax2);
548 PTRACKER pTracker = TrackerCreate(cMax2);
549 if (!pTracker)
550 {
551 RTTestIFailed("failed to create %d tracker!\n", cMax2);
552 return 1;
553 }
554
555 /* Insert a number of nodes in random order. */
556 for (i = 0; i < cMax; i++)
557 {
558 Progress(i, cMax);
559 uint32_t Key;
560 if (!TrackerNewRandom(pTracker, &Key))
561 {
562 RTTestIFailed("failed to allocate node no. %d\n", i);
563 TrackerDestroy(pTracker);
564 return 1;
565 }
566 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
567 pNode->Key = Key;
568 if (!RTAvloGCPhysInsert(pTree, pNode))
569 {
570 RTTestIFailed("random insert i=%d Key=%#x\n", i, Key);
571 return 1;
572 }
573 /* negative. */
574 AVLOGCPHYSNODECORE Node = *pNode;
575 if (RTAvloGCPhysInsert(pTree, &Node))
576 {
577 RTTestIFailed("linear negative insert i=%d Key=%#x\n", i, Key);
578 return 1;
579 }
580 TrackerInsert(pTracker, Key, Key);
581 }
582
583
584 /* delete the nodes in random order. */
585 ProgressPrintf(cMax, "~");
586 while (i-- > 0)
587 {
588 Progress(i, cMax);
589 uint32_t Key;
590 if (!TrackerFindRandom(pTracker, &Key))
591 {
592 RTTestIFailed("failed to find free node no. %d\n", i);
593 TrackerDestroy(pTracker);
594 return 1;
595 }
596
597 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, Key);
598 if (!pNode)
599 {
600 RTTestIFailed("random remove i=%d Key=%#x\n", i, Key);
601 return 1;
602 }
603 if (pNode->Key != Key)
604 {
605 RTTestIFailed("random remove i=%d Key=%#x pNode->Key=%#x\n", i, Key, (unsigned)pNode->Key);
606 return 1;
607 }
608 TrackerRemove(pTracker, Key, Key);
609 memset(pNode, 0xdd, sizeof(*pNode));
610 RTMemFree(pNode);
611 }
612 if (*pTree)
613 {
614 RTTestIFailed("random remove didn't remove it all!\n");
615 return 1;
616 }
617 ProgressPrintf(cMax, "\n");
618 TrackerDestroy(pTracker);
619 RTMemFree(pTree);
620 return 0;
621}
622
623
624
625int avlrogcphys(void)
626{
627 unsigned i;
628 unsigned j;
629 unsigned k;
630 PAVLROGCPHYSTREE pTree = (PAVLROGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
631
632 AssertCompileSize(AVLOGCPHYSNODECORE, 24);
633 AssertCompileSize(AVLROGCPHYSNODECORE, 32);
634
635 RTTestISubF("RTAvlroGCPhys");
636
637 /*
638 * Simple linear insert, get and remove.
639 */
640 /* insert */
641 for (i = 0; i < 65536; i += 4)
642 {
643 PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
644 pNode->Key = i;
645 pNode->KeyLast = i + 3;
646 if (!RTAvlroGCPhysInsert(pTree, pNode))
647 {
648 RTTestIFailed("linear insert i=%d\n", (unsigned)i);
649 return 1;
650 }
651
652 /* negative. */
653 AVLROGCPHYSNODECORE Node = *pNode;
654 for (j = i + 3; j > i - 32; j--)
655 {
656 for (k = i; k < i + 32; k++)
657 {
658 Node.Key = RT_MIN(j, k);
659 Node.KeyLast = RT_MAX(k, j);
660 if (RTAvlroGCPhysInsert(pTree, &Node))
661 {
662 RTTestIFailed("linear negative insert i=%d j=%d k=%d\n", i, j, k);
663 return 1;
664 }
665 }
666 }
667 }
668
669 /* do gets. */
670 for (i = 0; i < 65536; i += 4)
671 {
672 PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, i);
673 if (!pNode)
674 {
675 RTTestIFailed("linear get i=%d\n", i);
676 return 1;
677 }
678 if (pNode->Key > i || pNode->KeyLast < i)
679 {
680 RTTestIFailed("linear get i=%d Key=%d KeyLast=%d\n", i, (unsigned)pNode->Key, (unsigned)pNode->KeyLast);
681 return 1;
682 }
683
684 for (j = 0; j < 4; j++)
685 {
686 if (RTAvlroGCPhysRangeGet(pTree, i + j) != pNode)
687 {
688 RTTestIFailed("linear range get i=%d j=%d\n", i, j);
689 return 1;
690 }
691 }
692
693 /* negative. */
694 if ( RTAvlroGCPhysGet(pTree, i + 1)
695 || RTAvlroGCPhysGet(pTree, i + 2)
696 || RTAvlroGCPhysGet(pTree, i + 3))
697 {
698 RTTestIFailed("linear negative get i=%d + n\n", i);
699 return 1;
700 }
701
702 }
703
704 /* remove */
705 for (i = 0; i < 65536; i += 4)
706 {
707 PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysRemove(pTree, i);
708 if (!pNode)
709 {
710 RTTestIFailed("linear remove i=%d\n", i);
711 return 1;
712 }
713 memset(pNode, 0xcc, sizeof(*pNode));
714 RTMemFree(pNode);
715
716 /* negative */
717 if ( RTAvlroGCPhysRemove(pTree, i)
718 || RTAvlroGCPhysRemove(pTree, i + 1)
719 || RTAvlroGCPhysRemove(pTree, i + 2)
720 || RTAvlroGCPhysRemove(pTree, i + 3))
721 {
722 RTTestIFailed("linear negative remove i=%d + n\n", i);
723 return 1;
724 }
725 }
726
727 /*
728 * Make a sparsely populated tree.
729 */
730 for (i = 0; i < 65536; i += 8)
731 {
732 PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
733 pNode->Key = i;
734 pNode->KeyLast = i + 3;
735 if (!RTAvlroGCPhysInsert(pTree, pNode))
736 {
737 RTTestIFailed("sparse insert i=%d\n", i);
738 return 1;
739 }
740 /* negative. */
741 AVLROGCPHYSNODECORE Node = *pNode;
742 const RTGCPHYS jMin = i > 32 ? i - 32 : 1;
743 const RTGCPHYS kMax = i + 32;
744 for (j = pNode->KeyLast; j >= jMin; j--)
745 {
746 for (k = pNode->Key; k < kMax; k++)
747 {
748 Node.Key = RT_MIN(j, k);
749 Node.KeyLast = RT_MAX(k, j);
750 if (RTAvlroGCPhysInsert(pTree, &Node))
751 {
752 RTTestIFailed("sparse negative insert i=%d j=%d k=%d\n", i, j, k);
753 return 1;
754 }
755 }
756 }
757 }
758
759 /*
760 * Get and Remove using range matching in 5 cycles.
761 */
762 for (j = 0; j < 4; j++)
763 {
764 for (i = 0; i < 65536; i += 8 * 4)
765 {
766 /* gets */
767 RTGCPHYS KeyBase = i + j * 8;
768 PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, KeyBase);
769 if (!pNode)
770 {
771 RTTestIFailed("sparse get i=%d j=%d KeyBase=%d\n", i, j, (unsigned)KeyBase);
772 return 1;
773 }
774 if (pNode->Key > KeyBase || pNode->KeyLast < KeyBase)
775 {
776 RTTestIFailed("sparse get i=%d j=%d KeyBase=%d pNode->Key=%d\n", i, j, (unsigned)KeyBase, (unsigned)pNode->Key);
777 return 1;
778 }
779 for (k = KeyBase; k < KeyBase + 4; k++)
780 {
781 if (RTAvlroGCPhysRangeGet(pTree, k) != pNode)
782 {
783 RTTestIFailed("sparse range get i=%d j=%d k=%d\n", i, j, k);
784 return 1;
785 }
786 }
787
788 /* negative gets */
789 for (k = i + j; k < KeyBase + 8; k++)
790 {
791 if ( k != KeyBase
792 && RTAvlroGCPhysGet(pTree, k))
793 {
794 RTTestIFailed("sparse negative get i=%d j=%d k=%d\n", i, j, k);
795 return 1;
796 }
797 }
798 for (k = i + j; k < KeyBase; k++)
799 {
800 if (RTAvlroGCPhysRangeGet(pTree, k))
801 {
802 RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
803 return 1;
804 }
805 }
806 for (k = KeyBase + 4; k < KeyBase + 8; k++)
807 {
808 if (RTAvlroGCPhysRangeGet(pTree, k))
809 {
810 RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
811 return 1;
812 }
813 }
814
815 /* remove */
816 RTGCPHYS Key = KeyBase + ((i / 19) % 4);
817 if (RTAvlroGCPhysRangeRemove(pTree, Key) != pNode)
818 {
819 RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)Key);
820 return 1;
821 }
822 memset(pNode, 0xdd, sizeof(*pNode));
823 RTMemFree(pNode);
824 }
825 }
826 if (*pTree)
827 {
828 RTTestIFailed("sparse remove didn't remove it all!\n");
829 return 1;
830 }
831
832
833 /*
834 * Realworld testcase.
835 */
836 struct
837 {
838 AVLROGCPHYSTREE Tree;
839 AVLROGCPHYSNODECORE aNode[4];
840 } s1, s2, s3;
841 RT_ZERO(s1);
842 RT_ZERO(s2);
843 RT_ZERO(s3);
844
845 s1.aNode[0].Key = 0x00030000;
846 s1.aNode[0].KeyLast = 0x00030fff;
847 s1.aNode[1].Key = 0x000a0000;
848 s1.aNode[1].KeyLast = 0x000bffff;
849 s1.aNode[2].Key = 0xe0000000;
850 s1.aNode[2].KeyLast = 0xe03fffff;
851 s1.aNode[3].Key = 0xfffe0000;
852 s1.aNode[3].KeyLast = 0xfffe0ffe;
853 for (i = 0; i < RT_ELEMENTS(s1.aNode); i++)
854 {
855 PAVLROGCPHYSNODECORE pNode = &s1.aNode[i];
856 if (!RTAvlroGCPhysInsert(&s1.Tree, pNode))
857 {
858 RTTestIFailed("real insert i=%d\n", i);
859 return 1;
860 }
861 if (RTAvlroGCPhysInsert(&s1.Tree, pNode))
862 {
863 RTTestIFailed("real negative insert i=%d\n", i);
864 return 1;
865 }
866 if (RTAvlroGCPhysGet(&s1.Tree, pNode->Key) != pNode)
867 {
868 RTTestIFailed("real get (1) i=%d\n", i);
869 return 1;
870 }
871 if (RTAvlroGCPhysGet(&s1.Tree, pNode->KeyLast) != NULL)
872 {
873 RTTestIFailed("real negative get (2) i=%d\n", i);
874 return 1;
875 }
876 if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key) != pNode)
877 {
878 RTTestIFailed("real range get (1) i=%d\n", i);
879 return 1;
880 }
881 if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key + 1) != pNode)
882 {
883 RTTestIFailed("real range get (2) i=%d\n", i);
884 return 1;
885 }
886 if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->KeyLast) != pNode)
887 {
888 RTTestIFailed("real range get (3) i=%d\n", i);
889 return 1;
890 }
891 }
892
893 s3 = s1;
894 s1 = s2;
895 for (i = 0; i < RT_ELEMENTS(s3.aNode); i++)
896 {
897 PAVLROGCPHYSNODECORE pNode = &s3.aNode[i];
898 if (RTAvlroGCPhysGet(&s3.Tree, pNode->Key) != pNode)
899 {
900 RTTestIFailed("real get (10) i=%d\n", i);
901 return 1;
902 }
903 if (RTAvlroGCPhysRangeGet(&s3.Tree, pNode->Key) != pNode)
904 {
905 RTTestIFailed("real range get (10) i=%d\n", i);
906 return 1;
907 }
908
909 j = pNode->Key + 1;
910 do
911 {
912 if (RTAvlroGCPhysGet(&s3.Tree, j) != NULL)
913 {
914 RTTestIFailed("real negative get (11) i=%d j=%#x\n", i, j);
915 return 1;
916 }
917 if (RTAvlroGCPhysRangeGet(&s3.Tree, j) != pNode)
918 {
919 RTTestIFailed("real range get (11) i=%d j=%#x\n", i, j);
920 return 1;
921 }
922 } while (j++ < pNode->KeyLast);
923 }
924
925 return 0;
926}
927
928
929int avlul(void)
930{
931 RTTestISubF("RTAvlUL");
932
933 /*
934 * Simple linear insert and remove.
935 */
936 PAVLULNODECORE pTree = 0;
937 unsigned i;
938 /* insert */
939 for (i = 0; i < 65536; i++)
940 {
941 PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
942 pNode->Key = i;
943 if (!RTAvlULInsert(&pTree, pNode))
944 {
945 RTTestIFailed("linear insert i=%d\n", i);
946 return 1;
947 }
948 /* negative. */
949 AVLULNODECORE Node = *pNode;
950 if (RTAvlULInsert(&pTree, &Node))
951 {
952 RTTestIFailed("linear negative insert i=%d\n", i);
953 return 1;
954 }
955 }
956
957 for (i = 0; i < 65536; i++)
958 {
959 PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i);
960 if (!pNode)
961 {
962 RTTestIFailed("linear remove i=%d\n", i);
963 return 1;
964 }
965 pNode->pLeft = (PAVLULNODECORE)(uintptr_t)0xaaaaaaaa;
966 pNode->pRight = (PAVLULNODECORE)(uintptr_t)0xbbbbbbbb;
967 pNode->uchHeight = 'e';
968 RTMemFree(pNode);
969
970 /* negative */
971 pNode = RTAvlULRemove(&pTree, i);
972 if (pNode)
973 {
974 RTTestIFailed("linear negative remove i=%d\n", i);
975 return 1;
976 }
977 }
978
979 /*
980 * Make a sparsely populated tree.
981 */
982 for (i = 0; i < 65536; i += 8)
983 {
984 PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
985 pNode->Key = i;
986 if (!RTAvlULInsert(&pTree, pNode))
987 {
988 RTTestIFailed("linear insert i=%d\n", i);
989 return 1;
990 }
991 /* negative. */
992 AVLULNODECORE Node = *pNode;
993 if (RTAvlULInsert(&pTree, &Node))
994 {
995 RTTestIFailed("linear negative insert i=%d\n", i);
996 return 1;
997 }
998 }
999
1000 /*
1001 * Remove using best fit in 5 cycles.
1002 */
1003 unsigned j;
1004 for (j = 0; j < 4; j++)
1005 {
1006 for (i = 0; i < 65536; i += 8 * 4)
1007 {
1008 PAVLULNODECORE pNode = RTAvlULRemoveBestFit(&pTree, i, true);
1009 //PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i + j * 8);
1010 if (!pNode)
1011 {
1012 RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
1013 return 1;
1014 }
1015 pNode->pLeft = (PAVLULNODECORE)(uintptr_t)0xdddddddd;
1016 pNode->pRight = (PAVLULNODECORE)(uintptr_t)0xcccccccc;
1017 pNode->uchHeight = 'E';
1018 RTMemFree(pNode);
1019 }
1020 }
1021
1022 return 0;
1023}
1024
1025
1026int main()
1027{
1028 /*
1029 * Init.
1030 */
1031 RTTEST hTest;
1032 int rc = RTTestInitAndCreate("tstRTAvl", &hTest);
1033 if (rc)
1034 return rc;
1035 RTTestBanner(hTest);
1036 g_hTest = hTest;
1037
1038 rc = RTRandAdvCreateParkMiller(&g_hRand);
1039 if (RT_FAILURE(rc))
1040 {
1041 RTTestIFailed("RTRandAdvCreateParkMiller -> %Rrc", rc);
1042 return RTTestSummaryAndDestroy(hTest);
1043 }
1044
1045 /*
1046 * Testing.
1047 */
1048 unsigned i;
1049 RTTestSub(hTest, "oGCPhys(32..2048)");
1050 for (i = 32; i < 2048; i++)
1051 if (avlogcphys(i))
1052 break;
1053
1054 avlogcphys(_64K);
1055 avlogcphys(_512K);
1056 avlogcphys(_4M);
1057
1058 RTTestISubF("oGCPhys(32..2048, *1K)");
1059 for (i = 32; i < 4096; i++)
1060 if (avlogcphysRand(i, i + _1K))
1061 break;
1062 for (; i <= _4M; i *= 2)
1063 if (avlogcphysRand(i, i * 8))
1064 break;
1065
1066 avlrogcphys();
1067 avlul();
1068
1069 /*
1070 * Done.
1071 */
1072 return RTTestSummaryAndDestroy(hTest);
1073}
1074
Note: See TracBrowser for help on using the repository browser.

© 2023 Oracle
Contact – Privacy policy – Terms of Use