Changeset 59972 in vbox

Timestamp:

Mar 9, 2016 8:06:41 PM (9 years ago)

Author:

vboxsync

Message:

Implemented RTSortShell.

Location:

trunk

Files:

• include/iprt/mangling.h (modified) (1 diff)
• src/VBox/Runtime/common/dbg/dbgmodcodeview.cpp (modified) (8 diffs)
• src/VBox/Runtime/common/sort/shellsort.cpp (modified) (1 diff)
• src/VBox/Runtime/testcase/tstRTSort.cpp (modified) (3 diffs)

trunk/include/iprt/mangling.h

@@ -1730 +1730 @@
 # define RTSortApvShell                                 RT_MANGLER(RTSortApvShell)
 # define RTSortIsSorted                                 RT_MANGLER(RTSortIsSorted)
+# define RTSortShell                                    RT_MANGLER(RTSortShell)
 # define RTSpinlockAcquire                              RT_MANGLER(RTSpinlockAcquire)
 # define RTSpinlockAcquireNoInts                        RT_MANGLER(RTSpinlockAcquireNoInts)

trunk/src/VBox/Runtime/common/dbg/dbgmodcodeview.cpp

@@ -57 +57 @@
 #include <iprt/param.h>
 #include <iprt/path.h>
+#include <iprt/sort.h>
 #include <iprt/string.h>
 #include <iprt/strcache.h>
@@ -69 +70 @@
 *   Structures and Typedefs                                                                                                      *
 *********************************************************************************************************************************/
-/**
- * Directory sorting order.
- */
-typedef enum RTCVDIRORDER
-{
-    RTCVDIRORDER_INVALID = 0,
-    /** Ordered by module. */
-    RTCVDIRORDER_BY_MOD,
-    /** Ordered by module, but 0 modules at the end. */
-    RTCVDIRORDER_BY_MOD_0,
-    /** Ordered by section, with global modules at the end. */
-    RTCVDIRORDER_BY_SST_MOD
-} RTCVDIRORDER;
-
-
 /**
  * File type.
@@ -123 +109 @@
     /** The offset of the subsection directory (relative to offBase). */
     uint32_t        offDir;
-    /** The directory order. */
-    RTCVDIRORDER    enmDirOrder;
     /** @}  */
 
@@ -1375 +1359 @@
 
 /**
+ * @callback_method_impl{PFNRTSORTCMP,
+ *      Used by rtDbgModCvLoadDirectory to sort the directory.}
+ */
+static DECLCALLBACK(int) rtDbgModCvDirEntCmp(void const *pvElement1, void const *pvElement2, void *pvUser)
+{
+    PRTCVDIRENT32 pEntry1 = (PRTCVDIRENT32)pvElement1;
+    PRTCVDIRENT32 pEntry2 = (PRTCVDIRENT32)pvElement2;
+    if (pEntry1->iMod < pEntry2->iMod)
+        return -1;
+    if (pEntry1->iMod > pEntry2->iMod)
+        return 1;
+    if (pEntry1->uSubSectType < pEntry2->uSubSectType)
+        return -1;
+    if (pEntry1->uSubSectType > pEntry2->uSubSectType)
+        return 1;
+    return 0;
+}
+
+
+/**
  * Loads the directory into memory (RTDBGMODCV::paDirEnts and
  * RTDBGMODCV::cDirEnts).
@@ -1485 +1489 @@
     if (RT_SUCCESS(rc))
     {
+        uint32_t const cbDbgInfo    = pThis->cbDbgInfo;
+        uint32_t const cDirEnts     = pThis->cDirEnts;
+
         /*
-         * Basic info validation and determining the directory ordering.
+         * Just sort the directory in a way we like, no need to make
+         * complicated demands on the linker output.
          */
-        bool           fWatcom      = 0;
+        RTSortShell(pThis->paDirEnts, cDirEnts, sizeof(pThis->paDirEnts[0]), rtDbgModCvDirEntCmp, NULL);
+
+        /*
+         * Basic info validation.
+         */
         uint16_t       cGlobalMods  = 0;
         uint16_t       cNormalMods  = 0;
         uint16_t       iModLast     = 0;
-        uint32_t const cbDbgInfo    = pThis->cbDbgInfo;
-        uint32_t const cDirEnts     = pThis->cDirEnts;
         Log2(("RTDbgModCv: %u (%#x) directory entries:\n", cDirEnts, cDirEnts));
         for (uint32_t i = 0; i < cDirEnts; i++)
@@ -1537 +1547 @@
                     iModLast = pDirEnt->iMod;
                 }
-                else if (pDirEnt->iMod < iModLast)
-                    fWatcom = true;
                 cNormalMods++;
             }
@@ -1549 +1557 @@
         if (RT_SUCCESS(rc))
         {
-            if (fWatcom)
-                pThis->enmDirOrder = RTCVDIRORDER_BY_SST_MOD;
-            else if (pThis->paDirEnts[0].iMod == 0)
-                pThis->enmDirOrder = RTCVDIRORDER_BY_MOD_0;
-            else
-                pThis->enmDirOrder = RTCVDIRORDER_BY_MOD;
-            Log(("CV dir stats: %u total, %u normal, %u special, iModLast=%#x (%u), enmDirOrder=%d\n",
-                 cDirEnts, cNormalMods, cGlobalMods, iModLast, iModLast, pThis->enmDirOrder));
-
-
+            Log(("CV dir stats: %u total, %u normal, %u special, iModLast=%#x (%u)\n",
+                 cDirEnts, cNormalMods, cGlobalMods, iModLast, iModLast));
+
+#if 0 /* skip this stuff */
             /*
              * Validate the directory ordering.
              */
             uint16_t i = 0;
-
-            /* Old style with special modules up front. */
-            if (pThis->enmDirOrder == RTCVDIRORDER_BY_MOD_0)
-                while (i < cGlobalMods)
-                {
-                    if (pThis->paDirEnts[i].iMod != 0)
-                    {
-                        Log(("CV directory entry #%u: Expected iMod=%x instead of %x\n", i, 0, pThis->paDirEnts[i].iMod));
-                        rc = VERR_CV_BAD_FORMAT;
-                    }
-                    i++;
-                }
 
             /* Normal modules. */
@@ -1648 +1638 @@
                     i++;
                 }
-        }
-
+#endif
+        }
     }
 

trunk/src/VBox/Runtime/common/sort/shellsort.cpp

@@ -32 +32 @@
 #include <iprt/sort.h>
 
+#include <iprt/alloca.h>
+#include <iprt/assert.h>
+#include <iprt/string.h>
+
+
+
+RTDECL(void) RTSortShell(void *pvArray, size_t cElements, size_t cbElement, PFNRTSORTCMP pfnCmp, void *pvUser)
+{
+    Assert(cbElement <= 32);
+
+    /* Anything worth sorting? */
+    if (cElements < 2)
+        return;
+
+    uint8_t *pbArray = (uint8_t *)pvArray;
+    void    *pvTmp   = alloca(cbElement);
+    size_t   cGap    = (cElements + 1) / 2;
+    while (cGap > 0)
+    {
+        size_t i;
+        for (i = cGap; i < cElements; i++)
+        {
+            memcpy(pvTmp, &pbArray[i * cbElement], cbElement);
+            size_t  j     = i;
+            while (   j >= cGap
+                   && pfnCmp(&pbArray[(j - cGap) * cbElement], pvTmp, pvUser) > 0)
+            {
+                memmove(&pbArray[j * cbElement], &pbArray[(j - cGap) * cbElement], cbElement);
+                j -= cGap;
+            }
+            memcpy(&pbArray[j * cbElement], pvTmp, cbElement);
+        }
+
+        /* This does not generate the most optimal gap sequence, but it has the
+           advantage of being simple and avoid floating point. */
+        cGap /= 2;
+    }
+}
 
 

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

@@ -35 +35 @@
 #include <iprt/string.h>
 #include <iprt/test.h>
+#include <iprt/time.h>
 
 
@@ -94 +95 @@
 
 
+static DECLCALLBACK(int) testCompare(void const *pvElement1, void const *pvElement2, void *pvUser)
+{
+    return memcmp(pvElement1, pvElement2, (size_t)pvUser);
+}
+
+static void testSorter(RTTEST hTest, FNRTSORT pfnSorter, const char *pszName)
+{
+    RTTestISub(pszName);
+
+    /* Use pseudo random config and data. */
+    RTRAND hRand;
+    RTTESTI_CHECK_RC_OK_RETV(RTRandAdvCreateParkMiller(&hRand));
+    RTTIMESPEC Now;
+    uint64_t uSeed = RTTimeSpecGetSeconds(RTTimeNow(&Now));
+    RTTestIPrintf(RTTESTLVL_ALWAYS, "Seed %#RX64\n", uSeed);
+    RTRandAdvSeed(hRand, uSeed);
+
+    for (uint32_t cArrays = 0; cArrays < 512; cArrays++)
+    {
+        /* Create a random array with random data bytes. */
+        uint32_t const cElements = RTRandAdvU32Ex(hRand, 2, 8192);
+        uint32_t const cbElement = RTRandAdvU32Ex(hRand, 1, 32);
+        uint8_t       *pbArray;
+        RTTESTI_CHECK_RC_OK_RETV(RTTestGuardedAlloc(hTest, cElements * cbElement, 1 /*cbAlign*/,
+                                                    RT_BOOL(RTRandAdvU32Ex(hRand, 0, 1)) /*fHead*/, (void **)&pbArray));
+        RTTESTI_CHECK_RETV(pbArray);
+        RTRandAdvBytes(hRand, pbArray, cElements * cbElement);
+
+        /* sort it */
+        pfnSorter(pbArray, cElements, cbElement, testCompare, (void *)cbElement);
+
+        /* verify it */
+        if (!RTSortIsSorted(pbArray, cElements, cbElement, testCompare, (void *)cbElement))
+            RTTestIFailed("failed sorting %u elements of %u size", cElements, cbElement);
+
+        RTTestGuardedFree(hTest, pbArray);
+    }
+}
+
+
 int main()
 {
@@ -105 +146 @@
      * Test the different algorithms.
      */
+    testSorter(hTest, RTSortShell, "RTSortShell - shell sort, variable sized element array");
     testApvSorter(RTSortApvShell, "RTSortApvShell - shell sort, pointer array");