Runtime/testcase/tstRTAvl.cpp

/* $Id$ */
/** @file
 * IPRT Testcase - AVL trees.
 */

/*
 * Copyright (C) 2006-2010 Oracle Corporation
 *
 * This file is part of VirtualBox Open Source Edition (OSE), as
 * available from http://www.virtualbox.org. This file is free software;
 * you can redistribute it and/or modify it under the terms of the GNU
 * General Public License (GPL) as published by the Free Software
 * Foundation, in version 2 as it comes in the "COPYING" file of the
 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
 *
 * The contents of this file may alternatively be used under the terms
 * of the Common Development and Distribution License Version 1.0
 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
 * VirtualBox OSE distribution, in which case the provisions of the
 * CDDL are applicable instead of those of the GPL.
 *
 * You may elect to license modified versions of this file under the
 * terms and conditions of either the GPL or the CDDL or both.
 */

/*******************************************************************************
*   Header Files                                                               *
*******************************************************************************/
#include <iprt/avl.h>

#include <iprt/asm.h>
#include <iprt/initterm.h>
#include <iprt/mem.h>
#include <iprt/rand.h>
#include <iprt/stdarg.h>
#include <iprt/string.h>
#include <iprt/test.h>


/*******************************************************************************
*   Structures and Typedefs                                                    *
*******************************************************************************/
typedef struct TRACKER
{
    /** The max key value (exclusive). */
    uint32_t    MaxKey;
    /** The last allocated key. */
    uint32_t    LastAllocatedKey;
    /** The number of set bits in the bitmap. */
    uint32_t    cSetBits;
    /** The bitmap size. */
    uint32_t    cbBitmap;
    /** Bitmap containing the allocated nodes. */
    uint8_t     abBitmap[1];
} TRACKER, *PTRACKER;


/*******************************************************************************
*   Global Variables                                                           *
*******************************************************************************/
static RTTEST g_hTest;
static RTRAND g_hRand;


/**
 * Creates a new tracker.
 *
 * @returns Pointer to the new tracker.
 * @param   MaxKey      The max key value for the tracker. (exclusive)
 */
static PTRACKER TrackerCreate(uint32_t MaxKey)
{
    uint32_t cbBitmap = (MaxKey + sizeof(uint32_t) * sizeof(uint8_t) - 1) / sizeof(uint8_t);
    PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_OFFSETOF(TRACKER, abBitmap[cbBitmap]));
    if (pTracker)
    {
        pTracker->MaxKey = MaxKey;
        pTracker->LastAllocatedKey = MaxKey;
        pTracker->cbBitmap = cbBitmap;
        Assert(pTracker->cSetBits == 0);
    }
    return pTracker;
}


/**
 * Destroys a tracker.
 *
 * @param   pTracker        The tracker.
 */
static void TrackerDestroy(PTRACKER pTracker)
{
    RTMemFree(pTracker);
}


/**
 * Inserts a key range into the tracker.
 *
 * @returns success indicator.
 * @param   pTracker    The tracker.
 * @param   Key         The first key in the range.
 * @param   KeyLast     The last key in the range. (inclusive)
 */
static bool TrackerInsert(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
{
    bool fRc = !ASMBitTestAndSet(pTracker->abBitmap, Key);
    if (fRc)
        pTracker->cSetBits++;
    while (KeyLast != Key)
    {
        if (!ASMBitTestAndSet(pTracker->abBitmap, KeyLast))
            pTracker->cSetBits++;
        else
            fRc = false;
        KeyLast--;
    }
    return fRc;
}


/**
 * Removes a key range from the tracker.
 *
 * @returns success indicator.
 * @param   pTracker    The tracker.
 * @param   Key         The first key in the range.
 * @param   KeyLast     The last key in the range. (inclusive)
 */
static bool TrackerRemove(PTRACKER pTracker, uint32_t Key, uint32_t KeyLast)
{
    bool fRc = ASMBitTestAndClear(pTracker->abBitmap, Key);
    if (fRc)
        pTracker->cSetBits--;
    while (KeyLast != Key)
    {
        if (ASMBitTestAndClear(pTracker->abBitmap, KeyLast))
            pTracker->cSetBits--;
        else
            fRc = false;
        KeyLast--;
    }
    return fRc;
}


/**
 * Random key range allocation.
 *
 * @returns success indicator.
 * @param   pTracker    The tracker.
 * @param   pKey        Where to store the first key in the allocated range.
 * @param   pKeyLast    Where to store the first key in the allocated range.
 * @param   cMaxKey     The max range length.
 * @remark  The caller has to call TrackerInsert.
 */
static bool TrackerNewRandomEx(PTRACKER pTracker, uint32_t *pKey, uint32_t *pKeyLast, uint32_t cMaxKeys)
{
    /*
     * Find a key.
     */
    uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
    if (ASMBitTest(pTracker->abBitmap, Key))
    {
        if (pTracker->cSetBits >= pTracker->MaxKey)
            return false;

        int Key2 = ASMBitNextClear(pTracker->abBitmap, pTracker->MaxKey, Key);
        if (Key2 > 0)
            Key = Key2;
        else
        {
            /* we're missing a ASMBitPrevClear function, so just try another, lower, value.*/
            for (;;)
            {
                const uint32_t KeyPrev = Key;
                Key = RTRandAdvU32Ex(g_hRand, 0, KeyPrev - 1);
                if (!ASMBitTest(pTracker->abBitmap, Key))
                    break;
                Key2 = ASMBitNextClear(pTracker->abBitmap, RT_ALIGN_32(KeyPrev, 32), Key);
                if (Key2 > 0)
                {
                    Key = Key2;
                    break;
                }
            }
        }
    }

    /*
     * Determine the range.
     */
    uint32_t KeyLast;
    if (cMaxKeys == 1 || !pKeyLast)
        KeyLast = Key;
    else
    {
        uint32_t cKeys = RTRandAdvU32Ex(g_hRand, 0, RT_MIN(pTracker->MaxKey - Key, cMaxKeys - 1));
        KeyLast = Key + cKeys;
        int Key2 = ASMBitNextSet(pTracker->abBitmap, RT_ALIGN_32(KeyLast, 32), Key);
        if (    Key2 > 0
            &&  (unsigned)Key2 <= KeyLast)
            KeyLast = Key2 - 1;
    }

    /*
     * Return.
     */
    *pKey = Key;
    if (pKeyLast)
        *pKeyLast = KeyLast;
    return true;
}


/**
 * Random single key allocation.
 *
 * @returns success indicator.
 * @param   pTracker    The tracker.
 * @param   pKey        Where to store the allocated key.
 * @remark  The caller has to call TrackerInsert.
 */
static bool TrackerNewRandom(PTRACKER pTracker, uint32_t *pKey)
{
    return TrackerNewRandomEx(pTracker, pKey, NULL, 1);
}


/**
 * Random single key 'lookup'.
 *
 * @returns success indicator.
 * @param   pTracker    The tracker.
 * @param   pKey        Where to store the allocated key.
 * @remark  The caller has to call TrackerRemove.
 */
static bool TrackerFindRandom(PTRACKER pTracker, uint32_t *pKey)
{
    uint32_t Key = RTRandAdvU32Ex(g_hRand, 0, pTracker->MaxKey - 1);
    if (!ASMBitTest(pTracker->abBitmap, Key))
    {
        if (!pTracker->cSetBits)
            return false;

        int Key2 = ASMBitNextSet(pTracker->abBitmap, pTracker->MaxKey, Key);
        if (Key2 > 0)
            Key = Key2;
        else
        {
            /* we're missing a ASMBitPrevSet function, so here's a quick replacement hack. */
            uint32_t *pu32Start = (uint32_t *)&pTracker->abBitmap[0];
            uint32_t *pu32Cur   = (uint32_t *)&pTracker->abBitmap[Key >> 8];
            while (pu32Cur >= pu32Start)
            {
                if (*pu32Cur)
                {
                    *pKey = ASMBitLastSetU32(*pu32Cur) - 1 + (uint32_t)((pu32Cur - pu32Start) * 32);
                    return true;
                }
                pu32Cur--;
            }
            Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
            if (Key2 == -1)
            {
                RTTestIFailed("cSetBits=%u - but ASMBitFirstSet failed to find any", pTracker->cSetBits);
                return false;
            }
            Key = Key2;
        }
    }

    *pKey = Key;
    return true;
}


/*
bool TrackerAllocSeq(PTRACKER pTracker, uint32_t *pKey, uint32_t *pKeyLast, uint32_t cMaxKeys)
{
    return false;
}*/


/**
 * Prints an unbuffered char.
 * @param   ch  The char.
 */
static void ProgressChar(char ch)
{
    //RTTestIPrintf(RTTESTLVL_INFO, "%c", ch);
    RTTestIPrintf(RTTESTLVL_SUB_TEST, "%c", ch);
}

/**
 * Prints a progress indicator label.
 * @param   cMax        The max number of operations (exclusive).
 * @param   pszFormat   The format string.
 * @param   ...         The arguments to the format string.
 */
DECLINLINE(void) ProgressPrintf(unsigned cMax, const char *pszFormat, ...)
{
    if (cMax < 10000)
        return;

    va_list va;
    va_start(va, pszFormat);
    //RTTestIPrintfV(RTTESTLVL_INFO, pszFormat, va);
    RTTestIPrintfV(RTTESTLVL_SUB_TEST, pszFormat, va);
    va_end(va);
}


/**
 * Prints a progress indicator dot.
 * @param   iCur    The current operation. (can be descending too)
 * @param   cMax    The max number of operations (exclusive).
 */
DECLINLINE(void) Progress(unsigned iCur, unsigned cMax)
{
    if (cMax < 10000)
        return;
    if (!(iCur % (cMax / 20)))
        ProgressChar('.');
}


static int avlogcphys(unsigned cMax)
{
    /*
     * Simple linear insert and remove.
     */
    if (cMax >= 10000)
        RTTestISubF("oGCPhys(%d): linear left", cMax);
    PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
    unsigned i;
    for (i = 0; i < cMax; i++)
    {
        Progress(i, cMax);
        PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        if (!RTAvloGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("linear left insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLOGCPHYSNODECORE Node = *pNode;
        if (RTAvloGCPhysInsert(pTree, &Node))
        {
            RTTestIFailed("linear left negative insert i=%d\n", i);
            return 1;
        }
    }

    ProgressPrintf(cMax, "~");
    for (i = 0; i < cMax; i++)
    {
        Progress(i, cMax);
        PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
        if (!pNode)
        {
            RTTestIFailed("linear left remove i=%d\n", i);
            return 1;
        }
        memset(pNode, 0xcc, sizeof(*pNode));
        RTMemFree(pNode);

        /* negative */
        pNode = RTAvloGCPhysRemove(pTree, i);
        if (pNode)
        {
            RTTestIFailed("linear left negative remove i=%d\n", i);
            return 1;
        }
    }

    /*
     * Simple linear insert and remove from the right.
     */
    if (cMax >= 10000)
        RTTestISubF("oGCPhys(%d): linear right", cMax);
    for (i = 0; i < cMax; i++)
    {
        Progress(i, cMax);
        PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        if (!RTAvloGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("linear right insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLOGCPHYSNODECORE Node = *pNode;
        if (RTAvloGCPhysInsert(pTree, &Node))
        {
            RTTestIFailed("linear right negative insert i=%d\n", i);
            return 1;
        }
    }

    ProgressPrintf(cMax, "~");
    while (i-- > 0)
    {
        Progress(i, cMax);
        PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, i);
        if (!pNode)
        {
            RTTestIFailed("linear right remove i=%d\n", i);
            return 1;
        }
        memset(pNode, 0xcc, sizeof(*pNode));
        RTMemFree(pNode);

        /* negative */
        pNode = RTAvloGCPhysRemove(pTree, i);
        if (pNode)
        {
            RTTestIFailed("linear right negative remove i=%d\n", i);
            return 1;
        }
    }

    /*
     * Linear insert but root based removal.
     */
    if (cMax >= 10000)
        RTTestISubF("oGCPhys(%d): linear root", cMax);
    for (i = 0; i < cMax; i++)
    {
        Progress(i, cMax);
        PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        if (!RTAvloGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("linear root insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLOGCPHYSNODECORE Node = *pNode;
        if (RTAvloGCPhysInsert(pTree, &Node))
        {
            RTTestIFailed("linear root negative insert i=%d\n", i);
            return 1;
        }
    }

    ProgressPrintf(cMax, "~");
    while (i-- > 0)
    {
        Progress(i, cMax);
        PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)((intptr_t)pTree + *pTree);
        RTGCPHYS Key = pNode->Key;
        pNode = RTAvloGCPhysRemove(pTree, Key);
        if (!pNode)
        {
            RTTestIFailed("linear root remove i=%d Key=%d\n", i, (unsigned)Key);
            return 1;
        }
        memset(pNode, 0xcc, sizeof(*pNode));
        RTMemFree(pNode);

        /* negative */
        pNode = RTAvloGCPhysRemove(pTree, Key);
        if (pNode)
        {
            RTTestIFailed("linear root negative remove i=%d Key=%d\n", i, (unsigned)Key);
            return 1;
        }
    }
    if (*pTree)
    {
        RTTestIFailed("sparse remove didn't remove it all!\n");
        return 1;
    }

    /*
     * Make a sparsely populated tree and remove the nodes using best fit in 5 cycles.
     */
    const unsigned cMaxSparse = RT_ALIGN(cMax, 32);
    if (cMaxSparse >= 10000)
        RTTestISubF("oGCPhys(%d): sparse", cMax);
    for (i = 0; i < cMaxSparse; i += 8)
    {
        Progress(i, cMaxSparse);
        PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        if (!RTAvloGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("sparse insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLOGCPHYSNODECORE Node = *pNode;
        if (RTAvloGCPhysInsert(pTree, &Node))
        {
            RTTestIFailed("sparse negative insert i=%d\n", i);
            return 1;
        }
    }

    /* Remove using best fit in 5 cycles. */
    ProgressPrintf(cMaxSparse, "~");
    unsigned j;
    for (j = 0; j < 4; j++)
    {
        for (i = 0; i < cMaxSparse; i += 8 * 4)
        {
            Progress(i, cMax); // good enough
            PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemoveBestFit(pTree, i, true);
            if (!pNode)
            {
                RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
                return 1;
            }
            if (pNode->Key - (unsigned long)i >= 8 * 4)
            {
                RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)pNode->Key);
                return 1;
            }
            memset(pNode, 0xdd, sizeof(*pNode));
            RTMemFree(pNode);
        }
    }
    if (*pTree)
    {
        RTTestIFailed("sparse remove didn't remove it all!\n");
        return 1;
    }
    RTMemFree(pTree);
    ProgressPrintf(cMaxSparse, "\n");
    return 0;
}


int avlogcphysRand(unsigned cMax, unsigned cMax2)
{
    PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
    unsigned i;

    /*
     * Random tree.
     */
    if (cMax >= 10000)
        RTTestISubF("oGCPhys(%d, %d): random", cMax, cMax2);
    PTRACKER pTracker = TrackerCreate(cMax2);
    if (!pTracker)
    {
        RTTestIFailed("failed to create %d tracker!\n", cMax2);
        return 1;
    }

    /* Insert a number of nodes in random order. */
    for (i = 0; i < cMax; i++)
    {
        Progress(i, cMax);
        uint32_t Key;
        if (!TrackerNewRandom(pTracker, &Key))
        {
            RTTestIFailed("failed to allocate node no. %d\n", i);
            TrackerDestroy(pTracker);
            return 1;
        }
        PAVLOGCPHYSNODECORE pNode = (PAVLOGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = Key;
        if (!RTAvloGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("random insert i=%d Key=%#x\n", i, Key);
            return 1;
        }
        /* negative. */
        AVLOGCPHYSNODECORE Node = *pNode;
        if (RTAvloGCPhysInsert(pTree, &Node))
        {
            RTTestIFailed("linear negative insert i=%d Key=%#x\n", i, Key);
            return 1;
        }
        TrackerInsert(pTracker, Key, Key);
    }


    /* delete the nodes in random order. */
    ProgressPrintf(cMax, "~");
    while (i-- > 0)
    {
        Progress(i, cMax);
        uint32_t Key;
        if (!TrackerFindRandom(pTracker, &Key))
        {
            RTTestIFailed("failed to find free node no. %d\n", i);
            TrackerDestroy(pTracker);
            return 1;
        }

        PAVLOGCPHYSNODECORE pNode = RTAvloGCPhysRemove(pTree, Key);
        if (!pNode)
        {
            RTTestIFailed("random remove i=%d Key=%#x\n", i, Key);
            return 1;
        }
        if (pNode->Key != Key)
        {
            RTTestIFailed("random remove i=%d Key=%#x pNode->Key=%#x\n", i, Key, (unsigned)pNode->Key);
            return 1;
        }
        TrackerRemove(pTracker, Key, Key);
        memset(pNode, 0xdd, sizeof(*pNode));
        RTMemFree(pNode);
    }
    if (*pTree)
    {
        RTTestIFailed("random remove didn't remove it all!\n");
        return 1;
    }
    ProgressPrintf(cMax, "\n");
    TrackerDestroy(pTracker);
    RTMemFree(pTree);
    return 0;
}


int avlrogcphys(void)
{
    unsigned            i;
    unsigned            j;
    unsigned            k;
    PAVLROGCPHYSTREE    pTree = (PAVLROGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));

    AssertCompileSize(AVLOGCPHYSNODECORE, 24);
    AssertCompileSize(AVLROGCPHYSNODECORE, 32);

    RTTestISubF("RTAvlroGCPhys");

    /*
     * Simple linear insert, get and remove.
     */
    /* insert */
    for (i = 0; i < 65536; i += 4)
    {
        PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        pNode->KeyLast = i + 3;
        if (!RTAvlroGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("linear insert i=%d\n", (unsigned)i);
            return 1;
        }

        /* negative. */
        AVLROGCPHYSNODECORE Node = *pNode;
        for (j = i + 3; j > i - 32; j--)
        {
            for (k = i; k < i + 32; k++)
            {
                Node.Key = RT_MIN(j, k);
                Node.KeyLast = RT_MAX(k, j);
                if (RTAvlroGCPhysInsert(pTree, &Node))
                {
                    RTTestIFailed("linear negative insert i=%d j=%d k=%d\n", i, j, k);
                    return 1;
                }
            }
        }
    }

    /* do gets. */
    for (i = 0; i < 65536; i += 4)
    {
        PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, i);
        if (!pNode)
        {
            RTTestIFailed("linear get i=%d\n", i);
            return 1;
        }
        if (pNode->Key > i || pNode->KeyLast < i)
        {
            RTTestIFailed("linear get i=%d Key=%d KeyLast=%d\n", i, (unsigned)pNode->Key, (unsigned)pNode->KeyLast);
            return 1;
        }

        for (j = 0; j < 4; j++)
        {
            if (RTAvlroGCPhysRangeGet(pTree, i + j) != pNode)
            {
                RTTestIFailed("linear range get i=%d j=%d\n", i, j);
                return 1;
            }
        }

        /* negative. */
        if (    RTAvlroGCPhysGet(pTree, i + 1)
            ||  RTAvlroGCPhysGet(pTree, i + 2)
            ||  RTAvlroGCPhysGet(pTree, i + 3))
        {
            RTTestIFailed("linear negative get i=%d + n\n", i);
            return 1;
        }

    }

    /* remove */
    for (i = 0; i < 65536; i += 4)
    {
        PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysRemove(pTree, i);
        if (!pNode)
        {
            RTTestIFailed("linear remove i=%d\n", i);
            return 1;
        }
        memset(pNode, 0xcc, sizeof(*pNode));
        RTMemFree(pNode);

        /* negative */
        if (    RTAvlroGCPhysRemove(pTree, i)
            ||  RTAvlroGCPhysRemove(pTree, i + 1)
            ||  RTAvlroGCPhysRemove(pTree, i + 2)
            ||  RTAvlroGCPhysRemove(pTree, i + 3))
        {
            RTTestIFailed("linear negative remove i=%d + n\n", i);
            return 1;
        }
    }

    /*
     * Make a sparsely populated tree.
     */
    for (i = 0; i < 65536; i += 8)
    {
        PAVLROGCPHYSNODECORE pNode = (PAVLROGCPHYSNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        pNode->KeyLast = i + 3;
        if (!RTAvlroGCPhysInsert(pTree, pNode))
        {
            RTTestIFailed("sparse insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLROGCPHYSNODECORE Node = *pNode;
        const RTGCPHYS jMin = i > 32 ? i - 32 : 1;
        const RTGCPHYS kMax = i + 32;
        for (j = pNode->KeyLast; j >= jMin; j--)
        {
            for (k = pNode->Key; k < kMax; k++)
            {
                Node.Key = RT_MIN(j, k);
                Node.KeyLast = RT_MAX(k, j);
                if (RTAvlroGCPhysInsert(pTree, &Node))
                {
                    RTTestIFailed("sparse negative insert i=%d j=%d k=%d\n", i, j, k);
                    return 1;
                }
            }
        }
    }

    /*
     * Get and Remove using range matching in 5 cycles.
     */
    for (j = 0; j < 4; j++)
    {
        for (i = 0; i < 65536; i += 8 * 4)
        {
            /* gets */
            RTGCPHYS  KeyBase = i + j * 8;
            PAVLROGCPHYSNODECORE pNode = RTAvlroGCPhysGet(pTree, KeyBase);
            if (!pNode)
            {
                RTTestIFailed("sparse get i=%d j=%d KeyBase=%d\n", i, j, (unsigned)KeyBase);
                return 1;
            }
            if (pNode->Key > KeyBase || pNode->KeyLast < KeyBase)
            {
                RTTestIFailed("sparse get i=%d j=%d KeyBase=%d pNode->Key=%d\n", i, j, (unsigned)KeyBase, (unsigned)pNode->Key);
                return 1;
            }
            for (k = KeyBase; k < KeyBase + 4; k++)
            {
                if (RTAvlroGCPhysRangeGet(pTree, k) != pNode)
                {
                    RTTestIFailed("sparse range get i=%d j=%d k=%d\n", i, j, k);
                    return 1;
                }
            }

            /* negative gets */
            for (k = i + j; k < KeyBase + 8; k++)
            {
                if (    k != KeyBase
                    &&  RTAvlroGCPhysGet(pTree, k))
                {
                    RTTestIFailed("sparse negative get i=%d j=%d k=%d\n", i, j, k);
                    return 1;
                }
            }
            for (k = i + j; k < KeyBase; k++)
            {
                if (RTAvlroGCPhysRangeGet(pTree, k))
                {
                    RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
                    return 1;
                }
            }
            for (k = KeyBase + 4; k < KeyBase + 8; k++)
            {
                if (RTAvlroGCPhysRangeGet(pTree, k))
                {
                    RTTestIFailed("sparse negative range get i=%d j=%d k=%d\n", i, j, k);
                    return 1;
                }
            }

            /* remove */
            RTGCPHYS Key = KeyBase + ((i / 19) % 4);
            if (RTAvlroGCPhysRangeRemove(pTree, Key) != pNode)
            {
                RTTestIFailed("sparse remove i=%d j=%d Key=%d\n", i, j, (unsigned)Key);
                return 1;
            }
            memset(pNode, 0xdd, sizeof(*pNode));
            RTMemFree(pNode);
        }
    }
    if (*pTree)
    {
        RTTestIFailed("sparse remove didn't remove it all!\n");
        return 1;
    }


    /*
     * Realworld testcase.
     */
    struct
    {
        AVLROGCPHYSTREE     Tree;
        AVLROGCPHYSNODECORE aNode[4];
    }   s1, s2, s3;
    RT_ZERO(s1);
    RT_ZERO(s2);
    RT_ZERO(s3);

    s1.aNode[0].Key        = 0x00030000;
    s1.aNode[0].KeyLast    = 0x00030fff;
    s1.aNode[1].Key        = 0x000a0000;
    s1.aNode[1].KeyLast    = 0x000bffff;
    s1.aNode[2].Key        = 0xe0000000;
    s1.aNode[2].KeyLast    = 0xe03fffff;
    s1.aNode[3].Key        = 0xfffe0000;
    s1.aNode[3].KeyLast    = 0xfffe0ffe;
    for (i = 0; i < RT_ELEMENTS(s1.aNode); i++)
    {
        PAVLROGCPHYSNODECORE pNode = &s1.aNode[i];
        if (!RTAvlroGCPhysInsert(&s1.Tree, pNode))
        {
            RTTestIFailed("real insert i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysInsert(&s1.Tree, pNode))
        {
            RTTestIFailed("real negative insert i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysGet(&s1.Tree, pNode->Key) != pNode)
        {
            RTTestIFailed("real get (1) i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysGet(&s1.Tree, pNode->KeyLast) != NULL)
        {
            RTTestIFailed("real negative get (2) i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key) != pNode)
        {
            RTTestIFailed("real range get (1) i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->Key + 1) != pNode)
        {
            RTTestIFailed("real range get (2) i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysRangeGet(&s1.Tree, pNode->KeyLast) != pNode)
        {
            RTTestIFailed("real range get (3) i=%d\n", i);
            return 1;
        }
    }

    s3 = s1;
    s1 = s2;
    for (i = 0; i < RT_ELEMENTS(s3.aNode); i++)
    {
        PAVLROGCPHYSNODECORE pNode = &s3.aNode[i];
        if (RTAvlroGCPhysGet(&s3.Tree, pNode->Key) != pNode)
        {
            RTTestIFailed("real get (10) i=%d\n", i);
            return 1;
        }
        if (RTAvlroGCPhysRangeGet(&s3.Tree, pNode->Key) != pNode)
        {
            RTTestIFailed("real range get (10) i=%d\n", i);
            return 1;
        }

        j = pNode->Key + 1;
        do
        {
            if (RTAvlroGCPhysGet(&s3.Tree, j) != NULL)
            {
                RTTestIFailed("real negative get (11) i=%d j=%#x\n", i, j);
                return 1;
            }
            if (RTAvlroGCPhysRangeGet(&s3.Tree, j) != pNode)
            {
                RTTestIFailed("real range get (11) i=%d j=%#x\n", i, j);
                return 1;
            }
        } while (j++ < pNode->KeyLast);
    }

    return 0;
}


int avlul(void)
{
    RTTestISubF("RTAvlUL");

    /*
     * Simple linear insert and remove.
     */
    PAVLULNODECORE  pTree = 0;
    unsigned i;
    /* insert */
    for (i = 0; i < 65536; i++)
    {
        PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        if (!RTAvlULInsert(&pTree, pNode))
        {
            RTTestIFailed("linear insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLULNODECORE Node = *pNode;
        if (RTAvlULInsert(&pTree, &Node))
        {
            RTTestIFailed("linear negative insert i=%d\n", i);
            return 1;
        }
    }

    for (i = 0; i < 65536; i++)
    {
        PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i);
        if (!pNode)
        {
            RTTestIFailed("linear remove i=%d\n", i);
            return 1;
        }
        pNode->pLeft     = (PAVLULNODECORE)0xaaaaaaaa;
        pNode->pRight    = (PAVLULNODECORE)0xbbbbbbbb;
        pNode->uchHeight = 'e';
        RTMemFree(pNode);

        /* negative */
        pNode = RTAvlULRemove(&pTree, i);
        if (pNode)
        {
            RTTestIFailed("linear negative remove i=%d\n", i);
            return 1;
        }
    }

    /*
     * Make a sparsely populated tree.
     */
    for (i = 0; i < 65536; i += 8)
    {
        PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
        pNode->Key = i;
        if (!RTAvlULInsert(&pTree, pNode))
        {
            RTTestIFailed("linear insert i=%d\n", i);
            return 1;
        }
        /* negative. */
        AVLULNODECORE Node = *pNode;
        if (RTAvlULInsert(&pTree, &Node))
        {
            RTTestIFailed("linear negative insert i=%d\n", i);
            return 1;
        }
    }

    /*
     * Remove using best fit in 5 cycles.
     */
    unsigned j;
    for (j = 0; j < 4; j++)
    {
        for (i = 0; i < 65536; i += 8 * 4)
        {
            PAVLULNODECORE pNode = RTAvlULRemoveBestFit(&pTree, i, true);
            //PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i + j * 8);
            if (!pNode)
            {
                RTTestIFailed("sparse remove i=%d j=%d\n", i, j);
                return 1;
            }
            pNode->pLeft     = (PAVLULNODECORE)0xdddddddd;
            pNode->pRight    = (PAVLULNODECORE)0xcccccccc;
            pNode->uchHeight = 'E';
            RTMemFree(pNode);
        }
    }

    return 0;
}


int main()
{
    /*
     * Init.
     */
    RTTEST hTest;
    int rc = RTTestInitAndCreate("tstRTAvl", &hTest);
    if (rc)
        return rc;
    RTTestBanner(hTest);
    g_hTest = hTest;

    rc = RTRandAdvCreateParkMiller(&g_hRand);
    if (RT_FAILURE(rc))
    {
        RTTestIFailed("RTRandAdvCreateParkMiller -> %Rrc", rc);
        return RTTestSummaryAndDestroy(hTest);
    }

    /*
     * Testing.
     */
    unsigned i;
    RTTestSub(hTest, "oGCPhys(32..2048)");
    for (i = 32; i < 2048; i++)
        if (avlogcphys(i))
            break;

    avlogcphys(_64K);
    avlogcphys(_512K);
    avlogcphys(_4M);

    RTTestISubF("oGCPhys(32..2048, *1K)");
    for (i = 32; i < 4096; i++)
        if (avlogcphysRand(i, i + _1K))
            break;
    for (; i <= _4M; i *= 2)
        if (avlogcphysRand(i, i * 8))
            break;

    avlrogcphys();
    avlul();

    /*
     * Done.
     */
    return RTTestSummaryAndDestroy(hTest);
}