svn commit: r1412639 - /subversion/trunk/subversion/libsvn_subr/string.c

[br...@apache.org]

Author: brane
Date: Thu Nov 22 19:00:43 2012
New Revision: 1412639

URL: http://svn.apache.org/viewvc?rev=1412639&view=rev
Log:
Fix a couple nits in the string-LCS algorithm.

* subversion/libsvn_subr/string.c (svn_string__similarity): Fix the common
   suffix scanner, removing an edge-case buf, as per Julians most welcome
   suggestion. Also fix a string indexing bug (though I've no idea how that
   could've slipped past the test cases) and only initialize the part of the
   buffer that we actually need.

Modified:
    subversion/trunk/subversion/libsvn_subr/string.c

Modified: subversion/trunk/subversion/libsvn_subr/string.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/string.c?rev=1412639&r1=1412638&r2=1412639&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_subr/string.c (original)
+++ subversion/trunk/subversion/libsvn_subr/string.c Thu Nov 22 19:00:43 2012
@@ -1212,19 +1212,23 @@ svn_string__similarity(const svn_string_
     }
 
   /* ... and the common suffix */
-  if (stra < enda && strb < endb)
-    do
-      {
-        --enda; --endb;
-        ++lcs;
-      }
-    while (stra < enda && strb < endb && *enda == *endb);
+  while (stra < enda && strb < endb)
+    {
+      --enda; --endb;
+      if (*enda != *endb)
+        {
+          ++enda; ++endb;
+          break;
+        }
+
+      ++lcs;
+    }
 
   if (stra < enda && strb < endb)
     {
-      /* Move the end pointers past the non-matching part */
-      const apr_size_t resta = ++enda - stra;
-      const apr_size_t restb = ++endb - strb;
+      /* Move the end pointers back past the non-matching part */
+      const apr_size_t resta = enda - stra;
+      const apr_size_t restb = endb - strb;
       const apr_size_t slots = (resta > restb ? restb : resta);
       apr_size_t *curr, *prev;
       const char *pstr;
@@ -1243,10 +1247,10 @@ svn_string__similarity(const svn_string_
 
       /* Allocate two columns in the LCS matrix
          ### Optimize this to (slots + 2) instesd of 2 * (slots + 1) */
-      svn_membuf__ensure(buffer, 2 * (slots + 1) * sizeof(apr_size_t));
-      svn_membuf__zero(buffer);
-      curr = buffer->data;
-      prev = curr + slots + 1;
+      svn_membuf__resize(buffer, 2 * (slots + 1) * sizeof(apr_size_t));
+      svn_membuf__nzero(buffer, (slots + 2) * sizeof(apr_size_t));
+      prev = buffer->data;
+      curr = prev + slots + 1;
 
       /* Calculate LCS length of the remainder */
       for (pstr = stra; pstr < enda; ++pstr)
@@ -1254,7 +1258,7 @@ svn_string__similarity(const svn_string_
           int i;
           for (i = 1; i <= slots; ++i)
             {
-              if (*pstr == strb[i])
+              if (*pstr == strb[i-1])
                 curr[i] = prev[i-1] + 1;
               else
                 curr[i] = (curr[i-1] > prev[i] ? curr[i-1] : prev[i]);
@@ -1268,9 +1272,7 @@ svn_string__similarity(const svn_string_
           }
         }
 
-      /* The common suffix matcher always increments the lcs
-         so subtract 1 from the result. */
-      lcs += prev[slots] - 1;
+      lcs += prev[slots];
     }
 
   if (rlcs)