compose_delta.c

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

/* Add a range [OFFSET, LIMIT) into NDX. If NDX already contains a
   range that encloses [OFFSET, LIMIT), do nothing. Otherwise, remove
   all ranges from NDX that are superseded by the new range.
   NOTE: The range index must be splayed to OFFSET! */

static void
insert_range (apr_size_t offset, apr_size_t limit, apr_size_t target_offset,
              range_index_t *ndx)
{
  range_index_node_t *node = NULL;

  if (ndx->tree == NULL)
    {
      node = alloc_range_index_node(ndx, offset, limit, target_offset);
      ndx->tree = node;
    }
  else
    {
      if (offset == ndx->tree->offset
          && limit > ndx->tree->limit)
        {
          ndx->tree->limit = limit;
          ndx->tree->target_offset = target_offset;
          clean_tree(ndx, limit);
        }
      else if (offset > ndx->tree->offset
               && limit > ndx->tree->limit)
        {
          /* We have to make the same sort of checks as clean_tree()
             does for superseded ranges. Have to merge these someday. */

          const svn_boolean_t insert_range_p =
            (!ndx->tree->next
             || ndx->tree->limit < ndx->tree->next->offset
             || limit > ndx->tree->next->limit);

          if (insert_range_p)
            {
              /* Again, we have to check if the new node and the one
                 to the left of the root override root's range. */
              if (ndx->tree->prev && ndx->tree->prev->limit > offset)
                {
                  /* Replace the data in the splayed node. */
                  ndx->tree->offset = offset;
                  ndx->tree->limit = limit;
                  ndx->tree->target_offset = target_offset;
                }
              else
                {
                  /* Insert the range to the right of the splayed node. */
                  node = alloc_range_index_node(ndx, offset, limit,
                                                target_offset);
                  if ((node->next = ndx->tree->next) != NULL)
                    node->next->prev = node;
                  ndx->tree->next = node;
                  node->prev = ndx->tree;

                  node->right = ndx->tree->right;
                  ndx->tree->right = NULL;
                  node->left = ndx->tree;
                  ndx->tree = node;
                }
              clean_tree(ndx, limit);
            }
          else
            /* Ignore the range */;
        }
      else if (offset < ndx->tree->offset)
        {
          assert(ndx->tree->left == NULL);

          /* Insert the range left of the splayed node */
          node = alloc_range_index_node(ndx, offset, limit, target_offset);
          node->left = node->prev = NULL;
          node->right = node->next = ndx->tree;
          ndx->tree = node->next->prev = node;
          clean_tree(ndx, limit);
        }
      else
        /* Ignore the range */;
    }
}



/* ==================================================================== */
/* Juggling with lists of ranges. */

/* Allocate a node and add it to the range list. LIST is the head of
   the range list, TAIL is the last node in the list. NDX holds the
   freelist; OFFSET, LIMIT and KIND are node data. */
static range_list_node_t *
alloc_range_list (range_list_node_t **list,
                  range_list_node_t **tail,
                  range_index_t *ndx,
                  enum range_kind kind,
                  apr_size_t offset,
                  apr_size_t limit,
                  apr_size_t target_offset)
{
  range_list_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
  node->kind = kind;
  node->offset = offset;
  node->limit = limit;
  node->target_offset = target_offset;
  if (*list == NULL)
    {
      node->prev = node->next = NULL;
      *list = *tail = node;
    }
  else
    {
      node->prev = *tail;
      node->next = NULL;
      (*tail)->next = node;
      *tail = node;
    }
  return *list;
}

/* Free a range list. LIST is the head of the list, NDX holds the freelist. */
static void
free_range_list (range_list_node_t *list, range_index_t *ndx)
{
  while (list)
    {
      range_list_node_t *const node = list;
      list = node->next;
      free_block(node, &ndx->free_list);
    }
}


/* Based on the data in NDX, build a list of ranges that cover
   [OFFSET, LIMIT) in the "virtual" source data.
   NOTE: The range index must be splayed to OFFSET! */

static range_list_node_t *
build_range_list (apr_size_t offset, apr_size_t limit, range_index_t *ndx)
{
  range_list_node_t *range_list = NULL;
  range_list_node_t *last_range = NULL;
  range_index_node_t *node = ndx->tree;

  while (offset < limit)
    {
      if (node == NULL)
        return alloc_range_list(&range_list, &last_range, ndx,
                                range_from_source,
                                offset, limit, 0);

      if (offset < node->offset)
        {
          if (limit <= node->offset)
            return alloc_range_list(&range_list, &last_range, ndx,
                                    range_from_source,
                                    offset, limit, 0);
          else
            {
              alloc_range_list(&range_list, &last_range, ndx,
                               range_from_source,
                               offset, node->offset, 0);
              offset = node->offset;
            }
        }
      else
        {
          /* TODO: (Potential optimization) Investigate if it would
             make sense to forbid range_from_target lengths shorter
             than, say, VD_KEY_SIZE (see vdelta.c) */

          if (offset >= node->limit)
            node = node->next;
          else
            {
              const apr_size_t target_offset =
                offset - node->offset + node->target_offset;

              if (limit <= node->limit)
                return alloc_range_list(&range_list, &last_range, ndx,
                                        range_from_target,
                                        offset, limit, target_offset);
              else
                {
                  alloc_range_list(&range_list, &last_range, ndx,
                                   range_from_target,
                                   offset, node->limit, target_offset);
                  offset = node->limit;
                  node = node->next;
                }
            }
        }
    }

  assert(!"A range's offset isn't smaller than its limit? Impossible!");
  return range_list;
}


/* Copy the instructions from WINDOW that define the range [OFFSET,
   LIMIT) in WINDOW's target stream to TARGET_OFFSET in the window
   represented by BUILD_BATON. Use NDX to find the instructions in
   WINDOW. Allocate space in BUILD_BATON from POOL. */

static void
copy_source_ops (apr_size_t offset, apr_size_t limit,
                 apr_size_t target_offset,
                 svn_txdelta__ops_baton_t *build_baton,
                 const svn_txdelta_window_t *window,
                 const offset_index_t *ndx,
                 apr_pool_t *pool)
{
  const int first_op = search_offset_index (ndx, offset);
  const int last_op = search_offset_index (ndx, limit - 1);
  int op_ndx;

  for (op_ndx = first_op; op_ndx <= last_op; ++op_ndx)
    {
      const svn_txdelta_op_t *const op = &window->ops[op_ndx];
      const apr_size_t *const off = &ndx->offs[op_ndx];

      const apr_size_t fix_offset = (offset > off[0] ? offset - off[0] : 0);
      const apr_size_t fix_limit = (off[1] > limit ? off[1] - limit : 0);

      /* It would be extremely weird if the fixed-up op had zero length. */
      assert(fix_offset + fix_limit < op->length);

      if (op->action_code != svn_txdelta_target)
        {
          /* Delta ops that don't depend on the virtual target can be
             copied to the composite unchanged. */
          const char *const new_data = (op->action_code == svn_txdelta_new
                                        ? (window->new_data->data
                                           + op->offset + fix_offset)
                                        : NULL);

          svn_txdelta__insert_op(build_baton, op->action_code,
                                 op->offset + fix_offset,
                                 op->length - fix_offset - fix_limit,
                                 new_data, pool);
        }
      else
        {
          /* The source of a target copy must start before the current
             offset in the (virtual) target stream. */
          assert(op->offset < off[0]);

          if (op->offset + op->length - fix_limit <= off[0])
            {
              /* The recursion _must_ end, otherwise the delta has
                 circular references, and that is not possible. */
              copy_source_ops(op->offset + fix_offset,
                              op->offset + op->length - fix_limit,
                              target_offset,
                              build_baton, window, ndx, pool);
            }
          else
            {
              /* This is an overlapping target copy.
                 The idea here is to transpose the pattern, then generate
                 another overlapping copy. */
              const apr_size_t ptn_length = off[0] - op->offset;
              const apr_size_t ptn_overlap = fix_offset % ptn_length;
              apr_size_t fix_off = fix_offset;
              apr_size_t tgt_off = target_offset;
              assert(ptn_length > ptn_overlap);

#define MIN(a, b) ((a) < (b) ? (a) : (b))
              if (ptn_overlap >= 0)
                {
                  /* Issue second subrange in the pattern. */
                  const apr_size_t length =
                    MIN(op->length - fix_off - fix_limit,
                        ptn_length - ptn_overlap);
                  copy_source_ops(op->offset + ptn_overlap,
                                  op->offset + ptn_overlap + length,
                                  tgt_off,
                                  build_baton, window, ndx, pool);
                  fix_off += length;
                  tgt_off += length;
                }

              assert(fix_off + fix_limit <= op->length);
              if (ptn_overlap > 0
                  && fix_off + fix_limit < op->length)
                {
                  /* Issue the first subrange in the pattern. */
                  const apr_size_t length =
                    MIN(op->length - fix_off - fix_limit, ptn_overlap);
                  copy_source_ops(op->offset,
                                  op->offset + length,
                                  tgt_off,
                                  build_baton, window, ndx, pool);
                  fix_off += length;
                  tgt_off += length;
                }
#undef MIN

              assert(fix_off + fix_limit <= op->length);
              if (fix_off + fix_limit < op->length)
                {
                  /* Now multiply the pattern */
                  svn_txdelta__insert_op(build_baton, svn_txdelta_target,
                                         tgt_off - ptn_length,
                                         op->length - fix_off - fix_limit,
                                         NULL, pool);
                }
            }
        }

      /* Adjust the target offset for the next op in the list. */
      target_offset += op->length - fix_offset - fix_limit;
    }
}



/* ==================================================================== */
/* Bringing it all together. */


svn_txdelta_window_t *
svn_txdelta__compose_windows (const svn_txdelta_window_t *window_A,
                              const svn_txdelta_window_t *window_B,
                              apr_pool_t *pool)
{
  svn_txdelta__ops_baton_t build_baton = { 0 };
  svn_txdelta_window_t *composite;
  apr_pool_t *subpool = svn_pool_create(pool);
  offset_index_t *offset_index = create_offset_index(window_A, subpool);
  range_index_t *range_index = create_range_index(subpool);
  apr_size_t target_offset = 0;
  int i;

  /* Read the description of the delta composition algorithm in
     notes/fs-improvements.txt before going any further.
     You have been warned. */
  build_baton.new_data = svn_stringbuf_create("", pool);
  for (i = 0; i < window_B->num_ops; ++i)
    {
      const svn_txdelta_op_t *const op = &window_B->ops[i];
      if (op->action_code != svn_txdelta_source)
        {
          /* Delta ops that don't depend on the source can be copied
             to the composite unchanged. */
          const char *const new_data =
            (op->action_code == svn_txdelta_new
             ? window_B->new_data->data + op->offset
             : NULL);
          svn_txdelta__insert_op(&build_baton, op->action_code,
                                 op->offset, op->length,
                                 new_data, pool);
        }
      else
        {
          /* NOTE: Remember that `offset' and `limit' refer to
             positions in window_B's _source_ stream, which is the
             same as window_A's _target_ stream! */
          const apr_size_t offset = op->offset;
          const apr_size_t limit = op->offset + op->length;
          range_list_node_t *range_list, *range;
          apr_size_t tgt_off = target_offset;

          splay_range_index(offset, range_index);
          range_list = build_range_list(offset, limit, range_index);

          for (range = range_list; range; range = range->next)
            {
              if (range->kind == range_from_target)
                svn_txdelta__insert_op(&build_baton, svn_txdelta_target,
                                       range->target_offset,
                                       range->limit - range->offset,
                                       NULL, pool);
              else
                copy_source_ops(range->offset, range->limit, tgt_off,
                                &build_baton, window_A, offset_index,
                                pool);

              tgt_off += range->limit - range->offset;
            }
          assert (tgt_off == target_offset + op->length);

          free_range_list(range_list, range_index);
          insert_range(offset, limit, target_offset, range_index);
        }

      /* Remember the new offset in the would-be target stream. */
      target_offset += op->length;
    }

  svn_pool_destroy(subpool);

  composite = svn_txdelta__make_window(&build_baton, pool);
  composite->sview_offset = window_A->sview_offset;
  composite->sview_len = window_A->sview_len;
  composite->tview_len = window_B->tview_len;
  return composite;
}