Changeset 93693 in vbox for trunk/src/VBox

Timestamp:

Feb 11, 2022 11:06:35 AM (3 years ago)

Author:

vboxsync

Message:

IPRT/hardavl: Added a getHeight() method for tstRTAvl and extended the testcase to check the tree height. bugref:10093

File:

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

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

@@ -1217 +1217 @@
     Allocator.initSlabAllocator(cItems, (TESTNODE *)pvItems, (uint64_t *)pbmBitmap);
 
+    uint32_t cInserted = 0;
+
     /*
      * Simple linear insert, get and remove.
      */
     /* insert */
-    for (unsigned i = 0; i < cItems * 4; i += 4)
+    for (unsigned i = 0; i < cItems * 4; i += 4, cInserted++)
     {
         MYTESTNODE *pNode = Allocator.allocateNode();
@@ -1269 +1271 @@
                 return RTTestIFailed("freeNode(pNode2=%p) failed: %Rrc (i=%#x)", pNode2, rc, i);
         }
+
+        /* check the height */
+        uint8_t  const cHeight = Tree.getHeight(&Allocator);
+        uint32_t const cMax    = RT_BIT_32(cHeight);
+        if (cInserted > cMax || cInserted < (cMax >> 4))
+            RTTestIFailed("wrong tree height after linear insert i=%#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
+                          i, cMax, cInserted, cHeight);
     }
 
@@ -1308 +1317 @@
 
     /* remove */
-    for (unsigned i = 0, j = 0; i < cItems * 4; i += 4, j += 3)
+    for (unsigned i = 0, j = 0; i < cItems * 4; i += 4, j += 3, cInserted--)
     {
         MYTESTNODE *pNode;
@@ -1328 +1337 @@
                 return RTTestIFailed("linear negative remove(%#x): %Rrc pNode=%p", k, rc, pNode);
         }
+
+        /* check the height */
+        uint8_t  const cHeight = Tree.getHeight(&Allocator);
+        uint32_t const cMax    = RT_BIT_32(cHeight);
+        if (cInserted > cMax || cInserted < (cMax >> 4))
+            RTTestIFailed("wrong tree height after linear remove i=%#x: cMax=%#x, cInserted=%#x cHeight=%d\n",
+                          i, cMax, cInserted, cHeight);
     }
 
@@ -1342 +1358 @@
 
     /* insert all in random order */
+    cInserted = 0;
     for (unsigned i = 0; i < cItems; i++)
     {
@@ -1352 +1369 @@
         pNode->KeyLast = pNode->Key + cbStep - 1;
         int rc = Tree.insert(&Allocator, pNode);
-        if (rc != VINF_SUCCESS)
+        if (rc == VINF_SUCCESS)
+            cInserted++;
+        else
             RTTestIFailed("random insert failed: %Rrc, i=%#x, idx=%#x (%RGp ... %RGp)", rc, i, idx, pNode->Key, pNode->KeyLast);
 
@@ -1364 +1383 @@
         if (rc != VINF_SUCCESS)
             RTTestIFailed("enum after random insert %#x: %Rrc idx=%#x", i, rc, idx);
-        else if (cCount != i + 1)
-            RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, i + 1);
+        else if (cCount != cInserted)
+            RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cInserted);
+
+        /* check the height */
+        uint8_t  const cHeight = Tree.getHeight(&Allocator);
+        uint32_t const cMax    = RT_BIT_32(cHeight);
+        if (cInserted > cMax || cInserted < (cMax >> 4))
+            RTTestIFailed("wrong tree height after random insert %#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
+                          i, cMax, cInserted, cHeight);
     }
 
@@ -1380 +1406 @@
         else
         {
-            if (   pNode->Key     != idx * cbStep
+            cInserted--;
+            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)",
@@ -1395 +1422 @@
                 if (rc != VINF_SUCCESS)
                     RTTestIFailed("enum after random removal %#x: %Rrc idx=%#x", i, rc, idx);
-                else if (cCount != cItems - i - 1)
-                    RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cItems - i - 1);
+                else if (cCount != cInserted)
+                    RTTestIFailed("wrong count after random removal %#x: %#x, expected %#x", i, cCount, cInserted);
             }
 
@@ -1403 +1430 @@
                 RTTestIFailed("free after random removal %#x failed: %Rrc pNode=%p idx=%#x", i, rc, pNode, idx);
         }
+
+        /* check the height */
+        uint8_t  const cHeight = Tree.getHeight(&Allocator);
+        uint32_t const cMax    = RT_BIT_32(cHeight);
+        if (cInserted > cMax || cInserted < (cMax >> 4))
+            RTTestIFailed("wrong tree height after random removal %#x: cMax=%#x, cInserted=%#x, cHeight=%u\n",
+                          i, cMax, cInserted, cHeight);
     }
 
@@ -1411 +1445 @@
     RTRandAdvSeed(g_hRand, uSeed);
     RTTestIPrintf(RTTESTLVL_ALWAYS, "Random seed #2: %#RX64\n", uSeed);
-    uint32_t       cInserted    = 0;
     uint64_t       cItemsEnumed = 0;
     bool           fAdding      = true;
     uint64_t const nsStart      = RTTimeNanoTS();
     unsigned       i;
-    for (i = 0; i < _64M; i++)
+    for (i = 0, cInserted = 0; i < _64M; i++)
     {
         /* The operation. */
@@ -1483 +1516 @@
         else if (cCount != cInserted)
             RTTestIFailed("wrong count after random %s: %#x, expected %#x - i=%#x",
-                          cCount, cInserted, fDelete ? "removal" : "insert", i);
+                          fDelete ? "removal" : "insert", cCount, cInserted, i);
         cItemsEnumed += cCount;
+
+        /* check the height */
+        uint8_t  const cHeight = Tree.getHeight(&Allocator);
+        uint32_t const cMax    = RT_BIT_32(cHeight);
+        if (cInserted > cMax || cInserted < (cMax >> 4))
+            RTTestIFailed("wrong tree height after random %s: cMax=%#x, cInserted=%#x, cHeight=%u - i=%#x\n",
+                          fDelete ? "removal" : "insert", cMax, cInserted, cHeight, i);
 
         /* Check for timeout. */