summaryrefslogtreecommitdiffstats
path: root/src/VBox/Runtime/testcase/tstRTAvl.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/VBox/Runtime/testcase/tstRTAvl.cpp1074
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..1be4bfce
--- /dev/null
+++ b/src/VBox/Runtime/testcase/tstRTAvl.cpp
@@ -0,0 +1,1074 @@
+/* $Id: tstRTAvl.cpp $ */
+/** @file
+ * IPRT Testcase - AVL trees.
+ */
+
+/*
+ * Copyright (C) 2006-2019 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);
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-19 13:44:05 +0000