src/TortoiseMerge/libsvn_diff/lcs.c

   1 /*
   2  * lcs.c :  routines for creating an lcs
   3  *
   4  * ====================================================================
   5  * Copyright (c) 2000-2004 CollabNet.  All rights reserved.
   6  *
   7  * This software is licensed as described in the file COPYING, which
   8  * you should have received as part of this distribution.  The terms
   9  * are also available at http://subversion.tigris.org/license-1.html.
  10  * If newer versions of this license are posted there, you may use a
  11  * newer version instead, at your option.
  12  *
  13  * This software consists of voluntary contributions made by many
  14  * individuals.  For exact contribution history, see the revision
  15  * history and logs, available at http://subversion.tigris.org/.
  16  * ====================================================================
  17  */
  18
  19
  20 #include <apr.h>
  21 #include <apr_pools.h>
  22 #include <apr_general.h>
  23
  24 #include "svn_error.h"
  25 #include "svn_version.h"
  26 #include "svn_io.h"
  27
  28 #include "diff.h"
  29
  30
  31 /*
  32  * Calculate the Longest Common Subsequence between two datasources.
  33  * This function is what makes the diff code tick.
  34  *
  35  * The LCS algorithm implemented here is described by Sun Wu,
  36  * Udi Manber and Gene Meyers in "An O(NP) Sequence Comparison Algorithm"
  37  *
  38  */
  39
  40 typedef struct svn_diff__snake_t svn_diff__snake_t;
  41
  42 struct svn_diff__snake_t
  43 {
  44     apr_off_t             y;
  45     svn_diff__lcs_t      *lcs;
  46     svn_diff__position_t *position[2];
  47 };
  48
  49 static APR_INLINE void
  50 svn_diff__snake(apr_off_t k,
  51                 svn_diff__snake_t *fp,
  52                 int idx,
  53                 svn_diff__lcs_t **freelist,
  54                 apr_pool_t *pool)
  55 {
  56   svn_diff__position_t *start_position[2];
  57   svn_diff__position_t *position[2];
  58   svn_diff__lcs_t *lcs;
  59   svn_diff__lcs_t *previous_lcs;
  60
  61   /* The previous entry at fp[k] is going to be replaced.  See if we
  62    * can mark that lcs node for reuse, because the sequence up to this
  63    * point was a dead end.
  64    */
  65   lcs = fp[k].lcs;
  66   while (lcs)
  67     {
  68       lcs->refcount--;
  69       if (lcs->refcount)
  70         break;
  71
  72       previous_lcs = lcs->next;
  73       lcs->next = *freelist;
  74       *freelist = lcs;
  75       lcs = previous_lcs;
  76     }
  77
  78   if (fp[k - 1].y + 1 > fp[k + 1].y)
  79     {
  80       start_position[0] = fp[k - 1].position[0];
  81       start_position[1] = fp[k - 1].position[1]->next;
  82
  83       previous_lcs = fp[k - 1].lcs;
  84     }
  85   else
  86     {
  87       start_position[0] = fp[k + 1].position[0]->next;
  88       start_position[1] = fp[k + 1].position[1];
  89
  90       previous_lcs = fp[k + 1].lcs;
  91     }
  92
  93
  94   /* ### Optimization, skip all positions that don't have matchpoints
  95    * ### anyway. Beware of the sentinel, don't skip it!
  96    */
  97
  98   position[0] = start_position[0];
  99   position[1] = start_position[1];
 100
 101   while (position[0]->node == position[1]->node)
 102     {
 103       position[0] = position[0]->next;
 104       position[1] = position[1]->next;
 105     }
 106
 107   if (position[1] != start_position[1])
 108     {
 109       lcs = *freelist;
 110       if (lcs)
 111         {
 112           *freelist = lcs->next;
 113         }
 114       else
 115         {
 116           lcs = apr_palloc(pool, sizeof(*lcs));
 117         }
 118
 119       lcs->position[idx] = start_position[0];
 120       lcs->position[abs(1 - idx)] = start_position[1];
 121       lcs->length = position[1]->offset - start_position[1]->offset;
 122       lcs->next = previous_lcs;
 123       lcs->refcount = 1;
 124       fp[k].lcs = lcs;
 125     }
 126   else
 127     {
 128       fp[k].lcs = previous_lcs;
 129     }
 130
 131   if (previous_lcs)
 132     {
 133       previous_lcs->refcount++;
 134     }
 135
 136   fp[k].position[0] = position[0];
 137   fp[k].position[1] = position[1];
 138
 139   fp[k].y = position[1]->offset;
 140 }
 141
 142
 143 static svn_diff__lcs_t *
 144 svn_diff__lcs_reverse(svn_diff__lcs_t *lcs)
 145 {
 146   svn_diff__lcs_t *next;
 147   svn_diff__lcs_t *prev;
 148
 149   next = NULL;
 150   while (lcs != NULL)
 151     {
 152       prev = lcs->next;
 153       lcs->next = next;
 154       next = lcs;
 155       lcs = prev;
 156     }
 157
 158   return next;
 159 }
 160
 161
 162 svn_diff__lcs_t *
 163 svn_diff__lcs(svn_diff__position_t *position_list1, /* pointer to tail (ring) */
 164               svn_diff__position_t *position_list2, /* pointer to tail (ring) */
 165               apr_pool_t *pool)
 166 {
 167   int idx;
 168   apr_off_t length[2];
 169   svn_diff__snake_t *fp;
 170   apr_off_t d;
 171   apr_off_t k;
 172   apr_off_t p = 0;
 173   svn_diff__lcs_t *lcs, *lcs_freelist = NULL;
 174
 175   svn_diff__position_t sentinel_position[2];
 176
 177   /* Since EOF is always a sync point we tack on an EOF link
 178    * with sentinel positions
 179    */
 180   lcs = apr_palloc(pool, sizeof(*lcs));
 181   lcs->position[0] = apr_pcalloc(pool, sizeof(*lcs->position[0]));
 182   lcs->position[0]->offset = position_list1 ? position_list1->offset + 1 : 1;
 183   lcs->position[1] = apr_pcalloc(pool, sizeof(*lcs->position[1]));
 184   lcs->position[1]->offset = position_list2 ? position_list2->offset + 1 : 1;
 185   lcs->length = 0;
 186   lcs->refcount = 1;
 187   lcs->next = NULL;
 188
 189   if (position_list1 == NULL || position_list2 == NULL)
 190     return lcs;
 191
 192   /* Calculate length of both sequences to be compared */
 193   length[0] = position_list1->offset - position_list1->next->offset + 1;
 194   length[1] = position_list2->offset - position_list2->next->offset + 1;
 195   idx = length[0] > length[1] ? 1 : 0;
 196
 197   /* strikerXXX: here we allocate the furthest point array, which is
 198    * strikerXXX: sized M + N + 3 (!)
 199    */
 200   fp = apr_pcalloc(pool,
 201                    sizeof(*fp) * (apr_size_t)(length[0] + length[1] + 3));
 202   fp += length[idx] + 1;
 203
 204   sentinel_position[idx].next = position_list1->next;
 205   position_list1->next = &sentinel_position[idx];
 206   sentinel_position[idx].offset = position_list1->offset + 1;
 207
 208   sentinel_position[abs(1 - idx)].next = position_list2->next;
 209   position_list2->next = &sentinel_position[abs(1 - idx)];
 210   sentinel_position[abs(1 - idx)].offset = position_list2->offset + 1;
 211
 212   /* These are never dereferenced, only compared by value, so we
 213    * can safely fake these up and the void* cast is OK.
 214    */
 215   sentinel_position[0].node = (void*)&sentinel_position[0];
 216   sentinel_position[1].node = (void*)&sentinel_position[1];
 217
 218   d = length[abs(1 - idx)] - length[idx];
 219
 220   /* k = -1 will be the first to be used to get previous
 221    * position information from, make sure it holds sane
 222    * data
 223    */
 224   fp[-1].position[0] = sentinel_position[0].next;
 225   fp[-1].position[1] = &sentinel_position[1];
 226
 227   p = 0;
 228   do
 229     {
 230       /* Forward */
 231       for (k = -p; k < d; k++)
 232         {
 233           svn_diff__snake(k, fp, idx, &lcs_freelist, pool);
 234         }
 235
 236       for (k = d + p; k >= d; k--)
 237         {
 238           svn_diff__snake(k, fp, idx, &lcs_freelist, pool);
 239         }
 240
 241       p++;
 242     }
 243   while (fp[d].position[1] != &sentinel_position[1]);
 244
 245   lcs->next = fp[d].lcs;
 246   lcs = svn_diff__lcs_reverse(lcs);
 247
 248   position_list1->next = sentinel_position[idx].next;
 249   position_list2->next = sentinel_position[abs(1 - idx)].next;
 250
 251   return lcs;
 252 }