VirtualBox

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

Last change on this file since 14534 was 13836, checked in by vboxsync, 16 years ago

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