VirtualBox

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

Last change on this file since 4953 was 4071, checked in by vboxsync, 17 years ago

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