VirtualBox

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

Last change on this file since 3125 was 2981, checked in by vboxsync, 17 years ago

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