VirtualBox

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

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

tstAvl -> tstRTAvl; use RTTest.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 29.5 KB
Line 
1/* $Id: tstRTAvl.cpp 19945 2009-05-23 21:48:25Z vboxsync $ */
2/** @file
3 * IPRT Testcase - AVL trees.
4 */
5
6/*
7 * Copyright (C) 2006-2009 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* Header Files *
33*******************************************************************************/
34#include <iprt/avl.h>
35
36#include <iprt/asm.h>
37#include <iprt/initterm.h>
38#include <iprt/mem.h>
39#include <iprt/rand.h>
40#include <iprt/stdarg.h>
41#include <iprt/string.h>
42#include <iprt/test.h>
43
44
45/*******************************************************************************
46* Structures and Typedefs *
47*******************************************************************************/
48typedef struct TRACKER
49{
50 /** The max key value (exclusive). */
51 uint32_t MaxKey;
52 /** The last allocated key. */
53 uint32_t LastAllocatedKey;
54 /** The number of set bits in the bitmap. */
55 uint32_t cSetBits;
56 /** The bitmap size. */
57 uint32_t cbBitmap;
58 /** Bitmap containing the allocated nodes. */
59 uint8_t abBitmap[1];
60} TRACKER, *PTRACKER;
61
62
63/*******************************************************************************
64* Global Variables *
65*******************************************************************************/
66static RTTEST g_hTest;
67static RTRAND g_hRand;
68
69
70/**
71 * Creates a new tracker.
72 *
73 * @returns Pointer to the new tracker.
74 * @param MaxKey The max key value for the tracker. (exclusive)
75 */
76static PTRACKER TrackerCreate(uint32_t MaxKey)
77{
78 uint32_t cbBitmap = (MaxKey + sizeof(uint32_t) * sizeof(uint8_t) - 1) / sizeof(uint8_t);
79 PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_OFFSETOF(TRACKER, abBitmap[cbBitmap]));
80 if (pTracker)
81 {
82 pTracker->MaxKey = MaxKey;
83 pTracker->LastAllocatedKey = MaxKey;
84 pTracker->cbBitmap = cbBitmap;
85 Assert(pTracker->cSetBits == 0);
86 }
87 return pTracker;
88}
89
90
91/**
92 * Destroys a tracker.
93 *
94 * @param pTracker The tracker.
95 */
96static void TrackerDestroy(PTRACKER pTracker)
97{
98 RTMemFree(pTracker);
99}
100
101
102/**
103 * Inserts a key range into the tracker.
104 *
105 * @returns success indicator.
106 * @param pTracker The tracker.
107 * @param Key The first key in the range.
108 * @param KeyLast The last key in the range. (inclusive)
109 */
110static bool TrackerInsert(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
111{
112 bool fRc = !ASMBitTestAndSet(pTracker->abBitmap, Key);
113 if (fRc)
114 pTracker->cSetBits++;
115 while (KeyLast != Key)
116 {
117 if (!ASMBitTestAndSet(pTracker->abBitmap, KeyLast))
118 pTracker->cSetBits++;
119 else
120 fRc = false;
121 KeyLast--;
122 }
123 return fRc;
124}
125
126
127/**
128 * Removes a key range from the tracker.
129 *
130 * @returns success indicator.
131 * @param pTracker The tracker.
132 * @param Key The first key in the range.
133 * @param KeyLast The last key in the range. (inclusive)
134 */
135static bool TrackerRemove(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
136{
137 bool fRc = ASMBitTestAndClear(pTracker->abBitmap, Key);
138 if (fRc)
139 pTracker->cSetBits--;
140 while (KeyLast != Key)
141 {
142 if (ASMBitTestAndClear(pTracker->abBitmap, KeyLast))
143 pTracker->cSetBits--;
144 else
145 fRc = false;
146 KeyLast--;
147 }
148 return fRc;
149}
150
151
152/**
153 * Random key range allocation.
154 *
155 * @returns success indicator.
156 * @param pTracker The tracker.
157 * @param pKey Where to store the first key in the allocated range.
158 * @param pKeyLast Where to store the first key in the allocated range.
159 * @param cMaxKey The max range length.
160 * @remark The caller has to call TrackerInsert.
161 */
162static bool TrackerNewRandomEx(PTRACKER pTracker, uint32_t *pKey, uint32_t *pKeyLast, uint32_t cMaxKeys)
163{
164 /*
165 * Find a key.
166 */
167 uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
168 if (ASMBitTest(pTracker->abBitmap, Key))
169 {
170 if (pTracker->cSetBits >= pTracker->MaxKey)
171 return false;
172
173 int Key2 = ASMBitNextClear(pTracker->abBitmap, pTracker->MaxKey, Key);
174 if (Key2 > 0)
175 Key = Key2;
176 else
177 {
178 /* we're missing a ASMBitPrevClear function, so just try another, lower, value.*/
179 for (;;)
180 {
181 const uint32_t KeyPrev = Key;
182 Key = RTRandAdvU32Ex(g_hRand, 0, KeyPrev - 1);
183 if (!ASMBitTest(pTracker->abBitmap, Key))
184 break;
185 Key2 = ASMBitNextClear(pTracker->abBitmap, RT_ALIGN_32(KeyPrev, 32), Key);
186 if (Key2 > 0)
187 {
188 Key = Key2;
189 break;
190 }
191 }
192 }
193 }
194
195 /*
196 * Determin the range.
197 */
198 uint32_t KeyLast;
199 if (cMaxKeys == 1 || !pKeyLast)
200 KeyLast = Key;
201 else
202 {
203 uint32_t cKeys = RTRandAdvU32Ex(g_hRand, 0, RT_MIN(pTracker->MaxKey - Key, cMaxKeys - 1));
204 KeyLast = Key + cKeys;
205 int Key2 = ASMBitNextSet(pTracker->abBitmap, RT_ALIGN_32(KeyLast, 32), Key);
206 if ( Key2 > 0
207 && (unsigned)Key2 <= KeyLast)
208 KeyLast = Key2 - 1;
209 }
210
211 /*
212 * Return.
213 */
214 *pKey = Key;
215 if (pKeyLast)
216 *pKeyLast = KeyLast;
217 return true;
218}
219
220
221/**
222 * Random single key allocation.
223 *
224 * @returns success indicator.
225 * @param pTracker The tracker.
226 * @param pKey Where to store the allocated key.
227 * @remark The caller has to call TrackerInsert.
228 */
229static bool TrackerNewRandom(PTRACKER pTracker, uint32_t *pKey)
230{
231 return TrackerNewRandomEx(pTracker, pKey, NULL, 1);
232}
233
234
235/**
236 * Random single key 'lookup'.
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 TrackerRemove.
242 */
243static bool TrackerFindRandom(PTRACKER pTracker, uint32_t *pKey)
244{
245 uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
246 if (!ASMBitTest(pTracker->abBitmap, Key))
247 {
248 if (!pTracker->cSetBits)
249 return false;
250
251 int Key2 = ASMBitNextSet(pTracker->abBitmap, pTracker->MaxKey, Key);
252 if (Key2 > 0)
253 Key = Key2;
254 else
255 {
256 /* we're missing a ASMBitPrevSet function, so here's a quick replacement hack. */
257 uint32_t *pu32Start = (uint32_t *)&pTracker->abBitmap[0];
258 uint32_t *pu32Cur = (uint32_t *)&pTracker->abBitmap[Key >> 8];
259 while (pu32Cur >= pu32Start)
260 {
261 if (*pu32Cur)
262 {
263 *pKey = ASMBitLastSetU32(*pu32Cur) - 1 + (uint32_t)((pu32Cur - pu32Start) * 32);
264 return true;
265 }
266 pu32Cur--;
267 }
268 Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
269 if (Key2 == -1)
270 {
271 RTTestIFailed("cSetBits=%u - but ASMBitFirstSet failed to find any", pTracker->cSetBits);
272 return false;
273 }
274 Key = Key2;
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 */
294static void ProgressChar(char ch)
295{
296 //RTTestIPrintf(RTTESTLVL_INFO, "%c", ch);
297 RTTestIPrintf(RTTESTLVL_SUB_TEST, "%c", ch);
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
311 va_list va;
312 va_start(va, pszFormat);
313 //RTTestIPrintfV(RTTESTLVL_INFO, pszFormat, va);
314 RTTestIPrintfV(RTTESTLVL_SUB_TEST, pszFormat, va);
315 va_end(va);
316}
317
318
319/**
320 * Prints a progress indicator dot.
321 * @param iCur The current operation. (can be decending too)
322 * @param cMax The max number of operations (exclusive).
323 */
324DECLINLINE(void) Progress(unsigned iCur, unsigned cMax)
325{
326 if (cMax < 10000)
327 return;
328 if (!(iCur % (cMax / 20)))
329 ProgressChar('.');
330}
331
332
333static int avlogcphys(unsigned cMax)
334{
335 /*
336 * Simple linear insert and remove.
337 */
338 if (cMax >= 10000)
339 RTTestISubF("oGCPhys(%d): linear left", cMax);
340 PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
341 unsigned i;
342 for (i = 0; i < cMax; i++)
343 {
344 Progress(i, cMax);
345 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
346 pNode->Key = i;
347 if (!RTAvloGCPhysInsert(pTree, pNode))
348 {
349 RTTestIFailed("linear left insert i=%d\n", i);
350 return 1;
351 }
352 /* negative. */
353 AVLOGCPHYSNODECORE Node = *pNode;
354 if (RTAvloGCPhysInsert(pTree, &Node))
355 {
356 RTTestIFailed("linear left negative insert i=%d\n", i);
357 return 1;
358 }
359 }
360
361 ProgressPrintf(cMax, "~");
362 for (i = 0; i < cMax; i++)
363 {
364 Progress(i, cMax);
365 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
366 if (!pNode)
367 {
368 RTTestIFailed("linear left remove i=%d\n", i);
369 return 1;
370 }
371 memset(pNode, 0xcc, sizeof(*pNode));
372 RTMemFree(pNode);
373
374 /* negative */
375 pNode = RTAvloGCPhysRemove(pTree, i);
376 if (pNode)
377 {
378 RTTestIFailed("linear left negative remove i=%d\n", i);
379 return 1;
380 }
381 }
382
383 /*
384 * Simple linear insert and remove from the right.
385 */
386 if (cMax >= 10000)
387 RTTestISubF("oGCPhys(%d): linear right", cMax);
388 for (i = 0; i < cMax; i++)
389 {
390 Progress(i, cMax);
391 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
392 pNode->Key = i;
393 if (!RTAvloGCPhysInsert(pTree, pNode))
394 {
395 RTTestIFailed("linear right insert i=%d\n", i);
396 return 1;
397 }
398 /* negative. */
399 AVLOGCPHYSNODECORE Node = *pNode;
400 if (RTAvloGCPhysInsert(pTree, &Node))
401 {
402 RTTestIFailed("linear right negative insert i=%d\n", i);
403 return 1;
404 }
405 }
406
407 ProgressPrintf(cMax, "~");
408 while (i-- > 0)
409 {
410 Progress(i, cMax);
411 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
412 if (!pNode)
413 {
414 RTTestIFailed("linear right remove i=%d\n", i);
415 return 1;
416 }
417 memset(pNode, 0xcc, sizeof(*pNode));
418 RTMemFree(pNode);
419
420 /* negative */
421 pNode = RTAvloGCPhysRemove(pTree, i);
422 if (pNode)
423 {
424 RTTestIFailed("linear right negative remove i=%d\n", i);
425 return 1;
426 }
427 }
428
429 /*
430 * Linear insert but root based removal.
431 */
432 if (cMax >= 10000)
433 RTTestISubF("oGCPhys(%d): linear root", cMax);
434 for (i = 0; i < cMax; i++)
435 {
436 Progress(i, cMax);
437 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
438 pNode->Key = i;
439 if (!RTAvloGCPhysInsert(pTree, pNode))
440 {
441 RTTestIFailed("linear root insert i=%d\n", i);
442 return 1;
443 }
444 /* negative. */
445 AVLOGCPHYSNODECORE Node = *pNode;
446 if (RTAvloGCPhysInsert(pTree, &Node))
447 {
448 RTTestIFailed("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 RTTestIFailed("linear root remove i=%d Key=%d\n", i, (unsigned)Key);
463 return 1;
464 }
465 memset(pNode, 0xcc, sizeof(*pNode));
466 RTMemFree(pNode);
467
468 /* negative */
469 pNode = RTAvloGCPhysRemove(pTree, Key);
470 if (pNode)
471 {
472 RTTestIFailed("linear root negative remove i=%d Key=%d\n", i, (unsigned)Key);
473 return 1;
474 }
475 }
476 if (*pTree)
477 {
478 RTTestIFailed("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 if (cMaxSparse >= 10000)
487 RTTestISubF("oGCPhys(%d): sparse", cMax);
488 for (i = 0; i < cMaxSparse; i += 8)
489 {
490 Progress(i, cMaxSparse);
491 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
492 pNode->Key = i;
493 if (!RTAvloGCPhysInsert(pTree, pNode))
494 {
495 RTTestIFailed("sparse insert i=%d\n", i);
496 return 1;
497 }
498 /* negative. */
499 AVLOGCPHYSNODECORE Node = *pNode;
500 if (RTAvloGCPhysInsert(pTree, &Node))
501 {
502 RTTestIFailed("sparse negative insert i=%d\n", i);
503 return 1;
504 }
505 }
506
507 /* Remove using best fit in 5 cycles. */
508 ProgressPrintf(cMaxSparse, "~");
509 unsigned j;
510 for (j = 0; j < 4; j++)
511 {
512 for (i = 0; i < cMaxSparse; i += 8 * 4)
513 {
514 Progress(i, cMax); // good enough
515 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemoveBestFit(pTree, i, true);
516 if (!pNode)
517 {
518 RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
519 return 1;
520 }
521 if (pNode->Key - (unsigned long)i >= 8 * 4)
522 {
523 RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)pNode->Key);
524 return 1;
525 }
526 memset(pNode, 0xdd, sizeof(*pNode));
527 RTMemFree(pNode);
528 }
529 }
530 if (*pTree)
531 {
532 RTTestIFailed("sparse remove didn't remove it all!\n");
533 return 1;
534 }
535 RTMemFree(pTree);
536 ProgressPrintf(cMaxSparse, "\n");
537 return 0;
538}
539
540
541int avlogcphysRand(unsigned cMax, unsigned cMax2)
542{
543 PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
544 unsigned i;
545
546 /*
547 * Random tree.
548 */
549 if (cMax >= 10000)
550 RTTestISubF("oGCPhys(%d, %d): random", cMax, cMax2);
551 PTRACKER pTracker = TrackerCreate(cMax2);
552 if (!pTracker)
553 {
554 RTTestIFailed("failed to create %d tracker!\n", cMax2);
555 return 1;
556 }
557
558 /* Insert a number of nodes in random order. */
559 for (i = 0; i < cMax; i++)
560 {
561 Progress(i, cMax);
562 uint32_t Key;
563 if (!TrackerNewRandom(pTracker, &Key))
564 {
565 RTTestIFailed("failed to allocate node no. %d\n", i);
566 TrackerDestroy(pTracker);
567 return 1;
568 }
569 PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
570 pNode->Key = Key;
571 if (!RTAvloGCPhysInsert(pTree, pNode))
572 {
573 RTTestIFailed("random insert i=%d Key=%#x\n", i, Key);
574 return 1;
575 }
576 /* negative. */
577 AVLOGCPHYSNODECORE Node = *pNode;
578 if (RTAvloGCPhysInsert(pTree, &Node))
579 {
580 RTTestIFailed("linear negative insert i=%d Key=%#x\n", i, Key);
581 return 1;
582 }
583 TrackerInsert(pTracker, Key, Key);
584 }
585
586
587 /* delete the nodes in random order. */
588 ProgressPrintf(cMax, "~");
589 while (i-- > 0)
590 {
591 Progress(i, cMax);
592 uint32_t Key;
593 if (!TrackerFindRandom(pTracker, &Key))
594 {
595 RTTestIFailed("failed to find free node no. %d\n", i);
596 TrackerDestroy(pTracker);
597 return 1;
598 }
599
600 PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, Key);
601 if (!pNode)
602 {
603 RTTestIFailed("random remove i=%d Key=%#x\n", i, Key);
604 return 1;
605 }
606 if (pNode->Key != Key)
607 {
608 RTTestIFailed("random remove i=%d Key=%#x pNode->Key=%#x\n", i, Key, (unsigned)pNode->Key);
609 return 1;
610 }
611 TrackerRemove(pTracker, Key, Key);
612 memset(pNode, 0xdd, sizeof(*pNode));
613 RTMemFree(pNode);
614 }
615 if (*pTree)
616 {
617 RTTestIFailed("random remove didn't remove it all!\n");
618 return 1;
619 }
620 ProgressPrintf(cMax, "\n");
621 TrackerDestroy(pTracker);
622 RTMemFree(pTree);
623 return 0;
624}
625
626
627
628int avlrogcphys(void)
629{
630 unsigned i;
631 unsigned j;
632 unsigned k;
633 PAVLROGCPHYSTREE pTree = (PAVLROGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
634
635 AssertCompileSize(AVLOGCPHYSNODECORE, 24);
636 AssertCompileSize(AVLROGCPHYSNODECORE, 32);
637
638 RTTestISubF("RTAvlroGCPhys");
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)RTMemAlloc(sizeof(*pNode));
647 pNode->Key = i;
648 pNode->KeyLast = i + 3;
649 if (!RTAvlroGCPhysInsert(pTree, pNode))
650 {
651 RTTestIFailed("linear insert i=%d\n", (unsigned)i);
652 return 1;
653 }
654
655 /* negative. */
656 AVLROGCPHYSNODECORE Node = *pNode;
657 for (j = i + 3; 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 RTTestIFailed("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 RTTestIFailed("linear get i=%d\n", i);
679 return 1;
680 }
681 if (pNode->Key > i || pNode->KeyLast < i)
682 {
683 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("linear remove i=%d\n", i);
714 return 1;
715 }
716 memset(pNode, 0xcc, sizeof(*pNode));
717 RTMemFree(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 RTTestIFailed("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)RTMemAlloc(sizeof(*pNode));
736 pNode->Key = i;
737 pNode->KeyLast = i + 3;
738 if (!RTAvlroGCPhysInsert(pTree, pNode))
739 {
740 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("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 RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)Key);
823 return 1;
824 }
825 memset(pNode, 0xdd, sizeof(*pNode));
826 RTMemFree(pNode);
827 }
828 }
829 if (*pTree)
830 {
831 RTTestIFailed("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 RTTestIFailed("real insert i=%d\n", i);
859 return 1;
860 }
861 if (RTAvlroGCPhysInsert(&s1.Tree, pNode))
862 {
863 RTTestIFailed("real negative insert i=%d\n", i);
864 return 1;
865 }
866 if (RTAvlroGCPhysGet(&s1.Tree, pNode->Key) != pNode)
867 {
868 RTTestIFailed("real get (1) i=%d\n", i);
869 return 1;
870 }
871 if (RTAvlroGCPhysGet(&s1.Tree, pNode->KeyLast) != NULL)
872 {
873 RTTestIFailed("real negative get (2) i=%d\n", i);
874 return 1;
875 }
876 if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key) != pNode)
877 {
878 RTTestIFailed("real range get (1) i=%d\n", i);
879 return 1;
880 }
881 if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key + 1) != pNode)
882 {
883 RTTestIFailed("real range get (2) i=%d\n", i);
884 return 1;
885 }
886 if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->KeyLast) != pNode)
887 {
888 RTTestIFailed("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 RTTestIFailed("real get (10) i=%d\n", i);
901 return 1;
902 }
903 if (RTAvlroGCPhysRangeGet(&s3.Tree, pNode->Key) != pNode)
904 {
905 RTTestIFailed("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 RTTestIFailed("real negative get (11) i=%d j=%#x\n", i, j);
915 return 1;
916 }
917 if (RTAvlroGCPhysRangeGet(&s3.Tree, j) != pNode)
918 {
919 RTTestIFailed("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 RTTestISubF("RTAvlUL");
932
933 /*
934 * Simple linear insert and remove.
935 */
936 PAVLULNODECORE pTree = 0;
937 unsigned i;
938 /* insert */
939 for (i = 0; i < 65536; i++)
940 {
941 PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
942 pNode->Key = i;
943 if (!RTAvlULInsert(&pTree, pNode))
944 {
945 RTTestIFailed("linear insert i=%d\n", i);
946 return 1;
947 }
948 /* negative. */
949 AVLULNODECORE Node = *pNode;
950 if (RTAvlULInsert(&pTree, &Node))
951 {
952 RTTestIFailed("linear negative insert i=%d\n", i);
953 return 1;
954 }
955 }
956
957 for (i = 0; i < 65536; i++)
958 {
959 PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i);
960 if (!pNode)
961 {
962 RTTestIFailed("linear remove i=%d\n", i);
963 return 1;
964 }
965 pNode->pLeft = (PAVLULNODECORE)0xaaaaaaaa;
966 pNode->pRight = (PAVLULNODECORE)0xbbbbbbbb;
967 pNode->uchHeight = 'e';
968 RTMemFree(pNode);
969
970 /* negative */
971 pNode = RTAvlULRemove(&pTree, i);
972 if (pNode)
973 {
974 RTTestIFailed("linear negative remove i=%d\n", i);
975 return 1;
976 }
977 }
978
979 /*
980 * Make a sparsely populated tree.
981 */
982 for (i = 0; i < 65536; i += 8)
983 {
984 PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
985 pNode->Key = i;
986 if (!RTAvlULInsert(&pTree, pNode))
987 {
988 RTTestIFailed("linear insert i=%d\n", i);
989 return 1;
990 }
991 /* negative. */
992 AVLULNODECORE Node = *pNode;
993 if (RTAvlULInsert(&pTree, &Node))
994 {
995 RTTestIFailed("linear negative insert i=%d\n", i);
996 return 1;
997 }
998 }
999
1000 /*
1001 * Remove using best fit in 5 cycles.
1002 */
1003 unsigned j;
1004 for (j = 0; j < 4; j++)
1005 {
1006 for (i = 0; i < 65536; i += 8 * 4)
1007 {
1008 PAVLULNODECORE pNode = RTAvlULRemoveBestFit(&pTree, i, true);
1009 //PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i + j * 8);
1010 if (!pNode)
1011 {
1012 RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
1013 return 1;
1014 }
1015 pNode->pLeft = (PAVLULNODECORE)0xdddddddd;
1016 pNode->pRight = (PAVLULNODECORE)0xcccccccc;
1017 pNode->uchHeight = 'E';
1018 RTMemFree(pNode);
1019 }
1020 }
1021
1022 return 0;
1023}
1024
1025
1026int main()
1027{
1028 /*
1029 * Init.
1030 */
1031 int rc = RTR3Init();
1032 if (RT_FAILURE(rc))
1033 return 1;
1034
1035 RTTEST hTest;
1036 rc = RTTestCreate("tstRTAvl", &hTest);
1037 if (RT_FAILURE(rc))
1038 return 1;
1039 g_hTest = hTest;
1040 RTTestBanner(hTest);
1041
1042 rc = RTRandAdvCreateParkMiller(&g_hRand);
1043 if (RT_FAILURE(rc))
1044 {
1045 RTTestIFailed("RTRandAdvCreateParkMiller -> %Rrc", rc);
1046 return RTTestSummaryAndDestroy(hTest);
1047 }
1048
1049 /*
1050 * Testing.
1051 */
1052 unsigned i;
1053 RTTestSub(hTest, "oGCPhys(32..2048)");
1054 for (i = 32; i < 2048; i++)
1055 if (avlogcphys(i))
1056 break;
1057
1058 avlogcphys(_64K);
1059 avlogcphys(_512K);
1060 avlogcphys(_4M);
1061
1062 RTTestISubF("oGCPhys(32..2048, *1K)");
1063 for (i = 32; i < 4096; i++)
1064 if (avlogcphysRand(i, i + _1K))
1065 break;
1066 for (; i <= _4M; i *= 2)
1067 if (avlogcphysRand(i, i * 8))
1068 break;
1069
1070 avlrogcphys();
1071 avlul();
1072
1073 /*
1074 * Done.
1075 */
1076 return RTTestSummaryAndDestroy(hTest);
1077}
1078
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