VirtualBox

source: vbox/trunk/src/VBox/Runtime/testcase/tstAvl.cpp@ 6677

Last change on this file since 6677 was 5999, checked in by vboxsync, 17 years ago

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