Changeset 93691 in vbox for trunk/src/VBox

Timestamp:

Feb 11, 2022 10:10:12 AM (3 years ago)

Author:

vboxsync

Message:

IPRT/tstRTAvl: Fixed broke TrackerFindRandom code causing random test failures. Added some counting and heigh checks.

File:

• trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp (modified) (18 diffs)

trunk/src/VBox/Runtime/testcase/tstRTAvl.cpp

@@ -37 +37 @@
 #include <iprt/rand.h>
 #include <iprt/stdarg.h>
+#include <iprt/stream.h>
 #include <iprt/string.h>
 #include <iprt/test.h>
@@ -75 +76 @@
 static PTRACKER TrackerCreate(uint32_t MaxKey)
 {
-    uint32_t cbBitmap = (MaxKey + sizeof(uint32_t) * sizeof(uint8_t) - 1) / sizeof(uint8_t);
+    uint32_t cbBitmap = RT_ALIGN_32(MaxKey, 64) / 8;
     PTRACKER pTracker = (PTRACKER)RTMemAllocZ(RT_UOFFSETOF_DYN(TRACKER, abBitmap[cbBitmap]));
     if (pTracker)
@@ -254 +255 @@
         {
             /* 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)
+            uint32_t const *pu32Bitmap = (uint32_t const *)&pTracker->abBitmap[0];
+            Key >>= 5;
+            do
+            {
+                uint32_t u32;
+                if ((u32 = pu32Bitmap[Key]) != 0)
                 {
-                    *pKey = ASMBitLastSetU32(*pu32Cur) - 1 + (uint32_t)((pu32Cur - pu32Start) * 32);
+                    *pKey = ASMBitLastSetU32(u32) - 1 + (Key << 5);
                     return true;
                 }
-                pu32Cur--;
-            }
+            } while (Key-- > 0);
+
             Key2 = ASMBitFirstSet(pTracker->abBitmap, pTracker->MaxKey);
             if (Key2 == -1)
@@ -277 +279 @@
     *pKey = Key;
     return true;
+}
+
+
+/**
+ * Gets the number of keys in the tree.
+ */
+static uint32_t TrackerGetCount(PTRACKER pTracker)
+{
+    return pTracker->cSetBits;
 }
 
@@ -538 +549 @@
 
 
-int avlogcphysRand(unsigned cMax, unsigned cMax2)
+static DECLCALLBACK(int) avlogcphysCallbackCounter(PAVLOGCPHYSNODECORE pNode, void *pvUser)
+{
+    RT_NOREF(pNode);
+    *(uint32_t *)pvUser += 1;
+    return 0;
+}
+
+int avlogcphysRand(unsigned cMax, unsigned cMax2, uint32_t fCountMask)
 {
     PAVLOGCPHYSTREE pTree = (PAVLOGCPHYSTREE)RTMemAllocZ(sizeof(*pTree));
@@ -581 +599 @@
         }
         TrackerInsert(pTracker, Key, Key);
+
+        if (!(i & fCountMask))
+        {
+            uint32_t cCount = 0;
+            RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
+            if (cCount != TrackerGetCount(pTracker))
+                RTTestIFailed("wrong tree count after random insert i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
+        }
+    }
+
+    {
+        uint32_t cCount = 0;
+        RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
+        if (cCount != TrackerGetCount(pTracker))
+            RTTestIFailed("wrong tree count after random insert i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
     }
 
@@ -611 +644 @@
         memset(pNode, 0xdd, sizeof(*pNode));
         RTMemFree(pNode);
+
+        if (!(i & fCountMask))
+        {
+            uint32_t cCount = 0;
+            RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
+            if (cCount != TrackerGetCount(pTracker))
+                RTTestIFailed("wrong tree count after random remove i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
+        }
+    }
+    {
+        uint32_t cCount = 0;
+        RTAvloGCPhysDoWithAll(pTree, i & 1, avlogcphysCallbackCounter, &cCount);
+        if (cCount != TrackerGetCount(pTracker))
+            RTTestIFailed("wrong tree count after random insert i=%d: %u, expected %u", i, cCount, TrackerGetCount(pTracker));
     }
     if (*pTree)
@@ -937 +984 @@
      */
     PAVLULNODECORE  pTree = 0;
-    unsigned i;
+    unsigned        cInserted = 0;
+    unsigned        i;
+
     /* insert */
-    for (i = 0; i < 65536; i++)
+    for (i = 0; i < 65536; i++, cInserted++)
     {
         PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
@@ -948 +997 @@
             return 1;
         }
+
         /* negative. */
         AVLULNODECORE Node = *pNode;
@@ -955 +1005 @@
             return 1;
         }
-    }
-
-    for (i = 0; i < 65536; i++)
+
+        /* check height */
+        uint8_t  const cHeight = pTree ? pTree->uchHeight : 0;
+        uint32_t const cMax    = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
+        if (cInserted > cMax || cInserted < (cMax >> 2))
+            RTTestIFailed("bad tree height after linear insert i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
+    }
+
+    for (i = 0; i < 65536; i++, cInserted--)
     {
         PAVLULNODECORE pNode = RTAvlULRemove(&pTree, i);
@@ -977 +1033 @@
             return 1;
         }
+
+        /* check height */
+        uint8_t  const cHeight = pTree ? pTree->uchHeight : 0;
+        uint32_t const cMax    = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
+        if (cInserted > cMax || cInserted < (cMax >> 2))
+            RTTestIFailed("bad tree height after linear removal i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
     }
 
@@ -982 +1044 @@
      * Make a sparsely populated tree.
      */
-    for (i = 0; i < 65536; i += 8)
+    for (i = 0; i < 65536; i += 8, cInserted++)
     {
         PAVLULNODECORE pNode = (PAVLULNODECORE)RTMemAlloc(sizeof(*pNode));
@@ -991 +1053 @@
             return 1;
         }
+
         /* negative. */
         AVLULNODECORE Node = *pNode;
@@ -998 +1061 @@
             return 1;
         }
+
+        /* check height */
+        uint8_t  const cHeight = pTree ? pTree->uchHeight : 0;
+        uint32_t const cMax    = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
+        if (cInserted > cMax || cInserted < (cMax >> 2))
+            RTTestIFailed("bad tree height after sparse insert i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
     }
 
@@ -1006 +1075 @@
     for (j = 0; j < 4; j++)
     {
-        for (i = 0; i < 65536; i += 8 * 4)
+        for (i = 0; i < 65536; i += 8 * 4, cInserted--)
         {
             PAVLULNODECORE pNode = RTAvlULRemoveBestFit(&pTree, i, true);
@@ -1019 +1088 @@
             pNode->uchHeight = 'E';
             RTMemFree(pNode);
+
+            /* check height */
+            uint8_t  const cHeight = pTree ? pTree->uchHeight : 0;
+            uint32_t const cMax    = cHeight > 0 ? RT_BIT_32(cHeight) : 1;
+            if (cInserted > cMax || cInserted < (cMax >> 2))
+                RTTestIFailed("bad tree height after sparse removal i=%d: cMax=%#x, cInserted=%#x\n", i, cMax, cInserted);
         }
     }
@@ -1445 +1520 @@
      * Testing.
      */
+#if 0
     unsigned i;
     RTTestSub(hTest, "oGCPhys(32..2048)");
@@ -1457 +1533 @@
     RTTestISubF("oGCPhys(32..2048, *1K)");
     for (i = 32; i < 4096; i++)
-        if (avlogcphysRand(i, i + _1K))
+        if (avlogcphysRand(i, i + _1K, 0xff))
             break;
     for (; i <= _4M; i *= 2)
-        if (avlogcphysRand(i, i * 8))
+        if (avlogcphysRand(i, i * 8, i * 2 - 1))
             break;
 
     avlrogcphys();
+#endif
     avlul();