Changeset 25005 in vbox for trunk/src/VBox/Runtime

Timestamp:

Nov 26, 2009 2:42:59 PM (15 years ago)

Author:

vboxsync

Message:

IPRT: Optimized version of RTStrVersionCompare (thanks to Knut!), made it behave like strcmp().

Location:

trunk/src/VBox/Runtime

Files:

• common/string/strversion.cpp (modified) (1 diff)
• testcase/tstStrToVer.cpp (modified) (3 diffs)

trunk/src/VBox/Runtime/common/string/strversion.cpp

@@ -37 +37 @@
 
 #include <iprt/assert.h>
+#include <iprt/ctype.h>
 #include <iprt/err.h>
-#include <iprt/mem.h>
 
 
 /*******************************************************************************
-*   Defined Constants                                                          *
+*   Defined Constants And Macros                                               *
 *******************************************************************************/
-#define ISDIGIT(c) ((c) >= '0' && (c) <= '9')
+#define RTSTRVER_IS_PUNCTUACTION(ch)    \
+    ( (ch) == '_' || (ch) == '-' || (ch) == '+' || RT_C_IS_PUNCT(ch) )
 
 
-/*******************************************************************************
-*   Internal Functions                                                         *
-*******************************************************************************/
-static uint16_t RTStrVersionGetBlockCount(const char *pszVer)
+/**
+ * Parses a out the next block from a version string.
+ *
+ * @returns true if numeric, false if not.
+ * @param   ppszVer             The string cursor, IN/OUT.
+ * @param   pu32Value           Where to return the value if numeric.
+ * @param   pcchBlock           Where to return the block length.
+ */
+static bool rtStrVersionParseBlock(const char **ppszVer, uint32_t *pu32Value, size_t *pcchBlock)
 {
-    uint16_t l = 0;
-    const char *pszCur = pszVer;
-    while (pszCur = RTStrStr(pszCur, "."))
+    const char *psz = *ppszVer;
+
+    /* Check for end-of-string. */
+    if (!*psz)
     {
-        if (pszCur == NULL)
-            break;
-        l++;
-        pszCur++;
+        *pu32Value = 0;
+        *pcchBlock = 0;
+        return false;
     }
-    /* Adjust block count to also count in the very first block */
-    if (*pszVer != '\0')
-        l++;
-    return l;
+
+    bool fNumeric = RT_C_IS_DIGIT(*psz);
+    if (fNumeric)
+    {
+        do
+            psz++;
+        while (*psz && RT_C_IS_DIGIT(*psz));
+
+        char *pszNext;
+        int rc = RTStrToUInt32Ex(*ppszVer, &pszNext, 10, pu32Value);
+        AssertRC(rc);
+        Assert(pszNext == psz);
+        if (RT_FAILURE(rc) || rc == VWRN_NUMBER_TOO_BIG)
+        {
+            fNumeric = false;
+            *pu32Value = 0;
+        }
+    }
+    else
+    {
+        do
+            psz++;
+        while (*psz && !RT_C_IS_DIGIT(*psz) && !RTSTRVER_IS_PUNCTUACTION(*psz));
+        *pu32Value = 0;
+    }
+    *pcchBlock = psz - *ppszVer;
+
+    /* skip punctuation */
+    if (RTSTRVER_IS_PUNCTUACTION(*psz))
+        psz++;
+    *ppszVer = psz;
+
+    return fNumeric;
 }
 
 
-static int RTStrVersionGetUInt32(const char *pszVer, uint16_t u16Block, uint32_t *pu32)
-{
-    /* First make a copy of the version string so that we can modify it */
-    char *pszString;
-    int rc = RTStrDupEx(&pszString, pszVer);
-    if (RT_FAILURE(rc))
-        return rc;
-
-    /* Go to the beginning of the block we want to parse */
-    char *pszCur = pszString;
-    for (uint16_t i = 0; i < u16Block; i++)
-    {
-        pszCur = RTStrStr(pszCur, ".");
-        if (pszCur == NULL)
-            break;
-        if (*pszCur != '\0')
-            pszCur++;
-    }
-
-    if (pszCur != NULL && *pszCur != '\0')
-    {
-        /* Skip trailing non-digits at the start of the block */
-        while (pszCur && *pszCur != '\0')
-        {
-            if (ISDIGIT(*pszCur))
-                break;
-            pszCur++;
-        }
-
-        /* Mark ending of the block */
-        char *pszEnd = RTStrStr(pszCur, ".");
-        if (NULL != pszEnd)
-            *pszEnd = '\0';
-
-        /* Convert to number */
-        rc = RTStrToUInt32Ex(pszCur, NULL /* ppszNext */, 10 /* Base */, pu32);
-        /* Skip trailing warnings */
-        if (   rc == VWRN_TRAILING_CHARS
-            || rc == VWRN_TRAILING_SPACES)
-            rc = VINF_SUCCESS;
-    }
-    else
-        rc = VERR_NOT_FOUND;
-
-    RTStrFree(pszString);
-    return rc;
-}
-
-
-/**
- * Compares two version strings and returns the result. The version string has
- * to be made of at least one number section, each section delimited by a ".",
- * e.g. "123.45.67". Trailing zeros at the beginning and non-digits in a section
- * will be skipped, so "12.foo006" becomes "12.6".
- *
- * @returns iprt status code.
- *          Warnings are used to indicate convertion problems.
- * @retval  VWRN_NUMBER_TOO_BIG
- * @retval  VWRN_TRAILING_CHARS
- * @retval  VWRN_TRAILING_SPACES
- * @retval  VINF_SUCCESS
- * @retval  VERR_NO_MEMORY
- * @retval  VERR_NO_DIGITS
- *
- * @param   pszVer1     First version string to compare.
- * @param   pszVer2     First version string to compare.
- * @param   pui8Res     Pointer uint8_t value where to store the comparison result:
- *                      0 if equal, 1 if pszVer1 is greater, 2 if pszVer2 is greater.
- */
-int RTStrVersionCompare(const char *pszVer1, const char *pszVer2, uint8_t *pui8Res)
+RTDECL(int) RTStrVersionCompare(const char *pszVer1, const char *pszVer2)
 {
     AssertPtr(pszVer1);
     AssertPtr(pszVer2);
 
-    uint16_t len1 = RTStrVersionGetBlockCount(pszVer1);
-    uint16_t len2 = RTStrVersionGetBlockCount(pszVer2);
+    /*
+     * Do a parallel parse of the strings.
+     */
+    int iRes = 0;
+    while (*pszVer1 || *pszVer2)
+    {
+        const char *pszBlock1 = pszVer1;
+        size_t      cchBlock1;
+        uint32_t    uVal1;
+        bool        fNumeric1 = rtStrVersionParseBlock(&pszVer1, &uVal1, &cchBlock1);
 
-    int rc = 0;
-    if (len1 > 0 && len2 > 0)
-    {
-        /* Figure out which version string is longer and set the corresponding
-         * pointers */
-        uint16_t range;
-        uint16_t padding;
-        const char *pszShorter, *pszLonger;
-        if (len1 >= len2)
+        const char *pszBlock2 = pszVer2;
+        size_t      cchBlock2;
+        uint32_t    uVal2;
+        bool        fNumeric2 = rtStrVersionParseBlock(&pszVer2, &uVal2, &cchBlock2);
+
+        if (fNumeric1 && fNumeric2)
         {
-            range = len1;
-            padding = len1 - len2;
-            pszLonger = pszVer1;
-            pszShorter = pszVer2;
+            if (uVal1 != uVal2)
+            {
+                iRes = uVal1 > uVal2 ? 1 : 2;
+                break;
+            }
         }
-        else if (len2 > len1)
+        else if (   !fNumeric1 && fNumeric2 && uVal2 == 0 && cchBlock1 == 0
+                 || !fNumeric2 && fNumeric1 && uVal1 == 0 && cchBlock2 == 0
+                )
         {
-            range = len2;
-            padding = len2 - len1;
-            pszLonger = pszVer2;
-            pszShorter = pszVer1;
+            /* 1.0 == 1.0.0.0.0. */;
         }
-
-        /* Now process each section (delimited by a ".") */
-        AssertPtr(pszShorter);
-        AssertPtr(pszLonger);
-        AssertPtr(pui8Res);
-        *pui8Res = 0;
-        uint32_t val1, val2;
-        for (uint16_t i = 0;    i < range
-                             && *pui8Res == 0
-                             && RT_SUCCESS(rc)
-                           ; i++)
+        else
         {
-            rc = RTStrVersionGetUInt32(pszLonger, i, &val1);
-            if (RT_SUCCESS(rc))
+            int iDiff = RTStrNICmp(pszBlock1, pszBlock2, RT_MIN(cchBlock1, cchBlock2));
+            if (!iDiff && cchBlock1 != cchBlock2)
+                iDiff = cchBlock1 < cchBlock2 ? -1 : 1;
+            if (iDiff)
             {
-                if (i >= range - padding)
-                {
-                    /* If we're in the padding range, there are no numbers left
-                     * to compare with anymore, so just assume "0" then */
-                    val2 = 0;
-                }
-                else
-                {
-                    rc = RTStrVersionGetUInt32(pszShorter, i, &val2);
-                }
-            }
-
-            if (RT_SUCCESS(rc))
-            {
-                if (val1 > val2)
-                {
-                    *pui8Res = (pszLonger == pszVer1) ? 1 : 2;
-                    break;
-                }
-                else if (val2 > val1)
-                {
-                    *pui8Res = (pszShorter == pszVer1) ? 1 : 2;
-                    break;
-                }
+                iRes = iDiff > 0 ? 1 : 2;
+                break;
             }
         }
     }
-    else
-    {
-        rc = VERR_NO_DIGITS;
-    }
-
-    if (RT_FAILURE(rc))
-        *pui8Res = 0; /* Zero out value */
-    return rc;
+    return iRes;
 }
 RT_EXPORT_SYMBOL(RTStrVersionCompare);

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

@@ -39 +39 @@
     const char *pszVer1;
     const char *pszVer2;
-    int         rc;
     uint8_t     Result;
 };
@@ -47 +46 @@
     do \
     { \
-        Type Result; \
-        int rc = Fun(Test.pszVer1, Test.pszVer2, &Result); \
+        Type Result = Fun(Test.pszVer1, Test.pszVer2); \
         if (Result != Test.Result) \
         { \
             RTPrintf("failure: '%s' <-> '%s' -> " Fmt ", expected " Fmt ". (%s/%u)\n", Test.pszVer1, Test.pszVer2, Result, Test.Result, #Fun, iTest); \
-            cErrors++; \
-        } \
-        else if (rc != Test.rc) \
-        { \
-            RTPrintf("failure: '%s' <-> '%s' -> rc=%Rrc, expected %Rrc. (%s/%u)\n", Test.pszVer1, Test.pszVer2, rc, Test.rc, #Fun, iTest); \
             cErrors++; \
         } \
@@ -77 +70 @@
     static const struct TstU8 aTstU8[] =
     {
-        { "", "",                         VERR_NO_DIGITS, 0 },
-        { "asdf", "",                     VERR_NO_DIGITS, 0 },
-        { "asdf234", "1.4.5",             VINF_SUCCESS, 1 },
-        { "12.foo006", "12.6",            VINF_SUCCESS, 0 },
-        { "1", "1",                       VINF_SUCCESS, 0 },
-        { "1", "100",                     VINF_SUCCESS, 2 },
-        { "100", "1",                     VINF_SUCCESS, 1 },
-        { "3", "4",                       VINF_SUCCESS, 2 },
-        { "1", "0.1",                     VINF_SUCCESS, 1 },
-        { "1", "0.0.0.0.10000",           VINF_SUCCESS, 1 },
-        { "0100", "100",                  VINF_SUCCESS, 0 },
-        { "1.0.0", "1",                   VINF_SUCCESS, 0 },
-        { "1.0.0", "100.0.0",             VINF_SUCCESS, 2 },
-        { "1", "1.0.3.0",                 VINF_SUCCESS, 2 },
-        { "1.4.5", "1.2.3",               VINF_SUCCESS, 1 },
-        { "1.2.3", "1.4.5",               VINF_SUCCESS, 2 },
-        { "1.2.3", "4.5.6",               VINF_SUCCESS, 2 },
-        { "1.0.4", "1.0.3",               VINF_SUCCESS, 1 },
-        { "0.1", "0.0.1",                 VINF_SUCCESS, 1 },
-        { "0.0.1", "0.1.1",               VINF_SUCCESS, 2 },
-        { "3.1.0", "3.0.14",              VINF_SUCCESS, 1 },
-        { "2.0.12", "3.0.14",             VINF_SUCCESS, 2 },
-        { "3.1", "3.0.22",                VINF_SUCCESS, 1 },
-        { "3.0.14", "3.1.0",              VINF_SUCCESS, 2 },
-        { "45.63", "04.560.30",           VINF_SUCCESS, 1 },
-        { "45.006", "45.6",               VINF_SUCCESS, 0 },
-        { "23.206", "23.06",              VINF_SUCCESS, 1 },
-        { "23.2", "23.060",               VINF_SUCCESS, 2 },
+        { "", "",                         0 },
+        { "asdf", "",                     1 }, /* "asdf" is bigger than "" */
+        { "asdf234", "1.4.5",             1 },
+        { "12.foo006", "12.6",            1 }, /* "12.foo006" is bigger than "12.6" */
+        { "1", "1",                       0 },
+        { "1", "100",                     2 },
+        { "100", "1",                     1 },
+        { "3", "4",                       2 },
+        { "1", "0.1",                     1 },
+        { "1", "0.0.0.0.10000",           1 },
+        { "0100", "100",                  0 },
+        { "1.0.0", "1",                   0 },
+        { "1.0.0", "100.0.0",             2 },
+        { "1", "1.0.3.0",                 2 },
+        { "1.4.5", "1.2.3",               1 },
+        { "1.2.3", "1.4.5",               2 },
+        { "1.2.3", "4.5.6",               2 },
+        { "1.0.4", "1.0.3",               1 },
+        { "0.1", "0.0.1",                 1 },
+        { "0.0.1", "0.1.1",               2 },
+        { "3.1.0", "3.0.14",              1 },
+        { "2.0.12", "3.0.14",             2 },
+        { "3.1", "3.0.22",                1 },
+        { "3.0.14", "3.1.0",              2 },
+        { "45.63", "04.560.30",           1 },
+        { "45.006", "45.6",               0 },
+        { "23.206", "23.06",              1 },
+        { "23.2", "23.060",               2 },
 
-        { "VirtualBox-2.0.8-Beta2", "VirtualBox-2.0.8_Beta3-r12345", VINF_SUCCESS, 0 },
-        { "VirtualBox-2.2.4-Beta2", "VirtualBox-2.2.2", VINF_SUCCESS, 1 },
-        { "VirtualBox-3.1.0", "VirtualBox-3.1.2_Beta1", VINF_SUCCESS, 2 },
-        { "3.1.0_BETA-r12345", "3.1.2", VINF_SUCCESS, 2 },
+        { "VirtualBox-2.0.8-Beta2", "VirtualBox-2.0.8_Beta3-r12345", 2 },
+        { "VirtualBox-2.2.4-Beta2", "VirtualBox-2.2.2", 1 },
+        { "VirtualBox-2.2.4-Beta3", "VirtualBox-2.2.2-Beta4", 1 },
+        { "VirtualBox-3.1.8-Alpha1", "VirtualBox-3.1.8-Alpha1-r61454", 2 },
+        { "VirtualBox-3.1.0", "VirtualBox-3.1.2_Beta1", 2 },
+        { "3.1.0_BETA-r12345", "3.1.2", 2 },
     };
-    RUN_TESTS(aTstU8, uint8_t, "%#d", RTStrVersionCompare);
+    RUN_TESTS(aTstU8, int, "%#d", RTStrVersionCompare);
 
     /*