← Back to branch summary

~ubuntu-branches/ubuntu/trusty/virtualbox-lts-xenial/trusty-proposed

« back to all changes in this revision

Viewing changes to src/VBox/Runtime/testcase/tstRTAvl.cpp

  • Committer: Package Import Robot
  • Author(s): Gianfranco Costamagna
  • Date: 2016-02-23 14:28:26 UTC
  • Revision ID: package-import@ubuntu.com-20160223142826-bdu69el2z6wa2a44
Tags: upstream-4.3.36-dfsg
Import upstream version 4.3.36-dfsg

Show diffs side-by-side

added added

removed removed

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