1251881Speter/* 2251881Speter * compose_delta.c: Delta window composition. 3251881Speter * 4251881Speter * ==================================================================== 5251881Speter * Licensed to the Apache Software Foundation (ASF) under one 6251881Speter * or more contributor license agreements. See the NOTICE file 7251881Speter * distributed with this work for additional information 8251881Speter * regarding copyright ownership. The ASF licenses this file 9251881Speter * to you under the Apache License, Version 2.0 (the 10251881Speter * "License"); you may not use this file except in compliance 11251881Speter * with the License. You may obtain a copy of the License at 12251881Speter * 13251881Speter * http://www.apache.org/licenses/LICENSE-2.0 14251881Speter * 15251881Speter * Unless required by applicable law or agreed to in writing, 16251881Speter * software distributed under the License is distributed on an 17251881Speter * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 18251881Speter * KIND, either express or implied. See the License for the 19251881Speter * specific language governing permissions and limitations 20251881Speter * under the License. 21251881Speter * ==================================================================== 22251881Speter */ 23251881Speter 24251881Speter 25251881Speter#include <assert.h> 26251881Speter 27251881Speter#include <apr_general.h> /* For APR_INLINE */ 28251881Speter 29251881Speter#include "svn_delta.h" 30251881Speter#include "svn_pools.h" 31251881Speter#include "delta.h" 32251881Speter 33251881Speter/* Define a MIN macro if this platform doesn't already have one. */ 34251881Speter#ifndef MIN 35251881Speter#define MIN(a, b) ((a) < (b) ? (a) : (b)) 36251881Speter#endif 37251881Speter 38251881Speter 39251881Speter/* ==================================================================== */ 40251881Speter/* Support for efficient small-block allocation from pools. */ 41251881Speter 42251881Speter/* The following structs will be allocated and freed often: */ 43251881Speter 44251881Speter/* A node in the range index tree. */ 45251881Spetertypedef struct range_index_node_t range_index_node_t; 46251881Speterstruct range_index_node_t 47251881Speter{ 48251881Speter /* 'offset' and 'limit' define the range in the source window. */ 49251881Speter apr_size_t offset; 50251881Speter apr_size_t limit; 51251881Speter 52251881Speter /* 'target_offset' is where that range is represented in the target. */ 53251881Speter apr_size_t target_offset; 54251881Speter 55251881Speter /* 'left' and 'right' link the node into a splay tree. */ 56251881Speter range_index_node_t *left, *right; 57251881Speter 58251881Speter /* 'prev' and 'next' link it into an ordered, doubly-linked list. */ 59251881Speter range_index_node_t *prev, *next; 60251881Speter}; 61251881Speter 62251881Speter/* A node in a list of ranges for source and target op copies. */ 63251881Speterenum range_kind 64251881Speter { 65251881Speter range_from_source, 66251881Speter range_from_target 67251881Speter }; 68251881Speter 69251881Spetertypedef struct range_list_node_t range_list_node_t; 70251881Speterstruct range_list_node_t 71251881Speter{ 72251881Speter /* Where does the range come from? 73251881Speter 'offset' and 'limit' always refer to the "virtual" source data 74251881Speter for the second delta window. For a target range, the actual 75251881Speter offset to use for generating the target op is 'target_offset'; 76251881Speter that field isn't used by source ranges. */ 77251881Speter enum range_kind kind; 78251881Speter 79251881Speter /* 'offset' and 'limit' define the range. */ 80251881Speter apr_size_t offset; 81251881Speter apr_size_t limit; 82251881Speter 83251881Speter /* 'target_offset' is the start of the range in the target. */ 84251881Speter apr_size_t target_offset; 85251881Speter 86251881Speter /* 'prev' and 'next' link the node into an ordered, doubly-linked list. */ 87251881Speter range_list_node_t *prev, *next; 88251881Speter}; 89251881Speter 90251881Speter 91251881Speter/* This is what will be allocated: */ 92251881Spetertypedef union alloc_block_t alloc_block_t; 93251881Speterunion alloc_block_t 94251881Speter{ 95251881Speter range_index_node_t index_node; 96251881Speter range_list_node_t list_node; 97251881Speter 98251881Speter /* Links free blocks into a freelist. */ 99251881Speter alloc_block_t *next_free; 100251881Speter}; 101251881Speter 102251881Speter 103251881Speter/* Allocate a block. */ 104251881Speterstatic APR_INLINE void * 105251881Speteralloc_block(apr_pool_t *pool, alloc_block_t **free_list) 106251881Speter{ 107251881Speter alloc_block_t *block; 108251881Speter if (*free_list == NULL) 109251881Speter block = apr_palloc(pool, sizeof(*block)); 110251881Speter else 111251881Speter { 112251881Speter block = *free_list; 113251881Speter *free_list = block->next_free; 114251881Speter } 115251881Speter return block; 116251881Speter} 117251881Speter 118251881Speter/* Return the block back to the free list. */ 119251881Speterstatic APR_INLINE void 120251881Speterfree_block(void *ptr, alloc_block_t **free_list) 121251881Speter{ 122251881Speter /* Wrapper functions take care of type safety. */ 123251881Speter alloc_block_t *const block = ptr; 124251881Speter block->next_free = *free_list; 125251881Speter *free_list = block; 126251881Speter} 127251881Speter 128251881Speter 129251881Speter 130251881Speter/* ==================================================================== */ 131251881Speter/* Mapping offsets in the target streem to txdelta ops. */ 132251881Speter 133251881Spetertypedef struct offset_index_t 134251881Speter{ 135251881Speter int length; 136251881Speter apr_size_t *offs; 137251881Speter} offset_index_t; 138251881Speter 139251881Speter/* Create an index mapping target stream offsets to delta ops in 140251881Speter WINDOW. Allocate from POOL. */ 141251881Speter 142251881Speterstatic offset_index_t * 143251881Spetercreate_offset_index(const svn_txdelta_window_t *window, apr_pool_t *pool) 144251881Speter{ 145251881Speter offset_index_t *ndx = apr_palloc(pool, sizeof(*ndx)); 146251881Speter apr_size_t offset = 0; 147251881Speter int i; 148251881Speter 149251881Speter ndx->length = window->num_ops; 150251881Speter ndx->offs = apr_palloc(pool, (ndx->length + 1) * sizeof(*ndx->offs)); 151251881Speter 152251881Speter for (i = 0; i < ndx->length; ++i) 153251881Speter { 154251881Speter ndx->offs[i] = offset; 155251881Speter offset += window->ops[i].length; 156251881Speter } 157251881Speter ndx->offs[ndx->length] = offset; 158251881Speter 159251881Speter return ndx; 160251881Speter} 161251881Speter 162251881Speter/* Find the index of the delta op thet defines that data at OFFSET in 163251881Speter NDX. HINT is an arbitrary positin within NDX and doesn't even need 164251881Speter to be valid. To effectively speed up the search, use the last result 165251881Speter as hint because most lookups come as a sequence of decreasing values 166251881Speter for OFFSET and they concentrate on the lower end of the array. */ 167251881Speter 168251881Speterstatic apr_size_t 169251881Spetersearch_offset_index(const offset_index_t *ndx, 170251881Speter apr_size_t offset, 171251881Speter apr_size_t hint) 172251881Speter{ 173251881Speter apr_size_t lo, hi, op; 174251881Speter 175251881Speter assert(offset < ndx->offs[ndx->length]); 176251881Speter 177251881Speter lo = 0; 178251881Speter hi = ndx->length; 179251881Speter 180251881Speter /* If we got a valid hint, use it to reduce the range to cover. 181251881Speter Note that this will only be useful if either the hint is a 182251881Speter hit (i.e. equals the desired result) or narrows the range 183251881Speter length by a factor larger than 2. */ 184251881Speter 185251881Speter if (hint < hi) 186251881Speter { 187251881Speter if (offset < ndx->offs[hint]) 188251881Speter hi = hint; 189251881Speter else if (offset < ndx->offs[hint+1]) 190251881Speter return hint; 191251881Speter else 192251881Speter lo = hint+1; 193251881Speter } 194251881Speter 195251881Speter /* ordinary binary search */ 196251881Speter 197251881Speter for (op = (lo + hi)/2; lo != hi; op = (lo + hi)/2) 198251881Speter { 199251881Speter if (offset < ndx->offs[op]) 200251881Speter hi = op; 201251881Speter else 202251881Speter lo = ++op; 203251881Speter } 204251881Speter 205251881Speter --lo; 206251881Speter assert(ndx->offs[lo] <= offset && offset < ndx->offs[lo + 1]); 207251881Speter return lo; 208251881Speter} 209251881Speter 210251881Speter 211251881Speter 212251881Speter/* ==================================================================== */ 213251881Speter/* Mapping ranges in the source stream to ranges in the composed delta. */ 214251881Speter 215251881Speter/* The range index tree. */ 216251881Spetertypedef struct range_index_t 217251881Speter{ 218251881Speter range_index_node_t *tree; 219251881Speter alloc_block_t *free_list; 220251881Speter apr_pool_t *pool; 221251881Speter} range_index_t; 222251881Speter 223251881Speter/* Create a range index tree. Allocate from POOL. */ 224251881Speterstatic range_index_t * 225251881Spetercreate_range_index(apr_pool_t *pool) 226251881Speter{ 227251881Speter range_index_t *ndx = apr_palloc(pool, sizeof(*ndx)); 228251881Speter ndx->tree = NULL; 229251881Speter ndx->pool = pool; 230251881Speter ndx->free_list = NULL; 231251881Speter return ndx; 232251881Speter} 233251881Speter 234251881Speter/* Allocate a node for the range index tree. */ 235251881Speterstatic range_index_node_t * 236251881Speteralloc_range_index_node(range_index_t *ndx, 237251881Speter apr_size_t offset, 238251881Speter apr_size_t limit, 239251881Speter apr_size_t target_offset) 240251881Speter{ 241251881Speter range_index_node_t *const node = alloc_block(ndx->pool, &ndx->free_list); 242251881Speter node->offset = offset; 243251881Speter node->limit = limit; 244251881Speter node->target_offset = target_offset; 245251881Speter node->left = node->right = NULL; 246251881Speter node->prev = node->next = NULL; 247251881Speter return node; 248251881Speter} 249251881Speter 250251881Speter/* Free a node from the range index tree. */ 251251881Speterstatic void 252251881Speterfree_range_index_node(range_index_t *ndx, range_index_node_t *node) 253251881Speter{ 254251881Speter if (node->next) 255251881Speter node->next->prev = node->prev; 256251881Speter if (node->prev) 257251881Speter node->prev->next = node->next; 258251881Speter free_block(node, &ndx->free_list); 259251881Speter} 260251881Speter 261251881Speter 262251881Speter/* Splay the index tree, using OFFSET as the key. */ 263251881Speter 264251881Speterstatic void 265251881Spetersplay_range_index(apr_size_t offset, range_index_t *ndx) 266251881Speter{ 267251881Speter range_index_node_t *tree = ndx->tree; 268251881Speter range_index_node_t scratch_node; 269251881Speter range_index_node_t *left, *right; 270251881Speter 271251881Speter if (tree == NULL) 272251881Speter return; 273251881Speter 274251881Speter scratch_node.left = scratch_node.right = NULL; 275251881Speter left = right = &scratch_node; 276251881Speter 277251881Speter for (;;) 278251881Speter { 279251881Speter if (offset < tree->offset) 280251881Speter { 281251881Speter if (tree->left != NULL 282251881Speter && offset < tree->left->offset) 283251881Speter { 284251881Speter /* Right rotation */ 285251881Speter range_index_node_t *const node = tree->left; 286251881Speter tree->left = node->right; 287251881Speter node->right = tree; 288251881Speter tree = node; 289251881Speter } 290251881Speter if (tree->left == NULL) 291251881Speter break; 292251881Speter 293251881Speter /* Remember the right subtree */ 294251881Speter right->left = tree; 295251881Speter right = tree; 296251881Speter tree = tree->left; 297251881Speter } 298251881Speter else if (offset > tree->offset) 299251881Speter { 300251881Speter if (tree->right != NULL 301251881Speter && offset > tree->right->offset) 302251881Speter { 303251881Speter /* Left rotation */ 304251881Speter range_index_node_t *const node = tree->right; 305251881Speter tree->right = node->left; 306251881Speter node->left = tree; 307251881Speter tree = node; 308251881Speter } 309251881Speter if (tree->right == NULL) 310251881Speter break; 311251881Speter 312251881Speter /* Remember the left subtree */ 313251881Speter left->right = tree; 314251881Speter left = tree; 315251881Speter tree = tree->right; 316251881Speter } 317251881Speter else 318251881Speter break; 319251881Speter } 320251881Speter 321251881Speter /* Link in the left and right subtrees */ 322251881Speter left->right = tree->left; 323251881Speter right->left = tree->right; 324251881Speter tree->left = scratch_node.right; 325251881Speter tree->right = scratch_node.left; 326251881Speter 327251881Speter /* The basic top-down splay is finished, but we may still need to 328251881Speter turn the tree around. What we want is to put the node with the 329251881Speter largest offset where node->offset <= offset at the top of the 330251881Speter tree, so that we can insert the new data (or search for existing 331251881Speter ranges) to the right of the root. This makes cleaning up the 332251881Speter tree after an insert much simpler, and -- incidentally -- makes 333251881Speter the whole range index magic work. */ 334251881Speter if (offset < tree->offset && tree->left != NULL) 335251881Speter { 336251881Speter if (tree->left->right == NULL) 337251881Speter { 338251881Speter /* A single right rotation is enough. */ 339251881Speter range_index_node_t *const node = tree->left; 340251881Speter tree->left = node->right; /* Which is always NULL. */ 341251881Speter node->right = tree; 342251881Speter tree = node; 343251881Speter } 344251881Speter else 345251881Speter { 346251881Speter /* Slide down to the rightmost node in the left subtree. */ 347251881Speter range_index_node_t **nodep = &tree->left; 348251881Speter while ((*nodep)->right != NULL) 349251881Speter nodep = &(*nodep)->right; 350251881Speter 351251881Speter /* Now move this node to root in one giant promotion. */ 352251881Speter right = tree; 353251881Speter left = tree->left; 354251881Speter tree = *nodep; 355251881Speter *nodep = tree->left; 356251881Speter right->left = tree->right; /* Which is always NULL, too. */ 357251881Speter tree->left = left; 358251881Speter tree->right = right; 359251881Speter } 360251881Speter } 361251881Speter 362251881Speter /* Sanity check ... */ 363251881Speter assert((offset >= tree->offset) 364251881Speter || ((tree->left == NULL) 365251881Speter && (tree->prev == NULL))); 366251881Speter ndx->tree = tree; 367251881Speter} 368251881Speter 369251881Speter 370251881Speter/* Remove all ranges from NDX that fall into the root's range. To 371251881Speter keep the range index as small as possible, we must also remove 372251881Speter nodes that don't fall into the new range, but have become redundant 373251881Speter because the new range overlaps the beginning of the next range. 374251881Speter Like this: 375251881Speter 376251881Speter new-range: |-----------------| 377251881Speter range-1: |-----------------| 378251881Speter range-2: |--------------------| 379251881Speter 380251881Speter Before new-range was inserted, range-1 and range-2 were both 381251881Speter necessary. Now the union of new-range and range-2 completely covers 382251881Speter range-1, which has become redundant now. 383251881Speter 384251881Speter FIXME: But, of course, there's a catch. range-1 must still remain 385251881Speter in the tree if we want to optimize the number of target copy ops in 386251881Speter the case were a copy falls within range-1, but starts before 387251881Speter range-2 and ends after new-range. */ 388251881Speter 389251881Speterstatic void 390251881Speterdelete_subtree(range_index_t *ndx, range_index_node_t *node) 391251881Speter{ 392251881Speter if (node != NULL) 393251881Speter { 394251881Speter delete_subtree(ndx, node->left); 395251881Speter delete_subtree(ndx, node->right); 396251881Speter free_range_index_node(ndx, node); 397251881Speter } 398251881Speter} 399251881Speter 400251881Speterstatic void 401251881Speterclean_tree(range_index_t *ndx, apr_size_t limit) 402251881Speter{ 403251881Speter apr_size_t top_offset = limit + 1; 404251881Speter range_index_node_t **nodep = &ndx->tree->right; 405251881Speter while (*nodep != NULL) 406251881Speter { 407251881Speter range_index_node_t *const node = *nodep; 408251881Speter apr_size_t const offset = 409251881Speter (node->right != NULL && node->right->offset < top_offset 410251881Speter ? node->right->offset 411251881Speter : top_offset); 412251881Speter 413251881Speter if (node->limit <= limit 414251881Speter || (node->offset < limit && offset < limit)) 415251881Speter { 416251881Speter *nodep = node->right; 417251881Speter node->right = NULL; 418251881Speter delete_subtree(ndx, node); 419251881Speter } 420251881Speter else 421251881Speter { 422251881Speter top_offset = node->offset; 423251881Speter nodep = &node->left; 424251881Speter } 425251881Speter } 426251881Speter} 427251881Speter 428251881Speter 429251881Speter/* Add a range [OFFSET, LIMIT) into NDX. If NDX already contains a 430251881Speter range that encloses [OFFSET, LIMIT), do nothing. Otherwise, remove 431251881Speter all ranges from NDX that are superseded by the new range. 432251881Speter NOTE: The range index must be splayed to OFFSET! */ 433251881Speter 434251881Speterstatic void 435251881Speterinsert_range(apr_size_t offset, apr_size_t limit, apr_size_t target_offset, 436251881Speter range_index_t *ndx) 437251881Speter{ 438251881Speter range_index_node_t *node = NULL; 439251881Speter 440251881Speter if (ndx->tree == NULL) 441251881Speter { 442251881Speter node = alloc_range_index_node(ndx, offset, limit, target_offset); 443251881Speter ndx->tree = node; 444251881Speter } 445251881Speter else 446251881Speter { 447251881Speter if (offset == ndx->tree->offset 448251881Speter && limit > ndx->tree->limit) 449251881Speter { 450251881Speter ndx->tree->limit = limit; 451251881Speter ndx->tree->target_offset = target_offset; 452251881Speter clean_tree(ndx, limit); 453251881Speter } 454251881Speter else if (offset > ndx->tree->offset 455251881Speter && limit > ndx->tree->limit) 456251881Speter { 457251881Speter /* We have to make the same sort of checks as clean_tree() 458251881Speter does for superseded ranges. Have to merge these someday. */ 459251881Speter 460251881Speter const svn_boolean_t insert_range_p = 461251881Speter (!ndx->tree->next 462251881Speter || ndx->tree->limit < ndx->tree->next->offset 463251881Speter || limit > ndx->tree->next->limit); 464251881Speter 465251881Speter if (insert_range_p) 466251881Speter { 467251881Speter /* Again, we have to check if the new node and the one 468251881Speter to the left of the root override root's range. */ 469251881Speter if (ndx->tree->prev && ndx->tree->prev->limit > offset) 470251881Speter { 471251881Speter /* Replace the data in the splayed node. */ 472251881Speter ndx->tree->offset = offset; 473251881Speter ndx->tree->limit = limit; 474251881Speter ndx->tree->target_offset = target_offset; 475251881Speter } 476251881Speter else 477251881Speter { 478251881Speter /* Insert the range to the right of the splayed node. */ 479251881Speter node = alloc_range_index_node(ndx, offset, limit, 480251881Speter target_offset); 481251881Speter if ((node->next = ndx->tree->next) != NULL) 482251881Speter node->next->prev = node; 483251881Speter ndx->tree->next = node; 484251881Speter node->prev = ndx->tree; 485251881Speter 486251881Speter node->right = ndx->tree->right; 487251881Speter ndx->tree->right = NULL; 488251881Speter node->left = ndx->tree; 489251881Speter ndx->tree = node; 490251881Speter } 491251881Speter clean_tree(ndx, limit); 492251881Speter } 493251881Speter else 494251881Speter /* Ignore the range */; 495251881Speter } 496251881Speter else if (offset < ndx->tree->offset) 497251881Speter { 498251881Speter assert(ndx->tree->left == NULL); 499251881Speter 500251881Speter /* Insert the range left of the splayed node */ 501251881Speter node = alloc_range_index_node(ndx, offset, limit, target_offset); 502251881Speter node->left = node->prev = NULL; 503251881Speter node->right = node->next = ndx->tree; 504251881Speter ndx->tree = node->next->prev = node; 505251881Speter clean_tree(ndx, limit); 506251881Speter } 507251881Speter else 508251881Speter /* Ignore the range */; 509251881Speter } 510251881Speter} 511251881Speter 512251881Speter 513251881Speter 514251881Speter/* ==================================================================== */ 515251881Speter/* Juggling with lists of ranges. */ 516251881Speter 517251881Speter/* Allocate a node and add it to the range list. LIST is the head of 518251881Speter the range list, TAIL is the last node in the list. NDX holds the 519251881Speter freelist; OFFSET, LIMIT and KIND are node data. */ 520251881Speterstatic range_list_node_t * 521251881Speteralloc_range_list(range_list_node_t **list, 522251881Speter range_list_node_t **tail, 523251881Speter range_index_t *ndx, 524251881Speter enum range_kind kind, 525251881Speter apr_size_t offset, 526251881Speter apr_size_t limit, 527251881Speter apr_size_t target_offset) 528251881Speter{ 529251881Speter range_list_node_t *const node = alloc_block(ndx->pool, &ndx->free_list); 530251881Speter node->kind = kind; 531251881Speter node->offset = offset; 532251881Speter node->limit = limit; 533251881Speter node->target_offset = target_offset; 534251881Speter if (*list == NULL) 535251881Speter { 536251881Speter node->prev = node->next = NULL; 537251881Speter *list = *tail = node; 538251881Speter } 539251881Speter else 540251881Speter { 541251881Speter node->prev = *tail; 542251881Speter node->next = NULL; 543251881Speter (*tail)->next = node; 544251881Speter *tail = node; 545251881Speter } 546251881Speter return *list; 547251881Speter} 548251881Speter 549251881Speter/* Free a range list. LIST is the head of the list, NDX holds the freelist. */ 550251881Speterstatic void 551251881Speterfree_range_list(range_list_node_t *list, range_index_t *ndx) 552251881Speter{ 553251881Speter while (list) 554251881Speter { 555251881Speter range_list_node_t *const node = list; 556251881Speter list = node->next; 557251881Speter free_block(node, &ndx->free_list); 558251881Speter } 559251881Speter} 560251881Speter 561251881Speter 562251881Speter/* Based on the data in NDX, build a list of ranges that cover 563251881Speter [OFFSET, LIMIT) in the "virtual" source data. 564251881Speter NOTE: The range index must be splayed to OFFSET! */ 565251881Speter 566251881Speterstatic range_list_node_t * 567251881Speterbuild_range_list(apr_size_t offset, apr_size_t limit, range_index_t *ndx) 568251881Speter{ 569251881Speter range_list_node_t *range_list = NULL; 570251881Speter range_list_node_t *last_range = NULL; 571251881Speter range_index_node_t *node = ndx->tree; 572251881Speter 573251881Speter while (offset < limit) 574251881Speter { 575251881Speter if (node == NULL) 576251881Speter return alloc_range_list(&range_list, &last_range, ndx, 577251881Speter range_from_source, 578251881Speter offset, limit, 0); 579251881Speter 580251881Speter if (offset < node->offset) 581251881Speter { 582251881Speter if (limit <= node->offset) 583251881Speter return alloc_range_list(&range_list, &last_range, ndx, 584251881Speter range_from_source, 585251881Speter offset, limit, 0); 586251881Speter else 587251881Speter { 588251881Speter alloc_range_list(&range_list, &last_range, ndx, 589251881Speter range_from_source, 590251881Speter offset, node->offset, 0); 591251881Speter offset = node->offset; 592251881Speter } 593251881Speter } 594251881Speter else 595251881Speter { 596251881Speter /* TODO: (Potential optimization) Investigate if it would 597251881Speter make sense to forbid short range_from_target lengths 598251881Speter (this comment originally said "shorter than, say, 599251881Speter VD_KEY_SIZE (see vdelta.c)", but Subversion no longer 600251881Speter uses vdelta). */ 601251881Speter 602251881Speter if (offset >= node->limit) 603251881Speter node = node->next; 604251881Speter else 605251881Speter { 606251881Speter const apr_size_t target_offset = 607251881Speter offset - node->offset + node->target_offset; 608251881Speter 609251881Speter if (limit <= node->limit) 610251881Speter return alloc_range_list(&range_list, &last_range, ndx, 611251881Speter range_from_target, 612251881Speter offset, limit, target_offset); 613251881Speter else 614251881Speter { 615251881Speter alloc_range_list(&range_list, &last_range, ndx, 616251881Speter range_from_target, 617251881Speter offset, node->limit, target_offset); 618251881Speter offset = node->limit; 619251881Speter node = node->next; 620251881Speter } 621251881Speter } 622251881Speter } 623251881Speter } 624251881Speter 625251881Speter /* A range's offset isn't smaller than its limit? Impossible! */ 626251881Speter SVN_ERR_MALFUNCTION_NO_RETURN(); 627251881Speter} 628251881Speter 629251881Speter 630251881Speter/* Copy the instructions from WINDOW that define the range [OFFSET, 631251881Speter LIMIT) in WINDOW's target stream to TARGET_OFFSET in the window 632251881Speter represented by BUILD_BATON. HINT is a position in the instructions 633251881Speter array that helps finding the position for OFFSET. A safe default 634251881Speter is 0. Use NDX to find the instructions in WINDOW. Allocate space 635251881Speter in BUILD_BATON from POOL. */ 636251881Speter 637251881Speterstatic void 638251881Spetercopy_source_ops(apr_size_t offset, apr_size_t limit, 639251881Speter apr_size_t target_offset, 640251881Speter apr_size_t hint, 641251881Speter svn_txdelta__ops_baton_t *build_baton, 642251881Speter const svn_txdelta_window_t *window, 643251881Speter const offset_index_t *ndx, 644251881Speter apr_pool_t *pool) 645251881Speter{ 646251881Speter apr_size_t op_ndx = search_offset_index(ndx, offset, hint); 647251881Speter for (;; ++op_ndx) 648251881Speter { 649251881Speter const svn_txdelta_op_t *const op = &window->ops[op_ndx]; 650251881Speter const apr_size_t *const off = &ndx->offs[op_ndx]; 651289180Speter const apr_size_t fix_offset = (offset > off[0] ? offset - off[0] : 0); 652289180Speter const apr_size_t fix_limit = (off[0] >= limit ? 0 653289180Speter : (off[1] > limit ? off[1] - limit : 0)); 654251881Speter 655289180Speter /* Ideally, we'd do this check before assigning fix_offset and 656289180Speter fix_limit; but then we couldn't make them const whilst still 657289180Speter adhering to C90 rules. Instead, we're going to assume that a 658289180Speter smart optimizing compiler will reorder this check before the 659289180Speter local variable initialization. */ 660251881Speter if (off[0] >= limit) 661251881Speter break; 662251881Speter 663251881Speter /* It would be extremely weird if the fixed-up op had zero length. */ 664251881Speter assert(fix_offset + fix_limit < op->length); 665251881Speter 666251881Speter if (op->action_code != svn_txdelta_target) 667251881Speter { 668251881Speter /* Delta ops that don't depend on the virtual target can be 669251881Speter copied to the composite unchanged. */ 670251881Speter const char *const new_data = (op->action_code == svn_txdelta_new 671251881Speter ? (window->new_data->data 672251881Speter + op->offset + fix_offset) 673251881Speter : NULL); 674251881Speter 675251881Speter svn_txdelta__insert_op(build_baton, op->action_code, 676251881Speter op->offset + fix_offset, 677251881Speter op->length - fix_offset - fix_limit, 678251881Speter new_data, pool); 679251881Speter } 680251881Speter else 681251881Speter { 682251881Speter /* The source of a target copy must start before the current 683251881Speter offset in the (virtual) target stream. */ 684251881Speter assert(op->offset < off[0]); 685251881Speter 686251881Speter if (op->offset + op->length - fix_limit <= off[0]) 687251881Speter { 688251881Speter /* The recursion _must_ end, otherwise the delta has 689251881Speter circular references, and that is not possible. */ 690251881Speter copy_source_ops(op->offset + fix_offset, 691251881Speter op->offset + op->length - fix_limit, 692251881Speter target_offset, 693251881Speter op_ndx, 694251881Speter build_baton, window, ndx, pool); 695251881Speter } 696251881Speter else 697251881Speter { 698251881Speter /* This is an overlapping target copy. 699251881Speter The idea here is to transpose the pattern, then generate 700251881Speter another overlapping copy. */ 701251881Speter const apr_size_t ptn_length = off[0] - op->offset; 702251881Speter const apr_size_t ptn_overlap = fix_offset % ptn_length; 703251881Speter apr_size_t fix_off = fix_offset; 704251881Speter apr_size_t tgt_off = target_offset; 705251881Speter assert(ptn_length > ptn_overlap); 706251881Speter 707289180Speter /* Unconditionally issue the second subrange of the 708289180Speter pattern. This is always correct, since the outer 709289180Speter condition already verifies that there is an overlap 710289180Speter in the target copy. */ 711289180Speter { 712289180Speter const apr_size_t length = 713289180Speter MIN(op->length - fix_off - fix_limit, 714289180Speter ptn_length - ptn_overlap); 715289180Speter copy_source_ops(op->offset + ptn_overlap, 716289180Speter op->offset + ptn_overlap + length, 717289180Speter tgt_off, 718289180Speter op_ndx, 719289180Speter build_baton, window, ndx, pool); 720289180Speter fix_off += length; 721289180Speter tgt_off += length; 722289180Speter } 723251881Speter 724251881Speter assert(fix_off + fix_limit <= op->length); 725251881Speter if (ptn_overlap > 0 726251881Speter && fix_off + fix_limit < op->length) 727251881Speter { 728251881Speter /* Issue the first subrange in the pattern. */ 729251881Speter const apr_size_t length = 730251881Speter MIN(op->length - fix_off - fix_limit, ptn_overlap); 731251881Speter copy_source_ops(op->offset, 732251881Speter op->offset + length, 733251881Speter tgt_off, 734251881Speter op_ndx, 735251881Speter build_baton, window, ndx, pool); 736251881Speter fix_off += length; 737251881Speter tgt_off += length; 738251881Speter } 739251881Speter 740251881Speter assert(fix_off + fix_limit <= op->length); 741251881Speter if (fix_off + fix_limit < op->length) 742251881Speter { 743251881Speter /* Now multiply the pattern */ 744251881Speter svn_txdelta__insert_op(build_baton, svn_txdelta_target, 745251881Speter tgt_off - ptn_length, 746251881Speter op->length - fix_off - fix_limit, 747251881Speter NULL, pool); 748251881Speter } 749251881Speter } 750251881Speter } 751251881Speter 752251881Speter /* Adjust the target offset for the next op in the list. */ 753251881Speter target_offset += op->length - fix_offset - fix_limit; 754251881Speter } 755251881Speter} 756251881Speter 757251881Speter 758251881Speter 759251881Speter/* ==================================================================== */ 760251881Speter/* Bringing it all together. */ 761251881Speter 762251881Speter 763251881Spetersvn_txdelta_window_t * 764251881Spetersvn_txdelta_compose_windows(const svn_txdelta_window_t *window_A, 765251881Speter const svn_txdelta_window_t *window_B, 766251881Speter apr_pool_t *pool) 767251881Speter{ 768251881Speter svn_txdelta__ops_baton_t build_baton = { 0 }; 769251881Speter svn_txdelta_window_t *composite; 770251881Speter apr_pool_t *subpool = svn_pool_create(pool); 771251881Speter offset_index_t *offset_index = create_offset_index(window_A, subpool); 772251881Speter range_index_t *range_index = create_range_index(subpool); 773251881Speter apr_size_t target_offset = 0; 774251881Speter int i; 775251881Speter 776251881Speter /* Read the description of the delta composition algorithm in 777251881Speter notes/fs-improvements.txt before going any further. 778251881Speter You have been warned. */ 779251881Speter build_baton.new_data = svn_stringbuf_create_empty(pool); 780251881Speter for (i = 0; i < window_B->num_ops; ++i) 781251881Speter { 782251881Speter const svn_txdelta_op_t *const op = &window_B->ops[i]; 783251881Speter if (op->action_code != svn_txdelta_source) 784251881Speter { 785251881Speter /* Delta ops that don't depend on the source can be copied 786251881Speter to the composite unchanged. */ 787251881Speter const char *const new_data = 788251881Speter (op->action_code == svn_txdelta_new 789251881Speter ? window_B->new_data->data + op->offset 790251881Speter : NULL); 791251881Speter svn_txdelta__insert_op(&build_baton, op->action_code, 792251881Speter op->offset, op->length, 793251881Speter new_data, pool); 794251881Speter } 795251881Speter else 796251881Speter { 797251881Speter /* NOTE: Remember that `offset' and `limit' refer to 798251881Speter positions in window_B's _source_ stream, which is the 799251881Speter same as window_A's _target_ stream! */ 800251881Speter const apr_size_t offset = op->offset; 801251881Speter const apr_size_t limit = op->offset + op->length; 802251881Speter range_list_node_t *range_list, *range; 803251881Speter apr_size_t tgt_off = target_offset; 804251881Speter 805251881Speter splay_range_index(offset, range_index); 806251881Speter range_list = build_range_list(offset, limit, range_index); 807251881Speter 808251881Speter for (range = range_list; range; range = range->next) 809251881Speter { 810251881Speter if (range->kind == range_from_target) 811251881Speter svn_txdelta__insert_op(&build_baton, svn_txdelta_target, 812251881Speter range->target_offset, 813251881Speter range->limit - range->offset, 814251881Speter NULL, pool); 815251881Speter else 816251881Speter copy_source_ops(range->offset, range->limit, tgt_off, 0, 817251881Speter &build_baton, window_A, offset_index, 818251881Speter pool); 819251881Speter 820251881Speter tgt_off += range->limit - range->offset; 821251881Speter } 822251881Speter assert(tgt_off == target_offset + op->length); 823251881Speter 824251881Speter free_range_list(range_list, range_index); 825251881Speter insert_range(offset, limit, target_offset, range_index); 826251881Speter } 827251881Speter 828251881Speter /* Remember the new offset in the would-be target stream. */ 829251881Speter target_offset += op->length; 830251881Speter } 831251881Speter 832251881Speter svn_pool_destroy(subpool); 833251881Speter 834251881Speter composite = svn_txdelta__make_window(&build_baton, pool); 835251881Speter composite->sview_offset = window_A->sview_offset; 836251881Speter composite->sview_len = window_A->sview_len; 837251881Speter composite->tview_len = window_B->tview_len; 838251881Speter return composite; 839251881Speter} 840