Third batch

diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c
index 6e20f75fe85eb71c23dd60ad35419e531d9feb86..c7b35a9667f322c151bc8de276654ecd38974aef 100644 (file)
--- a/xdiff/xhistogram.c
+++ b/xdiff/xhistogram.c
@@ -42,8 +42,6 @@
  */
 
 #include "xinclude.h"
-#include "xtypes.h"
-#include "xdiff.h"
 
 #define MAX_PTR        UINT_MAX
 #define MAX_CNT        UINT_MAX
@@ -243,44 +241,21 @@ static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env,
                                  line1, count1, line2, count2);
 }
 
-static int find_lcs(struct histindex *index, struct region *lcs,
-       int line1, int count1, int line2, int count2) {
-       int b_ptr;
-
-       if (scanA(index, line1, count1))
-               return -1;
-
-       index->cnt = index->max_chain_length + 1;
-
-       for (b_ptr = line2; b_ptr <= LINE_END(2); )
-               b_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);
-
-       return index->has_common && index->max_chain_length < index->cnt;
+static inline void free_index(struct histindex *index)
+{
+       xdl_free(index->records);
+       xdl_free(index->line_map);
+       xdl_free(index->next_ptrs);
+       xdl_cha_free(&index->rcha);
 }
 
-static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
-       int line1, int count1, int line2, int count2)
+static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
+                   struct region *lcs,
+                   int line1, int count1, int line2, int count2)
 {
+       int b_ptr;
+       int sz, ret = -1;
        struct histindex index;
-       struct region lcs;
-       int sz;
-       int result = -1;
-
-       if (count1 <= 0 && count2 <= 0)
-               return 0;
-
-       if (LINE_END(1) >= MAX_PTR)
-               return -1;
-
-       if (!count1) {
-               while(count2--)
-                       env->xdf2.rchg[line2++ - 1] = 1;
-               return 0;
-       } else if (!count2) {
-               while(count1--)
-                       env->xdf1.rchg[line1++ - 1] = 1;
-               return 0;
-       }
 
        memset(&index, 0, sizeof(index));
 
@@ -318,8 +293,54 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
        index.ptr_shift = line1;
        index.max_chain_length = 64;
 
+       if (scanA(&index, line1, count1))
+               goto cleanup;
+
+       index.cnt = index.max_chain_length + 1;
+
+       for (b_ptr = line2; b_ptr <= LINE_END(2); )
+               b_ptr = try_lcs(&index, lcs, b_ptr, line1, count1, line2, count2);
+
+       if (index.has_common && index.max_chain_length < index.cnt)
+               ret = 1;
+       else
+               ret = 0;
+
+cleanup:
+       free_index(&index);
+       return ret;
+}
+
+static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
+       int line1, int count1, int line2, int count2)
+{
+       struct region lcs;
+       int lcs_found;
+       int result;
+redo:
+       result = -1;
+
+       if (count1 <= 0 && count2 <= 0)
+               return 0;
+
+       if (LINE_END(1) >= MAX_PTR)
+               return -1;
+
+       if (!count1) {
+               while(count2--)
+                       env->xdf2.rchg[line2++ - 1] = 1;
+               return 0;
+       } else if (!count2) {
+               while(count1--)
+                       env->xdf1.rchg[line1++ - 1] = 1;
+               return 0;
+       }
+
        memset(&lcs, 0, sizeof(lcs));
-       if (find_lcs(&index, &lcs, line1, count1, line2, count2))
+       lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2);
+       if (lcs_found < 0)
+               goto out;
+       else if (lcs_found)
                result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);
        else {
                if (lcs.begin1 == 0 && lcs.begin2 == 0) {
@@ -333,21 +354,21 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
                                                line1, lcs.begin1 - line1,
                                                line2, lcs.begin2 - line2);
                        if (result)
-                               goto cleanup;
-                       result = histogram_diff(xpp, env,
-                                               lcs.end1 + 1, LINE_END(1) - lcs.end1,
-                                               lcs.end2 + 1, LINE_END(2) - lcs.end2);
-                       if (result)
-                               goto cleanup;
+                               goto out;
+                       /*
+                        * result = histogram_diff(xpp, env,
+                        *            lcs.end1 + 1, LINE_END(1) - lcs.end1,
+                        *            lcs.end2 + 1, LINE_END(2) - lcs.end2);
+                        * but let's optimize tail recursion ourself:
+                       */
+                       count1 = LINE_END(1) - lcs.end1;
+                       line1 = lcs.end1 + 1;
+                       count2 = LINE_END(2) - lcs.end2;
+                       line2 = lcs.end2 + 1;
+                       goto redo;
                }
        }
-
-cleanup:
-       xdl_free(index.records);
-       xdl_free(index.line_map);
-       xdl_free(index.next_ptrs);
-       xdl_cha_free(&index.rcha);
-
+out:
        return result;
 }