VirtualBox

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

Last change on this file since 53428 was 48935, checked in by vboxsync, 11 years ago

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