contrib/subversion/subversion/libsvn_delta/compose_delta.c

   1 /*
   2  * compose_delta.c:  Delta window composition.
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24
  25 #include <assert.h>
  26
  27 #include <apr_general.h>        /* For APR_INLINE */
  28
  29 #include "svn_delta.h"
  30 #include "svn_pools.h"
  31 #include "delta.h"
  32
  33 /* Define a MIN macro if this platform doesn't already have one. */
  34 #ifndef MIN
  35 #define MIN(a, b) ((a) < (b) ? (a) : (b))
  36 #endif
  37
  38 \f
  39 /* ==================================================================== */
  40 /* Support for efficient small-block allocation from pools. */
  41
  42 /* The following structs will be allocated and freed often: */
  43
  44 /* A node in the range index tree. */
  45 typedef struct range_index_node_t range_index_node_t;
  46 struct range_index_node_t
  47 {
  48   /* 'offset' and 'limit' define the range in the source window. */
  49   apr_size_t offset;
  50   apr_size_t limit;
  51
  52   /* 'target_offset' is where that range is represented in the target. */
  53   apr_size_t target_offset;
  54
  55   /* 'left' and 'right' link the node into a splay tree. */
  56   range_index_node_t *left, *right;
  57
  58   /* 'prev' and 'next' link it into an ordered, doubly-linked list. */
  59   range_index_node_t *prev, *next;
  60 };
  61
  62 /* A node in a list of ranges for source and target op copies. */
  63 enum range_kind
  64   {
  65     range_from_source,
  66     range_from_target
  67   };
  68
  69 typedef struct range_list_node_t range_list_node_t;
  70 struct range_list_node_t
  71 {
  72   /* Where does the range come from?
  73      'offset' and 'limit' always refer to the "virtual" source data
  74      for the second delta window. For a target range, the actual
  75      offset to use for generating the target op is 'target_offset';
  76      that field isn't used by source ranges. */
  77   enum range_kind kind;
  78
  79   /* 'offset' and 'limit' define the range. */
  80   apr_size_t offset;
  81   apr_size_t limit;
  82
  83   /* 'target_offset' is the start of the range in the target. */
  84   apr_size_t target_offset;
  85
  86   /* 'prev' and 'next' link the node into an ordered, doubly-linked list. */
  87   range_list_node_t *prev, *next;
  88 };
  89
  90
  91 /* This is what will be allocated: */
  92 typedef union alloc_block_t alloc_block_t;
  93 union alloc_block_t
  94 {
  95   range_index_node_t index_node;
  96   range_list_node_t list_node;
  97
  98   /* Links free blocks into a freelist. */
  99   alloc_block_t *next_free;
 100 };
 101
 102
 103 /* Allocate a block. */
 104 static APR_INLINE void *
 105 alloc_block(apr_pool_t *pool, alloc_block_t **free_list)
 106 {
 107   alloc_block_t *block;
 108   if (*free_list == NULL)
 109     block = apr_palloc(pool, sizeof(*block));
 110   else
 111     {
 112       block = *free_list;
 113       *free_list = block->next_free;
 114     }
 115   return block;
 116 }
 117
 118 /* Return the block back to the free list. */
 119 static APR_INLINE void
 120 free_block(void *ptr, alloc_block_t **free_list)
 121 {
 122   /* Wrapper functions take care of type safety. */
 123   alloc_block_t *const block = ptr;
 124   block->next_free = *free_list;
 125   *free_list = block;
 126 }
 127
 128
 129 \f
 130 /* ==================================================================== */
 131 /* Mapping offsets in the target streem to txdelta ops. */
 132
 133 typedef struct offset_index_t
 134 {
 135   int length;
 136   apr_size_t *offs;
 137 } offset_index_t;
 138
 139 /* Create an index mapping target stream offsets to delta ops in
 140    WINDOW. Allocate from POOL. */
 141
 142 static offset_index_t *
 143 create_offset_index(const svn_txdelta_window_t *window, apr_pool_t *pool)
 144 {
 145   offset_index_t *ndx = apr_palloc(pool, sizeof(*ndx));
 146   apr_size_t offset = 0;
 147   int i;
 148
 149   ndx->length = window->num_ops;
 150   ndx->offs = apr_palloc(pool, (ndx->length + 1) * sizeof(*ndx->offs));
 151
 152   for (i = 0; i < ndx->length; ++i)
 153     {
 154       ndx->offs[i] = offset;
 155       offset += window->ops[i].length;
 156     }
 157   ndx->offs[ndx->length] = offset;
 158
 159   return ndx;
 160 }
 161
 162 /* Find the index of the delta op thet defines that data at OFFSET in
 163    NDX. HINT is an arbitrary positin within NDX and doesn't even need
 164    to be valid. To effectively speed up the search, use the last result
 165    as hint because most lookups come as a sequence of decreasing values
 166    for OFFSET and they concentrate on the lower end of the array. */
 167
 168 static apr_size_t
 169 search_offset_index(const offset_index_t *ndx,
 170                     apr_size_t offset,
 171                     apr_size_t hint)
 172 {
 173   apr_size_t lo, hi, op;
 174
 175   assert(offset < ndx->offs[ndx->length]);
 176
 177   lo = 0;
 178   hi = ndx->length;
 179
 180   /* If we got a valid hint, use it to reduce the range to cover.
 181      Note that this will only be useful if either the hint is a
 182      hit (i.e. equals the desired result) or narrows the range
 183      length by a factor larger than 2. */
 184
 185   if (hint < hi)
 186     {
 187       if (offset < ndx->offs[hint])
 188         hi = hint;
 189       else if (offset < ndx->offs[hint+1])
 190         return hint;
 191       else
 192         lo = hint+1;
 193     }
 194
 195   /* ordinary binary search */
 196
 197   for (op = (lo + hi)/2; lo != hi; op = (lo + hi)/2)
 198     {
 199       if (offset < ndx->offs[op])
 200         hi = op;
 201       else
 202         lo = ++op;
 203     }
 204
 205   --lo;
 206   assert(ndx->offs[lo] <= offset && offset < ndx->offs[lo + 1]);
 207   return lo;
 208 }
 209
 210
 211 \f
 212 /* ==================================================================== */
 213 /* Mapping ranges in the source stream to ranges in the composed delta. */
 214
 215 /* The range index tree. */
 216 typedef struct range_index_t
 217 {
 218   range_index_node_t *tree;
 219   alloc_block_t *free_list;
 220   apr_pool_t *pool;
 221 } range_index_t;
 222
 223 /* Create a range index tree. Allocate from POOL. */
 224 static range_index_t *
 225 create_range_index(apr_pool_t *pool)
 226 {
 227   range_index_t *ndx = apr_palloc(pool, sizeof(*ndx));
 228   ndx->tree = NULL;
 229   ndx->pool = pool;
 230   ndx->free_list = NULL;
 231   return ndx;
 232 }
 233
 234 /* Allocate a node for the range index tree. */
 235 static range_index_node_t *
 236 alloc_range_index_node(range_index_t *ndx,
 237                        apr_size_t offset,
 238                        apr_size_t limit,
 239                        apr_size_t target_offset)
 240 {
 241   range_index_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
 242   node->offset = offset;
 243   node->limit = limit;
 244   node->target_offset = target_offset;
 245   node->left = node->right = NULL;
 246   node->prev = node->next = NULL;
 247   return node;
 248 }
 249
 250 /* Free a node from the range index tree. */
 251 static void
 252 free_range_index_node(range_index_t *ndx, range_index_node_t *node)
 253 {
 254   if (node->next)
 255     node->next->prev = node->prev;
 256   if (node->prev)
 257     node->prev->next = node->next;
 258   free_block(node, &ndx->free_list);
 259 }
 260
 261
 262 /* Splay the index tree, using OFFSET as the key. */
 263
 264 static void
 265 splay_range_index(apr_size_t offset, range_index_t *ndx)
 266 {
 267   range_index_node_t *tree = ndx->tree;
 268   range_index_node_t scratch_node;
 269   range_index_node_t *left, *right;
 270
 271   if (tree == NULL)
 272     return;
 273
 274   scratch_node.left = scratch_node.right = NULL;
 275   left = right = &scratch_node;
 276
 277   for (;;)
 278     {
 279       if (offset < tree->offset)
 280         {
 281           if (tree->left != NULL
 282               && offset < tree->left->offset)
 283             {
 284               /* Right rotation */
 285               range_index_node_t *const node = tree->left;
 286               tree->left = node->right;
 287               node->right = tree;
 288               tree = node;
 289             }
 290           if (tree->left == NULL)
 291             break;
 292
 293           /* Remember the right subtree */
 294           right->left = tree;
 295           right = tree;
 296           tree = tree->left;
 297         }
 298       else if (offset > tree->offset)
 299         {
 300           if (tree->right != NULL
 301               && offset > tree->right->offset)
 302             {
 303               /* Left rotation */
 304               range_index_node_t *const node = tree->right;
 305               tree->right = node->left;
 306               node->left = tree;
 307               tree = node;
 308             }
 309           if (tree->right == NULL)
 310             break;
 311
 312           /* Remember the left subtree */
 313           left->right = tree;
 314           left = tree;
 315           tree = tree->right;
 316         }
 317       else
 318         break;
 319     }
 320
 321   /* Link in the left and right subtrees */
 322   left->right = tree->left;
 323   right->left = tree->right;
 324   tree->left  = scratch_node.right;
 325   tree->right = scratch_node.left;
 326
 327   /* The basic top-down splay is finished, but we may still need to
 328      turn the tree around. What we want is to put the node with the
 329      largest offset where node->offset <= offset at the top of the
 330      tree, so that we can insert the new data (or search for existing
 331      ranges) to the right of the root. This makes cleaning up the
 332      tree after an insert much simpler, and -- incidentally -- makes
 333      the whole range index magic work. */
 334   if (offset < tree->offset && tree->left != NULL)
 335     {
 336       if (tree->left->right == NULL)
 337         {
 338           /* A single right rotation is enough. */
 339           range_index_node_t *const node = tree->left;
 340           tree->left = node->right; /* Which is always NULL. */
 341           node->right = tree;
 342           tree = node;
 343         }
 344       else
 345         {
 346           /* Slide down to the rightmost node in the left subtree. */
 347           range_index_node_t **nodep = &tree->left;
 348           while ((*nodep)->right != NULL)
 349             nodep = &(*nodep)->right;
 350
 351           /* Now move this node to root in one giant promotion. */
 352           right = tree;
 353           left = tree->left;
 354           tree = *nodep;
 355           *nodep = tree->left;
 356           right->left = tree->right; /* Which is always NULL, too. */
 357           tree->left = left;
 358           tree->right = right;
 359         }
 360     }
 361
 362   /* Sanity check ... */
 363   assert((offset >= tree->offset)
 364          || ((tree->left == NULL)
 365              && (tree->prev == NULL)));
 366   ndx->tree = tree;
 367 }
 368
 369
 370 /* Remove all ranges from NDX that fall into the root's range.  To
 371    keep the range index as small as possible, we must also remove
 372    nodes that don't fall into the new range, but have become redundant
 373    because the new range overlaps the beginning of the next range.
 374    Like this:
 375
 376        new-range: |-----------------|
 377          range-1:         |-----------------|
 378          range-2:                |--------------------|
 379
 380    Before new-range was inserted, range-1 and range-2 were both
 381    necessary. Now the union of new-range and range-2 completely covers
 382    range-1, which has become redundant now.
 383
 384    FIXME: But, of course, there's a catch. range-1 must still remain
 385    in the tree if we want to optimize the number of target copy ops in
 386    the case were a copy falls within range-1, but starts before
 387    range-2 and ends after new-range. */
 388
 389 static void
 390 delete_subtree(range_index_t *ndx, range_index_node_t *node)
 391 {
 392   if (node != NULL)
 393     {
 394       delete_subtree(ndx, node->left);
 395       delete_subtree(ndx, node->right);
 396       free_range_index_node(ndx, node);
 397     }
 398 }
 399
 400 static void
 401 clean_tree(range_index_t *ndx, apr_size_t limit)
 402 {
 403   apr_size_t top_offset = limit + 1;
 404   range_index_node_t **nodep = &ndx->tree->right;
 405   while (*nodep != NULL)
 406     {
 407       range_index_node_t *const node = *nodep;
 408       apr_size_t const offset =
 409         (node->right != NULL && node->right->offset < top_offset
 410          ? node->right->offset
 411          : top_offset);
 412
 413       if (node->limit <= limit
 414           || (node->offset < limit && offset < limit))
 415         {
 416           *nodep = node->right;
 417           node->right = NULL;
 418           delete_subtree(ndx, node);
 419         }
 420       else
 421         {
 422           top_offset = node->offset;
 423           nodep = &node->left;
 424         }
 425     }
 426 }
 427
 428
 429 /* Add a range [OFFSET, LIMIT) into NDX. If NDX already contains a
 430    range that encloses [OFFSET, LIMIT), do nothing. Otherwise, remove
 431    all ranges from NDX that are superseded by the new range.
 432    NOTE: The range index must be splayed to OFFSET! */
 433
 434 static void
 435 insert_range(apr_size_t offset, apr_size_t limit, apr_size_t target_offset,
 436              range_index_t *ndx)
 437 {
 438   range_index_node_t *node = NULL;
 439
 440   if (ndx->tree == NULL)
 441     {
 442       node = alloc_range_index_node(ndx, offset, limit, target_offset);
 443       ndx->tree = node;
 444     }
 445   else
 446     {
 447       if (offset == ndx->tree->offset
 448           && limit > ndx->tree->limit)
 449         {
 450           ndx->tree->limit = limit;
 451           ndx->tree->target_offset = target_offset;
 452           clean_tree(ndx, limit);
 453         }
 454       else if (offset > ndx->tree->offset
 455                && limit > ndx->tree->limit)
 456         {
 457           /* We have to make the same sort of checks as clean_tree()
 458              does for superseded ranges. Have to merge these someday. */
 459
 460           const svn_boolean_t insert_range_p =
 461             (!ndx->tree->next
 462              || ndx->tree->limit < ndx->tree->next->offset
 463              || limit > ndx->tree->next->limit);
 464
 465           if (insert_range_p)
 466             {
 467               /* Again, we have to check if the new node and the one
 468                  to the left of the root override root's range. */
 469               if (ndx->tree->prev && ndx->tree->prev->limit > offset)
 470                 {
 471                   /* Replace the data in the splayed node. */
 472                   ndx->tree->offset = offset;
 473                   ndx->tree->limit = limit;
 474                   ndx->tree->target_offset = target_offset;
 475                 }
 476               else
 477                 {
 478                   /* Insert the range to the right of the splayed node. */
 479                   node = alloc_range_index_node(ndx, offset, limit,
 480                                                 target_offset);
 481                   if ((node->next = ndx->tree->next) != NULL)
 482                     node->next->prev = node;
 483                   ndx->tree->next = node;
 484                   node->prev = ndx->tree;
 485
 486                   node->right = ndx->tree->right;
 487                   ndx->tree->right = NULL;
 488                   node->left = ndx->tree;
 489                   ndx->tree = node;
 490                 }
 491               clean_tree(ndx, limit);
 492             }
 493           else
 494             /* Ignore the range */;
 495         }
 496       else if (offset < ndx->tree->offset)
 497         {
 498           assert(ndx->tree->left == NULL);
 499
 500           /* Insert the range left of the splayed node */
 501           node = alloc_range_index_node(ndx, offset, limit, target_offset);
 502           node->left = node->prev = NULL;
 503           node->right = node->next = ndx->tree;
 504           ndx->tree = node->next->prev = node;
 505           clean_tree(ndx, limit);
 506         }
 507       else
 508         /* Ignore the range */;
 509     }
 510 }
 511
 512
 513 \f
 514 /* ==================================================================== */
 515 /* Juggling with lists of ranges. */
 516
 517 /* Allocate a node and add it to the range list. LIST is the head of
 518    the range list, TAIL is the last node in the list. NDX holds the
 519    freelist; OFFSET, LIMIT and KIND are node data. */
 520 static range_list_node_t *
 521 alloc_range_list(range_list_node_t **list,
 522                  range_list_node_t **tail,
 523                  range_index_t *ndx,
 524                  enum range_kind kind,
 525                  apr_size_t offset,
 526                  apr_size_t limit,
 527                  apr_size_t target_offset)
 528 {
 529   range_list_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
 530   node->kind = kind;
 531   node->offset = offset;
 532   node->limit = limit;
 533   node->target_offset = target_offset;
 534   if (*list == NULL)
 535     {
 536       node->prev = node->next = NULL;
 537       *list = *tail = node;
 538     }
 539   else
 540     {
 541       node->prev = *tail;
 542       node->next = NULL;
 543       (*tail)->next = node;
 544       *tail = node;
 545     }
 546   return *list;
 547 }
 548
 549 /* Free a range list. LIST is the head of the list, NDX holds the freelist. */
 550 static void
 551 free_range_list(range_list_node_t *list, range_index_t *ndx)
 552 {
 553   while (list)
 554     {
 555       range_list_node_t *const node = list;
 556       list = node->next;
 557       free_block(node, &ndx->free_list);
 558     }
 559 }
 560
 561
 562 /* Based on the data in NDX, build a list of ranges that cover
 563    [OFFSET, LIMIT) in the "virtual" source data.
 564    NOTE: The range index must be splayed to OFFSET! */
 565
 566 static range_list_node_t *
 567 build_range_list(apr_size_t offset, apr_size_t limit, range_index_t *ndx)
 568 {
 569   range_list_node_t *range_list = NULL;
 570   range_list_node_t *last_range = NULL;
 571   range_index_node_t *node = ndx->tree;
 572
 573   while (offset < limit)
 574     {
 575       if (node == NULL)
 576         return alloc_range_list(&range_list, &last_range, ndx,
 577                                 range_from_source,
 578                                 offset, limit, 0);
 579
 580       if (offset < node->offset)
 581         {
 582           if (limit <= node->offset)
 583             return alloc_range_list(&range_list, &last_range, ndx,
 584                                     range_from_source,
 585                                     offset, limit, 0);
 586           else
 587             {
 588               alloc_range_list(&range_list, &last_range, ndx,
 589                                range_from_source,
 590                                offset, node->offset, 0);
 591               offset = node->offset;
 592             }
 593         }
 594       else
 595         {
 596           /* TODO: (Potential optimization) Investigate if it would
 597              make sense to forbid short range_from_target lengths
 598              (this comment originally said "shorter than, say,
 599              VD_KEY_SIZE (see vdelta.c)", but Subversion no longer
 600              uses vdelta). */
 601
 602           if (offset >= node->limit)
 603             node = node->next;
 604           else
 605             {
 606               const apr_size_t target_offset =
 607                 offset - node->offset + node->target_offset;
 608
 609               if (limit <= node->limit)
 610                 return alloc_range_list(&range_list, &last_range, ndx,
 611                                         range_from_target,
 612                                         offset, limit, target_offset);
 613               else
 614                 {
 615                   alloc_range_list(&range_list, &last_range, ndx,
 616                                    range_from_target,
 617                                    offset, node->limit, target_offset);
 618                   offset = node->limit;
 619                   node = node->next;
 620                 }
 621             }
 622         }
 623     }
 624
 625   /* A range's offset isn't smaller than its limit? Impossible! */
 626   SVN_ERR_MALFUNCTION_NO_RETURN();
 627 }
 628
 629
 630 /* Copy the instructions from WINDOW that define the range [OFFSET,
 631    LIMIT) in WINDOW's target stream to TARGET_OFFSET in the window
 632    represented by BUILD_BATON. HINT is a position in the instructions
 633    array that helps finding the position for OFFSET. A safe default
 634    is 0. Use NDX to find the instructions in WINDOW. Allocate space
 635    in BUILD_BATON from POOL. */
 636
 637 static void
 638 copy_source_ops(apr_size_t offset, apr_size_t limit,
 639                 apr_size_t target_offset,
 640                 apr_size_t hint,
 641                 svn_txdelta__ops_baton_t *build_baton,
 642                 const svn_txdelta_window_t *window,
 643                 const offset_index_t *ndx,
 644                 apr_pool_t *pool)
 645 {
 646   apr_size_t op_ndx = search_offset_index(ndx, offset, hint);
 647   for (;; ++op_ndx)
 648     {
 649       const svn_txdelta_op_t *const op = &window->ops[op_ndx];
 650       const apr_size_t *const off = &ndx->offs[op_ndx];
 651       apr_size_t fix_offset;
 652       apr_size_t fix_limit;
 653
 654       if (off[0] >= limit)
 655           break;
 656
 657       fix_offset = (offset > off[0] ? offset - off[0] : 0);
 658       fix_limit = (off[1] > limit ? off[1] - limit : 0);
 659
 660       /* It would be extremely weird if the fixed-up op had zero length. */
 661       assert(fix_offset + fix_limit < op->length);
 662
 663       if (op->action_code != svn_txdelta_target)
 664         {
 665           /* Delta ops that don't depend on the virtual target can be
 666              copied to the composite unchanged. */
 667           const char *const new_data = (op->action_code == svn_txdelta_new
 668                                         ? (window->new_data->data
 669                                            + op->offset + fix_offset)
 670                                         : NULL);
 671
 672           svn_txdelta__insert_op(build_baton, op->action_code,
 673                                  op->offset + fix_offset,
 674                                  op->length - fix_offset - fix_limit,
 675                                  new_data, pool);
 676         }
 677       else
 678         {
 679           /* The source of a target copy must start before the current
 680              offset in the (virtual) target stream. */
 681           assert(op->offset < off[0]);
 682
 683           if (op->offset + op->length - fix_limit <= off[0])
 684             {
 685               /* The recursion _must_ end, otherwise the delta has
 686                  circular references, and that is not possible. */
 687               copy_source_ops(op->offset + fix_offset,
 688                               op->offset + op->length - fix_limit,
 689                               target_offset,
 690                               op_ndx,
 691                               build_baton, window, ndx, pool);
 692             }
 693           else
 694             {
 695               /* This is an overlapping target copy.
 696                  The idea here is to transpose the pattern, then generate
 697                  another overlapping copy. */
 698               const apr_size_t ptn_length = off[0] - op->offset;
 699               const apr_size_t ptn_overlap = fix_offset % ptn_length;
 700               apr_size_t fix_off = fix_offset;
 701               apr_size_t tgt_off = target_offset;
 702               assert(ptn_length > ptn_overlap);
 703
 704               /* ### FIXME: ptn_overlap is unsigned, so the if() condition
 705                  below is always true!  Either it should be '> 0', or the
 706                  code block should be unconditional.  See also r842362. */
 707               if (ptn_overlap >= 0)
 708                 {
 709                   /* Issue second subrange in the pattern. */
 710                   const apr_size_t length =
 711                     MIN(op->length - fix_off - fix_limit,
 712                         ptn_length - ptn_overlap);
 713                   copy_source_ops(op->offset + ptn_overlap,
 714                                   op->offset + ptn_overlap + length,
 715                                   tgt_off,
 716                                   op_ndx,
 717                                   build_baton, window, ndx, pool);
 718                   fix_off += length;
 719                   tgt_off += length;
 720                 }
 721
 722               assert(fix_off + fix_limit <= op->length);
 723               if (ptn_overlap > 0
 724                   && fix_off + fix_limit < op->length)
 725                 {
 726                   /* Issue the first subrange in the pattern. */
 727                   const apr_size_t length =
 728                     MIN(op->length - fix_off - fix_limit, ptn_overlap);
 729                   copy_source_ops(op->offset,
 730                                   op->offset + length,
 731                                   tgt_off,
 732                                   op_ndx,
 733                                   build_baton, window, ndx, pool);
 734                   fix_off += length;
 735                   tgt_off += length;
 736                 }
 737
 738               assert(fix_off + fix_limit <= op->length);
 739               if (fix_off + fix_limit < op->length)
 740                 {
 741                   /* Now multiply the pattern */
 742                   svn_txdelta__insert_op(build_baton, svn_txdelta_target,
 743                                          tgt_off - ptn_length,
 744                                          op->length - fix_off - fix_limit,
 745                                          NULL, pool);
 746                 }
 747             }
 748         }
 749
 750       /* Adjust the target offset for the next op in the list. */
 751       target_offset += op->length - fix_offset - fix_limit;
 752     }
 753 }
 754
 755
 756 \f
 757 /* ==================================================================== */
 758 /* Bringing it all together. */
 759
 760
 761 svn_txdelta_window_t *
 762 svn_txdelta_compose_windows(const svn_txdelta_window_t *window_A,
 763                             const svn_txdelta_window_t *window_B,
 764                             apr_pool_t *pool)
 765 {
 766   svn_txdelta__ops_baton_t build_baton = { 0 };
 767   svn_txdelta_window_t *composite;
 768   apr_pool_t *subpool = svn_pool_create(pool);
 769   offset_index_t *offset_index = create_offset_index(window_A, subpool);
 770   range_index_t *range_index = create_range_index(subpool);
 771   apr_size_t target_offset = 0;
 772   int i;
 773
 774   /* Read the description of the delta composition algorithm in
 775      notes/fs-improvements.txt before going any further.
 776      You have been warned. */
 777   build_baton.new_data = svn_stringbuf_create_empty(pool);
 778   for (i = 0; i < window_B->num_ops; ++i)
 779     {
 780       const svn_txdelta_op_t *const op = &window_B->ops[i];
 781       if (op->action_code != svn_txdelta_source)
 782         {
 783           /* Delta ops that don't depend on the source can be copied
 784              to the composite unchanged. */
 785           const char *const new_data =
 786             (op->action_code == svn_txdelta_new
 787              ? window_B->new_data->data + op->offset
 788              : NULL);
 789           svn_txdelta__insert_op(&build_baton, op->action_code,
 790                                  op->offset, op->length,
 791                                  new_data, pool);
 792         }
 793       else
 794         {
 795           /* NOTE: Remember that `offset' and `limit' refer to
 796              positions in window_B's _source_ stream, which is the
 797              same as window_A's _target_ stream! */
 798           const apr_size_t offset = op->offset;
 799           const apr_size_t limit = op->offset + op->length;
 800           range_list_node_t *range_list, *range;
 801           apr_size_t tgt_off = target_offset;
 802
 803           splay_range_index(offset, range_index);
 804           range_list = build_range_list(offset, limit, range_index);
 805
 806           for (range = range_list; range; range = range->next)
 807             {
 808               if (range->kind == range_from_target)
 809                 svn_txdelta__insert_op(&build_baton, svn_txdelta_target,
 810                                        range->target_offset,
 811                                        range->limit - range->offset,
 812                                        NULL, pool);
 813               else
 814                 copy_source_ops(range->offset, range->limit, tgt_off, 0,
 815                                 &build_baton, window_A, offset_index,
 816                                 pool);
 817
 818               tgt_off += range->limit - range->offset;
 819             }
 820           assert(tgt_off == target_offset + op->length);
 821
 822           free_range_list(range_list, range_index);
 823           insert_range(offset, limit, target_offset, range_index);
 824         }
 825
 826       /* Remember the new offset in the would-be target stream. */
 827       target_offset += op->length;
 828     }
 829
 830   svn_pool_destroy(subpool);
 831
 832   composite = svn_txdelta__make_window(&build_baton, pool);
 833   composite->sview_offset = window_A->sview_offset;
 834   composite->sview_len = window_A->sview_len;
 835   composite->tview_len = window_B->tview_len;
 836   return composite;
 837 }