subversion/libsvn_delta/compose_delta.c

147   offset_index_t *ndx = apr_palloc(pool, sizeof(*ndx));
151   ndx->length = window->num_ops;
152   ndx->offs = apr_palloc(pool, (ndx->length + 1) * sizeof(*ndx->offs));
154   for (i = 0; i < ndx->length; ++i)
156       ndx->offs[i] = offset;
159   ndx->offs[ndx->length] = offset;
161   return ndx;
171 search_offset_index(const offset_index_t *ndx,
177   assert(offset < ndx->offs[ndx->length]);
180   hi = ndx->length;
189       if (offset < ndx->offs[hint])
191       else if (offset < ndx->offs[hint+1])
201       if (offset < ndx->offs[op])
208   assert(ndx->offs[lo] <= offset && offset < ndx->offs[lo + 1]);
230   range_index_t *ndx = apr_palloc(pool, sizeof(*ndx));
231   ndx->tree = NULL;
232   ndx->pool = pool;
233   ndx->free_list = NULL;
234   return ndx;
239 alloc_range_index_node(range_index_t *ndx,
244   range_index_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
255 free_range_index_node(range_index_t *ndx, range_index_node_t *node)
261   free_block(node, &ndx->free_list);
268 splay_range_index(apr_size_t offset, range_index_t *ndx)
270   range_index_node_t *tree = ndx->tree;
369   ndx->tree = tree;
393 delete_subtree(range_index_t *ndx, range_index_node_t *node)
397       delete_subtree(ndx, node->left);
398       delete_subtree(ndx, node->right);
399       free_range_index_node(ndx, node);
404 clean_tree(range_index_t *ndx, apr_size_t limit)
407   range_index_node_t **nodep = &ndx->tree->right;
421           delete_subtree(ndx, node);
439              range_index_t *ndx)
443   if (ndx->tree == NULL)
445       node = alloc_range_index_node(ndx, offset, limit, target_offset);
446       ndx->tree = node;
450       if (offset == ndx->tree->offset
451           && limit > ndx->tree->limit)
453           ndx->tree->limit = limit;
454           ndx->tree->target_offset = target_offset;
455           clean_tree(ndx, limit);
457       else if (offset > ndx->tree->offset
458                && limit > ndx->tree->limit)
464             (!ndx->tree->next
465              || ndx->tree->limit < ndx->tree->next->offset
466              || limit > ndx->tree->next->limit);
472               if (ndx->tree->prev && ndx->tree->prev->limit > offset)
475                   ndx->tree->offset = offset;
476                   ndx->tree->limit = limit;
477                   ndx->tree->target_offset = target_offset;
482                   node = alloc_range_index_node(ndx, offset, limit,
484                   if ((node->next = ndx->tree->next) != NULL)
486                   ndx->tree->next = node;
487                   node->prev = ndx->tree;
489                   node->right = ndx->tree->right;
490                   ndx->tree->right = NULL;
491                   node->left = ndx->tree;
492                   ndx->tree = node;
494               clean_tree(ndx, limit);
499       else if (offset < ndx->tree->offset)
501           assert(ndx->tree->left == NULL);
504           node = alloc_range_index_node(ndx, offset, limit, target_offset);
506           node->right = node->next = ndx->tree;
507           ndx->tree = node->next->prev = node;
508           clean_tree(ndx, limit);
527                  range_index_t *ndx,
533   range_list_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
555 free_range_list(range_list_node_t *list, range_index_t *ndx)
561       free_block(node, &ndx->free_list);
571 build_range_list(apr_size_t offset, apr_size_t limit, range_index_t *ndx)
575   range_index_node_t *node = ndx->tree;
580         return alloc_range_list(&range_list, &last_range, ndx,
587             return alloc_range_list(&range_list, &last_range, ndx,
592               alloc_range_list(&range_list, &last_range, ndx,
614                 return alloc_range_list(&range_list, &last_range, ndx,
619                   alloc_range_list(&range_list, &last_range, ndx,
647                 const offset_index_t *ndx,
650   apr_size_t op_ndx = search_offset_index(ndx, offset, hint);
654       const apr_size_t *const off = &ndx->offs[op_ndx];
695                               build_baton, window, ndx, pool);
721                                   build_baton, window, ndx, pool);
737                                   build_baton, window, ndx, pool);