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