text_delta.c

来自「linux subdivision ying gai ke yi le ba」· C语言 代码 · 共 748 行 · 第 1/2 页

/* 
 * text-delta.c -- Internal text delta representation
 * 
 * ====================================================================
 * Copyright (c) 2000-2004 CollabNet.  All rights reserved.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution.  The terms
 * are also available at http://subversion.tigris.org/license-1.html.
 * If newer versions of this license are posted there, you may use a
 * newer version instead, at your option.
 *
 * This software consists of voluntary contributions made by many
 * individuals.  For exact contribution history, see the revision
 * history and logs, available at http://subversion.tigris.org/.
 * ====================================================================
 */


#include <assert.h>
#include <string.h>

#include <apr_general.h>        /* for APR_INLINE */
#include <apr_md5.h>            /* for, um...MD5 stuff */

#include "svn_delta.h"
#include "svn_io.h"
#include "svn_md5.h"
#include "svn_pools.h"
#include "delta.h"


/* Text delta stream descriptor. */

struct svn_txdelta_stream_t {
  /* These are copied from parameters passed to svn_txdelta. */
  svn_stream_t *source;
  svn_stream_t *target;

  /* Private data */
  svn_boolean_t more;           /* TRUE if there are more data in the pool. */
  svn_filesize_t pos;           /* Offset of next read in source file. */
  char *buf;                    /* Buffer for vdelta data. */

  apr_md5_ctx_t context;        /* APR's MD5 context container. */

  /* Calculated digest from MD5 operations.
     NOTE:  This is only valid after this stream has returned the NULL
     (final) window.  */
  unsigned char digest[APR_MD5_DIGESTSIZE]; 
};


/* Target-push stream descriptor. */

struct tpush_baton {
  /* These are copied from parameters passed to svn_txdelta_target_push. */
  svn_stream_t *source;
  svn_txdelta_window_handler_t wh;
  void *whb;
  apr_pool_t *pool;

  /* Private data */
  char *buf;
  apr_size_t source_offset;
  apr_size_t source_len;
  svn_boolean_t source_done;
  apr_size_t target_len;
};


/* Text delta applicator.  */

struct apply_baton {
  /* These are copied from parameters passed to svn_txdelta_apply.  */
  svn_stream_t *source;
  svn_stream_t *target;

  /* Private data.  Between calls, SBUF contains the data from the
   * last window's source view, as specified by SBUF_OFFSET and
   * SBUF_LEN.  The contents of TBUF are not interesting between
   * calls.  */
  apr_pool_t *pool;             /* Pool to allocate data from */
  char *sbuf;                   /* Source buffer */
  apr_size_t sbuf_size;         /* Allocated source buffer space */
  svn_filesize_t sbuf_offset;   /* Offset of SBUF data in source stream */
  apr_size_t sbuf_len;          /* Length of SBUF data */
  char *tbuf;                   /* Target buffer */
  apr_size_t tbuf_size;         /* Allocated target buffer space */

  apr_md5_ctx_t md5_context;    /* Leads to result_digest below. */
  unsigned char *result_digest; /* MD5 digest of resultant fulltext;
                                   must point to at least APR_MD5_DIGESTSIZE
                                   bytes of storage. */

  const char *error_info;       /* Optional extra info for error returns. */
};



svn_txdelta_window_t *
svn_txdelta__make_window (const svn_txdelta__ops_baton_t *build_baton,
                          apr_pool_t *pool)
{
  svn_txdelta_window_t *window;
  svn_string_t *new_data = apr_palloc (pool, sizeof (*new_data));

  window = apr_palloc (pool, sizeof (*window));
  window->sview_offset = 0;
  window->sview_len = 0;
  window->tview_len = 0;

  window->num_ops = build_baton->num_ops;
  window->src_ops = build_baton->src_ops;
  window->ops = build_baton->ops;

  /* just copy the fields over, rather than alloc/copying into a whole new
     svn_string_t structure. */
  /* ### would be much nicer if window->new_data were not a ptr... */
  new_data->data = build_baton->new_data->data;
  new_data->len = build_baton->new_data->len;
  window->new_data = new_data;

  return window;
}


/* Compute and return a delta window using the vdelta algorithm on
   DATA, which contains SOURCE_LEN bytes of source data and TARGET_LEN
   bytes of target data.  SOURCE_OFFSET gives the offset of the source
   data, and is simply copied into the window's sview_offset field. */
static svn_txdelta_window_t *
compute_window (const char *data, apr_size_t source_len, apr_size_t target_len,
                apr_size_t source_offset, apr_pool_t *pool)
{
  svn_txdelta__ops_baton_t build_baton = { 0 };
  svn_txdelta_window_t *window;

  /* Compute the delta operations. */
  build_baton.new_data = svn_stringbuf_create ("", pool);
  svn_txdelta__vdelta (&build_baton, data, source_len, target_len, pool);
  
  /* Create and return the delta window. */
  window = svn_txdelta__make_window (&build_baton, pool);
  window->sview_offset = source_offset;
  window->sview_len = source_len;
  window->tview_len = target_len;
  return window;
}



svn_txdelta_window_t *
svn_txdelta__copy_window (const svn_txdelta_window_t *window,
                          apr_pool_t *pool)
{
  svn_txdelta__ops_baton_t build_baton = { 0 };
  svn_txdelta_window_t *new_window;
  const apr_size_t ops_size = (window->num_ops * sizeof (*build_baton.ops));

  build_baton.num_ops = window->num_ops;
  build_baton.src_ops = window->src_ops;
  build_baton.ops_size = window->num_ops;
  build_baton.ops = apr_palloc (pool, ops_size);
  memcpy (build_baton.ops, window->ops, ops_size);
  build_baton.new_data =
    svn_stringbuf_create_from_string (window->new_data, pool);

  new_window = svn_txdelta__make_window (&build_baton, pool);
  new_window->sview_offset = window->sview_offset;
  new_window->sview_len = window->sview_len;
  new_window->tview_len = window->tview_len;
  return new_window;
}



/* Insert a delta op into a delta window. */

void
svn_txdelta__insert_op (svn_txdelta__ops_baton_t *build_baton,
                        enum svn_delta_action opcode,
                        apr_size_t offset,
                        apr_size_t length,
                        const char *new_data,
                        apr_pool_t *pool)
{
  svn_txdelta_op_t *op;

  /* Check if this op can be merged with the previous op. The vdelta
     algorithm will never generate such ops, but the delta combiner
     can, and this is the obvious place to make the check. */
  if (build_baton->num_ops > 0)
    {
      op = &build_baton->ops[build_baton->num_ops - 1];
      if (op->action_code == opcode
          && (opcode == svn_txdelta_new
              || op->offset + op->length == offset))
        {
          op->length += length;
          if (opcode == svn_txdelta_new)
            svn_stringbuf_appendbytes (build_baton->new_data,
                                       new_data, length);
          return;
        }
    }

  /* Create space for the new op. */
  if (build_baton->num_ops == build_baton->ops_size)
    {
      svn_txdelta_op_t *const old_ops = build_baton->ops;
      int const new_ops_size = (build_baton->ops_size == 0
                                ? 16 : 2 * build_baton->ops_size);
      build_baton->ops =
        apr_palloc (pool, new_ops_size * sizeof (*build_baton->ops));

      /* Copy any existing ops into the new array */
      if (old_ops)
        memcpy (build_baton->ops, old_ops,
                build_baton->ops_size * sizeof (*build_baton->ops));
      build_baton->ops_size = new_ops_size;
    }

  /* Insert the op. svn_delta_source and svn_delta_target are
     just inserted. For svn_delta_new, the new data must be
     copied into the window. */
  op = &build_baton->ops[build_baton->num_ops];
  switch (opcode)
    {
    case svn_txdelta_source:
      ++build_baton->src_ops;
      /*** FALLTHRU ***/
    case svn_txdelta_target:
      op->action_code = opcode;
      op->offset = offset;
      op->length = length;
      break;
    case svn_txdelta_new:
      op->action_code = opcode;
      op->offset = build_baton->new_data->len;
      op->length = length;
      svn_stringbuf_appendbytes (build_baton->new_data, new_data, length);
      break;
    default:
      assert (!"unknown delta op.");
    }

  ++build_baton->num_ops;
}



/* Allocate a delta stream descriptor. */

void
svn_txdelta (svn_txdelta_stream_t **stream,
             svn_stream_t *source,
             svn_stream_t *target,
             apr_pool_t *pool)
{
  *stream = apr_palloc (pool, sizeof (**stream));
  (*stream)->source = source; 
  (*stream)->target = target;
  (*stream)->more = TRUE;
  (*stream)->pos = 0;
  (*stream)->buf = apr_palloc (pool, 2 * SVN_DELTA_WINDOW_SIZE);

  /* Initialize MD5 digest calculation. */
  apr_md5_init (&((*stream)->context));
}



/* Pull the next delta window from a stream.

   Our current algorithm for picking source and target views is one
   step up from the dumbest algorithm of "compare corresponding blocks
   of each file."  A problem with that algorithm is that an insertion
   or deletion of N bytes near the beginning of the file will result
   in N bytes of non-overlap in each window from then on.  Our
   algorithm lessens this problem by "padding" the source view with
   half a target view's worth of data on each side.

   For example, suppose the target view size is 16K.  The dumbest
   algorithm would use bytes 0-16K for the first source view, 16-32K
   for the second source view, etc..  Our algorithm uses 0-24K for the
   first source view, 8-40K for the second source view, etc..
   Obviously, we're chewing some extra memory by doubling the source
   view size, but small (less than 8K) insertions or deletions won't
   result in non-overlap in every window.

   If we run out of source data before we run out of target data, we
   reuse the final chunk of data for the remaining windows.  No grand
   scheme at work there; that's just how the code worked out. */
svn_error_t *
svn_txdelta_next_window (svn_txdelta_window_t **window,
                         svn_txdelta_stream_t *stream,
                         apr_pool_t *pool)
{
  svn_error_t *err;
  apr_size_t source_len = SVN_DELTA_WINDOW_SIZE;
  apr_size_t target_len = SVN_DELTA_WINDOW_SIZE;
  
  /* Read the source stream. */
  err = svn_stream_read (stream->source, stream->buf, &source_len);
  
  /* Read the target stream. */
  if (err == SVN_NO_ERROR)
    err = svn_stream_read (stream->target, stream->buf + source_len,
                           &target_len);
  if (err != SVN_NO_ERROR)
    return err;
  stream->pos += source_len;
  
  /* ### The apr_md5 functions always return APR_SUCCESS.  At one
     point, we proposed to APR folks that the interfaces change to
     return void, but for some people that was apparently not a good
     idea, and we didn't bother pressing the matter.  In the meantime,
     we just ignore their return values below. */
  if (target_len == 0)
    {
      /* No target data?  We're done; return the final window. */
      apr_md5_final (stream->digest, &(stream->context));
      *window = NULL;
      stream->more = FALSE;
      return SVN_NO_ERROR;
    }
  else
    {
      apr_md5_update (&(stream->context), stream->buf + source_len,
                      target_len);
    }

  *window = compute_window(stream->buf, source_len, target_len,
                           stream->pos - source_len, pool);
  
  /* That's it. */
  return SVN_NO_ERROR;
}


const unsigned char *
svn_txdelta_md5_digest (svn_txdelta_stream_t *stream)
{
  /* If there are more windows for this stream, the digest has not yet
     been calculated.  */
  if (stream->more)
    return NULL;

  return stream->digest;
}



/* Functions for implementing a "target push" delta. */

/* This is the write handler for a target-push delta stream.  It reads
 * source data, buffers target data, and fires off delta windows when
 * the target data buffer is full. */
static svn_error_t *
tpush_write_handler (void *baton, const char *data, apr_size_t *len)
{
  struct tpush_baton *tb = baton;
  apr_size_t chunk_len, data_len = *len;
  apr_pool_t *pool = svn_pool_create (tb->pool);
  svn_txdelta_window_t *window;

  while (data_len > 0)
    {
      svn_pool_clear (pool);

      /* Make sure we're all full up on source data, if possible. */
      if (tb->source_len == 0 && !tb->source_done)
        {