diff options
Diffstat (limited to 'src/VBox/Runtime/testcase/tstRTAvl.cpp')
| -rw-r--r-- | src/VBox/Runtime/testcase/tstRTAvl.cpp | 1074 |
1 files changed, 1074 insertions, 0 deletions
diff --git a/src/VBox/Runtime/testcase/tstRTAvl.cpp b/src/VBox/Runtime/testcase/tstRTAvl.cpp new file mode 100644 index 00000000..9db14df6 --- /dev/null +++ b/src/VBox/Runtime/testcase/tstRTAvl.cpp @@ -0,0 +1,1074 @@ +/* $Id: tstRTAvl.cpp $ */ +/** @file + * IPRT Testcase - AVL trees. + */ + +/* + * Copyright (C) 2006-2020 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_UOFFSETOF_DYN(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)(uintptr_t)0xaaaaaaaa; + pNode->pRight = (PAVLULNODECORE)(uintptr_t)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)(uintptr_t)0xdddddddd; + pNode->pRight = (PAVLULNODECORE)(uintptr_t)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); +} + |