Changeset 93672 in vbox

Timestamp:

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

Author:

vboxsync

Message:

IPRT/hardavl: A fix, a few build fixes and some more tests. bugref:10093

Location:

trunk

Files:

• include/iprt/cpp/hardavlrange.h (modified) (5 diffs)
• src/VBox/Runtime/testcase/tstRTAvl.cpp (modified) (4 diffs)

trunk/include/iprt/cpp/hardavlrange.h

@@ -292 +292 @@
                                      AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5], *AVLStack.apidxEntries[RT_ELEMENTS(AVLStack.apidxEntries) - 5]),
                                     m_cErrors++, VERR_HARDAVL_STACK_OVERFLOW);
-                AVLStack.apidxEntries[cEntries] = pidxDeleteNode;
+                AVLStack.apidxEntries[cEntries] = pidxLeftLeast;
                 AVLStack.cEntries = cEntries + 1;
 
@@ -437 +437 @@
                     if (pLeftNode)
                     {
+#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
                         AssertCompile(kMaxStack > 6);
+#endif
                         AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
                                             ("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
@@ -469 +471 @@
                     if (pRightNode)
                     {
+#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
                         AssertCompile(kMaxStack > 6);
+#endif
                         AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
                                             ("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],
@@ -554 +558 @@
                     if (pLeftNode)
                     {
+#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
                         AssertCompile(kMaxStack > 6);
+#endif
                         AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
                                             ("%p[%#x] %p %p %p %p %p %p\n", pLeftNode, pNode->idxLeft, apEntries[kMaxStack - 1],
@@ -582 +588 @@
                     if (pRightNode)
                     {
+#if RT_GNUC_PREREQ_EX(4,7, 1) /* 32-bit 4.4.7 has trouble, dunno when it started working exactly */
                         AssertCompile(kMaxStack > 6);
+#endif
                         AssertMsgReturnStmt(cEntries < RT_ELEMENTS(apEntries),
                                             ("%p[%#x] %p %p %p %p %p %p\n", pRightNode, pNode->idxRight, apEntries[kMaxStack - 1],

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

@@ -1045 +1045 @@
 }
 
+
+static uint32_t PickClearBit(uint64_t *pbm, uint32_t cItems)
+{
+    uint32_t idx = RTRandU32Ex(0, cItems - 1);
+    if (ASMBitTest(pbm, idx) == 0)
+        return idx;
+
+    /* Scan forward as we've got code for that already: */
+    uint32_t const idxOrg = idx;
+    idx = ASMBitNextClear(pbm, cItems, idx);
+    if ((int32_t)idx >= 0)
+        return idx;
+
+    /* Scan backwards bit-by-bit because we don't have code for this: */
+    for (idx = idxOrg - 1; idx < cItems; idx--)
+        if (ASMBitTest(pbm, idx) == 0)
+            return idx;
+
+    AssertFailed();
+    RTTestIFailed("no clear bit in bitmap!\n");
+    return 0;
+}
+
+
+static uint32_t PickClearBitAndSetIt(uint64_t *pbm, uint32_t cItems)
+{
+    uint32_t idx = PickClearBit(pbm, cItems);
+    RTTESTI_CHECK(ASMBitTestAndSet(pbm, idx) == false);
+    return idx;
+}
+
+
+static uint32_t PickSetBit(uint64_t *pbm, uint32_t cItems)
+{
+    uint32_t idx = RTRandU32Ex(0, cItems - 1);
+    if (ASMBitTest(pbm, idx) == 1)
+        return idx;
+
+    /* Scan forward as we've got code for that already: */
+    uint32_t const idxOrg = idx;
+    idx = ASMBitNextSet(pbm, cItems, idx);
+    if ((int32_t)idx >= 0)
+        return idx;
+
+    /* Scan backwards bit-by-bit because we don't have code for this: */
+    for (idx = idxOrg - 1; idx < cItems; idx--)
+        if (ASMBitTest(pbm, idx) == 1)
+            return idx;
+
+    AssertFailed();
+    RTTestIFailed("no set bit in bitmap!\n");
+    return 0;
+}
+
+
+static uint32_t PickSetBitAndClearIt(uint64_t *pbm, uint32_t cItems)
+{
+    uint32_t idx = PickSetBit(pbm, cItems);
+    RTTESTI_CHECK(ASMBitTestAndSet(pbm, idx) == true);
+    return idx;
+}
+
+
 /** @return meaningless, just for return RTTestIFailed(); */
 int hardAvlRangeTreeGCPhys(RTTEST hTest)
@@ -1184 +1247 @@
      * Randomized stuff.
      */
-    /** @todo add randomized testing step.  Split the address space up into equal
-     *        portition and pick what to insert/remove/lookup using a random
-     *        function against a insertion status bitmap. */
+    uint64_t uSeed = RTRandU64();
+    RTRandAdvSeed(g_hRand, uSeed);
+    RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed: %#RX64\n", uSeed);
+
+    RTGCPHYS const   cbStep     = RTGCPHYS_MAX / cItems + 1;
+    uint64_t * const pbmPresent = (uint64_t *)RTMemAllocZ(RT_ALIGN_32(cItems, 64) / 64 * 8);
+    RTTESTI_CHECK_RET(pbmPresent, 1);
+
+    /* insert all in random order */
+    for (unsigned i = 0; i < cItems; i++)
+    {
+        MYTESTNODE *pNode = Allocator.allocateNode();
+        if (!pNode)
+            return RTTestIFailed("out of nodes: i=%#x #3", i);
+
+        uint32_t const idx = PickClearBitAndSetIt(pbmPresent, cItems);
+        pNode->Key     = idx * cbStep;
+        pNode->KeyLast = pNode->Key + cbStep - 1;
+        int rc = Tree.insert(&Allocator, pNode);
+        if (rc != VINF_SUCCESS)
+            RTTestIFailed("random insert failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)", rc, i, idx, pNode->Key, pNode->KeyLast);
+
+        MYTESTNODE *pNode2 = (MYTESTNODE *)(intptr_t)i;
+        rc = Tree.lookup(&Allocator, pNode->Key, &pNode2);
+        if (rc != VINF_SUCCESS || pNode2 != pNode)
+            return RTTestIFailed("lookup after random insert %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
+    }
+
+#if 0 /** @todo this doesn't work quit right yet */
+    /* remove all in random order. */
+    for (unsigned i = 0; i < cItems; i++)
+    {
+        uint32_t const idx = PickSetBitAndClearIt(pbmPresent, cItems);
+
+        MYTESTNODE *pNode = (MYTESTNODE *)(intptr_t)i;
+        int rc = Tree.remove(&Allocator, idx * cbStep, &pNode);
+        if (rc != VINF_SUCCESS)
+            RTTestIFailed("random remove failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)",
+                          rc, idx, idx * cbStep, idx * cbStep + cbStep - 1);
+        else if (   pNode->Key     != idx * cbStep
+                 || pNode->KeyLast != idx * cbStep + cbStep - 1)
+            RTTestIFailed("random remove returned wrong node: %RGp ... %RGp, expected %RGp ... %RGp (i=%#x, idx=%#x)",
+                          pNode->Key, pNode->KeyLast, idx * cbStep, idx * cbStep + cbStep - 1, i, idx);
+        else
+        {
+            MYTESTNODE *pNode2 = (MYTESTNODE *)(intptr_t)i;
+            rc = Tree.lookup(&Allocator, idx * cbStep, &pNode2);
+            if (rc != VERR_NOT_FOUND)
+                RTTestIFailed("lookup after random removal %#x: %Rrc pNode=%p pNode2=%p idx=%#x", i, rc, pNode, pNode2, idx);
+
+            rc = Allocator.freeNode(pNode);
+            if (rc != VINF_SUCCESS)
+                RTTestIFailed("free after random removal %#x failed: %Rrc pNode=%p idx=%#x", i, rc, pNode, idx);
+        }
+    }
+#endif
+
+    /** @todo Add more random stuff here where we pick the operation to perform
+     *        using random as well and just do large number of these iterations. */
 
     return 0;
@@ -1214 +1333 @@
      * Testing.
      */
+#if 0
     unsigned i;
     RTTestSub(hTest, "oGCPhys(32..2048)");
@@ -1234 +1354 @@
     avlrogcphys();
     avlul();
+#endif
+
     hardAvlRangeTreeGCPhys(hTest);